Perbedaan Sistem Terdistribusi dengan Sistem Operasi Terdistribusi

A. Sistem Terdistribusi/Sistem Tersebar

Sistem terdistribusi adalah sekumpulan prosesor yang tidak saling berbagi memori atau clock dan terhubung melalui jaringan komunikasi yang bervariasi, yaitu melalui Local Area Network ataupun melalui Wide Area Network. Prosesor dalam sistem terdistribusi bervariasi, dapat berupa small microprocessor, workstation, minicomputer, dan lain sebagainya. Berikut adalah ilustrasi struktur sistem terdistribusi:


Karakteristik sistem terdistribusi adalah sebagai berikut:
1. Concurrency of components. Pengaksesan suatu komponen/sumber daya (segala hal yang dapat digunakan bersama dalam jaringan komputer, meliputi H/W dan S/W) secara bersamaan. Contoh: Beberapa pemakai browser mengakses halaman web secara bersamaan
2. No global clock. Hal ini menyebabkan kesulitan dalam mensinkronkan waktu seluruh komputer/perangkat yang terlibat. Dapat berpengaruh pada pengiriman pesan/data, seperti saat beberapa proses berebut ingin masuk ke critical session.
3. Independent failures of components. Setiap komponen/perangkat dapat mengalami kegagalan namun komponen/perangkat lain tetap berjalan dengan baik.


Ada empat alasan utama untuk membangun sistem terdistribusi, yaitu:
1. Resource Sharing (sharing sumberdaya)
2. Computation Speedup (mempercepat proses komputasi)
3. Reliability (kemudahan)
4. Communication. (komunikasi)


Tantangan-tantangan yang harus dipenuhi oleh sebuah sistem terdistribusi:
1. Keheterogenan perangkat/multiplisitas perangkat.
2. Keterbukaan.
3. Keamanan
4. Penangan kegagalan.
5. Concurrency of components
6. Transparansi


B. Sistem Operasi Terdistribusi/Sistem Operasi Tersebar

Sistem operasi terdistribusi adalah salah satu implementasi dari sistem terdistribusi, di mana sekumpulan komputer dan prosesor yang heterogen terhubung dalam satu jaringan. Koleksi-koleksi dari objek-objek ini secara tertutup bekerja secara bersama-sama untuk melakukan suatu tugas atau pekerjaan tertentu. Tujuan utamanya adalah untuk memberikan hasil secara lebih, terutama dalam:

1. file system
2. name space
3. Waktu pengolahan
4. Keamanan
5. Akses ke seluruh resources, seperti prosesor, memori, penyimpanan sekunder, dan perangakat keras.

Sistem operasi terdistribusi bertindak sebagai sebuah infrastruktur/rangka dasar untuk network-transparent resource management. Infrastruktur mengatur low-level resources (seperti Processor, memory, network interface dan peripheral device yang lain) untuk menyediakan sebuah platform untuk pembentukan/penyusunan higher-level resources(seperti Spreadsheet, electronic mail messages, windows).

Dalam sistem operasi terdistribusi, user mengakses sumber daya jarak jauh (remote resources) sama halnya dengan mengakses sumber daya lokal (local resources). Migrasi data dan proses dari satu situs ke situs yang lain dikontrol oleh sistem operasi terdistribusi.

Berikut ini adalah fitur-fitur yang didukung oleh sistem operasi terdistribusi:

1. Data Migration
2. Computation Migration.
3. Process Migration.

Contoh system operasi terdistribusi :

1. Chorus (Sun Microsystems)
2. GLUnix (University of California, Berkeley)
3. Spring System (Sun)


C. Rangkuman

