Xin chào mọi người, nối tiếp seri về kinh nghiệm IT: https://huongtlu.wordpress.com//kinh-nghiem-it/ bài viết này mình chia sẻ về 3 thuật toán chính liên quan tại bài viết:

https://huongtlu.wordpress.com/2020/06/26/huong-dan-tu-hoc-de-do-chung-chi-fe-fundamental-it-engineer-bai-6/

Đây là 3 thuật toán liên quan tới xử lý tiến trình trong hệ điều hành máy tính. Đề thi FE (Fundamental IT Engineer) các năm gần đây mình thấy đa số đều có ít nhất 1 câu liên quan tới các thuật toán này.

Ngoài ra còn có 1 số thuật toán khác như: Round Robin, …

Theo dõi list bài học luyên thi FE (Fundamental IT Engineer): TẠI ĐÂY

XEM VIDEO HƯỚNG DẪN:

• Thuật toán FCFS (First Come First Served)
• Thuật toán SJF (Shortest Job First)
• Thuật toán SRT (Shortest Remain Time)

Bài tập kiểm tra

Quiz 1: Below is the list of processes, P1, P2, P3, and P4, and their burst time for CPU scheduling algorithms.

Which of the following combinations is the average waiting time in millisecond for a First-Come, First-Serve (FCFS) scheduling and Shortest-Job-First (SJF) scheduling given that the process arrives in the order P1, P2, P3, and P4, and the latency can be ignored. Note that the burst time is the actual time required to complete a process.

Dạnh mục từ viết tắt.........................................................................................

Lời mở đầu......................................................................................................... 1

Nội dung

Chương 1: Giới thiệu

1 Các khái niệm cơ bản................................................................................... 2

1 Mục tiêu........................................................................................................ 2

Chương 2: Cơ chế hoạt động

2 Mô tả thuật toán SJF.................................................................................... 4

2 Quy trình lựa chọn công việc ngắn nhất...................................................... 4

2 Thời gian đợi trung bình và thời gian hoàn thành trung bình...................... 6

Chương 3: Đánh giá và so sánh................................................................................ 7

Chương 4: Ưu tiên và không ưu tiên

4 Non-Preemptive SJF.................................................................................... 9

4 Preemptive SJF............................................................................................ 9

Chương 5: Cài đặt

5 Cài đặt giải thuật Non-Preemptive SJF........................................................ 12

5 Cài đặt giải thuật Preemptive SJF............................................................... 12

Chương 6: Ứng dụng................................................................................................. 14

Kết luận.............................................................................................................. 15

Tài liệu tham khảo............................................................................................. 16

ii

Lời mở đầu

Trong lĩnh vực quản lý và lập lịch hệ thống máy tính, việc tối ưu hóa thời gian xử lý và

tăng hiệu suất là một yêu cầu cấp thiết. Một trong những thuật toán lập lịch phổ biến và

được sử dụng rộng rãi để giải quyết vấn đề này là SJF (Shortest Job First).

SJF là một thuật toán lập lịch non-preemptive (không bị gián đoạn) mà nhiệm vụ có

thời gian xử lý ngắn nhất được ưu tiên xử lý trước. Ý tưởng chính của SJF là đảm bảo

rằng công việc sẽ được hoàn thành nhanh nhất có thể. Khi một công việc mới được

thêm vào hàng đợi, thuật toán SJF sẽ so sánh thời gian xử lý của công việc với các

công việc đang chờ xử lý và chọn công việc có thời gian xử lý ngắn nhất để xử lý tiếp

theo.

Một trong những ưu điểm nổi bật của SJF là giảm thiểu thời gian chờ đợi và thời gian

quay vòng của các công việc trong hàng đợi. Điều này có thể cải thiện hiệu suất và

hiệu quả tổng thể của hệ thống.

Tuy nhiên, SJF cũng gặp một số hạn chế. Vấn đề &

039;lợi thế chờ đợi&

039; (Lớn job chờ đợi) có

thể xảy ra khi một công việc có thời gian xử lý dài phải chờ đợi trong khi có nhiều

