Đồng Bộ Hóa Tiến Trình – Ôn Tập 3

I. Giải Pháp Chờ Đợi Bận

Giải pháp này chỉ áp dụng khi có 2 tiến trình cùng thực thi 1 lúc, P0 và P1. quy uớc 1 tiến trình là Pi, và Pj là tiến trình còn lại, khi đó j = 1 – i.

  • Giải thuật 1:

cho 2 tiến trình sử dụng 1 biến dùng chung turn = 0 hoặc 1; nếu turn ==0 thì Pi được thực thi trong vùng tranh chấp của nó.

Trong đó

critical section: vùng tranh chấp chứa mã thực thi của tiến trình.

remainder section: phần còn lại thực hiện một số thao tác phụ.


//Tiến trình Pi
do{
while (turn != i);
//critical section
turn = j;
//remainder section
}while(1);
//Tiến trình Pj
do{
while (turn != j);
//critical section
turn = i;
//remainder section
}while(1);

Hạn chế:

Giải thuật không giữ được thông tin trạng thái của mỗi tiến trình.

  • Giải thuật 2:

Thay thế turn bằng boolean flag[2], gán các phần tử trong flag giá trị là false, nếu flag[i] == true → Pi sẵn sàng đi vào vùng tranh chấp.

 
//Tiến trình Pi 
do{ 
flag[i] = true;
while (flag[j]); 
//critical section
 flag[i] = false; 
//remainder section 
}while(1); 
//Tiến trình Pj 
do{ 
flag[j] = true;
while (flag[i]);
//critical section 
flag[j] = false;
//remainder section 
}while(1); 

Hạn chế:

  • P0 flag[0]=true;
  • P1 flag[1]=true;

Tiến trình P0, P1 sẽ đợi chờ mãi.

  • P0 flag[0]=false;
  • P1 flag[1]=true;

Tiến trình P1 được vào vùng tranh chấp.

  • P0 flag[0]=true;
  • P1 flag[1]=false;

Tiến trình P0 được vào vùng tranh chấp.

  • P0 flag[0]=false;
  • P1 flag[1]=false;

Nếu tiến 1 trong 2 tiến trình P0 hoặc P1 vào vùng sẵn sàng chạy trước thì sẽ được chạy trước, vì sẽ có flag[0] hoặc flag[1] sẽ bằng false.

Nếu cả 2 tiến trinhg P0 và P1 vào vùng sẵn sàng và bật flag[i]=true và flag[j]=true cùng lúc thì P0 và P1 sẽ chờ đợi mãi.

II. Giải Thuật Peterson

Giải thuật Peterson là sự kết hợp từ 2 giải thuật 1 và 2 ở trên.

 
//Tiến trình Pi 
do{ 
flag[i] = true;
turn=j;
while (flag[j] && turn==j); 
//critical section
 flag[i] = false; 
//remainder section 
}while(1); 
//Tiến trình Pj 
do{ 
flag[j] = true;
turn=i;
while (flag[i] && turn=i);
//critical section 
flag[j] = false;
//remainder section 
}while(1); 

Pi đi vào vùng tranh chấp nếu và chỉ nếu flag[j] = false hoặc turn = 0.

Không thể có trường hợp 2 tiến trình cùng thực thi 1 lúc, vì giả sử điều này xảy ra, ta có flag[i]==flag[j] == true, nhưng turn sẽ là 1 hoặc 0.

Giả sử turn = i, và turn = j được thực hiện đồng thời, khi đó sẽ chỉ có 1 kết quả cuối cùng, và vì vậy, turn == 0, hoặc turn == 1.

II. Giải Thuật Bakery

Loading…

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s