Sistem terdistribusi adalah sekumpulan prosesor yang tidak saling berbagi memori atau clock. Setiap prosesornya memiliki memori lokal tersendiri dan berkomunikasi satu sama lain melalui jaringan komunikasi, seperti LAN atau WAN. Secara umum, topologi jaringan ada dua macam, yaitu fully connected network dan partially connected network yang terbagi lagi menjadi tiga jenis, yaitu tree-structured network, star network, dan ring network. Sistem operasi terdistribusi adalah salah satu implementasi dari sistem terdistribusi, di mana sekumpulan komputer dan prosesor yang heterogen terhubung dalam satu jaringan.Keuntungan dari sistem terdistribusi adalah memberikan akses bagi pengguna untuk dapat mengembangkan sumber daya sistem, peningkatan kecepatan komputasi, dan meningkatkan availibilitas atau ketersediaan dan reliabilitas data. Sebuah sistem terdistribusi harus menyediakan mekanisme sinkronisasi proses dan komunikasi, agar terhindar dari deadlock serta dapat mengatasi failure yang tidak muncul dalam sistem terpusat. 

sumber

Tugas SO 4

Proteksi Memory

 

Proteksi adalah suatu mekanisme untuk mengontrol akses oleh program, proses atau user pada sistem maupun resource dari user. Masalah proteksi pada banyak partisi dengan banyak proses di satu sistem secara bersamaan dikhawatirkan

proses menggunakan atau memodifikasi daerah yang dikuasai proses lain (yang bukan haknya). Bila kejadian ini terjadi, maka proses lain dapat terganggu dan hasil yang diperolehnya dapat menjadi kacau.

Mekanisme sistem proteksi yang harus disediakan sistem meliputi :

• Membedakan antara penggunaan yang sah dan yang tidak sah.
• Menentukan kontrol yang terganggu.
• Menetapkan cara pelaksanaan proteksi.

Proteksi pada monoprogramming sederhana.

Pada monoprogramming, pemakai mempunyai kendali penuh terhadap seluruh memori utama. Memori terbagi menjadi tiga bagian, yaitu :

a. Bagian yang berisi rutin-rutin sistem operasi.

b. Bagian yang berisi program pemakai.

c. Bagian yang tidak digunakan.

Masalah proteksi di monoprogramming adalah cara memproteksi rutin sistem operasi dari penghancuran program pemakai. Program pemakai dapat tersesat sehingga memanipulasi atau menempati ruang memori rutin sistem operasi. Aktivitas program pemakai ini dapat merusak sistem operasi. Sistem operasi harus diproteksi dari modifikasi program pemakai. Proteksi ini diimplementasikan menggunakan satu registe batas (boundary register) dipemroses.Setiap kali program pemakai mengacu alamat memori dibandingkan register batas untuk memastikan proses pemakai tidak merusak sistem operasi, yaitu tidak melewati nilai register batas. Register batas berisi alamat memori tertinggi yang dipakai sistem operasi.

Jika program pemakai mencoba memasuki sistem operasi, instruksi diintersepsi dan job diakhiri dan diberi pesan kesalahan. Untuk memperoleh layanan sistem operasi, program pemakai harus menggunakan instruksi spesifik meminta layanan sistem operasi.

Integritas sistem operasi terjaga dan program pemakai tidak merusak bagian sistem operasi.

Gambar  Proteksi pada monoprogramming

Gambar menunjukkan skema proteksi menggunakan register batas. Register batas menunjuk alamat terakhir sistem operasi. Bila program pemakai mengacu ke alamat daerah sistem operasi, pemroses menjadi fault  menyatakan terjadinya pelanggaran pengaksesan oleh proses pemakai.

MASALAH PROTEKSI DI MONOPROGRAMMING

Merupakan cara memproteksi rutin sistem operasi dari penghancuran program pemakai. Program pemakai dapat tersesat sehingga memanipulasi atau menempati ruang memori rutin sistem operasi. Aktivitas program pemakai ini dapat merusak sistem operasi. Untuk mengatasinya Sistem operasi harus diproteksi dari modifikasi program pemakai.

Proteksi ini diimplementasikan menggunakan satu register batas (boundary register) dipemroses.Setiap kali program pemakai mengacu alamat memori dibandingkan register batas untuk memastikan proses pemakai tidak merusak sistem operasi, yaitu tidak melewati nilai register batas.

