Thảo luận Bài 6

Thảo luận những vấn đề liên quan đến Bài 6

Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.

Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.

Mục đích:
Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau :

a) Sự công bằng ( Fairness) :

Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

b) Tính hiệu qủa (Efficiency) : Hệ thống phải tận dụng được CPU 100% thời gian.

c) Thời gian đáp ứng hợp lý (Response time) : Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

d) Thời gian lưu lại trong hệ thống ( Turnaround Time) : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

e) Thông lượng tối đa (Throughput ) : Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.

Điều phối hoạt động của các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ điều hành khi giải quyết phải xem xét nhiều yếu tố khác nhau để có thể đạt được những mục tiêu đề ra. Một số đặc tính của tiến trình cần được quan tâm như tiêu chuẩn điều phối :

a) Tính hướng xuất / nhập của tiến trình ( I/O-boundedness):

Khi một tiến trình nhận được CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình như thế thường bao gồm nhiều lượt sử dụng CPU , mỗi lượt trong một thời gian khá ngắn.

b) Tính hướng xử lý của tiến trình ( CPU-boundedness):

Khi một tiến trình nhận được CPU, nó có khuynh hướng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình như thế thường bao gồm một số ít lượt sử dụng CPU , nhưng mỗi lượt trong một thời gian đủ dài.

c) Tiến trình tương tác hay xử lý theo lô :

Người sử dụng theo kiểu tương tác thường yêu cầu được hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ được xử lý theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận được.

d) Độ ưu tiên của tiến trình :

Các tiến trình có thể được phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ ưu tiên cao hơn) cần được ưu tiên hơn.

e) Thời gian đã sử dụng CPU của tiến trình :

Một số quan điểm ưu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên chọn chúng.

f) Thời gian còn lại tiến trình cần để hoàn tất :

Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng cách cho các tiến trình cần ít thời gian nhất để hoàn tất được thực hiện trước. Tuy nhiên đáng tiếc là rất hiếm khi biết được tiến trình cần bao nhiêu thời gian nữa để kết thúc xử lý.

Bốn tình huống ra quyết định của trình điều phối CPU:
* Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối có tiếm quyền(Preemptive Scheduling) và điều phối không tiếm quyền (Non-Preemptive Scheduling)
+ Có tiếm quyền: Điều phối chỉ xảy ra ở thời điểm 1 va 4, không xảy ra điều phối ở thời điểm 2 và 3. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting (cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer. Trên HĐH hiện đại đa số có tiếm quyền.
+ Không tiếng quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến đang chạy, không cho độc chiếm CPU

Henry Laurence Gantt (sinh 1861 - mất 23 tháng 11 năm 1919) là một kĩ sư cơ khí và cố vấn dự án người Mỹ, nổi tiếng với việc phát triển sơ đồ Gantt năm 1910. Sơ đồ Gantt được sử dụng rộng rãi trong những công trình lớn như đập Hoover hay hệ thống đường quốc lộ liên bang Mỹ và ngày nay vẫn là một công cụ quan trọng trong quản lý dự án.

Tiểu sử

Henry Gantt sinh tại quận Calvert, Maryland, Hoa Kỳ. Ông tốt nghiệp trường McDonogh năm 1878 và trường cao đẳng Johns Hopkins rồi làm thầy giáo và người vẽ đồ án trước khi trở thành kĩ sư cơ khí. Năm 1887 ông cùng Frederick W. Taylor quản lý công ty thép Midvale và công ty thép Bethlehem cho đến năm 1893. Sau này, khi làm cố vấn dự án, ngoài sơ đồ Gantt, ông còn thiết kế hệ thống thưởng năng suất - trong đó nhân viên có năng suất vượt định mức sẽ được thưởng phần trăm. Ngoài ra, ông còn phát triển một số phương pháp đo đạc hiệu suất và năng suất nhân viên.

Đóng góp

Henry Gantt đã có nhiều đóng góp cho môn khoa học quản lý, đáng nói nhất bao gồm:
Sơ đồ Gantt: Đến ngày nay, sơ đồ Gantt vẫn được coi là một công cụ quản lý quan trọng. Sơ đồ Gantt biểu thị thời gian biểu của dự án dùng để quản lý, lên kế hoạch và kiểm soát tiến độ công việc trong dự án. PERT (Program Evaluation and Review Technique - Phương pháp ước lượng và xem xét chương trình) là một biến thể của sơ đồ Gantt.
Hiệu suất công nghiệp: Hiệu suất công nghiệp có thể được nâng cao bằng cách phân tích một cách khoa học mọi khía cạnh của công việc. Công tác quản lý công nghiệp là cải tiến hiệu suất bằng cách hạn chế tối đa rủi ro.
Hệ thống thưởng năng suất: Henry Gantt thưởng phần trăm quản lý viên tương ứng với năng suất vượt định mức nhân viên dưới quyền họ đạt được.
Trách nhiệm xã hội của doanh nghiệp: Henry Gantt tin rằng doanh nghiệp phải có trách nhiệm với xã hội.

Henry Laurence Gantt's legacy to management is the Gantt chart.


Ví dụ về biểu đồ Gantt


Tham khảo tại từ điển bách khoa toàn thư mở Wikipedia và trong tài liệu hệ điều hành thầy cho ( tiếng anh)

A. Bốn tình huống ra quyết định của trình điều phối CPU:
* Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
* Sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4 được gọi là điều phối không tiếm quyền (Non-Preemptive): Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting . Dùng khi máy không có Timer.
* Sơ đồ điều phối tiến hành trong cả 4 tình huống được gọi là điều phối có tiếm quyền (Preemptive).
B. Phân biệt điều phối có tiếm quyền và không có tiếm quyền:
- Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).
- Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.
- Non-Preemptive Scheduling: Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1 , sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
- Preemptive Scheduling : có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.