công việc khác có thời gian xử lý ngắn nằm trong hàng đợi. Điều này có thể làm gia

tăng thời gian chờ đợi cho công việc dài hơn và ảnh hưởng đến hiệu suất tổng thể của

hệ thống.

Nghiên cứu về SJF đòi hỏi việc xem xét và đánh giá cẩn thận các ưu điểm, hạn chế và

các biến thể của thuật toán này. Nghiên cứu SJF cung cấp cơ sở để phát triển các thuật

toán lập lịch mới và cải tiến hiệu suất của hệ thống máy tính.

Trên thực tế, SJF không phải lúc nào cũng là giải pháp lý tưởng cho tất cả các tình

huống. Điều quan trọng là hiểu rõ về thuật toán SJF, ưu điểm và hạn chế của nó, và áp

dụng đúng cách để đảm bảo tối ưu hóa hiệu suất của hệ thống máy tính.

Chương 1: Giới thiệu

1 Các khái niệm cơ bản

Lập lịch CPU là quá trình sử dụng các thuật toán để giúp hệ điều hành xác định được

tiến trình nào sẽ được thực thi trên bộ xử lý (CPU) tiếp theo. Trong các hệ thống đa

nhiệm, có nhiều tiến trình đang chạy cùng một lúc, nhưng chỉ có một tiến trình có thể

được thực thi trên CPU tại một thời điểm. Lập lịch CPU quyết định tiến trình nào sẽ

được thực thi tiếp theo.

Shortest Job First (SJF) là một thuật toán lập lịch CPU đơn giản và phổ biến. SJF lựa

chọn tiến trình có thời gian xử lý ngắn nhất vào hàng đợi sẵn sàng để thực thi.

Tiến trình (process) là một chương trình đang chạy trên hệ thống. Tiến trình được tạo

ra bởi hệ điều hành khi người dùng khởi chạy một chương trình. Tiến trình có thể được

xem như một thực thể đang chạy trên hệ thống, bao gồm các trạng thái, bộ nhớ, tài

nguyên và các thông tin khác.

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

Tiến trình có thể ở một trong các trạng thái sau:

 New: Tiến trình mới được tạo ra và chưa được thực thi.

 Ready: Tiến trình đã được tạo ra và sẵn sàng để được thực thi trên CPU.

 Running: Tiến trình đang được thực thi trên CPU.

 Waiting: Tiến trình đang chờ đợi một sự kiện nào đó xảy ra, chẳng hạn như

I/O hoặc tín hiệu.

 Terminated: Tiến trình đã hoàn thành và không còn tồn tại trên hệ thống.

Burst time là thời gian mà một tiến trình cần để sử dụng CPU. Burst time được đo

bằng đơn vị thời gian, chẳng hạn như giây (s) hoặc mili giây (ms), nano giây (ns),

micro giây (μs )...

Giả sử có một tiến trình có thời gian thực thi là 10 giây và thời gian I/O là 5 giây.

Burst time của tiến trình này là:

burst time = 10 + 5 = 15

Hàng đợi là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử được thêm vào ở một

đầu và được lấy ra ở đầu kia. Hàng đợi tuân theo cơ chế FIFO (First In First Out),

nghĩa là phần tử được thêm vào đầu tiên sẽ được lấy ra đầu tiên.

1 Mục tiêu

Chương 2: Cơ chế hoạt động

2 Mô tả giải thuật

Thuật toán SJF ưu tiên xử lý các tiến trình có thời gian xử lý ngắn nhất trước. Ý

tưởng chính của SJF là đảm bảo rằng nhiệm vụ sẽ được hoàn thành nhanh nhất có thể.

Khi một tiến trình mới được thêm vào hàng đợi, thuật toán SJF so sánh thời gian xử lý

của tiến trình đó với các tiến trình đang chờ xử lý và chọn tiến trình có thời gian xử lý

ngắn nhất để xử lý tiếp theo.

Hình minh họa thuật toán SJF

