proses sinkronisasi pada sistem operasi

Proses Sinkronisasi Pada Sistem Operasi

Konsep Interaksi

Dalam menjalankan fungsinya dalam sistem operasi, dibutuhkan interaksi antara beberapa proses yang berbeda. Interaksi tersebut bertujuan agar terjadi kesinambungan antar proses yang terjadi sehingga sistem operasi dapat berjalan sebagaimana mestinya. Interaksi tersebut dapat melalui sistem berbagi memori atau dengan cara saling berkirim pesan. Terkadang, beberapa pesan yang dikirim tidak dapat diterima seluruhnya oleh penerima dan menyebabkan informasi yang lain menjadi tidak valid, maka dibutuhkanlah sebuah mekanisme sinkronasi yang akan mengatur penerimaan dan pengiriman pesan sehingga kesalahan penerimaan pesan dapat diperkecil. Pesan yang dikirim dapat ditampung dalam penyangga sebelum diterima oleh penerima.

Interaksi antar proses dapat juga terjadi antara proses yang memiliki sistem berbeda. Dalam interaksi tersebut dikenal sebutan client dan server yang memungkinkan sistem yang berbeda untuk berinteraksi dengan menggunakan socket. Dalam interaksi tersebut dikenal juga RPC (Remote Procedure Call) yaitu metode yang memungkinkan sebuah sistem mengakses prosedur sistem lain dalam komputer berbeda.

Dalam interaksi antar proses, terkadang suatu proses saling menunggu proses yang lain sebelum melanjutkan prosesnya, sehingga proses-proses tersebut saling menunggu tanpa akhir, hal ini disebut deadlock. Jika deadlock terjadi dalam waktu lama, maka terjadilah starvation, yaitu suatu proses tidak mendapatkan resource yang dibutuhkan.

Sinkronisasi

Suatu proses yang bekerja bersama-sama dan saling berbagi data dapat mengakibatkan race condition atau pengaksesan data secara bersama-sama. Critical section adalah suatu segmen kode dari proses-proses itu yang yang memungkinkan terjadinya race condition. Untuk mengatasi masalah critical section ini, suatu data yang sedang diproses tidak boleh diganggu proses lain.

Solusi prasyarat critical section:

Mutual Exclusion.

Terjadi kemajuan (progress).

Ada batas waktu tunggu (bounded waiting).

Critical section dalam kernel:

Interupsi.

Page Fault .

Kernel code memanggil fungsi penjadwalan sendiri.

Solusi Critical Section

Solusi critical section harus memenuhi ketiga syarat berikut:

Mutual Exclusion

Progress

Bounded Waiting

Algoritma I dan II terbukti tidak dapat memecahkan masalah critical section untuk 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

Perangkat Sinkronisasi

v  Instruksi TestAndSet(). instruksi atomik yang dapat digunakan untuk menangani masalahcritical section.

v  Semafor. sebuah variabel yang hanya dapat diakses oleh dua buah operasi standar yaituincrement dan decrement. Dua buah jenis semafor, yaitu Binary Semaphore dan Counting Semaphore. Semafor berfungsi untuk menangani masalah critical section, mengatur alokasiresource, dan sinkronisasi antarproses.

v  Monitor. digunakan untuk menangani masalah yang muncul karena pemakaian semafor. Monitor menjamin mutual exclusion. Untuk menangani masalah sinkronisasi yang lebih rumit monitor menyediakan condition variable.

v  JVM. mengimplementasikan monitor. Monitor JVM bekerja dengan object locking danmethod-method wait() serta notify(). Monitor JVM dapat digunakan dengan menggunakan keyword synchronized.

Transaksi Atomik

Transaksi merupakan sekumpulan instruksi atau operasi yang menjalankan sebuah fungsi logis dan memiliki sifat atomicity, consistency, isolation, dan durability. Sifat atomicity pada transaksi menyebabkan transaksi tersebut akan dijalankan secara keseluruhan atau tidak sama sekali. Operasi-operasi pada transaksi atomik disimpan dalam log agar dapat dilakukan rolled-back jika terjadi kegagalan sistem. Dengan memanfaatkan log, pemulihan data dapat dilakukan dengan melakukan undo atau redo. Untuk menghemat waktu pada saat rolled-back, kita dapat memberikan operasi checkpoint pada transaksi sehingga kita tidak perlu memeriksa keseluruhan transaksi untuk memutuskan melakukan undo/redo.

