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

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:

Nguyên tắc: điều phối cho thời gian chờ đợi trung bình cho mọi quá trình là như nhau, bình đẳng.

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. - Không thể chuyển từ trạng thái sử dụng về trạng thái chuẩn bị. Tài nguyên CPU không bị phân phối lại.

Ưu điểm:

- Thao tác đơn giản

- Chi phí tổ chức thực hiện thấp nhất

Nhược điểm :

- 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 chờ đợi trung bình cũng tăng theo.

- Thời gian chờ trung bình không phải là nhỏ nhất

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. Do người dùng hoặc do ngầm đị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 khi có các phần tử khác được thêm vào sẽ có xu thế đẩy các quá trình dài về sau.

- Số bất định với số thực tế.

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ào 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. Ưu 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 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ớ trong cho một yêu cầu phân phối hiện tại.Sau đó khi chương trình được thực hiện thì phần bộ nhớ đó lại được chuyển vào.

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. Nhưng mô đun chương trình thuộc về hệ điều hành.

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

- Swap out :định hướng chọn quá trình để đưa ra đĩa từ là quá trình đanh bị đỉnh chỉ mà chiếm một vùng nhớ đủ lớn để có thể phân phối lại cho quá trình đanh yêu cầu.

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

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

Việc swap out, swap in đối với quá trình ảnh hưởng đến thời gian thực hiện quá trình và tốc độ vào ra với bộ nhớ ngoài.

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ử hoạt động như sau: sau khi thông điệp được băm. Người gửi mã hóa giá trị băm thành mã riêng rồi gửi thông điệp cùng giá trị băm đã mã hóa cho người nhận.Người nhận nhận được thông điệp sẽ giải mã bằng khóa công khai của người gửi, đồng thời băm thông điệp của Alice thành một xâu.So sánh 2 giá trị băm này, nếu giống nhau thì OK.

Vì private key chỉ mình người gửi biết nên dù thông điệp bị thay đổi có giá trị băm mới nhưng không thể giả mạo được.

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.

- Vai trò: Nó cung cấp các lệnh đặc thù để 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 (API). Tối ưu hiệu suất tổng thể của hệ thống với phương pháp điểu khiển tích hợp.

Ý 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.

Trong MS-DOS, đĩa từ được thể hiện bằng các đĩa logic, có cấu trúc theo quy định và được đặt tên xác định (A, B, C ...). Các đĩa logic có cùng một cấu trúc tổ chức như dưới đây:

BOOT ROOT DATA

FAT1 FAT2

- Vùng BOOT là sector đầu tiên trong đĩa thường được chia làm 2 phần: phần chứa thông tin về đĩa logic đó, và phần chương trình tải hệ điều hành vào làm việc

- Phần ngay sau BOOT là vùng đi trước FAT trong đĩa logic bao gồm những thông tin trợ giúp việc tổ chức và truy nhập thông tin trên đĩa từ.

- Bảng định vị file FAT là vùng chứa thông tin định vị các vùng chứa nội dung các file trên đĩa, thường có 2 bảng FAT giống nhau để đảm bảo an toàn

Vùng ROOT chứa nội dung thư mục gốc.

- Vùng DATA chứa nội dung các file có trên đĩa.

§ Trong MS-DOS, file được lưu trữ trên một tập các cluster của đĩa từ.

§ Thông tin về các File được lưu trữ tại các thư mục. Trừ thư mục gốc có vùng dành riêng, còn các thư mục khác được lưu trữ như các File trên đĩa. Trong thư mục, thông tin về một File được lưu trữ trong điểm vào File. Mỗi điểm vào File có độ dài 32 byte có cấu trúc như sau:

- 0 - 0AH: tên file

- 0BH: thuộc tính của file

- 0CH - 15H: dành riêng cho DOS

- 16H - 17H: thời gian

- 18H - 19H: ngày

