[He dieu hanh] Chuong 5 Các giải pháp đồng bộ hóa

Chương 5:       CÁC GIẢI PHÁP ĐỒNG BỘ HOÁ

5.1 GiẢi pháp “busy waiting”

5.1.1. Các giải pháp phần mềm

a) Sử dụng các biến cờ hiệu:

a.1 Tiếp cân: các tiến trình chia sẻ một biến chung đóng vai trò “chốt cửa” (lock), biến này được khởi động là 0. Một tiến trình muốn vào miền găng trước tiên phải kiểm tra giá trị của biến lock. Nếu lock = 0, tiến trình đặt lại giá trị cho lock = 1 và đi vào miền găng. Nếu lock đang nhận giá trị 1, tiến trình phải chờ bên ngoài miền găng cho đến khi lock có giá trị 0. Như vậy giá trị 0 của lock mang ý nghĩa là không có tiến trình nào đang ở trong miền găng, và lock = 1 khi có một tiến trình đang ở trong miền găng.

while (TRUE) {        while (lock == 1); // wait           lock = 1;           critical-section ();           lock = 0;           Noncritical-section (); }

Hình 3.5 Cấu trúc một chương trình sử dụng biến khóa để đồng bộ

a.2 Thảo luận: Giải pháp này có thể vi phạm điều kiện thứ nhất: hai tiến trình có thể cùng ở trong miền găng tại một thời điểm. Giả sử một tiến trình nhận thấy lock = 0 và chuẩn bị vào miền găng, nhưng trước khi nó có thể đặt lại giá trị cho lock là 1, nó bị tạm dừng để một tiến trình khác hoạt động. Tiến trình thứ hai này thấy lock vẫn là 0 thì vào miền găng và đặt lại lock = 1. Sau đó tiến trình thứ nhất được tái kích hoạt, nó gán lock = 1 lần nữa rồi vào miền găng. Như vậy tại thời điểm đó cả hai tiến trình đều ở trong miền găng.

b) Sử dụng việc kiểm tra luân phiên:

b.1 Tiếp cận: Đây là một giải pháp đề nghị cho hai tiến trình. Hai tiến trình này sử dụng chung biến turn (phản ánh phiên tiến trình nào được vào miền găng), được khởi động với giá trị 0. Nếu turn = 0, tiến trình A được vào miền găng. Nếu turn = 1, tiến trình A đi vào một vòng lặp chờ đến khi turn nhận giá trị 0. Khi tiến trình A rời khỏi miền găng, nó đặt giá trị turn về 1 để cho phép tiến trình B đi vào miền găng.

while (TRUE) { while (turn != 0); // wait critical-section (); turn = 1; Noncritical-section (); } (a) Cấu trúc tiến trình A

while (TRUE) { while (turn != 1); // wait critical-section (); turn = 0; Noncritical-section (); } (b) Cấu trúc tiến trình B

Hình 3.6 Cấu trúc các tiến trình trong giải pháp kiểm tra luân phiên

b.2 Thảo luận: Giải pháp này dựa trên việc thực hiện sự kiểm tra nghiêm ngặt đến lượt tiến trình nào được vào miền găng. Do đó nó có thể ngăn chặn được tình trạng hai tiến trình cùng vào miền găng, nhưng lại có thể vi phạm điều kiện thứ ba: một tiến trình có thể bị ngăn chặn vào miền găng bởi một tiến trình khác không ở trong miền găng. Giả sử tiến trình B ra khỏi miền găng rất nhanh chóng. Cả hai tiến trình đều ở ngoài miền găng, và turn = 0. Tiến trình A vào miền găng và ra khỏi nhanh chóng, đặt lại giá trị của turn là 1, rồi lại xử lý đoạn lệnh ngoài miền găng lần nữa. Sau đó, tiến trình A lại kết thúc nhanh chóng đoạn lệnh ngoài miền găng của nó và muốn vào miền găng một lần nữa. Tuy nhiên lúc này B vẫn còn mãi xử lý đoạn lệnh ngoài miền găng của mình, và turn lại mang giá trị 1! Như vậy, giải pháp này không có giá trị khi có sự khác biệt lớn về tốc độ thực hiện của hai tiến trình, nó vi phạm cả điều kiện thứ hai.

c) Giải pháp của Peterson

c.1 Tiếp cận: Peterson đưa ra một giải pháp kết hợp ý tưởng của cả hai giải pháp kể trên. Các tiến trình chia sẻ hai biến chung:

int turn; // đến phiên ai

int interesse[2]; // khởi động là FALSE

Nếu interesse[i] = TRUE có nghĩa là tiến trình Pi muốn vào miền găng. Khởi đầu, interesse[0]=interesse[1]=FALSE. Để có thể vào được miền găng, trước tiên tiến trình Pi đặt giá trị interesse[i]=TRUE (xác định rằng tiến trình muốn vào miền găng), sau đó đặt turn=j (đề nghị thử tiến trình khác vào miền găng). Nếu tiến trình Pj không quan tâm đến việc vào miền găng (interesse[j]=FALSE), thì Pi có thể vào miền găng, nếu không, Pi phải chờ đến khi interesse[j]=FALSE. Khi tiến trình Pi rời khỏi miền găng, nó đặt lại giá trị cho interesse[i]= FALSE.

while (TRUE) { int j = 1-i; // j là tiến trình còn lại interesse[i]= TRUE; turn = j; while (turn == j && interesse[j]==TRUE); critical-section (); interesse[i] = FALSE; Noncritical-section (); }

Hình 3.7 Cấu trúc tiến trình Pi trong giải pháp Peterson

c.2 Thảo luận: giải pháp này ngăn chặn được tình trạng mâu thuẫn truy xuất: mỗi tiến trình Pi chỉ có thể vào miền găng khi interesse[j] = FALSE hoặc turn = i. Nếu cả hai tiến trình đều muốn vào miền găng thì interesse[i] = interesse[j] = TRUE nhưng giá trị của turn chỉ có thể hoặc là 0 hoặc là 1, do vậy chỉ có một tiến trình được vào miền găng.

 5.1.2. Các giải pháp phần cứng

a) Cấm ngắt:

a.1 Tiếp cân: cho phép tiến trình cấm tất cả các ngắt trước khi vào miền găng, và phục hồi ngắt khi ra khỏi miền găng. Khi đó, ngắt đồng hồ cũng không xảy ra, do vậy hệ thống không thể tạm dừng hoạt động của tiến trình đang xử lý để cấp phát CPU cho tiến trình khác, nhờ đó tiến trình hiện hành yên tâm thao tác trên miền găng mà không sợ bị tiến trình nào khác tranh chấp.

a.2 Thảo luận: giải pháp này không được ưa chuộng vì rất thiếu thận trọng khi cho phép tiến trình người dùng được phép thực hiện lệnh cấm ngắt. Hơn nữa, nếu hệ thống có nhiều bộ xử lý, lệnh cấm ngắt chỉ có tác dụng trên bộ xử lý đang xử lý tiến trình, còn các tiến trình hoạt động trên các bộ xử lý khác vẫn có thể truy xuất đến miền găng!

b)  Chỉ thị TSL (Test-and-Set):