Ví dụ, có ba tiến trình (bỏ qua thời gian xuất hiện) : Tiến trình P1 yêu cầu 10 đơn vị

thời gian để hoàn thành, Tiến trình P2 yêu cầu 5 đơn vị thời gian để hoàn thành, tiến

trình P3 yêu cầu 16 đơn vị thời gian để hoàn thành.

Process Burst Time

P1 10

P2 5

P3 16

Vì P2 có thời gian xử lý thấp nhất nên sẽ được ưu tiên để xử lý, tiếp đó đến P1 và cuối

cùng là P3.

P2 P1 P

0 5 15 31

2 Quy trình lựa chọn thời gian ngắn nhất:

Quy trình lựa chọn tiến trình ngắn nhất của thuật toán SJF (Shortest Job First) được mô

tả như sau:

1. Khởi tạo hàng đợi: Bắt đầu bằng việc tạo một hàng đợi rỗng để lưu trữ các tiến

trình chờ xử lý.

2. Tiếp nhận tiến trình: Khi một tiến trình mới được gửi đến hệ thống, nó sẽ được

tiếp nhận và các thông tin về tiến trình như thời gian xử lý sẽ được xác định.

3. Thêm tiến trình vào hàng đợi: Tiến trình sẽ được thêm vào hàng đợi theo thứ

tự từ tiến trình có thời gian xử lý ngắn nhất đến tiến trình có thời gian xử lý dài

hơn. Trong trường hợp hai tiến trình có cùng thời gian xử lý, có thể sử dụng các

tiêu chí khác như thứ tự tiếp nhận để quyết định vị trí của chúng trong hàng đợi.

4. Lựa chọn tiến trình để xử lý: Khi cần chọn tiến trình để xử lý tiếp theo, thuật

toán SJF sẽ lựa chọn tiến trình có thời gian xử lý ngắn nhất từ hàng đợi. Công

việc này sẽ được chuyển đến bộ xử lý để tiếp tục xử lý.

5. Xử lý tiến trình: Tiến trình được chuyển đến bộ xử lý và được xử lý cho đến

khi hoàn thành.

6. Hoàn thành tiến trình: Khi tiến trình đã hoàn thành nhiệm vụ của nó, thông tin

về thời gian đợi và thời gian hoàn thành có thể được tính toán và lưu trữ cho

mục đích thống kê.

7. Quá trình lặp lại: Quá trình trên sẽ được lặp lại cho đến khi tất cả các tiến rình

trong hàng đợi được xử lý hoàn thành.

Quy trình lựa chọn tiến trình có thời gian thực thi ngắn nhất trong thuật toán SJF đảm

bảo rằng các công việc có thời gian xử lý ngắn nhất sẽ được ưu tiên xử lý trước, từ đó

giảm thiểu thời gian chờ đợi và thời gian quay vòng của các tiến trình trong hệ thống.

2 Thời gian đợi và thời gian hoàn thành trung bình:

Thời gian chờ (Waiting Time) là thời gian từ khi một tiến trình được đưa vào hàng

đợi (Arrival time) cho đến khi nó được xử lý. Thời gian chờ của các tiến trình trong

SJF có thể được tính từ thời điểm tiến trình đến cho tới khi tiến trình được hoàn thành

xử lý hoặc tạm thời hoàn thành xử lý.

Arrival time (thời gian xuất hiện) là thời gian mà một tiến trình đến và sẵn sàng để

được xử lý trong hệ thống. Nó biểu thị thời điểm mà tiến trình được đưa vào hàng đợi

hoặc bắt đầu quá trình xử lý. Thời gian chờ nếu không được khai báo sẽ mặc định bằng

0.

Ví dụ, giả sử có ba tiến trình đến theo thứ tự sau: P1, P2, P3, với thời gian cần để hoàn

thành tiến trình lần lượt là 7, 6, 8 (ms) và thời gian xuất hiện lần lượt là 3, 5, 2 (ms).

 Tại thời điểm 2ms, chỉ có P3 xuất hiện nên sẽ được xử lý đầu tiên.

