Bài 1. Xét tập các tiến trình sau (với thời gian yêu cầu CPU và độ ưu tiên kèm theo) :

Giả sử các tiến trình cùng được đưa vào hệ thống tại thời điểm 0
a)Cho biết kết quả điều phối hoạt động của các tiến trình trên theo thuật toán FIFO; SJF; điều phối theo độ ưu tiên độc quyền (độ ưu tiên 1 > 2 > ...); và RR (quantum=2).
b)Cho biết thời gian lưu lại trong hệ thống (turnaround time) của từng tiến trình trong từng thuật toán điều phối ở câu a.
c)Cho biết thời gian chờ trong hệ thống (waiting time) của từng tiến trình trong từng thuật toán điều phối ở câu a.
d)Thuật toán điều phối nào trong các thuật toán ở câu a cho thời gian chờ trung bình là cực tiểu ?
Bài 2. Giả sử có các tiến trình sau trong hệ thống :

Sử dụng nguyên tắc điều phối độc quyền và các thông tin có được tại thời điểm ra quyết định để trả lời các câu hỏi sau đây :
a)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối FIFO.
b)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối SJF.
c)Thuật toán SJF dự định cải tiến sự thực hiện của hệ thống , nhưng lưu ý chúng ta phải chọn điều phối P1 tại thời điểm 0 vì không biết rằng sẽ có hai tiến trình ngắn hơn vào hệ thống sau đó . Thử tính thời gian lưu lại trung bình trong ệ thống nếu để CPU nhàn rỗi trong 1 đơn vị thời gian đầu tiên và sau đó sử dụng SJF để điều phối. Lưu ý P1 và P2 sẽ phải chờ trong suốt thời gian nhàn rỗi này, do vậy thời gian chờ của chúng tăng lên. Thuật toán điều phối này được biết đến như điều phối dựa trên thông tin về tương lai.
Bài 3. Phân biệt sự khác nhau trong cách tiếp cận để ưu tiên cho tiến trình ngắn trong các thuật toán điều phối sau :
a) FIFO.
b)RR
c)Điều phối với độ ưu tiên đa cấp
Bài 4. Cho biết hai ưu điểm chính của mô hình đa tiểu trình so với đa tiến trình. Mô tả một ứng dụng thích hợp vớ mô hình đa tiểu trình và một ứng dụng khác không thích hợp.
Bài 5. Mô tả các xử lý hệ điều hành phải thực hiện khi chuyển đổi ngữ cảnh giữa :
a)các tiến trình
b)các tiểu trình
Bài 6. Xác định thời lượng quantum q là một nhiệm vụ khó khăn. Giả sử chi phí trung bình cho một lần chuyển đổi ngữ cảnh là s, và thời gian trung bình một tiến trình hướng nhập xuất sử dụng CPU trước khi phát sinh một yêu cầu nhập xuất là t ( t>>s). Thảo luận các tác động đến sự thực hiện của hệ thống khi chọn q theo các quy tắc sau :
a)q bất định 
b)q lớn hơn 0 1 ít
c)q = s
d)s < q < t
e)q = t
f)q > t
Bài 7. Giả sử một hệ điều hành áp dụng giải thuật điều phối multilevel feedback với 5 mức ưu tiên (giảm dần). Thời lượng quantum dành cho hàng đợi cấp 1 là 0,5s. Mỗi hàng đợi cấp thấp hơn sẽ có thời lượng quantum dài gấp đôi hàng đợi ứng với mức ưu tiên cao hơn nó. Một tiến trình khi vào hệ thống sẽ được đưa vào hàng đợi mức cao nhất, và chuyển dần xuống các hàng đợi bên dưới sau mỗi lượt sử dụng CPU. Một tiến trình chỉ có thể bị thu hồi CPU khi đã sử dụng hết thời lượng quantum dành cho nó. Hệ thống có thể thực hiện các tác vụ xử lý theo lô hoặc tương tác, và mỗi tác vụ lại có thể hướng xử lý hay hướng nhập xuất.
a)Giải thích tại sao hệ thống này hoạt động không hiệu quả ?
b)Cần phải thay đổi (tối thiểu) như thế nào để hệ thống điều phối các tác vụ với những bản chất khác biệt như thế tốt hơn ?
Trước tiên là phần lý thuyết của phần này nhé. Phần điều phối tiến trình chúng ta có 4 cách là FIFO , RR , SJF, và độ ưu tiên. Với những bài toán của điều phối tiến trình chúng ta sẽ phải tính một trong những thông số sau :
Thời gian xử lý,Thời gian xử lý trung bình
Thời gian đợi,Thời gian đợi trung bình
Thời gian lưu lại trong hệ thống
================================================== =========
1.Điều phối FIFO
CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất. Đây là thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập/xuất.