b.1 Tiếp cận: đây là một giải pháp đòi hỏi sự trợ giúp của cơ chế phần cứng. Nhiều máy tính cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set Lock (TSL) và được định nghĩa như sau:

Test-and-Setlock(boolean target) { Test-and-Setlock = target; target = TRUE; }

Nếu có hai chỉ thị TSL xử lý đồng thời (trên hai bộ xử lý khác nhau), chúng sẽ được xử lý tuần tự. Có thể cài đặt giải pháp truy xuất độc quyền với TSL bằng cách sử dụng thêm một biến lock, được khởi gán là FALSE. Tiến trình phải kiểm tra giá trị của biến lock trước khi vào miền găng, nếu lock = FALSE, tiến trình có thể vào miền găng.

while (TRUE) { while (Test-and-Setlock(lock)); critical-section (); lock = FALSE; Noncritical-section (); }

Hình 3.8 Cấu trúc một chương trình trong giải pháp TSL

b.2 Thảo luận: cũng giống như các giải pháp phần cứng khác, chỉ thị TSL giảm nhẹ công việc lập trình để giải quyết vấn đề, nhưng lại không dễ dàng để cài đặt chỉ thị TSL sao cho được xử lý một cách không thể phân chia, nhất là trên máy với cấu hình nhiều bộ xử lý.

  Tất cả các giải pháp trên đây đều phải thực hiện một vòng lặp để kiểm tra liệu nó có được phép vào miền găng, nếu điều kiện chưa cho phép, tiến trình phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc tiến trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền găng như thế được gọi các giải pháp “busy waiting”. Lưu ý rằng việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy tiến trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hóa là nên tránh các giải pháp “busy waiting”.

5.2 Các giẢi pháp “SLEEP and WAKEUP”

Để loại bỏ các bất tiện của giải pháp “busy waiting”, chúng ta có thể tiếp cận theo hướng cho một tiến trình chưa đủ điều kiện vào miền găng chuyển sang trạng thái blocked, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái tiến trình. Hai thủ tục cơ bản SLEEP và WAKEUP thường được sử dụng để phục vụ mục đích này.

SLEEP là một lời gọi hệ thống có tác dụng tạm dừng hoạt động của tiến trình (blocked) gọi nó và chờ đến khi được một tiến trình khác “đánh thức”. Lời gọi hệ thống WAKEUP nhận một tham số duy nhất: tiến trình sẽ được tái kích hoạt (đặt về trạng thái ready).

Ý tưởng sử dụng SLEEP và WAKEUP như sau: khi một tiến trình chưa đủ điều kiện vào miền găng, nó gọi SLEEP để tự khóa đến khi có một tiến trình khác gọi WAKEUP để giải phóng cho nó. Một tiến trình gọi WAKEUP khi ra khỏi miền găng để đánh thức một tiến trình đang chờ, tạo cơ hội cho tiến trình này vào miền găng:

int busy;  // 1 nếu miền găng đang bị chiếm, nếu không là 0 int blocked;  // đếm số lượng tiến trình đang bị khóa while (TRUE)  {       if (busy) {                    blocked = blocked + 1;                    sleep(); } else busy = 1; critical-section (); busy = 0; if(blocked) {           wakeup(process);           blocked = blocked - 1; } Noncritical-section (); }

Hình 3.9 Cấu trúc chương trình trong giải pháp SLEEP and WAKEUP

Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy ra tình trạng mâu thuẫn truy xuất trong một vài tình huống đặc biệt như sau: giả sử tiến trình A vào miền găng, và trước khi nó rời khỏi miền găng thì tiến trình B được kích hoạt. Tiến trình B thử vào miền găng nhưng nó nhận thấy A đang ở trong đó, do vậy B tăng giá trị biến blocked và chuẩn bị gọi SLEEP để tự khoá. Tuy nhiên trước khi B có thể thực hiện SLEEP, tiến trình A lại được tái kích hoạt và ra khỏi miền găng. Khi ra khỏi miền găng A nhận thấy có một tiến trình đang chờ (blocked=1) nên gọi WAKEUP và giảm giá trị của blocked. Khi đó tín hiệu WAKEUP sẽ lạc mất do tiến trình B chưa thật sự “ngủ” để nhận tín hiệu đánh thức! Khi tiến trình B được tiếp tục xử lý, nó mới gọi SLEEP và tự khóa vĩnh viễn!

Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra tư cách vào miền găng và việc gọi SLEEP hay WAKEUP là những hành động tách biệt, có thể bị ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến một tiến trình chưa bị khóa sẽ lạc mất.

Để tránh những tình huống tương tự, hệ điều hành cung cấp những cơ chế đồng bộ hóa dựa trên ý tưởng của chiến lược “SLEEP and WAKEUP” nhưng được xây dựng bao hàm cả phương tiện kiểm tra điều kiện vào miền găng giúp sử dụng an toàn.

5.2.1. Semaphore

a) Tiếp cận: Được Dijkstra đề xuất vào 1965, một semaphore s là một biến có các thuộc tính sau:

-       Một giá trị nguyên dương e(s)

-       Một hàng đợi f(s) lưu danh sách các tiến trình đang bị khóa (chờ) trên semaphore s

-       Chỉ có hai thao tác được định nghĩa trên semaphore:

o   Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu semaphore có trị e(s) > 0, và tiếp tục xử lý. Ngược lại, nếu e(s) ≤ 0, tiến trình phải chờ đến khi e(s) >0.

o   Up(s): tăng giá trị của semaphore s lên 1 đơn vị. Nếu có một hoặc nhiều tiến trình đang chờ trên semaphore s, bị khóa bởi thao tác Down, thì hệ thống sẽ chọn một trong các tiến trình này để kết thúc thao tác Down và cho tiếp tục xử lý.

Hình 3.10 Semaphore s

b) Cài đặt: Gọi p là tiến trình thực hiện thao tác Down(s) hay Up(s).

Down(s): e(s) = e(s) - 1; if e(s) < 0 { status(P)= blocked; enter(P,f(s)); }

