ÔN TẬP NGUYÊN LÝ HỆ ĐIỀU HÀNH

Câu 2 Khái niệm tiến trình, phân biệt giữa tiến trình và chương trình. Các loại tiến

Trình :

1.1 Khái niệm tiến trình:

Tiến trình là một ctr đang xử lý(hoạt động, thực hiện), sở hữu một con trỏ lệnh, tập các thanh ghi và các biến. Để hoàn thành tác vụ, tiến trình cần tài nguyên: CPU, bộ nhớ, thiết bị I/O,...

 Một tiến trình gồm:

 Mã nguồn chương trình (code) (không thay đổi)

 Dữ liệu (data)

 Bộ đếm CT (Program Counter)

 Ngăn xếp (Stack)

 Giá trị ở các thanh ghi (Register values)

1.2 Phân biệt giữa tiến trình và chương trình:

Chương trình là một thực thể thụ động chứa lệnh & dữ liệu để tiến hành một tác vụ( công việc). Khi thực hiện các lệnh, chương trình chuyển thành tiến trình.

 Tiến trình là một thực thể hoạt động

1.3 Các loại Tiến trình

- Tiến trình tuần tự:

Hai hay nhiều tiến trình gọi là tuần tự khi điểm kết thúc của tiến trình này là sự bắt đầu của tiến trình khác.

- Tiến trình song song

Điểm bắt đầu của tiến trình này nằm giữa điểm bắt đầu và kết thúc của tiến trình khác.

- Tiến trình có quan hệ thông tin

Trao đổi thông tin qua một vùng nhớ được biểu diễn như một hộp thư có thể trao đổi thông tin qua đó.

-Tiến trình độc lập

Hai hay nhiều tiến trình gọi là độc lập khi chúng không có quan hệ thông tin với nhau, hoạt động của tiến trình này không ảnh hưởng đến hoạt động của tiến trình khác và ngược lại.

-Tiến trình cha và tiến trình con

Một tiến trình được sinh ra từ một tiến trình khác thì được gọi là sự phân cấp của tiến trình hay được gọi là tiến trình cha và tiến trình con

-Tiến trình đồng mức

Thể hiện các tiến trình đó truy nhập tài nguyên dung chung theo nguyên tắc lần lượt.

Câu 3 Trình bày hoạt động và các trạng thái của Tiến trình .Mô tả Mô hình của tiến trình

1 Hoạt động và các trạng thái của tiến trình

1.1 Hoạt động (quá trình chuyển trạng thái):

 Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running. Trong khi đó, nhiều tiến trình có thể ở trạng thái waiting hay ready.

 Tiến trình mới tạo được đưa vào hệ thống, được cung cấp đủ tài nguyên ở trạng thái ready(chờ được phân phối CPU để thực hiện)

 Khi tiến trình đang thực hiện(running), nó có thể chuyển sang trạng thái:

 Kết thúc(terminal) nếu thực hiện xong

 Chờ(waiting) tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác nhập/xuất

Sẵn sàng(ready) khi xảy ra ngắt để chuyển CPU cho tiến trình có mức ưu tiên cao hơn. Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU hoặc hết thời gian chiếm hữu CPU

 Bộ điều phối chọn một tiến trình khác có trạng thái ready cho xử lý.

Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác I/O tiến trình đang đợi(có trạng tháiwaiting) hoàn tất, tiến trình chuyển sang ready

1.2 Các trạng thái của tiến trình:

 Trạng thái của tiến trình tại một thời điểm xác định bởi hoạt động của tiến trình tại thời điểm đó.

 Trong quá trình sống, tiến trình có thể thay đổi trạng thái do các nguyên nhân:

 Phải dừng hoạt động do hết thời gian

 Đợi một thao tác I/O hoàn tất

 Phải chờ một sự kiện xảy ra

 Tại một thời điểm, tiến trình có thể có một trong các trạng thái:

 new: Tiến trình đang được tạo

 running: Tiến trình đang chiếm hữu CPU & thực hiện các lệnh.

 waiting: Tiến trình đang chờ cung được cấp tài nguyên hoặc chờ một sự kiện nào đó xuất hiện để chuyển sang trạng thái sẵn sàng.

