Bài giảng Hệ điều hành - Chương 3: Đồng bộ và giải quyết tranh chấp - Lê Ngọc Minh

false;
 Remainder Section
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -30-
 15
 Semaphore
‰ Là công cụ đồng bộ cung cấp bởi OS mà không đòi hỏi
 busy waiting
‰ Semaphore S là một biến số nguyên, ngoài thao tác
 khởi động biến thì chỉ có thể được truy xuất qua hai tác
 vụ có tính đơn nguyên (atomic) và loại trừ (mutual 
 exclusive)
 – wait(S) hay còn gọi là P(S): giảm giá trị semaphore. Nếu giá trị
 này âm thì process thực hiện lệnh wait() bị blocked.
 – signal(S) hay còn gọi là V(S): tăng giá trị semaphore. Nếu giá trị
 này âm, một process đang blocked bởi một lệnh wait() sẽ được
 hồi phục để thực thi.
‰ Tránh busy waiting: khi phải đợi thì process sẽ được đặt
 vào một blocked queue, trong đó chứa các process đang
 chờ đợi cùng một sự kiện.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -31-
 Hiện thực Semaphore 
‰ Định nghĩa semaphore như một record
 typedefstru c t {
 intvalue;
 structprocess *L ; /* process queue */
 } sem aphore;
‰ Giả sử có hai tác vụ đơn:
 – block: tạm treo process nào thực thi lệnh này.
 – wakeup(P): hồi phục quá trình thực thi của một
 process P đang blocked .
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -32-
 16
 Hiện thực Semaphore (t.t)
