Phương pháp … không đòi hỏi công cụ đặc biệt, do đó có thể tổ chức bằng một ngôn ngữ bất kỳ và thực hiện trên mọi hệ thống. Tuy nhiên độ phức tạp sẽ tăng khi số tiến trình nhiều hoặc số lượng đoạn tới hạn trong các tiến trình lớn. Hãy lựa chọn đáp án đúng điền vào chỗ thiếu trên?

Phương pháp được mô tả là "Phương pháp kiểm tra và xác lập" (Test and Set). Trong phương pháp này, mỗi tiến trình chỉ cần kiểm tra quyền truy cập vào đoạn tới hạn một lần. Nếu quyền được cấp, tiến trình sẽ vào đoạn tới hạn. Nếu không, nó sẽ phải xếp hàng đợi và không ở trạng thái tích cực (busy waiting) trong khi chờ đợi. Các phương pháp khác như khóa trong (lock), dùng thư ký (secretary), đèn hiệu (semaphore) không phù hợp với mô tả này.

Câu hỏi yêu cầu tìm phương án *không* phải thuật toán lập lịch CPU.

* A. FCFS (First-Come, First-Served): Là thuật toán lập lịch CPU cơ bản, tiến trình nào đến trước sẽ được thực hiện trước.
* B. SSTF (Shortest Seek Time First): Là thuật toán lập lịch đĩa, chọn yêu cầu đọc/ghi có thời gian tìm kiếm ngắn nhất tiếp theo. Nó không phải là thuật toán lập lịch CPU.
* C. SJF (Shortest Job First): Là thuật toán lập lịch CPU, tiến trình nào có thời gian thực hiện ngắn nhất sẽ được thực hiện trước.
* D. SRT (Shortest Remaining Time): Là thuật toán lập lịch CPU, chọn tiến trình có thời gian còn lại ngắn nhất để thực hiện. Đây là phiên bản preemptive của SJF.

Vậy, đáp án đúng là B vì SSTF là thuật toán lập lịch đĩa, không phải thuật toán lập lịch CPU.

Phương pháp RR (Round Robin) là một thuật toán lập lịch CPU, trong đó mỗi tiến trình được cấp một khoảng thời gian CPU nhất định, gọi là lượng tử thời gian (time quantum). Các tiến trình được đặt trong một hàng đợi theo kiểu vòng tròn. Khi một tiến trình hết lượng tử thời gian, nó sẽ bị ngắt và đưa về cuối hàng đợi, và CPU sẽ chuyển sang tiến trình tiếp theo trong hàng đợi. Điều này đảm bảo rằng mọi tiến trình đều nhận được một lượng thời gian CPU công bằng.

Để giải bài toán này, ta cần xét thứ tự thực hiện các tiến trình theo thuật toán MLFQ (Multi-Level Feedback Queue) với các hàng đợi và thuật toán con như sau:

* Hàng đợi 1: P1 và P2 sử dụng RR (Round Robin) với quantum q=3.
* Hàng đợi 2: P3 và P4 sử dụng SJF (Shortest Job First).

Giả sử hàng đợi 1 được ưu tiên thực hiện trước. Ta có bảng thời gian thực hiện như sau:

| Tiến trình | Thời gian thực hiện | Thời gian đến (giả sử đều đến 0) | Hàng đợi |
| :-------- | :----------------- | :------------------------------- | :------ |
| P1 | 6 | 0 | 1 |
| P2 | 8 | 0 | 1 |
| P3 | 3 | Sau khi hàng đợi 1 kết thúc | 2 |
| P4 | 2 | Sau khi hàng đợi 1 kết thúc | 2 |

Hàng đợi 1 (RR, q=3):

* P1 chạy 3 đơn vị thời gian, còn lại 3 đơn vị. P2 chạy 3 đơn vị thời gian, còn lại 5 đơn vị.
* P1 chạy tiếp 3 đơn vị thời gian (hoàn thành). Thời gian hoàn thành của P1 là 3 + 3 = 6.
* P2 chạy tiếp 3 đơn vị thời gian, còn lại 2 đơn vị. Thời gian hoàn thành của P2 đến nay là 3 + 3 + 3 = 9.
* P2 chạy 2 đơn vị thời gian cuối (hoàn thành). Thời gian hoàn thành của P2 là 9 + 2 = 11.

