Cần giúp về giải thuật SRTF

Bạn tham khảo ở đây nhé!

loanh quanh trên mạng. gặp ngay ông bạn. Và đang có mối quan tâm chung

@Tri_H_i_D_ng @Trinh_Phuong
Cái tên giải thuật này nói lên tất cả Shortest Remaining Time First (Thằng nào thời gian chạy còn lại ngắn nhất thì ưu tiên trước) cơ giải thích khá là dài dòng…cái này thì yêu cầu các bác đầu óc tưởng tượng một tí

Em lấy một ví dụ như thế này:

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P1             6                1
  P2             3                1
  P3             0                7
  P4             2                3
  P5             0                8
  P6             2                2
  P7             1                5

• Trước khi làm thì cần phải chú ý nguyên tắc của thuật toán này như sau:

  • Tại cùng một thời điểm nếu có 2 hay nhiều hơn Process yêu cầu chạy thì thuật toán sẽ ưu tiên thằng có thời gian thực thi bé hơn chạy trước.

  • Khi một Process đang thực thi, tới một thời điểm mà có các Process khác yêu cầu chạy, thì thuật toán sẽ tiến hành so sánh thời gian thực thi còn lại của process đang chạy với thời gian thực thi của các Process có yêu cầu, thằng nào bé nhất thì được ưu tiên chạy trước.

  • Chỉ số thời gian chờ chỉ được xét tới trong lần chạy đầu tiên và lần so sánh đầu tiên, sau khi Process nào đã thực thi cho dù chưa xong thì chỉ số thời gian chờ của Process đó không còn được quan tâm nữa, tương tự các Process nếu đã được so sánh thời gian thực thi trong một lượt nào đó rồi thì chỉ số thời gian chờ cũng không còn giá trị lập lịch nữa.

• Tiến hành giải ví dụ:

  • Tại thời điểm 0 ta thấy có hai thằng P3 và P5 yêu cầu chạy, so sánh thì thấy thời gian thực thi của P3 < P5 -> P3 được chạy trước:
    

  • Sau khi P3 thực thi được 1s tức là tới thời điểm 1, ta thấy có P7 yêu cầu được chạy, so sánh thời gian thực thi còn lại của P3 là 7-1 = 6 với thời gian thực thi của P7 thì P7 nhỏ hơn -> P7 được chạy, còn P3 chuyển sang trạng thái ngủ chờ được thực thi tiếp (lúc này chỉ số thời gian chờ của P3, P7 nó không còn giá trị lập lịch)
    

  • Sau khi P7 thực thi được 1s tức là tới thời điểm 2, ta thấy có P4 và P6 yêu cầu được chạy, so sánh thời gian thực thi (thời gian thực thi còn lại) của 3 thằng này thì P6 bé nhất -> P6 được vào chạy, P7 ngủ.
    

  • Tiếp tục, sau khi thằng P6 chạy được 1s tức là tới thời điểm 3,
    
    đến chỗ này có trường hợp đặc biệt xảy ra, để cẩn thận ta cùng xét lại bảng lập lịch sau những thay đổi (đoạn này hay nhầm nha):

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P1             6                1
  P2             3                1
  P3                              7 - 1 = 6
  P4                              3
  P5                              8
  P6                              2 - 1 = 1
  P7                              5 - 1 = 4

Tới thời điểm 3 ta thấy có P2 yêu cầu chạy, nhưng khi so sánh thời gian thực thi thì với P6 sau khi đã chạy được 1s thì bằng nhau (đều bằng 1), thì thay vì chạy thằng P2, thuật toán sẽ ưu tiên hoàn thành nốt công việc cho thằng P6 tức là chạy nốt 1s nữa

Thằng P6 đã hoàn thành công việc -> ta loại ra khỏi bảng lập lịch cho dễ nhìn, các thằng còn lại ngoài thằng P1 chưa có yêu cầu thì các thằng khác đều đã được chạy hoặc so sánh cho nên thời gian chờ của bọn này không còn giá trị, tất cả cạnh tranh công bằng qua so sánh thời gian thực thi:

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P1             6                1
  P2                              1
  P3                              7 - 1 = 6
  P4                              3
  P5                              8
  P7                              5 - 1 = 4

