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

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.

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;

}

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.

a. Thời gian chiếm giữ CPU liên tục là ngắn -> giảm thời gian chờ đợi

cho các chương trình khác

b. 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 vào thay thế -> giảm thời gian chờ đợi

c. Nếu để chương trình có ít thao tác vào ra ở hàng ưu tiên cao, nó sẽ chiếm CPU trong thời gian dài liên tục -> tăng thời gian chờ đợi trung bình chung

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 hàng đợi các quá trình trong phân phối CPU(FCFS, ...), trong phân phối bộ nhớ (LRU, FIFO...)

5. Câu 5: Trình bày bốn chế độ điều khiển CPU thực với một dòng xếp hàng các quá trình sẵn sàng

( Trang 107- 110 )

Bốn chế độ : - FCFS (First Come First Served)

- SJN (Shortest Job Next)

- SRTN (Shortest Remaining Time Next)

- RR (Round-Robin)

1/ FCFS:

Mục tiêu : điều phối cho thời gian chờ đợi trung bình cho mọi quá trình là như nhau.

Chế độ FCFS hoạt động theo dòng xếp hàng nguyên thuỷ, thực hiện lần lượt các quá trình theo thứ tự xếp hàng có sẵn.

Ưu điểm :

- Thao tác đơn giản

- Giờ của CPU không bị phân phối lại, chi phí tổ chức thực hiện thấp nhất

Nhược điểm :

- Không hiệu quả. Các quá trình ngắn cũng phải chờ đợi như các quá trình dài.

- Thời gian chờ đợi trung bình chung lớn. Khi tăng thời gian thực hiện của các quá trình thì thời gian trung bình chờ cũng tăng theo.

2/ SJN

Mục tiêu : cực tiểu hoá thời gian chờ đợi trung bình.

Chế độ SJN sắp xếp các quá trình theo thời gian đòi hỏi CPU thực hiện quá trình.

Ưu điểm :

- So với FCFS, SJN làm giảm thời gian chờ đợi trung bình.

- Nhanh chóng loại bỏ các tiến trình ngắn, giảm số lượng các tiến trình trong hàng đợi.

Nhược điểm :

- Vì SJN làm giảm số phần tử trong hàng đợi, dẫn đến sẽ có các phần tử khác được thêm vào, và nảy sinh sự phân phối lại. Do vậy sẽ có xu thế đẩy các quá trình dài về sau.

3/ SRTN

Mục tiêu : Ưu tiên điều phối cao hơn cho các quá trình có xác suất đòi hỏi thời gian CPU nhỏ là cao hơn.

Chế độ SRTN hoạt động căn bản như trong SJN, tuy nhiên có bước cải tiến đó là sử dụng thời gian thực hiện còn lại làm tham số điều khiển. Hệ thống sử dụng nguyên tắc: "kế tiếp là quá trình với thời gian còn lại nhỏ nhất".

Ưu điểm :

- Đảm bảo thời gian chờ đợi trung bình chung, ưu tiên các quá trình ngắn hơn quá trình dài.

Nhược điểm :

- Phức tạp thêm do phải ghi nhận thời gian thực hiện của các quá trình mỗi lần vào CPU.

4/ RR

Mục tiêu : điều phối đồng đều cho các quá trình.

Chế độ RR sử dụng lượng tử thời gian. Mỗi quá trình trong hàng đợi nhận được một lượng tử thời gian q và nếu quá trình thực hiện hết thời lượng này mà không kết thúc hoặc không bị kết khối thì nó sẽ được đưa và cuối hàng đợi.

Ưu điểm :

- Quá trình đòi hỏi ít thời gian sẽ kết thúc nhanh hơn. Uu tiên quá trình ngắn, nhưng cũng không tổn hại lớn cho các quá trình dài.

- q có độ dài càng thích hợp thì hệ thống càng được thực hiện nhanh.

Nhược điểm :

- Do phải thường xuyên phân phối lại giờ CPU nên thời gian chờ đợi trung bình chung có thể lớn hơn FCFS.

6. Câu 6: Trình bày các nội dung cơ bản về swapping bộ nhớ.

( Trang 83- 84 )

Swapping là cách thức hệ thống thực hiện việc chuyển giao nội dung một số phần bộ nhớ ra đĩa từ để giải phóng bộ nhớ cho một yêu cầu phân phối hiện tại.

Swapping áp dụng chủ yếu cho điều phối bộ nhớ liên tục song trong một số trường hợp cũng được dùng trong điều phối bộ nhớ gián đoạn.