ready: Tiến trình ở trạng thái sẵn sàng, được phân phổi đủ tài nguyên cần thiết, đang chờ đến lượt được thực hiện theo cơ chế lập lịch của hệ điều hành.

 terminated: Tiến trình kết thúc. Nó không biến mất cho đến khi một tiến trình khác đọc được trạng thái thoát của nó.

2 Mô tả mô hình của tiến trình:

 Cách thực hiện:

 Chia chương trình thành nhiều tiến trình

 Khởi tạo và đưa vào hệ thống nhiều tiến trình (của một hoặc của nhiều chương

trình khác nhau )

 Cấp phát đầy đủ tài nguyên (trừ processor) cho tiến trình và đưa các tiến trình

sang trạng thái sẵn sàng.

 Bắt đầu cấp processor cho một tiến trình trong số các tiến trình ở trạng thái sẵn

sàng để tiến trình này hoạt động

 Sau một khoảng thời gian nào đó hệ điều hành thu hồi processor để cấp cho một

tiến trình sẵn sàng khác

 Cứ như thế cho đến khi tất cả các tiến trình mà hệ điều hành khởi tạo đều hoạt

động và kết thúc được.

 Khoảng thời gian chuyển processor từ tiến trình này sang tiến trình khác (hay giữa

hai lần cấp phát processor của một tiến trình) là rất nhỏ nên các tiến trình có cảm giác luôn được sở hữu processor (logic)

 Có cảm giác các tiến trình/ chương trình hoạt động song song

 Hiện tượng này được gọi là sự song song giả.

Câu 5 Khái niệm Tắc nghẽn, Điều kiện hình thành Tắc nghẽn?

1 Khái niệm tắc nghẽn

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.

2 Điều kiện

- Tồn tại tài nguyên găng

- Có tổ chức sắp xếp hàng đợi

- Không phân phối lại tài nguyên

- Tồn tại hiện tượng chờ đợi vòng tròn

Câu 6 Phương pháp xử lý tắc nghẽn.Đánh giá hướng tiếp cận xử lý?

1.Phương pháp xử lý:

• Sử dụng phương thức để ngăn ngừa hoặc tránh, đảm bảo hệ thống không bao giờ đi vào trạng thái bế tắc.

• Cho phép hệ thống đi vào trạng thái bế tắc rồi khôi phục lạià nhận biết và khắc phục

• Dự báo và tránh

2. Đánh giá hướng tiếp cận:

Phòng tránh tắc nghẽn : tuân thủ một vài nghi thức bảo đảm hệ thống kh�ng

bao giờ l�m vào trạng thái tắc nghẽn.

Phát hiện tắc nghẽn : khi có tắc nghẽn xảy ra, phát hiện các tiến trình liên

quan và tìm cách phục hồi.

Bỏ qua tắc nghẽn : xem như hệ thống không bao giờ lâm vào trạng thái

tắc nghẽn

Câu 7 :Thuật toán kiểm tra trạng thái an toàn của hệ thống?

Giải thuật để xác định hệ thống ở trạng thái an toàn hay không có thể được mô tả

như sau:

1) Gọi Work và Finish là các vector có chiều dài m và n tương ứng. Khởi tạo

Work:=Available và Finish[i]:=false cho i = 1, 2, ...,n.

2) Tìm i thỏa:

a) Finish[i] = false

b) Need i ≤ Work.

Nếu không có i nào thỏa, di chuyển tới bước 4

3) Work:=Work + Allocation i

Finish[i] := true

Di chuyển về bước 2.

4) Nếu Finish[i] = true cho tất cả i, thì hệ thống đang ở trạng thái an toàn.

Giải thuật này có thể yêu cầu độ phức tạp mxn2 thao tác để quyết định trạng thái

là an toàn hay không.

Câu 8 Trình bày các chiến lược lập lịch CPU .Phân biệt lập lịch độc quyền và không độc quyền. FCFS, SJC, RR giải thuật nào thực hiện lập lịch độc quyền, giải thuật nào thực hiện lập lịch không độc quyền?

1.1 Các chiến lược lập lịch CPU

 FCFS (First Come First Served)

􀁺 Tiến trình nào có yêu cầu sử dụng CPU trước sẽ được thực hiện trước.

􀁺 Ưu điểm: Thuật toán đơn giản nhất

􀁺 Nhược điểm: Hiệu quả của thuật toán phụ thuộc vào thứ tự của các tiến trình trong hàng chờ, vì thứ tự này ảnh hưởng rất lớn đến thời gian chờ trung bình (average waiting time).

 SJF (Shortest Job First)

