On thi Ly tuyet môn HDH (tiep theo)

Đáp án lý thuyết môn Hệ điều hành lần I
HKII 2008-2008
Câu 1 (1 điểm)
Phân biệt Multiprocessor Systems với Clustered Systems.

Trả lời:
- Multiprocessor Systems là hệ thống đa xử lý (với hệ điều hành tương ứng) hỗ trợ nhiều CPU trên một máy.
- Clustered Systems là hệ thống gom cụm (với hệ điều hành tương ứng) bao gồm nhiều máy tính cùng thực hiện một công việc chung, nối mạng với nhau qua đường truyền tốc độ cao.

Câu 2 (1 điểm)
So sánh chức năng của Medium-Term Scheduler với chức năng của Short-Term Scheduler

Trả lời:
- Medium-Term Scheduler (trình điều phối vừa) là Short-Term Scheduler (trình điều phối nhanh) nhưng được bổ sung thêm chức năng đẩy bớt một số tiến trình ra đĩa cứng nhằm giảm độ đa chương, đảm bảo hỗn hợp các loại tiến trình (hướng CPU và hướng I/O) tối ưu hơn, nâng cao hiệu năng của hệ thống.
- Hoán đổi tiến trình với đĩa cứng trong chức năng của Medium-Term Scheduler:



Câu 3 (1 điểm)
Nguyên lý tập luồng (Thread Pools) và ứng dụng. Cho ví dụ minh hoạ.

Trả lời:
- Tiến trình cha tạo lập sẵn một tập luồng ở trạng thái chờ công việc.
- Khi cần xử lý một yêu cầu mới, một luồng được đánh thức và đưa nhanh vào vận hành, xong việc lại trở về tập luồng.
- Nếu số yêu cầu vượt quá số luồng trong tập luồng, tiến trình cha chờ đến khi có luồng được giải phóng.
- Ví dụ minh hoạ: Web Server, Database Server đều làm việc theo nguyên lý này.

Cau4 (1 điểm)
Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải dùng kỹ thuật Busy-Waiting.

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à sản xuất 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 bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.
- Thuật giải dùng kỹ thuật Busy-Waiting (chờ bận) với biến đếm count (chứa số sản phẩm trong Buffer):
+ Producer:
Code:


while(1){
while(count == BUFFER_SIZE); // Vòng lặp chờ bận
// Đưa sản phẩm vào Buffer
count++; // Tăng count lên 1
}

+ Consumer:
Code:



while(1){
while(count == 0); // Vòng lặp chờ bận
// Lấy sản phẩm từ Buffer
count--; // Giảm count đi 1
}

Ghi chú:
- Vòng lặp chờ bận phải liên tục kiểm tra giá trị biến đếm count, tốn thời gian CPU, dẫn đến giảm hiệu năng hệ thống.
- Có thể không dùng biến đếm count. Khi đó, vòng lặp chờ bận cho Producer được thực thi bằng:
Code:


while(((in+1)%BUFFER_SIZE)==out); // Vòng lặp chờ bận

Còn đối với Consumer thì dùng:
Code:


while(in==out); // Vòng lặp chờ bận

Câu 5 (1 điểm)
Trình bày thuật giải bảo vệ bộ nhớ trong bằng Thanh ghi tái định vị và Thanh ghi giới hạn.

Trả lời:


Trong đó:
- Logical Address - Địa chỉ lô-gic sản sinh bởi CPU trong qua trình vận hành của tiến trình. Địa chỉ lô-gic hợp lệ phải trong khoảng [0, m-1], với m là nội dung Thanh ghi giới hạn.
- Limit Register – Thanh ghi giới hạn chứa số byte của vùng nhớ dành cho tiến trình hiện hành.
- Relocation Register – Thanh ghi tái định vị chứa địa chỉ byte đầu tiên của vùng nhớ dành cho tiến trình hiện hành.
- Physical Address - Địa chỉ vật lý tính theo công thức:
Địa chỉ vật lý = Nội dung Thanh ghi tái định vị + Địa chỉ lô-gic
Câu 6 (1 điểm)
Phân tích ưu và nhược điểm của Dynamic Disk so với Basic Disk.

Trả lời:
- Ưu điểm của Dynamic Disk: Số luợng phân vùng không bị hạn chế (có thể hơn 4). Mỗi phân vùng cài hệ tập tin NTFS đảm bảo độ tin cậy và tính bảo mật cao. Đĩa động hỗ trợ nhiều tính năng mới như: Ổ ghép (Spanned Volume), Ổ song song (Striped Volume, tức RAID-0), Ổ ánh xạ gương (Mirrored Volume, tức RAID-1) và Ổ RAID-5.
- Nhược điểm của Dynamic Disk: Chỉ dùng cho môi trường Windows 2000 trở lên, trong khi phân hoạch theo chuẩn Basic Disk cho phép cài cả các hệ điều hành khác Windows như Unix/Linux, Mac OS, OS/2,... vào các phân vùng khác nhau.

Câu 7 (2 điểm)
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)

P1
3
37

P2
10
20

P3
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 8 (2 điểm)
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,0 đ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)=0
- 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ì:
- Need2=(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ám ơn bạn đã đưa bài giải rất chi tiết. Tranh thủ học thui các bạn ơi

Thanks bạn nhìu vì đã cung cấp thông tin bổ ích này

Thanks bạn, nhưng mình thấy thuật giải vòng ROBIN của những câu hỏi này không được ổn cho lắm chỗ điều phối P2 và P3. Bạn xem lại nhé.

Bạn yên tâm đi, bài giải đó của Thầy giải mà, kết quả đúng rồi đó bạn.