Sistem Operasi Komputer. Pertemuan VI Proses Sinkronisasi

Sistem Operasi Komputer

Sistem Operasi Komputer Pertemuan VI – Proses Sinkronisasi

Proses Sinkronisasi • Latar belakang • Critical section problem (low level synchronization) • Sinkronisasi hardware • Semaphores • Problem klasik sinkronisasi • Critical regions (high level synchronization) • Monitors (high level synchronization) • Sinkronisasi windows 2000

Universitas Kristen Maranatha -- IT Department

1


Latar belakang

• Konkurensi akses ke shared-data mungkin menyebabkan inkonsistensi data • Perawatan konsistensi data memerlukan mekanisme untuk memastikan urutan eksekusi proses-proses yang bekerja sama • Contoh: Solusi shared-memory untuk boundedbuffer, mengijinkan (n-1) items di dalam buffer untuk suatu waktu tertentu. Lihat slide tentang Proses (Pert. IV) • Solusi untuk penggunaan n buffer sulit diimplementasikan – Modifikasi kode producer-consumer, dengan menambahkan variabel counter, diinisialisasi pada 0, dan dinaikkan setiap kali item baru masuk ke buffer

Bounded-Buffer (1) • Shared data #define BUFFER_SIZE 10 typedef struct { ... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;


2


Bounded-Buffer (2) •

Producer process item nextProduced; while (1) { while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter ++; }

Bounded-Buffer (3) • Consumer process item nextConsumed; while (1) { while (counter == 0) ; /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter --; }


3


Bounded-Buffer (4)

• Statement dalam counter ++; counter --; harus dieksekusi secara atomic. • Berarti harus diselesaikan secara tuntas tanpa pada suatu proses tanpa interupsi/intervensi dari proses lainnya

Bounded-Buffer (6)

• Statement “count++” dapat diimplementasikan sebagai (dalam bahasa assembly): register1 = counter register1 = register1 + 1 counter = register1 • Statement “count--” dapat diimplementasikan sebagai: register2 = counter register2 = register2 – 1 counter = register2


4


Bounded-Buffer (7)

• Jika kedua proses produser dan konsumer berusaha untuk mengupdate buffer secara bersamaan (terjadi konkurensi), maka statement assembly akan memberikan interleaved (peralihan) • Interleaving bergantung pada bagaimana proses consumer-produser dijadwalkan,apakah Pi atau Pj yang akan diberikan tempat pada CPU

Bounded-Buffer (8)

• Anggap nilai awal counter 5. Suatu contoh skema peralihan (interleaving), sebagai berikut: producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6) consumer: register2 = counter (register2 = 5) consumer: register2 = register2 – 1 (register2 = 4) producer: counter = register1 (counter = 6) consumer: counter = register2 (counter = 4)

• Isi counter mungkin 6 atau 4, padahal nilai yang seharusnya adalah 5


5


Race condition • Situasi dimana beberapa proses memasuki dan memanipulasi shared-data secara konkurensi • Hasil akhir shared-data, bergantung pada urutan proses yang selesai terakhir • Untuk menghindari race conditions, proses yang berkonkurensi harus disinkronisasikan (synchronized)

Critical section problem (low level synchronization) Critical section adalah: bagian yang berisi sejumlah variabel yang akan di-share (dapat dipengaruhi dan mempengaruhi) proses yang lain • Problem: – Bagaimana untuk meyakinkan jika suatu proses sedang mengeksekusi critical section, tidak ada proses lain yang memasuki critical section yang sama pada saat yang bersamaan. Solusi harus memenuhi syarat: – Mutual exclusion jika suatu proses sedang mengerjakan critical section, maka tidak boleh ada proses lain yang masuk critical section tersebut – Progress jika tidak ada proses yang mengerjakan critical section dan ada beberapa proses yang akan masuk ke critical section, maka hanya prosesproses yang sedang berada pada entry-section saja yang boleh berkompetisi untuk mengerjakan critical section – Bounded waiting besarnya waktu tunggu dari suatu proses yang akan masuk critical section, mulai dari meminta ijin hingga permintaan critical section dipenuhi. Suatu proses tidak boleh terlalu lama berada dalam critical section dan membiarkan proses lainnya menunggu •


