Thực hành Hệ điều hành - Bài thực hành số 4.1: Lập lịch chạy các process (thread)

Nội dung text: Thực hành Hệ điều hành - Bài thực hành số 4.1: Lập lịch chạy các process (thread)

1. E D C B A temps 4 7 10 12 17 attente exécution Thời gian ₫áp ứng = lúc kết thúc - lúc ₫ược kích hoạt chạy A : 17 B : 4 C : 4 D : 4 E : 5 Lưu ý : thời gian ₫áp ứng không nhất thiết là ₫ộ ₫o tốt về hiệu năng làm việc của hệ thống vì nó không ₫ể ý tới nhu cầu dùng CPU của từng process. Thí dụ với các thông số trên, các process B, C, D có cùng thời gian ₫áp ứng nhưng chúng không cùng mức ₫ộ thỏa mãn vì chúng yêu cầu thời gian chạy khác nhau (4, 3, 2). Tỉ lệ phạt = thời gian ₫áp ứng/thời gian ₫ược phục vụ A : 3.4 B : 1 C : 1.33 D : 2 E : 1.66 Với giải thuật lập lịch SJN (hay PSJN), nạn ₫ói chỉ xảy ra khi CPU bận 100% liên tục theo thời gian. Cụ thể nếu các process ngắn ₫ược kích hoạt ₫ều ₫ều, process dài sẽ không có cơ may ₫ược chạy. Tuy nhiên trình trạng này rất ít khi xảy ra trong thực tế. 2.2 Nếu dùng giải thuật lập lịch PSJN (), hãy miêu tả việc thi hành các process dưới dạng biểu ₫ồ. Hãy tính thời gian ₫áp ứng và tỉ lệ phạt của từng process. Có nguy cơ xuất hiện nạn ₫ói trên các process không ? Giải thích. E D C B A temps 35 68 10 12 17 attente exécution Trong giải thuật lập lịch này, 1 process mới chỉ có thể ngắt process khác nếu nó có quyền ưu tiên cao hơn (tức có thời gian chạy ngắn hơn). Thời gian ₫áp ứng : A : 17 B : 12 C : 3 D : 2 E : 6 Tỉ lệ phạt : A : 3.4 B : 3 C : 1 D : 1 E : 2 3. Lập lịch trong chế ₫ộ phân chia thời gian (time sharing) Giải thuật Round-robin Trong giải thuật lập lịch xoay vòng (round-robin), các process ₫ược xếp trong 1 hàng chờ duy nhất, ai tới trước sắp trước, ai tới sau sắp sau. Khi CPU rảnh, trình lập lịch sẽ cho CPU
2. 3.2 Hãy nêu ưu khuyết ₫iểm của giải thuật lập lịch round-robin. Nạn ₫ói có thể xảy ra không ? Vì sao ? Ưu : ₫ơn giản. Khuyết : không ₫ể ý tới các process cần khẩn cấp (ưu tiên hơn) các process khác. Nguy cơ nạn ₫ói : Không, sau khi process vào hàng chờ, nó sẽ ₫ược chạy sau 1 khoàng thời gian hữu hạn. Cụ thể, chỉ có các process xếp trước nó mới có thể chạy tối ₫a 1 khe thới gian trước khi nó ₫ược chạy. Giải thuật round-robin không cho phép ₫ể ý tới các process cần khẩn cấp (ưu tiên hơn) các process khác. Do ₫ó ta cần giải thuật lập biểu khác mà xử lý quyền ưu tiên của các process. Lập lịch với quyền ưu tiên cố ₫ịnh Trong giải thuật này, mỗi process ₫ược cấp 1 quyền ưu tiên xác ₫ịnh lúc bắt ₫ầu chạy và nó giữ quyền này cho ₫ến khi thi hành xong toàn bộ. Giả sử có 4 mức quyền ưu tiên, ₫ánh số từ 0 - 3 (0 ưu tiến thấp nhất). Xét các process sau ₫ây : Time CPU I/O Thời gian Mức ưu I/O tiên T1 300 ms Không có 0 T2 30 ms Sau mỗi 10 ms 250 ms 3 T3 200 ms Không có 1 T4 40 ms Sau mỗi 20 ms 180 ms 3 T5 300 ms Không có 1 3.3 Miêu tả chính xác sự tiến triển của hệ thống : từng thời ₫iểm, sự kiện gì xảy ra (chuyển ngữ cảnh - CNC, yêu cầu I/O, xong I/O), process ₫ược chọn, trạng thái hàng chờ. Với từng process, xác ₫ịnh thời ₫iểm kết thúc chạy. Giả sử quantum = 100ms, các process lúc ₫ầu ₫ều ready và ₫ược xếp theo chỉ số của chúng, card ₫iều khiển ₫ĩa ₫iều khiển 2 ₫ĩa, 2 process T2 và T4 thực hiện I/O trên các ₫ĩa khác nhau. Ứng với mỗi mức quyền ưu tiên, có 1 hàng chờ các process cùng quyền ưu tiên ở mức này. Ta dùng giải thuật round-robin ₫ể chọn process chạy trong từng hàng chờ. Trong bàng dưới ₫ây, ta dùng dấu / ₫ể ngăn 4 hàng chờ của 4 mức ưu tiên khác nhau. Time Sự kiện Process Trạng thái hàng chờ Chú thích ₫ược chọn 0 Nạp chạy T2 T2 2p 4p / / 3p 5p / 1p 10 I/O của T2, CNC T4 4p 2b / / 3p 5p / 1p 30 I/O của T4, CNC T3 2b 4b / / 3p 5p / 1p 130 CNC T5 2b 4b / / 5p 3p / 1p 210 Xong I/O của T4 T5 2b 4p / / 5p 3p / 1p 230 CNC T4 4p 2b / / 3p 5p / 1p 250 I/O của T4, CNC T3 2b 4b / / 3p 5p / 1p
3. 215 CNC 1.1 1.1 / 2.0 3.0 230 CNC 2.0 / 2.0 3.0 300 1.2 & 2.1 chạy 2.0 1.2 2.1 / 2.0 3.0 330 CNC 1.2 1.2 2.1 / 3.0 345 CNC 2.1 2.1 / 3.0 445 CNC 3.0 / 3.0 2.1 450 1.3 chạy 3.0 1.3 / 3.0 2.1 545 CNC 1.3 1.3 / 2.1 / 3.0 560 CNC 2.1 / 2.1 / 3.0 600 1.4 & 2.2 chạy 2.1 1.4 2.2 / 2.1 / 3.0 660 CNC 1.4 1.4 2.2 / / 3.0 675 CNC 2.2 2.2 / / 3.0 750 1.5 chạy 2.2 2.2 1.5 / / 3.0 775 CNC 1.5 1.5 / 2.2 / 3.0 790 CNC 2.2 / 2.2 / 3.0 890 CNC 3.0 / / 3.0