HĐH - Ôn Tập Cuối Kỳ - Part 3 (Bài Tập) | Facebook

FacebookTham gia hoặc đăng nhập Facebook   Email hoặc điện thoạiMật khẩuQuên tài khoản?Đăng nhậpBạn có muốn tham gia Facebook không?Đăng kýĐăng kýHĐH - Ôn tập cuối kỳ - Part 3 (Bài tập)Lưu Biêu Nghị·Thứ Tư, 19 tháng 6, 2019·Nhóm công khai#StudyWithMe #HĐHChào các bạn !Sau phần lý thuyết, hôm nay chúng mình sẽ cùng ôn lại một số bài tập nhé !Bài tập chương 5.Câu 1 : Xét giải pháp phần mềm do Dekker đề nghị để tổ chức truy xuất độc quyền cho 2 tiến trình. Hai tiến trình P0 và P1 chia sẻ các biến sau :

• Biến flag : Là một Array [0…1] với kiểu dữ liệu boolean (khởi tạo tất cả giá trị đều là false).
• Biến turn : Nhận 2 giá trị 0 hoặc 1 (thể hiện lượt chạy của process 1 hoặc 2).

Xét 2 tiến trình kí hiệu là i và j. Cấu trúc một tiến trình Pi (hiển nhiên i có thể nhận giá trị 0 hoặc 1, và j nhận giá trị còn lại) như sau :

Cấu trúc chương trình.

Giải pháp có thoả 3 yêu cầu trong việc giải quyết tranh chấp không ?Câu 2 : Xét giải pháp đồng bộ hoá sau :

Giải pháp đồng bộ hoá.

Giải pháp trên có thoả yêu cầu độc quyền truy xuất (Mutual Exclusion) không ?Câu 3 : Xét hai tiến trình sau :

Tiến trình A và B.

a. Đồng bộ hoá xử lý của 2 tiến trình trên, sử dụng 2 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, ban đầu giá trị của na và nb đều bằng 0.b. Nếu giảm điều kiện chỉ có là na <= nb + 10, giải pháp của bạn sẽ được 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à B cùng thực hiện ?Câu 4 : Xét 2 tiến trình xử lý đoạn chương trình sau :

Tiến trình P1 và P2.

Đồng bộ hoá hoạt động của 2 tiến trình này sao cho cả A1 và B1 đều hoàn tất trước khi A2 và B2 bắt đầu.Câu 5 : Cho tiến trình có đoạn chương trình sau :

Tiến trình P1 và P2.

