Chương 4: Các process song song không đồng bộ
asynchronous concurent process
4.1 Mở đầu
Các process gọi là song song nếu các process đó tồn tại đồng thời. Các process song song (concurent process) có thể hoạt động hoàn toàn độc lập với nhau hoặc song song không đồng bộ – asynchronous, tức là theo chu kỳ chúng cần đồng bộ và tương tác với nhau. Asynchronism – song song không đồng bộ là một vấn đề phức tạp.
Chúng ta sẽ xem xét một số vấn đề liên quan đến điều khiển các quá trình song song không đồng bộ – asynchronous concurent process. Các ví dụ được đưa ra với ngôn ngữ giả pascal. Một số ví dụ về ngôn ngữ cho phép lập trình song song là ngôn ngữ Modula (Nicolar Witt), ngôn ngữ Ada.
4.2 Xử lý song song
Theo sự phát triển của máy tính chúng ta có thấy sự phổ biến của các hệ thống đa BXL (multiprocessor) và cùng với nó là sự phổ biến của xử lý song song. Nếu như một quá trình logic có thể xử lý song song logic thì các hệ thống mới có thể xử lý chúng song song thực sự và có thể công việc được phân chia giữa các BXL khác nhau.
Xử lý song song là vấn đề được quan tâm và có nhiều khó khăn do một loạt nguyên nhân khác nhau. Con người theo tự nhiên có xu hướng chỉ chú ý đến một công việc tại mỗi thời điểm hơn là nghĩ đến nhiều việc khác nhau cúng một lúc. Thông thường khó mà xác định những thao tác nào có thể thực hiện song song. Và theo dõi một chương trình song song khó hơn nhiều so với chương trình xử lý tuần tự.
Các asynchronous process cần tương tác qua lại lẫn nhau theo chu kỳ thời gian và tương tác này có thể khá phức tạp. Cuối cùng, việc chứng tỏ sự đúng đắn cho các chương trình song song khó hơn nhiều so với trường hợp chương trình tuần tự. Và chúng ta cũng đến phương pháp hiệu quả để chứng minh tính đúng đắn của chương trình, có như thế chúng ta mới có thể xây dựng các hệ thống có tính ổn định cao.
4.3 Các lệnh chỉ thị xử lý song song: parbegin và parend
Trong nhiều ngôn ngữ lập trình đ• có các chỉ thị yêu cầu xử lý song song(như trong Ada, Modula,...) các chỉ thị này thường đi theo cặp:
Chỉ thị đầu tiên chỉ ra rằng bắt đầu từ sau lệnh đó, chương trình được tách thành một số dòng điều khiển (thread control) thực hiện song song.
Chỉ thị thứ hai chỉ ra rằng từ đó chương trình lại được xử lý tuần tự.
Có nhiều tên khác nhau nhưng người ta thường dùng cặp parbegin/parend (Dijktra – cooperating sequenical process). Nói chung đoạn m• chương trình được thực hiện song song có dạng
parbegin
operator 1
operator 2
. . . . . .
operator n
parend
Việc thực hiện đoạn chương trình song song có thể hình dung như sau. Chương trình được thực hiện theo một luồng điều khiển tuần tự, đến khi gặp lệnh parbegin, luồng xử lý sẽ được chia thành n quá trình xử lý độc lập, mỗi quá trình sẽ xử lý một thao tác tương ứng từ operator 1, ... đến operator n. Thao tác này có thể là các lệnh đơn, lời gọi hàm, khối các lệnh tuần tự nằm giữa begin/end hay là tổ hợp các thao tác đó.
Các quá trình xử lý sẽ dần thực hiện đến lệnh parend lúc đó luồng điều khiển lại hợp nhất thành một luồng xử lý các lệnh tiếp theo một cách tuần tự.
Ví dụ xét biểu thức:
x:= ( -b + ( b2 - 4*a*c ) * 5 ) / (2*a)
nếu quá trình xử lý là hoàn toàn tuần tự chúng ta có thể làm theo các bước sau:
b2
4*a
(4*a)*c
b2 - (4*a*c)
(b2 - (4*a*c))*5
-b
-b + ((b2 - (4*a*c))*5)
2*a
(-b + ((b2 - (4*a*c))*5)) / (2*a)
Các bước xử lý trên theo đúng trình tự quy tắc thực hiện phép toán.
Với hệ thống hỗ trợ xử lý song song chúng ta có thể làm như sau:
parbegin
temp1 := -b
temp2 := b2
temp3 := 4*a
temp4 := 2*a
parend
temp5 := temp3*c
temp5 := temp2 - temp5
temp5 := temp5 * 5
temp5 := temp1 + temp5
x := temp5 / temp4
Ta thấy nếu thực hiện xử lý song song thì thời gian tính toán giảm đi đáng kể so với khi tính tuần tự.
4.4 Mutual exclusion (loại trừ nhau)
Xét trường hợp hệ thống phục vụ trong chế độ phân chia thời gian cho nhiều thiết bị đầu cuối – terminal. Giả sử khi người sử dụng đánh hết một dòng và gõ Enter, cần tính số dòng của tất cả các người sử dụng đ• gõ từ tất cả các terminal. Để thực hiện điều đó, mỗi khi một người sử dụng nào đó gõ enter thì process của người dùng đó sẽ tăng thêm 1 đơn vị cho một biến toàn cục (global) totalLine. Vì hệ thống là đa xử lý và đa người dùng, do đó hoàn toàn có khả năng là hai người dùng khác nhau gõ enter gần như đồng thời, khi đó 2 process điều khiển ứng với 2 người dùng đó sẽ đồng thời muốn truy nhập đến biến toàn cục totalLine. Để tăng biến đó giả sử mỗi process ứng dụng đều dùng các lệnh sau:
1- load totalline
2- totalline := totalline + 1
3- store totalline
Giả sử tại một thời điểm, totalline có giá trị 62829
Bây giờ nếu mới process 1 thực hiện được 2 lệnh đầu tiên:
load totalline (đọc giá trị hiện thời của biến) và tăng 1 cho giá trị biến totalline := totalline + 1 khi đó trong một thanh ghi (ví dụ Ax) chứa giá trị mới 62830 của biến totalline.
Sau đó process 1 không được quyền sử dụng BXL nữa (ví dụ do ngắt thời gian) và đến lượt process 2 được thực hiện. Giả sử process 2 kịp thực hiện cả 3 lệnh trên, khi đó giá trị của biến totalline sau khi thực hiện xong sẽ có giá trị 62830. Sau đó điều khiển được trả lại cho HĐH và đến lượt process 1 được tiếp tục, nó thực hiện nốt lệnh thứ 3 tức là ghi lại giá trị 62830 vào biến totalline. Chúng ta thấy do sự điều khiển truy xuất không đúng mà chương trình hoạt động không đúng.
Ta thấy rằng vấn đề này có thể khắc phục nếu mỗi process có quyền truy nhập duy nhất đến biến totalline, tức là khi một process đang truy nhập đến biến totalline thì các process khác phải đợi đến khi process đầu tiên kết thúc truy nhập.
Như thế, khi một process truy nhập đến dữ liệu chung thì cần cấm tất cả các process khác truy nhập đến cùng dữ liệu vào thời điểm đó. Điều đó gọi là mutual exclusion (loại trừ lẫn nhau)
4.5 Khoảng tới hạn Critical region
Loại trừ lẫn nhau chỉ cần thiết trong trường hợp khi các process cùng truy nhập đến dữ liệu chung, hay khi chúng thực hiện các thao tác có thể dẫn tới tranh chấp (conflic) dữ liệu nói chung, còn khi chúng thực hiện các thao tác operation không dẫn tới tranh chấp thì hoàn toàn có thể thực hiện song song đồng thời. Khi process truy nhập đến dữ liệu chung thì người ta nói rằng lúc đó process nằm trong khoảng tới hạn – critical region.
Rõ ràng là để giải quyết tranh chấp thì khi có một process nằm trong khoảng tới hạn, cần phải không cho phép process khác (ít nhất là các process truy nhập đến cùng một dữ liệu) được vào khoảng tới hạn (tất nhiên chúng vẫn có thể thực hiện các thao tác khác ngoài khoảng thới hạn). Còn khi proces ra khỏi khoảng tới hạn thì một trong số các process đang chờ vào khoảng tới hạn phải được tiếp tục vào khoảng tới hạn. Đảm bảo 'loại trừ lẫn nhau' là một trong những vấn đề mấu chốt của lập trình xử lý song song. Có nhiều phương pháp được đề xuất từ thực hiện hoàn toàn bằng phần mềm đến thực hiện bằng phần cứng, từ mức thấp đến mức cao, có những phương pháp cho phép loại trừ lẫn nhau trong điều kiện tương đối thoải mái, còn có những phương pháp thì bắt buộc phải có thêm các điều kiện chặt chẽ.
Khi một process nằm trong khoảng tới hạn thì có nhiều vấn đề cần quan tâm. Trong chế độ này nó có toàn quyền truy nhập dữ liệu chung còn các process khác phải chờ. Do đó các process cần ra khỏi chế độ này càng nhanh càng tốt, trong chế độ này nó không được chuyển sang trạng thái blocked, do đó các khoảng tới hạn cần thiết kế, kiểm tra cẩn thận (để ví dụ không cho phép xảy ra vòng lặp chờ trong khoảng tới hạn...)
Khi process kết thúc (ra khỏi) khoảng tới hạn (bình thường hoặc ngay cả khi có lỗi) thì HĐH phải kiểm soát được để huỷ bỏ chế độ tới hạn, nhờ thế các process khác có thể đến lượt vào khoảng tới hạn.
4.6 Mutual exclusion Primitive
Chương trình song song dưới đây đảm bảo bài toán trong mục 4.4 hoạt động đúng. Từ đây trở đi chúng ta xét trường hợp chỉ có hai process song song, cần phải nói rằng trường hợp có n process (n>2) thì bài toán phức tạp hơn rất nhiều.
Trong chương trình 4.2 chúng ta dùng hai chỉ thị: enterMutualExclusion và exitMutualExclusion trong mỗi process ở đoạn code truy nhập đến dữ liệu chung (biến toàn cục totalLine), hai chỉ thị này bao hai đầu khoảng tới hạn. Đôi khi các chỉ thị này được gọi là mutual exclusion primitive
Chương trình 4.2
Program MutualExclusionSample
var
totalLine: integer;
procedure process1
begin
while true do begin
get line {readln}
enterMutualExclusion;
totalLine := totalLine +1;
exitMutualExclusion;
processing line ...
end;
end;
procedure process2
begin
while true do begin
get line {readln}
enterMutualExclusion;
totalLine := totalLine +1;
exitMutualExclusion;
processing line ...
end;
end;
begin
totalLine := 0;
parbegin
process1;
process2;
parend;
end.
Trong trường hợp có hai process, các lệnh primitive làm việc như sau: khi process 1 thực hiện chỉ thị enterMutualExclusion (và lúc đó process 2 ở ngoài khoảng tới hạn) thì nó được vào khoảng tới hạn, thực hiện các lệnh trong khoảng tới hạn và đến khi thực hiện lệnh exitMutualExclusion là lúc báo hiệu nó ra khỏi khoảng tới hạn. Còn nếu khi process1 muốn vào khoảng thới hạn, trong lúc đó process 2 đ• ở trong khoảng tới hạn thì process1 nó phải chờ đến khi process2 ra khỏi khoảng tới hạn để có thể tiếp tục vào khoảng tới hạn.
Nếu cả hai process thực hiện enterMutualExclusion cùng một lúc thì một trong hai process sẽ được phép vào khoảng tới hạn còn process kia sẽ phải chờ, có thể sự lựa chọn là ngẫu nhiên.
4.7 Thực hiện mutual exclusion primitive
Chúng ta sẽ tìm cách thực hiện các primitive enter và exit với các hạn chế sau:
Vấn đề giải quyết hoàn toàn bằng chương trình (phần mềm) trên hệ thống không có lệnh chuyên cho mutual exclusion. Mỗi lệnh được thực hiện trọn vẹn không bị ngắt giữa chừng. Khi có nhiều process cùng muốn truy nhập đến dữ liệu chung thì tranh chấp được giải quyết bằng phần cứng, một cách tình cờ sẽ có một process được chọn.
Không có bất cứ giả sử gì về tốc độ tương đối của các asynchronous parallel process
Các process nằm ngoài khoảng tới hạn không thể cấm các process khác vào khoảng tới hạn.
Không được để process chờ vô hạn để vào khoảng tới hạn.
Cơ chế thực hiện loại trừ lẫn nhau bằng chương trình được nhà toán học Hà lan Dekker đề ra đầu tiên. Chúng ta sẽ xem xét các version của thuật toán Dekker do Dijkstra thực hiện.
4.8 Thuật toán Dekker
Đầu tiên, chúng ta xem xét version đầu tiên
Có thể coi mỗi process như là một vòng lặp vô tận với nhiều lần lặp vào chế độ mutual exclusion. Trong version này primitive enter mutual exclusion được thực hiện nhịp vòng lặp while chờ đến khi biến processno bằng số của process, còn primitive exit mutual exclusion thực hiện như một lệnh đặt biến processno bằng số của process khác.
Chương trình 4.3
Program Version1
var
processNo: integer;
procedure process1
begin
while true do begin
....
while processNo = 2 do ;
{critical region}
processNo := 2;
....
end;
end;
procedure process2
begin
while true do begin
....
while processNo = 1 do ;
{critical region}
processNo := 1;
....
end;
end;
begin
processNo := 1;
parbegin
process1;
process2;
parend;
end.
Hoạt động: cả hai process cùng thực hiện. Vì đầu tiên biến processNo gán bằng 1 do đó chỉ process1 được vào critical region. Process 2 khi muốn vào critical region kiểm tra thấy biến processno có giá trị 1 do đó nó phải chờ bằng vòng lặp rỗng, nó chờ đến khi processNo=2 tức là khi process 1 ra khỏi critical region và đặt processNo :=2. Vậy chương trình đ• đảm bảo loại trừ lẫn nhau (mutual exclusion).
Version1 có nhiều nhược điểm, process 1 phải vào critical region trước tiên (tức là dù process 2 sẵn sàng trước thì nó vẫn phải chờ) và các process lần lượt vào critical region theo thứ tự cố định (do đó nếu một process thực hiện các lệnh trong critical region thường xuyên hơn thì nó phải làm việc với tốc độ chậm hơn nhiều). Chương trình này đảm bảo không rơi vào tình trạng deadlock vì khi cả hai process cùng muốn vào critical region thì có ít nhất một process tiếp tục. Còn khi một process kết thúc thì sau đó process còn lại cũng kết thúc.
Trong version 1 việc thực hiện mutual exclusion chỉ bằng một biến do đó có vấn đề các process vào khoảng tới hạn theo thứ tự cố định. Để cải tiến, trong version 2 sử dụng hai biến logic: flag1 và flag2, chúng nhận giá trị true khi process tương ứng nằm trong critical region.
Trong version này process 1 chủ động chờ (active wait) trong khi biến flag2 vẫn là true. Khi process 2 ra khỏi khoảng tới hạn, nó đặt lại flag2 := false và do đó process1 ra khỏi vòng chờ while, đặt biến flag1 = true và vào khoảng tới hạn. Khi flag1 còn là true thì process 2 không thể vào khoảng tới hạn.
Chương trình 4.4
Program Version2
var
flag1, flag2: boonlean;
procedure process1
begin
while true do begin
....
while flag2 = true do ;
flag1 := true;
{critical region}
flag1 := false;
....
end;
end;
procedure process2
begin
while true do begin
....
while flag1 = true do ;
flag2 := true;
{critical region}
flag2 := false;
....
end;
end;
begin
flag1 := false;
flag2 := false;
parbegin
process1;
process2;
parend;
end.
Nhưng lại xuất hiện một số vấn đề liên quan đến lập trình song song. Vì process 1 và process 2 là song song do đó chúng có thể đồng thời thử vào critical region. Đầu tiên các biến flag1 và flag2 có giá trị false. Process 1 kiểm tra biến flag2 thấy flag2=false và thoát khỏi vòng lặp chờ, trước khi nó kịp đặt flag1 thành true bằng lệnh flag1:= true thì đến lượt process 2 được chiếm BXL, process2 cũng có thể kiểm tra thấy flag1 là false (vì lúc đó process1 chưa kịp đặt)- lúc đó process 2 đặt flag2:= true và cũng vào critical region. Như thế cả hai process cùng vào chế độ critical, do đó version 2 không đảm bảo loại trừ lẫn nhau.
Điểm yếu của version 2 là giữa thời điểm khi process nằm trong vòng chờ xác định thấy nó có thể đi tiếp và thời điểm nó đặt cờ (biến flag) nói rằng nó đ• vào critical region. Do đó cần thiết để vào lúc process kết thúc vòng lặp chờ, process khác không thể ra khỏi vòng lặp chờ. Trong chương trình version3 (4,5) để giải quyết vấn đề này người ta đặt cờ cho mỗi process trước khi thực hiện vòng lặp chờ.
Chương trình 4.5
Program Version3
var
flag1, flag2: boonlean;
procedure process1
begin
while true do begin
....
flag1 := true;
while flag2 = true do ;
{critical region}
flag1 := false;
....
end;
end;
procedure process2
begin
while true do begin
....
flag2 := true
while flag1 = true do ;
{critical region}
flag2 := false;
....
end;
end;
begin
flag1 := false;
flag2 := false;
parbegin
process1;
process2;
parend;
end.
Version 3 giải quyết được một vấn đề nhưng lại nảy sinh vấn đề khác. Nếu như mỗi process trước khi vào vòng chờ đặt cờ của mình thì mỗi process có thể kiểm tra thấy cờ của process khác đ• đặt và cả hai process đều chờ ở vòng lặp vô tận. Chương trình này là một ví dụ của khái niệm deadlock - tắc ngẽn.
Điểm yếu của Version 3 là ở chỗ mỗi process đều có thể bị block ở vùng chờ. Chúng ta cần có biện pháp thoát khỏi vòng chờ này.
Trong version 4 để làm điều đó, ta đặt lại cờ (biến flag) trong khoảng thời gian ngắn về giá trị false để process kia có cơ hội thoát khỏi vòng chờ.
Chương trình 4.6
Program Version4
var
flag1, flag2: boonlean;
procedure process1
begin
while true do begin
....
flag1 := true;
while flag2 = true do begin
flag1 := false;
Delay(random);
flag1 := true;
end;
{critical region}
flag1go := false;
....
end;
end;
procedure process2
begin
while true do begin
....
flag2 := true
while flag1 = true do begin
flag2 := false;
Delay(random);
flag2 := true;
end;
{critical region}
flag2 := false;
....
end;
end;
begin
flag1 := false;
flag2 := false;
parbegin
process1;
process2;
parend;
end.
Thoạt xem, version4 đảm bảo sự loại trừ lẫn nhau và không bị deadlock, nhưng lại xuất hiện vấn đề khác cũng rất quan trọng, và cũng là vòng chờ vô tận. Chúng ta xét xem tại sao điều đó xảy ra. Vì chúng ta không có giả sử gì về tốc độ tương đối giữa các process do đó có thể có trường hợp các process lần lượt thực hiện d•y thao tác như sau trong một interval:
1. đặt cờ flag giá trị true, vào vòng lặp chờ,
2. đặt lại cờ flag giá trị false, chờ random
3. lại đặt cờ giá trị true và lặp lại quá trình trong vòng chờ.
Khi đó các process thực hiện xong tất cả các thao tác đó, điều kiện kiểm tra luôn đúng và không thể thoát khỏi vòng chờ. Mặc dù trường hợp đó rất hiếm nhưng về nguyên tắc là có thể, do đó version 4 cũng không thể áp dụng ví dụ như trong hệ thống điều khiển chuyến bay vũ trụ, ... dù xác suất nhỏ.
Như thế chúng ta cần khắc phục sự chờ vô tận. Thuật toán Dekker loại trừ tình trạng chờ vô tận trong Version 4. Với một số lượng không lớn code, chương trình theo thuật toán của Dekker cho phép giải quyết triệt để vấn đề loại trừ lẫn nhau cho hai process, không đòi hỏi các lệnh đặc biệt nào.
Chương trình 4.7
Program Dekker
var
flag1, flag2go: boonlean;
selection : byte; {set of 1,2}
procedure process1
begin
while true do begin
....
flag1 := true;
while flag2 = true do begin
if selection = 2 then begin
flag1 := false;
while selection = 2 do ;
flag1 := true;
end;
end;
{critical region}
selection := 2;
flag1 := false;
....
end;
end;
procedure process2
begin
while true do begin
....
flag2 := true
while flag1 = true do begin
if selection = 1 then begin
flag2 := false;
while selection = 1 do ;
flag2 := true;
end;
end;
{critical region}
selection := 1;
flag2 := false;
....
end;
end;
begin
flag1 := false;
flag2 := false;
selection := 1;
parbegin
process1;
process2;
parend;
end.
Process 1 thông báo rằng muốn vào khoảng tới hạn bằng cách đặt cờ của mình (process1go := true). Sau đó nó vào vòng lặp kiểm tra xem process 2 có muốn vào khoảng tới hạn hay không. Nếu như cờ của process 2 không đặt (process2go = true) thì nó ra khỏi vòng lặp và vào khoảng tới hạn. Giả sử trong vòng lặp kiểm tra nói trên nó thấy cờ của process 2 đ• đặt thì nó phải vào vòng lặp kiểm tra biến selectprocess- biến dùng để giải quyết tranh chấp khi cả hai process đồng thời muốn vào khoảng tới hạn. Nếu select process =1 thì nó ra khỏi vòng lặp của lệnh if và lặp lại kiểm tra cờ của process 2- cho đến khi process 2 bỏ cờ của mình (chúng ta sẽ thấy process 2 nhất định sẽ bỏ cờ của mình).
Nếu process 1 xác định thấy quyền ưu tiên thuộc về process 2 (biến select process =2) thì nó vào lệnh if và bỏ cờ của mình, sau đó lặp trong vòng chờ khi select process vẫn là 2. Với việc bỏ cờ của mình process 1 cho phép process 2 ra khỏi vòng kiểm tra và đi vào khoảng tới hạn.
Cùng với thời gian, process 2 ra khỏi khoảng tới hạn và thực hiện chỉ thị exit critical region bằng 2 lệnh đặt quyền ưu tiên cho process 1 (select process:=1) và bỏ cờ của mình (process2go := false). Khi đó process 1 có cơ hội ra khỏi vòng chờ và đi vào khoảng tới hạn nếu như process2go = false. Nếu process 2 ngay lập tức lại muốn vào khoảng tới hạn tức là nó lại đặt process2go := true thì process1 chưa thoát khỏi vòng lặp chờ ở ngoài (while process2go = true do), khi đó process 2 vào vòng chờ, vào lệnh kiểm tra if và vì selectprocess=1 - quyền ưu tiên thuộc về process1 nên process2 bỏ cờ của nó, do đó process 1 ra khỏi vòng lặp ngoài để vào khoảng tới hạn còn process 2 chờ đến lượt mình.
Còn một khả năng mà chúng ta cần xem xét. Khi process 1 ra khỏi vòng lặp ở trong, nó chưa kịp đặt cờ của nó thì bị mất quyền sử dụng BXL, đến lượt process 2 cũng muốn vào khoảng tới hạn; Nó đặt cờ của mình, kiểm tra thấy cờ của process 1 chưa dựng và lại đi vào khoảng tới hạn. Khi process 1 lại có BXL, nó đặt cờ của mình và bị tiếp tục chờ ở vòng lặp ngoài. Vì select process sẽ có giá trị 1 nên khi process 2 ra khỏi khoảng tới hạn process 2 sẽ không thể vào khoảng tới hạn một lần nữa và phải chờ ở vòng lặp trong, do đó process 1 có cơ hội vào khoảng tới hạn.
4.9 Loại trừ lẫn nhau cho N process
Giải pháp thực hiện bằng chương trình cho vấn đề Mutual Exclusion Primitive đối với N process lần đầu tiên được Dijkstra đề xuất. Sau đó Knuth hoàn thiện thêm phương pháp của Dijkstra, loại trừ được tình trạng chờ vô tận, nhưng vẫn còn nhược điểm là một số process vẫn có thể bị chờ lâu. Do đó nhiều nhà nghiên cứu tìm tòi những thuật toán cho phép rút ngắn thời gian trễ (chờ). Eisenberg và McGuite đ• đề ra lời giải đảm bảo rằng process bất kỳ sẽ được vào khoảng tới hạn sau không quá N-1 lần thử. Lamport đ• thiết kế thuật toán được áp dụng riêng cho các hệ cơ sở dữ liệu phân tán.
4.10 Thực hiện loại trừ lẫn nhau bằng phần cứng: lệnh test and set
Thuật toán Decker là giải pháp phần mềm cho vấn đề loại trừ lẫn nhau. Bây giờ chúng ta sẽ xem xét giải páp phần cứng. Điều quan trọng để đảm bảo giải quyết vấn đề là có một lệnh phần cứng: lệnh này đọc biến, ghi giá trị của biến vào vùng lưu trữ và đặt giá trị cụ thể cho biến đó. Lệnh này thường gọi là test and set. Tất cả các thao tác trên được gói gọn trong một lệnh và được thực hiện trọn vẹn không bị ngắt.
Lệnh test and set (a,b) đọc giá trị của biến logic b, copy giá trị vào biến a và sau đó đặt giá trị true cho b. Ví dụ sử dụng lệnh testandset để thực hiện Mutual Exclusion được thể hiện trong chương trình 4.8
Biến active kiểu boolean có giá trị true khi một trong các process nằm trong khoảng tới hạn và giá trị false trong trường hợp ngược lại. Process1 có được vào khoảng tới hạn hay không phụ thuộc vào giá trị biến local kiểu boolean disable1. Nó đặt disable1 := true, sau đó vào vòng lặp kiểm tra thực hiện lệnh testandset đối với biến toàn cục active. Nếu lúc đó process2 không nằm trong khoảng tới hạn, biến active có giá trị false. Lệnh test and set sẽ ghi giá trị đó vào biến disable1 và đặt giá trị active= true. Do đó process 1 ra khỏi vòng lặp chờ kiểm tra và vào khoảng tới hạn. Vì biến active có giá trị true nên process 2 không thể vào khoảng tới hạn.
Chương trình 4.8
Program TestAndSet
var
disable1, disable 2: boonlean;
active: boolean;
procedure process1
var
disable1: boonlean;
begin
while true do begin
....
disable1 := true;
while disable1 = true do
testAndSet(disable1, active);
{critical region}
active := false;
....
end;
end;
procedure process2
var
disable2: boonlean;
begin
while true do begin
....
disable2 := true;
while disable2 = true do
testAndSet(disable2, active);
{critical region}
active := false;
....
end;
end;
begin
active := false;
parbegin
process1;
process2;
parend;
end.
Giả sử rằng process 2 đ• nằm trong khoảng tới hạn, khi process 1 muốn vào khoảng tới hạn nó đặt biến disable1 := true và vào vòng kiểm tra. Vì giá trị của active là true (do process 2 đang trong khoảng tới hạn) nên lệnh test and set copy giá trị đó (true) vào biến disable1 và như vậy điều kiện vòng lặp vẫn đúng và process1 phải thực hiện vòng lặp kiểm tra. Khi process 2 ra khỏi khoảng tới hạn, nó đặt lại biến active := false, lúc đó lệnh testandset (trong vòng lặp kiểm tra của process 1) thấy biến active= false, copy giá trị này vào biến disable1 và đặt active:= true (làm cho proces 2 không thể tiếp tục vào khoảng tới hạn), và vì disable1 có giá trị false nên process 1 có thể đi vào khoảng tới hạn.
Nhưng phương pháp này không loại trừ được tình huống chờ vô tận dù xác suất xảy ra thấp, đặc biệt khi hệ thống có lớn hơn hai BXL. Khi một process ra khỏi khoảng tới hạn, đặt biến active= false, lệnh test and set của process khác có thể 'chiếm' biến active (đặt lại giá trị bằng true) trước khi process đầu kịp thực hiện xong thao tác.
4.11 Semaphore
Các khái niệm trên liên quan đến laọi trừ nhau, đ• được Dijkstra tổng kết qua khái niệm semaphore. Semaphore là biến được bảo vệ, giá trị của nó chỉ có thể đọc, ghi bằng các lệnh đặc biệt P, V và lệnh khởi tạo. Semaphore nhị phân (binary semaphore) chỉ có thể nhận 2 giá trị: 0 và 1. Semaphore đếm (counting semaphore) chỉ có thể nhận giá trị tự nhiên.
Lệnh P trên semaphore S, ký hiệu P(S) thực hiện như sau:
if S > 0 then S := S - 1
else waiting for S
Lệnh V trên semaphore S, ký hiệu V(S) thực hiện như sau:
if (exist process waiting for S) then
allow one of them (waiting process) continue
else S:=S+1;
Chúng ta sẽ giả sử rằng hàng đợi các process đối với một semaphore S sẽ được phục vụ theo nguyên tắc FIFO.
Cũng giống như lệnh TetsAndSet, các lệnh P và V trên semaphore S là một đơn vị, không chia cắt. Đoạn chương trình laọi trừ nhau đối với semahore S của process sẽ được bao bởi các lệnh P(S) và V(S). Nếu đồng thời có nhiều process cùng muốn thực hiện lệnh P(S) thì chỉ có 1 process được phép, còn các proces khác sẽ phải chờ.
Semaphore và các lệnh trên S có thể được xây dựng-cài đặt (implement) bằng phần mềm cũng như bằng phần cứng. Nói chung chúng được cài đặt trong nhân của HĐH, là nơi thực hiện việc đổi trạng thái của process.
Chương trình 4.9 sau cho ta ví dụ đảm bảo loại trừ nhau bằng semaphore. Trong đó, lệnh P có vai trò như giả lệnh EnterExclusion còn lệnh V báo về sự kết thúc.
program Semaphore1
var active: semaphore
procedure process1;
begin
while true do begin
P(active);
critical region;
V(active);
end;
end;
procedure process2;
begin
while true do begin
P(active);
critical region;
V(active);
end;
end;
begin
initilizeSemaphore(active,1);
parbegin
process1;
process2;
parend
end.
4.12 Đồng bộ tiến trình dùng semaphore
Khi process yêu cầu thực hiện I/O, nó tự block và chuyển sang trạng thái chờ sự kiện kết thúc thao tác I/O (blocked process). Process ở trạng thái blocked cần phải được kích hoạt bởi 1 process nào đó. Sự kích hoạt đó có thể được thực hiện ví dụ bằng hàm nào đó liên quan đến giao thức khoá/kích hoạt.
Chúng ta xem xét trường hợp tổng quát hơn, khi 1 process cần phải được thông báo về một sự kiện nào đó xảy ra. Chúng ta giả sử rằng có 1 process khác nhận biết được sự kiện đó. Ví dụ sau đây là ví dụ chúng ta có thể dùng semaphore để thực hiện đồng bộ giữa 2 process.
program block_activate
var event: semaphore;
procedure process1;
begin
P(event);
end;
procedure process2;
begin
V(event);
end;
begin
initializeSemaphore(event,0)
parbegin
process1;
process2;
parend
end.
Trong chương trình này, process 1 thực hiện bình thường, sau khi thực hiện yêu cầu I/O thì thực hiện lệnh P(event), bởi vì ban đầu, event = 0 nên process 1 sẽ phải chờ event. Theo thời gian, khi sự kiện xảy ra, process2 nhận biết nó và thực hiện V(event), bởi vì lúc đó có process1 đang chờ event nên lệnh V rẽ nhánh true và cho phép process1 tiếp tục.
Cần để ý rằng chương trình này vẫn thực thi đúng nhiệm vụ của nó ngay cả khi sự kiện xảy ra trước khi process1 thực hiện lệnh P(event). Khi có sự kiện, process2 thực hiện V(event) theo đó event:=event+1=1 vì không có process nào chờ. Sau đó, khi process1 thực hiện đến lệnh P(event) thì vì event=1 nên nó rẽ nhánh đặt lại event:=event-1=0 và tiếp tục mà không chờ.
4.14 Counting Semaphore
Counting semaphore hữu ích khi có tài nguyên được lấy từ nhóm (pool) các tài nguyên cùng loại. Khi khởi tạo semaphore, giá trị của nó là chỉ số lượng tài nguyên của nhóm. Mỗi lệnh P sẽ giảm giá trị của semaphore đi 1, tương ứng với việc có 1 tài nguyên đ• được lấy từ nhóm. Mỗi lệnh V sẽ tăng gia strị semaphare 1 tương ứng với việc process trả lại 1 tài nguyên cho nhóm, và tài nguyên đó có thể được cấp cho process khác. Trong trường hợp thực hiện lệnh P mà giá trị của semaphore là 0, nghĩa là không còn tài nguyên trống, thì process sẽ phải chờ đến khi nào giá trị semaphore khác 0 nghĩa là có lệnh V được thực hiện (ứng với sự kienẹ có tài nguyên giải phóng)
Bạn đang đọc truyện trên: Truyen2U.Pro