*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0; P2=24-1 =23 ; P3 = 24+3-2 = 25
*Thời gian đợi trung bình: (0+23+25)/3 = 16
* Thời gian lưu lại trong hệ thống : P1=24 ; P2=3; P3=3
* Thời gian lưu lại trung bình : (24+3+3)/3 =10

2.Chiến lược điều phối xoay vòng :
Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng để đợi được cấp CPU trong lượt kế tiếp.



*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi :
P1=0
P2=4-1=3
P3=4+3-2=5
P1'=4+3+3-3=6
đến lúc này p1 sẽ được xử lý liên tục nên không phải tính thời gian chờ của p1'' p1'''...
*Thời gian đợi trung bình: (0+3+5+6)/3=4.66
* Thời gian lưu lại trong hệ thống : 
P1: vòng 1 =4 vòng 2=20 khoảng cách 2 vòng là 6 => thời gian lưu lại của P1 =4+20+6 =30
P2=3
P3=3
* Thời gian lưu lại trung bình : (30+3+3)/3=12

3.Điều phối với độ ưu tiên
Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên. Độ ưu tiên có thể được định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ưu tiên nội tại sử dụng các đại lượng có thể đo lường để tính toán độ ưu tiên của tiến trình, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ…Độ ưu tiên cũng có thể được gán từ bên ngoài dựa vào các tiêu chuẩn do hệ điều hành như tầm quan trọng của tiến trình, loại người sử dụng sỡ hữu tiến trình… Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền. Khi một tiến trình được đưa vào danh sách các tiến trình sẵn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phốivới độ ưu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó.


* Trường hợp độc quyền
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0;P2=23;P3=25
*Thời gian đợi trung bình: (0+23+25)/3=16
* Thời gian lưu lại trong hệ thống : P1=24; P2=3;P3=3
* Thời gian lưu lại trung bình: ( 24+3+3)/3=10

*Trường hợp không độc quyền:
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : 

P1=0
P2=0+1-1=0
P3=0+1+3-2=2
P1'=0+1+3+3-3=4
*Thời gian đợi trung bình: (0+0+2+4)/3=2
* Thời gian lưu lại trong hệ thống :
P1 Vòng 1 = 1 vòng 2= 23 khoảng cách giữa 2 vòng =6 => thời gian lưu lại của p1= 1+23+6=30
p2=3
p3=3

* Thời gian lưu lại trung bình : (30+3+3)/3=12

4.Chiến lược công việc ngắn nhất (Shortest-job-first SJF)
Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.



* Trường hợp độc quyền

*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi : P1=0 p4=5 ; p3=6; p2=9
*Thời gian đợi trung bình: (0+5+6+9)/4=5
* Thời gian lưu lại trong hệ thống : P1=6; P4=2;P3=4;P2=8
* Thời gian lưu lại trung bình: ( 6+2+4+8)/4=5

*Trường hợp không độc quyền:
*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi : 
P1=0
P4=2
P1'=3
P3=5
P2=8
*Thời gian đợi trung bình: (0+2+3+5+8)/4=4.5
* Thời gian lưu lại trong hệ thống :
P1 Vòng 1 = 3 vòng 2= 3 khoảng cách giữa 2 vòng =2 => thời gian lưu lại của p1= 3+3+2=8
P4=2
p3=4
P2=8
* Thời gian lưu lại trung bình : (8+2+4+8)/4=5