›
›

Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Tiết 3) - Trường Đại học Công nghệ thông tin

pdf 52 trang Hùng Dũng 04/01/2024 380
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Tiết 3) - Trường Đại học Công nghệ thông tin", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_dieu_hanh_chuong_5_dong_bo_tiet_3_truong_dai_ho.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Tiết 3) - Trường Đại học Công nghệ thông tin

  1. HỆ ĐIỀU HÀNH Chương 5 – Đồng bộ (3) 1/17/2018 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 1
  2. Ơn tập chương 5 (2)  Khi nào thì xảy ra tranh chấp race condition?  Vấn đề Critical Section là gì?  Yêu cầu của lời giải cho CS problem?  Cĩ mấy loại giải pháp? Kể tên? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 2
  3. Mục tiêu chương 5 (3)  Biết được các giải pháp đồng bộ tiến trình theo kiểu “Sleep & Wake up” bao gồm: Semaphore Critical Region Monitor  Áp dụng các giải pháp này vào các bài tốn đồng bộ kinh điển 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 3
  4. Nội dung chương 5 (2)  Các giải pháp “Sleep & Wake up” Semaphore Các bài tốn đồng bộ kinh điển Critical Region Monitor  Áp dụng các giải pháp này vào các bài tốn đồng bộ kinh điển 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 4
  5. Các giải pháp “Sleep & Wake up” int busy; // =1 nếu CS đang bị chiếm int blocked; // sớ P đang bị khóa do{ if (busy){ blocked = blocked +1; sleep(); } else busy =1; CS; busy = 0; if (blocked !=0){ wakeup (process); blocked = blocked -1; } RS; } while (1); 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 5
  6. 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.  Ngồ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 (S=S-1) . Kế đĩ 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 (S=S+1) . Kế đĩ nếu giá trị này khơng dương, 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. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 6
  7. Semaphore (tt)  P(S) hay wait(S) sử dụng để giành tài nguyên và giảm biến đếm S=S-1  V(S) hay signal(S) sẽ giải phĩng tài nguyên và tăng biến đếm S= S+1  Nếu P được thực hiện trên biến đếm <= 0 , tiến trình phải đợi V hay chờ đợi sự giải phĩng tài nguyên 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7
  8. Semaphore (tt) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 8
  9. Hiện thực semaphore  Định nghĩa semaphore là một record typedef struct { int value; struct process *L; /* process queue */ } semaphore;  Giả sử hệ điều hành cung cấp hai tác vụ (system call): 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 process P đang blocked 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 9
  10. Hiện thực semaphore (tt)  Các tác vụ semaphore được hiện thực như sau void wait(semaphore S) { S.value ; if (S.value < 0) { add this process to S.L; block(); } } void signal(semaphore S) { S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } } 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 10
  11. Hiện thực semaphore (tt)  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 khi chọ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 block: chuyển từ running sang waiting wakeup: chuyển từ waiting sang ready 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 11
  12. Ví dụ sử dụng semaphore1 Shared data:  Dùng cho n process semaphore mutex; /* initially mutex.value = 1 */  Khởi tạo S.value = 1  Chỉ duy nhất một process Process Pi: được vào CS (mutual do { exclusion) wait(mutex); critical section  Để cho phép k process vào signal(mutex); CS, khởi tạo S.value = k remainder section } while (1); 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 12
  13. Ví dụ sử dụng semaphore2 Để đồng bộ hoạt động theo  Hai process: P1 và P2 yêu cầu, P1 phải định nghĩa  Yêu cầu: lệnh S1 trong P1 cần như sau: được thực thi trước lệnh S2 S1; trong P2 signal(synch);  Định nghĩa semaphore synch để đồng bộ  Khởi động semaphore: Và P2 định nghĩa như sau: synch.value = 0 wait(synch); S2; 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 13
  14. Ví dụ sử dụng semaphore3 Để đồng bộ hoạt động theo  Xét 2 tiến trình xử lý đoạn yêu cầu, P1 phải định nghĩa chương trình sau: như sau:  Tiến trình P1 {A1, A2} Tiến A1; trình P2 {B1, B2} signal(s1);,  Đồng bộ hĩa hoạt động của 2 tiến trình sao cho cả A1 và B1 wait(s2); đều hồn tất trước khi A2 và A2; B2 bắt đầu. Và P2 định nghĩa như sau:  Khởi tạo B1 semaphore s1.v = s2.v = 0 signal(s2); wait(s1); B2; 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 14
  15. 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 là |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 tranh chấp 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 15
  16. Nhận xét (tt)  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). Nhưng 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ư giải thuật Dekker, Peterson) hoặc giải pháp hardware (TestAndSet, Swap). Vì CS rất nhỏ nên chi phí cho busy waiting sẽ rất thấp. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 16
  17. 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 wait(S); wait(Q); wait(Q); wait(S); signal(S); signal(Q); signal(Q); signal(S); P0 thực thi wait(S), rồi P1 thực thi wait(Q), rồi P0 thực thi wait(Q) bị blocked, P1 thực thi wait(S) bị blocked.  Starvation (indefinite blocking) Một tiến trình cĩ thể khơng bao giờ được lấy ra khỏi hàng đợi mà nĩ bị treo trong hàng đợi đĩ. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 17
  18. Các loại semaphore  Counting semaphore: một sớ nguyên cĩ giá trị khơng hạn chế.  Binary semaphore: cĩ trị là 0 hay 1. Binary semaphore rất dễ hiện thực.  Cĩ thể hiện thực counting semaphore bằng binary semaphore 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 18
  19. Các bài tốn đồng bộ kinh điển  Bounded Buffer Problem  Dining-Philosophers Problem  Readers and Writers Problem 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 19
  20. Bài tốn bounder buffer  Dữ liệu chia sẻ: Semaphore full, empty, mutex;  Khởi tạo: full = 0; /* sớ buffers đầy */ empty = n; /* sớ buffers trớng */ mutex = 1; n buffers out 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 20
  21. Bài tốn bounder buffer (tt) producer consumer do { do { wait(full) nextp = new_item(); wait(mutex); wait(empty); nextc = get_buffer_item(out); wait(mutex); signal(mutex); insert_to_buffer(nextp); signal(empty); signal(mutex); consume_item(nextc); signal(full); } while (1); } while (1); 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 21
  22. Bài tốn “Dining Philosophers”  5 triết gia ngồi ăn và suy nghĩ  Mỡi người cần 2 chiếc đũa (chopstick) để ăn  Trên bàn chỉ cĩ 5 đũa  Bài tốn này minh họa 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à  Khởi đầu các biến đều là 1 starvation 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 22
  23. Bài tốn “Dining Philosophers” (tt) 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); 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 23
  24. Bài tốn “Dining Philosophers” (tt)  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 chiếc đũa bên tay trái ⇒ deadlock  Một sớ giải pháp khác giải quyết được 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 các đũa chỉ khi cả hai chiếc đũa đều sẵn sàng (nghĩa là tác vụ cầm các đũ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  Starvation? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 24
  25. Bài tốn Reader-Writers  Writer khơng được cập nhật dữ liệu khi cĩ một Reader đang truy xuất CSDL  Tại một thời điểm, chỉ cho phép một Writer được sửa đởi nội dung CSDL R2 R3 R1 W1 W2 Database 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 25
  26. Bài tốn Reader-Writers (tt) Reader process  Bộ đọc trước bộ ghi (first wait(mutex); reader-writer) readcount++;  Dữ liệu chia sẻ if (readcount == 1) wait(wrt); semaphore mutex = 1; signal(mutex); semaphore wrt = 1; int readcount = 0; reading is performed  Writer process wait(mutex); wait(wrt); readcount ; if (readcount == 0) writing is performed signal(wrt); signal(mutex); signal(wrt); 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 26
  27. Bài tốn Reader-Writers (tt)  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), hệ thớng cĩ thể phục hồi thực thi của một trong các reader đang đợi hoặc writer đang đợi. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 27
  28. 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, nếu 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) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 28
  29. Critical Region (CR)  Là một cấu trúc ngơn ngữ cấp cao (high-level language construct, được dịch sang mã máy bởi một compiler), 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 chia sẻ v chỉ cĩ thể được truy xuất qua phát biểu sau region v when B do S; /* B là một biểu thức Boolean */  Ý nghĩa: trong khi S được thực thi, khơng cĩ quá trình khác cĩ thể truy xuất biến v. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 29
  30. CR và bài tốn bounded buffer Dữ liệu chia sẻ: Producer region buffer when (count 0){ nextc = pool[out]; out = (out + 1) % n; count ; } 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 30
  31. Monitor  Cũng là một cấu trúc ngơn ngữ cấp cao 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, Java,  Cĩ thể hiện thực bằng semaphore 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 31
  32. Monitor (tt)  Là một module phần mềm, bao gồm Một hoặc nhiều thủ tục (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) shared data entry queue operations initialization Mơ hình của một monitor code đơn giản 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 32
  33. Monitor (tt)  Đặ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 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 33
  34. Cấu trúc của monitor monitor monitor-name{ shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } procedure body Pn ( ) { . . . } { initialization code } } 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 34
  35. 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ể thao tác lên biến điều kiện bằng hai thủ tục: a.wait: 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ụ a.signal a.signal: 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 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 35
  36. Monitor cĩ condition variable shared data entry queue a  Các process cĩ thể đợi ở entry b queue hoặc đợi ở các condition queue (a, b, )  Khi thực hiện lệnh a.wait, process sẽ được chuyển vào condition queue a  Lệnh a.signal chuyển một process operations từ condition queue a vào monitor  Khi đĩ, để bảo đảm mutual initialization exclusion, process gọi a.signal sẽ bị code blocked và được đưa vào urgent queue 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 36
  37. Monitor cĩ condition variable (tt) entry queue monitor waiting area entrance MONITOR local data condition c1 condition variables c1.wait procedure 1 condition cn cn.wait procedure k urgent queue initialization code cx.signal exit 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 37
  38. Monitor và dining philosophers 3 2 4 1 0 monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 38
  39. Monitor và dining philosophers (tt) 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); // left neighbor test((i + 1) % 5); // right } 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 39
  40. Monitor và dining philosophers (tt) 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 init() { for (int i = 0; i < 5; i++) state[ i ] = thinking; } } 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 40
  41. Monitor và dining philosophers (tt)  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); ăn dp.putdown(i);  Giải thuật khơng deadlock nhưng cĩ thể gây starvation. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 41
  42. Các bài tốn đồng bộ kinh điển  Bounded Buffer Problem  Readers and Writers Problem  Dining-Philosophers Problem 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 42
  43. Bài tập 1  Xét giải pháp phần mềm do Dekker đề nghị để tở chức truy xuất độc quyền cho 2 tiến trình. Hai tiến trình P0 và P1 chia sẻ các biến sau: Var flag : array [0 1] of Boolean; (khởi động là false) Turn : 0 1;  Cấu trúc một tiến trình Pi ( i=0 hay 1, và j là tiến trình cịn lại như sau: repeat flag[i] := true; while flag[j] do if turn = j then begin flag[i]:= false; Giải pháp này cĩ thỏa 3 while turn = j do ; yêu cầu trong việc giải flag[i]:= true; end; quyết tranh chấp khơng? critical_section(); turn:= j; flag[i]:= false; non_critical_section(); until false; 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 43
  44. Bài tập 2  Xét giải pháp đồng bộ hĩa sau: while (TRUE) { int j = 1-i; flag[i]= TRUE; turn = i; while (turn == j && flag[j]==TRUE); critical-section (); flag[i] = FALSE; Noncritical-section (); } Giải pháp này cĩ thỏa yêu cầu độc quyền truy xuất khơng? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 44
  45. Bài tập 3  Giả sử một máy tính khơng cĩ chỉ thị TSL, nhưng cĩ chỉ thị Swap cĩ khả năng hốn đởi nội dung của hai từ nhớ chỉ bằng một thao tác khơng thể phân chia: procedure Swap() var a,b: boolean); var temp : boolean; begin temp := a; a:= b; b:= temp; end; Sử dụng chỉ thị này cĩ thể tổ chức truy xuất độc quyền khơng? Nếu cĩ, xây dựng cấu trúc chương trình tương ứng. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 45
  46. Bài tập 4  Xets hai tiến trình sau: process A {while (TRUE) na = na +1; } process B {while (TRUE) nb = nb +1; } a. Đồng bộ hĩa xử lý của 2 tiến trình trên, sử dụng 2 semaphore tởng quát, sao cho tại bất kỳ thời điểm nào cũng cĩ nb <= na <= nb +10 b. Nếu giảm điều kiện chỉ cĩ làna <= nb +10, giải pháp của bạn sẽ được sửa chữa như thế nào? c. Giải pháp của bạn cĩ cịn đúng nếu cĩ nhiều tiến trình loại A và B cùng thực hiện? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 46
  47. Bài tập 5  Một biến X được chia sẻ bởi2 tiến trình cùng thực hiện đoạn code sau : do X = X +1; if ( X == 20) X = 0; while ( TRUE );  Bắt đầu với giá trị X 0= , chứng tỏ rằng giá trị X cĩ thể vượt quá 20. Cần sửa chữa đoạn chương trình trên như thế nào để đảm bảo X khơng vượt quá 20? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 47
  48. Bài tập 6  Xét2 tiến trình xử lý đoạn chương trình sau: process P1 { A1 ; A2 } process P2 { B1 ; B2 } Đồng bộ hĩa hoạt động của 2 tiến trình này sao cho cả A1 và B1 đều hồn tất trước khi A2 và B2 bắt đầu 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 48
  49. Bài tập 7  Tởng quát hĩa câu hỏi 6 cho các tiến trình cĩ đoạn chương trình sau: process P1 { for ( i = 1; i <= 100; i ++) Ai } process P2 { for ( j = 1; j <= 100; j ++) Bj } Đồng bộ hĩa hoạt động của 2 tiến trình này sao cho vớik bất kỳ (2<=k<=100), Ak chỉ cĩ thể bắt đầu khi B(k-1) đã kết thúc và Bk chỉ cĩ thể bắt đầu khi A(k-1) đã kết thúc. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 49
  50. Bài tập 8  Sử dụng semaphore để viết lại chương trình sau theo mơ hình xử lý đồng hành: w := x1 * x2 v := x3 * x4 y := v * x5 z := v * x6 x := w * y z := w * z ans := y + z 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 50
  51. Bài kiểm tra 30 phút Bài 1: Xét giải pháp đồng bộ hĩa sau cĩ bảo đảm 3 điều kiện khơng? while (TRUE) { int j = 1-i; flag[i]= TRUE; turn = j; while (turn == j && flag[j]==TRUE); critical-section (); flag[j] = FALSE; Noncritical-section (); } Bài 2: Sử dụng semaphore để viết lại chương trình sau theo mơ hình xử lý đồng hành A = x1 + x2; B = A*x3; C= A + x4; D= B + C; E = B*x5 + C; 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 51
  52. Tĩm tắt lại nội dung buởihọc  Biết được các giải pháp đồng bộ tiến trình theo kiểu “Sleep & Wake up” bao gồm: Semaphore Critical Region Monitor  Áp dụng các giải pháp này vào các bài tốn đồng bộ kinh điển 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 52