PENGALOKASIAN MEMORI

• Salah satu tanggung jawab Sistem Operasi adalah mengontrol akses ke sumber daya sistem. Salah satunya adalah memori
• Pengalokasian memori dibagi 2 tipe, yaitu :
  • Pengalokasian berurutan (Contiguous Allocation)
  • Pengalokasian tidak berurutan (Non Contiguous Allocation)

PENGALOKASIAN BERURUTAN ( CONTIGOUS ALLICATION )

Tiap proses menempati satu blok tunggal lokasi memori yang berurutan.

Pada Multiprogramming memori utama harus mengalokasikan tempat untuk sistem operasi dan beberapa user proses

Memori harus mengakomodasi baik OS dan proses user

• Memori dibagi menjadi 2 partisi :
  • Untuk OS yang resident
  • Untuk Proses User

• Ada 2 tipe Contiguos Allocation :
  • Single Partition (Partisi Tunggal)

Multiple Partition (Partisi Banyak)

• Single Partition (Partisi Tunggal)
  • Pada skema ini, diasumsikan OS ditempatkan di memori rendah, dan proses user dieksekusi di memori tinggi
  • Proteksi dapat dilakukan dengan dengan menggunakan register relokasi dan register limit
    • Register relokasi à berisi nilai dari alamat fisik terkecil
    • Register Limit à berisi jangkauan alamat logika
    • Alamat logika harus lebih kecil dari register limit
• Multiple Partition (Partisi Banyak)
  • Ruang kosong à blok memori yang tersedia, ruang kosong dengan berbagai ukuran tersebar pada memori
  • Proses akan dialokasikan memori pada ruang kosong yang cukup besar untuk ditempatinya
  • OS akan mengelola informasi mengenai :
    • Partisi yang dialokasikan
    • Partisi bebas (ruang kosong)
  • Contoh multiple allocation

Ada 2 skema dalam Multiple Partition Allocation:

• Partisi Fixed Size (MFT)
  • Memori dibagi menjadi beberapa blok dengan ukuran tertentu yang seragam
  • Setiap partisi berisi tepat 1 proses
  • Digunakan oleh IBM OS/360 yang disebut Multiprogramming with a Fixed number of Task (MFT)
  • Masalah yang muncul pada MFT :
    • Sifat Program dinamis (alokasi dan dealokasi)
    • Memori yang teralokasi mungkin lebih besar dari memori yang diminta, sehingga mengakibatkan fragmentasi internal

• Pada MVT OS akan menyimpan tabel yang  berisi bagian memori yang tersedia dan yang digunakan:
  • Mula-mula,semua memori tersedia untuk proses user sebagai satu blok besar (large hole)
  • Bila proses datang dan memerlukan memori, dicari hole yang cukup untuk proses tersebut
  • Bila ditemukan, memory manager akan mengalokasikan sejumlah memori yang dibutuhkan dan menyimpan sisanya untuk permintaan berikutnya

• Contoh :
  • Diasumsikan tersedia memori 2560 Kb dan untuk OS 400 Kb. Sisa 2160 Kb digunakan untuk user proses
  • Diasumsikan terdapat 5 job (P1 s/d P5) terdapat pada input queue.

Diasumsikan penjadwalan FCFS digunakan untuk load job ke memori. Penjadwalan CPU secara Round Robin (quantum time =1) untuk penjadwalan job yang sudah ada di memori

MULTIPLE PARTITION

Menggunakan MVT, terdapat beberapa kali hole untuk ukuran berbeda:

• Bila proses datang dan memerlukan memori, dicari dari hole yang cukup untuk proses
• Dynamic Storage Allocation dapat dilibatkan untuk memenuhi permintaan ukuran n dari hole bebas :
  • First Fit à alokasi hole yang pertama yang memenuhi permintaan.
  • Best Fit à alokasi hole terkecil yang memenuhi permintaan.