Đồng bộ hoá hoạt động của 2 tiến trình này sao cho 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.Câu 6 :Một biến X được chia sẻ bởi hai tiến trình cùng thực hiện đoạn code sau:do{X = 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. Sửa lại đoạn code trên để giá trị của X không vượt quá 20.Câu 7: Một hãng sản xuất xe đạp có các bộ phận sản xuất hoạt động song song:- Bộ phận sản xuất khung xevoid SXKhung(){printf(“San xuat khung”);}- Bộ phận sản xuất bánh xevoid SXBanhXe(){printf(“San xuat banh xe”);}- Bộ phận lắp ráp: Sau khi có đủ 1 khung và 2 bánh thì tiến hành lắp ráp.void LapRapXe(){printf(“Lap rap xe”);}Hãy đồng bộ hoạt động của các bộ phận trên theo nguyên tắc: tại mỗi thời điểm chỉ cho phép sản xuất 1 khung xe, cần chờ đủ 2 bánh xe để gắn vào khung xe hiện tại này trước khi sản xuất một khung xe khác.Bài tập chương 6.Bài 1 : Cho 1 hệ thống có 4 tiến trình P1 đến P4 và 3 loại tài nguyên R1 (3), R2(2), R3(2). P1 giữ 1 R1 và yêu cầu 1 R2, P2 giữ 2 R2 và yêu cầu 1 R1 và 1 R3, P3 giữ 1 R1 và yêu cầu 1 R2, P4 giữ 2 R3 và yêu cầu 1 R1.

• Vẽ đồ thị tài nguyên cho hệ thống này ?
• Deadlock ?
• Tìm chuỗi an toàn (nếu có) ?

Bài 2 :

Yêu cầu tài nguyên của các process.

Sử dụng thuật toán Banker :

• Tìm Need ?
• Hệ thống có an toàn không ?
• Nếu P1 yêu cầu (0,4,2,0) thì có thể cấp phát cho nó ngay không ?

Bài 3 : Sử dụng thuật toán Banker xem các trạng thái sau có an toàn hay không ? Nếu có thì đưa ra chuỗi thực thi an toàn, nếu không thì nêu rõ lý do không an toàn ?

Bài 3.

a. Available = (0,3,0,1).b. Available = (1,0,0,2).Bài 4 : Trả lời các câu hỏi sau sử dụng giải thuật Banker.

Bài 4.

a. Hệ thống có an toàn không ? Đưa ra chuỗi an toàn nếu có ?b. Nếu P1 yêu cầu (1,1,0,0) thì có thể cấp phát cho nó ngay không ? Bài tập chương 7.Bài 1 : Xét một không gian địa chỉ có 12 trang, mỗi trang có kích thước 2K, ánh xạ vào bộ nhớ vật lý có 32 khung trang.a. Địa chỉ logic gồm bao nhiêu bit ?b. Địa chỉ physic gồm bao nhiêu bit ?c. Bảng trang có bao nhiêu mục ? Mỗi mục trong bảng trang cần bao nhiêu bit ?Bài 2 : Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính.a. Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200ns thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ?b. Nếu sử dụng TLBs với hit-ratio là 75%, thời gian để tìm tròn TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống.Bài 3 : Xét bảng phân đoạn trong hình :

Bảng phân đoạn bài 3.

Tính địa chỉ vật lý tương ứng với các địa chỉ logic sau đây :a. 0,430.b. 1,10.c. 2,500.d. 3,400.e. 4,112.Bài 4 : Xét một không gian có bộ nhớ luận lý có 15 trang, mỗi trang có 1024 từ, mỗi từ là 2 byte được ánh xạ vào bộ nhớ vật lý có 32 trang, trả lời các câu hỏi sau :a. Địa chỉ bộ nhớ vật lý có bao nhiêu bit ?b. Địa chỉ bộ nhớ luận lý có bao nhiêu bit ?c. Có bao nhiêu mục trong bảng phân trang ? Mỗi mục chứa bao nhiêu bit ?Bài tập chương 8.Bài 1 : Xét chuỗi truy xuất bộ nhớ sau :1, 2, 3, 4, 3, 5, 1, 6, 2, 1, 2, 3, 7, 5, 3, 2, 1, 2, 3, 6.Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay thế sau đây, biết có 4 khung trang.a. LRU.b. FIFO.c. Chiến lược tối ưu (OPT).Bài 2 : Một máy tính 32-bit địa chỉ, sử dụng một bảng trang 2 cấp. Địa chỉ ảo được phân bổ như sau : 9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2, và còn lại cho offset. Cho biết kích thước một trang trong hệ thống và địa chỉ ảo có bao nhiêu trang ?Bài 3 : Giả sử địa chỉ ảo 32-bit được phân tách thành 4 trường a,b,c,d. 3 trường đầu tiên được dùng cho bảng trang 3 cấp, trường thứ 4 dành cho offset. Số lượng trang có phụ thuộc vào kích thước của cả 4 trường này không ? Nếu không, những trường nào ảnh hưởng đến số lượng trang, những trường nào không ảnh hưởng ?================================================================Bài giải:Chương 5:Câu 1: *Cơ sở lý thuyết: 3 tính chất của một giải thuật giải quyết tranh chấp:1) Loại trừ tương hỗ (Mutual exclusion): Khi một tiến đang thực thi trong vùng tranh chấp của nó thì không có process Q nào khác đang thực thi trong CS của Q.2) Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng 3) Bounded waiting: Mỗi process chỉ phải chờ để được vào vùng tranh chấp trong một khoảng thời gian có hạn định nào đó. Không xảy ra tình trạng đói tài nguyên.Giải:- Quan sát trên giải thuật:

Giải thuật.

- Nhận thấy: nếu một tiến trình Pj muốn vào vùng tranh chấp, trong khi tiến trình Pi cũng đang muôn vào vùng tranh chấp: =>dựa vài biến turn để xác nhận Pi hay Pj được tiến hành, do turn chỉ có một giá trị cùng một lúc nên chỉ có một trong 2 được vào vùng tranh chấp của nó => thoả mãn tính chất 1.- Không có bất kỳ động thái ngăn cản tiến trình Pj vào miền găng khi Pi đang không ở trong miền găng (như đổi turn từ j thành i, đổi flag[j] thành false) => thoả mãn tính chất 2.- Khi Pi hoàn thành thì sẽ nhường lượt cho Pj, nếu Pi bị tắc thì Pj sẽ tiến và nhường lượt cho Pi => thoả mãn điều kiện 3.Bài 2: Ta thấy code này có đoạn j = 1 – i => đề chỉ đang nói tới xét 2 tiê trình P1 và P0 vì khi i = 0 thì j = 1 và ngược lại.- Giải thuật này không thoả mãn:Xét tình huống khi flag[0] =1; turn =0; lúc này P0 vào CS, Nếu lúc đó flag[1] = 1, P1 có thể gán turn = 1 và vào luôn CS (2 tiến trình cùng vào CS một lúc).Câu 3:

Đề bài câu 3.

a) nb <= na <= nb + 10.Cách giải: Chúng ta phải làm 2 việc với 2 semaphore đã cho: đảm bảo na >= nb và na <= nb + 10, như vậy nghĩa là khi na = nb thì tiến trình B bị block cho tới khi A tiến hành được ít nhất một lần, cũng như khi na = nb + 10 thì A bị block cho tới khi B tiến hành được ít nhất một lần.

Source bài giải.

c) Đúng, vì có thể có nhiều tiến trình loại A hoặc loại B cùng thực hiện nhưng chỉ có 2 biến Semaphore toàn cục mà chúng sẽ thao tác (đối với câu b là 1 Semaphore).Câu 4:

Source bài giải.

Câu 5:

Source bài giải.

Câu 6: do{X = X +1;if ( X == 20) X = 0;}while ( TRUE );Do X được chia sẻ chung ở cả hai tiến trình và chỉ bị reset khi X == 20 nên X có thể vượt quá 20 khi:- Có một lý do trong máy đột ngột khiến tiến trình 2 dừng lại. Sau đó tại tiến trình 1, khi X = 19 thì tiến trình 2 được release đúng ngay đoạn X = X + 1, và cộng dồn với X = 20 sau lệnh X = X + 1 của tiến trình 1 dẫn tới X vượt quá 20 và còn bị cộng tới vô cùng.*Đây là code demo với cách giả định P2 bị crash và release bằng một lệnh sleep nhỏ, kết quả của X sẽ vượt quá 20 trong tích tắ

Code demo (1).

Code demo (2).

- Để giải quyết vấn đề này ( làm cho X luôn nhỏ hơn 20 ) thì ta có thẻ giải quyết bằng cách đưa 2 tiến trình về làm 1, tức là làm cho cùng một lúc chỉ có một trong hai tiến trình được chạy bằng một biến Semaphore khởi tạo bằng 1.Câu 7:Semaphore_Khung = 0;Semaphore_Banh = 0,;Semaphore_LapRap = 1;Process Khung:while(true){wait(Semaphore_LapRap);printf(“San xuat khung”);signal(Semaphore_Khung);}}Process BanhXe:while(true){printf(“San xuat banh xe”);signal(Semaphore_Banh);}Process LapRapXe:while(true){down(Semaphore_Khung);down(Semaphore_Banh);down(Semaphore_Banh);printf(“Lap rap xe”);signal(Semaphore_LapRap);}Chương 6:Câu 1 : Cho 1 hệ thống có 4 tiến trình P1 đến P4 và 3 loại tài nguyên R1 (3), R2(2), R3(2). P1 giữ 1 R1 và yêu cầu 1 R2, P2 giữ 2 R2 và yêu cầu 1 R1 và 1 R3, P3 giữ 1 R1 và yêu cầu 1 R2, P4 giữ 2 R3 và yêu cầu 1 R1.

• Vẽ đồ thị tài nguyên cho hệ thống này ?
• Deadlock ?
• Tìm chuỗi an toàn (nếu có) ?

a)

Đáp án câu a.

b)

Bảng yêu cầu tài nguyên của các tiến trình.

c) Chuỗi an toàn: P4 -> P2 -> P3 -> P1Câu 2:

Đề bài câu 2.

Sử dụng thuật toán Banker :

• Tìm Need ?
• Hệ thống có an toàn không ?
• Nếu P1 yêu cầu (0,4,2,0) thì có thể cấp phát cho nó ngay không ?

Bảng yêu cầu tài nguyên.

=> Chuỗi an toàn: P0 -> P2 -> P3 -> P4 -> P1=> Hệ thống an toàn.Nếu P1 yêu cầu (0,4,2,0):Ta có: Request1 <= Need1 Request1 <= AvailableGiả sử cấp phát tài nguyên cho P1 thành công, ta có:Available = Available – Request1 = (1,1,0,0)Need1 = Need1 - Request1 = (0,3,3,0)Allcation­1 = Allocation1 + Request1 = (1,4,2,0)