Về hình thức có thể coi swapping là một biến thể của overlay.

Môđun hệ thống của swapping là swapper, có các chức năng:

- Swap out : chọn quá trình để đưa ra đĩa từ

- Swap in : chọn quá trình để đưa trở lại từ đĩa từ vào bộ nhớ trong

- Định vị và quản l‎ý không gian swap

7. Câu 7: Trình bày các nội dung về kiểu dữ liệu semaphore nhị phân và đa giá trị (giá trị, phép toán)

(Trang 128)

1/ semaphore nhị phân

Dijkstra đã sử dụng hai toán tử: P (SIGNAL - yêu cầu tài nguyên) và V (WAIT - giải phóng tài nguyên). Các toán tử này làm việc trên các biến gọi là semaphore. Trong semaphore nhị phân, tương ứng với giá trị 1 là mở semaphore (cho phép chạy) còn giá trị 0 là đóng semaphore (không chạy).

Phép toán: với mỗi semaphore, gắn một danh sách các quá trình đi tới samephore.

P(s), V(s): các toán tử thực hiện. s: biến semaphore nhị phân.

P(s): if s=1

then s0 {đóng semaphore}

else Kết khối quá trình này (chứa lời gọi P(s)) theo s;

đặt một quá trình đang chuẩn bị vào bộ xử lý

V(s): if Danh sách quá trình chờ đợi s không rỗng

then Tách khối quá trình chờ đợi s

else s1 {mở semaphore}

(Trang 133-134)

2/ semaphore đa giá trị

Một semaphore đa giá trị s nhận các giá trị từ 0 đến N (N là số tài nguyên cùng loại). Khi s =0 tức là không còn tài nguyên rỗi để thực hiện nhu cầu.

Phép toán: P(s), V(s): các toán tử thực hiện. s: biến semaphore đa giá trị.

P(s): if s>0

then ss-1

else Kết khối quá trình theo s

đặt một quá trình đang chuẩn bị vào CPU

V(s): if Danh sách quá trình chờ đợi s không rỗng

then Tách khối quá trình chờ đợi

else ss+1

8. Câu 8: Trình bày giải pháp chữ ký điện tử liên quan tới tính toàn vẹn dữ liệu. Giải pháp này có thực sự chống được kẻ tấn công thay đổi nội dung thông điệp hay không ?

Chữ ký điện tử (Digital Signature) dựa trên kỹ thuật sử dụng mã hóa khóa công

khai. Trong đó, cả người gửi và người nhận, mỗi người có một cặp khóa là khóa bí mật, hay riêng tư (Private Key) và khóa công khai (Public Key).

Chữ ký điện tử hoạt động khi một người gửi một thông điệp, người đó dùng khóa riêng c ủa mình để mã hóa thông điệp sang một dạng khó nhận dạng. Người nhận

dùng khóa công khai của người gửi để mã hóa thông điệp. Tuy nhiên, để an toàn thật sự phải có các bước bổ sung. Do đó, thuật toán băm MD5 và thuật toán mã hóa RSA có thể được áp dụng để xây dựng ứng dụng chữ ký điện tử

9. Câu 9: Trình bày khái niệm bế tắc và điều kiện nảy sinh bế tắc.

(Trang 134- 135)

1/ Khái niệm:

Bế tắc là hiện tượng khi một nhóm các quá trình bị kết khối một cách lâu dài.

2/ Điều kiện nảy sinh:

Bế tắc khi xảy ra đồng thời 4 điều kiện sau:

- Loại trừ việc dùng chung (chiếm giữ và chờ đợi): các quá trình không chia sẻ dùng đồng thời mà có nhu cầu sử dụng độc lập tài nguyên hệ thống, không nhường cho các quá trình khác và đồng thời yêu cầu thêm tài nguyên mới.

- Chờ đợi : quá trình có nhu cầu tài nguyên mới và chỉ khi mà nhu cầu được đáp ứng thì mới tiếp tục thực hiện.

- Không được phân phối lại : Không được bổ sung thêm tài nguyên và không thực hiện việc phân phối lại tài nguyên cho các quá trình.

- Sự chờ đợi vòng tròn : các quá trình chờ đợi vòng tròn lẫn nhau.

10. Câu 10: Trình bày khái niệm tách khối, kết khối trong điều khiển dữ liệu.

(Trang 44)

1/ Tách khối:

- Tách khối là quá trình từ các khối đưa ra được các bản ghi cần tìm có liên quan đến khối đó. Tách khối diễn ra sau khi hệ thống đã đọc một khối từ ngoài vào bộ nhớ trong và trước khi chương trình người dùng xử lý bản ghi. Việc tách khối có thể do hệ điều hành hoặc do người dùng đảm nhận.

