Tài liệu ôn thi HDH

huytran2035 4/1/2010, 13:52

Mình mới sưu tầm được, share mọi người tham khảo nha ^^

Download

thanchon 4/1/2010, 14:27

Câu 1 (2 điểm)
Phân tích định nghĩa hệ điều hành là Máy tính mở rộng (Extended Machine) hay Máy tính ảo (Virtual Machine).
Trả lời:
- Ẩn các chi tiết của phần cứng để máy tính dễ sử dụng hơn.
- Người sử dụng và người lập trình được cung cấp một giao diện đơn giản, dễ hiểu, dễ sử dụng và không phụ thuộc vào thiết bị cụ thể.
- Thực tế, hệ điều hành bao gồm nhiều máy tính trừu tượng (Abstract Machine) xếp thành các lớp. Máy tính mức dưới phục vụ cho máy tính mức trên.
- Bản thân chương trình ứng dụng cũng là một máy tính trừu tượng và phải dễ sử dụng nhất.
- Công việc của người lập trình là liên tục xây dựng những máy tính như vậy, cho người khác và cho cả chính mình sử dụng.

Câu 2 (2 điểm)
Trình bày 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.
- Điểm thưởng nếu nêu trường hợp: Năm 1999, thày đến mạng Phương Nam giải quyết sự cố liên quan đến ứng dụng Web động (dùng CGI) Giới thiệu việc làm qua mạng.

Câu 3 (2 điểm)
Giải thích đoạn mã sau:
Code:
#define BUFFER_SIZE 50
HANDLE semEmpty, semFull;
semEmpty=CreateSemaphore(0, BUFFER_SIZE, BUFFER_SIZE, "SemEmpty");
semFull=CreateSemaphore(0, 0, BUFFER_SIZE, "SemFull");
WaitForSingleObject(semEmpty, INFINITE);
printf(“semEmpty Handle=%d”, semEmpty);
WaitForSingleObject(semFull, INFINITE);
printf(“semFull Handle=%d”, semFull);