• Dalam stratagi ini memerlukan pencarian keseluruhan hole, kecuali bila ukuran sudah terurut
  • Worst Fit à alokasi hole terbesar. Strategi ini memerlukan pencarian keseluruhan hole, kecuali bila ukuran sudah terurut
    • Diantara algoritma diatas, first fit dan best fit lebih baik dibandingkan worst fit dalam hal menurunkan waktu dan utilitas penyimpanan. Dan First Fit lebih cepat.
    • Diantara algoritma diatas, first fit dan best fit lebih baik dibandingkan worst fit dalam hal menurunkan waktu dan utilitas penyimpanan. Dan First Fit lebih cepat .

Keunggulan :

• Sederhana
• tidak akan terbentuk lubang-lubang (rongga) memori bersebaran
• Karena berurutan, proses dapat dieksekusi dengan cepat.

Kelemahannya :

• Dapat memboroskan Memori
• Tidak dapat memuatkan proses bila tidak ada satu blok memori yang mencukup

PENGALOKASIAN TAK BERURUTAN ( NON CONTIGUOS ALLOCATION )

Program dibagi menjadi beberapa blok atau segmen. Blokblok program ditempatkan di memori dalam potonganpotongan tanpa perlu saling berdekatan.

Teknik ini biasa digunakan pada sistem memori maya sebagai alokasi page-page dilakukan secara global.

• Paging
  • Paging adalah solusi untuk permasalahan fragmentasi external
  • Memori fisik dibagi ke dalam blok-blok ukuran tetap yang disebut “frame”
  • Memori logika dibagi ke dalam blok-blok dengan ukuran yang sama yang disebut “page”
  • Untuk menjalankan program berukuran n page, harus dicari frame kosong sebanyak n untuk meload program
  • Page table digunakan untuk translasikan alamat lojik ke alamat fisik
• Alamat yang dibangkitkan CPU dibagi menjadi :
  • Page number (p) à digunakan sebagai index ke page table. Page table berisi alamat basis dari setiap page pada memori fisik.
  • Page Offset (d) à dikombinasikan dengan alamat basis untuk mendefinisikan alamat memori fisik yang dikirim ke unit memori.
• Skema translasi alamat
• Model Paging
• Ukuran page atau frame ditentukan oleh hardware
  • Ukuran page merupakan bilangan 2 pangkat k mulai 512 sampai 8192 tergantung arsitektur komputer
• Segmentasi
  • Segmentasi adalah skema pengaturan memori yang mendukung user untuk melihat memori tersebut
  • Tiap-tiap segmen memiliki nama dan panjang.
  • Pandangan user mengenai memori.
  • Dukungan Hardware :
    • Pemetaan ke alamat fisik dilakukan dengan menggunakan tabel segmen, masing-masing berisi base dan limit

Keuntungan :

• Sistem dapat memanfaatkan memori utama secar lebih efisien
• Sistem operasi masih mampu memuatkan proses bila jumlah total lubang-lubang memori cukup untuk memuat proses yang akan dieksekusi

Kelemahan :

• Memerlukan pengendalian yang lebih rumit dan sulit
• Memori dapat menjadi banyak lubang tersebar (memori tak terpakai bertebaran).

Kerispatih - Lagu Rindu

Tugas SO 3

Solusi Masalah Critical Section dan Penjadwalan Preemptive dan Non Preemptive


Penjadwalan Preemptive

Penjadwalan CPU mungkin akan dijalankan ketika proses dalam keadaan:

1. Berubah dari running ke waiting state.
2. Berubah dari running ke ready state.
3. Berubah dari waiting ke ready state.
4. Dihentikan.

Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini bisa saja termasuk penjadwalan proses atau M/K. Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses. Membuat penjadwalan yang Preemptivemempunyai keuntungan yaitu sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.

Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebut CPU Bound. Terkadang juga suatu sistem mengalami kondisi yang disebut busywait, yaitu saat dimana sistem menunggu request input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut, proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari CPU. Dengan penjadwalanPreemptive, hal tersebut dapat dihindari.