2/ Kết khối:

- Kết khối là quá trình ngược lại với tách khối. Kết khối diễn ra sau khi chương trình người dùng chuẩn bị xong nội dung bản ghi và đưa bản ghi đó vào khối để chuyển ra ngoài. Việc kết khối cũng có thể do hệ điều hành hoặc người dùng đảm nhận.

11. Câu 11: Trình bày khái niệm và vai trò của trình điều khiển thiết bị. Giải thích câu nói "Chuẩn giao diện thiết bị tăng khả năng tiếp thị cho nhà sản xuất thiết bị ngoại vi"

- Chương trình điều khiển hay trình điều khiển là một loại phần mềm máy tính đặc biệt, được phát triển để cho phép tương tác với các thiết bị phần cứng. Mỗi trình điều khiển ứng với một thiết bị nhất định. Chương trình này tạo ra một giao diện để giao tiếp với thiết bị ứng với nó qua các bus máy tính đặc biệt. Nó cung cấp các lệnh để nhận và gửi dữ liệu tới thiết bị đó. Trình điều khiển còn cung cấp giao tiếp cần thiết cho hệ điều hành và các phần mềm ứng dụng.

- Thường được gọi đơn giản là driver, trình điều khiển thiết bị là phần mềm máy tính được viết riêng cho một thiết bị phần cứng cụ thể và một hệ điều hành cụ thể cho phép một chuơng trình, thường là hệ điều hành hoặc ứng dụng phần mềm, tương tác trong suốt với thiết bị đó. Trình điều khiển thiết bị cung cấp việc xử lý các ngắt cần thiết mà các giao tiếp phần cứng phụ thuộc thời gian bất đối xứng đòi hỏi.

Ý b tự làm, dễ....

12. Câu 12: Trình bày lưu trữ File gián đoạn lên đĩa từ: Nội dung, tác dụng. Lấy ví dụ từ lưu trữ file của hệ điều hành MS-DOS. Giải thích lý do xây dựng các công cụ thực hiện việc gom lại các phần rời rạc của các file lại càng gần càng tốt.

13. Câu 13: Trình bày lý do Virus máy tính nén chương trình chứa virus; Có tình huống nào virus máy tính nén toàn bộ chương trình mang và bản thân virus hay không ? Giải thích ?