Bảng yêu cầu tài nguyên.

Sau khị cấp phát ta có chuỗi an toàn là: P0 -> P2 -> P1 -> P4 -> P3 => Có thể cấp phát được.Câu 3 : Kiểm tra xem các trạng thái sau có an toàn hay không ? Nếu có thì đưa ra chuỗi thực thi an toàn, nếu không thì nêu rõ lý do không an toàn ?

Đề câu 3.

a. Available = (0,3,0,1).b. Available = (1,0,0,2).a)

Đáp án câu a.

=> Trạng thái không an toàn do không tìm được giá trị Needi nhỏ hơn Available = (5,11,4,2) b)

Đáp án câu b.

=> Chuỗi an toàn: P1 -> P2 -> P3 -> P4 -> P0=> Trạng thái an toànBài 4 : Trả lời các câu hỏi sau sử dụng giải thuật Banker.a. Hệ thống có an toàn không ? Đưa ra chuỗi an toàn nếu có ?b. Nếu P1 yêu cầu (1,1,0,0) thì có thể cấp phát cho nó ngay không ?

Đề bài 4.

a)

Đáp án câu a.

Chuỗi an toàn: P0 -> P3 -> P4 -> P1 -> P2 b)Ta có: Request1 <= Need1Request1 <= AvailableGiả sử cấp phát tài nguyên cho P1 thành công:Available = Available – Request1 = (2,2,2,1)Need1 = Need1 – Request1 = (1,0,3,1)Allocation1 = Allocation1 + Request1 = (4,2,2,1)

Đáp án câu b.

Chuỗi an toàn: P0 -> P3 -> P4 -> P1 -> P2Chương 7:Câu 1 : Xét một không gian địa chỉ có 12 trang, mỗi trang có kích thước 2K, ánh xạ vào bộ nhớ vật lý có 32 khung trang.a. Địa chỉ logic gồm bao nhiêu bit ?b. Địa chỉ physic gồm bao nhiêu bit ?c. Bảng trang có bao nhiêu mục ? Mỗi mục trong bảng trang cần bao nhiêu bit ?Giải:a) Ta có: 12 <= 24 => cần 4 bit để biểu diễn số trang.2K <= 211 => cần 11 bit để biễu diễn độ dời trong 1 trangð Cần 15 bit để biểu diễn địa chỉ logicb) Ta có: 32 <= 25 => cần 5 bit để biểu diễn số khung trangð Cần 16 bit để biểu diễn c) Bảng trang có 16 mục, mỗi mục 5 bit.Bài 2 : Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính.a. Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200ns thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ?b.Nếu sử dụng TLBs với hit-ratio là 75%, thời gian để tìm tròn TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống.Giải:a) Thời gian truy xuất trong bộ nhớ trong hệ thống đã cho: 2x200 = 400 nsb) Nếu sử dụng TLBs với hit-ratio là 75%:(200 + 0) x 0.75 + (200 + 200 + 0) x 0.25 = 250Bài 3 : Xét bảng phân đoạn trong hình :

Segment table.

Tính địa chỉ vật lý tương ứng với các địa chỉ logic sau đây :a) 0,430. => 219 + 430 = 649 b) 1,10. => 2300 + 10 = 2310c) 2,500. => Không hợp lệd) 3,400. => 1327 + 400 = 1727e) 4,112. => Không hợp lệBài 4 : Xét một không gian có bộ nhớ luận lý có 15 trang, mỗi trang có 1024 từ, mỗi từ là 2 byte được ánh xạ vào bộ nhớ vật lý có 32 khung trang, trả lời các câu hỏi sau :a) Địa chỉ bộ nhớ vật lý có bao nhiêu bit ?b) Địa chỉ bộ nhớ luận lý có bao nhiêu bit ?c) Có bao nhiêu mục trong bảng phân trang ? Mỗi mục chứa bao nhiêu bit ?Giải:a) Ta có: 32 <= 25 => cần 5 bit biểu diễn số khung trang,1024 WORD = 2048 bytes <= 211 => cần 11 bit biễu diễn độ dờiCần 16 bit để biểu diễn bộ nhớ vật lý.b) Ta có: 15 <= 24 => cần 4 bit để biểu diễn số trang.=> cần 15 bit để biểu diễn địa chỉ logicc)Có 16 mục trong bảng phân trang, mỗi mục 5 bit.Chương 8:Bài 1 : Xét chuỗi truy xuất bộ nhớ sau :1, 2, 3, 4, 3, 5, 1, 6, 2, 1, 2, 3, 7, 5, 3, 2, 1, 2, 3, 6.Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay thế sau đây, biết có 4 khung trang.a. LRU.b. FIFO.c. Chiến lược tối ưu (OPT).a)