Dengan kata lain, penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Penjadwalan nomor 1 dan 4 bersifat Non Preemptive sedangkan lainnyaPreemptive. Penjadwalan yang biasa digunakan sistem operasi dewasa ini biasanya bersifat Preemptive. Bahkan beberapa penjadwalan sistem operasi, contohnya Linux 2.6, mempunyai kemampuan Preemptive terhadap system call-nya ( preemptible kernel). Windows 95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT adalah beberapa contoh sistem operasi yang menerapkan penjadwalan Preemptive.

Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalanPreemptive disebut time slice/quantum. Penjadwalan berjalan setiap satu satuan time slice untuk memilih proses mana yang akan berjalan selanjutnya. Bila time slice terlalu pendek maka penjadwal akan memakan terlalu banyak waktu proses, tetapi bila time slice terlau lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari luar secepat yang diharapkan.

Penjadwalan Non Preemptive

Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di-interupt.

Penjadwalan Non Preemptive terjadi ketika proses hanya:

1. Berjalan dari running state sampai waiting state.
2. Dihentikan.

Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting stateataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untukplatforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalanPreemptive).

Solusi Critical Section Pada Perangkat Lunak

Dengan menggunakan algoritma-alogoritma yang nilai kebenarannya tidak tergantung pada asumsi-asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang bukan nol. Berikut Algoritmanya:

Algoritma I

Algoritma I mencoba mengatasi masalah critical section untuk dua proses. Algoritma ini menerapkan sistem bergilir kepada kedua proses yang ingin mengeksekusi critical section, sehingga kedua proses tersebut harus bergantian menggunakan critical section.

Gambar 1 Algoritma I

Algoritma ini menggunakan variabel bernama turn, nilai turn menentukan proses mana yang boleh memasuki critical section dan mengakses data yang di-sharing. Pada awalnya variabel turn diinisialisasi 0, artinya P0 yang boleh mengakses critical section. Jika turn= 0 dan P0 ingin menggunakan critical section, maka ia dapat mengakses critical section-nya. Setelah selesai mengeksekusi critical section, P0 akan mengubah turn menjadi 1, yang artinya giliran P1 tiba dan P1 diperbolehkan mengakses critical section. Ketika turn= 1 dan P0 ingin menggunakan critical section, maka P0 harus menunggu sampai P1 selesai menggunakan critical section dan mengubah turn menjadi 0.

Ketika suatu proses sedang menunggu, proses tersebut masuk ke dalam loop, dimana ia harus terus-menerus mengecek variabel turn sampai berubah menjadi gilirannya. Proses menunggu ini disebut busy waiting. Sebenarnya busy waitingmesti dihindari karena proses ini menggunakan CPU. Namun untuk kasus ini, penggunaan busy waiting diijinkan karena biasanya proses menunggu hanya berlangsung dalam waktu yang singkat.

Pada algoritma ini masalah muncul ketika ada proses yang mendapat giliran memasuki critical section tapi tidak menggunakan gilirannya sementara proses yang lain ingin mengakses critical section. Misalkan ketika turn= 1 dan P1 tidak menggunakan gilirannya maka turn tidak berubah dan tetap 1. Kemudian P0 ingin menggunakan critical section, maka ia harus menunggu sampai P1 menggunakan critical section dan mengubah turn menjadi 0. Kondisi ini tidak memenuhi syarat progress karena P0 tidak dapat memasuki critical sectionpadahal saat itu tidak ada yang menggunakan critical section dan ia harus menunggu P1 mengeksekusi non- critical section-nya sampai kembali memasuki critical section. Kondisi ini juga tidak memenuhi syarat bounded waiting karena jika pada gilirannya P1 mengakses critical section tapi P1 selesai mengeksekusi semua kode dan terminate, maka tidak ada jaminan P0 dapat mengakses critical section dan P0-pun harus menunggu selamanya.

Algoritma II