Serialisasi diperlukan ketika beberapa transaksi atomik dijalankan secara bersamaan. Hal ini dimaksudkan agar sifat konsistensi hasil eksekusi transaksi dapat terpenuhi. Ada dua cara untuk menjaga agar penjadwalan bersifat serializable, yaitu protokol penguncian dan protokol berbasis waktu. Pada protokol penguncian, setiap data yang akan diakses harus dikunci oleh transaksi yang akan memakainya agar transaksi lain tidak bisa mengakses data yang sama. Sedangkan, pada protokol berbasis waktu, setiap transaksi diberikan suatu timestamp yang unik, sehingga dapat diketahui apakah transaksi tersebut sudah dijalankan atau belum. Protokol berbasis waktu dapat mengatasi masalah deadlock, sedangkan protokol penguncian tidak.

Sinkronisasi Linux

ada suatu saat dalam sebuah kernel, tidak terkecuali kernel LINUX, dapat terjadi concurrent access. Dalam hal ini diperlukan proteksi dalam kernel yang bersangkutan. Proteksi dapat dilakukan dengan sinkronisasi.

Sebuah proses memiliki bagian dimana bagian ini akan melakukan akses dan manipulasi data. Bagian ini disebut dengan critical section. Ketika sebuah proses sedang dijalankan dalam critical section nya, tidak ada proses lain yang boleh dijalankan dalam critical section nya.

Ada dua jenis concurrency yaitu pseudo-concurrency dan true-concurrency. Ada beberapa penyebab konkurensi kernel, diantaranya interrupt, softirqs dan tasklets, kernel preemption,sleeping dan synchronization with user-space, dan symmetrical multiprocessing.

Salah satu metode dalam kernel LINUX untuk sinkronisasi adalah atomic operations. Integer atomik adalah salah satu jenis dari atomic operations. Integer Atomik menyediakan instruksi yang dijalankan secara atomik (tanpa interrupt).

Locking yang paling umum digunakan dalam LINUX adalah spin lock. Spin lock adalah lock yang hanya dapat dilakukan oleh satu thread. Ketika sebuah thread yang akan dijalankan meminta spin lock yang sedang digunakan, maka thread ini akan loops menunggu sampai spin lock tersebut selesai digunakan oleh thread yang sedang berjalan.

Semafor dalam LINUX adalah sleeping locks. Ketika sebuah thread meminta semafor yang sedang digunakan, maka semafor akan meletakkan thread tersebut dalam wait queue dan menyebabkan thread tersebut masuk status sleep.

Symmetrical multiprocessing (SMP) mendukung adanya pengeksekusian secara paralel dua atau lebih thread oleh dua atau lebih processor. Kernel LINUX 2.0 adalah kernel LINUX pertama yang memperkenalkan konsep SMP.

Deadlocks

Deadlock adalah suatu keadaan dimana sistem seperti terhenti dikarenakan setiap proses memiliki sumber daya yang tidak bisa dibagi dan menunggu untuk mendapatkan sumber daya yang sedang dimiliki oleh proses lain

Starvation adalah keadaan dimana satu atau beberapa proses ‘kelaparan’ karena terus dan terus menunggu kebutuhan sumber dayanya dipenuhi. Namun, karena sumber daya tersebut tidak tersedia atau dialokasikan untuk proses lain, akhirnya proses yang membutuhkan tidak bisa memilikinya. Kondisi seperti ini merupakan akibat dari keadaan menunggu yang berkepanjangan.

Karakteristik terjadinya deadlock:

Mutual Exclusion .

Hold and Wait .

No Preemption .

Circular Wait .

Mekanisme penanganan deadlock:

Pengabaian. Ostrich Algorithm.

Pencegahan. Mencegah terjadinya salah satu kondisi deadlock.

Penghindaran. Memastikan sistem berada pada safe state dan dengan menggunakandeadlock avoidance algorithm.

Pendeteksian dan Pemulihan. Mekanisme pendeteksian menggunakan detection algorithm, sedangkan pemulihan dengan cara rollback and restart sistem ke safe state.

