Giải đề thi HĐH ngày 20/6/2010 - khoá I91C

Câu 4: Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình---------------Thời điểm đến (ms)-------------CPU-Burst (ms)
---P0--------------------------2------------------------------19
---P1-------------------------14-------------------------------6
---P2-------------------------20-------------------------------7
Dùng thuật giải SJFS có tiếm quyền để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt.
b. Tính thời gian chờ trung bình của các tiến trình.

Giải:
a.
--------------P0--------------P1----------P0---------P2-------
|--|----------------------|----------|------------|------------|
0--2--------------------14---------20----------27----------34

b. Thời gian chờ trung bình là: [(20-14) + (14-14) + (27-20)]/3 = 4.33 (ms)




Câu 5: Một hệ thống có 5 tiến trình với trạng thái tài nguyên như sau:

Process|Allocation|.Max.|Available
...........|A.B.C.D|A.B.C.D|A.B.C.D

....P0....|0.0.1.2|0.0.1.2|1.5.2.0
....P1....|1.0.0.0|1.7.5.0|
....P2....|1.3.5.4|2.3.5.6|
....P3....|0.6.3.2|0.6.5.2|
....P4....|0.0.1.4|0.6.5.6|
Dùng thuật giải Nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có nên đáp ứng yêu cầu (0,4,3,0) của P1?

Giải:
a.
* Xét tại thời điểm T0 mà 3 tiến trình được cấp phát như đề bài, ta có:

.......P[i].......Allocation[i]............Need[i]............Max[i].............Available
.......P0...........0.0.1.2...............0.0.0.0...........0.0.1.2...............1.5.2.0
.......P1...........1.0.0.0...............0.7.5.0...........1.7.5.0
.......P2...........1.3.5.4...............1.0.0.2...........2.3.5.6
.......P3...........0.6.3.2...............0.0.2.0...........0.6.5.2
.......P4...........0.0.1.4...............0.6.4.2...........0.6.5.6
Với: Need[i] = Max[i] - Allocation[i]
Ta có: Need[0] = (0,0,1,2) - (0,0,1,2) = (0,0,0,0)
Need[1] = (1,7,5,0) - (1,0,0,0) = (0,7,5,0)
Need[2] = (2,3,5,6) - (1,3,5,4) = (1,0,0,2)
Need[3] = (0,6,5,2) - (0,6,3,2) = (0,0,2,0)
Need[4] = (0,6,5,6) - (0,0,1,4) = (0,6,4,2)

* Tìm chuỗi an toàn:
......P[i].......Work[i]....>=......Need[i]............Allocation[i].
.......P0.......1.5.2.0.............0.0.0.0..............0.0.1.2
.......P2.......1.5.3.2.............1.0.0.2..............1.3.5.4
.......P3.......2.8.8.6.............0.0.2.0..............0.6.3.2
.......P4.......2.14.11.8..........0.6.4.2..............0.0.1.4
.......P1.......2.14.12.12........0.7.5.0..............1.0.0.0
Chuỗi an toàn tìm được là : {P0, P2,P3,P4,P1}
Vậy tại thời điểm T0 hệ thống ở trạng thái an toàn.

b.Xét yêu cầu của P1 thoả: Request[1] <= Need[1] vì : (0,4,3,0) <= (0,7,5,0)
nhưng không thoả: Request[1] <= Available
Vậy không thể đáp ứng yêu cầu của P1.


Đây là bài giải của mình, không biết có trùng với đáp án của các bạn không? Các bạn bắt tay vào giải đề cùng mình nhé. Thanks.

09H1010040_PhuongHuy đã viết:Câu 4: Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình---------------Thời điểm đến (ms)-------------CPU-Burst (ms)
---P0--------------------------2------------------------------19
---P1-------------------------14-------------------------------6
---P2-------------------------20-------------------------------7
Dùng thuật giải SJFS có tiếm quyền để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt.
b. Tính thời gian chờ trung bình của các tiến trình.

Giải:
a.
--------------P0--------------P1----------P0---------P2-------
|--|----------------------|----------|------------|------------|
0--2--------------------14---------20----------27----------34

b. Thời gian chờ trung bình là: [(20-14) + (14-14) + (27-20)]/3 = 4.33 (ms)




Câu 5: Một hệ thống có 5 tiến trình với trạng thái tài nguyên như sau:

Process|Allocation|.Max.|Available
...........|A.B.C.D|A.B.C.D|A.B.C.D

....P0....|0.0.1.2|0.0.1.2|1.5.2.0
....P1....|1.0.0.0|1.7.5.0|
....P2....|1.3.5.4|2.3.5.6|
....P3....|0.6.3.2|0.6.5.2|
....P4....|0.0.1.4|0.6.5.6|
Dùng thuật giải Nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có nên đáp ứng yêu cầu (0,4,3,0) của P1?

Giải:
a.
* Xét tại thời điểm T0 mà 3 tiến trình được cấp phát như đề bài, ta có:

.......P[i].......Allocation[i]............Need[i]............Max[i].............Available
.......P0...........0.0.1.2...............0.0.0.0...........0.0.1.2...............1.5.2.0
.......P1...........1.0.0.0...............0.7.5.0...........1.7.5.0
.......P2...........1.3.5.4...............1.0.0.2...........2.3.5.6
.......P3...........0.6.3.2...............0.0.2.0...........0.6.5.2
.......P4...........0.0.1.4...............0.6.4.2...........0.6.5.6
Với: Need[i] = Max[i] - Allocation[i]
Ta có: Need[0] = (0,0,1,2) - (0,0,1,2) = (0,0,0,0)
Need[1] = (1,7,5,0) - (1,0,0,0) = (0,7,5,0)
Need[2] = (2,3,5,6) - (1,3,5,4) = (1,0,0,2)
Need[3] = (0,6,5,2) - (0,6,3,2) = (0,0,2,0)
Need[4] = (0,6,5,6) - (0,0,1,4) = (0,6,4,2)

* Tìm chuỗi an toàn:
......P[i].......Work[i]....>=......Need[i]............Allocation[i].
.......P0.......1.5.2.0.............0.0.0.0..............0.0.1.2
.......P2.......1.5.3.2.............1.0.0.2..............1.3.5.4
.......P3.......2.8.8.6.............0.0.2.0..............0.6.3.2
.......P4.......2.14.11.8..........0.6.4.2..............0.0.1.4
.......P1.......2.14.12.12........0.7.5.0..............1.0.0.0
Chuỗi an toàn tìm được là : {P0, P2,P3,P4,P1}
Vậy tại thời điểm T0 hệ thống ở trạng thái an toàn.

b.Xét yêu cầu của P1 thoả: Request[1] <= Need[1] vì : (0,4,3,0) <= (0,7,5,0)
nhưng không thoả: Request[1] <= Available
Vậy không thể đáp ứng yêu cầu của P1.


Đây là bài giải của mình, không biết có trùng với đáp án của các bạn không? Các bạn bắt tay vào giải đề cùng mình nhé. Thanks.

Giống mình gê!