Ảnh dưới cho thấy chuỗi page cần xử lý của 1 tiến trình (tiến trình chỉ được cấp 3 pages), kèm theo đó là minh họa cho 1 giải thuật thay thế trang (page replacement). Những vị trí có ký hiệu F là thời điểm cần thay thế trang. Hãy cho biết tên của giải thuật thay trang.
Đáp án đúng: A
Để xác định giải thuật thay thế trang được sử dụng trong hình, chúng ta cần phân tích cách các trang được thay thế (ký hiệu F) dựa trên chuỗi trang tham chiếu và số lượng trang được cấp phát (3 trang).
- **FIFO (First-In, First-Out)**: Trang nào vào trước thì sẽ bị loại bỏ trước. Trong ví dụ này, khi trang 4 cần được đưa vào, trang 0 được thay thế (F). Tiếp theo, khi trang 1 cần được đưa vào, trang 2 được thay thế. Sau đó, trang 2 lại cần, trang 4 được thay thế. Điều này phù hợp với nguyên tắc FIFO.
- **Optimal**: Thay thế trang nào mà thời gian sử dụng tiếp theo là lâu nhất. Giải thuật này yêu cầu biết trước toàn bộ chuỗi tham chiếu.
- **LRU (Least Recently Used)**: Thay thế trang nào ít được sử dụng nhất trong quá khứ. Điều này đòi hỏi phải theo dõi lịch sử sử dụng trang.
- **SJF (Shortest Job First)**: Đây là giải thuật lập lịch cho CPU, không phải giải thuật thay thế trang.
Dựa trên việc trang 0, rồi trang 2, rồi trang 4 bị thay thế một cách tuần tự khi các trang mới cần vào, giải thuật phù hợp nhất ở đây là FIFO.
Câu hỏi liên quan
* Tiến trình (Process) được biểu diễn bằng hình tròn.
* Tài nguyên (Resource) được biểu diễn bằng hình vuông.
* Yêu cầu tài nguyên (Request Edge): Mũi tên từ tiến trình đến tài nguyên, thể hiện tiến trình đang yêu cầu tài nguyên đó.
* Cấp phát tài nguyên (Assignment Edge): Mũi tên từ tài nguyên đến tiến trình, thể hiện tài nguyên đó đã được cấp phát cho tiến trình.
Đồ thị chờ (Wait-For Graph) là một đồ thị đặc biệt, được sử dụng trong hệ thống quản lý cơ sở dữ liệu để phát hiện bế tắc (deadlock) giữa các giao dịch. Trong đồ thị này:
* Nút (Node): Đại diện cho một giao dịch (Transaction).
* Cạnh (Edge): Mũi tên từ giao dịch T1 đến giao dịch T2, thể hiện T1 đang chờ T2 giải phóng một tài nguyên nào đó.
Như vậy:
* (a) là đồ thị cấp phát tài nguyên, vì có cả tiến trình, tài nguyên, yêu cầu và cấp phát tài nguyên.
* (b) là đồ thị chờ tài nguyên, vì các nút đại diện cho tiến trình và các cạnh thể hiện sự chờ đợi giữa các tiến trình.
Đáp án đúng là A.
Trong các hệ điều hành sử dụng cả luồng nhân (kernel threads) và luồng người dùng (user threads), giải thuật điều phối CPU sẽ được áp dụng trực tiếp cho các luồng nhân. Lý do là vì kernel thread được quản lý và điều khiển bởi chính hệ điều hành, do đó bộ điều phối CPU của hệ điều hành sẽ trực tiếp chọn lựa kernel thread nào sẽ được thực thi tiếp theo. User threads nằm trên tầng ứng dụng, việc điều phối chúng (nếu có) sẽ do thư viện luồng hoặc tiến trình thực hiện, nhưng cuối cùng vẫn phải thông qua kernel để truy cập CPU.
Để trả lời câu hỏi này, chúng ta cần hiểu rõ về các mô hình ánh xạ user thread (luồng người dùng) vào kernel thread (luồng nhân) và cách chúng ảnh hưởng đến tranh chấp CPU.
- Mô hình One-to-One: Mỗi user thread được ánh xạ tới một kernel thread riêng biệt. Do đó, tranh chấp CPU xảy ra trực tiếp giữa các kernel thread, mỗi thread đại diện cho một user thread.
- Mô hình Many-to-One: Nhiều user thread được ánh xạ tới một kernel thread duy nhất. Trong mô hình này, chỉ một user thread có thể truy cập kernel tại một thời điểm, và tranh chấp CPU xảy ra chủ yếu ở mức user thread, khi các user thread phải tranh giành để được sử dụng kernel thread duy nhất.
- Mô hình One-to-Many: Đây không phải là một mô hình ánh xạ thread tiêu chuẩn.
- Mô hình Many-to-Many: Nhiều user thread được ánh xạ tới nhiều kernel thread. Tranh chấp CPU xảy ra ở mức kernel thread, nhưng không giới hạn ở các kernel thread đại diện trực tiếp cho user thread đang chạy. Các kernel thread có thể tranh chấp để thực hiện các tác vụ hệ thống khác.
Như vậy, mô hình mà tranh chấp CPU chỉ xảy ra tại các kernel threads là mô hình One-to-One, vì mỗi user thread có một kernel thread riêng.
* Fixed priority scheduling (A): Trong giải thuật này, mỗi hàng đợi được gán một mức độ ưu tiên cố định. CPU sẽ thực hiện các process trong hàng đợi có độ ưu tiên cao nhất trước, sau đó mới đến các hàng đợi có độ ưu tiên thấp hơn. Điều này phù hợp với yêu cầu của bài toán, khi các process hiển thị trên màn hình (Foreground queue) cần được ưu tiên hơn các process chạy nền (Background queue).
* Priority scheduling (B): Giải thuật này gán độ ưu tiên cho từng process riêng lẻ, không phân biệt hàng đợi. Mặc dù có thể sử dụng Priority scheduling để ưu tiên các process hiển thị trên màn hình, nhưng nó không tận dụng được cấu trúc hàng đợi đã được phân chia, và có thể dẫn đến việc một process chạy nền có độ ưu tiên cao hơn một process hiển thị trên màn hình, gây ra trải nghiệm không tốt cho người dùng.
* Time slice scheduling (C): Giải thuật này chia CPU thành các khoảng thời gian nhỏ (time slice) và cấp phát cho mỗi process một khoảng thời gian. Nó phù hợp cho các hệ thống chia sẻ thời gian, nhưng không đảm bảo được việc ưu tiên các process hiển thị trên màn hình.
* Round Robin scheduling (D): Tương tự như Time slice scheduling, Round Robin scheduling cũng chia CPU thành các khoảng thời gian và cấp phát cho mỗi process một khoảng thời gian theo vòng tròn. Nó không phù hợp cho việc ưu tiên các process hiển thị trên màn hình.
Như vậy, giải thuật Fixed priority scheduling là phù hợp nhất trong trường hợp này, vì nó cho phép hệ điều hành ưu tiên các process hiển thị trên màn hình hơn các process chạy nền, đảm bảo trải nghiệm tốt cho người dùng.