Diagram Graf

Deadlock adalah suatu kondisi dimana proses tidak berjalan lagi ataupun tidak ada komunikasi lagi antar proses di dalam sistem operasi. deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut.

Untuk mendeteksi deadlock dan menyelesaikannya dapat digunakan graf sebagai visualisasinya. Jika dalam graf terlihat adanya perputaran, maka proses tersebut memiliki potensi terjadideadlock. Namun, jika dalam graf tidak terlihat adanya perputaran, maka proses tersebut tidak akan terjadi deadlock.

implementasi graf dalam sistem operasi, yaitu penggunaannya untuk penanganan deadlock pada sistem operasi. Diantaranya adalah graf alokasi sumber daya dan graf tunggu.Graf alokasi sumber daya dan graf tunggu merupakan graf sederhana dan graf berarah. Dua graf tersebut adalah bentuk visualisasi dalam mendeteksi masalah deadlock pada sistem operasi.

Untuk mengetahui ada atau tidaknya deadlock dalam suatu graf alokasi sumber daya dapat dilihat dari perputaran dan sumber daya yang dimilikinya. Jika tidak ada perputaran berarti tidak deadlock. Jika ada perputaran, ada potensi terjadi deadlock. Sumber daya dengan instans tunggal dan perputaran pasti akan mengakibatkan deadlock.

Pada graf tunggu, deadlock terjadi jika dan hanya jika pada graf tersebut ada perputaran. Untuk mendeteksi adanya perputaran diperlukan operasi sebanyak n 2, dimana n adalah jumlah simpul dalam graf alokasi sumber daya.

Bounded-Buffer

Proses yang kooperatif bisa berbagi data melalui penukaran pesan. Pesan-pesan yang dikirim antar proses akan disimpan dalam sebuah antrian sementara, yaitu buffer. Jika kapasitas buffertersebut terbatas, maka dia disebut bounded-buffer. Untuk mencegah inkonsistensi data yang terjadi akibat akses data oleh proses kooperatif yang berjalan secara konkuren, maka diperlukan sinkronisasi antar proses-proses tersebut.

Permasalahan bounded-buffer ini diilustrasikan dalam proses produsen-konsumen. Masalah-masalah yang timbul adalah

buffer yang merupakan critical section, sehingga hanya boleh diakses satu proses pada satu waktu;

keadaan dimana produsen ingin menaruh data di antrian, namun antrian penuh

keadaan dimana konsumen ingin mengambil data dari antrian namun antrian kosong.

Untuk menyelesaikan masalah, digunakanlah perangkat sinkronisasi semafor. Semafor yang digunakan adalah

mutex. yang menjaga buffer hanya diakses satu proses pada satu waktu;

tempat_kosong. jumlah tempat kosong.

tempat_terisi. jumlah tempat terisi

Dengan demikian produsen yang ingin menaruh data atau konsumen yang ingin mengakses data harus memeriksa apakah proses lain sedang memakai buffer (menggunakan mutex) dan memeriksa apakah buffer penuh atau kosong (menggunakan tempat_kosong dan tempat_terisi).

Readers/Writers

Readers/Writers merupakan sebuah masalah klasik dalam contoh sinkronisasi untuk menjaga validitas data. Jika reader sedang mengakses data, reader-reader yang lain boleh ikut mengakses data, tapi writer harus menunggu sampai data tidak diakses siapapun. Jika writer sedang mengakses data, tidak boleh ada thread lain yang mengakses data. Semaphore digunakan untuk sinkronisasi antar thread (baik readers maupun writers).

Sinkronisasi Dengan Semafor

Program Hompimpah merupakan ilustrasi dimana sebuah thread memegang kendali sinkronisasi thread lainnya. Seperti yang dijelaskan dalam program masing-masing dari pemain saling mengendalikan satu sama lain, dengan menggunakan alat sinkronisasi yang bernama semafor. Semafor dalam program adalah semafor buatan berupa class Semafor yang dibuat dalam bahasa Java. Adapun di dalamnya terdapat 2 fungsi yaitu fungsi buka() dan fungsikunci() dengan fungsi-fungsi inilah masing-masing thread dapat mengendalikan satu sama lain

