BÀI TẬP THỰC HÀNH VỀ HỆ ĐIỀU HÀNH

Chia sẻ: Trần Công Chính | Ngày: | Loại File: DOCX | Số trang:11

Thêm vào BST

Báo xấu

975
lượt xem 114
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

ĐÂY LÀ BÀI TẬP THỰC HÀNH VỀ HỆ ĐIỀU HÀNH BẰNG TIẾNG ANH GỬI ĐẾN CÁC BẠN ĐỘC GIẢ THAM KHẢO.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI TẬP THỰC HÀNH VỀ HỆ ĐIỀU HÀNH

WAIT and SIGNAL strict WaitSignalVar { Boolean lock; proceesQueue queue; }; Void Wait(WaitSignalVar var) { If (TestAndSet(var.lock)) Var.ProcessQuere.Insert(); } Void Signal(WaitSigntVar var) { Var.ProcessQuere.Remove(); Var.lock=false; } Chú ý: Hàm Insert() đặt tiến trình vào hang đợi và gán trạng thái tiến trình thành bị chặn. Hàm Remove() chọn tiến trình trong hang đợi và gán trạng thái từ bị chặn trở thành sẵn sàng. SEMAPHORE Struct semaphore { Int count; ProcessQuere queue; }; Void P(semaphore s) //proveren: to test { If (s.count > 0) s.count=s.count -1; else s.quere.Insert(); // block this process } Void V(semaphore s) { If (s.quere.empty())
s.count=s.count + 1; else s.quere.Remove(); } SEMAPHORE nhị phân Void P(semaphore s) //proveren: to test { If (s.count ==1) s.count=0; else s.quere.Insert(); // block this process } Void V(semaphore s) { If (s.quere.empty()) s.count= 1; else s.quere.Remove(); } Sử dụng cấu trúc SEMAPHORE để giải quyết vấn đề Mutual Exclusion( loại trừ tương hỗ) Share semaphore s=1; // ……. P(s); // Critical Section V(s); Gán biến s=1 . Trước khi vào vùng tranh chấp, gọi hàm P(s), và sau khi ra khỏi vùng tranh chấp thì gọi hàm V(s) BÀI TẬP Cho hàm TestAndSet sau: Boolean testAndSet( Boolean locked) { If (locked) Return true; Else { Locked=true; Return false; } } a)Cho các tiến trình sử dụng TestAndSet như sau: share Boolean lock=false; //……. While (TestAndSet(lock)) DoNoThing();
// Critical-Section Lock=false; Hãy chứng minh giải pháp TestAndSet thỏa mãn tính loại trừ tương hỗ(Mutual Exclucsion). Hãy cho vd với 3 tiến trình P1, P2, P3. Giải Giải pháp dùng TestAndSet trong trường hợp này cho thấy khi tiến trình nào đó muốn vào vùng tranh chấp thì nó thực hiện hàm TestAndSet : hàm trả về false làm cho tiến trình bỏ qua vòng While, đồng thời gán lock=true để khóa các tiến trình khác không vào miền găng. Nếu tiến trình nào đó muốn vào miền găng(vùng tranh chấp) thì do lock=true nên vòng While bắt tiến trình đó phải chờ(do hàm TestAndSet trả về true) VÍ DỤ: P1 P2 P3  Lock=false  Thực hiện hàm TestAndSet trả về false, thoát khỏi while và vào miền găng, đồng thời gán lock=true( ngụ ý khóa các tiến trình P1,P3 vào miền găng)  Do lock=true nên P1 thực  Do lock=true nên P3 thực  Khi P2 ra khỏi miền găng, hiện vòng While để chờ hiện vòng While để chờ nó gán lock=false vào miền găng vào miền găng  Khi lock=false nên hàm TestAndSet sẽ return về false làm cho P3 không còn chờ nữa(thoát While) và vào miền găng  Gán lock=true để khóa P1 và P2 vào miền găng BÀI TẬP SEMAPHORE 1)Cho các thao tác P,V như sau: Void P(semaphore s) { if (s.count==1) s.count=0; else s.queue.Insert();//block this process }
Void V(semaphore s) { If (s.queue.empty()) s.count=1; else s.queue.remove();//schedule a process } Share semaphore s=1; //--- P(s); Critical-Section; V(s); Chứng minh các tiến trình thỏa mãn yêu cầu mutual-exclusion. 2)Cho cấu trúc SWAP như sau: Void swap(Boolean a, Boolean b) { Boolean temp; temp=b; b=a; a =temp; } Shared boolean lock=false; Boolean key; //…. Key=true; Do Swap(lock,key); While (key); //critical-section; Lock=false; a)Hãy sử dụng chỉ thị swap để tổ chức mutual exclusion b)Hãy chứng minh các tiến trình thỏa yêu cầu mutual exclusion c)Cho ví dụ với n tiến trình BÀI TẬP DEADLOCK 1)Cho trạng thái hiện hành của hệ thống như sau: AVAILABLE(dự trữ) MAX(t ALLO ối đa) CATI ON(đa ng có) R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 3 2 2 1 0 0 4 1 2 P2 6 1 2 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à vẫn bảo đảm không xảy ra tình trạng deadlock hay không? Giải Vì AVAILABLE[1]=4, AVAILABLE[3]=2 thỏa mãn yêu cầu P2, ta có : MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 0 1 0 P2 6 1 3 6 1 3 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 2 0 6 2 3 P2 0 0 0 0 0 0 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 3 2 2 4 0 1 P2 0 0 0 0 0 0 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 0 0 0 0 0 0 6 2 3 P2 0 0 0 0 0 0 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 0 0 0 0 0 0 2 0 3 P2 0 0 0 0 0 0 P3 3 1 4 2 1 1 P4 0 0 0 0 0 0 MAX ALLO AVAILABLE CATIO N R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 0 0 0 0 0 0 6 2 3 P2 0 0 0 0 0 0 P3 3 1 4 2 1 1 P4 0 0 0 0 0 0 SLEEPING BARBER PROBLEM Một tiệm cắt tóc có n ghế cho khách chờ, 1 ghế hớt tóc và 1 thợ hớt tóc.  Nếu khách hàng vào tiệm và không có ghế trống, thì khách đi về  Nếu khách vào tiệm nhưng thợ ngủ thì khách hàng đánh thức và hớt tóc  Ngược lại, khách ngồi chờ.  Nếu thợ cắt xong, thì hớt cho khách kế tiếp. Ngược lại thợ đi ngủ Hãy sử dụng semaphore, viết các hàm chức năng điều khiển hoạt động của thợ và khách. Giải Share semaphore cutHair=0; Share semaphore waiting=0; Share semaphore countMutex=1; Void barber() { While (true) { P(cutHair); GiveHaircut (); } } -------------------------------------------
Void customer() { P(countMutex); If (count== n+1) Exit (); Count=count +1; If (count > 1) { // -------------------------- //take a chair //--------------------------- V( countMutex); P(waiting); } Else V(countMutex); //------------------------------------------ V(cutHair); ReceiveHair(); //-------------------------------------------------- P( countMutex); Count=count – 1; If ( count > 0 ) V( waiting); V(countMutex); } Bài tập Mutual Exclusion *Xét đoạn code sau : Share Boolean waiting[MAX_PID]=false; Share Boolean lock = false ; Int pid = ThisProcessPid(); Boolean ts; Int nextPid; // ----------- waiting[pid]=true; ts= true; while (waiting[pid] and ts ) ts=TestAndSet(lock); waiting[pid] =false; //critical-section nextPid = (pid + 1) mod MAX_PID; while ( nextPid != pid && waiting[nextPid] == false ) nextPid= (pid + 1 ) mod MAX_PID ; if (nextPid == pid ) lock = false; else
waiting[nextPid]= false ; Hãy chứng minh rằng giải pháp dùng TestAndSet bảo đảm tính loại trừ tương hỗ. Giải: Một tiến trình muốn vào miền găng chỉ khi biến ts bằng false hoặc waiting[pid] bằng false.  Nếu ts bằng false thì hàm TestAndSet phải trả về false đồng thời gán lock=true  Bất kỳ tiến trình nào muốn vào miền găng thì hàm TestAndSet sẽ chặn lại.  Khi tiến trình ra khỏi miền găng thì biến lock gán bằng false  Biến waiting[pid] cũng có thể gán false khi tiến trình nào đó rời khỏi miền găng  Một tiến trình nào đó cũng có thể đặt phần tử biến waiting thành false nếu như nó không thể gán lock bằng true. Như vậy chỉ có chỉ có một tiến trình trong miền bởi vì thành phần waiting của nó là false  Không có tiến trình nào có thể có biến ts bằng false ở cùng thời điểm Vậy : Tính loại trừ lẫn nhau (mutual exclusion) được chứng minh. *Cho đoạn code sau : Shared int turn = 1; int myPid=0;// myPid =0 cho tiến trình 0, 1 cho tiến trình 1 int othePid=1 – myPid ; while (turn != myPid ) DoNoThing(); // Critical-Section Turn = otherPid; a)Chứng minh đoạn code này không thỏa mãn cơ chế truy xuất miền găng. b) Sửa đoạn code để thỏa mãn tính mutual-exclusion Giải a)  Khi một tiến trình thực hiện muốn vào miền găng thì bị chặn bởi vòng while do turn # myPid  Một tiến trình ở ngoài miền găng sẽ ngăn cản tiến trình khác vào miền găng b) share int turn = 0; //------------------------------------- int mypid= 0; while (turn != mypid) DoNoThing(); turn =1; // Critical-section; turn =0; *DEKKER’S ALGORITHM //---------------------------------------------- Process_1 Process_2 //---------------------------------- //---------------------------------- p1wantstoenter=true; p2wantstoenter=true; While (p2wantstoenter) While (p1wantstoenter) If (favoredprocess==second) If (favoredprocess==first) { p1wantstoenter=false; { p2wantstoenter=false; While (favoredprocess==second) While (favoredprocess==first)
DoNoThing(); DoNoThing(); p1wantstoenter=true; p2wantstoenter=true; } } CRITICAL-SECTION; CRITICAL-SECTION; favoredprocess=second; favoredprocess=first; p1wantstoenter=false; p2wantstoenter=false; //------------------------------------- //------------------------------------- p1wantstoenter=false; p2wantstoenter=false; favovedprocess=first; { Process_1; Process_2; } Chứng minh rằng thuật toán Dekker thỏa mãn yêu cầu truy xuất đến miền găng. Giải  Các biến p1wantstoenter =true có nghĩa là tiến trình 1 muốn vào miền găng, khi ra khỏi sẽ gán thành false.  Giả sử P1 xử lý trước nên p1wantstoenter =true ->tiến trình 1 sẽ bỏ qua điều kiện vòng while do khi đó p2wantstoenter =false -> P1 vào miền găng.  Trong khi P1 ở trong miền găng thì tiến trình P2 muốn vào miền găng nhưng do điều kiện while p1wantstoenter =true nên P2 phải thực hiện vòng while này. Biến favoredprocess=first làm cho P2 phải chờ trong khi P1 đang ở trong miền găng  Biến favoredprocess=first làm cho điều kiện vòng while đúng nên buộc P2 phải chờ.  Khi P1 ra khỏi miền găng, nó gán biến favoredprocess=second và p1wantstoenter=false. Như vậy tiến trình P2 mới thoát ra khỏi vòng while để vào miền găng. Vậy tính loại trừ lẫn nhau(mutual exclusion) được bảo đảm DEKKER’S ALGORITHM DẠNG 2 Share Boolean wantIn[2] = false; Shrare int favored = 0; Int myPid = 0 ; Int otherPid = 1 – myPid; P1 P2 wantIn[myPid] = true ; wantIn[otherPid] = true ; while (wantIn[otherPid]) while (wantIn[myPid]) { { If (favored == otherPid) If (favored == myPid) { { wantIn[myPid]=false; wantIn[otherPid]=false; while (favored==otherPid) while (favored==myPid)
DoNothing(); DoNothing(); wantIn[myPid]=true; wantIn[otherPid]=true; } } } } //CRITICAL-SECTION //CRITICAL-SECTION Favored = otherPid; Favored = myPid; wantIn[myPid] = false ; wantIn[otherPid] = false ; *PETERSON’S ALGORITHM Shared Boolean wantIn[2]=false; Share int turn =1; Int myPid=0; //for process 0. Set to 1 for process 1 Int otherPid = 1 – myPid; P1 P2 wantIn[myPid] = true ; wantIn[otherPid] = true ; turn = otherPid ; turn = myPid ; while (wantIn[otherPid] && turn == otherPid) while (wantIn[myPid] && turn == myPid) DoNothing(); DoNothing(); //CRITICAL-SECTION //CRITICAL-SECTION wantIn[myPid] = false; wantIn[otherPid] = false; Chứng minh rằng thuật toán Peterson thỏa mãn yêu cầu truy xuất đến miền găng. Giải:
Xét trường hợp tiến trình P1 vào miền găng : wantIn[myPid] = true ; turn =  otherPid Khi đó điều kiện wantIn[otherPid] && turn == otherPid bằng false ->P1 vào  miền găng. Trong khi đó, nếu P2 muốn vào miền găng thì điều kiện while không thỏa, nghĩa là điề kiện bằng true ->làm cho P2 phải chờ cho đến khi P1 ra khỏi miền găng. Xét trường hợp cả hai tiến trình cùng thực hiện , cùng gán wantIn[myPid] =  wantIn[otherPid] = true ; nhưng biến turn sẽ gán myPid hoặc otherPid. Nếu turn=otherPid thì tiến trình P1 phải chờ để cho tiến trình P2 thao tác trên miền găng, ngược lại nếu turn = myPid thì tiến trình P2 phải chờ trong khi tiến trình P1 ở trong miền găng. Vậy thuật toán đảm bảo tính chất Mutual Exclusion  *BAKERY’S ALGORITHM Chứng minh thuật toán Bakery thỏa mãn yêu cầu truy truy xuất miền găng //--------------------------------------------- Shared Boolean choosing[N] =false; Share int number[N] = 0; Int myPid = 0; // for process 0. X for process x Int jj ; Choosing[myPid] = true; Number[myPid] = MAX(number) + 1 ; Choosing[myPid] = false ; For (jj=0 ; jj < N ; jj =jj+1) { While (choosing[jj]) DoNothing(); While (number[jj] != 0 && ((number[jj] < number[myPid]) || (number[jj] == number[myPid] && j < i )) DoNothing(); } //CRITICAL-SECTION Number[myPid] = 0;