Sistem Operasi 6 “Process Synchronization Synchronization” Antonius Rachmat C, S.Kom, M.Cs
P Paralel l lP Processing i • Pa Paralel alel processing p ocessing is a situation sit ation in which hich two/more processor operate in unison. – Executing instruction simultaneously
• Benefits: increase reliability & faster processing • Evolution:
– Job level: each job has its own processor and all processes and threads are run by the same processor – Process level: unrelated process, are assigned d to any available l bl processor – Thread level: threads are assigned to avaliable processor
M Mengapa Sinkronisasi Si k i i • Sink Sinkronisasi oni i diperlukan dipe l k n untuk nt k menghindari menghind i terjadinya ketidak konsistenan data akibat adanya akses data secara konkuren • Diperlukan p adanya y suatu mekanisme untuk memastikan urutan / giliran pengaksesan suatu data yang saling bekerjasama sehingga terjadi sinkronisasi • If we don’t don t make process synchronization: – Race Condition
Review: Producer and Consumer Consumer #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0;
P d Producer while (true) {
}
/* produce an item and put in nextProduced */ while ((count == BUFFER_SIZE){ ){ } // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; BUFFER SIZE; count++;
Consumer Consumer while (true) { while (count == 0){ } // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count ; count--; /* consume the item in nextConsumed
}
A Atomic i P Process • The Th statements t t t counter++; counter--; must be performed atomically. • Atomic operation means an operation that completes in its entirety without interruption.
Bounded--Buffer Bounded • Perintah “count++” diimplementasikan pada bahasa mesin: – register1 i t 1 = counter t – register1 = register1 + 1 – counter = register1
• Perintah “count--” “count ” diimplementasikan pada bahasa mesin: – register2 = counter – register2 = register2 – 1 – counter = register2
• Jika kedua perintah tersebut berusaha mengakses nilai counter secara konkuren, maka dapat terjadi kesalahan pada nilai counter karena sifat bahasa mesin yang menggunakan register untuk mengupdate nilai counter • Kesalahan nilai akhir counter dapat terjadi, tergantung penjadwalan j y yang g dilakukan terhadap pp proses y yang g dari p dilakukan oleh produsen dan konsumen. • Dengan kata lain, masalah tersebut belum tentu terjadi, tapi dapat terjadi
Mi l Misalnya • Consider this execution interleaving with “count = 5” initially: t0: producer execute register1 = count
{register1 = 5}
t1: producer execute register1 = register1 + 1 {register1 = 6}
t2: consumer execute register2 = count
{register2 = 5}
t3: consumer execute register2 = register2 - 1 {register2 = 4}
t4: producer execute count = register1 {count = 6 } t5: consumer execute count = register2 {count = 4}
R Race C Condition di i • Race condition: situasi dimana beberapa proses mengakses dan memanipulasi suatu data secara konkuren. – Nilai akhir dari data tersebut tergantung dari proses mana yang terakhir mengubah data
• Untuk menghindari terjadinya situasi tersebut, semua proses yang dapat mengakses suatu data tertentu harus disinkronisasi
C ii lS Critical Section i • Lebih da darii sat satu proses p o e berlomba-lomba be lomb lomb pada saat yang sama untuk menggunakan data yang sama. • Setiap proses memiliki segmen kode yang digunakan g untuk mengakses g data y yang g digunakan secara bersama-sama. – Segmen kode tersebut disebut critical section. section
• Masalahnya: menjamin bahwa jika suatu proses sedang p g menjalankan j critical section, maka proses lain tidak boleh masuk ke dalam critical section tersebut.
Solusi masalah critical section i • Mutual Exclusion
– Tidak ada dua proses yang berada di critical section pada saat yang bersamaan.
• Terjadi T j di kemajuan k j (Progress) (P )
– Jika tidak ada proses yang sedang berada di critical section, maka proses lain yang ingin menjalankan critical iti l section ti d dapat t masuk k ke k dalam d l critical iti l section ti tersebut.
• Ada batas waktu tunggu (Bounded Waiting)
– Tidak ada proses yang menunggu selama-lamanya untuk masuk ke dalam critical section – Assume that each process executes at a nonzero speed d – Tidak ada asumsi lain mengenai kecepatan relatif setiap proses ataupun jumlah CPU.
I Implementasi l i solusi l i • Solusi perangkat lunak – Dengan menggunakan algoritma-algoritma yang nilai kebenarannya tidak tergantung pada asumsi-asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang bukan nol
• Solusi perangkat keras –T Tergantung t pada d beberapa b b i t k i mesin instruksi i tertentu, misalnya dengan me-non-aktifkan interuppt atau dengan mengunci (lock) suatu variabel tertentu
Implementasi software dan asumsinya i • Misal Mi l hanya h ada d dua d proses, yaitu it P0 dan d P1. P1 • Struktur umum dari proses Pi (proses yang lain: Pj)
• Proses-proses Proses proses tersebut boleh berbagi beberapa variabel yang sama untuk mensinkronisasikan apa yang akan dilakukan oleh setiap proses t tersebut. b t
Algoritma g 1 • Variabel yang digunakan bersama: •
– int turn; //pada awalnya turn = 0 – turn = i; //Pi dapat masuk ke critical section Untuk proses Pi
• If P0 ingin akses critical section turn diset ke 0, if P1 juga akses, turn diset ke 1 Mutual exclusion but not progress nor bounded buffer If P0 selesai menggunakan critical section, turn diset ke 1, tapi P1 tidak ingin masuk ke critical section, section jadi turn tidak akan diset ke 0.
Algoritma 2 • Variabel yang digunakan bersama: – boolean b l fl flag[2]; [2] • pada awalnya flag [0] = flag [1] = false
– flag [i] = true; //Pi dapat masuk kk ke critical iti l section ti
If P0 mengakses critical section P0 mengeset flag[0] ke True. Sementara P1 masih menggunakan critical section, P0 akan menunggu If P0 finish menunggu. finish, P0 akan set flag[0] ke false. false Mutual exclusion but not progress nor bounded buffer Tapi jika P0 & P1 ingin akses ke c critical itical section secara seca a konkuren, konk en keduanya akan set flag[0] & flag[1] ke true, dan semua proses menunggu terus…
P Peterson’s ’ Algorithm Al ih • The Th two processes share h two variables: – int turn; g[ ]; – Boolean flag[2];
• The variable turn indicates whose turn it is to enter the critical section section. • The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!
Algorithm for Process Pi while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } Mutual exclusion, exclusion progress progress, and bounded buffer! If P0 want to access critical section, P0 will set flag[0] to true and turn to P1.
B k Bakery Algorithm Al ih Critical C iti l section ti ffor: n processes • Sebelum memasuki critical section, setiap proses menerima sebuah nomor. nomor • Yang memegang ID terkecil yang dilayani dahulu. • Skema penomoran selalu naik secara berurut, contoh: 1, 2, 2, 2, 3, 3, 4, 5… • Diperkenalkan pertama kali oleh Leslie Lamport. • Data yang digunakan bersama – boolean choosing [n]; – int number [n];
• Struktur data diinisialisi awal ke false dan 0. • (a,b) < (c,d) jika a < c atau jika a = c dan b < d
B k Bakery Algorithm Al ih
Si k Sinkronisasi i i • Metode dalam sinkronisasi hardware
– Processor Synchronous ( Disable Interrupt ) – Memory Synchronous ( Instruksi Test-And-Set )
• Interrupt used in Round Robin Algorithm, Algorithm with quantum time • Processor synchronous – Dengan men men-disable disable interupsi (interrupt) – Dalam lingkungan multiprocessor:
• Hanya satu processor bisa didisable interruptnya
• Memory synchronous
– Instruksi Test-And-Set, Wait-Signal, dan Semaphore – Dalam lingkungan multiprocessor:
• Bisa dilakukan • Semua processor tidak dapat memakai resource karena proteksi dilakukan di memory
– Instruksi harus bersifat atomik
T TestAndSet Test A dS dengan AndSet d JJava
Kelemahan: bisa terjadi starvation & busy waiting
M Mutual l Exclusion: E l i S Swap HardwareData lock = new HardwareData(false); // a shared lock HardwareData key = new HardwareData(true); // my key while (true) { key.set(true); // my key is now true do { lock.swap(key); y key yg got lock’s content. // my
1st Process
2nd Process
key true
key true
false
I got it! 1st swap
2nd swap
} while (key.get() == true); // this means lock was true locked! criticalSection( c t ca Sect o ( ); // now o in c critical t ca sect section o code lock.set(false); nonCriticalSection( ); // out of critical section }
Lock false
true
Mutual Exclusion: Memory synchronous h • Kelebihan: Kelebihan
– Dapat diaplikasikan ke beberapa prosesor, dengan sharing memory – Simpel dan mudah diverifikasi – Dapat digunakan untuk banyak critical section
• Kekurangan:
– Busy-waiting memakan processor time yang besar – Mungkin terjadi starvation – Deadlock
• Jika low priority process mendapat critical region dan higher priority process butuh juga, higher priority process akan mendapat processor dan low priority process akan k menunggu
S Semaphore h • Invented by Djikstra (1960) • Semaphore digunakan untuk memberi sinyal y • Non negative integer • Jika proses menunggu sinyal, maka dia akan ditunda sampai sinyal yg ditunggu tersebut terkirim • Operasi: p wait dan signal g • Wait dan signal operations tidak dapat diinterupt • Queue digunakan untuk menahan proses proses yang sedang menunggu semaphore
S Semaphore h • Two standard operations modify S: wait() and signal() – Originally called P() and V() • Can only be accessed via two indivisible (atomic) operations – wait (S) { while S <= 0 ; // no-op S--; } jika s < 0 akan menunggu, lalu menjalankan proses lain – signal (S) { S++; } memberikan kesempatan p bagi g p para p proses untuk berkompetisi mendapatkan semafore
S Semaphore: h Wait W i - Spinlock S i l k
Semaphore: Wait – non spinlock i l k
S Semaphore: h Signal Si l
C Contoh hS Semaphore h
Test(s) = if mutex > 0 then mutex = mutex – 1 Inc(s) = mutex = mutex + 1
I Implementasi l iS Semaphore h • Windows Wi d – Fungsi yg dipakai adalah CreateSemaphore – Biasanya Bi digunakan di k untuk t k membatasi b t i jumlah j l h thread yang memakai suatu resource secara bersamaan
• Java – Semafor di Java Java™ bersifat transparan oleh programmer • Java™ menyembunyikan Semafor dibalik konsep monitor • Reserved Word yang dipakai Java™ adalah synchronized
Classical Problems of S Synchronization h i ti • Bounded-Buffer Problem • Readers and Writers Problem • Dining-Philosophers Problem
B Bounded d d Buffer B ff • Penge Pengertian: ti n temp tempatt penampung pen mp ng d data t yang ng ukurannya terbatas • Contoh: proses produsen dan konsumen • Masalah produsen produsen-konsumen konsumen – Produsen menaruh data pada buffer. Jika buffer tersebut sudah terisi penuh, maka produsen tidak melakukan apa-apa apa apa dan menunggu sampai konsumen mengosongkan isi buffer. – Konsumen K mengambil bil data d dari d i buffer. b ff Jika Jik buffer tersebut kosong, maka konsumen tidak p p dan menunggu gg sampai p melakukan apa-apa buffer tersebut diisi oleh produsen.
Penyelesaian dgn S Semaphore h • Semafor S f mutex t – Menyediakan mutual exclusion untuk mengakses buffer – Inisialisasi dengan nilai 1
• Semafor full – Menyatakan jumlah buffer yang sudah terisi – Inisialisasi dengan nilai 0
• Semafor empty – Menyatakan jumlah buffer yang kosong – Inisialisasi dengan nilai n (jumlah buffer)
B Bounded d d Buffer B ff Producer P d
• Init => full = 0,, empty p y = n,, mutex = 1
B Bounded d d Buffer B ff Consumer C
Contoh Producer & Consumer Consumer
The Readers Readers--Writers P bl Problem
• Multiple p readers or a single g writer can use DB.
writer
X
reader reader
writer it reader
reader
writer
X
X writer
reader reader reader reader
R d & Writers Reader W i • Diketahui Dik t h i dua d macam proses: – Pembaca (reader) – Penulis (writer)
• Kedua jenis proses berbagi sumber daya penyimpanan yang sama, Misal: Basis data • Tujuan: data tidak korup dan inkonsisten • Kondisi: – P Proses-proses pembaca b dapat d membaca b sumber b daya d secara simultan – Hanya boleh ada satu penulis menulis pada setiap saat – Bila ada yang menulis, tidak boleh ada yang membaca
Sh Shared d Data D • Data set • Semaphore mutex initialized to 1, 1 tanda mutual exclusion • Semaphore S h wrtt initialized i iti li d tto 1 1, ttanda d untuk menulis • Integer readcount initialized to 0, tanda untuk membaca
Readers--Writers Readers • The structure of a writer process while (true) { wait (wrt) ( ); //
writing iti is i performed f d
signal (wrt) ; }
R d ReadersReaders -Writers W i •
The structure of a reader process while (true) { wait (mutex) ; readcount ++ ; if (readcount == 1) wait (wrt) ; signal (mutex) // reading is performed
}
wait (mutex) ; readcount d --; if (readcount == 0) signal (wrt) ; signal (mutex) ;
Di i Dining Phil Philosopher h • Diketahui:
– Mie (Data) – Sebuah meja bundar – N filsuf duduk melingkar di meja bundar – Antara dua filsuf terdapat sebuah b h sumpit it – Didepan setiap filsuf terdapat semangkuk mie
• S Setiap ti filsuf fil f hanya h dapat d t berada pada salah satu kondisi berikut: – Berpikir – Lapar – Makan
Di i Dining Phil Philosopher h • Shared data –Bowl of rice (data set) – Semaphore chopstick [5] initialized to 1
• Dua hal yang harus diperhatikan: – Deadlock: Semua filsuf ingin makan dan telah memegang sumpit – Starvation: Ada filsuf yang kelaparan dalam waktu yang lama
The Structure of Philosopher i
Philosopher I While (true) { wait ( chopstick[i] ); //kanan wait ( chopStick[ (i + 1) % 5] ); //kiri // eat signal ( chopstick[i] ); //kanan signal (chopstick[ (i + 1) % 5] ); //kiri
Waiting
Picked up
// think }
A deadlock occurs!
K l Kelemahan h S Semaphore h • Termasuk Low Level pemeliharaannya, y , karena • Kesulitan dalam p tersebar dalam seluruh program. > dapat terjadi nonnon • Menghapus wait => mutual exclusion. • Menghapus signal => dapat terjadi deadlock • Error yang terjadi sulit untuk dideteksi
S System Model M d l • Assures that operations happen as a single logical unit of work, in its entirety, or not at all • Challenge is assuring atomicity despite computer system failures • Transaction - collection of instructions or operations that performs single logical function
– Here we are concerned with changes to stable storage – disk – Transaction is series of read and write operations – Terminated by commit (transaction successful) or abort (transaction failed) operation – Aborted transaction must be rolled back to undo any changes it performed
T Types off Storage S Media M di • Volatile storage – information stored here does not survive system crashes – Example: main memory, cache
• Nonvolatile storage – information usually survives crashes – Example: disk and tape
• Stable storage – information never lost – Not actually possible, so approximated via replication or RAID to devices with independent failure modes
L -Based LogLog B d Recovery R • Re Record o d to stable t ble storage to ge information info m tion about bo t all modifications by a transaction • Most common is write-ahead logging – Log on stable storage, each log record describes single transaction write operation, i l di including • • • •
Transaction name Data item name Old value New value
– <Ti starts> written to log when transaction Ti starts – <Ti commits> written when Ti commits
Log--Based Recovery Log Al Algorithm ih • U Using i th the llog, system t can handle h dl any volatile l til memory errors – Undo(Ti) restores value of all data updated by Ti – Redo(Ti) sets values of all data in transaction Ti to new values
• Undo(Ti) and redo(Ti) must be idempotent
– Multiple executions must have the same result as one execution
• If system fails, restore state of all updated data via log – If log contains <Ti starts> without <Ti commits>, commits> undo(Ti) – If log contains <Ti starts> and <Ti commits>, redo(Ti)
Ch k i Checkpoints • L Log could ld b become long, l and d recovery could take long • Checkpoints Ch k i t shorten h t log l and d recovery time. • Checkpoint Ch k i t scheme: h 1. Output all log records currently in volatile storage to stable storage 2. Output all modified data from volatile to stable storage g 3. Output a log record
to the log on stable storage
NEXT • Deadlock