C. Chủ ý: Trong 4 tình huống ra quyết định của trình điều phổi CPU ở trên thì tình huống(Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con) và Khi tiến trình kết thúc công việc.) là tình huống mà điều phổi không tiếm quyền(Không dùng CPU) vì lúc này chương trình tự nguyện trá CPU.Còn tình huống(Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra) vá Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)) là tình huống mad điều phổi có tiếm quyền.Đây là mô hình hiện đại nhằm giúp CPU hoạt động hết hiệu suất của mình để làm giám thiếu tối đa thời gian chờ nhằm đáp ứng được hiệu quả công việc cao hơn.

Bốn tình huống ra quyết định của trình điều phối.
1. Khi tiến trình chuyển từ Running sang Waiting (chờ I/O, chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready( do ngắt xảy ra).
3. Khi tiến trình chuyển từ Waiting sang Ready( do kết thúc I/O).
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối tiếm quyền và điều phối không tiếm quyền:
• Điều phối không tiếm quyền( Non - Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting( cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.
• Điều phối có tiếm quyền( Preemptive):sơ đồ điều phối tiến hành trong cả 4 tình huống.
• Giống nhau: cùng điều phối CPU( chọn tiến trình trong Ready Queue để cấp thời gian CPU( chuyển sang trạng thái Running)).
• Khác nhau:
 Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non – Preemptive Scheduling thì điều phối CPU không tiếm quyền.
 Non – Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1, P2, P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.

SJFS có tiếm quyền
thời điểm tiến trình khoảng CPU kế tiếp
0 p1 7
2 p2 4
4 p3 1
5 p4 5
a)Thể hiện bằng biểu đồ Gantt.
b)Tính thời gian chờ trung bình của các tiến trình.
Trả lời:
a)Biểu đồ Gantt:






Giải thích:
Đầu tiên ta vẽ các thời điểm đến:0,2,4,5.
Sai khi chon xong thì khoảng CPU của các tiến trình là:
P1=7-2=5.
P2=4-2=2.
P3=1-1=0 //tiến trình P3 đã thực hiện xong.
P4=4.
==>Các tiến trình còn lại lần lượt là:P2,P4,P1.
b)ta có:
P1=11-2=9ms.
P2=5-4=1ms.
P3=0 ms.//Không có thời gian chờ
P4=7-5=2ms .
Thời gian chờ trung bình =(9+1+0+2)/4=3ms.

CÁC BẠN CHỈ GIÚP DÙM MÌNH CÁCH ĐƯA HÌNH LÊN NHÉ, MÌNH LÀM HOÀI MÀ KHÔNG ĐƯỢC.

