Nguyên lý hệ điều hành - Tuần 5: Tiến trình và Semaphore. Môn Nguyên lý hệ điều hành (UET) | Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.

lOMoAR cPSD| 58833082
Bài 1: Ba tiến trình sau đây chạy đồng thời với 3 semaphores nhị phân
được khởi tạo là S0 = 1, S1 = 1, S2 = 0. Process P0 Process P1 Process P2 wait(S1); wait(S2); while(true) signal (S0); { wait(S0); signal(S0); print '0'; signal(S1); signal(S2); }
P0 sẽ in bao nhiêu lần ‘0’ ? Giải thích. Bài làm -
Ban đầu, P0 sẽ thực thi trước vì chỉ có S0 = 1. Nó sẽ in ký tự '0' lần đầu. ● wait(S0) giảm S0=1
● print ‘0’ in ra ký tự 0 lần đầu tiên ● signal(S1) tăng S1=2 ● signal(S2) tăng S2=1 -
Sau đó, P0 sẽ thực thi signal đến S1 và S2, bất kỳ một trong hai
tiến trình này có thể thực thi.
● Lúc này S0=1, S1=1 (do binary semaphore chỉ nhận giá trị 0 và
1, lúc này S1 sẽ giữ nguyên giá trị), S2=1
+ Trường hợp 1: thực thi tuần tự ● P1 thực thi: lOMoAR cPSD| 58833082 wait(S1) giảm S1=1 signal(S0) tăng S0=1 ● P0 Thực thi: wait(S0) giảm S0=0
print ‘0’ in ra kí tự 0 lần thứ hai
signal(S1) tăng S1=2 signal(S2) tăng S2=2 ● P2 thực thi: wait(S2) giảm S2=1 signal(S0) tăng S0=1 ● P0 thực thi:
wait(S0) giảm S0=0 print ‘0’
in ra kí tự 0 lần thứ ba Vậy P0 sẽ in
ra ký tự ‘0’ được 3 lần.
+ Trường hợp 2: Sau khi P1 thực thi thì sẽ đến P2 thực thi ● P1 thực thi: wait(S1) giảm S1=1 signal(S0) tăng S0=1 ● P2 thực thi: wait(S2) giảm S2=0 signal(S0) tăng S0=1 ● P0 thực thi:
wait(S0) giảm S0=0 print ‘0’ in ra ký tự 0 lần thứ hai
Vậy P0 sẽ in được ký tự ‘0’ được 2 lần
Vậy S0 sẽ có thể in được 2 lần ký tự ‘0’ hoặc 3 lần ký tự ‘0’
Không có trường hợp in kí tự ‘0’ được 1 lần vì ban đầu ta có S2=0 thì
sẽ phải chờ S0 thực thi lần đầu tiên, sau khi S0 thực thi và in ra lần
đầu thì S2=1 và sẽ được thực thi. Bài 2: lOMoAR cPSD| 58833082
Mỗi tiến trình Pi, i = 1, 2 … 9 có đoạn mã như sau: repeat P(mutex) { Critical Section } V(mutex) forever
Tiến trình P10 có đoạn mã tương tự nhưng V(mutex), P(mutex) đổi
chỗ cho nhau. Hỏi số lượng tiến trình nhiều nhất cùng ở ở khu vực
quan trọng trong một thời điểm ?
1. Giả sử giá trị của mutex ban đầu là 1
Trường hợp 1: Hệ thống có cơ chế ngắt định kì, lúc này mỗi khi hệ
thống ngắt chọn ngắt P10:
- Xét đoạn mã với vòng lặp từ i = 1 đến 9:
+ Ban đầu, giá trị của mutex được đặt là 1, do đó nó chỉ cho phép
một tiến trình vào Critical section tại một thời điểm.
+ Khi P1 vào vùng găng, tất cả các tiến trình còn lại (P2, P3, P4, ...,
P9) sẽ bị chặn (blocked) vì mutex không cho phép nhiều tiến trình truy cập cùng lúc.
- Xét trường hợp của tiến trình P10:
+ P10 thực hiện V(mutex) tăng giá trị mutex lên 1 sau đó P10 thực
hiện P(mutex) để giảm giá trị mutex xuống 0 và P10 vào
Critical Section. Vậy lúc này P10 ở trong Critical Section và
đồng thời sau khi thực thi V(mutex) thì một tiến trình từ P1 đến
P9 được giải phóng, cùng P10 vào Critical section.
+ Mỗi khi hệ thống định kì ngắt, chỉ định P10 để khi chạy lại P10
sẽ được chạy tiếp rồi đồng thời cũng kéo theo một tiến trình bất
kỳ từ P1 đến P9 còn lại vào Critical section mà trước đó đã có
sẵn một tiến tình trong Critical section ở bước trên. lOMoAR cPSD| 58833082
+ Mỗi lần hệ thống định kì ngắt như vậy sẽ có thêm một tiến trình
được đưa vào Critical Section cho đến khi hết tiến trình cần được giải phóng.
Như vậy, cả 10 tiến trình (P1 đến P10) đều có thể vào Critical Section. Trường hợp 2:
- Ban đầu mutex có giá trị là 1.
- P1 được cho phép thực hiện P(mutex) giảm giá trị mutex xuống 0 và P1 vào Critical Section.
- context switch sang P10: P10 được cho phép và thực hiện V(mutex)
tăng giá trị mutex lên 1 sau đó P10 thực hiện P(mutex) để giảm giá
trị mutex xuống 0 và P10 vào Critical Section. Vậy lúc này cả P1 và
P10 đều trong Critical Section
- Context Switch sang P2, P2 thực hiện P(mutex) giảm giá trị mutex
xuống 0 và P2 vào Critical Section. Lúc này sẽ có 3 tiến trình trong
Critical Section trong khi giá trị mutex=0. Như vậy sẽ có 3 tiển trình trong Critical section
2. Giả sử giá trị của mutex ban đầu là 0:
- P10 được cho phép và thực hiện V(mutex) tăng giá trị mutex lên
1. Lúc này Từ P1 đến P9 sẽ có một tiến trình được giải phóng,
đi vào Critical section và Đồng thời P10 cũng vào Critical
section. Vậy có 2 tiến trình trong Critical section.
Vậy sẽ có 2 tiến trình trong Critical section
Xét cả 3 trướng hợp, kết luận rắng số lượng tiến trình nhiều nhất ở
cùng một khu vực quan trọng trong một thời điểm là 10.