Đáp án câu a.

b)

Đáp án câu b.

=> Có 15 lỗi trangc)

Đáp án câu c.

=> Có 9 lỗi trang.Bài 3 : Giả sử địa chỉ ảo 32-bit được phân tách thành 4 trường a,b,c,d. 3 trường đầu tiên được dùng cho bảng trang 3 cấp, trường thứ 4 dành cho offset. Số lượng trang có phụ thuộc vào kích thước của cả 4 trường này không ? Nếu không, những trường nào ảnh hưởng đến số lượng trang, những trường nào không ảnh hưởng ?Giải:Số lượng trang chỉ phụ thuộc vào kích thước trường d và bằng: 2(32 – d)Các trường a, b, c có thể thay đổi kích thước nhưng vẫn không làm thay đổi số trang nếu trường d không thay đổi.Bài 4: Giả sử có một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu. Bảng trang được lưu trữ trong các thanh ghi. Để xử lý một lỗi trang tốn 8 miliseconds nếu có sẵn một khung trang trống, hoặc trang bị thay thế không bị sửa đổi nội dung, và tốn 20 miliseconds nếu trang bị thay thế bị sửa đổi nội dung. Mỗi truy xuất bộ nhớ tốn 100 nanoseconds. Giả sử trang bị thay thế có xác suất bị sửa đổi là 70%.Tỷ lệ phát sinh lỗi trang phải là bao nhiêu để có thể duy trì thời gian truy xuất bộ nhớ ( effective acess time) không vượt quá 200 nanoseconds ?Gọi tỉ lệ xảy ra lỗi trang cần tìm là rDo bảng trang được lưu trữ trong các thanh ghi => thời gian truy xuất vào bàng trang không đáng kể.=> Thời gian truy xuất bộ nhớ: 100 nanoseconds– Thời gian trung bình để xử lý lỗi trang: 0,3 * 8 + 0,7 * 20 = 16.4 miliseconds– Theo đề: EAT <= 200 nanoseconds=> EAT = 100 + r*16.4 <= 200 => r <= (200-100)/16,4 = 0,609%Bài giảiđược thực hiện bởi : Nguyễn Văn Đông.Phù, đây là bài viết cuối cùng nằm trong chuỗi bài StudyWithMe HĐH rồi. Bài này tụi mình post chậm hơn lịch dự kiến một ngày để có thời gian chuẩn bị kỹ hơn cho các bạn.Cảm ơn các bạn đã theo dõi chuỗi bài viết StudyWithMe. Hy vọng sẽ được tiếp tục gặp lại các bạn ở các hoạt động tiếp theo của BHT !Chúc các bạn thi thật tốt !Nếu có bất kỳ thắc mắc hoặc sai sót nào, các bạn có thể góp ý tại comment bên dưới nhé !Xem ôn tập cuối kỳ - Lý thuyết (part 1) : http://bit.ly/2KsBhE4Xem ôn tập cuối kỳ - Lý thuyết (part 2) : http://bit.ly/2FnJt4C

• Tiếng Việt
• English (UK)
• 中文(台灣)
• 한국어
• 日本語
• Français (France)
• ภาษาไทย
• Español
• Português (Brasil)
• Deutsch
• Italiano

• Đăng ký
• Đăng nhập
• Messenger
• Facebook Lite
• Video
• Địa điểm
• Trò chơi
• Marketplace
• Meta Pay
• Cửa hàng trên Meta
• Meta Quest
• Meta AI
• Instagram
• Threads
• Chiến dịch gây quỹ
• Dịch vụ
• Trung tâm thông tin bỏ phiếu
• Chính sách quyền riêng tư
• Trung tâm quyền riêng tư
• Nhóm
• Giới thiệu
• Tạo quảng cáo
• Tạo Trang
• Nhà phát triển
• Tuyển dụng
• Cookie
• Lựa chọn quảng cáo
• Điều khoản
• Trợ giúp
• Tải thông tin liên hệ lên & đối tượng không phải người dùng
• Cài đặt
• Nhật ký hoạt động

Meta © 2024