Up(s): e(s) = e(s) + 1; if s ≤ 0 { exit(Q,f(s)); //Q là tiến trình đang chờ trên s status (Q) = ready; enter(Q,ready-list); }

Lưu ý cài đặt này có thể đưa đến một giá trị âm cho semaphore, khi đó trị tuyệt đối của semaphore cho biết số tiến trình đang chờ trên semaphore.

Điều quan trọng là các thao tác này cần thực hiện một cách không bị phân chia, không bị ngắt nửa chừng, có nghĩa là không một tiến trình nào được phép truy xuất đến semaphore nếu tiến trình đang thao tác trên semaphore này chưa kết thúc xử lý hay chuyển sang trạng thái blocked.

c) Sử dụng: có thể dùng semaphore để giải quyết vấn đề truy xuất độc quyền hay tổ chức phối hợp giữa các tiến trình.

c.1 Tổ chức truy xuất độc quyền với Semaphores: khái niệm semaphore cho phép bảo đảm nhiều tiến trình cùng truy xuất đến miền găng mà không có sự mâu thuẫn truy xuất. N tiến trình cùng sử dụng một semaphore s, e(s) được khởi gán là 1. Để thực hiện đồng bộ hóa, tất cả các tiến trình cần phải áp dụng cùng cấu trúc chương trình sau đây:

while (TRUE)  { Down(s) critical-section (); Up(s) Noncritical-section (); }

Hình 3.11 Cấu trúc một chương trình trong giải pháp semaphore

c.2 Tổ chức đồng bộ hóa với Semaphores: với semaphore có thể đồng bộ hóa hoạt động của hai tiến trình trong tình huống một tiến trình phải đợi một tiến trình khác hoàn tất thao tác nào đó mới có thể bắt đầu hay tiếp tục xử lý. Hai tiến trình chia sẻ một semaphore s, khởi gán e(s) là 0. Cả hai tiến trình có cấu trúc như sau:

P1: while (TRUE) { job1(); Up(s); //đánh thức P2 }

P2: while (TRUE) { Down(s); // chờ P1 job2(); }

Hình 3.12 Cấu trúc chương trình trong giải pháp semaphore

 d) Thảo luận: Nhờ có thực hiện một cách không thể phân chia, semaphore đã giải quyết được vấn đề tín hiệu "đánh thức" bị thất lạc. Tuy nhiên, nếu lập trình viên vô tình đặt các primitive Down và Up sai vị trí, thứ tự trong chương trình, thì tiến trình có thể bị khóa vĩnh viễn.

Ví dụ: while (TRUE) {

Down(s)
critical-section ();
Noncritical-section ();

}

tiến trình trên đây quên gọi Up(s), và kết quả là khi ra khỏi miền găng nó sẽ không cho tiến trình khác vào miền găng!

Vì thế việc sử dụng đúng cách semaphore để đồng bộ hóa phụ thuộc hoàn toàn vào lập trình viên và đòi hỏi lập trình viên phải hết sức thận trọng.

5.2.2. Monitors

a) Tiếp cận: Để có thể dễ viết đúng các chương trình đồng bộ hóa hơn, Hoare(1974) và Brinch & Hansen (1975) đã đề nghị một cơ chế cao hơn được cung cấp bởi ngôn ngữ lập trình, là monitor. Monitor là một cấu trúc đặc biệt bao gồm các thủ tục, các biến và cấu trúc dữ liệu có các thuộc tính sau:

-       Các biến và cấu trúc dữ liệu bên trong monitor chỉ có thể được thao tác bởi các thủ tục định nghĩa bên trong monitor đó. (encapsulation).

-       Tại một thời điểm, chỉ có một tiến trình duy nhất được hoạt động bên trong một monitor (mutual exclusive).

-       Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm theo là Wait và Signal như sau: gọi c là biến điều kiện được định nghĩa trong monitor:

o   Wait(c): chuyển trạng thái tiến trình gọi sang blocked, và đặt tiến trình này vào hàng đợi trên biến điều kiện c.

o   Signal(c): nếu có một tiến trình đang bị khóa trong hàng đợi của c, tái kích hoạt tiến trình đó, và tiến trình gọi sẽ rời khỏi monitor.

Hình 3.13 Monitor và các biến điều kiện

b) Cài đặt: trình biên dịch chịu trách nhiệm thực hiện việc truy xuất độc quyền đến dữ liệu trong monitor. Để thực hiện điều này, một semaphore nhị phân thường được sử dụng. Mỗi monitor có một hàng đợi toàn cục lưu các tiến trình đang chờ được vào monitor, ngoài ra, mỗi biến điều kiện c cũng gắn với một hàng đợi f(c) và hai thao tác trên đó được định nghĩa như sau:

Wait(c): status(P)= blocked; enter(P,f(c));

Signal(c):   if (f(c) != NULL){ exit(Q,f(c)); //Q là tiến trình chờ trên c status(Q) = ready; enter(Q,ready-list); }

c) Sử dụng: Với mỗi nhóm tài nguyên cần chia sẻ, có thể định nghĩa một monitor trong đó đặc tả tất cả các thao tác trên tài nguyên này với một số điều kiện nào đó:

monitor <tên monitor > condition <danh sách các biến điều kiện>; <declaration variables>;             procedure Action1();             {             }                         ....             procedure Actionn();             {             }  end monitor;

Hình 3.14 Cấu trúc một monitor

Các tiến trình muốn sử dụng tài nguyên chung này chỉ có thể thao tác thông qua các thủ tục bên trong monitor được gắn kết với tài nguyên:

while (TRUE) { Noncritical-section (); <monitor>.Actioni; //critical-section(); Noncritical-section (); }

Hình 3.15 Cấu trúc tiến trình Pi trong giải pháp monitor

d) Thảo luận: Với monitor, việc truy xuất độc quyền được bảo đảm bởi trình biên dịch mà không do lập trình viên, do vậy nguy cơ thực hiện đồng bộ hóa sai giảm rất nhiều. Tuy nhiên giải pháp monitor đòi hỏi phải có một ngôn ngữ lập trình định nghĩa khái niệm monitor, và các ngôn ngữ như thế chưa có nhiều.

5.2.3. Trao đổi thông điệp

a) Tiếp cận: Giải pháp này dựa trên cơ sở trao đổi thông điệp với hai primitive Send và Receive để thực hiện sự đồng bộ hóa:

-       Send(destination, message): Gởi một thông điệp đến một tiến trình hay gởi vào hộp thư.

-       Receive(source,message): Nhận một thông điệp từ một tiến trình hay từ bất kỳ một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận.