Gải thuật Shortest-Job-First (SJF)

􀂄 Gắn với mỗi tiến trình là thời gian sử dụng CPU tiếp sau của nó.Thời gian này được sử dụng để lập lịch các tiến trình với thờigian ngắn nhất.

􀂄 Hai phương pháp:

􀁺 không ưu tiên trước (non-preemptive)- một tiến trình nếu sử dụng

CPU thì không nhường cho tiến trình khác cho đến khi nó kết thúc.

􀁺 có ưu tiên trước (preemptive)- nếu một tiến trình đến có thời giansử dụng CPU ngắn hơn thời gian còn lại của tiến trình đang thựchiện thì ưu tiên tiến trình mới đến trước. Phương pháp này cònđược gọi là Shortest-Remaining-Time-First (SRTF).

􀂄 SJF là tối ưu - cho thời gian chờ đợi trung bình của các tiến trình là nhỏ nhất..

d.Round Robin(RR)

-Phục vụ vòng tròn.

-CPU luân phiên phục vụ các tiến trình trong 1 khoảng thời gian như nhau và khá nhỏ(10 đến 100 micro giây)

1.2 Phân biệt lập lịch độc quyền và không độc quyền:

Độc quyền (nonpreemptive) Không độc quyền (preemptive)

Khi tiến trình được phân phối CPU, nó sẽ sử dụng CPU cho đến khi nó giải phóng CPU bằng cách kết thúc hoặc chuyển sang trạng thái chờ.

Khi một tiến trình có độ ưu tiên cao hơn, nó có thể đẩy tiến trình đang được thực hiện để giành quyền điều khiển CPU. Tiến trình đang được thực hiện sẽ được chuyển sang trạng thái chờ.

Trong 2 giải thuật thực hiện lập lịch: FCFS, SJC, RR, giải thuật FCFS là thực hiện lập lịch độc quyền; giải thuật SJC có thể vừa độc quyền có thế không độc quyền; giải thuật RR thực hiện lập lịch độc quyền

Câu 9Phân biệt lập lịch với hàng đợi đa mức và hàng đợi đơn mức. Trong lập lịch hàng đợi đa mức, khi một tiến trình ở hàng đợi có mức ưu tiên thấp được chọn để thực hiện. Tiến trình này đang thực hiện thì có một tiến trình đi vào hàng đợi có mức ưu tiên cao hơn. Quá trình tiếp theo sẽ diễn ra thế nào? Tại sao?

1 Phân biệt lập lịch với hàng đợi đa mức và hàng đợi đơn mức:

 Hàng đợi đơn mức: tại một thời điểm chỉ có một hàng đợi sẵn sàng.

 Hàng đợi đa mức: chia ready queue thành nhiều queue, các tiến trình trên cùng queue có cùng độ ưu tiên., tức là tại một thời điểm có nhiều hàng đợi sẵn sàng.

2Trong lập lịch hàng đợi đa mức, khi một tiến trình ở hàng đợi có mức ưu tiên thấp được chọn để thực hiện. Tiến trình này đang thực hiện thì có một tiến trình đi vào hàng đợi có mức ưu tiên cao hơn thì tiến trình có mức ưu tiên cao hơn cũng không ảnh hưởng đến tiến trình đang chạy có mức ưu tiên thấp hơn. Khi tiến trình có mức ưu tiên thấp hơn thực hiện xong, các tiến trình trong cùng Queue với tiến trình này sẽ được thực hiện tiếp. Đến khi Queue rỗng, các Queue có mức ưu tiên cao hơn chứa tiến trình đi vào sẽ thực hiện trước. Khi các Queue có độ ưu tiên cao hơn thực hiện xong (rỗng) thì tiến trình sẽ trở lại trạng thái bình thường và tiếp tục thực hiện.

Câu10 Đoạn găng là gì. Một tiến trình đang ở trong đoạn găng có thể có các trạng thái nào. Giải thích?

Đoạn Găng là đoạn mã lệnh có khả năng xảy ra mâu thuẫn khi truy xuất tài nguyên chung