Algoritma II juga mencoba memecahkan masalah critical section untuk dua proses. Algoritma ini mengantisipasi masalah yang muncul pada algoritma I dengan mengubah penggunaan variabel turn dengan variabel flag. Variabel flagmenyimpan kondisi proses mana yang boleh masuk critical section. Proses yang membutuhkan akses ke critical section akan memberikan nilai flag-nya true. Sedangkan proses yang tidak membutuhkan critical section akan men- set nilai flagnya bernilai false.

Gambar 2 Algoritma II

Suatu proses diperbolehkan mengakses critical section apabila proses lain tidak membutuhkan critical section atau flag proses lain bernilai false. Tetapi apabila proses lain membutuhkan critical section (ditunjukkan dengan nilai flag-nyatrue), maka proses tersebut harus menunggu dan "mempersilakan" proses lain menggunakan critical section-nya. Disini terlihat bahwa sebelum memasukicritical section suatu proses melihat proses lain terlebih dahulu (melalui flag-nya), apakah proses lain membutuhkan critical section atau tidak.

Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan critical section. Jika P0 ingin mengaksescritical section, ia akan mengubah flag[0] menjadi true. Kemudian P0 akan mengecek apakah P1 juga membutuhkan critical section, jika flag[1] bernilaifalse maka P0 akan menggunakan critical section. Namun jika flag[1] bernilaitrue maka P0 harus menunggu P1 menggunakan critical section dan mengubahflag[1] menjadi false.

Pada algoritma ini masalah muncul ketika kedua proses secara bersamaan menginginkan critical section, kedua proses tersebut akan men- set masing-masing flag-nya menjadi true. P0 men- set flag[0] = true, P1 men- set flag[1] = true. Kemudian P0 akan mengecek apakah P1 membutuhkan critical section. P0 akan melihat bahwa flag[1] = true, maka P0 akan menunggu sampai P1 selesai menggunakan critical section. Namun pada saat bersamaan, P1 juga akan mengecek apakah P0 membutuhkan critical section atau tidak, ia akan melihat bahwa flag[0] = true, maka P1 juga akan menunggu P0 selesai menggunakan critical section-nya. Kondisi ini menyebabkan kedua proses yang membutuhkan critical section tersebut akan saling menunggu dan "saling mempersilahkan" proses lain untuk mengakses critical section, akibatnya malah tidak ada yang mengakses critical section. Kondisi ini menunjukkan bahwa Algoritma II tidak memenuhi syarat progress dan syarat bounded waiting, karena kondisi ini akan terus bertahan dan kedua proses harus menunggu selamanya untuk dapat mengakses critical section.

Algoritma III

Algoritma III ditemukan oleh G.L. Petterson pada tahun 1981 dan dikenal juga sebagai Algoritma Petterson. Petterson menemukan cara yang sederhana untuk mengatur proses agar memenuhi mutual exclusion. Algoritma ini adalah solusi untuk memecahkan masalah critical section pada dua proses. Ide dari algoritma ini adalah menggabungkan variabel yang di- sharing pada Algoritma I dan Algoritma II, yaitu variabel turn dan variabel flag. Sama seperti pada Algoritma I dan II, variabel turn menunjukkan giliran proses mana yang diperbolehkan memasuki critical section dan variabel flag menunjukkan apakah suatu proses membutuhkan akses ke critical section atau tidak.