Chương 3: Đánh giá và so sánh

Ưu điểm:

1. Thời gian chờ trung bình thấp: Bằng cách ưu tiên xử lý các tiến trình có thời

gian xử lý ngắn nhất, thuật toán SJF giúp giảm thời gian chờ trung bình cho các

tiến trình. Điều này cải thiện hiệu suất hệ thống và khả năng phản hồi nhanh.

2. Hiệu suất cao đối với các tiến trình ngắn: SJF là thuật toán tối ưu cho các hệ

thống có nhiều tiến trình ngắn. Nếu hệ thống có nhiều tiến trình có thời gian xử

lý ngắn, SJF có thể đảm bảo rằng những tiến trình này được xử lý sớm, tối ưu

hóa thời gian hoàn thành tổng thể.

3. Dễ triển khai: SJF là một thuật toán đơn giản và dễ triển khai. Không cần có

nhiều thông tin và các bước phức tạp để xác định thời gian thực hiện của các

quá trình.

Nhược điểm:

1. Không công bằng đối với các tiến trình dài: Một nhược điểm chính của SJF là

sự ưu tiên cho các tiến trình ngắn, dẫn đến thiếu công bằng đối với các tiến trình

dài hơn. Điều này có thể gây ra hiện tượng đói (starvation) cho các tiến trình dài

hơn khi chúng phải chờ lâu hơn để được xử lý.

2. Thiếu thông tin thực tế: SJF yêu cầu có thông tin chính xác về thời gian xử lý

của các tiến trình trước khi thực thi. Tuy nhiên, trong thực tế, việc xác định thời

gian xử lý cụ thể của mỗi tiến trình có thể khá khó khăn và không chắc chắn.

Bảng so sánh các thuật toán lập lịch CPU phổ biến hiện nay

Đặc điểm SJF FCFS RR

Tiêu chí

đánh giá

Thời gian đợi trung

bình

Thời gian đợi trung

bình

Thời gian đợi trung

bình

Cách thức

lựa chọn

tiến trình

Tiến trình có thời

gian xử lý ngắn nhất

Tiến trình đến trước

được ưu tiên

Tiến trình được luân

phiên sử dụng CPU

theo định mức thời

gian

Ưu điểm Thời gian đợi trung

bình ngắn nhất

Sử dụng đơn giản, dễ

thực hiện

Đảm bảo tính công

bằng cho các tiến trình

Nhược

điểm

Có thể dẫn đến trình

trạng đói CPU

Tiến trình đến sớm có

thể phải chờ đợi lâu

Thời gian đợi trung

bình cao

Khả năng

áp dụng

Phù hợp với hệ

thống có các tiến

trình có thời gian xử

lý khác nhau

Phù hợp với hệ thống

có các tiến rình có

thời gian xử lý tương

đương

Phù hợp với hệ thống

cần đảm bảo tính công

bằng cho các tiến tình

Tuy nhiên, tính hữu dụng của thuật toán còn phụ thuộc vào yêu cầu cụ thể của hệ

thống, ta có thể chọn thuật toán lập lịch phù hợp. SJF là một lựa chọn tốt khi nhắm đến

tối ưu hóa thời gian chờ đợi và hoàn thành các tiến trình có thời gian thực hiện tương

đối nhỏ. Tuy nhiên, nếu hệ thống yêu cầu tính toán chính xác thời gian thực hiện hoặc

ưu tiên các tiến trình lớn, các thuật toán khác như Round Robin hoặc Priority

Scheduling có thể phù hợp hơn.

Trong SRTF, thay vì chỉ xem xét thời gian thực hiện tổng cộng, thuật toán đồng thời

theo dõi thời gian xử lý còn lại của mỗi tiến trình. Khi một tiến trình mới được triển

khai hoặc tiến trình đang thực thi bị gián đoạn (preempted), SRTF sẽ so sánh thời gian

xử lý còn lại của tiến trình mới với tiến trình đang được thực hiện. Nếu thời gian thực