-Multilevel Queue Scheduling:
--- Được chia thành nhiều queue riêng biệt
---------Foreground(Chứa các interactive process)
---------Background(Chứa các backprocess)
--- Mỗi hàng chờ có thuật giải điều phối riêng
--------- Foreground: RR
---------Background:FCFS
--- Quan hệ giữa các mức
---------Lập lịch với mức độ ưu tiên
---------Phân chia thời gian: mỗi queue nhận được một lượng thời gian CPU nào đó mà có thể lập lịch các tiến trình của nó
--- Tiến trình trong queue có mức độ ưu tiên thấp hơn chỉ có thể chạy khi các queue có mức ưu tiên thấp hơn rỗng
--- Tiến trình có mức ưu tiên cao hơn khi vào ready queue không ảnh hưởng đến tiến trình đang chạy có mức ưu tiên thấp hơn.
Ví dụ:
Việc phục vụ khách trong nhà hàng
--- Thực khách sẽ đến và gọi món ăn, nước uống.
--- Mỗi thức ăn và nước uống đều có thời gian chuẩn bị là khác nhau.
---Thời gian trung bình đợi của thực khách là khác nhau
---------Nếu khách hàng quen thân hoặc đặc bàn trước chúng ta sẽ ưu tiên trước (lập lịch với mức độ ưu tiên)
---------Còn lại thường thì các nhà hàng sẽ phục vụ theo kiểu người nào đến trước phục vụ trước(FCFS)
*Multilevel Feedback Queue Scheduling
--- Điều tiết tiến trình có thể di chuyển giữa các queue khác nhau
--- Đa mức hàng đợi đặc trưng bởi các thông số sau:
---------Số lượng hàng chờ
---------Giải thuật lập lịch cho mỗi hàng chờ
---------Phương pháp sử dụng để xác định khi nào thì tăng, giảm mức ưu tiên của một tiến trình
---------Phương pháp được sử dụng để xác định hàng chờ nào mà tiến rình sẽ đến khi nó cần được phục vụ.

• Biểu đồ Gantt:

https://2img.net/r/ihimg/photo/my-images/703/rrsw.jpg/

• Thời gian chờ TB :

((78-3-35)+(50-10-20)+(40-25-15))/3=20 ms
Mong thầy và các bạn góp ý ! Em cám ơn

SƠ ĐỒ THANH NGANG (SƠ ĐỒ GANTT)

Sơ đồ Gantt là một trong những công cụ cổ điển nhất mà vẫn được sử dụng phổ biến trong quản lý tiến độ thực hiện dự án. Sơ đồ này được xây dựng vào năm 1915 bởi Henry L. Gantt, một trong những nhà tiên phong về lĩnh vực quản lý khoa học.

Trong sơ đồ Gantt, các công tác được biểu diễn trên trục tung bằng thanh ngang, thời gian tương ứng được thể hiện trên trục hoành.

*Multilevel Queue Scheduling - MQS

-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-Quan hệ giữa các mức:
+ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

* Multilevel Feedback Queue Scheduling - MFQS

-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+Thuật giải điều phối cho mỗi mức.
+Phương thức nâng cấp tiến trình.
+Phương thức hạ cấp tiến trình.
+Phương thức chọn hàng chờ cho tiến trình mới.

Ví dụ: Trong ga Hòa Hưng có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ cửa 2: cho thương binh, Mẹ VNAH.
+ cửa 3: cho những người bình thường, khách vảng lai.
+ cửa 4: khách có độ ưu tiên thấp hơn.
+ cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.
ĐỘ ƯU TIÊN HẠ TỪ TRÊN XUỐNG, KHÔNG CÓ SỰ ƯU TIÊN TỪ MỨC DƯỚI ĐI NGƯỢC LÊN MỨC TRÊN.

nguyenthingocloan (I11C) đã viết:*Multilevel Queue Scheduling - MQS

-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-Quan hệ giữa các mức:
+ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

* Multilevel Feedback Queue Scheduling - MFQS

-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+Thuật giải điều phối cho mỗi mức.
+Phương thức nâng cấp tiến trình.
+Phương thức hạ cấp tiến trình.
+Phương thức chọn hàng chờ cho tiến trình mới.

Ví dụ: Trong ga Hòa Hưng có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ cửa 2: cho thương binh, Mẹ VNAH.
+ cửa 3: cho những người bình thường, khách vảng lai.
+ cửa 4: khách có độ ưu tiên thấp hơn.
+ cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.
ĐỘ ƯU TIÊN HẠ TỪ TRÊN XUỐNG, KHÔNG CÓ SỰ ƯU TIÊN TỪ MỨC DƯỚI ĐI NGƯỢC LÊN MỨC TRÊN.

Cảm ơn bạn Nguyễn Thị Ngọc Loan nhiều,
Học kỳ này quyết tâm qua môn Hệ điều hành nhưng dạo này công việc gặp khó khăn nhiều quá nên Hoàng không đến lớp thường xuyên như trước được
chỉ biết tối lên forums xem các bài post của các bạn, để biết tiến trình học tới đâu rồi.
các bạn giúp Hoàng học nhé.
Bạn Loan chắc giỏi lắm,có gì giúp Hoàng nhé
Regards
Trần Thanh Hoàng

KimHue36 (I11C) đã viết:

• Biểu đồ Gantt:

https://2img.net/r/ihimg/photo/my-images/703/rrsw.jpg/

• Thời gian chờ TB :

((78-3-35)+(50-10-20)+(40-25-15))/3=20 ms
Mong thầy và các bạn góp ý ! Em cám ơn