b) Sử dụng: Có nhiều cách thức để thực hiện việc truy xuất độc quyền bằng cơ chế trao đổi thông điệp. Đây là một mô hình đơn giản: một tiến trình kiểm soát việc sử dụng tài nguyên và nhiều tiến trình khác yêu cầu tài nguyên này. Tiến trình có yêu cầu tài nguyên sẽ gởi một thông điệp đến tiến trình kiểm soát và sau đó chuyển sang trạng thái blocked cho đến khi nhận được một thông điệp chấp nhận cho truy xuất từ tiến trình kiểm soát tài nguyên. Khi sử dụng xong tài nguyên, tiến trình gởi một thông điệp khác đến tiến trình kiểm soát để báo kết thúc truy xuất. Về phần tiến trình kiểm soát, khi nhận được thông điệp yêu cầu tài nguyên, nó sẽ chờ đến khi tài nguyên sẵn sàng để cấp phát thì gởi một thông điệp đến tiến trình đang bị khóa trên tài nguyên đó để đánh thức tiến trình này.

while (TRUE) { Send(process controler, request message); Receive(process controler, accept message); critical-section (); Send(process controler, end message); Noncritical-section (); }

Hình 3.16 Cấu trúc tiến trình yêu cầu tài nguyên trong giải pháp message

c) Thảo luận: Các primitive semaphore và monitor có thể giải quyết được vấn đề truy xuất độc quyền trên các máy tính có một hoặc nhiều bộ xử lý chia sẻ một vùng nhớ chung. Nhưng các primitive không hữu dụng trong các hệ thống phân tán, khi mà mỗi bộ xử lý sở hữu một bộ nhớ riêng biệt và liên lạc thông qua mạng. Trong những hệ thống phân tán như thế, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và được dùng để giải quyết bài toán đồng bộ hóa.

5.3 Các vẤn đỀ cỔ điỂn cỦa đỒng bỘ hoá

5.3.1. Vấn đề Người sản xuất – Người tiêu thụ (Producer-Consumer)

a) Vấn đề: Hai tiến trình cùng chia sẻ một bộ đệm có kích thước giới hạn. Một trong hai tiến trình đóng vai trò người sản xuất – tạo ra dữ liệu và đặt dữ liệu vào bộ đệm - và tiến trình kia đóng vai trò người tiêu thụ – lấy dữ liệu từ bộ đệm ra để xử lý. 

Hình 3.17 Producer và Consumer

Để đồng bộ hóa hoạt động của hai tiến trình sản xuất tiêu thụ cần tuân thủ các quy định sau:

-       Tiến trình sản xuất (producer) không được ghi dữ liệu vào bộ đệm đã đầy.

-       Tiến trình tiêu thụ (consumer) không được đọc dữ liệu từ bộ đệm đang trống.

-       Hai tiến trình sản xuất và tiêu thụ không được thao tác trên bộ đệm cùng lúc.

b) Giải pháp:

b.1 Semaphore

Sử dụng ba semaphore: full, đếm số chỗ đã có dữ liệu trong bộ đệm; empty, đếm số chỗ còn trống trong bộ đệm; và mutex, kiểm tra việc Producer và Consumer không truy xuất đồng thời đến bộ đệm.

          BufferSize = 3;               // số chỗ trong bộ đệm

          semaphore mutex = 1;    // kiểm soát truy xuất độc quyền

          semaphore empty = BufferSize;   // số chỗ trống

          semaphore full = 0;        // số chỗ đầy