Một tiến trình đang ở trong đoạn Găng có thể có các trạng thái Running và Ready bởi vì đoạn Găng sẽ quyết định chỉ cho một tiến trình hợp lệ vào miền Găng để thực hiện các lệnh trong miền này (tức là đang ở trạng tháiRunning ), còn lại các tiến trình khác phải chờ khi tiến trình ở trong miền Găng thực hiện xong mới có thể thực hiện (tức là đang ở trạng thái Ready) và chúng không thể vào trong miền Găng gây xung đột trong quá trình xử lý.

Câu 11 Phân biệt mô hình phân phối nhớ liên tục và phân phối nhớ gián đoạn. Chỉ ra sự phân mành trong và phân mành ngoài trong kĩ thuật phân vùng cố định và phân vùng động , phân đoạn đơn , phân trang đơn.

1 Phân biệt mô hình phân phối nhớ liên tục và phân phối nhớ gián đoạn:

Đối với mô hình phân phối gián đoạn thì không gian địa chỉ logic của một tiến trình có thể không kề nhau; tiến trình được phân phối bộ nhớ vật lý bất kỳ lúc nào khi bộ nhớ sẵn có. Còn đối với mô hình phân phối bộ nhớ liên tục thì bộ nhớ được chia thành các partition (phân vùng or miền or chương..) cố định; tên partition, địa chỉ, dung lượng được gán trong quá trình khởi tạo hệ điều hành.

2 Phân mành ngoài và phân mành trong:

-Kĩ thuật phân vùng cố định: Có phân mành trong vì một tiến trình được phân phối kích thước nhỏ hơn so với dung lượng của nó.

- Phân vùng động: Không phân mành trong do tiến trình chỉ được phân phối kích thước bằng dung lượng của nó. Có phân mành ngoài.

- Phân trang: Phân mành trong khi kích thước tiến trình nhỏ hơn kích thước 1 trang. Không

có phân mành ngoài

- Phân đoạn: Phân mành trong khi kích thước trong thay đổi. Có phân mành ngoài

khi vùng rỗi nhỏ hơn đoạn cần thiết .

Câu 12 Tư tưởng của Overlay và Swapping

- Overlay: Chỉ giữ trong bộ nhớ những lệnh và dữ liệu cần đến tại mọi thời điểm( thường là các module tải) để giảm không gian nhớ liên tục dành cho ctr.

- Swapping: Sử dụng một thiết bị nhớ thứ cấp đủ lớn (Backing Store) để cung cấp bản sao của tất cả hình ảnh bộ nhớ cho tất cả người sử dụng. Trong các hệ điều hành sử dụng swapping, tồn tại module hệ thống swapper có chức năng: chọn tiến trình swap out (chọn tiến trình để đưa ra backing store), chọn tiến trình swap in(chọn tiến trình từ backing store để đưa vào bộ nhớ trong), định vị & quản lý không gian chuyển

Câu 13 Trình bày các kỹ thuật cấp phát bộ nhớ : Kỹ thuât phân vùng cố đình , phân vùng động , phân đoạn đơn , phân trang đơn.

1. Kỹ thuật phân vùng cố định (Fixed Partitioning)

-Quản lý bộ nhớ với những phân đọan cố định .Hệ điều hành chia bộ nhớ thành n vùng nhớ cố định( có thể không bằng nhau)

-Việc phân chia này được thực hiện vào lúc khởi động hệ thống và không thay đổi suốt quá trình chạy.Với tổ chức như vậy cần duy trì một hàng đợi duy nhất để lưu trữ những tiến trình chưa được cấp phát bộ nhớ

-Tất cả tiến trình được đặt trong một hàng đợi duy nhất. Khi có một phân vùng tự do , tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng này và cho xử lý.

-Nếu kích thước của tiến trình không vừa đúng bằng kích thước phân vùng chứa nó, phần bộ nhớ không sử dụng đến trong phân vùng sẽ bị lãng phí xảy ra hiện tượng phân mảnh nội vi.

-Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng.Vấn đề bảo vệ giữa các phân vùng: Để bảo vệ cần tổ chức hai thanh ghi : thanh ghi nền và thanh ghi giới hạn.

-Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước của tiến trình

- Sau đó mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi được cấp phát cho nó.

2. Kỹ thuật phân vùng động (Dynamic Partitioning)

- Số lượng các phân vùng trên bộ nhớ và kích thước của mỗi phân vùng là có thể thay đổi.