Gambar 3 Algoritma III

Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan akses ke critical section. Kemudian jika suatu proses ingin memasuki critical section, ia akan mengubah flag-nya menjadi true (memberikan tanda bahwa ia butuh critical section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya tidak menginginkancritical section (flag-nya false), maka proses tersebut dapat menggunakancritical section, dan setelah selesai menggunakan critical section ia akan mengubah flag-nya menjadi false. Tetapi apabila proses lawannya juga menginginkan critical section maka proses lawan-lah yang dapat memasukicritical section, dan proses tersebut harus menunggu sampai proses lawan menyelesaikan critical section dan mengubah flag-nya menjadi false.

Misalkan ketika P0 membutuhkan critical section, maka P0 akan mengubahflag[0] = true, lalu P0 mengubah turn= 1. Jika P1 mempunyai flag[1] = false, (berapapun nilai turn) maka P0 yang dapat mengakses critical section. Namun apabila P1 juga membutuhkan critical section, karena flag[1] = true dan turn= 1, maka P1 yang dapat memasuki critical section dan P0 harus menunggu sampai P1 menyelesaikan critical section dan mengubah flag[1] = false, setelah itu barulah P0 dapat mengakses critical section.

Bagaimana bila kedua proses membutuhkan critical section secara bersamaan? Proses mana yang dapat mengakses critical section terlebih dahulu? Apabila kedua proses (P0 dan P1) datang bersamaan, kedua proses akan menset masing-masing flag menjadi true (flag[0] = true dan flag[1] = true), dalam kondisi ini P0 dapat mengubah turn = 1 dan P1 juga dapat mengubah turn = 0. Proses yang dapat mengakses critical section terlebih dahulu adalah proses yang terlebih dahulu mengubah turn menjadi turn lawannya. Misalkan P0 terlebih dahulu mengubah turn= 1, lalu P1 akan mengubah turn= 0, karena turn yang terakhir adalah 0 maka P0-lah yang dapat mengakses critical section terlebih dahulu dan P1 harus menunggu.

Algoritma III memenuhi ketiga syarat yang dibutuhkan. Syarat progress danbounded waiting yang tidak dipenuhi pada Algoritma I dan II dapat dipenuhi oleh algoritma ini karena ketika ada proses yang ingin mengakses critical section dan tidak ada yang menggunakan critical section maka dapat dipastikan ada proses yang bisa menggunakan critical section, dan proses tidak perlu menunggu selamanya untuk dapat masuk ke critical section.

Algoritma Tukang Roti

Algoritma Tukang Roti adalah solusi untuk masalah critical section pada n-buah proses. Algoritma ini juga dikenal sebagai Lamport's Baker Algorithm. Ide algoritma ini adalah dengan menggunakan prinsip penjadwalan seperti yang ada di tempat penjualan roti. Para pelanggan yang ingin membeli roti sebelumnya harus mengambil nomor urut terlebih dahulu dan urutan orang yang boleh membeli ditentukan oleh nomor urut yang dimiliki masing-masing pelanggan tersebut.

Prinsip algoritma ini untuk menentukan proses yang boleh mengakses critical section sama seperti ilustrasi tukang roti diatas. Proses diibaratkan pelanggan yang jumlahnya n-buah dan tiap proses yang membutuhkan critical sectiondiberi nomor yang menentukan proses mana yang diperbolehkan untuk masuk kedalam critical section. Nomor yang diberikan adalah sekuensial atau terurut, tapi seperti juga nomor urut yang ada di tukang roti, tidak ada jaminan bahwa tiap proses mendapat nomor urut yang berbeda. Untuk mengatasinya digunakan parameter lain yaitu proses ID. Dikarenakan tiap proses memiliki proses ID yang unik dan terurut maka dapat dipastikan hanya satu proses yang dapat mengakses critical section dalam satu waktu. Proses yang dapat mengakses critical section terlebih dahulu adalah proses yang memiliki nomor urut paling kecil. Apabila ada beberapa proses yang memiliki nomor yang sama maka proses yang mempunyai nomor ID paling kecil yang akan dilayani terlebih dahulu.

Kesimpulan :

Solusi critical section harus memenuhi ketiga syarat berikut:

1. Mutual Exclusion
2. Progress
3. Bounded Waiting

Algoritma I dan II terbukti tidak dapat memecahkan masalah critical sectionuntuk dua proses karena tidak memenuhi syarat progress dan bounded waiting. Algoritma yang dapat menyelesaikan masalah critical section pada dua proses adalah Algoritma III. Sedangkan untuk masalah critical section pada n-buah proses dapat diselesaikan dengan menggunakan Algoritma Tukang Roti

Solusi Critical Section pada Perangkat Keras

Tergantung pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi atau dengan mengunci suatu variabel tertentu.

sumber 1

sumber 2

sumber 3