NGUYÊN LÝ HĐH (Đề cương 24 câu)

-------------------------Full------------------------

1. Câu 1: Giả sử MCB đầu tiên trong MSDOS có địa chỉ quy ước là A0. Hãy trình bày (bằng một trong ba phương pháp phổ biến và có tính xác định càng cao càng tốt) thuật toán phân phối bộ nhớ cho một chương trình sẽ được tải và thuật toán giải phóng bộ nhớ cho chương trình vừa hoàn thiện.

Giải phóng bộ nhớ

void free(void *firstbyte) {

struct mem_control_block *mcb;

/* Backup from the given pointer to find the

* mem_control_block

*/

mcb = firstbyte - sizeof(struct mem_control_block);

/* Mark the block as being available */

mcb->is_available = 1;

/* That's It! We're done. */

return;

}

Cấp phát bộ nhớ (theo first fit):

giả sử yêu cầu m suy ra vùng nhớ cần m+16 (vì MCB bắt đầu vùng có độ dài 16 bài)

1. Now_location = a0

2. Tách 16 byte từ now_location cho mcb

3. If (mcb-> available) then

4. If (mcb->size >= m+16) then

5. Jump to 9

6. Else

7. Now_location = now_location+mcb->size

8. Quay về 2

9. Địa chỉ bắt đầu ct là now_location+16,

10. đánh dấu mcb->available = false

11. return now_location+16,

2. Câu 2: Giải thích lý do trong lập lịch quá trình nhiều dòng xếp hàng thì các quá trình có nhiều thao tác vào-ra được xếp vào dòng ưu tiên cao hơn.

Thời gian 1 lần chiếm giữ CPU liên tục là nhỏ -> giảm thời gian chờ đợi

trung bình chung

Vì khả năng tạm dừng chiếm giữ CPU để chờ vào ra là cao, trong thời gian chờ vào ra có thể cho chương trình khác chiếm giữ CPU -> giảm thời gian chờ đợi

3. Câu 3: Giới thiệu về thuật toán đọc File trong hệ điều hành MS-DOS (minh họa bằng dạng đoạn chương trình hoặc sơ đồ khối).

( Trang 62- 63 )

Trong thuật toán này, giả sử:

- Nội dung bảng FAT được cho bởi một mảng FAT: FAT[i] cho biết nội dung ô FAT thứ i;

- K‎í hiệu EOF tương ứng với dấu hiệu ô FAT kết thúc File;

- Thủ tục DOC(i) thực hiện đọc nội dung cluster thứ i để sử dụng;

- L0 là độ dài File tính theo byte, N0 là số hiệu cluster đầu tiên của File. Hai giá

trị này có trong điểm vào của File;

- L1 là độ dài của cluster tính theo byte

- n là chỉ số cluster hiện thời, L là khối lượng byte đã đọc;

Biểu diễn đoạn chương trình:

n := N0;

L := 0;

Repeat

Doc(n);

L := L + L1;

n:= FAT[n];

Util (L>=L0) OR (n=EOF);

Điều kiện thoát khỏi vòng lặp (L>=L0) là điều kiện bổ sung, vì với File văn bản DOS, MS-DOS đưa thêm vào một đoạn 128 byte vào cuối File.

4. Câu 4: Tìm những nội dung trong hệ điều hành minh chứng cho nhận định "Trong các hệ điều hành, cấu trúc dữ liệu danh sách được sử dụng khá rộng rãi".

a. Sử dụng trong dòng xếp hàng các quá trình trong phân phối CPU

b. Trong điều khiển bộ nhớ liên tục MCB cũng có thể coi là sử dụng cấu trúc dữ liệu danh sách.

c. Trong quản lý bộ nhớ gián đoạn, chiến lược giải phóng trang cũng sử dụng cấu trúc dữ liệu này (FIFO, LRU, ...)

d. Dùng để quản lý không gian lưu trữ file trong đĩa từ.

e. Danh sách gắp với semaphore