• Tại thời điểm 4 không có Process mới nào yêu cầu chạy, thuật toán tiến hành thực hiện nốt những process thực thi dở hoặc những process bị bỏ qua trong những lần so sánh, so sánh thời gian thực thi, ta thấy P2 nhỏ nhất -> P2 được thực thi. Chạy được 1s thì P2 hoàn thành -> loại khỏi lập lịch:
  

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P1             6                1
  P3                              7 - 1 = 6
  P4                              3
  P5                              8
  P7                              5 - 1 = 4

• Tại thời điểm 5 vẫn không có yêu cầu mới, tiếp tục so sánh hàng tồn kho, ta thấy P4 bé nhất -> P4 được thực thi
  

• Sau khi P4 chạy được 1s tức thời điểm 6 thì P1 có yêu cầu được chạy, so sánh thời gian thực thi (thời gian thực thi còn lại), ta thấy P1 nhỏ hơn -> P1 được chạy. Do trong bảng lập lịch ta thấy sẽ không có yêu cầu được chạy nào mới trong tương lại, nôm na là trong bảng bây giờ toàn là hàng cũ/hàng tồn sẽ không còn hàng mới nữa, nên bắt đầu từ hàng zin cuối cùng còn xót lại tức là P1 thì sẽ được chơi tới bến , thực thi cho tới hoàn thành thì thôi.
  
  P1 hoàn thành -> loại ra khỏi bảng lập lịch:

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P3                              7 - 1 = 6
  P4                              3 - 1 = 2
  P5                              8
  P7                              5 - 1 = 4

• So sánh thời gian thực thi, P4 bé nhất -> chạy tới khi hoàn thành:
  
  Còn lại:

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P3                              7 - 1 = 6
  P5                              8
  P7                              5 - 1 = 4

• Tiếp tục là P7 -> hoàn thành:
  
  Còn lại:

Process    Thời_gian_chờ    Thời_gian_thực_thi
  P3                              7 - 1 = 6
  P5                              8

• Cứ thế, ta có kết quả lập lịch:
  Biểu đồ Gantt hoàn chỉnh:
  

Tính thời gian đợi của các Process :
[(thời chờ thực tế) - (thời gian chờ lý thuyết)]

Với các Process bị chia thành nhiều lần thực thi thì thời gian đợi:
{tổng_của_các[(thời điểm thực thi lại) - (thời điểm ngủ trước đó)]}
+
[(Thời điểm chạy lần đầu) - (Thời gian chờ thực tế)]

• Áp dụng:
  P1 = 6 - 6 = 0
  P2 = 4 - 3 = 1
  P3 = (13 - 1) + (0 - 0) = 12
  P4 = (7 - 6) + (5 - 2) = 4
  P5 = 19 - 0 = 19
  P6 = (2 - 2) = 0
  P7 = (9 - 2) + (1 - 1) = 7

=> thời gian chờ trung bình: (0 + 1 + 12 + 4 + 19 + 0 + 7) / 7 = 6,14

• Mục đich: Tại sao phải lập lịch lằng nhằng kiểu này khi mà tổng thời gian thực thi với tất cả các thuật toán đều như nhau 27? -> Thuật toán này nhằm tối ưu hóa, giảm thiểu thời gian đợi trung bình của các Process.
  (P/s: Cái này bạn sẽ thấy ngay nếu cùng giải ví dụ này với thuật toán FCFS thì sẽ có thời gian chờ trung bình lớn hơn khá nhiều, mà các bác biết rằng 1s trong xử lý máy tính là một con số không hề nhỏ)

bây h mới để ý tin nhắn bạn cmt trong dien dan daynhauhc.bạn tham gia cái này lâu chưa

ok.mình cẢM ƠN BẠN NHA,

Nếu thời gian bằng nhau thì sao…?