Producer() {  int item;  while (TRUE) {      produce_item(&item);// tạo dữ liệu mới  down(&empty);// giảm số chỗ trống  down(&mutex);// báo  hiệu vào miền găng  enter_item(item);// đặt dữ liệu vào bộ đệm  up(&mutex);     // ra khỏi miền găng  up(&full);                 // tăng số chỗ đầy  } }

Consumer() {  int item;  while (TRUE) {          down(&full);            // giảm số chỗ đầy  down(&mutex);// báo  hiệu vào miền găng  remove_item(&item);// lấy dữ liệu từ bộ đệm  up(&mutex);            // ra khỏi miền găng  up(&empty);            // tăng số chỗ trống  consume_item(item);// xử lý dữ liệu  } }

b.2 Monitor

Định nghĩa một monitor ProducerConsumer với hai thủ tục enter và remove thao tác trên bộ đệm. Xử lý của các thủ tục này phụ thuộc vào các biến điều kiện full và empty.

monitor ProducerConsumer   condition full, empty;   int count;   procedure enter();  {   if (count == N)             wait(full);     // nếu bộ đệm đầy, phải chờ   enter_item(item);          // đặt dữ liệu vào bộ đệm   count ++;            // tăng số chỗ đầy   if (count == 1)     // nếu bộ đệm không trống             signal(empty);    // thì kích hoạt Consumer  }  procedure remove();  {   if (count == 0)             wait(empty)        // nếu bộ đệm trống, chờ   remove_item(&item);            // lấy dữ liệu từ bộ đệm   count --;                       // giảm số chỗ đầy   if (count == N-1)                   // nếu bộ đệm không đầy     signal(full);                 // thì kích hoạt Producer  }  count = 0;  end monitor;

Producer();  {   while (TRUE)   {           produce_item(&item);           ProducerConsumer.enter;   }  }

Consumer();  {   while (TRUE)   {           ProducerConsumer.remove;           consume_item(item);   }  }

b.3. Trao đổi thông điệp

Thông điệp empty hàm ý có một chỗ trống trong bộ đệm. Tiến trình Consumer bắt đầu công việc bằng cách gởi 4 thông điệp empty đến Producer. Tiến trình Producer tạo ra một dữ liệu mới và chờ đến khi nhận được một thông điệp empty thì gởi ngược lại cho Consumer một thông điệp chứa dữ liệu. Tiến trình Consumer chờ nhận thông điệp chứa dữ liệu, và sau khi xử lý xong dữ liệu này, Consumer sẽ lại gởi một thông điệp empty đến Producer,...

BufferSize = 4; Producer() { int item; message m;       // thông điệp while (TRUE) { produce_item(&item); receive(consumer,&m);// chờ thông điệp empty create_message(&m, item);// tạo thông điệp dữ liệu send(consumer,&m);// gởi dữ liệu đến Consumer } }

Consumer() { int item; message m; for(0 to N) send(producer, &m); // gởi N thông điệp empty while (TRUE) {  receive(producer, &m); // chờ thông điệp dữ liệu remove_item(&m,&item);// lấy dữ liệu từ thông điệp send(producer, &m); // gởi thông điệp empty consumer_item(item);// xử lý dữ liệu } }

5.3.2. Mô hình Readers-Writers

a) Vấn đề: Nhiều tiến trình đồng thời sử dụng một cơ sở dữ liệu. Các tiến trình chỉ cần lấy nội dung của cơ sở dữ liệu được gọi là các tiến trình Reader, nhưng một số tiến trình khác lại có nhu cầu sửa đổi, cập nhật dữ liệu trong cơ sở dữ liệu chung này, chúng được gọi là các tiến trình Writer. Các quy định đồng bộ hóa việc truy xuất cơ sở dữ liệu cần tuân thủ là:

-       Không cho phép một tiến trình Writer cập nhật dữ liệu trong cơ sở dữ liệu khi các tiến trình Reader khác đang truy xuất nội dung cơ sở dữ liệu.

-       Tại một thời điểm, chỉ cho phép một tiến trình Writer được sửa đổi nội dung cơ sở dữ liệu.

b) Giải pháp:

b.1. Semaphore

Sử dụng một biến chung rc để ghi nhớ số lượng các tiến trình Reader muốn truy xuất cơ sở dữ liệu. Hai semaphore cũng được sử dụng: mutex, kiểm soát sự truy cập đến rc; và db, kiểm tra sự truy xuất độc quyền đến cơ sở dữ liệu.

semaphore mutex = 1;  // Kiểm tra truy xuất rc

semaphore db = 1;        // Kiểm tra truy xuất cơ sở dữ liệu

int rc;         // Số lượng tiến trình Reader

Reader() {  while (TRUE) {              down(&mutex);// giành quyền truy xuất rc    rc = rc + 1;// thêm một tiến trình Reader    if (rc == 1)// nếu là Reader đầu tiên thì     down(&db);// cấm Writer truy xuất dữ liệu    up(&mutex); // chấm dứt truy xuất rc    read_database();   // đọc dữ liệu    down(&mutex);// giành quyền truy xuất rc    rc = rc - 1; // bớt một tiến trình Reader    if (rc == 0)// nếu là Reader cuối cùng thì      up(&db);// cho phép Writer truy xuất db      up(&mutex);// chấm dứt truy xuất rc    use_data_read();  } }

Writer() {  while (TRUE) {              create_data();    down(&db);// giành quyền truy xuất db    write_database();  // cập nhật dữ liệu    up(&db);      // chấm dứt truy xuất db  } }

b.2. Monitor

Sử dụng một biến chung rc để ghi nhớ số lượng các tiến trình Reader muốn truy xuất cơ sở dữ liệu. Một tiến trình Writer phải chuyển sang trạng thái chờ nếu rc > 0. Khi ra khỏi miền găng, tiến trình Reader cuối cùng sẽ đánh thức tiến trình Writer đang bị khóa.

monitor ReaderWriter

  condition OKWrite, OKRead;

  int     rc = 0;

  Boolean  busy = false;

procedure BeginRead()  {   if (busy)// nếu db đang bận, chờ wait(OKRead);   rc++;     // thêm một Reader   signal(OKRead);  }	procedure FinishRead()  {    rc--;   // bớt một Reader    if (rc == 0)    // nếu là Reader cuối cùng     signal(OKWrite);// thì cho phép Writer                         // truy xuất db  }
procedure BeginWrite()  {   if (busy || rc != 0) // nếu db đang bận, hay một             wait(OKWrite);// Reader đang đọc db,chờ   busy = true;  }	procedure FinishWrite()  {   busy = false;   If (OKRead.Queue)    signal(OKRead);   else    signal(OKWrite);   }
Reader()  {    while (TRUE)                         {     ReaderWriter.BeginRead();     Read_database();        ReaderWriter.FinishRead();    }  }	Writer()  {    while (TRUE)                         {        create_data(&info);                 ReaderWriter.BeginWrite();        Write_database();        ReaderWriter.FinishWrite();    }  }

end monitor

 b.3. Trao đổi thông điệp

Cần có một tiến trình server điều khiển việc truy xuất cơ sở dữ liệu.

Các tiến trình Writer và Reader gởi các thông điệp yêu cầu truy xuất đến server và nhận từ server các thông điệp hồi đáp tương ứng.

Reader() {   while (TRUE) {      send (server, RequestRead);      receive (server, value);      print(value); } }

Writer() {   while (TRUE) {      create_data(&value);      send (server, RequestWrite,value);      receive (server,OKWrite); } }

5.4 TẮc nghẼn (Deadlock)

5.4.1. Định nghĩa:

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.

Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy không có tiến trình nào có thể tiếp tục xử lý, cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn !

Vấn đề Bữa ăn tối của các triết gia: 5 nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học cần dùng 2 cái nĩa để có thể ăn spaghetti. Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Mỗi nhà triết học sẽ suy ngẫm các triết lý của mình đến khi cảm thấy đói thì dự định lần lượt cầm 1 cái nĩa bên trái và 1 cái nĩa bên phải để ăn. Nếu cả 5 nhà triết học đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti. Đây chính là tình trạng tắc nghẽn.

Hình 3.18 Bữa ăn tối của các triết gia

5.4.2. Điều kiện xuất hiện tắc nghẽn

Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:

-       Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình, khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

-       Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.

-       Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.

-       Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên (Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.

Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.

5.4.3. Đồ thị cấp phát tài nguyên

Có thể sử dụng một đồ thị để mô hình hóa việc cấp phát tài nguyên. Đồ thị này có 2 loại nút: các tiến trình được biểu diễn bằng hình tròn, và mỗi tài nguyên được hiển thị bằng hình vuông.

Hình 3.19 Đồ thị cấp phát tài nguyên

5.4.4. Các phương pháp xử lý tắc nghẽn

Chủ yếu có ba hướng tiếp cận để xử lý tắc nghẽn:

-       Sử dụng một nghi thức (protocol) để bảo đảm rằng hệ thống không bao giờ xảy ra tắc nghẽn.

-       Cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.

-       Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn.

5.4.5. Ngăn chặn tắc nghẽn

Để tắc nghẽn không xảy ra, cần bảo đảm tối thiểu một trong 4 điều kiện cần không xảy ra:

-       Tài nguyên không thể chia sẻ: nhìn chung gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một số tài nguyên về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ.

-       Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp đặt một trong hai cơ chế truy xuất sau:

o   Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý.

Þ Phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý. Ngoài ra nếu tiến trình chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.

o   Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ, sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới.

Þ Phương pháp này làm phát sinh các khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.

-       Không thu hồi tài nguyên: Cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khóa và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm sự toàn vẹn dữ liệu.

-       Tồn tại một chu kỳ: Tránh tạo chu kỳ trong đồ thị bằng cách cấp phát tài nguyên theo một sự phân cấp như sau:

Gọi R = {R₁, R₂,...,Rm} là tập các loại tài nguyên.

Các loại tài nguyên được phân cấp từ 1-N.

Ví dụ: F(đĩa) = 2, F(máy in) = 12

Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định: khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri).

5.4.6. Tránh tắc nghẽn

Ngăn cản tắc nghẽn là một mối bận tâm lớn khi sử dụng tài nguyên. Tránh tắc nghẽn là loại bỏ tất cả các cơ hội có thể dẫn đến tắc nghẽn trong tương lai. Cần phải sử dụng những cơ chế phức tạp để thực hiện ý định này.

a) Một số khái niệm cơ sở

a.1 Trạng thái an toàn: trạng thái A là an toàn nếu hệ thống có thể thỏa mãn các nhu cầu tài nguyên (cho đến tối đa) của mỗi tiến trình theo một thứ tự nào đó mà vẫn ngăn chặn được tắc nghẽn.

a.2 Một chuỗi cấp phát an toàn: một thứ tự của các tiến trình <P₁, P₂,...,Pn> là an toàn đối với tình trạng cấp phát hiện hành nếu với mỗi tiến trình Pi nhu cầu tài nguyên của Pi có thể được thỏa mãn với các tài nguyên còn tự do của hệ thống, cộng với các tài nguyên đang bị chiếm giữ bởi các tiến trình Pj khác, với j<i.

  Một trạng thái an toàn không thể là trạng thái tắc nghẽn. Ngược lại một trạng thái không an toàn có thể dẫn đến tình trạng tắc nghẽn.

b) Chiến lược cấp phát: chỉ thỏa mãn yêu cầu tài nguyên của tiến trình khi trạng thái kết quả là an toàn!

c) Giải thuật xác định trạng thái an toàn

Cần sử dụng các cấu trúc dữ liệu sau:

int Available[NumResources];

/* Available[r]= số lượng các thể hiện còn tự do của tài nguyên r*/

int Max[NumProcs, NumResources];

/*Max[p,r]= nhu cầu tối đa của tiến trình p về tài nguyên r*/

int Allocation[NumProcs, NumResources];

/* Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p*/

int Need[NumProcs, NumResources];

/* Need[p,r] = Max[p,r] - Allocation[p,r]*/

c.1 Giả sử có các mảng

int Work[NumProcs, NumResources] = Available;

int Finish[NumProcs] = false;

c.2 Tìm i sao cho

Finish[i] == false

Need[i] <= Work[i]

Nếu không có i như thế, đến bước 4.

c.3 Work = Work + Allocation[i];

  Finish[i] = true;

  Đến bước 2

c.4 Nếu Finish[i] == true với mọi i, thì hệ thống ở trạng thái an toàn.

d) Ví dụ: Giả sử tình trạng hiện hành của hệ thống được mô tả như sau:

Max			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	3	2	2	1	0	0
P2	6	1	3	2	1	1
P3	3	1	4	2	1	1
P4	4	2	2	0	0	2

Nếu tiến trình P2 yêu cầu 4 cho R1, 1 cho R3. Hãy cho biết yêu cầu này có thể đáp ứng mà bảo đảm không xảy ra tình trạng deadlock hay không? Nhận thấy Available[1] =4, Available[3] =2 đủ để thỏa mãn yêu cầu của P2, ta có

Need			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	2	2	2	1	0	0
P2	0	0	1	6	1	2
P3	1	0	3	2	1	1
P4	4	2	0	0	0	2

Need			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	2	2	2	1	0	0
P2	0	0	0	0	0	0
P3	1	0	3	2	1	1
P4	4	2	0	0	0	2

Need			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	0	0	0	0	0	0
P2	0	0	0	0	0	0
P3	1	0	3	2	1	1
P4	4	2	0	0	0	2

Need			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	0	0	0	0	0	0
P2	0	0	0	0	0	0
P3	0	0	0	0	0	0
P4	4	2	0	0	0	2

Need			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	0	0	0	0	0	0
P2	0	0	0	0	0	0
P3	0	0	0	0	0	0
P4	0	0	0	0	0	0

Trạng thái kết quả là an toàn, có thể cấp phát.

e) Giải thuật yêu cầu tài nguyên

Giả sử tiến trình Pi yêu cầu k thể hiện của tài nguyên r.

Bước 1. Nếu k <= Need[i], đến bước 2
  Ngược lại, xảy ra tình huống lỗi

Bước 2. Nếu k <= Available[i], đến bước 3
  Ngược lại, Pi phải chờ 

Bước 3. Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật tình trạng hệ thống như sau:

Available[i] = Available[i] - k;
Allocation[i]= Allocation[i]+ k;
Need[i] = Need[i] - k; 

  Nếu trạng thái kết quả là an toàn, lúc này các tài nguyên trên sẽ được cấp phát thật sự cho Pi 

  Ngược lại, Pi phải chờ

5.4.7. Phát hiện tắc nghẽn

Cần sử dụng các cấu trúc dữ liệu sau:

int Available[NumResources];

// Available[r]= số lượng các thể hiện còn tự do của tài nguyên r

int Allocation[NumProcs, NumResources];

// Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p

int Request[NumProcs, NumResources];

// Request[p,r] = số lượng tài nguyên r tiến trình p yêu cầu thêm

Giải thuật phát hiện tắc nghẽn

B1. int Work[NumResources] = Available;

     int Finish[NumProcs];

     for (i = 0; i < NumProcs; i++)

       Finish[i] = (Allocation[i] == 0);

B2. Tìm i sao cho

     Finish[i] == false

     Request[i] <= Work

     Nếu không có i như thế, đến bước 4.

B3. Work = Work + Allocation[i];

     Finish[i] = true;

     Đến bước 2

B4. Nếu Finish[i] == true với mọi i,

     thì hệ thống không có tắc nghẽn

     Nếu Finish[i] == false với một số giá trị i,

     thì các tiến trình  mà Finish[i] == false sẽ ở trong

     tình trạng tắc nghẽn.

5.4.8. Hiệu chỉnh tắc nghẽn

Khi đã phát hiện được tắc nghẽn, có hai lựa chọn chính để hiệu chỉnh tắc nghẽn:

a) Đình chỉ hoạt động của các tiến trình liên quan

Cách tiếp cận này dựa trên việc thu hồi lại các tài nguyên của những tiến trình bị kết thúc. Có thể sử dụng một trong hai phương pháp sau:

-       Đình chỉ tất cả các tiến trình trong tình trạng tắc nghẽn 

-       Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình gây tắc nghẽn: để chọn được tiến trình thích hợp bị đình chỉ, phải dựa vào các yếu tố như độ ưu tiên, thời gian đã xử lý, số lượng tài nguyên đang chiếm giữ, số lượng tài nguyên yêu cầu...

b) Thu hồi tài nguyên

Có thể hiệu chỉnh tắc nghẽn bằng cách thu hồi một số tài nguyên từ các tiến trình và cấp phát các tài nguyên này cho những tiến trình khác cho đến khi loại bỏ được chu trình tắc nghẽn. Cần giải quyết 3 vấn đề sau:

-       Chọn lựa một nạn nhân: tiến trình nào sẽ bị thu hồi tài nguyên? và thu hồi những tài nguyên nào?

-       Trở lại trạng thái trước tắc nghẽn: khi thu hồi tài nguyên của một tiến trình, cần phải phục hồi trạng thái của tiến trình trở lại trạng thái gần nhất trước đó mà không xảy ra tắc nghẽn.

-       Tình trạng “đói tài nguyên”: làm sao bảo đảm rằng không có một tiến trình luôn luôn bị thu hồi tài nguyên?

5.5 Tóm tẮt

1) Các giải pháp đồng bộ hoá do lập trình viên xây dựng không được ưa chuộng vì phải tiêu thụ CPU trong thời gian chờ vào miền găng (“busy waiting”), và khó mở rộng. Thay vào đó, lập trình viên có thể sử dụng các cơ chế đồng bộ do hệ điều hành hay trình biên dịch trợ giúp như semaphore, monitor, trao đổi thông điệp.

2) Tắc nghẽn là tình trạng xảy ra trong một tập các tiến trình nếu có hai hay nhiều hơn các tiến trình chờ đợi vô hạn một sự kiện chỉ có thể được phát sinh bởi một tiến trình cũng đang chờ khác trong tập các tiến trình này.

3) Có 3 hướng tiếp cận chính trong xử lý tắc nghẽn:

-       Phòng tránh tắc nghẽn: tuân thủ một vài nghi thức bảo đảm hệ thống không bao giờ lâm vào trạng thái tắc nghẽn.

-       Phát hiện tắc nghẽn: khi có tắc nghẽn xảy ra, phát hiện các tiến trình liên
quan và tìm cách phục hồi.

-       Bỏ qua tắc nghẽn: xem như hệ thống không bao giờ lâm vào trạng thái
tắc nghẽn.

5.6 Củng cố bài học

Các câu hỏi cần trả lời được sau bài học này:

1. Phân biệt nhóm giải pháp busy waiting và Sleep&Wakeup

2. Phân biệt cách sử dụng semaphore, monitor và message để đồng bộ hoá.

3. Mô hình giải quyết nhu cầu độc quyền truy xuất và mô hình giải quyết nhu cầu phối hợp hoạt động.

5.7 Bài tập

Bài 1. Xét giải pháp phần mềm do Dekker đề nghị để tổ chức truy xất độc quyền cho hai tiến trình. Hai tiến trình P₀, P₁ 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;
while turn = j do;
flag[i]: = true;

end;

  critical_section();

  turn: = j;

flag[i]: = false;

non_critical_section();

until false;

Giải pháp này có phải là một giải pháp đúng thỏa mãn 4 yêu cầu không?

Bài 2. Xét giải pháp phần mềm do Eisenberg và McGuire đề nghị để tổ chức truy xất độc quyền cho N tiến trình. Các tiến trình chia sẻ các biến sau:

var flag: array [0..N-1] of (idle, want-in, in-cs);

turn: 0..N-1;

Tất cả các phần tử của mảng flag được khởi động là idle, turn được khởi gán một trong những giá trị từ 0..N-1

Cấu trúc một tiến trình Pi như sau:

repeat

repeat

flag[i]: = want-in;

j: = turn;

while j<>i do

if flag[j]<> idle then j: = turn

else j: = j+1 mod n;

flag[i]: = in-cs;

j: =0;

while (j<N) and (j = i or flag[j] <> in-cs) do j: =j+1;

until (j>=N) and (turn =i or flag[turn] = idle);

turn: = i;

critical_section();

j: = turn + 1 mod N;

while (flag[j]= idle) do j: = j+1 mod N;

turn: = j;

flag[i]: = idle;

non_critical_section();

until false;

Giải pháp này có phải là một giải pháp đúng thỏa mãn 4 yêu cầu không?

Bài 3. Xét giải pháp đồng bộ hoá 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 ();

}

