Process Synchronization

Process Synchronization SISTIM OPERASI (Operating System) IKI-20230 Johny Moningka ([email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001

Process Synchronization n n n n n n

Background The Critical-Section Problem Synchronization Hardware Semaphores Classical Problems of Synchronization Monitors

OS Processes JM -2000/v1.1/2

1

Synchronization n

Sinkronisasi: n

n

Koordinasi akses ke shared data, misalkan hanya satu proses yang dapat menggunakah shared var. Contoh operasi terhadap var. “counter” harus dijamin di-eksekusi dalam satu kesatuan (atomik) : • counter := counter + 1; • counter := counter - 1;

n

Sinkronisasi merupakan “issue” penting dalam rancangan/implementasi OS (shared resources, data, dan multitasking).


The Critical-Section Problem n n n

n

n proses mencoba menggunakan shared data bersamaan Setiap proses mempunyai “code” yang mengakses/ manipulasi shared data tersebut => “critical section” Problem: Menjamin jika ada satu proses yang sedang “eksekusi” pada bagian “critical section” tidak ada proses lain yang diperbolehkan masuk ke “code” critical section dari proses tersebut. Structure of process Pi repeat entry section critical section exit section reminder section until false; OS Processes JM -2000/v1.1/4

2

Solution (pre-requsite) n

Ide: n

n

n

Mencakup pemakaian secara “exclusive” dari shared variable tersebut Menjamin proses lain dapat menggunakan shared variable tersebut

Solusi “critical section problem” harus memenuhi: 1.

2.

Mutual Exclusion: Jika proses Pi sedang “eksekusi” pada bagian “critical section” (dari proses Pi) maka tidak ada prosesproses lain dapat “eksekusi” pada bagian critical section dari proses-proses tersebut. Progress: Jika tidak ada proses sedang eksekusi pada critical section-nya dan jika terdapat lebih dari satu proses lain yang ingin masuk ke critical section, maka pemilihan siapa yang berhak masuk ke critical section tidak dapat ditunda tanpa terbatas. OS Processes JM -2000/v1.1/5

Solutions (cont.) 3.

Bounded Waiting: Terdapat batasan berapa lama suatu proses harus menunggu giliran untuk mengakses “critical section” – jika seandainya proses lain yang diberikan hak akses ke critical section. •

•

Menjamin proses dapat mengakses ke “critical section” (tidak mengalami starvation: proses se-olah berhenti menunggu request akses ke critical section diperbolehkan). Tidak ada asumsi mengenai kecepatan eksekusi prosesproses n tersebut.


3

Simple solution: case 2 process n n

Hanya 2 proses Struktur umum dari program code Pi dan Pj: repeat entry section critical section exit section reminder section until false;

n

Software solution: merancang algoritma program untuk solusi critical section n

Proses dapat mengunakan “common var.” untuk menyusun algoritma tsb. OS Processes JM -2000/v1.1/7

Algorithm 1 n

Shared variables: n

n

n

n

var turn: (0..1); initially turn = 0 turn = i ⇒ Pi dapat masuk ke critical section

Process Pi repeat while turn ≠ i do no-operation; critical section turn := j; reminder section until false; Satisfies mutual exclusion, but not progress OS Processes JM -2000/v1.1/8

4

Algorithm 2 n

Shared variables n n

n

n

var flag: array [0..1] of boolean; initially flag [0] = flag [1] = false. flag [i] = true ⇒ Pi ready to enter its critical section

Process Pi repeat flag[i] := true; while flag[j] do no-op; critical section flag [i] := false; remainder section until false; Satisfies mutual exclusion, but not progress requirement. OS Processes JM -2000/v1.1/9

Algorithm 3 n Combined n Process

shared variables of algorithms 1 and 2.

Pi

repeat flag [i] := true; turn := j; while (flag [j] and turn = j) do no-op; critical section flag [i] := false; remainder section until false; n Meets all three requirements; solves the critical-section problem for two processes. OS Processes JM -2000/v1.1/10

5

“Bakery Algorithm” n

Critical Section for n processes n

n

Sebelum proses akan masuk ke dalam “critical section”, maka proses harus mendapatkan “nomor” (tiket). Proses dengan nomor terkecil berhak masuk ke critical section. • If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first.

n

The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5...


Bakery Algorithm (Cont.) n Notasi

<≡ lexicographical order (ticket #, process id #) => pasti unik n

n

(a,b) < (c,d) if a < c or if a = c and b < d note: (b dan d pasti tidak sama) max (a0,…, a n-1) is a number, k, such that k ≥ a i for i 0, …, n – 1

n Shared

data var choosing: array [0..n – 1] of boolean; number: array [0..n – 1] of integer, n Initialized: choosing =: false ; number => 0 OS Processes JM -2000/v1.1/12

6

Bakery Algorithm (Cont.) repeat choosing[i] := true; number[i] := max(number[0], number[1], …, number[n – 1])+1; choosing[i] := false; for j := 0 to n – 1 do begin while choosing[j] do no-op; while number[j] ≠ 0 and (number[j],j) < (number[i], i) do no-op; end; critical section number[i] := 0; remainder section until false; OS Processes JM -2000/v1.1/13

Synchronization Hardware n

Memerlukan dukungan hardware (prosesor) n n

n

Dalam bentuk “instruction set” khusus: test-and-set Menjamin operasi atomik (satu kesatuan): test nilai dan ubah nilai tersebut.

Test-and-Set dapat dianalogikan dengan kode:

function Test-and-Set (var target:boolean): boolean; begin Test-and-Set := target; target := true; end; OS Processes JM -2000/v1.1/14

7

Test-and-Set (mutual exclusion) n

Mutual exclusion dapat diterapkan: n

n

n

Gunakan shared data, variabel: lock: boolean (initially false) lock: menjaga critical section

Process Pi: repeat while Test-and-Set (lock) do no-op; .. critical section .. lock := false; remainder section until false; OS Processes JM -2000/v1.1/15

Semaphore n n

Synchronization tool that does not require busy waiting. Semaphore S – integer variable n

Dapat dijamin akses ke var. S oleh dua operasi atomik: • wait (S): while S ≤ 0 do no-op; S := S – 1; • signal (S): S := S + 1;


8

Example: n processes n

Shared variables n n

n

var mutex : semaphore initially mutex = 1

Process Pi repeat wait(mutex); critical section signal(mutex); remainder section until false; OS Processes JM -2000/v1.1/17

Semaphore Implementation n Define

a semaphore as a record type semaphore = record value: integer L: list of process; end; n Assume two simple operations: n n

block() : suspends the process that invokes it. wakeup(P) : resumes the execution of a blocked process P.


9

Implementation (Cont.) n Semaphore

operations now defined as

n

wait(S ):

S.value := S.value – 1; if S.value < 0 then begin add this process to S.L; block; end;

n

signal(S ): S.value := S.value + 1; if S.value ≤ 0 then begin remove a process P from S.L; wakeup(P ); end; OS Processes JM -2000/v1.1/19

Semaphore: Synchronization Tool n n

Execute B in Pj only after A executed in Pi Use semaphore flag initialized to 0 n

Code: Pi Pj M M A wait(flag) signal(flag) B


10

Two Types of Semaphores n

Counting semaphore n

n

Integer value can range over an unrestricted domain. Efektif untuk pemakaian membatasi jumlah proses, counter (blok pada nilai tertentu) dll. • Semaphore s = 10;

n

Binary semaphore n n

Integer value can range only between 0 and 1; Digunakan untuk mutula exclusion: membatasi hanya ada satu proses pada critical section. • Semaphore s = 1; OS Processes JM -2000/v1.1/21

Semaphore: bounded buffer C

P n Shared data (array of item): buffer Semaphore:

Binary Semaphore mutex; // mutual exclusion akses ke buffer Semaphore empty_slot; // slot buffer yang kosong : Semaphore full_item; // item di buffer;

Inisialisasi: mutex = 1; empty_slot = n; full_item = 0;


11

Semaphrore: bounded buffer Producer: do .. produce item pada nextp; wait(empty_slot); wait(mutex); …(critical section)

… add nextp to buffer; … signal(mutex); signal(full_item); while (true);

Consumer: do wait(full_item); wait(mutex); …(critical section)

… remove nextp buffer; … signal(mutex); signal(empty_slot); .. consume item nextp; while (true); OS Processes JM -2000/v1.1/23

Deadlock and Starvation n Deadlock

– two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes. n Let S and Q be two semaphores initialized to 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S); M M signal(S); signal(Q); signal(Q) signal(S); n Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. OS Processes JM -2000/v1.1/24

12

Process Synchronization

Recommend Documents