bạn ơi hình như biểu đồ sai thì phải? mình dùng giải thuật round robin với thời lượng là 10MS mà. rất sory vì mình chưa giải bài này trên máy, mình mới giải trên giấy thui. và thời gian chờ TB là 25.
đây là ý kiến của mình, có gì không phải xin bỏ qua nha.thanks

- Có 3 hàng chờ Ready với độ ưu tiên khác nhau. Hoạt động các tiến trình ở 2 mức trên (Mức 1: Độ 0 và Mức 2: Độ 1) được điều phối bằng thuật giải RRS (Round Robin Scheduling) với thời lượng tương ứng là 8 và 16 ms. Mức 3 (độ ưu tiên thấp nhất) dùng thuật giải FCFS (First-come, first-served Scheduling)(đến trước chạy trước, không có tiếm quyền).
- Đầu tiên, tiến trình mới được đưa vào hàng chờ Mức 1 (Độ 0 là độ ưu tiên cao nhất).
- Hệ điều hành có thể "Hạ cấp" tiến trình bằng cách đưa xuống mức dưới, khi tiến trình đó ảnh hưởng đến hiệu năng toàn hệ (ví dụ, quá "Hướng CPU").
- Theo sơ đồ, có sự "Nâng cấp" tiến trình từ Mức 3 (Độ 2) lên Mức 2 (Độ 1), khi một tiến trình cần được ưu tiên hơn nữa (ví dụ, khi nó làm việc lâu mà vẫn chưa xong hoặc trước đó quá "Hướng I/O" mà bây giờ cần CPU để nhanh chóng hoàn tất công việc).

Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

Biểu đồ gant:



thời gian chờ Tb:
(35+20+20)/3= 25ms

các bạn tham khảo, bổ sung dùm mình nha. thanks

1. Vì sao hệ điều hành phải có chức năng điều phối CPU?
Trong các hệ đa chương thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống.
Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất  chiến lược định thời CPU.

2.Năm tiêu chí điều phối CPU là những tiêu chí nào?
1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.
CHÚC CÁC BẠN HỌC TỐT!

NguyenHaThanh97 (I11C) đã viết:Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

Số liệu trên biểu đồ Gantt đó bạn.các số trong dấu () là thời gian chờ còn số 4 là số tiến trình.

NguyenHaThanh97 (I11C) đã viết:Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

P1: 53
P2: 17
P3: 68
P4: 24
Thoi luong 20ms

ban ap dung theo cong thuc
Ti =Thoi diem ket thuc - thoi gian den -thoi gian dung cpu
dau tien la P1 (0,57,24)
0= Thoi diem ket thuc (20) - thoi gian den (0) - thoi gian dung cpu(20)
57 = 97 - 20 -20
24 = 134 - 97 -13
ban ap dung tuong tu cho P2,P3 & P4
Theo cach hieu cua minh la nhu vay, mong cac ban dong gop them y kien

NguyenHaThanh97 (I11C) đã viết:Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ( (0+57+24) + 20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

theo cách hiểu của mình vì các tiến trình có thời điểm đến như nhau (đều =0) ta có:

• p1:
  0->20 p1 đang chạy nên ko chờ
  20->77 p2 p3 p4 đang chạy nên p1 chờ trong khoản 77-20 = 57
  77->97 p1 đang chạy nên ko chờ
  97->121 p3 p4 đang chạy nên p1 chờ trong khoản 121-97 = 24
  => Tp1=0+57+24
  121->134 p1 đang chạy và kết thúc

• p2:
  0->20 p1 đang chạy nên p2 chờ trong khoản 20-0 = 20
  20->37 p2 đang chạy và kết thúc
  =>Tp2=20

• p3:
  0->37 p1 p2 đang chạy nên p3 chờ trong khoản 37-0=37
  37->57 p3 đang chạy nên không chờ
  57->97 p4 p1 đang chạy nên p3 chờ trong khoản 97-57=40
  97->117 p3 đang chạy nên không chờ
  117->134 p4 p1 đang chạy nên p3 chờ trong khoản 134-117=17
  =>Tp3= 37+40+17
  134->162 p3 chạy và kết thúc

• tương tự ta có
  p4 :
  với Tp4=57+40

TGCTB = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 ms

Trong các hệ đa chương thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống.
Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, cần phải giải quyết vấn đề phân
chia, lựa chọn process thực thi sao cho được hiệu quả nhất => chiến lược định thời CPU.

Đến trước - Phục vụ trước (First-Come, First-Served Scheduling - FCFS)
- Đơn giản, dễ thực hiện.
- Các tiến trình trong Ready Queue được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO (First-In, First-Out).
- Thời gian chờ trung bình khá lớn

- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.