hiện còn lại của tiến trình mới ngắn hơn, nó sẽ được ưu tiên và tiến trình hiện tại sẽ bị

gián đoạn.

Mô hình hoạt động của SRTF

Ta cùng xét ví dụ sau:

Process Burst Time (ms) Arrival Time (ms)

P1 16 0

P2 5 2

P3 10 8

 Tại thời điểm t = 0ms, chỉ có P1 xuất hiện nên sẽ được đưa vào xử lý.

 Tại thời điểm t = 2ms, khi P2 xuất hiện, thời gian cần để hoàn thành xử lý còn

lại của hai tiến trình P1 và P2 lần lượt là 14ms và 10ms. Vì vậy, P2 sẽ được ưu

tiên đưa vào xử lý.

 Từ khoảng thời điểm P2 xuất hiện đến thời điểm P2 được xử lý hoàn tất (2-7ms)

không có tiến trình nào xuất hiện có thời gian cần hoàn thành thấp hơn P2 nên

P2 được xử lý hoàn thành đầu tiên.

 Tại thời điểm t = 7ms, khi P2 đã được xử lý, chỉ còn duy nhất P1 trong hàng đợi

nên CPU sẽ mặc định xử lý tiếp P1 cho đến khi có tiến trình khác xuất hiện.

 Khi P3 xuất hiện, (t = 8ms), CPU sẽ tiến hành so sánh thời gian cần hoàn thành

còn lại của P1 và P3 (13ms và 10ms). CPU nhận thấy rằng thời gian cần hoàn

thành còn lại của P3 nhỏ hơn P1. Vì vậy P1 sẽ bị tạm dừng và đưa vào hàng đợi,

còn P3 sẽ được CPU xử lý.

 Sau khỉ P3 được hoàn thành, P1 sẽ được xử lý tiếp phần thời gian còn lại và kết

thúc quá trình xử lý của CPU.

P1 P2 P1 P3 P

0 2 7 8 18 31(ms)

Khi áp dụng SRTF, các thời gian chờ và thời gian đợi sẽ là:

 Thời gian chờ của P1:

o Từ t = 2 đến t = 7, P1 phải đợi 5ms

o Từ t = 8 đến t = 18. P1 đợi thêm 10ms

Vậy thời gian đợi của P1 = 5 + 10 = 15ms

 Thời gian chờ của P2:

o P2 xuất hiện tại t = 5 và đến t = 7 là hoàn thành nên P2 không phải đợi

bất ký tiến trình nào

 Thời gian chờ của P3:

o P3 tương tự P

\=> Thời gian đợi trung bình = (15 + 0 + 0) / 3 = 5ms

 Thời gian hoàn thành của P1: 15 + 16 = 31ms

 Thời gian hoàn thành của P2: 0 + 5 = 5ms

 Thời gian hoàn thành của P3: 0 + 10 = 10ms

\=> Thời gian đợi trung bình = (31 + 5 + 10) / 3 = 15,333ms

So với Non-Preemptive, Preemptive SJF có thể giúp tối ưu hóa thời gian chờ và thời

gian hoàn thành của các tiến trình một cách cụ thể hơn. Nhờ theo dõi và ưu tiên tiến

trình có thời gian xử lý còn lại ngắn nhất, nó có thể đảm bảo rằng các tiến trình ngắn và

có thời gian xử lý thấp sẽ được hoàn thành trước, đồng thời tránh việc chờ đợi không

cần thiết cho những tiến trình đang có thời gian xử lý dài hơn.

Tuy nhiên, nhược điểm chính của thuật toán Preemptive là việc gây ra tình trạng “đói

tiến trình”. Tình trạng “đói tiến trình” xảy ra khi một tiến trình không thể thực thi vì

các tiến trình khác luôn có thời gian còn lại ít hơn. Trong trường hợp này, các tiến trình

dài có thể bị trì hoãn vô thời hạn nếu các tiến trình ngắn liên tục được thêm vào.

waitTime = zeros(1, n);

finishTime = zeros(1, n);

remainingTime = burst;

currentTime = arrival(1);

while true