6


Usaha awal solusi critical section problem

• Struktur umum proses Pi (proses lainnya Pj) do { entry section

// Permohonan masuk critical // section

critical section exit section

remainder section } while (true); • Beberapa proses diijinkan share variabel untuk mengsinkronisasikan aksi-aksinya

Solusi CS - Algoritma 1 (Variabel Turn)

• Shared variables: • int turn; inisialisasi turn = 0 (atau 1) • j = turn - i ⇒ Pj boleh memasuki CS

• Process Pi do { while (turn != i) ; /* do nothing */ critical section turn = j; remainder section } while (1); •

Memenuhi mutual exclusion, namun tidak memenuhi syarat progress, karena adanya ketidakluwesan penggunaan variabel turn. Contoh: jika turn = 0, maka Pj tidak dapat masuk CS walaupun ia berada pada entry section-nya.


7


Solusi CS – Algoritma 2 (array Flag) • Shared variables – boolean flag [ 0 .. 1 ]; inisialisasi flag [ 0 ] = flag [ 1 ] = false. – flag [ i ] = true ⇒ Pi siap untuk memasuki CS

• Process Pi do { flag[ i ] := true; while (flag[ j ]); /* do nothing */ critical section flag [ i ] = false; remainder section } while (1); •

•

Memenuhi mutual exclusion, namun tidak memenuhi persyaratan untuk progress, Pi dan Pj (proses lain) bisa berada pada keadaan looping bila keduanya terus bernilai true (tidak dapat ditentukan mana yang boleh masuk ke CS) Bergantung pada “waktu” pemrosesan timer CPU dapat digunakan, namun bahayanya keduanya bisa berada bersamaan pada CS, dan melanggar syarat mutual exclusion

Solusi CS – Algoritma 3 (turn dan flag) • Kombinasi shared variabel: turn dan flag • Process Pi do { turn bisa 1 atau 0 namun tidak flag [i]:= true; keduanya (mutex) turn = j; while (flag [ j ] and turn = j); /*do nothing */ critical section flag [ i ] = false; remainder section } while (1); •

•

Karena Pi tidak mengubah nilai turn pada saat mengeksekusi while, Pi dapat memasuki CS (progress) setelah paling banyak satu Pj memasuki CS-nya (boundedwaiting) Memenuhi ketiga syarat, dapat digunakan efektif untuk sinkronisasi dua proses


8


Algoritma Bakery (antrian di tukang roti) banyak proses

• Critical section untuk n proses • Sebelum memasuki CS, proses mendapat nomor urut. Yang mendapat nomor terkecil boleh memasuki CS • Jika dua proses Pi dan Pj menerima nomor yang sama (i < j), maka Pi dilayani terlebih dahulu • Skema penomoran selalu menggunakan nomor yang menaik, seperti1,2,3,3,3,3,4,5... • Proses yang beroperasi di remainder section tidak dapat mencegah proses lain yang ingin masuk CS

Algoritma Bakery (2)

• Notasi – (#antrian, #proses_id) – (a,b) < (c,d) jika a < c or a = c and b < d – max (a0,…, an-1) adalah, k, dimana k ≥ ai untuk i = 0,…, n - 1

• Shared data boolean choosing[n]; int number[n]; – Struktur data diinisialisasi dengan FALSE dan 0


9


Algoritma Bakery (3) 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 ] < number[ i ])) ; } critical section number[i] = 0; remainder section } while (1);

Sinkronisasi Hardware (test-and-set) • Instruksi mesin untuk membantu implementasi mutual exclusion • Test dan modifikasi isi dari word secara otomatis boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; }


10


Mutual exclusion dengan test-and-set • Shared data: boolean lock = false; • Process Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section }

Sinkronisasi hardware (swapping) • Swap dua variabel secara atomik void Swap(boolean &a, boolean &b) { boolean temp = a; a = b; b = temp; }


11


Mutual exclusion dengan swap • Shared data (inisialisasi dengan false): boolean lock; boolean waiting[n];

• Process Pi do { key = true; while (key == true) Swap(lock,key); critical section lock = false; remainder section }

Semaphores • Alat sinkronisasi yang diupayakan tidak menyebabkan busy waiting (looping di dalam entry section, sementara ada proses yang berada di critical section) • Semaphore S sebagai variabel integer • Hanya dapat diakses melalui dua operasi atomik yang tidak terpisahkan wait (S): while S ≤ 0 do {nothing}; S--; Catatan: signal (S): S++;


Masih mungkin terjadi busy waiting

12


Critical section n proses • Shared data: semaphore mutex; //inisialisasi mutex = 1 • Process Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1);

Implementasi semaphore (1) • Definisikan semaphore sebagai record typedef struct { int value; struct process *L; // daftar antrian proses } semaphore;

• Andaikan dua operasi sederhana: – block menghentikan proses yang memanggilnya – wakeup( P ) memulai kembali proses P yang diblok


13


Implementasi semaphore (2) • Operasi semaphore sekarang dituliskan sebagai berikut (untuk menghindari spinlock, proses “berputar” pada saat menunggu lock): Nilai absolut dari wait(S): S.value--; if (S.value < 0) { add this process to S.L; block; }

s.value menunjukkan jumlah proses yang sedang mengantri untuk mengakses critical section.

signal(S): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); }

Semaphore sebagai alat sinkronisasi • Eksekusi B dalam Pj hanya setelah A selesai dieksekusi dalam Pi • Gunakan semaphore flag dengan inisialisasi 0 • Skenario implementasi: Pi Pj M M A wait(flag) signal(flag) B


14


Rangkuman Sinkronisasi (Cooperating Process)

Contoh Sinkronisasi: Shared Variable Teknik yang digunakan untuk untuk threads yang menggunakan ruang alamat memori yang sama. Hanya efektif jika informasi dapat dibagikan antara proses / threads, tanpa mempengaruhi hasil satu dengan yang lainnya.


15


Penggunaan Sinkronisasi (Resources Sharing) • Bounded-Buffer • Readers and Writers • Dining-Philosophers

P0 wait (S) wait (Q) . . signal (S) signal (Q)

P1 wait (Q) wait (S) . . signal(Q) signal (S)

Sharing Resources: dapat menyebabkan deadlock (Keadaan saling menunggu antara proses-proses yang ada, dimana event yang menyebabkan suatu proses dapat dieksekusi, juga sedang dalam keadaan waiting) dapat menyebabkan starvation (Keadaan dimana suatu proses menunggu giliran terus menerus tanpa pernah memperoleh resource yang diperlukannya

Bounded-Buffer Problem (Producer-Consumer) Buffer terisi

• Shared data

Buffer kosong Tanda masuk buffer

semaphore full, empty, mutex; • Nilai awal inisialisasi full = 0, empty = n, mutex = 1


16


do {

Bounded-Buffer Problem Producer & Consumer

… produce an item in nextp … wait(empty); wait(mutex); … add nextp to buffer … signal(mutex); signal(full); } while (1);

do { wait(full) wait(mutex);

… remove an item from buffer to nextc … signal(mutex); signal(empty); … consume the item in nextc … } while (1);

Producer mengisi buffer untuk consumer, atau consumer mengosongkan buffer untuk producer

Readers-Writers Problem • Proses-proses berkonkurensi memasuki shared data, ada yang hanya ingin membacanya atau bahkan mengupdatenya (membaca + menulisi) • Readers boleh secara eksklusif memasuki shared data (critical section) • Shared data semaphore mutex, wrt; • Dengan nilai awal mutex = 1, wrt = 1, readcount = 0


17


Readers-Writers Problem Writer Process wait(wrt); … writing is performed … signal(wrt); Jika ada writer yang menunggu, maka tidak boleh ada reader yang membaca (prioritas writer lebih tinggi dari reader)

Readers-Writers Problem Reader Process wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); … reading is performed … wait(mutex); readcount--; if (readcount == 0) signal(wrt); signal(mutex):