Thời gian hàng đợi 1 kết thúc là 11.

Hàng đợi 2 (SJF):

Vì P3 và P4 chỉ được thực hiện sau khi hàng đợi 1 kết thúc, ta áp dụng SJF tại thời điểm 11.

* P4 (thời gian 2) được thực hiện trước. Thời gian hoàn thành của P4 là 11 + 2 = 13.
* P3 (thời gian 3) được thực hiện sau. Thời gian hoàn thành của P3 là 13 + 3 = 16.

Tính thời gian chờ:

* Thời gian chờ của P1: 0
* Thời gian chờ của P2: 6 -0 =6
* Thời gian chờ của P3: 13-11= 2
* Thời gian chờ của P4: 11-11=0

Thời gian chờ trung bình = (0 + 6 + 13-11 + 11-11) / 4 = (0+6+2+0)/4 = 8/4 = 2+ (3+2)/4 = 2 +5/4=2+1.25 = 2

Vậy, theo cách tính trên có lẽ không có đáp án nào đúng cả. Cần xem xét lại việc tính toán hoặc giả định về thời điểm đến của các tiến trình.

Tuy nhiên, nếu chúng ta tính thời gian chờ từ 0, có thể tính lại như sau:
P1: 0
P2: 3
P3: 11
P4: 11
Thời gian chờ trung bình = (0+3+11+11)/4 = 25/4 = 6.25. Vậy cũng không có đáp án đúng.

Để có một đáp án gần đúng, chúng ta cần phải xem xét lại đề bài và các giả định, đặc biệt là thời điểm đến của tiến trình và cách hàng đợi được xử lý khi chuyển giao. Trong trường hợp này, không có đáp án nào khớp với kết quả tính toán.

Nếu đề bài yêu cầu tính thời gian chờ trung bình sau khi tất cả các tiến trình hoàn thành (tức là từ thời điểm 0 đến khi tất cả hoàn thành), ta có thể làm như sau:

P1 hoàn thành tại 6, thời gian chờ = 0
P2 hoàn thành tại 11, thời gian chờ = 3
P4 hoàn thành tại 13, thời gian chờ = 11
P3 hoàn thành tại 16, thời gian chờ = 13
Tổng thời gian chờ = 0+3+11+13 = 27
Thời gian chờ trung bình = 27/4 = 6.75

Như vậy, đáp án đúng nhất trong các đáp án đã cho là không có đáp án nào đúng.

Để giải bài toán này, ta cần phân tích thứ tự thực hiện của các tiến trình theo thuật toán MLFQ, SRT và FCFS. Vì P1 và P2 ở hàng đợi 1 dùng SRT (Shortest Remaining Time), P3 và P4 ở hàng đợi 2 dùng FCFS (First Come First Serve).

- Ban đầu: P1 (6), P2 (8), P3 (3), P4 (2).
- Thời điểm 0: P1 và P2 ở hàng đợi 1 được ưu tiên. SRT chọn P1 vì có thời gian thực hiện ngắn hơn so với P2. P1 chạy.
- Thời điểm 2: P4 (2) đến.
- Thời điểm 2: P1 vẫn đang chạy (còn 4 đơn vị). P2 chưa được chạy, P3 và P4 ở hàng đợi 2 vẫn phải chờ.
- Thời điểm 2: Vì P4 có thời gian ngắn hơn P1 còn lại, nên P4 được đưa lên để chạy.
- Thời điểm 4: P4 hoàn thành. P3 bắt đầu chạy (FCFS).
- Thời điểm 7: P3 hoàn thành. Lúc này P1 và P2 tiếp tục chạy, áp dụng SRT, P1 có 4 đơn vị còn lại, P2 có 8 đơn vị, nên P1 được chạy.
- Thời điểm 11: P1 hoàn thành. P2 được chạy.

Vậy thời gian chờ của P1 là thời gian từ khi P1 bắt đầu đến khi P4 đến (2) + thời gian P4 và P3 chạy (2+3) = 2. Do P1 đã thực hiện 2 đơn vị trước đó và bị ngắt bởi P4 và P3 nên phải chờ P4 và P3 thực hiện xong. Sau đó P1 lại tiếp tục được thực hiện. Vậy thời gian chờ của P1 là 2.
Như vậy, đáp án là A. 2,3.