Sinkronisasi Pada Sistem Operasi

Posted by Fauzan Muntahal Posted on 10:23 PM with No comments

Apa itu Sinkronisasi ? kenapa Sistem Operasi Membutuhkan Sinkronisasi? Seperti kita ketahui bahwa hidup saling berkaitan satu sama lain, begitu juga Sinkronisasi Pada Sistem Operasi. Hal ini jika tidak ada penopang dalam menjalankan suatu sistem, maka akan menemui suatu kendala yang berakibat ketidakkonsistenan pada data, sehingga data tidak menjadi konkuren. 

Pengertian dari Sinkronisasi adalah Akses bebarengan untuk berbagi dua bersama dapat mengakibatkan inkosistensi data. Pemeliharaan konsistensi data memerlukan mekanisme untuk memastikan eksekusi dari proses kerjasama. 

Tujuan dari sinkronisasi itu sendiri ialah untuk menghindari terjadinya inkonsitensi data karena pengaksesan oleh beberapa proses yang berbeda serta untuk mengatur urutan jalannya proses-proses sehingga dapat berjalan dengan baik dan sesuai apa yang di harapkan.

Masalah pada Sistem Operasi Sinkronisasi bisa terdapat dari masalah lainnya, seperti   MasalahRace Condition  & Critical Section. 

Arti dari Race Conditon adalah situasi di mana beberapa proses mengakses dan memanipulasi data bersama pada saat besamaan.

Arti dari masalah Critical Section adalah sebuah segmen kode di mana sebuah proses yang mana sumber daya bersama diakses

Critical Section mempunyai beberapa kode :

Entry Section : kode yang digunakan untuk masuk ke dalam critical section

Critical Section : Kode di mana hanya ada satu proses yang dapat dieksekusi pada satu waktu.

Exit Section: akhir dari critical section, mengizinkan proses lain.

Remainder Section : kode istirahat setelah masuk ke critical section.

Kunci untuk mencegah masalah ini dan di situasi yang lain yang melibatkan shared memori, shared berkas, and shared sumber daya yang lain adalah menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan proses writing dan reading kepada shared data pada saat yang sama.

Bagaimana pun setiap kali sebuah proses mengakses shared memory atau shared berkas atau melakukan sesuatu yang kitis akan menggiring kepada race conditions. Bagian dari program dimana shaed memory diakses disebut Critical Section atau Critical Region. Walau pun dapat mencegah race conditions, tapi tidak cukup untuk melakukan kerjasama antar proses secara pararel dengan baik dan efisien dalam menggunakan shared data, kita butuh 4 kondisi agar menghasilkan solusi yang baik yakni :

Tidak ada dua proses secara bersamaan masuk ke dalam citical section.

Tidak ada asumsi mengenai kecepatan atau jumlah cpu.

Tidak ada proses yang berjalan di luar critical secion yang dapat mengeblok proses lain.

Tidak ada proses yang menunggu selamamya untuk masuk critical section.

Solusi untuk mengatasi masalah Critical Section, yaitu:

 Mutual exclution : Jika proses pi sedang mengeksekusi critical section-nya maka tidak ada proses lain yang dapat mengeksekusi dalam critical section mereka.

 Progress : Jika tidak ada proses yang sedang dieksekusi dalam critical section  dan ada beberapa proses yang ingin masuk ke critical section mereka, maka pemilihan proses yang akan masuk ke critical section berikutnya tidak bias ditunda.

Bounded Waiting :Suatu keterikatan harus ada pada sejumlah proses yang diijinkan masuk ke critical section mereka, setelah adanya proses yang meminta masuk ke critical section dan sebelum  permintaan itu diterima.

Akses bebarengan untuk berbagi dua bersama dapat mengakibatkan inkosistensi data. Pemeliharaan konsistensi data memerlukan mekanisme untuk memastikan eksekusi dari proses kerjasama.

Adapun pengertian lainnya yaitu  Sinkronisasiadalah proses pengaturan jalannya beberapa proses pada saat yang bersamaan. Akses berbarengan untuk berbagi dua atau bersamaan dapat mengakibatkan inkosistensi data. Pemeliharaan konsistensi data memerlukan mekanisme untuk memastikan eksekusi dari proses kerjasama.