idx = find(arrival <= currentTime & remainingTime > 0);

if isempty(idx)

break;

end

[~, shortestIdx] = min(remainingTime(idx));

currentProcess = idx(shortestIdx);

remainingTime(currentProcess) = remainingTime(currentProcess) - 1;

currentTime = currentTime + 1;

if remainingTime(currentProcess) == 0

finishTime(currentProcess) = currentTime;

waitTime(currentProcess) = ...

finishTime(currentProcess) - arrival(currentProcess) -

burst(currentProcess);

end

end

averageWaitTime = sum(waitTime)/n;

fprintf(&

039;Th ời gian đ ợi c ủa các ti ến trình:\n&

039; );

for i = 1:n

fprintf(&

039;Ti ến trình: %s, Th ời gian đ ợi: %d ms\n&

039; , processes(i),

waitTime(i));

end

fprintf(&

039;Th ời gian đ ợi trung bình: % ms\n&

039; , averageWaitTime);

end

Chương 6: Ứng dụng

SJF là một thuật toán lập lịch được sử dụng khá phổ biến. SJF thường được sử dụng

vào quản lý công việc cá nhân, quản lý deadline và quản lý dự án, nó có thể giúp tối ưu

hóa thời gian và đạt được hiệu suất làm việc cao hơn. Việc ưu tiên thực hiện công việc

theo thứ tự từ ngắn đến dài, xác định công việc quan trọng và có deadline gần nhất,

cũng như xác định thứ tự tiến hành công việc trong dự án dựa trên thời gian ước tính

hoàn thành sẽ mang lại hiệu quả trong quản lý công việc của chúng ta.

Quản lý công việc cá nhân:

Thời gian quản lý công việc trong đời sống hàng ngày, chẳng hạn như làm việc,

học tập hay hoàn thành nhiệm vụ, là vấn đề quan trọng đối với mọi người. Áp

dụng SJF vào quản lý công việc cá nhân có thể giúp ta xác định và ưu tiên thực

hiện công việc theo thứ tự từ ngắn đến dài. Điều này sẽ giúp ta hoàn thành công

việc hiệu quả hơn và tối ưu hóa thời gian.

Quản lý deadline:

Khi cần hoàn thành nhiều công việc trong một khoảng thời gian nhất định, SJF có

thể được áp dụng để xác định công việc quan trọng nhất và có deadline gần nhất.

Thay vì tiến hành các công việc theo thứ tự đơn điệu, ta có thể ưu tiên hoàn thành

những công việc có deadline sắp tới nhất để tránh trì hoãn và đảm bảo sự hiệu

quả trong quản lý thời gian.

Quản lý dự án:

Trong quản lý dự án, SJF có thể được sử dụng

để quản lý tiến độ dự án. Các công việc cần

được thực hiện trong dự án có thể được xem như

các "tiến trình" và áp dụng SJF để xác định thứ

tự tiến hành dựa trên thời gian ước tính hoàn

thành. Điều này giúp đảm bảo dự án tiến hành

theo đúng tiến độ và tối ưu hóa sự phân công

công việc.

Tài liệu tham khảo

Silberschatz, Abraham, Galvin, Peter B., & Gagne, Greg (2018). Operating System

Concepts. John Wiley & Sons, Inc., Hoboken, New Jersey.

Patterson, David A., & Hennessy, John L. (2014). Chapter 7: Cache Memory. In

Computer Organization and Design: The Hardware/Software Interface. David A.

Patterson & John L. Hennessy, Morgan Kaufmann Publishers, San Francisco,

California, 213-242.

Wikipedia. Scheduling (computing), 09/2023,

en.wikipedia/wiki/Scheduling_(computing).

Phạm Thị Sinh. Giải thuật điều phối Shortest Job First Scheduling (SJF),

09/2023, sinhvientot/giai-thuat-dieu-phoi-shortest-job-first-scheduling-

sjf/.

Vaibhavi Desai. Scheduling Algorithms, GitHub,

09/2023, github/desaivaibhavi/scheduling-algorithms.