Bài tập đồng bộ hoá tiến trình có lời giải

Bài ôn tập:„Đồng bộ hoá tiến trìnhCâu 1 : 2 nhu cầu trao đổi thông tin của tiến trình nhằm :a. Chia sẻ tài nguyên chung, Phối hợp hoạt độngb. Xử lý song song , Phối hợp hoạt độngc. Bảo đảm độc lập, Thông báo lỗiĐáp án : a11/8/2005Trần Hạnh NhiBài ôn tập 3 :„Đồng bộ hoá tiến trìnhCâu 2 : Race Condition làa. Kết quả thực hiện tiến trình phụ thuộc vào kết quả điều phốib. Hiện tượng các tiến trình chia sẻ tài nguyên chungc. Kết quả tiến trình thực hiện luôn luôn saiĐáp án : a11/8/2005Trần Hạnh NhiBài ôn tập 3 :„Đồng bộ hoá tiến trìnhCâu 3 : Critical section làa.b.c.d.Tài nguyên dùng chung giữa các tiến trìnhCơ chế bảo vệ tài nguyên dùng chungĐoạn chương trình có khả năng gây ra hiện tượng race conditionĐoạn chương trình có truy cập tài nguyên dùng chungĐáp án : c11/8/2005Trần Hạnh NhiBài ôn tập 3 :„Đồng bộ hoá tiến trìnhCâu 4 : 2 nhu cầu đồng bộ tiến trình là :a.b.c.d.Hò hẹn , Phối hợp hoạt độngTrao đổi thông tin, Phối hợp hoạt độngĐộc quyền truy xuất , Giải quyết tranh chấpKhông có câu nào đúngĐáp án : d11/8/2005Trần Hạnh NhiBài ôn tập 3 :„Đồng bộ hoá tiến trìnhCâu 5 : Cho biết các điều kiện cho một giải pháp đồng bộtốtĐáp án :ƒ Mutual Exclusion : Không có hai tiến trình cùng ở trong miềngăng cùng lúcƒ Progess : Một tiến trình tạm dừng bên ngoài miền găngkhông được ngăn cản các tiến trình khác vào miền găngƒ Bounded Waiting : Không có tiến trình nào phải chờ vô hạnđể được vào miền găng.ƒ Không có giả thiết nào đặt ra cho sự liên hệ về tốc độcủa các tiến trình, cũng như về số lượng bộ xử lý tronghệ thống11/8/2005Trần Hạnh NhiCâu 6 : Xét giải pháp phần mềm do Dekker đề nghò để tổ chức truy xất độc quyền cho haitiến trình . Hai tiến trình P0, 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 :repeatflag[i] := true;while flag[j] doif turn = j thenbeginflag[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 ?Câu 6: Đáp ánƒ Đúng.ƒ Giải pháp này bảo đảm yêu cầu độc quyền truy xuất vì khicả 2 tiến trình Pi và Pj đồng thời quan tâm đến việc vào miềngăng [flag[i]=true và flag[j]=true] thì chỉ có một tiến trìnhđược vào miền găng tùy theo giá trò của turn.ƒ11/8/2005Nếu tiến trình Pi đang xử lý Non_criticalsection, thì trước đóflag[i] đã được gán giá trò false, do vậy không ngăn cản Pjquay lại criticalsectionTrần Hạnh NhiCâu 7 : 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 ?Đáp án :ƒ Không. Xét tình huống khi flag[0] =1; turn =0=> P0vào CS, nếu lúc đó flag[1]= 1, P1 có thể gán turn = 1và vào luôn CS !Câu 8 : 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;begintemp := 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ấuchương trình tương ứng.Caâu 8: Ñaùp aùnwhile [TRUE]{}11/8/2005key = TRUE;while [ key = TRUE]Swap[lock,key];critical-section [];lock = false;Noncritical-section[];Traàn Haïnh Nhi„Câu 9 : 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 +10
b. Nếu giảm điều kiện chỉ là na 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à Bcùng thực hiện?Caâu 9: Ñaùp aùnÑaùp aùn : semaphore a = 0 ; b = 10 ;Process A[]{Process B[]{int item;int item;while [TRUE]while [TRUE]{{down[b];down[a];na = na + 1;nb = nb + 1;up[a];up[b];}}}}11/8/2005Traàn Haïnh Nhi„ Câu 10 :Một biến X được chia sẻ bởi hai tiến trình cùng thực hiện đoạn codesau :doX = 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 Xkhông vượt quá 20 ?Caâu 10: Ñaùp aùnÑaùp aùn :11/8/2005Semaphore mutex = 1;do{down[mutex];X = X +1;if [ X == 20] X = 0;up[mutex];}while [ TRUE ];Traàn Haïnh Nhi„ Câu 11 :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ả A1 và B1 đềuhoàn tất trước khi A2 hay B2 bắt đầu .Caâu 11: Ñaùp aùnÑaùp aùn : semaphore ab = 0 ; ba = 0 ;Process A[]Process B[]{{B1;A1;up[ba];up[ab];down[ab];down[ba];A2;B2;}}11/8/2005Traàn Haïnh Nhi„ Câu 12 :Tổng quát hoá câu hỏi 8] cho các tiến trình xử lý đoạn chương trìnhsau :

process P1 { for [ i = 1; i process P2 { for [ j = 1; j Đồ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.Caâu 12: Ñaùp aùnÑaùp aùn : semaphore ab = 1 ; ba =1 ;Process A[]Process B[]{{

for [ i = 1; i
for [ i = 1; i{{down[ba];down[ab];Bi;Ai;up[ab];up[ba];}}}11/8/2005Traàn Haïnh Nhi„ Câu 13 :Sử dụng semaphore để viết lại chương trình sau theo mô hình xử lýđồng hành:w := x1 * x2v := x3 * x4y := v * x5z := v * x6y := w * yz := w * zans := y + zÑaùp aùn :process P1P1P2{ w := x1 * x2 ;up[s15] ;P3up[s16] ;P5P6}process P2P7{ v := x3 * x4 ;up[s23] ;up[s24] ;}process P3{down[s23] ;y := v * x5 ;up[s35] ;}process P4{down[s24] ;z := v * x ;up[s46] ;}11/8/2005P4process P5{down[s15] ;down[s35] ;y := w * y ;up[s57] ;}process P6{down[s16] ;down[s46] ;z := w * z ;up[s67] ;}process P7{down[s57] ;down[s67] ;ans := y + z ;}Traàn Haïnh NhiCaâu 14:Cho mảng sau:int x[20];Sử dụng cơ chế đồng bộ hoá là semaphore để viết code cho 3 threadsB,C,D cùng thực hiện đồng thời các thao tác trên mảng x thoả mãncác yêu cầu sau:a. B tính tổng giá trị các phần tử mảng x có chỉ số chẵn.b. C tính tổng giá trị các phần tử mảng x có chỉ số lẽ.c. D tính tổng giá trị tất cả các phần tử của mảng x, dựa trên kết quả trảvề của B và C.d. Các threads được khởi động cùng lúc.e. Các threads kết thúc khi xong công việc của mình, không cần chờ lẫnnhau.f. Phải khai thác tối đa khả năng xử lý song song,chia sẽ tài nguyên dùngchung của các threads.11/8/2005Traàn Haïnh NhiCaâu 14 – Caùch 1:Ñaùp aùn : semaphore overB =0, overC =0 ;Interger sumB, sumC = 0;Process B[]Process C[]{Process D[]{{

for[i=0;i

for[i=0;i