Đây có phải là một giải pháp bảo đảm được độc quyền truy xuất không?

Bài 4. Giả sử một máy tính không có chỉ thị TSL, nhưng có chỉ thị Swap có khả năng hoá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.

Bài 5. Chứng tỏ rằng nếu các primitive Down và Up trên semaphore không thực hiện một cách không thể phân chia, thì sự truy xuất độc quyền sẽ bị vi phạm.

Bài 6. Sử dụng semaphore để cài đặt cơ chế monitor.

Bài 7. Xét hai tiến trình sau:

process A

{        while (TRUE)

na = na +1;

}

process B

{        while (TRUE)

nb = nb +1;

}

a) Đồng bộ hoá xử lý của hai tiến trình trên, sử dụng hai 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ỉ 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?

Bài 8. Một biến X được chia sẻ bởi hai 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 để bảo đảm X không vượt quá 20?

Bài 9. Xét hai tiến trình xử lý đoạn chương trình sau:

process P₁ { A₁; A₂ } process P₂ { B₁; B₂ }

Đồng bộ hoá hoạt động của hai tiến trình này sao cho cả A₁ và B₁ đều hoàn tất trước khi A₂ hay B₂ bắt đầu.

Bài 10. Tổng quát hoá câu hỏi 8) cho các tiến trình xử lý đoạn chương trình sau:

