De Thi lan 1 Mon HDH cua lop Chinh Qui

TRƯỜNG ĐẠI HỌC MỞ TP HỒ CHÍ MINH
KHOA CÔNG NGHỆ THÔNG TIN

ĐỀ THI 1
MÔN : Hệ điều hành HỌC KỲ: 1 NĂM HỌC: 2007-2008
LỚP: TH06A1, TH06B1, TH06C1 HỆ: Chính quy tập trung
Thời gian làm bài: 120 phút Sinh viên không được sử dụng tài liệu

Câu 1 (1 điểm)
Mục tiêu, ý nghĩa và cấu trúc môn học “Hệ điều hành”.
Giải:
a) Ý nghĩa
- Hiểu sâu nguyên lý hoạt động của phần cứng và phần mềm máy tính.
- Học phương pháp phân tích, thiết kế và lập trình một hệ thống lớn để áp dụng cho công tác nghiệp vụ sau này.
b) Mục tiêu
- Cung cấp các khái niệm cơ bản về cấu trúc và hoạt động của máy tính và hệ điều hành
c) Cấu trúc môn học
- Khái niệm chung, lịch sử, phân loại hệ điều hành.
- Nguyên lý và hoạt động các khối chức năng.
- Giới thiệu dòng hệ điều hành Windows NT/ 2000/ XP/2003.

Câu 2 (1 điểm)
Nguyên lý hoạt động của hệ điều hành đa chương.
Giải:
+ Hệ điều hành đa chương (Multiprogramming System): Đây là hệ cho phép nhiều công việc cùng chạy một lúc. Cùng chia sẻ quyền sử dụng CPU theo một thuật toán nào đó. Ví dụ như Windows 3.1, Windows 9x… Nhìn chung:
- Có nhiều tác vụ (tiến trình) cùng một lúc được nạp đồng thời vào bộ nhớ chính.
- Thời gian xử lý của CPU được phân chia giữa các tác vụ đó.
- Tận dụng được thời gian rảnh tăng hiệu suất sử dụng CPU (CPU utilization)
- Và khi một một tác vụ không cần đến CPU (do phải thực hiện I/O với thiết bị ngoại vi), thì tác vụ khác được thi hành.
- Yêu cầu:
 Đồng thời công việc (job scheduling): chọn job trong job pool trên đĩa và nạp nó vào bộ nhớ để thực thi.
 Quản lý bộ nhớ (memory management).
 Định thời CPU (CPU scheduling).
 Cấp phát tài nguyên (đĩa, máy in,…).
 Bảo vệ.


Câu 3 (1 điểm)
Phân biệt Synchronous I/O với Asynchronous I/O. Cho các ví dụ minh hoạ.
Giải:
- Synchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình chuyển sang trạng thái chờ đến khi Nhập/Xuất hoàn tất rồi mới chạy tiếp (thực hiện lệnh kế tiếp)
Ví dụ: Khi ta tạo mới một tài liệu nhập dữ liệu từ bàn phím, khi muốn lưu lại ta phải chọn Save, sau đó đặt tên file, và chọn nơi lưu trữ. Các tiến trình đó ở trạng thái chờ tiến trình trước nhập xuất hoàn tất đã.

- ASynchronous I/O: Sau khi phát ra lệnh Nhập/Xuất, tiến trình không chờ Nhập/Xuất hoàn tất mà thực hiện ngay lệnh kế tiếp. Như vậy, tiến trình vận hành song song với công việc Nhập/Xuất.
Để chứng minh điều đó, hãy xem hình vẽ sau:
Ví dụ: Khi ta nhập dữ liệu mới hoặc thêm vào tài liệu đã có, khi ta muốn lưu thì ta chọn Save và lúc này tiến trình vận hành song song với việc phát ra lệnh từ Save.

Câu 4 (1 điểm)
So sánh Basic Disk với Dynamic Disk.
Giải:
- Một Basic Disk là một ổ cứng vật lý bao gồm các phân vùng chính (Primary Partition), các phân vùng mở rộng (Extended Partition) hoặc các ổ đĩa luận lý (Logical Drive). Các phân vùng và các ổ đĩa luận lý trên các basic disk còn được hiểu như là các Basic Volume.
Số phân vùng (Partition) ta tạo trên một Basic disk tuỳ thuộc vào loại phân vùng của ổ đĩa (Disk’s Partition Type).
 Đối với MBR (Master Boot Record) disks, chúng ta có thể tạo được nhiều nhất 4 phần vùng chính (Primary Partition), hoặc 3 phân vùng chính và một phân vùng mở rộng (Extended Partion). Trong phân vùng mở rộng ta có thể tạo vô hạn các ổ đĩa luận lý (Logical Drive).
 Đối với GPT (GUIDs Partition Table) disks, chúng ta có thể tạo lên đến 128 phân vùng chính (Primary Partition). Bởi vì GPT disks không giới hạn 4 phân vùng chính nên chúng ta không cần tạo phân vùng mở rộng hay các ổ đĩa luận lý.
