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

Trang chủ » Bài Tập Semaphore Hệ điều Hành Có Lời Giải » BÀI TẬP THỰC HÀNH VỀ HỆ ĐIỀU HÀNH - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Hệ điều hành Windows
  • Hệ điều hành Linux
  • Hệ điều hành MAC
  • Hệ điều hành Ubuntu
  • Hệ điều hành iOS
  • HOT
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • TL.01: Bộ Tiểu Luận Triết Học
    • EXAM.04: Bộ 290+ Đề Thi Vào Lớp 10...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • EXAM.06: Bộ 240 Đề Thi Thử THPT Quốc...
    EXAM.05: Bộ 300+ Đề Thi Thử THPT Quốc Gia...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Hệ điều hành 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 971 lượt xem 113 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.

AMBIENT/ Chủ đề:
  • thủ thuật máy tính
  • thủ thuật cài đặt
  • hệ điều hành
  • bài tập hệ điều hành
  • tài liệu hệ điều hành

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

Đă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

  1. 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())
  2. 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();
  3. // 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 }
  4. 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
  5. 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
  6. 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 (); } } -------------------------------------------
  7. 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
  8. 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)
  9. 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)
  10. 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:
  11. 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;
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Thực hành điều khiển lập trình PLC - Mạng PLC

    pdf 47 p | 1934 | 1171

  • Bài tập cấu trúc dữ liệu và giải thuật - Bài thực hành số 1

    pdf 13 p | 1370 | 170

  • Bài tập Thực hành môn Tin học nâng cao - Trường ĐH Tài Chính - Marketing

    pdf 18 p | 1167 | 147

  • Bài tập học thực hành JavaScript

    pdf 22 p | 422 | 98

  • Bài tập thực hành môn Phân tích thiết kế hệ thống thông tin

    doc 6 p | 1172 | 62

  • Giáo án bài tập thực hành: Lập trình hướng đối tượng

    doc 45 p | 355 | 40

  • Bài tập thực hành về C # - Bài 3,4,5

    doc 37 p | 239 | 39

  • Bài tập thực hành User Account, Group

    pdf 1 p | 156 | 19

  • Hệ điều hành Linux - Bài 4: Giao tiếp giữa các tiến trình trên Linux

    pdf 5 p | 229 | 14

  • Bài tập thực hành cơ sở dữ liệu: Phần 1

    pdf 66 p | 87 | 12

  • Bài tập thực thành số 1 môn Hệ điều hành

    doc 5 p | 37 | 8

  • Bài giảng Thực hành tin ứng dụng - GV. Nguyễn Trung Thuận

    pdf 68 p | 30 | 7

  • Bài tập thực hành cơ sở dữ liệu: Phần 2

    pdf 96 p | 51 | 6

  • Hệ điều hành Linux - Bài 6a: Lập trình đa tuyến(multi –thread)

    pdf 9 p | 124 | 4

  • Bài tập thực hành tin học đại cương: Phần 2

    pdf 67 p | 85 | 3

  • Tự luyện CCNA trên máy tính cá nhân: Hướng dẫn thực hành - Phần 1

    pdf 172 p | 7 | 3

  • Sách giao bài tập Tin học đại cương - Th.S Nguyễn Ngọc Lan

    pdf 57 p | 1 | 1

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » Bài Tập Semaphore Hệ điều Hành Có Lời Giải