process P₁ { for (i = 1; i <= 100; i ++) Ai }

process P₂ { for (j = 1; j <= 100; j ++) Bj }

Đồng bộ hoá hoạt động của hai tiến trình này sao cho cả với k 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.

Bài 11. 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

            y: = w * y

            z: = w * z

            ans: = y + z

Bài 12. Xây dựng một giải pháp (sử dụng semaphore) để giải quyết vấn đề Readers_Writers trong đó:

a) Readers được ưu tiên (khi không có ai truy xuất database, Reader được ưu tiên truy cập database ngay, Writer phải đợi tất cả các Reader truy xuất xong mới được vào database)

b) Writers được ưu tiên (khi không có ai truy xuất database, Writer được ưu tiên truy cập database ngay, Reader phải đợi tất cả các Write truy xuất xong mới được vào database)

c) Công bằng cho Reader, Writer (khi không có ai truy xuất database, Writer hoặc Reader có cơ hội ngang nhau để truy cập database)

Bài 13. Dining Philosophers: Giả sử hành vi của một triết gia thứ i trong bữa ăn tối được mô tả như sau:

#define N 5

void philosopher(int i)

{ while (TRUE)

{ think(); // Suy nghĩ

take_fork(i); // lấy nĩa bên trái

take_fork((i+1)%N); // lấy nĩa bên phải

eat(); // yum-yum, spaghetti

put_fork(i); // đặt nĩa bên trái lên bàn lại

put_fork((i+1)%N); // đặt nĩa bên phải lên bàn lại

}

}