- 1AH - 1BH: số hiệu cluster đầu tiên chứa nội dung File

- 1CH - 1FH: độ dài

Ø Gom các phần rời rạc của File càng lại gần càng tốt vì: thời gian để di chuyển đầu đọc chiếm tỉ trọng rất lớn khi đọc các khối của một File, khi các phần của file được gom lại gần nhau, đầu đọc sẽ di chuyển ít hơn, từ đấy tiết kiệm đáng kể thời gian đọc file

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 ?

Khi virus nhiễm vào file của người sử dụng máy tính, file đó bị lớn ra về kích thước và đó là một trong những điểm để nhận biết file bị nhiễm virus. Do đó, để tránh bị phát hiện, virus nén file chứa nó lại làm cho kích thước của file sau khi nén + kích thước của virus ≈ kích thước file ban đầu.

Khi chương trình của người dùng được gọi, virus sẽ được thực thi đầu tiên, nó thực hiện giải nén chương trình của người dùng, sau đó để chương trình người dùng thực hiện.

(Chắc chắn) Virus máy tính có thể nén cả chương trình mang và bản thân virus có kèm thao mã hóa. (Tau đoán) Khi virus nén cả bản thân nó thì nó khó bị phát hiện hơn bởi các chương trình antivirus.

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).

Gồm mô đun điều phối chính và monitor

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.

Gồm Mô đun điều phối và lập lịch

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:

Trong đó người ta dùng một vùng, được gọi là Bitmap, để trình bày tình trạng rỗi/bận của tất cả các khối trên đĩa. Mỗi khối trên đĩa được tương ứng với một bít trong vùng Bitmap và tình trạng rỗi/bận của khối đó được xác định bằng giá trị 0/1 của bit tương ứng.

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ớ

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.

Giải pháp: để có thể làm được điều này, hệ điều hành cần biết về các cấu trúc của các thiết bị phần cứng khác nhau đồng thời trừu tượng hóa các điểm khác biệt đủ để lớp phầm mềm cao hơn có thể sử dụng đó. Đó là Hardware Abstraction Layer hoặc Service Provider Interface.

Ví dụ : 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 FIFO, 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:

- Khó thực hiện chính xác. Phức tạp hơn so với FIFO

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. ( không biết còn thiếu hay không)

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).

Như vậy 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.

Việc phân phối CPU ảo chỉ xảy ra một lần: chương trình xuất hiện rồi kết thúc, không có sự phân phối lại CPU ảo. CPU thực được phân phối nhiều lần cho một chương trình.

CPU ảo thể hiện tính mở của hệ điều hành.CPU thực thể hiện tính chất hệ điều hành là một hệ quản trị tài nguyên.

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".

Đa luồng của quá trình là các thành phần được thực hiện đồng thời và song song.

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. Trong hệ có 1 CPU, đa luồng làm tăng tính sẵn sàng của chương trình, sử dụng hệ thống một cách triệt để hơn: CPU ở trong trạng thái làm việc nhiều hơn do khi luồng này tạm dừng để chờ tài nguyên thì luồng khác có thể hoạt động

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,

- Giải pháp:

Sử dụng vi nhân:

a. Vi nhân: Nhân tối thiểu vạn năng, trên dó dịch vụ HĐH chuẩn thi hành=Nhân tối thiểu phụ thuộc nền cứng + tập thi hành độc lập phần cứng (dịch vụ hệ thống) trong Bộ giao diện trình ứng dụng (API: Application Program Interface). API cung cấp tính mở cho ứng dụng mức cao. (nhiều nhà phát triển có thể viết chương trình cho hệ điề hành)

b. Cung cấp môi trường chứa điều kiện cần và đủ để cấu trúc HĐH/hệ thống con đáp ứng nhu cầu bất kỳ.

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".

500->430->600->605->707->893->900->950->987->198->125->5

500->600->605->707->893->900->950->987->430->198->125->5