Bab 6: Sinkronisasi Proses Latar Belakang Permasalahan Critical-Section Hardware Sinkronisasi Semaphores Permasalahan Klasik Sinkronisasi Sinkronisasi pada Solaris 2 dan Windows 2000
7.1
Latar Belakang Akses yang konkuren pada shared data kemungkinan menghasilkan inkonsistensi Mempertahankan konsistensi data membutuhkan mekanisme untuk mejamin eksekusi yang teratur pada proses yang saling bekerjasama (cooperating processes). Solusi Shared-memory untuk permasalahan boundedbuffer memungkinkan terdapat n – 1 item dalam buffer pada waktu yang sama. Sebuah solusi, dimana semua buffer N digunakan bukan sesuatu yang sederhana Misalnya kita memodifikasi kode program produsenkonsumen dengan menambahkan variabel counter, diinisialisasi ke 0 dan bertambah setiap kali item baru ditambahkan ke buffer
7.2
1
Bounded-Buffer Shared data #define BUFFER_SIZE 10 typedef struct { ... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;
7.3
Bounded-Buffer Proses Produser item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; }
7.4
2
Bounded-Buffer Proses Konsumer item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; }
7.5
Bounded Buffer Pernyataan counter++; counter--; harus dilakukan secara atomik Operasi atomik maksudnya operasi yang menyelesaikan pekerjaannya tanpa interupsi
7.6
3
Bounded Buffer Pernyataan “counter++” apabila diimplementasikan dalam bahasa mesin sbb: register1 = counter register1 = register1 + 1 counter = register1 Pernyataan “counter--” diimplementasikan sbb: register2 = counter register2 = register2 – 1 counter = register2
7.7
Bounded Buffer Jika baik produser dan konsumer melakukan update buffer secara konkuren (bersamaan), pernyataan bahasa assembly tersebut akan disisipkan Penyisipan tergantung bagaimana proses produser dan konsumer dijadwalkan
7.8
4
Bounded Buffer Misalkan counter diinisialisasi 5. Sebuah pernyataan penyisipan sbb: produser: register1 = counter (register1 = 5) produser: register1 = register1 + 1 (register1 = 6) konsumer: register2 = counter (register2 = 5) konsumer: register2 = register2 – 1 (register2 = 4) produser: counter = register1 (counter = 6) konsumer: counter = register2 (counter = 4) Nilai counter dapat bernilai 4 atau 6, dimana hasil yang benar seharusnya 5.
7.9
Race Condition Race condition: Situasi dimana beberapa proses mengakses dan memanipulasi shared data secara bersamaan. Nilai akhir dari shared data tergantung proses yang diselesaikan paling akhir. Untuk mencegah race condition, proses konkuren harus di- sinkronisasi
7.10
5
Permasalahan Critical-Section n proses semua berkompetisi menggunakan shared data Setiap proses mempunyai segmen kode yang disebut critical section, dimana shared data diakses. Permasalahan – menjamin ketika satu proses menjalankan critical section nya, tidak ada proses lain yang mengeksekusi critical section nya.
7.11
Solusi Permasalahan CriticalSection 1. Mutual Exclusion. Jika proses Pi mengekseskusi critical section nya, maka tidak ada proses lain yang dapat mengeksekusi critical section nya. 2. Progress. Jika tidak ada proses yang mengeksekusi critical section nya dan terdapat beberapa proses yang akan memasuki critical section, maka pemilihan proses yang akan memasuki critical section berikutnya tidak dapat ditunda tanpa batas 3. Bounded Waiting. Ada batasan waktu tunggu ketika proses diizinkan untuk memasuki critical section setelah proses membuat permintaan untuk memasuki critical section dan sebelum permintaan yang diberikan. Diasumsikan setiap proses dieksekusi dengan kecepatan lebih dari 0 Tidak ada asumsi mengenai kecepatan relatif proses n.
7.12
6
Cara Penyelesaian Hanya ada 2 proses, P0 dan P1 Struktur umum dari proses Pi (proses lain Pj) do { entry section critical section exit section reminder section } while (1); Proses mungkin menggunakan variabel umum yang sama untuk sinkronisasi aksinya
7.13
Algoritma 1 Shared variable: int turn; initially turn = 0 turn = i Pi can enter its critical section
Proses Pi
do { while (turn != i) ; critical section turn = j; reminder section } while (1); Memenuhi mutual exclusion, tetapi tidak memenuhi progress
7.14
7
Algoritma 2 Shared variable: boolean flag[2]; initially flag [0] = flag [1] = false. flag [i] = true Pi ready to enter its critical section
Proses Pi
do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); Memenuhi mutual exclusion, tetapi tidak memenuhi progress.
7.15
Algoritma 3 (Peterson) Mengkombinasikan shared variable dari algoritma 1 dan 2. Proses Pi do { flag [i]:= true; turn = j; while (flag [j] and turn = j) ; critical section flag [i] = false; remainder section } while (1); Memenuhi tiga hal untuk pemecahan permasalahan critical-section untuk 2 proses.
7.16
8
Algoritma Bakery Critical section untuk n proses Sebelum masuk ke critical section, proses menerima nomor. Pemegang nomor terkecil memasuki critical section. Jika proses Pi dan Pj menerima nomor yang sama, jika i < j, maka Pi dilayani dahulu; apabila sebaliknya Pj dilayani dahulu. Skema penomoran menggunakan nomor urut; misalnya 1,2,3,3,3,3,4,5...
7.17
Algoritma Bakery Notasi <≡ lexicographical order (ticket #, process id #) (a,b) < (c,d) jika a < c atau jika a = c dan b < d max (a0,…, an-1) adalah sebuah nilai, k, dimana k ≥ ai for i 0, …, n – 1
Shared data boolean choosing[n]; int number[n]; Struktur data diinisialisasi false dan 0
7.18
9
Algoritma Bakery do { choosing[i] = true; number[i] = max(number[0], number[1], …, number [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)) ; } critical section number[i] = 0; remainder section } while (1);
7.19
Hardware Sinkronisasi Test and set memodifikasi nilai secara atomik . boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; }
7.20
10
Mutual Exclusion dengan Testand-Set Shared data: boolean lock = false; Proses Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section }
7.21
Hardware Sinkronisasi Secara atomik menukar 2 variabel. void Swap(boolean &a, boolean &b) { boolean temp = a; a = b; b = temp; }
7.22
11
Mutual Exclusion dengan Swap Shared data (diinisialisasi false): boolean lock; boolean waiting[n];
Proses Pi
do { key = true; while (key == true) Swap(lock,key); critical section lock = false; remainder section }
7.23
Semaphores Adalah perangkat sinkorinisasi yang tidak memerlukan busy waiting. Semaphore S – variabel integer Hanya dapat diakses melalui 2 operasi atomik wait (S): while S≤ ≤ 0 do no-op; S--; signal (S): S++;
7.24
12
Critical Section dari n Proses Shared data: semaphore mutex; //diinisialisasi mutex = 1 Proses Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1);
7.25
Implementasi Semaphore Tentukan semaphore sebagai typedef struct { int value; struct process *L; } semaphore; Diasumsikan 2 operasi sederhana: block menghentikan sementara (suspend) proses yang memanggil wakeup(P) melanjutkan (resume) eksekusi dari proses P yang di-blok
7.26
13
Implementasi Operasi Semaphore didefinisikan wait(S): S.value--; if (S.value < 0) { tambah proses ke S.L; block; } signal(S):
S.value++; if (S.value <= 0) { menghapus proses P dari S.L; wakeup(P); }
7.27
Semaphore sebagai Perangkat Sinkronisasi Umum Eksekusi B oleh Pj hanya setelah A dieksekusi pada Pi Gunakan semaphore flag yang diinisialisasi 0 Kode: Pi Pj A signal(flag)
wait(flag) B
7.28
14
Deadlock dan Starvation Deadlock – dua atau lebih proses menunggu tanpa kepastian suatu event yang dapat disebabkan oleh satu proses yang sedang menunggu. Misalnya S dan Q adalah 2 semaphores yang diinisialisasi 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S); signal(S); signal(Q); signal(Q) signal(S); Starvation – blok yang tidak pasti. Sebuah proses mungkin tidak pernah dihapus dari antrian semaphore yang dihentikan sementara (suspend)
7.29
Dua Jenis Semaphores Counting semaphore – nilai integer dapat berkisar melalui domain tak terbatas. Binary semaphore – nilai integer dapat mempunyai jangkauan 0 dan 1; lebih sederhana untuk diimplementasikan Dapat mengimplementasikan counting semaphore S sebagai binary semaphore.
7.30
15
Implementasi S sebagai Binary Semaphore Struktur Data: binary-semaphore S1, S2; int C: Inisialisasi: S1 = 1 S2 = 0 C = nilai awal dari semaphore S
7.31
Implementasi S Operasi wait wait(S1); C--; if (C < 0) { signal(S1); wait(S2); } signal(S1); Operasi signal wait(S1); C ++; if (C <= 0) signal(S2); else signal(S1);
7.32
16
Permasalahan Klasik Sinkronisasi Permasalahan Bounded-Buffer Permasalahan Readers and Writers Permasalahan Dining-Philosophers
7.33
Permasalahan Bounded-Buffer Shared data semaphore full, empty, mutex; Inisialisasi: full = 0, empty = n, mutex = 1
7.34
17
Permasalahan Bounded-Buffer Proses Produser do { … memproduksi item pada nextp … wait(empty); wait(mutex); … tambahkan nextp ke buffer … signal(mutex); signal(full); } while (1);
7.35
Permasalahan Bounded-Buffer Proses Konsumer do { wait(full) wait(mutex); … mengambil item dari buffer ke nextc … signal(mutex); signal(empty); … mengkonsumsi item pada nextc … } while (1);
7.36
18
Permasalahan Readers-Writers Shared data semaphore mutex, wrt; Inisialisasi mutex = 1, wrt = 1, readcount = 0
7.37
Permasalahan Readers-Writers Proses Writer wait(wrt); … menulis … signal(wrt);
7.38
19
Permasalahan Readers-Writers Proses Reader wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); … membaca … wait(mutex); readcount--; if (readcount == 0) signal(wrt); signal(mutex):
7.39
Permasalahan DiningPhilosophers
Shared data semaphore chopstick[5]; Inisialisasi semua nilai dg1 7.40
20
Permasalahan DiningPhilosophers Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … makan … signal(chopstick[i]); signal(chopstick[(i+1) % 5]); … berfikir … } while (1);
7.41
Sinkronisasi Solaris 2 Mengimplementasikan beberapa lock kunci untuk mendukung multitasking, multithreading (termasuk thread real-time), dan multiprocessing. Menggunakan adaptive mutexes untuk efisiensi ketika melindungi data dari segmen kode pendek Menggunakan condition variables dan readers-writers locks ketika segmen kode panjang memerlukan akses ke data. Menggunakan turnstiles untuk memesan daftar thread menunggu untuk memperoleh adaptive mutexes atau readers-writers locks
7.42
21
Sinkronisasi Windows 2000 Menggunakan interrupt mask untuk melindungi akses ke sumber daya global pada sistem prosesor tunggal. Menggunakan spinlocks pada sistem multiprosessor Juga menyediakan dispatcher object yang dapat bertindak sebagai mutex dan semaphore. Dispatcher object juga dapat menyediakan event. Event bertindak seperti sebuah variabel kondisi.
7.43
22
