---
# System prepended metadata

title: 'Exercises for OS #5'
tags: [Lecture HCMUS, Operating System]

---

Câu 01:
## CPU Scheduling
### Câu 01
:::info
Hệ thống có 4 tiến trình P1, P2, P3 và P4 trong hàng đợi thực thi với thời gian đến, thời gian thực thi, và độ ưu tiên (số càng lớn thì tiến trình càng được ưu tiên) như bên dưới. 
a. Vẽ sơ đồ điều phối minh hoạ cho điều phối CPU với chiến lược: SJF, SRTN
b. Ứng với từng chiến lược, tính: thời gian lưu trú trung bình, thời gian chờ trung bình, khả năng (hiệu suất sử dụng CPU).
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434744026_425472353562044_7194619306536383347_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ZUGrpPnbVUkAb61k18A&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEEB4eIqUeXPXGunSIXbffB45yKbUPFWjJkrszwb5j_Mg&oe=6649A6A2></center>
:::
Bài Làm
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/438102009_1864273324023369_5528546989652596194_n.jpg?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=IKopt9DXgrsAb6dRSKA&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFMk3YrgHQ0phduEy-ESTaLEwU8WKPdqvhNAY2Zhz_lkg&oe=664988F5></center>
<center></center>

### Câu 02:
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/435810458_1583122205818486_4364852214082483206_n.jpg?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=GluJFmdRYPcAb7h1LFV&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEmuFljV9teIvJXCNqAgGuls5IQfOFEzKHaB2bG9uJoHQ&oe=66498525>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/438069687_2117620238600806_8587008537383122901_n.jpg?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=jhJP_ijlzgcAb5gZbK4&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGNKvQ31pYhZZV64h_YVcLQ-gxGBgzpyqsPRo6OeZ_C-w&oe=6649B063></center>


## Đồng bộ hóa
### Câu 07
:::info
Cho mảng sau: int x\[20\]; Dùng semaphore đồng bộ hoá cho 3 threads B, C, D thực hiện các nhiệm vụ sau trên tiêu chí khai thác tối đa khả năng xử lý song song, chia sẻ tài nguyên dùng chung giữa các threads. a. B tính tổng giá trị các phần tử của mảng x có chỉ số chẵn b. C tính tổng giá trị các phần tử của mảng x có chỉ số lẽ c. D tính tổng giá trị các phần tử của mảng x dựa trên kết quả từ B và C Giả sử: B, C, D cùng đến hệ thống tại 1 thời điểm, có thể kết thúc công việc mà không cần chờ đợi nhau.
:::
Bài Làm
```cpp!=
semaphore tB = 0, tC = 0, tD = 1;
int sumB = 0, sumC = 0, sumD = 0;
init(tB, 0); init(tC, 0); init(tD, 1);
ProcessB (int x[]) {
down(tD);
for(int i = 0; i < 20; ++i){
if(x[i] % 2 == 0)
            sumB += x[i];
}
up(tB);
}
ProcessC (int x[]) {
down(tB);
for(int i = 0; i < 20; ++i){
if(x[i] % 2 != 0)
            sumC += x[i];
}
up(tC);
}

ProcessD () {
down(tC);
sumD = sumB + sumC;
up(tD);
}
```
## Quản lý bộ nhớ
### Câu 01:
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434724172_454996830266578_5477540729435023518_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=kBKZGFcLZmgAb4xil87&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFST_0GzmlC9U8is6Joa4PHaU8gCV5GV8ReeMIirEcasQ&oe=664984BF><p>
	<b>BÀI LÀM</b>
	</p></center>

* Optimal
	<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437944631_372934339071089_4654435086810044314_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=5Nm9gyPvSvAAb7eENDD&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGpHiKkzWG59d5lX1Ix4HCUeuy8cEGQ-rxj0AFxGH6dAg&oe=664993EB></center>
	
	* Tỷ lệ lỗi trang: ${\bf p} = \displaystyle \frac{10}{21}$
	* ${\bf EAT} = (1 - {\bf p}) \times {\bf t_m} + {\bf p} \times {\bf t_p} \approx 146.4286 \text{ ns}$
* LRU
	<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434749084_978976220419872_4625442525296047719_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=wGfsA_WP-boAb60taZ0&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFmnPLBfqXfIIm9j_jHqHlqVyaYuxuoMSHVWHeVbC2KAg&oe=664980FC></center>
	
	* Tỷ lệ lỗi trang: ${\bf p} = \displaystyle \frac{11}{21}$
	* ${\bf EAT} = (1 - {\bf p}) \times {\bf t_m} + {\bf p} \times {\bf t_p} \approx 150.5715 \text{ ns}$
