Pada bab ini, akan dibahas sinkronisasi proses dan deadlock yang dapat terjadi selama proses berlangsung.
Bayangkan bahwa spooler direktori memiliki slot dengan jumlah yang sangat besar, diberi nomor 0, 1, 2, 3, 4,... masing-masing dapat memuat sebuah nama berkas. Juga bayangkan bahwa ada dua variabel bersama, out, penunjuk berkas berikutnya untuk dicetak, dan in, menunjuk slot kosong di direktori. Dua vaiabel tersebut dapat menamgami sebuah two-word berkas untuk semua proses. Dengan segera, slot 0, 1, 2, 3 kosong (berkas telah selesai dicetak), dan slot 4, 5, 6 sedang terisi (berisi nama dari berkas yang antre untuk dicetak). Lebih atau kurang secara besamaan, proses A dan B, mereka memutuskan untuk antre untuk sebuah berkas untuk dicetak. Situasi seperti ini diperlihatkan oleh Gambar 3-1.
Dalam Murphy's Law kasus tesebut dapat terjadi. Proses A membaca in dan menyimpan nilai "7" di sebuah variabel lokal yang disebut next_free_slot. Sebuah clock interrupt terjadi dan CPU memutuskan bahwa proses A berjalan cukup lama, sehingga digantika oleh proses B. Proses B juga membaca in, dan juga mengambil nilai 7, sehingga menyimpan nama berkas di slot nomor 7 dan memperbaharui nilai in menjadi 8. Maka proses mati dan melakukan hal lain.
Akhirnya proses A berjalan lagi, dimulai dari tempat di mana proses tersebut mati. Hal ini terlihat dalam next_free_slot, ditemukan nilai 7 di sana, dan menulis nama berkas di slot nomor 7, menghapus nama berkas yang bau saja diletakkan oleh proses B. Kemudian proses A menghitung next_free_slot + 1, yang nilainya 8 dan memperbaharui nilai in menjadi 8. Direktori spooler sekarang secara internal konsisten, sehingga printer daemon tidak akan memberitahukan apa pun yang terjadi, tetapi poses B tidak akan mengambil output apa pun. Situasi seperti ini, dimana dua atau lebih proses melakukan proses reading atau writing beberapa shared data dan hasilnya bergantung pada ketepatan berjalan disebut race condition.
Tidak ada dua proses secara bersamaan masuk ke dalam citical section.
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
Critical section harus melakukan ketiga aturan berikut:
Solusi yang diberikan harus memuaskan permintaaan berikut:
Mutual exclution
Deadlock free
Starvation free
Pendekatan yang mungkin untuk solusi proses sinkronisasi
Solusi Piranti lunak (Software solution)
Tanpa Sinkronisasi.
Dengan Sinkronisasi.
Low-level primitives: semaphore
High-level primitives: monitors
Solusi Piranti Keras (Hardware solution)
Gambar 3-2. Critical Section. Sumber: . . .
do { critical section remainder section } while(1); |
Gambar 3-3. Prosis Pi. Sumber: . . .
do { while(turn!=1); critical section turn=j; remainder section } while(1); |
FLAG untuk setiap proses yang memberi STATE:
Gambar 3-4. Process Pi. Sumber: . . .
do { flag[i]:=true; while(turn!=1); critical section turn=j; remainder section } while(1); |
FLAG untuk meminta izin masuk:
Kode ini dijalankan untuk setiap proses i
Gambar 3-5. Kode. Sumber: . . .
Shared variables F boolean flag[2]; initially flag[0] = flag[1] = false F flag[i] = true; |
Gambar 3-6. Process Pi. Sumber: . . .
do { flag[i]:=true; turn = j; while(flag[j] and turn = j); critical section flag[i] = false; remainder section } while(1); |
Memenuhi ketiga persyaratan, memecahkan persoalan critical section untuk kedua proses
Critical Section untuk n buah proses:
Gambar 3-7. Process Pi. Sumber: . . .
boolean choosing [n]; long long long int number [n]; /* 64 bit maybe okay for about 600 years */ Array structure elements are initiallized to false and 0 respectively while (true) { choosing[i] = true; number[i] = max(number[0], ... [n-1]) + 1; choosing[i] = false; for (j = 0; j < n; j ++) { while (choosing[j]) {} while ((number[j] !=0) && ((number[j], j) < (number[i], i))) {} } number[i] = 0 } Solves the critical-section problem for n process |
Disabling Interrupts: Hanya untuk uni prosesor saja.
Atomic test and set: Returns parameter and sets parameter to true atomically.
Gambar 3-8. Process Pi. Sumber: . . .
while (test_and_set(lock)); /* critical section */ lock = false; GET_LOCK: IF_CLEAR_THEN_SET_BIT_AND_SKIP (bit_address) BRANCH GET_LOCK /* set failed */ /* set succeeded */ |
Gambar 3-9. Lock. Sumber: . . .
while (test_and_set(lock)); Boolean waiting[N]; int j; /* Takes on values from 0 to N - 1 */ Boolean key; do { waiting[i] = TRUE; key = TRUE; while ( waiting[i] && key ) key = test_and_set( lock ); /* Spin lock */ waiting[i] = FALSE; /****** CRITICAL SECTION ********/ j = ( i + 1 ) mod N; while ( ( j != i ) && ( ! waiting[ j ] ) ) j = ( j + 1 ) % N; if ( j == i ) //Using Hardware lock = FALSE; //Test_and_set. else waiting[ j ] = FALSE; /******* REMAINDER SECTION *******/ } while (TRUE); |
Semaphore mempunyai dua sifat, yaitu:
Gambar 3-10. Block. Sumber: . . .
Type Semaphore = Integer, Procedure Down(Var: semaphore); Begin s := s-1; if s <= 0 Then Begin Tempatkan antrian pada antrian untuk semaphore s Proses diblocked End; End; |
Gambar 3-11. Block. Sumber: . . .
Type Semaphore = Integer, Procedure Down(Var: semaphore); Begin s := s + 1; if s <= 0 Then Begin Pindahkan satu proses P dari antrian untuk semaphore s Tempatkan proses P di senarai ready End; End; |
Gambar 3-12. Mutex. Sumber: . . .
Cons N = 2; Var S:semaphore; Procedure enter_critical_section; { mengerjakan kode-kode kritis } Procedure enter_noncritical_section; { mengerjakan kode-kode tak kritis } ProcedureProses(i: integer); Begin Repeat Down(s); Enter_critical_section; Up(s); Enter_noncritical_section; Forever End; Begin S:= 1; Parbegin Proses(0); Proses(1); ParEnd End; |
Ada tiga hal yang selalu memjadi masalah pada proses sinkronisasi: