BAB 4. SINKRONISASI & DEADLOCK

BAB 4. SINKRONISASI & DEADLOCK Sinkronisasi Perangkat Keras dan Semafor Oleh Muhammad Irfan Nasrullah Email : [email protected]

Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

1

Sinkronisasi Perangkat Keras Mengapa perlu sinkronisasi perangkat keras?


2

Metode pendekatan perangkat keras • Processor Synchronous Men-disabled interrupt

-----> Mutual Exlusion

• Memory Synchronous Dukungan hardware untuk Instruksi Atomic


3

Instruksi Atomic Instruksi i++ dalam bahasa mesin : Load Inc Store

R1, i R1 i, R1


4

Data Structure for Hardware Solutions public class HardwareData { private boolean data; public HardwareData(boolean data) { this.data = data; } public boolean get() { return data; } public void set(boolean data) { this.data = data; } // Continued on Next Slide


5

Data Structure for Hardware Solutions - cont public boolean getAndSet(boolean data) { boolean oldValue = this.get(); this.set(data); return oldValue; } public void swap(HardwareData other) { boolean temp = this.get(); this.set(other.get()); other.set(temp); } } Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

6

Thread Using get-and-set Lock // lock is shared by all threads HardwareData lock = new HardwareData(false); while (true) { while (lock.getAndSet(true)) Thread.yield(); criticalSection(); lock.set(false); nonCriticalSection(); } Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

7

Semafor •

Definisi: 1. Suatu variabel int yang digunakan untuk menghitung banyaknya proses yang sedang aktif atau yang sedang tidur. 2. Suatu variabel int, selain inisialisasi, hanya dapat diakses melalui 2 subrutin yang atomik: P (for wait; proberen dalam Belanda) dan V (for signal; verhogen dalam Belanda). <Silberchatz, Galvin & Gagne, 2002> 3. Suatu variabel yang memiliki nilai int. <William Stallings slide chapter 04>


8

Jenis-jenis Semafor • Binary Semafor - Semafor yang hanya bernilai 1 dan 0. - Digunakan untuk mutual exclusion: membatasi hanya ada satu proses pada critical section. • Counting Semafor - Semafor yang dapat bernilai 1, 0 dan integer lainnya.


9

Subrutin Wait dan Signal • Wait - Subrutin wait dalam pseudocode: wait (S) { while (S ≤ 0) ; //no-op S--; } - mengurangi 1 nilai dari Semafor S • Signal - Subrutin signal dalam pseudocode: signal(S) { S++; } - menambah 1 nilai dari Semafor S Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah 10 nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

2 Versi Subrutin Wait ● Spinlock Waiting 00 void waitSpinLock( int semaphore[] ) 01 { 02 while(semaphore[0] <= 0) { .. Do nothing .. } // spinlock 03 semaphore[0]--; 04 } ● Non-spinlock Waiting 10 void synchronized waitNonSpinLock( int semaphore []) 11 { 12 while(semaphore[0] <= 0) { 13 wait(); // blocks thread 14 } 15 semaphore[0]--; 16 } Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah 11 nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

2 Versi Subrutin Wait ● Spinlock Waiting

- Proses menunggu dengan menjalankan perintah-perintah yang tidak ada artinya. - Proses masih dalam keadaan running state. - Keuntungannya: pada lingkungan multiprocessor tidak diperlukannya context switch. - Kerugiannya: menghabiskan CPU cycle. ● Non-spinlock Waiting - Proses memblock dirinya sendiri dan secara otomatis akan membawa proses tersebut ke dalam waiting queue. - Proses tidak akan aktif sebelum ada yang membangunkannya. - Keuntungannya: CPU cycle dapat digunakan proses lain dalam mengeksekusi perintah-perintah yang berguna.

Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah 12 nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

2 Versi Subrutin Signal // Signal Spinlock 00 void signalSpinLock( int semaphore []) 01 { 02 semaphore[0]++; 03 } // Signal Non-Spinlock 10 void synchronized signalNonSpinLock( int semaphore []) 11 { 12 semaphore[0]++; 13 notifyAll(); // membawa waiting thread ke ready queue 14 }


Solusi Critical Section Problem • 3 tahap dalam menyelesaikan masalah Critical Section: 1. Pintu masuk (Entry Section) 2. Critical Section 3. Pintu keluar (Exit Section) • Dengan Semafor, 3 syarat utama sinkronisasi dapat dipenuhi. 1. Mutual Exclusive 2. Make progress 3. Bounded waiting Copyright © 2004 Muhammad Irfan & Nasrullah. Silahkan menggandakan dan mendistribusikan isi dari slide ini, tanpa mengubah 14 nota hak cipta ini. Dilarang memodifikasi isi slide ini tanpa persetujuan dari penulis.

Implementasi Semafor // Entry Section wait(S);

wait (S) { while (S ≤ 0) ; //no-op S--; }

// Critical Section …………. // Exit Section signal(S);

signal(S) { S++; }


BAB 4. SINKRONISASI & DEADLOCK

Recommend Documents