a) Lưu ý là trên bàn chỉ có 5 cái nĩa, và nếu có 2 triết gia cùng muốn lấy một cái nĩa, thì chỉ một người được quyền lấy cái nĩa đó. Sử dụng semaphore để tổ chức độc quyền truy xuất đến các cái nĩa cho đoạn chương trình trên (Gợi ý: dùng mỗi semaphore phản ánh tình trạng sử dụng của mỗi cái nĩa)

b) Liệu giải pháp của câu a) có là một giải pháp tốt cho bài toán Dining philosopher? Nếu không, cho biết các tình huống lỗi sẽ xảy ra, và đề nghị phương pháp cải tiến.

Bài 14. Xét một giải pháp đúng cho bài toán Dining philosophers:

#define N                      5

#define LEFT               (i-1)%N

#define RIGHT             (i+1)%N

#define THINKING      0

#define HUNGRY        1

#define EATING          2

int                    state[N];

semaphore       mutex = 1;

semaphore       s[N];

void philosopher(int i) // i: xác định triết gia nào (0..N-1)

{

while (TRUE)

{ thinhk(); // Suy nghĩ

take_forks(i); // yêu cầu đến khi có đủ 2 nĩa

eat(); // yum-yum, spaghetti

put_forks(i); // đặt cả 2 nĩa lên bàn lại

}

}

void take_forks (int i) // i: xác định triết gia nào (0..N-1)

{

while (TRUE)

{ down(mutex); // vào miền găng

state[i] = HUNGRY; // ghi nhận triết gia i đã đói

test(i); // cố gắng lấy 2 nĩa

up(mutex); // ra khỏi miền găng

down(s[i]); // chờ nếu không có đủ 2 nĩa

}

}

}

void put_forks (int i) // i: xác định triết gia nào (0..N-1)

{

while (TRUE)

{ down(mutex); // vào miền găng

state[i] = THINKING; // ghi nhận triết gia i ăn xong

test(LEFT); // kiểm tra người bên trái đã có thể ăn?

test(RIGHT); // kiểm tra người bên phải đã có thể ăn?

up(mutex); // ra khỏi miền găng

}

}

void test (int i) // i: xác định triết gia nào (0..N-1)

{

if(state[i]==HUNGRY && state[LEFT]!=EATING

&& state[RIGHT]!= EATING

{

state[i] = EATING;

up(s[i]);

}

}

a)Tại sao phải đặt state[i] = HUNGRY trong take_forks?

b)Giả sử trong put_forks, lệnh gán state[i] = THINKING được thực hiện sau hai lệnh test(LEFT), test(RIGHT). Điều này ảnh hưởng thế nào đến giải pháp cho 3 triết gia? Cho 100 triết gia?

Bài 15. Xây dựng giải pháp monitor cho bài toán Dining Philosophers.

Bài 16. Baber problem: Một cửa hiệu cắt tóc có một thợ, một ghế cắt tóc và N ghế cho khách đợi. Nếu không có khách hàng, anh thợ cắt tóc sẽ ngồi vào ghế cắt tóc và ngủ thiếp đi. Khi một khách hàng vào tiệm, anh ta phải đánh thức người thợ. Nếu một khách hàng vào tiệm khi người thợ đang bận cắt tóc cho khách hàng khác, người mới vào sẽ phải ngồi chờ nếu có ghế đợi trống, hoặc rời khỏi tiệm nếu đã có N người đợi. Xây dựng một giải pháp với semaphore để thực hiện đồng bộ hóa hoạt động của thợ và khách hàng trong cửa hiệu cắt tóc này.

/* Semaphore to protect critical sections */

Semaphore mutex = 1;

/* Semaphore for the number of waiting customers.

 * This lets the barber go to sleep when there are no customers */

Semaphore customers = 0;

/* Number of waiting customers in the barber shop */

/* Just used to turn away customers when there are too many already. */

int waiting_customers = 0

/* Semaphore on which to wait for a haircut */

Semaphore haircut = 0;

/* Customer calls this function to try to get their hair cut

 * it returns true if the hair gets cut. */

int customer()

{

 /* protect access to shared variables with semaphore mutex */

 wait(mutex);

 /* Make sure there is an empty chair */

 if(waiting_customers >= 5){

  signal(mutex);

  return 0;

 }

 /* there is now a new waiting customer */

 waiting_customers += 1;

 signal(mutex);

 /* Wake the barber if the shop was empty */

 signal(customers);

 /* Wait for a haircut from the barber */

 wait(haircut);

 return 1;

}

/* Barber loops within this function */

void barber()

{

 while(1){

  /* Go to sleep if there are no customers */

  wait(customers);

  // protect access to shared variables with semaphore mutex

  wait(mutex);

  /* take customer out of a chair */

  waiting_customers -= 1;

  signal(mutex);

  /* cut hair of the current customer */

  cut_hair();

  /* Let the customer go. */

  signal(haircut);

 }

}

Bài 17. Giải quyết bài toán Baber trong trường hợp tiệm có nhiều thợ.

Bài 18. Xét trạng thái hệ thống:

Max			Allocation			Available
R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	3	2	2	1	0	0
P2	6	1	3	2	1	1
P3	3	1	4	2	1	1
P4	4	2	2	0	0	2

Nếu tiến trình P2 yêu cầu 4 cho R1, 1 cho R3. Hãy cho biết yêu cầu này có thể đáp ứng mà bảo đảm không xảy ra tình trạng deadlock hay không?

Bài 19. Xét trạng thái hệ thống:

Max				Allocation				Available
A	B	C	D	A	B	C	D	A	B	C	D
P1	0	0	1	2	0	0	1	2
P2	1	7	5	0	1	0	0	0
P3	2	3	5	6	1	3	5	4
P4	0	6	5	2	0	6	3	2
P5	0	6	5	6	0	0	1	4

a) Cho biết nội dung của bảng Need.

b) Hệ thông có ở trạng thái an toàn không?

c) Nếu tiến trình P2 có yêu cầu tài nguyên (0,4,2,0), yêu cầu này có được đáp ứng tức thời không?