Shared memory merupakan solusi ke masalah bounded-butter yang mengijinkan paling banyak n-1 materi dalam buffer pada waktu yang sama. Suatu solusi, jika semua N buffer digunakan tidaklah sederhana. Dimisalkan kita memdifikasi producer-consumer code dengan menambahkan suatu variable counter, dimulai dari 0 dan masing-masing waktu tambahan dari suatu item baru diberikan kepada buffer.

Tujuan utama sinkronisasi adalah untuk menghindari terjadinya inkonsitensi data karena pengaksesan oleh beberapa proses yang berbeda (mutual exclusion) serta untuk mengatur urutan jalannya proses-proses sehingga dapat berjalan dengan lancar dan terhindar dari deadlock dan starvation. Sinkronisasi umumnya dilakukan dengan bantuan perangkat sinkronisasi. Penyelesaian terhadap masalah ini sangat penting karena perkembangan teknologi sistem komputer menuju ke sistem multiprocessing, terdistribusi dan paralel yang mengharuskan adanya proses-proses kongkuren.

Sinkronisasi sederhananya  :  Saling bertukar data agar memiliki jumlah data yang sama.
tujuan utama mungkin lebih condong ke arah back-up (membuat cadangan)
tapi ada pula sinkronisasi jadwal kerja (kalender) untuk menciptakan suatu event yang tepat secara bersamaan diantara pelaku sinkronisasi. Sinkronisasi umumnya dilakukan dengan bantuan perangkat sinkronisasi.

1.     Race Condition

Race Condition adalah situasi di mana beberapa proses mengakses dan memanipulasi data bersama pada saat besamaan. Nilai akhir dari data bersama tersebut tergantung pada proses yang terakhir selesai. Untuk mencegah race condition, proses-proses yang berjalan besamaan harus di disinkronisasi.

Dalam beberapa sistem operasi, proses-proses yang berjalan bersamaan mungkin untuk membagi beberapa penyimpanan umum, masing-masing dapat melakukan proses baca (read) dan proses tulis (write). Penyimpanan bersama (shared storage) mungkin berada di memori utama atau berupa sebuah berkas bersama, lokasi dari memori bersama tidak merubah kealamian dari komunikasi atau masalah yang muncul. Untuk mengetahui bagaimana komunikasi antar proses bekerja, mari kita simak sebuah contoh sederhana, sebuah print spooler. Ketika sebuah proses ingin mencetak sebuah berkas, proses tersebut memasukkan nama berkas ke dalam sebuah spooler direktori yang khusus. Proses yang lain, printer daemon, secara periodik memeriksa untuk mengetahui jika ada banyak berkas yang akan dicetak, dan jika ada berkas yang sudah dicetak dihilangkan nama berkasnya dari direktori.

Contoh Race Condition

  int counter = 0;

  //Proses yang dilakukan oleh produsen

  item nextProduced;

  while (1) {

    while (counter == BUFFER_SIZE) { ... do nothing ... }

     buffer[in] = nextProduced;

     in = (in + 1) % BUFFER_SIZE;

    counter++;

 }

//Proses yang dilakukan oleh konsumen

 item nextConsumed;

 while (1) {

    while (counter == 0)            { ... do nothing ... }

    nextConsumed = buffer[out] ;

    out = (out + 1) % BUFFER_SIZE;

    counter--;

}

Pada program di atas, terlihat bahwa terdapat variabel counter yang diinisialisasi dengan nilai 0, dan ditambah 1 setiap kali terjadi produksi serta dikurangi 1 setiap kali terjadi konsumsi. Pada bahasa mesin, baris kode counter++ dan counter-- diimplementasikan seperti di bawah ini:

Contoh Race Condition pada bahasa mesin

//counter++

register1 = counter

register1 = register1 + 1

counter   = register1

//counter--

register2 = counter

register2 = register2 - 1

counter   = register2

Jika perintah counter++ dan counter-- berusaha mengakses nilai counter secara konkuren, maka nilai akhir dari counter bisa salah. Hal ini tidak berarti nilainya pasti salah, tapi ada kemungkinan untuk terjadi kesalahan. Contoh urutan eksekusi baris kode tersebut yang mengakibatkan kesalahan pada nilai akhir counter:

Contoh program yang memperlihatkan Race Condition

2//misalkan nilai awal counter adalah 2

    .produsen: register1 = counter       (register1 = 2)

    .produsen: register1 = register1 + 1 (register1 = 3)

    .konsumen: register2 = counter       (register2 = 2)

    .konsumen: register2 = register2 - 1 (register2 = 1)

    .konsumen: counter   = register2     (counter = 1)

.produsen: counter   = register1     (counter = 3)

Status akhir dari counter seharusnya adalah 0, tapi kalau urutan pengeksekusian program berjalan seperti di atas, maka hasil akhirnya menjadi 3. Perhatikan bahwa nilai akhir counter akan mengikuti eksekusi terakhir yang dilakukan oleh komputer. Pada program di atas, pilihannya bisa 1 atau 3. Perhatikan bahwa nilai dari counter akan bergantung dari perintah terakhir yang dieksekusi. Oleh karena itu maka kita membutuhkan sinkronisasi yang merupakan suatu upaya yang dilakukan agar proses-proses yang saling bekerjasama dieksekusi secara beraturan demi mencegah timbulnya suatu keadaanrace condition.

Ilustrasi program produsen dan konsumen

2.     Masalah Critical Section

Kunci untuk mencegah masalah ini dan di situasi yang lain yang melibatkan shared memori, shared berkas, and shared sumber daya yang lain adalah menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan proses writing dan reading kepada shared data pada saat yang sama. Dengan kata lain kita memutuhkan mutual exclusion, sebuah jalan yang menjamin jika sebuah proses sedang menggunakan shared berkas, proses lain dikeluarkan dari pekerjaan yang sama. Kesulitan yang terjadi karena proses 2 mulai menggunakan variabel bersama sebelum proses 1 menyelesaikan tugasnya.

Masalah menghindari race conditions dapat juga diformulasikan secara abstrak. Bagian dari waktu, sebuah proses sedang sibuk melakukan perhitungan internal dan hal lain yang tidak menggiring ke kondisi race conditions. Bagaimana pun setiap kali sebuah proses mengakses shared memory atau shared berkas atau melakukan sesuatu yang kitis akan menggiring kepada race conditions. Bagian dari program dimana shaed memory diakses disebut Critical Section atau Critical Region.

Walau pun dapat mencegah race conditions, tapi tidak cukup untuk melakukan kerjasama antar proses secara pararel dengan baik dan efisien dalam menggunakan shared data. Kita butuh 4 kondisi agar menghasilkan solusi yang baik:

Tidak ada dua proses secara bersamaan masuk ke dalam citical section.

Tidak ada asumsi mengenai kecepatan atau jumlah cpu.

Tidak ada proses yang berjalan di luar critical secion yang dapat mengeblok proses lain.

Tidak ada proses yang menunggu selamamya untuk masuk critical section.

Critical Section adalah sebuah segmen kode di mana sebuah proses yang mana sumber daya bersama diakses. Terdiri dari:

Entry Section: kode yang digunakan untuk masuk ke dalam critical section

Critical Section: Kode di mana hanya ada satu proses yang dapat dieksekusi pada satu waktu

Exit Section: akhir dari critical section, mengizinkan proses lain

Remainder Section: kode istirahat setelah masuk ke critical section.

Ada bebrapa Solusi untuk mengatasi masalah Critical Section, yaitu:

Mutual exclution

Jika proses pi sedang mengeksekusi critical section-nya maka tidak ada proses lain yang dapat mengeksekusi dalam critical section mereka.

Progress

Jika tidak ada proses yang sedang dieksekusi dalam critical section  dan ada beberapa proses yang ingin masuk ke critical section mereka, maka pemilihan proses yang akan masuk ke critical section berikutnya tidak bias ditunda.

Bounded Waiting

Suatu keterikatan harus ada pada sejumlah proses yang diijinkan masuk ke critical section mereka, setelah adanya proses yang meminta masuk ke critical section dan sebelum  permintaan itu diterima.

a.     Asumsikan bahwa tiap proses mengeksekusi pada nonzero speed.

b.     Tidak ada asumsi mengenai kecepatan relative dan n proses.

Cara-cara memecahkan masalah