14. Câu 14: Trình bày ngắn gọn hai thuật toán lập lịch di chuyển đầu đọc-ghi đĩa từ: SSF (chuyển tiếp tới yêu cầu gần nhất" và Elevator (chuyển tiếp kiểu thang máy) với một tập yêu cầu thao tác đĩa.

1/ SSF (Shortest Seek First):

Track nào có thời gian di chuyển đầu từ đọc ghi ngắn nhất thì phục vụ trước.

SSF có thể gây ra một số yêu cầu không bao giờ được phục vụ.

2/ Elevator:

Đầu đọc của đĩa di chuyển từ một phía (ví dụ bên ngoài hoặc bên trong đĩa) sang phía kia để phục vụ các yêu cầu đọc, sau đó di chuyển ngược lại. Quá trình này lặp đi lặp lại.

15. Câu 15: Trình bày ngắn gọn khái niệm "lập lịch dài hạn" , "lập lịch ngắn hạn", "lập lịch trung hạn".

1/ Lập lịch dài hạn:

Điều phối CPU ảo, làm việc với dòng xếp hàng chương trình đợi vào bộ nhớ trong (xác định quá trình nào được chấp nhận vào hệ thống).

Đối với mỗi quá trình thực hiện một lần (bao gồm phát sinh/ hoàn thiện).

2/ Lập lịch ngắn hạn:

Điều phối CPU thực, xác định quá trình nào được thực thi tiếp theo.

Thực hiện nhiều lần cho một quá trình.

3/ Lập lịch trung hạn:

Lập lịch xác định quá trình nào được đưa vào (swap in), đưa ra (swap out) khỏi bộ nhớ chính

16. Câu 16: Trình bày nội dung quản lý đĩa từ theo phương pháp bitmap và theo phương pháp danh sách liên kết. So sánh ưu, nhược điểm của hai phương pháp này.

Phương pháp Bitmap:

Chia bộ nhớ thành từng đơn vị nhỏ (vài bytes) . Xây dựng bitmap, ứng với mỗi bit trong bitmap là một đơn vị bộ nhớ.

Bit được đánh dấu là 1 khi đơn vị bộ nhớ tương ứng đã được cấp phát

Bit được đánh dấu 0 khi đơn vị bộ nhớ tương ứng chưa được cấp phát.

Thao tác cấp phát bộ nhớ là : Giả sử tiến trình cần k đơn vị bộ nhớ, HĐH duyệt bitmap và tìm ra k bit liên tiếp bằng 0

Quản lý bộ nhớ với những phân đọan động

Quản lý bộ nhớ với những phân đọan động (tt)

Quản vùng nhớ còn trống bằng danh sách liên kết

Tổ chức một danh sách liên kết, mỗi phần tử tương ứng với một tiến trình hay lỗ hổng. Mỗi phần tử trong danh sách có 4 trường :

cờ biểu thị tiến trình (P) hay lỗ hổng (H)

Địa chỉ bắt đầu của vùng nhớ tương ứng

Kích thước của vùng nhớ

Con trỏ Next

Quản lý bộ nhớ với những phân đọan động (tt)

Thao tác cấp phát bộ nhớ

First Fit : Xác định lỗ hổng đầu tiên trong danh sách có kích thước đủ lớn để cấp phát cho tiến trình và lỗ hổng này được chia làm 2 phần : 1 phần cho tiến trình và phần kia là lỗ hổng mới.

Best Fit : xác định lỗ hổng bé nhất có kích thước đủ lớn để cấp phát cho tiến trình.

Worst Fit : Cấp phát phân đoạn tự do lớn nhất đủ lớn để cấp phát cho riến trình.

Có thể làm tăng tốc độ bcho cả 3 thuật toán trên bằng cách tổ chức 2 danh sách : 1 cho tiến trình và một cho lỗ hổng. Tuy nhiên lại làm chậm thao tác giải phóng bộ nhớ.

17. Câu 17: Trình bày nội dung và ý nghĩa nguyên nhân việc đặt tham số TIME (thời gian chạy chương trình nhiều nhất) trong một số hệ điều hành:

Trong điều phối các quá trình xếp hàng, có thể xảy ra trường hợp có một quá trình nào đó có độ ưu tiên thấp và bị đẩy lùi lại, không được thực hiện. Việc đặt thêm tham số TIME là để tính "tuổi" của quá trình đó (nếu giá trị này cao, quá trình sẽ được ưu tiên thực hiện) để tránh có quá trình nào đó bị nghẽn, không biết bao giờ mới được thực hiện.

18. Câu 18: Trình bày sơ bộ về điều khiển bộ nhớ trong MFT: Chương bộ nhớ - lớp chương trình - thuật toán.

(Trang 76 + Trang 63-64 [sách thầy Đặng Vũ Tùng])

Điều khiển bộ nhớ trong MFT tương ứng với chiến lược giới hạn tĩnh (chiến lược phân chương) trong phân phối bộ nhớ liên tục.

1/ Chương bộ nhớ:

Bộ nhớ được chia thành các chương, và mỗi chương được sử dụng như một bộ nhớ độc lập. Mỗi chương đều gồm các thông số: chỉ số chương, địa chỉ, dung lượng.

2/ Lớp chương trình:

Trừ chương dành cho nhân, mỗi chương sẽ được gắn với một số lớp chương trình. Chương trình khi định vị vào bộ nhớ sẽ được phân lớp (do người dùng gắn hoặc ngầm định). Mỗi chương chỉ phục vụ các chương trình thuộc lớp do mình quản lý.

3/ Thuật toán phân phối bộ nhớ:

Trong phân phối với chiến lược phân chương, cần phải chọn được chương có kích thước phù hợp với kích thước chương trình để đạt hiệu quả cao. Các thuật toán thường dùng:

- Phân phối nhanh nhất (First Fit): gặp chương được gắn, đủ rộng đầu tiên.

- Phân phối tối ưu (Best Fit): chọn chương với vùng nhớ dư thừa là ít nhất.

- Worst Fit (Phân phối không tối ưu) [thuật toán không thường dùng]: chọn

chương có kích thước lớn nhất để cấp phát.

19. Câu 19: Trình bày tính khả chuyển của một hệ điều hành: khái niệm và giải pháp. Lấy ví dụ từ mang chuyển Minix sang PowerPC.

- Tính khả chuyển: khả năng chạy trên lớp rộng lớn hạ tầng thiết bị phần cứng với không có (hoặc rất ít) thay đổi.

Tính khả chuyển của một hệ điều hành giúp bạn chuyển nó từ một nền này sang nền khác mà vẫn hoạt động tốt. Thí dụ UNIX là một hệ có tính khả chuyển cao. Ban đầu UNIX chỉ hoạt động trên một nền duy nhất, đó là máy tính mini DEC PDP-7.

Hiện nay UNIX và Linux có khả năng chạy trên bất kỳ nền nào, từ máy xách tay cho đến máy tính lớn. Nhờ tính khả chuyển, các máy tính chạy UNIX và Linux trên nhiều nền khác nhau có thể liên lạc với nhau một cách chính xác và hữu hiệu. Những hệ này có thể hoạt động mà không cần phải bổ sung thêm bất kỳ giao diện liên lạc đắt tiền nào, mà thông thường bạn phải mua thêm sau khi mua những hệ điều hành khác.

20. Câu 20: Trình bày về các chế độ loại bỏ trang FCFS, LRU trong điều khiển bộ nhớ gián đoạn.

(Trang 95-96)

Hai chiến lược giải phóng trang:

1/ FIFO (First In First Out):

Trang được đưa vào bộ nhớ trong sớm nhất (ở đầu danh sách) sẽ được giải phóng để nhường chỗ cho trang mới nạp vào (trang mới được đưa vào cuối danh sách).

Ưu điểm:

- Thao tác đơn giản, hoạt động theo cấu trúc dòng xếp hàng.

Nhược điểm:

- Trang ở lâu trong bộ nhớ lại hay được sử dụng.

- Có thể loại bỏ mất trang quan trọng mà sẽ sử dụng thường xuyên.

2/ LRU (Least Recent Used):

Cơ chế LRU sử dụng một stack hoặc gán biến đếm cho các trang để kiểm tra xem trang nào đang nằm trong bộ nhớ mà ít có yêu cầu truy cập nhất (không được sử dụng lâu nhất). Sau đó sẽ loại bỏ trang đó ra khi mà có yêu cầu nạp thêm trang mới vào. Nếu sử dụng stack thì các trang hay được sử dụng sẽ nằm ở đỉnh ngăn xếp còn các trang ít được dùng sẽ nằm ở đáy ngăn xếp.

Ưu điểm:

- Cải tiến hơn cơ chế FIFO, làm giảm số lần loại bỏ và nạp trang.

Nhược điểm:

21. Câu 21: Trình bày về các khái niệm phân phối CPU ảo và CPU thực. So sánh hai loại phân phối này. ( còn thiếu )

Trong chế độ đa chương trình, user quan niệm nhiều ctr thực hiện đồng thời nhưng khi thực hiện CPU chỉ phục vụ một ctr tại một thời điểm (CPU thực), các ctr đang thực hiện đồng thời còn lại sử dụng CPU ảo.

CPU ảo là CPU logic được phân phối cho toàn bộ tiến trình

CPU ảo tốc độ << CPU thực

22. Câu 22: Trình bày khái niệm đa luồng của quá trình. Giải thích khẳng định "giải pháp đa luồng làm tăng tính sẵn sàng của CPU".

Còn cái khái niệm ???

Sử dụng kiến trúc đa xử lý: các lợi điểm của đa luồng có thể phát huy trong kiến trúc đa xử lý, ở đó mỗi luồng thực thi song song trên một bộ xử lý khác nhau. Một quá trình đơn luồng chỉ có thể chạy trên một CPU. Đa luồng trên một máy nhiều CPU gia tăng tính đồng hành. Trong kiến trúc đơn xử lý, CPU thường chuyển đổi qua lại giữa mỗi luồng quá nhanh để tạo ra hình ảnh của sự song song nhưng trong thực tế chỉ một luồng đang chạy tại một thời điểm.

23. Câu 23: Trình bày tính mở của hệ điều hành: khái niệm, giải pháp

- Tỉnh mở: khả năng làm việc với lớp rộng lớn các phần mềm ứng dung, kết nối các hệ điều hành khác,

24. Câu 24: Xét một đĩa từ có 1000 khối đĩa được đánh chỉ số từ 0 tới 999. Trong lần di chuyển trước đây, đầu đọc đĩa đi theo chiều tăng của các khối đĩa tới khối thứ 500. Hiện thời, dòng xếp hàng nhu cầu làm việc với khối đĩa có nội dung như sau (viết theo chiều tăng của các chỉ số): 5, 125, 198, 430, 600, 605, 707, 893, 900, 950, 987. Hãy liệt kê trình tự đáp ứng nhu cầu làm việc khối đĩa (dãy khối đĩa) theo từng phương pháp (1) Phương pháp "tới các gần nhất"; (2) Phương pháp "cầu thang máy".