Jika ada writer yang menunggu, sebuah reader tidak perlu menunggu reader lainnya untuk selesai (prioritas reader lebih tinggi dari writer) Jika ada satu writer dalam C.S., dan ada n reader menunggu, maka satu reader menunggu di wrt, dan (n-1) menunggu di mutex

18


Dining-Philosophers Problem (1) 3

3

2

4

2

4

1 0

1 0

• Shared data semaphore chopstick[5]; Nilai awal semua elemen array chopstick =1

Dining-Philosophers Problem (2) • Philosopher i : do { wait(chopstick[ i ]) wait(chopstick[(i +1) % 5]) … eat … signal(chopstick[ i ]); signal(chopstick[(i +1) % 5]); … think … } while (1);


19


Critical regions

• Region = Sekuensial program yang dienkapsulasi dalam proses yang sama • Shared variable v dengan tipe T, dideklarasikan v : shared T

• Variabel v diakses hanya dalam statement S region v while B do S

• Ketika v diakses oleh eksekusi statement S, v tidak dapat diakses oleh proses manapun juga • Contoh Bounded-buffer: Shared data: struct buffer { int pool [ n ]; int count, in, out; }

Bounded Buffer Producer Process • Producer menyisipkan nextp ke dalam buffer yang di-share region buffer when (count < n) { pool[in] = nextp; in:= (in+1) % n; count++; }


20


Bounded Buffer Consumer Process • Consumer memindahkan item dari buffer yang di share dan menaruhnya dalam nextc region buffer when (count > 0) { nextc = pool[out]; out = (out+1) % n; count--; }

Monitors (1) •

Mengijinkan sharing yang aman antara sebuah abstract data type antara beberapa proses yang berkonkurensi dalam prosedur lokal monitor monitor-name { shared variable declarations procedure body P1 (…) { ... } procedure body P2 (…) { ... } procedure body Pn (…) { ... } { initialization code } }


Kumpulan prosedur, variabel dan data struktur dalam satu modul

21


Monitors (2) •

•

Untuk menjamin bahwa suatu proses menunggu dalam suatu monitor, harus ada variabel kondisi condition x, y Hanya dapat digunakan dengan operasi wait dan signal x.wait( ) proses yang melihatnya harus berhenti beraktivitas, sampai ada … x.signal( ) mengaktifkan satu proses yang ditunda

• Keterbatasan: – Tidak semua kompiler dapat mutual exclusion – Tidak dapat diterapkan pada sistem terdistribusi

Contoh monitor Dining Philosopher (1) monitor dp { enum { thinking, hungry, eating } state[5]; condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init( ) { for (int i = 0; i < 5; i++) state[ i ] = thinking; } }


22


