Chia sẻ một chút ~

Chào mọi người, mình là Rek. Hiện tại thì mình đang là sinh viên năm 3 của HaUI với 2 chuyên ngành là IT và Cơ điện tử. Mình thì khá thích ngành IT, cơ mà do lỡ đăng kí vào Cơ điện tử nên đến giờ mình mới bắt đầu học song song chương trình IT được. Và với vốn kiến thức hạn chế của mình, mong rằng sẽ nhận được những lời góp ý cũng như bổ sung hay chỉnh sửa của mọi người nha

Okay giờ thì bắt đầu nào ~

Biết tới Viblo cũng từ khá lâu, mà giờ mới đủ dũng khí tham gia MayFest Về cơ bản thì mình đang học môn Nguyên Lý Hệ Điều Hành, và với môn này thì có một điều khiến mình thấy khá hấp dẫn cũng như hơi loằng ngoằng với mấy bạn mới bắt đầu: Các thuật toán lập lịch CPU. Và trong bài này, mình sẽ chia sẻ những hiểu biết, cũng như những mẹo để khiến lập lịch CPU không còn là cơn đau đầu với các bạn >.O

Những thuật toán lập lịch CPU cơ bản gồm:

1. First Come First Served (FCFS)
2. Shortest Job First (SJF)
3. Shortest Remaining Time First (SRTF)
4. Round Robin (RR)

Cùng bắt đầu với thuật toán lập lịch đầu tiên nhé.

~ FCFS aka First Come First Served

Như cái tên luôn, thuật toán này gói gọn trong 4 chữ: Đến trước làm trước

Ai đó từng nói:

Thay vì ngồi để dành công việc rồi ngồi nghĩ nên làm cái nào trước, thì tốt hơn hết là bắt đầu làm ngay khi công việc xuất hiện

Với thuật toán này thì hàng đợi của các tiến trình được tổ chức theo FIFO (First In First Out), tiến trình nào xuất hiện đầu tiên sẽ được ưu tiên xử lý trước và xử lý xong, tiếp đó là tiến trình xuất hiện thứ 2, thứ 3,...

Với hình minh hoạ và biểu đồ Gantt như dưới đây:

Thuật toán này là thuật toán đơn giản nhất, tuy nhiên cũng có những nhược điểm sau:

• Thời gian chờ đợi trung bình (Avg Waiting Time ) sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình.
• Nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
• Khi có tiến trình dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.

Hiệu suất xử lý của FCFS kém hơn so với các thuật toán khác.

~ SJF aka Shortest Job First

Okay, tiếp tục với thuật toán tiếp theo: Shortest Job First. SJF là một thuật toán đơn giản, với thuật toán này thì tiến trình nào xuất hiện đầu tiên sẽ được ưu tiên xử lý trước và xử lý xong, tiếp theo, tiến trình nào đã xuất hiện có thời gian thực hiện (burst time) ngắn nhất sẽ được xử lý trước và xử lý xong. Trong trường hợp xuất hiện 2 tiến trình trong hàng đợi có thời gian thực hiện bằng nhau, tiến trình nào xuất hiện sớm hơn sẽ được xử lý trước và xử lý xong.

Hình minh hoạ và biểu đồ Gantt của thuật toán này được mô tả như dưới đây:

Thuật toán đã giảm được thời gian chờ đợi trung bình so với FCFS, tuy nhiên vẫn tồn tại những nhược điểm:

• Cần biết trước thời gian thực hiện của tiến trình, tuy nhiên điều này khó có thể thực hiện.
• Trong trường hợp những tiến trình ngắn xuất hiện sau, có thể những tiến trình dài trước đó sẽ phải chờ đợi rất lâu mới có thể thực hiện.

~ SRTF aka Shortest Remaining Time First

Với thuật toán này, thay vì xử lý tiến trình một cách liên tục, thuật toán sẽ xử lý tiến trình nào có thời gian thực hiện tại thời điểm đó là ngắn nhất. Nói một cách đơn giản, là sau mỗi 1 đơn vị CPU time thì sẽ so sánh và chọn ra tiến trình có thời gian thực hiện là ngắn nhất để xử lý trước. Trong trường hợp xuất hiện 2 tiến trình trong hàng đợi có thời gian thực hiện bằng nhau, tiến trình nào xuất hiện sớm hơn sẽ được xử lý trước.

Dưới đây là một ví dụ cho việc sử dụng thuật toán SRTF:

SRTF đã giảm được thời gian chờ đợi so với SJF, ngoài ra còn tối ưu được thời gian thực hiện của các tiến trình. Nhưng không thể phủ nhận rằng SRTF vẫn tồn tại những nhược điểm:

• Yêu cầu quản lý các tiến trình thời gian còn lại, tốn nhiều tài nguyên hơn so với các thuật toán khác.
• Các tiến trình có thời gian thực hiện lớn sẽ dễ bị "đói" CPU.
• Khó áp dụng trong thực tế khi không biết thời gian thực hiện của các tiến trình trước khi chúng được thực hiện.

~ RR aka Round Robin

Chẹp chẹp, với mớ lý thuyết ở trên thì có vẻ mọi chuyện vẫn ổn Nhưng giờ chúng ta sẽ đến với thứ thú vị nhất này: Round Robin. Khi mới bắt đầu với RR, mình đã tự hỏi:

Vãi mèo, họ nghĩ ra cái thứ quái quỉ gì đây nhở

Và mình nghĩ thì thực sự Round Robin là một trong những cơn đau đầu dai dẳng với những bạn biết tới nó lần đầu Nhưng đây lại là một thuật toán mà được nhắc đến rất nhiều bởi sự ưu việt của nó so với các thuật toán trên, vậy mấu chốt ở đây là gì !?

Lượng tử thời gian aka Time Quantum

Nghe thì có vẻ khá đáng sợ khi gắn chữ "lượng tử" vào, tuy nhiên thực chất đây chỉ giống như một "miếng bánh thời gian CPU" được cung cấp cho tíến trình để nó được thực hiện

Logic về Round Robin

Các tiến trình sẽ được tổ chức theo FIFO, với mỗi tiến trình khi đến lượt nó thực hiện thì sẽ được cấp cho 1 time quantum "miếng bánh thời gian CPU. Tiến trình có thể sẽ ăn hết "miếng bánh" này mà vẫn còn đói, nó sẽ phải chạy xuống cuối hàng và chờ đợi đến lượt.

Ví dụ về Round Robin:

Ta chọn time quantum = 2 và có được biểu đồ Gantt:

Thực sự lúc mới đầu nhìn biểu đồ Gantt của RR, mình đã khá trầm cảm Nó dài, và nhiều đoạn tiến trình cùng mốc thời gian. Nhưng hãy để mình kể một câu chuyện ngắn nhé:

Ở một thành phố nọ, có một tiệm bánh CPU nổi tiếng tổ chức phát bánh miễn phí cho mọi người. Việc duy nhất họ phải làm là nhận lấy 1 tấm vé, và xếp hàng dựa trên số thứ tự ghi trên vé tương ứng với thời gian mà họ nhận tấm vé đó, ai có số thứ tự nhỏ hơn sẽ được đứng trước. Mọi người trong thành phố rất háo hức được thưởng thức những chiếc bánh trứ danh của tiệm. Tiệm bánh đăng thông cáo rằng: "Mọi người có thể ăn thoả thích những chiếc bánh cho tới khi họ no, tuy nhiên mỗi người chỉ được ăn N chiếc bánh mỗi lượt, và sau mỗi lượt, nếu họ muốn ăn tiếp thì họ phải đổi chiếc vé cũ và lấy vé mới tại quầy, sau đó phải về cuối hàng và chờ đợi". Mỗi người đều mất 1 đơn vị thời gian để ăn 1 chiếc bánh ngọt ngào. Chà, và mọi điều xảy ra đúng như kế hoạch đề ra, cư dân của thành phố được ăn no nê một bữa được thết đãi bởi tiệm bánh hào phóng.

(hình ảnh minh hoạ thôi nha)

Giờ thì:

• Tiệm bánh = CPU
• 1 cư dân thành phố = 1 tiến trình
• Số thứ tự trên vé = Arrival Time = Thời gian xuất hiện của tiến trình
• N bánh mỗi lượt = Time Quantum = Lượng tử thời gian

Giờ thì hẳn mọi thứ đã đơn giản hơn rồi

Kết thúc nào ~

Việc lập lịch CPU cho tiến trình là thứ mà bạn sẽ gặp khi tiếp cận Nguyên Lý Hệ Điều Hành. Mong rằng với bài viết này, với những bạn mới làm quen NLHĐH cũng như thuật toán lập lịch có thể dễ dàng hơn khi lập lịch CPU Và đây cũng là bài viết hẳn hoi đầu tiên mà mình viết, có điều gì sai sót thì hãy bổ sung dưới bình luận nha Cảm ơn mọi người