- Một Dynamic Disk cung cấp các tính năng mà Basic Disk không có, như khả năng tạo những volume mở rộng trên nhiều ổ đĩa vật lý (Spanned and Striped Volumes) và khả năng tạo ra những volume Fault Tolerance (Mirrored and Raid-5 Volumes). Các volume trên Dynamic Disk ta gọi là Dynamic Volumes, và một Dynamic Disk có thể hỗ trợ lên tới 2000 Volume trên một ổ đĩa (dù vậy Microsoft đã giới thiệu số lượng Dynamic Volumes là 32 hoặc ít hơn trên một ổ đĩa). Có 5 loại Dynamic Volume là: Simple, Spanned, Stripped, Mirrored và Raid-5. Trong đó Mirrored và Raid-5 chỉ chạy trên máy tính có hệ điều hành Windows 2000 Server, Windows 2000 Advanced Server, Windows 2000 Datacenter Server, or Windows XP….

Câu 5 (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 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;
empty = BUFFER_SIZE;
mutex = 1;


Câu 6 (1 điểm)
Giới thiệu các hàm của Win32 API dùng để lập trình đa luồng.
Giải:
- CreateThread: tạo một luồng để thực thi trong địa chỉ lời gọi tiến trình.
- ExitThread: dùng để kết thúc một luồng.
- GetCurrentThread: có chức năng trả về mục quản tạm cho luồng hiện tại.
- TerminateThread: có chức ngắt luồng.
- SetThreadPriority: có chức năng thiết lập giá trị ưu tiên cho một luồng.
…………………

Câu 7 (1 điểm)
Trên một hệ tập tin FAT32, tập tin DeThi1.pdf có nội dung tại liên cung 5, trong khi DapAn1.pdf cần các liên cung 8, 6, 7. Hãy thể hiện bằng hình vẽ cấu trúc bảng FAT và các Directory Entry.
Giải:

Tớ xin lỗi câu này tớ chưa học nhưng đọc tài liệu của thầy rồi tự làm, nếu có sai các bạn sửa lại giúp nhé!

Câu 8 (1 điểm)
Giả sử trong quá trình quản lý bộ nhớ ảo dạng phân đoạn, hệ điều hành duy trì Segment Table:
Segment Base Limit
0 300 700
1 1200 500
2 2000 600
Hãy tính địa chỉ vật lý cho mỗi địa chỉ lô-gic sau: (1, 200), (1, 0), (0, 700), (2, 0), (2, 600)
Giải:
Theo đề bài, ta lập sơ đồ tổ chức của Physical Memory như sau:

Giải thuật tìm địa chỉ vật lý:

Áp dụng giải thuật trên ta có, ứng với các địa chỉ logic (1, 200), (1, 0), (0, 700), (2, 0), (2, 600) ta có các địa chỉ vật lý theo thứ tự là: 1400, 1000, không hợp lệ, 2000, không hợp lệ.
Ví dụ:
- Với địa chỉ logic (1, 200) thì s = 1 (segment = 1) và d = 200 < limit1 = 500 nên địa chỉ vật lý sẽ là: base1 + d = 1200 + 200 = 1400.
- Còn với địa chỉ logic (0, 700) thì s = 0 (segment = 0) và d = 700 = limit0 nên địa chỉ này không hợp lệ. Do đó ta không thể tìm được địa chỉ vật lý trong trường hợp này.

Câu 9 (2 điểm)
Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau:
Process Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
Duøng thuaät giaûi Nhaø baêng ñeå:
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 yêu cầu (0, 4, 3, 0) của P1 ? (1 điểm)
Giải:
a. Xét tại thời điểm T0 mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]
Process Need
A B C D
P0 0 0 0 0
P1 0 7 5 0
P2 1 0 0 2
P3 0 0 2 0
P4 0 4 4 2

Tìm chuỗi an toàn:
Work >= Need[i] P[i] Allocation[i]
A B C D A B C D A B C D
1 5 2 0 0 0 0 0 P0 0 0 1 2
1 5 3 2 1 0 0 2 P2 1 3 5 4
2 8 8 6 0 0 2 0 P3 0 6 3 2
2 14 11 8 0 4 4 2 P4 0 1 1 4
2 15 12 12 0 7 5 0 P1 1 0 0 0
Vậy tại thời điểm T0 tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.

b. Ta thấy, yêu cầu thêm (0, 4, 3, 0) của P1 thoả điều kiện Request1  Need1, nhưng không thoả điều kiện: Request1  Available vì tài nguyên C trong hệ thống chỉ còn 2 mà yêu cầu 3. Do vậy, không thể cấp phát thêm (0, 4, 3, 0) cho P1 được.


Xác nhận của Khoa Người ra đề: TS Tô Tuấn (0983.57.93.84)