Contoh monitor Dining Philosopher (2) void pickup (int i) { state[ i ] = hungry; test[ i ]; if (state[ i ] != eating) self [ i ].wait(); } void putdown (int i) { state[ i ] = thinking; //test left and right //neighbors test(( i + 4) % 5); test(( i + 1) % 5); }

void test (int i) { if ( (state[(i + 4) % 5] != eating) && (state[ i ] == hungry) && (state[(i + 1) % 5] != eating)) { state [ i ] = eating; self [ i ].signal(); } } void main ( ) { dp.init ( ) dp.pickup ( i ); … eating … dp.putdown ( i ); }

Sinkronisasi Windows 2000 • Menggunakan interrupt masks (interrupt request line dihentikan, sebelum eksekusi sederetan instruksi kritis yang tidak dapat diinterupsi) untuk melindungi akses ke sumber daya global pada sistem uniprosesor • Menggunakan spinlocks (tidak perlu adanya context switching apabila suatu proses sedang menunggu) pada sistem multiprosesor • Menyediakan dispatcher objects yang bertindak sebagai mutex dan semaphore • Menyediakan pula events yang bertindak sebagai variabel kondisi


23


Latihan Soal Sinkronisasi 1. 2. 3. 4. 5. 6.

7.

Apakah manfaat utama adanya sinkronisasi proses? Dengan menghindari adanya mutual exclusion, apakah menjamin bahwa deadlock tidak akan terjadi? Mengapa Algoritma-2 solusi sinkronisasi, tidak menunjukkan adanya progress? Sebutkan kesulitan-kesulitan yang sering timbul pada masalah sinkronisasi! Tunjukkan perbedaan antara busy waiting (spinlock) dengan blocking! Apabila arsitektur suatu sistem komputer menggunakan interrupt untuk melakukan pergantian antara 2 proses, informasi apa saja yang dibutuhkan? Bagaimana caranya menghindari masalah-masalah klasik dalam sinkronisasi? Jelaskan secara singkat!

Kuis Algoritma Sinkronisasi 1. 2. 3. 4. 5. 6.

Apakah yang dimaksudkan dengan “race condition” pada kerja sama antar proses ? (15 point) Sebutkan syarat yang harus dipenuhi untuk solusi pada problem “critical section” ! (15 point) Mengapa algoritma 1 tidak memenuhi syarat progress ? Jelaskan dengan skenario ! (20 point) Mengapa algoritma 2 tidak memenuhi syarat progress ? Jelaskan dengan skenario ! (20 point) Apa yang dimaksud dengan busy waiting pada semaphore ? (15 point) Jelaskan alternatif implementasi semaphore dengan menggunakan block dan wakeup ! (15 point)


24


1.

2.

3.

Kuis Aplikasi Sinkronisasi

Apakah peran dari semaphore empty dan full pada producer dan consumer process dalam bounded-buffer problem ? (15 point) Terangkan versi ke-2 masalah reader-writer yang memberi prioritas pada writer process ! Berikan solusinya dengan semaphore wrt ! (15 point) Dalam problem nyatanya, seperti apakah kira-kira dining philosopher problem itu ? Dan bagaimana ilustrasi DP dapat membantunya ? (20 point)

KUIS Sinkronisasi D3 2005/06

1. 2. 3. 4.

Proses-proses yang bagaimanakah yang memerlukan sinkronisasi ? Jelaskan 3 syarat yang harus dipenuhi untuk mengatasi masalah critical section ! Jelaskan mengapa Algoritma-3 efektif untuk solusi sinkronisasi antara 2 proses ! Perhatikan 2 proses berikut ini, manakah yang akan dijalankan terlebih dahulu, jika keduanya diaktifkan secara pararel ? Hasil apa yang akan di print ? Jelaskan !

5.

P1: ? Jelaskan ! Pada keadaan di berikut,P0: apakah terjadi deadlock Print “dua” Wait (S) Signal (S) Print “satu” P0: wait (S) wait (Q) . . signal (S) signal (Q)


P1: wait (Q) wait (S) . . signal(Q) signal (S)

25


Jawaban Kuis 2005/06 1. 2. 3.

4.

Proses-proses yang saling bekerja sama (cooperating processes) dan memerlukan suatu resource yang sama. Mutual exclusion, Progress, Bounded waiting -. Menggunakan 2 kondisi dalam entry section, yaitu variabel turn dan array flag[i], dengan dua index. -. Karena Pi tidak mengubah nilai turn pada saat mengeksekusi entry secton, Pi dapat memasuki CS (progress) setelah paling banyak satu Pj memasuki CS-nya (boundedwaiting) P0 baru P1 (“dua”, “satu”) P0

“dua”

Signal (S)

P1 Wait (S) 5.

“satu”

Ya. P0 dan P1 saling menunggu untuk mengeksekusi signal(S), dan signal (Q). Pada saat P0 memerlukan S, S belum dilepaskan oleh P1, demikian pula pada saat P1 memerlukan Q, Q tersebut belum dilepaskan oleh P0.


26

Sistem Operasi Komputer. Pertemuan VI Proses Sinkronisasi

Recommend Documents