Hanya dua proses, Po dan P1

Struktur umum dari proses adalah Pi (proses lain Pj)

3.     Bakery Algorithm

Critical section untuk n proses:

Sebelum memasuki critical Section-nya, proses menerima nomor pemilik nomor terkecil memasuki critical section.

Jika proses Pi dan Pj menerima nomor yang sama, jika i < j, maka Pi dilayani duluan, lainnya Pj dilayani duluan (if i< j, then Pi is served first; else Pj is served first).

Skema penomoran selalu menghasilkan angka –angka yang disebutkan satu per satu, yaitu 1,2,3,3,3,3,4,5….

4.     Semaphore

Semaphore adalah pendekatan yang diajukan oleh Djikstra, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.

Semaphore mempunyai dua sifat, yaitu:

Semaphore dapat diinisialisasi dengan nilai non-negatif.

Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.

Ø  Operasi Down

Operasi ini menurunkan nilai semaphore, jika nilai semaphore menjadi non-positif maka proses yang mengeksekusinya diblocked. Operasi Down adalah atomic, tak dapat diinterupsi sebelaum diselesaikan.Emnurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblocked sebagai instruksi tunggal. Sejak dimulai, tak ada proses alain yang dapat mengakses semaphore sampai operasi selesai atau diblocked.

Ø  Operasi Up

Operasi Up menakkan nilai semaphore. Jika satu proses atau lebih diblocked pada semaphore itu tak dapat menyelesaikan operasi Down, maka salah satu dipilih oleh system dan menyelesaikan operasi Down-nya. Urutan proses yang dipilih tidak ditentukan oleh Djikstra, dapat dipilih secara acak. Adanya semaphore mempermudah persoalan mutual exclusion. Skema penelesaian mutual exclusion mempunyai bagan sebagai berikut:

Sebelum masuk critical section, proses melakukan Down. Bila berhasil maka proses masuk ke critical section. Bila tidak berhasil maka proses di-blocked atas semaphore itu. Proses yang diblocked akan dapat melanjutkan kembali bila proses yang ada di critical section keluar dan melakukan opersai up sehingga menjadikan proses yang diblocked ready dan melanjutkan sehingga opersi Down-nya berhasil.

Problem Klasik pada Sinkronisasi

Ada tiga hal yang selalu memjadi masalah pada proses sinkronisasi:

Problem Bounded buffer.

Problem Reades and Writer.

Problem Dining Philosophers.

5.     Monitors

Solusi sinkronisasi ini dikemukakan oleh Hoare pada tahun 1974. Monitor adalah kumpulan prosedur, variabel dan struktur data di satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur yang dideklarasikan minitor untuk mengakses struktur internal.

Properti-properti monitor adalah sebagai berikut:

Variabel-variabel data lokal, hanya dapat diakses oleh prosedur-prosedur dala monitor dan tidak oleh prosedur di luar monitor.

Hanya satu proses yang dapat aktif di monitor pada satu saat. Kompilator harus mengimplementasi ini(mutual exclusion).

Terdapat cara agar proses yang tidak dapat berlangsung di-blocked. Menambahkan variabel-variabel kondisi, dengan dua operasi, yaitu Wait dan Signal.

Wait: Ketika prosedur monitor tidak dapat berkanjut (misal producer menemui buffer penuh) menyebabkan proses pemanggil diblocked dan mengizinkan proses lain masuk monitor.

Signal: Proses membangunkan partner-nya yang sedang diblocked dengan signal pada variabel kondisi yang sedang ditunggu partnernya.

Versi Hoare: Setelah signal, membangunkan proses baru agar berjalan dan menunda proses lain.

Versi Brinch Hansen: Setelah melakukan signal, proses segera keluar dari monitor.

Dengan memaksakan disiplin hanya satu proses pada satu saat yang berjalan pada monitor, monitor menyediakan fasilitas mutual exclusion. Variabel-variabel data dalam monitor hanya dapat diakses oleh satu proses pada satu saat. Struktur data bersama dapat dilindungi dengan menempatkannya dalam monitor. Jika data pada monitor merepresentasikan sumber daya, maka monitor menyediakan fasilitas mutual exclusion dalam mengakses sumber daya itu.