‰ Các tác vụ semaphore được định nghĩa như sau
 wait(S):
 S.value--;
 if (S.value < 0) { 
 add this process to S.L;
 block;
 }
 signal(S): 
 S.value++;
 if (S.value <= 0) {
 remove a process P from S.L;
 wakeup(P);
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -33-
 Hiện thực Semaphore (t.t)
‰ Khi một process phải chờ trên semaphore S, nó
 sẽ bị blocked và được đặt trong hàng đợi
 semaphore
 – Hàng đợi này là danh sách liên kết các PCB
‰ Tác vụ signal() thường sử dụng cơ chế FIFO để
 chuyển một process từ hàng đợi và đưa vào
 hàng đợi ready
‰ block() và wakeup() thay đổi trạng thái của
 process – đó là các system call cơ bản.
 – Block: chuyển từ running sang waiting
 – wakeup: chuyển từ waiting sang ready
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -34-
 17
 Hiện thực Mutex với Semaphore
‰ Dùng cho n process ‰ Shared data:
 semaphore mutex; 
‰ Khởi tạo S.value = 1
 /*initially mutex.value = 1*/
‰ Chỉ duy nhất một 1 
 ‰ Process Pi: 
 process được vào CS 
 (mutual exclusion)
 do {
 wait(mutex);
‰ Để cho phép k process 
 critical section
 vào CS, khởi tạo
 S.value = k signal(mutex);
 remainder section
 } while (1);
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -35-
 Đồng bộ process bằng semaphore
‰ Hai process: P1 và P2 ‰ Để đồng bộ hoạt động
 theo yêu cầu, P1 phải
 định nghĩa như sau: 
‰ Yêu cầu: lệnh S1 trong
 P1 cần được thực thi S1;
 trước lệnh S2 trong P2 signal(synch);
 ‰ Và P2 định nghĩa như sau:
‰ Định nghĩa semaphore 
 “synch” dùng đồng bộ wait(synch);
 S2;
‰ Khởi động semaphore:
 synch.value= 0
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -36-
 18
 Nhận xét
‰ Khi S.value >=0: số process có thể thực thi wait(S)mà
 không bị blocked = S.value
‰ Khi S.value<0: số process đang đợi trên S = |S.value|
‰ Atomic và mutual exclusion: không được xảy ra trường
 hợp 2 process cùng đang ở trong thân lệnh wait(S) và
 signal(S) (cùng semaphore S) tại một thời điểm (ngay cả
 với hệ thống multiprocessor) 
 ⇒ do đó, đoạn mã định nghĩa các lệnh wait(S) và
 signal(S) cũng chính là vùng xảy ra tranh chấp (critical 
 section)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -37-
 Nhận xét (t.t)
‰ wait() và signal() phải thực thi atomic và mutual 
 execution
‰ Vùng tranh chấp của các tác vụ wait(S) và signal(S) 
 thông thường rất nhỏ: khoảng 10 lệnh.
‰ Giải pháp cho vùng tranh chấp wait(S) và signal(S):
 – Uniprocessor: có thể dùng cơ chế cấm ngắt (disable 
 interrupt) để giải quyết tranh chấp (trong một khoảng thời
 gian rất ngắn). Phương pháp này không làm việc trên hệ
 thống multiprocessor.
 – Multiprocessor: có thể dùng các giải pháp software (như
 Dekker, Peterson) hoặc giải pháp hardware (test-and-set, 
 swap). Vì CS rất nhỏ nên chi phí cho busy waiting sẽ rất
 thấp.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -38-
 19
 Deadlock và Starvation
‰ Deadlock – hai hay nhiều process đang chờ đợi vô
 hạn định một sự kiện không bao giờ xảy ra (vd: sự
 kiện do một trong các process đang đợi tạo ra).
‰ Gọi S và Q là hai biến semaphore được khởi tạo = 1
 P0 P1
 P(S); P(Q);
 P(Q); P(S);
 MM
 V(S); V(Q);
 V(Q) V(S);
‰ Starvation (indefinite blocking) có thể xảy ra khi
 chúng ta bỏ process vào hàng đợi và lấy ra theo cơ
 chế LIFO.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -39-
 Các loại semaphore
‰ Counting semaphore: một số nguyên có giá trị
 không hạn chế.
‰ Binary semaphore: một số nguyên có giá trị nằm
 trong khoảng [0,1]. Binary semaphore rất dễ
 hiện thực.
‰ Chúng ta có thể hiện thực counting semaphore 
 S bằng binary semaphore.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -40-
 20
 Các bài toán đồng bộ
‰ Bài toán Bounded-Buffer
 – Dữ liệu chia sẻ:
 SEMAPHORE full, empty, mutex;
 – Khởi tạo:
 full = 0;
 empty = BUFFER_SIZE;
 mutex = 1;
circular buffer
 out in
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -41-
 Bounded Buffer (t.t)
 PRODUCER CONSUMER
do { do { 
 wait(full)
 nextp= new _item (); wait(mutex);
 wait(em pty); nextc= get_buffer_item (out);
 wait(mutex); 
  signal(mutex);
 insert_to_buffer(nextp); signal(em pty);
 signal(mutex); consum e_item (nextc);
 signal(full); 
} while (1); } while (1);
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -42-
 21
 Bài toán “Dining Philosopher”
‰ 5 triết gia ngồi ăn và suy
 nghĩ
‰ Mỗi người cần 2 chiếc
 đũa để ăn
‰ Trên bàn chỉ có 5 đũa
‰ Bài toán này minh hoạ sự
 khó khăn trong việc phân
 phối tài nguyên giữa các
 ‰Dữ liệu chia sẻ:
 process sao cho không semaphore chopstick[5];
 xảy ra deadlock và
 starvation
 ‰Khởi đầu các biến đều là 1
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -43-
 Bài toán “Dining Philosopher”
 Triết gia thứ i:
 do {
 wait(chopstick[i])
 wait(chopstick[ (i+1) % 5 ] )
 eat
 signal(chopstick[i]);
 signal(chopstick[ (i+1) % 5] );
 think
 } while (1);
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -44-
 22
 Bài toán “Dining Philosopher”
‰ Giải pháp trên có thể gây ra deadlock
 – Khi tất cả triết gia đói bụng cùng lúc và đồng thời
 cầm một chiếc đũa bên tay trái ⇒ deadlock
‰ Một số cách giải quyết deadlock
 – Cho phép nhiều nhất 4 triết gia ngồi vào cùng một lúc.
 – Cho phép triết gia cầm đũa khi cả hai chiếc đũa đều
 sẵn sàng (nghĩa là tác vụ cầm đũa phải xảy ra trong
 CS)
 – Triết gia ngồi ở vị trí lẻ cầm đũa bên trái trước, sau đó
 mới đến đũa bên phải, trong khi đó triết gia ở vị trí
 chẵn cầm đũa bên phải trước, sau đó mới đến đũa
 bên trái
‰ Có thể xảy ra trường hợp starvation (tại sao?)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -45-
 Bài toán Readers-Writers
‰ Dữ liệu chia sẻ ‰Reader Process
 semaphore mutex=1;
 semaphore wrt = 1; wait(mutex);
 integer readcount =0; readcount++;
 if (readcount == 1)
‰ Writer process wait(wrt);
 wait(wrt); signal(mutex);
 ... ...
 writing is performed reading is performed
 ... ...
 signal(wrt); wait(mutex);
 readcount--;
 if (readcount == 0)
 signal(wrt);
 signal(mutex):
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -46-
 23
 Bài toán Readers-Writers (t.t)
‰ mutex: bảo vệ biến readcount
‰ wrt
 – Bảo đảm mutual exclusion đối với các writer
 – Được sử dụng bởi reader đầu tiên hoặc cuối cùng
 vào hay ra khỏi vùng tranh chấp.
‰ Nếu một writer đang ở trong CS và có n reader 
 đang đợi thì một reader được xếp trong hàng
 đợi của wrt và n-1 reader kia trong hàng đợi của
 mutex
‰ Khi writer thực thi signal(wrt), chúng ta có thể
 phục hồi thực thi của một trong các reader đang
 đợi hoặc writer đang đợi ⇒ dựa vào scheduler
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -47-
 Các vấn đề với semaphore
‰ Semaphore cung cấp một công cụ mạnh mẽ để bảo
 đảm mutual exclusion và phối hợp đồng bộ các process
‰ Tuy nhiên, các tác vụ wait(S) và signal(S) nằm rải rác ở
 rất nhiều processes ⇒ khó nắm bắt được hiệu ứng của
 các tác vụ này. Nếu không sử dụng đúng ⇒ có thể xảy
 ra tình trạng deadlock hoặc starvation.
‰ Một process bị “die” có thể kéo theo các process khác
 cùng sử dụng biến semaphore.
 signal(mutex) wait(mutex) signal(mutex)
 critical section critical section critical section
 wait(mutex) wait(mutex) signal(mutex)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -48-
 24
 Critical Region (CR)
‰ Critical Region còn được gọi là conditional critical region 
 (CCR)
‰ Cơ sở: dựa trên semaphore, xây dựng cấu trúc ngôn ngữ
 cấp cao, thuận tiện hơn cho người lập trình.
‰ Một biến chia sẻ v kiểu dữ liệu T, khai báo như sau:
 v: shared T
‰ Biến chung v chỉ có thể được truy xuất qua phát biểu sau
 region v when B do S
‰ Các region tham chiếu đến cùng một biến chia sẻ thì bị
 loại trừ tương hỗ.
‰ Khi một process muốn thực thi các lệnh trong region, 
 biểu thức Boolean B được kiểm tra. Nếu B=true, lệnh S
 được thực thi. Nếu B= false, process bị trì hoãn cho đến
 khi B = true và không có process nào đang ở trong
 region cùng tham chiếu đến biến v.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -49-
 CR và bài toán bounded-buffer
 Dữ liệu chia sẻ: Producer
 region buffer when (count < n) {
 structbuffer 
 pool[in] = nextp;
 { in = ( in + 1 ) % n;
 intpool[n]; count++;
 intcount; }
 intin;
 Consum er
 intout;
 } region buffer when (count > 0){
 nextc = pool[out];
 out = ( out + 1 ) % n;
 count--;
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -50-
 25
 Monitor
‰ Cũng là một cấu trúc ngôn ngữ cấp cao (high-level 
 language construct) tương tự CR, có chức năng như
 semaphore nhưng dễ điều khiển hơn
‰ Xuất hiện trong nhiều ngôn ngữ lập trình đồng thời như
 – Concurrent Pascal, Modula-3, uC++, Java...
‰ Có thể hiện thực bằng semaphore (!!!)
 shared data
 ... Entry queue
 operations
 initialization
 code
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -51-
 Monitor
‰ Là một module phần mềm trong đó bao gồm
 – Một hoặc nhiều thủ tục/hàm (procedure)
 – Một đoạn code khởi tạo (initialization code)
 – Các biến dữ liệu cục bộ (local data variable)
‰ Đặc tính của monitor:
 – Local variable chỉ có thể truy xuất bởi các thủ tục của
 monitor
 – Process vào monitor bằng cách gọi một trong các thủ
 tục đó
 – Chỉ có một process có thể vào monitor tại một thời
 điểm ⇒ Mutual Exclusion được bảo đảm
‰ Hiện thực monitor (tham khảo tài liệu)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -52-
 26
 Cấu trúc của Monitor
 m onitor m onitor-nam e
 {
 shared variable declarations
 procedure body P1 () {
 . . .
 }
 procedurebody P2 () {
 . . .
 } 
 procedure body Pn () {
 . . .
 } 
 {
 initialization code
 }
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -53-
 Condition Variable
‰ Nhằm cho phép một process đợi trong monitor, phải khai
 báo biến điều kiện (condition variable) 
 condition a, b;
‰ Các biến điều kiện đều cục bộ và chỉ được truy cập bên
 trong monitor.
‰ Chỉ có thể truy xuất và thay đổi bằng hai thủ tục:
 – cwait(a): process gọi tác vụ này sẽ bị block trên biến điều kiện a 
 » process này chỉ có thể tiếp tục thực thi khi có process khác
 thực hiện tác vụ csignal(a);
 – csignal(a): phục hồi quá trình thực thi của process bị block trên
 biến điều kiện a.
 » Nếu có nhiều process: chỉ chọn một
 » Nếu không có process: không có tác dụng.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -54-
 27
 Monitor có condition variable
 shared data entrance queue
 a
 b ª Các process có thể đợi ở
 entrance queue hoặc đợi ở các
 condition queue (a, b,...)
 ª Khi thực hiện lệnh cwait(a), 
 ... process sẽ được chuyển vào
 condition queue a
 operations ª Lệnh csignal(a) chuyển một
 process trong condition queue a
 vào monitor
 initialization ª Do đó, process gọi csignal(cn) 
 code sẽ bị blocked và được đưa vào
 urgent queue
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -55-
 Monitor có condition variable
 entrance
 queue
m onitor waiting area entrance
 MONITOR
 local data
 condition c1
 conditional variable
 cw ait(c1)
 Procedure 1
 ...
 condition cn ...
 cw ait(cn) Procedure k
 urgent queue initialization code
 csignal exit
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -56-
 28
 Monitor và Dining Philosopher
type dining-philosophers = monitor 
{
 var state : array [0..4] of :(thinking, hungry, eating);
 var self : array [0..4] of condition;
 procedure pickup (i: 0..4);
 begin
 state[i] := hungry;
 test (i);
 if state[i] ≠ eating then self[i].wait;
 end;
}
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -57-
 Monitor và Dining Philosopher
 monitor dp
 {
 enum {thinking, hungry, eating} state[5];
 condition self[5];
 void pickup(int i); 
 void putdown(int i);
 void test(int i);
 void init() 
 {
 for (int i = 0; i < 5; i++)
 state[i] = thinking;
 }
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -58-
 29
 Dining Philosopher (t.t)
 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);
 }
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -59-
 Dining Philosopher (t.t)
 void test(int i) {
 if ( (state[(I + 4) % 5] != eating) &&
 (state[i] == hungry) &&
 (state[(i + 1) % 5] != eating)) {
 state[i] = eating;
 self[i].signal();
 }
 }
‰ Trước khi ăn, mỗi triết gia phải gọi hàm pickup(), ăn
 xong rồi thì phải gọi hàm putdown()
 dp.pickup(i);
 /* yum...yum...yum */
 dp.putdown(i);
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -60-
 30