He-dieu-hanh pham-dang-hai bai-tap-he-dieu-hanh – [cuuduongthancong – 1 MOT SO BAI TAP CAN CHU Y !!! – StuDocu

1

MOT SO BAI TAP CAN CHU Y !!!

Round-Robin, SJFS, Bộ nhớ ảo, Bảng FAT, Thuật giải Nhà băng, Sản xuất-
Tiêu thụ (semFull-semEmpty), Dining-Philosopers (deadlock, không
deadlock).

Thuật giải Nhà băng …………………………………………………………………………………. 1 Round-Robin, SJFS, ………………………………………………………………………………… 4 bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic …………………………………… 7 bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic có trường hợp không hợp lệ …………………………………………………………………………………………………. 9 Bảng FAT, …………………………………………………………………………………………….. 11 RAG …………………………………………………………………………………………………….. 13 Bộ nhớ ảo …………………………………………………………………………………………….. 15 Sản xuất-Tiêu thụ ( semFull-semEmpty ), ……………………………………………………. 19 Dining-Philosopers ( deadlock, không deadlock ). ………………………………………… 22

BÀI TẬP HỆ ĐIỀU HÀNH

Thuật giải Nhà băng

Câu 1:
Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp
phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allocation = (1, 0, 1) và
Max = (1, 2, 2):
Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn. (1 điểm)
b. Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của của
P3? (1 điểm)
Giải:
a. Xét tại thời điểm Ti mà 3 tiến trình được cấp phát như đề bài ta có:

Với : Need [ i ] = Max [ i ] – Allocation [ i ] và Available = 3 – ( 1 + 0 + 1 ) = 1 Tìm chuỗi bảo đảm an toàn :Vậy tại thời gian T0 sống sót chuỗi bảo đảm an toàn { P1, P2, P3 }. Suy ra, mạng lưới hệ thống tại thời gian Ti ở trạng thái an toàn .

2

b. Ta thấy, nhu yếu thêm 1 ổ nữa của P3 thoả những điều kiện kèm theo : o Request3 < = Need3 và Request1 < = Available o Hơn nữa việc cấp phép thêm 1 ổ nữa cho P3 thì mạng lưới hệ thống vẫn ở trạng thái an toàn vì sống sót chuỗi bảo đảm an toàn { P1, P3, P2 } trong khi tài nguyên trong mạng lưới hệ thống không còn nữa. Thật vậy :Do vậy ta hoàn toàn có thể cấp thêm cho nhu yếu xin thêm 1 của P3 tại thời gian này .

Câu 2
Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài
nguyên tại thời điểm Ti thể hiện bằng các véc-tơ Allocation=(0, 2, 1) và Max=(2,
2, 2).
Dùng thuật giải Nhà băng để:
a. Chứng minh trạng thái này an toàn (1,0 điểm)
b. Xác định có đáp ứng được hay không yêu cầu xin thêm 1 ổ nữa của P2 (1,
điểm)

Trả lời:
a. Chứng minh trạng thái tại thời điểm Ti an toàn :

• Tính Need = Max – Allocation = (2, 0, 1)
• Tính Available=3-(0+2+1)=
• Theo thuật giải Nhà băng, tìm được 2 chuỗi an toàn là:

Do tồn tại ít nhất 1 chuỗi an toàn (chuỗi nào cũng được), trạng thái hệ thống tại
thời điểm Ti là an toàn.
b. Xác định có đáp ứng được hay không yêu cầu xin thêm 1 ổ nữa của P2 :
Không được vì:

• Need 2 =(2-2)=0, nghĩa là đã hết hạn mức ấn định cho P2.
• Mặt khác, Available=0, nghĩa là hệ không còn ổ băng nào.

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

4

Round-Robin, SJFS,

Câu 2
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 )

P

3

37

P

10

20

P

24

14

Dùng thuật giải Round-Robin với thời lượng 10 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm)

Trả lời:
a. Thể hiện bằng biểu đồ Gantt :

b. Thời gian chờ trung bình của các tiến trình :
(34+13+29)/3 = 76/3 = 25,3 ms
Câu 4

Một mạng lưới hệ thống có 3 tiến trình với thời gian đến và thời hạn sử dụng CPU như sau :Tiến trình Thời điểm đến ( ms )CPU-Burst ( ms )

P1 5 47

5

P

23

15

P

45

28

Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để điều phối CPU :a. Thể hiện bằng biểu đồ Gantt ( 0,5 điểm )b. Tính thời hạn chờ trung bình của những tiến trình ( 0,5 điểm )

Trả lời:

a. Thể hiện bằng biểu đồ Gantt :b. Tính thời hạn chờ trung bình của những tiến trình :

• Thời gian chờ của các tiến trình:

P1 = 35 ms

P2 = 2 ms

P3 = 22 ms

• Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

7

bài tập phân đoạn, tính địa chỉ vật lý cho địa chỉ logic

sau khi khám phá về bài tập này, mình post lên cho mọi người cùng trao đổi

GIẢI

1. Vẽ vùng bộ nhớ Vật lý dạng các đoạn segment
   Từ bảng dữ liệu đề bài

Ta vẽ được vùng bộ nhớ vật lý như sau :

8

Các bạn nhìn vào hình mình đã hướng dẫn cách tính và cách vẽ, các bạn chú ý
phần màu chữ mình sử dụng để nhận ra dễ hơn.
Với segment 0 : ta có

• Địa chỉ vật lý cơ sở (basic) là 300
• Limit là 700
  ==> địa chỉ vật lý của segment 0 là từ 300 – > 1000
  Với segment 1 :
• Địa chỉ vật lý cơ sở (basic) là 1200, nên ta sẽ vẽ bắt đầu từ 1200, như vậy từ
  1000->1200 là trống, không có segment nào
• Limit là 500
  ==> địa chỉ vật lý của segment 1 là từ 1200 – > 1700

và segment 2 các bạn tính tương tự

2. Cách tính địa chỉ logic

10

a. 0430 b. 1010 c. 2500 d. 3400 e. 4112 giảiTính địa chỉ vật lý

• Với dữ liệu đề bài cho là (0,430) = 219 +430 = 649 ( hợp lệ) Vì nó nằm trong
  đoạn Segment 0.
• (1,010) = 2300+ 10 = 2310 (hợp lệ)
• (2,500) = 90 + 500 = 1400 (không hợp lệ)
• (3,400) = 1327+ 400 = 1727 (hợp lệ)
• (4,112) = 1952 + 112 = 2064 (không hợp lệ)

=>Với các địa chỉ logic (0,430); (1,010); (1,500); (3,400); (4,112) ta có các địa
chỉ vật lý tương ứng là 649; 2310; không hợp lệ;1727; không hợp lệ.

11

Bảng FAT,

Trên một hệ tập tin FAT32, tập tin Lớp HC08TH2 có nội dung trải trên
các liên cung 5, 6, 9, 10; trong khi Icon1 chỉ cần liên cung 8. Hãy thể
hiện bằng hình vẽ cấu trúc bảng FAT và các Directory Entry.
Giải:

Cần đến 2 Directory Entry cho Lớp HC08TH2

2. j p g A 0 C
   K

0

1 Lớp A 0

C

K H C 0 8 T 0

H

2

L

o p H C 0 ~ 1 A

N

T S

Creation timeLast acc UppLast write Low Size

Ghi chú: Lớp gồm 5 ký tự Lowps.
H C 0 8 T có 5 ký tự + 1 ký tự khoảng trắng ( _ ) phía trước là 6.

jpg

File Lớp HC08TH2

Bytes

13

RAG

Một hệ thống có 1 máy in laser và 1 ổ băng từ. Hai tiến trình P1 và P2 đang
vận hành với trạng thái cấp phát tài nguyên như sau:

Hãy : a. Thể hiện bằng RAG b. Xác định và lý giải trạng thái này. Giải : a. Đồ thị cấp phép tài nguyên RAG :b. Trạng thái này là trạng thái Deadlock. vì mỗi tài nguyên chỉ có một phiên bản và sống sót quy trình hay vòng tròn khép kín những nhu yếu tài nguyên .

16

Với đề bài và cách giải trên thì mình xin làm và lý giải theo cách hiểu của mình Bạn nào có cách lý giải rõ hơn, đúng mực hơn thì bổ trợ nhé

• Hình 1 : Logical Memory
• Hình 2 : Page table
• Hình 3 : Physical memory

17

• Hình 4: Backstore

19

Sản xuất-Tiêu thụ (semFull-semEmpty),

Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 2
đèn hiệu semFull và semEmpty.
Giải:
Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường
được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai
quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến
semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm
và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số
khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới
giá trị n ; biến semaphore full được khởi tạo tới giá trị 0.

• Dữ liệu chia sẻ:
  SEMAPHORE full, empty, mutex;
• Khởi tạo:
  full = 0;

20

empty = BUFFER_SIZE;
mutex = 1;

Câu 2 (1 điểm)

Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 3 đèn hiệu semFull, semEmpty và Mutex .Trả lời :

• Tiến trình sản xuất ( Producer ) tạo ra dòng thông tin để tiến trình tiêu thụ ( Consumer ) sử dụng .
• Ví dụ : Compiler và Assembler vừa là nhà phân phối vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor .
• Phát biểu bài toán : Bộ nhớ đệm Buffer gồm có 1 số ít hữu hạn những khoang chứa ( Items ). Producer lần lượt đưa những mẫu sản phẩm S1, S2, .. ào những khoang của Buffer. Consumer lấy mẫu sản phẩm ra theo đúng thứ tự. Công việc của những tiến trình phải đồng điệu với nhau : không đưa ra loại sản phẩm khi hết chỗ trống, không lấy được mẫu sản phẩm khi chưa có .

out i

n

Buffer xoay vòng

while (1)
{
wait(full)
wait(mutex);

nullnull

nextC = get_buffer_item(out);
…
signal(mutex);
signal(empty);
…
consume_item ( nextC );
…
}

while (1)
{
…
nextP = new_item();
…
wait(empty);
wait(mutex);
…
insert_to_buffer( nextP );
…
signal(mutex);
signal(full);
}

PRODUCER CONSUMER

Source: https://vh2.com.vn
Category : Ứng Dụng