int Available[NumResources]

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 ?

procedure Swap() var a,b: boolean);

var temp : boolean;

begin

a:= b;

end;

process A

{ while (TRUE)

na = na +1;

}

process B

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

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?

do

  X = X +1;

    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 P1 { A1 ; A2 } process P2 { B1 ; B2 }

Đồ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 P1 { for ( i = 1; i <= 100; i ++) Ai }

process P2 { 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.

w := x1 * x2

v := x3 * x4

y := v * x5

z := v * x6

y := w * y

z := w * z

ans := y + z

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)

#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)

#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)

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)

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

}

}

{

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

{

state[i] = EATING;

}

}

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?

/* 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;

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

int customer()

{

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

if( waiting_customers >= 5 ){

signal( mutex );

return 0;

}

/* there is now a new waiting customer */

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 ){

wait( customers );

wait( mutex );

waiting_customers -= 1;

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) 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?