- Phần user program trên bộ nhớ không được phân chia trước mà nó chỉ được ấn định sau khi đã có một tiến trình được nạp vào bộ nhớ chính. -Khi có một tiến trình được nạp vào bộ nhớ nó được hệ điều hành cấp cho nó không gian vừa đủ để chứa tiến trình, phần còn lại để sẵn sàng cấp cho tiến trình khác sau này.

-Khi một tiến trình kết thúc nó được đưa ra ngoài và phần không gian bộ nhớ mà tiến trình này trả lại cho hệ điều hành sẽ được hệ điều hành cấp cho tiến trình khác, cả khi tiến trình này có kích thước nhỏ hơn kích thước của không gian nhớ trống đó.

-Khi có một tiến trình cần được nạp vào bộ nhớ mà trong bộ nhớ có nhiều hơn một khối nhớ trống (Free Block) có kích thước lớn hơn kích thước của tiến trình đó, thì hệ điều hành phải quyết định chọn một khối nhớ trống phù hợp nào để nạp tiến trình sao cho việc lựa chọn này dẫn đến việc sử dụng bộ nhớ chính là hiệu quả nhất.

-Có 3 thuật toán mà hệ điều hành sử dụng trong trường hợp này, đó là: Best-fit, First-fit, và Next-fit. Cả 3 thuật toán này đều phải chọn một khối nhớ trống có kích thước bằng hoặc lớn hơn kích thước của tiến trình cần nạp vào, nhưng nó có các điểm khác nhau cơ bản sau đây:

-Best-fit: chọn khối nhớ có kích thước vừa đúng bằng kích thước của tiến trình cần được nạp vào bộ nhớ.

- First-fit: trong trường hợp này hệ điều hành sẽ bắt đầu quét qua các khối nhớ trống bắt đầu từ khối nhớ trống đầu tiên trong bộ nhớ, và sẽ chọn khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình.

- Next-fit: tương tự như First-fit nhưng ở đây hệ điều hành bắt đầu quét từ khối nhớ trống kế sau khối nhớ vừa được cấp phát và chọn khối nhớ trống kế tiếp đủ lớn để nạp tiến trình.

Câu 14 . Phân biệt giữa phân đoạn và phân trang.

- Phân đoạn: Một chương trình là một tập hợp các đoạn. Mỗi đoạn là một đơn vị logic như là: main program, procedure, function, method, object, local variables, global variables, common block, stack.

- Phân trang: Không gian địa chỉ logic của một tiến trình có thể không kề nhau; tiến trình được phân phối bộ nhớ vật lý bất kỳ lúc nào khi bộ nhớ sẵn có.

Câu 15 Khái niệm kỹ thuật bộ nhớ ảo và cài đặt . Định nghĩa Page fault.Thay trang diễn ra khi nào .Các bước xử lý thay trang.

1. Bộ nhớ ảo : sử dụng kỹ thuật phân trang theo yêu cầu, kết hợp thêm kỹ thuật swapping để mở rộng bộ nhớ chính. Tách biệt không gian địa chỉ và không gian vật lý, nhờ đó có thể xử lý các chương trình có kích thước lớn hơn bộ nhớ vật lý thật sự.

2. Cài đặt :

 Kỹ thuật phân trang theo yêu cầu (demand paging).

 Kỹ thuật phân đoạn theo yêu cầu (demand segmentation)

3. Định nghĩa Page fault:

Page faul là trang tham chiếu (đến bộ nhớ ảo) không hợp lệ hoặc chưa được đưa vào bộ nhớ trong

21Thay trang:Thay trang diễn ra khi không co Frame rỗi

aCác bước xử lý thay trang:

1. Tìm vị trí của trang muốn đưa vào trên đĩa

2. Tìm một frame rỗi:

 Nếu đó là frame rỗi thì sử dụng nó

 Nếu đó không phải là frame rỗi thì sử dụng một giải thuật thay trang để chọn một frame nạn nhân

3. Đọc trang được yêu cầu vào frame rỗi. Cập nhật trang và bảng frame

4. Khởi động lại tiến trình

Câu 16 Phân phối frames là gì. Phân biệt phân phối công bằng, phân phối theo kích thước, phân phối có ưu tiên. Cơ chế phân phối nào cho phép thay thế toàn cục, cơ chế nào cho phép thay thế cục bộ. Giải thích

1 Phân phối frame:

Phân phồi frame là quá trình chọn một frame trong số các frame để thay cho một page fault

2 Phân biệt:

- Phân phối công bằng: Là sự phân bố các trang ở mỗi tiến trình là bằng nhau mà không hề quan tâm đến mức ưu tiên hay kích thước của các tiến trình .Cơ chế này cho phép thay thế toàn bộ một tiến trình có thể lấy một frame từ một tiến trình khác.

- Phân phối theo kích thước: là sự phân bố trang cho các tiến trình dựa trên tiêu chuẩn về kích thước của tiến trình, tiến trình nào có kích thước nhỏ thì số trang để thực hiện ít, tiến trình nào có kích thước lớn thì số trang để thực hiện tiến trình là nhiều. Cơ chế này cho phép thay thế toàn bộ vì tiến trình chọn một frame thay thế từ tập tất cả các frame

Phân phối theo mức ưu tiên: Nếu tiến trình Pi phát sinh một page fault, chọn thay thế một trong số các frame của nó. Frame thay vào đó được chọn từ một tiến trình có mức ưu tiên thấp hơn. Cơ chế này cho phép thay thế cục bộ vì mỗi tiến trình chỉ chọn một frame thay thế từ chính tập các frame đã phân phối cho nó

Câu 19: So sánh các thuật toán đọc đĩa. Lựa chọn các thuật toán đọc đĩa như thế nào? Nguyên nhân các lôic truy xuất đĩa và cách khắc phục

Lập lịch cho đĩa là xây dựng các thuật toán dịch chuyển đầu từ đọc ghi sao cho thời gian truy nhập đĩa là tối ưu nhất

Thời gian truy nhập đĩa

Thời gian di chuyển đầu từ đọc ghi đến strack thích hợp(seek-time)

Thời gian chờ cho khối cần thiết dưới đầu đọc(latency -time)

Thời gian vận chuyển dữ liệu giữa đĩa và bộ nhớ chính(transfer-time)

Các thuật toán lập lịch cho đĩa( thuật toán đọc đĩa)

o First come first Served(FCFS)

o Shortest seek time first(SSTF)

o Scan

o C-Scan

o Look

o C-Look

1.First come first Served(FCFS)

o Để truy nhập tới 1 file, hệ thống sẽ tổ chức một hàng đợi các yêu cầu phục vụ của các track(lưu trữ dữ liệu của file cần truy nhập)

o Nội dung:track nào có yêu cầu phục vụ trước thì đầu đọc ghi sẽ dịch chuyển tới đó trước

-Ưu điểm:

+)Dễ lập trình

+)Các track cần truy xuất là liên tục

2-Nhược điểm

+)Số track mà đầu đọc phải di chuyển là nhiều

+)Hiệu quả của thuật toán phụ thuộc vào thứ tự của các track trong hàng đợi

2-Shortest Seek time First

• Nội dung: track nào có thời gian di chuyển đầu từ đọc ghi ngắn nhất thì phục vụ trước - Ưu tiên đọc các khối gần với vị trí hiện tại của đầu đọc nhất.

-Ưu điểm

Số track mà đầu đọc phải đi chuyển giảm

-nhược điểm

Có thể gây ra 1 số yêu cầu không bao giờ được phục vụ

3-Scan

• Nội dung:Đầ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

Đặc điểm :Phương thức h/đ như thang máy, Số bước đầu đọc phải di chuyển giảm

4.C-Scan

• Nội dung: Đầu đọc chuyển từ một phía (trong/ngoài)sang phía kia và phục vụ các yêu cầu. Khi sang đến phía kia, đầu đọc quay trở lại nhưng trong khi quay trở lại không phục vụ yêu cầu nào.(quét 1 chiều)

5-Look

 Nội dung:tương tự như Scan nhưng trong thuật toán này đầu đọc ghi chỉ quét trong phạm vi các track có nhu cầu phục vụ không quét tới track đầu tiên hoặc cuối cùng

6.C-Look

 Nội dung:Tương tự như Look nhưng đầu đọc ghi không phục vụ đường về

Lựa chọn một giải thuật lập lịch đĩa

 FCFS là thuật toán phù hợp khi các track cần truy xuất là liên tục

 SSTF phổ biến và có hiệu quả tốt.

 SCAN và LOOK thích hợp cho những hệ thống phải truy xuất dữ liệu lớn