Trả lời:
1. Khai báo kích thước bộ nhớ đệm bằng 50 (cho bài toán Sản xuất-Tiêu thụ).
2. Khai báo 2 biến semEmpty và semFull dùng chứa mục quản (Handle) của 2 đèn hiệu (Semaphore).
3. Yêu cầu hệ điều hành tạo lập đèn hiệu liên tiến trình tên là SemEmpty với giá trị ban đầu và tối đa bằng 50 (BUFFER_SIZE). Mục quản của đèn hiệu gửi vào biến semEmpty.
4. Yêu cầu hệ điều hành tạo lập đèn hiệu liên tiến trình tên là SemFull với giá trị ban đầu bằng 0 và giá trị tối đa bằng 50 (BUFFER_SIZE). Mục quản của đèn hiệu gửi vào biến semFull.
5. Chờ vô hạn (INFINITE) đến khi giá trị của đèn SemEmpty lớn hơn 0 (hiện bằng 50 nên qua được, sau đó giá trị của SemEmpty còn 49).
6. Lệnh printf() đưa ra Mục quản của đèn hiệu SemEmpty.
7. Lời gọi chờ tại SemFull sẽ chuyển luồng hiện hành sang trạng thái chờ đến khi giá trị của đèn này lớn hơn 0 (hiện bằng 0).
8. Lệnh printf() đưa ra Mục quản của đèn hiệu SemFull, nhưng hiện tại không thực hiện, do luồng hiện hành phải chờ đến khi giá trị của SemFull lớn hơn 0.
Câu 4 (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:

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. Tính thời gian chờ trung bình của các tiến trình:
- Thời gian chờ của các tiến trình: P1 = 20 ms, P2 = 30 ms, P3 = 17 ms
- Thời gian chờ trung bình của các tiến trình = (20 30 17)/3 = 67/3 = 22,3 ms

Chú ý:
Bạn AsmKing có nhận xét đúng: Tại thời điểm 32, P1 phải được chọn, vì trong Ready Queue, P1 trước P3, và kết quả là 19 ms. Những năm trước đều chấp nhận cả 2 phương án.

Cách giải của AsmKing:
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:
- Thời gian chờ của các tiến trình:
P1 = 0 + (32 - 22) = 10 ms
P2 = (22 - 15) + (47 - 32) + (65 - 57) = 30 ms
P3 = (37 - 30) + (57 - 47) = 17 ms
- Thời gian chờ trung bình của các tiến trình = (10+30+17)/3 = 19 ms

Câu 5 (2 điểm)
Một hệ thống có 4 ổ 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 = (1, 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 ở thời điểm Ti là an toàn:
1. Available = 4 – (1 2 1) = 0
2. Need = Max – Allocation = (2, 2, 2) – (1, 2, 1) = (1, 0, 1)
3. Tìm được 2 chuỗi an toàn (một trong hai cũng được):

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 = 0 (P2 đã được cấp số lượng tối đa được phép có)

NhutNguyen 7/1/2010, 10:06

huytran2035 đã viết:Mình mới sưu tầm được, share mọi người tham khảo nha ^^

Download

Cam on ban nhieu, sap thi roi chuc moi nguoi thi tot.

tamcoi 7/1/2010, 11:15

thanchon đã viết:Câu 1 (2 điểm)
Phân tích định nghĩa hệ điều hành là Máy tính mở rộng (Extended Machine) hay Máy tính ảo (Virtual Machine).
Trả lời:
- Ẩn các chi tiết của phần cứng để máy tính dễ sử dụng hơn.
- Người sử dụng và người lập trình được cung cấp một giao diện đơn giản, dễ hiểu, dễ sử dụng và không phụ thuộc vào thiết bị cụ thể.
- Thực tế, hệ điều hành bao gồm nhiều máy tính trừu tượng (Abstract Machine) xếp thành các lớp. Máy tính mức dưới phục vụ cho máy tính mức trên.
- Bản thân chương trình ứng dụng cũng là một máy tính trừu tượng và phải dễ sử dụng nhất.
- Công việc của người lập trình là liên tục xây dựng những máy tính như vậy, cho người khác và cho cả chính mình sử dụng.

Câu 2 (2 điểm)
Trình bày 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.
- Điểm thưởng nếu nêu trường hợp: Năm 1999, thày đến mạng Phương Nam giải quyết sự cố liên quan đến ứng dụng Web động (dùng CGI) Giới thiệu việc làm qua mạng.

Câu 3 (2 điểm)
Giải thích đoạn mã sau:
Code:
#define BUFFER_SIZE 50
HANDLE semEmpty, semFull;
semEmpty=CreateSemaphore(0, BUFFER_SIZE, BUFFER_SIZE, "SemEmpty");
semFull=CreateSemaphore(0, 0, BUFFER_SIZE, "SemFull");
WaitForSingleObject(semEmpty, INFINITE);
printf(“semEmpty Handle=%d”, semEmpty);
WaitForSingleObject(semFull, INFINITE);
printf(“semFull Handle=%d”, semFull);

Trả lời:
1. Khai báo kích thước bộ nhớ đệm bằng 50 (cho bài toán Sản xuất-Tiêu thụ).
2. Khai báo 2 biến semEmpty và semFull dùng chứa mục quản (Handle) của 2 đèn hiệu (Semaphore).
3. Yêu cầu hệ điều hành tạo lập đèn hiệu liên tiến trình tên là SemEmpty với giá trị ban đầu và tối đa bằng 50 (BUFFER_SIZE). Mục quản của đèn hiệu gửi vào biến semEmpty.
4. Yêu cầu hệ điều hành tạo lập đèn hiệu liên tiến trình tên là SemFull với giá trị ban đầu bằng 0 và giá trị tối đa bằng 50 (BUFFER_SIZE). Mục quản của đèn hiệu gửi vào biến semFull.
5. Chờ vô hạn (INFINITE) đến khi giá trị của đèn SemEmpty lớn hơn 0 (hiện bằng 50 nên qua được, sau đó giá trị của SemEmpty còn 49).
6. Lệnh printf() đưa ra Mục quản của đèn hiệu SemEmpty.
7. Lời gọi chờ tại SemFull sẽ chuyển luồng hiện hành sang trạng thái chờ đến khi giá trị của đèn này lớn hơn 0 (hiện bằng 0).
8. Lệnh printf() đưa ra Mục quản của đèn hiệu SemFull, nhưng hiện tại không thực hiện, do luồng hiện hành phải chờ đến khi giá trị của SemFull lớn hơn 0.
Câu 4 (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:

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. Tính thời gian chờ trung bình của các tiến trình:
- Thời gian chờ của các tiến trình: P1 = 20 ms, P2 = 30 ms, P3 = 17 ms
- Thời gian chờ trung bình của các tiến trình = (20 30 17)/3 = 67/3 = 22,3 ms

Chú ý:
Bạn AsmKing có nhận xét đúng: Tại thời điểm 32, P1 phải được chọn, vì trong Ready Queue, P1 trước P3, và kết quả là 19 ms. Những năm trước đều chấp nhận cả 2 phương án.

Cách giải của AsmKing:
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:
- Thời gian chờ của các tiến trình:
P1 = 0 + (32 - 22) = 10 ms
P2 = (22 - 15) + (47 - 32) + (65 - 57) = 30 ms
P3 = (37 - 30) + (57 - 47) = 17 ms
- Thời gian chờ trung bình của các tiến trình = (10+30+17)/3 = 19 ms

Câu 5 (2 điểm)
Một hệ thống có 4 ổ 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 = (1, 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 ở thời điểm Ti là an toàn:
1. Available = 4 – (1 2 1) = 0
2. Need = Max – Allocation = (2, 2, 2) – (1, 2, 1) = (1, 0, 1)
3. Tìm được 2 chuỗi an toàn (một trong hai cũng được):

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 = 0 (P2 đã được cấp số lượng tối đa được phép có)