* FIFO Second Chance
	<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434850313_1157660488771781_1477293392000764238_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=L2dMMH8YMMYAb5PpxaY&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGv5IK8Wg53w9a9CXnQW4Rm1rLl_am6SbBFzFbt83wFQg&oe=66499D86></center>
	
	* Tỷ lệ lỗi trang: ${\bf p} = \displaystyle \frac{12}{21}$
	* ${\bf EAT} = (1 - {\bf p}) \times {\bf t_m} + {\bf p} \times {\bf t_p} \approx 154.7143 \text{ ns}$
### Câu 03:
:::info
Một máy tính sử dụng bộ nhớ ảo phân trang, biết rằng bộ nhớ ảo sử dụng 10bit địa chỉ, RAM 1KB, kích thước mỗi trang là 256 bytes. 
a. Số lượng trang tối đa cho một tiến trình thực thi trên hệ thống này là bao nhiêu? 
b. Giả sử sử dụng bảng trang nghịch đảo thì số lượng entry trong bảng trang là bao nhiêu. 
c. Thử đề xuất một giải pháp phân trang đa cấp để quản lý địa chỉ ảo của tiến trình.
:::
Ta có:
Page size $= 256 \text{ bytes} = 2^8 \text{ bytes}$
the size of physical address space $= 1 \text{ KB} = 2^{10} \text { bytes}$
No. of bits for logical address space $= 10 \text{ bits}$
a. Số bits dùng để lưu số offset: d = 8 bits
Số bits dùng để lưu số trang: p = 10 - 8 = 2 bits
Số lượng trang tối đa cho một tiến trình: $2^2 = 4$ trang
b. Bảng trang nghịch đảo lưu trữ thông tin về các trang mà một tiến trình đang sử dụng. Vì mỗi entry trong bảng trang nghịch đảo chỉ cần lưu vị trí của trang trong bộ nhớ ảo (10 bit địa chỉ), số lượng entry sẽ bằng số trang tối đa mà một tiến trình có thể sử dụng. => Số lượng entry = Số lượng trang tối đa = 4 entries
c. Thử đề xuất một giải pháp ?
Giải pháp phân trang đa cấp:
-   Trong phân trang đa cấp, mỗi tiến trình được chia thành các phân đoạn (segments).
-   Mỗi phân đoạn lại được chia thành các trang.
-   Giải pháp này giúp tăng hiệu suất quản lý bộ nhớ vì ta chỉ cần load vào bộ nhớ các trang cần thiết của các phân đoạn mà không cần load toàn bộ tiến trình vào bộ nhớ khi tiến trình được thực thi.
-   Để triển khai phân trang đa cấp, ta cần sử dụng một bảng trang cho mỗi phân đoạn, và có thể sử dụng bảng trang nghịch đảo cho mỗi phân đoạn hoặc một phương pháp khác.
-   Việc triển khai cụ thể cũng phụ thuộc vào yêu cầu cụ thể của hệ điều hành và cấu trúc của tiến trình.

Như vậy, đó là cách giải quyết bài toán phân trang với các yêu cầu và thách thức cụ thể như trên.

### Câu 04:
:::info
Cho các tiến trình có bộ nhớ tương ứng A(300K), B(500K), C(200K), D(200K), E(300K). Sử dụng giải thuật Best-fit (trong kỹ thuật phân vùng động) cấp phát bộ nhớ theo trình tự : A→B→C→thu hồi A →D→thu hồi B→E với dung lượng bộ nhớ dùng để cấp phát là 2000k. 
a. Cho biết hiện trạng bộ nhớ và danh sách quản lý bộ nhớ ở các thời điểm cấp phát theo trình tự trên \[Vẽ hiện trạng bộ nhớ dùng mẫu như ví dụ bên dưới\]. 
b. Theo bạn giải thuật nào phù hợp nhất? 
c. Giải thuật này có thể gặp phải hiện tượng phân mảnh nào.
:::
Bài làm
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/437893345_320681517707846_6513498956997345088_n.jpg?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=XV66sgc9bq8Ab71ct4-&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHwN6dvOB4u0I_1DXwDh6-3nTcpubOFg3gn7bcP4dvA3A&oe=6649AE7C></center>
