Thảo luận Bài 6

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

1. Giống nhau:
- Cùng là điều phối với các hàng chờ nhiều mức (nhiều mức nghĩa là nhiều hàng đợi/hàng chờ).
- Mỗi mức có thuật giải điều phối riêng. Ví dụ: Round-Robin (RRS) hoặc FCFS

2. Khác nhau:
* Điều phối hàng chờ nhiều mức (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.
Ví dụ: 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.

* Điều phối hàng chờ nhiều mức có điều tiết (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.
Ví dụ: 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ụ: (Lấy từ khóa trước)
Trong nhà ga có 3 cửa bán vé, những người mua vé xếp hàng vào 3 cửa. Có 3 loại khách hàng với 3 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.
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 đó, không có sự chia độ ưu tiên.
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.

*Công thức tính thời gian chờ của tiến trình Pi
Pi = (Thời gian kết thúc - thời điềm đến) - khoảng CPU

1. Biểu đồ Gantt là gì?
Biểu đồ Gantt là đồ thị với những thanh nằm ngang để chỉ hoạt động ngược lại với ngày. Đây là công cụ để đo lường tiến độ thực hiện dự án so với kế hoạch đề ra.

Cách vẽ một biểu đồ Gantt:

Vẽ đường thời gian của dự án/ chương trình từ đầu cho đến cuối dự án trên trục toạ độ (trục tung- nằm ngang);
Trên trục hoành (ngược lại với trục tung) thể hiện các hoạt động cần được hoàn thành trong suốt dự án/ chương trình;
Vẽ một thanh nằm ngang ở mỗi mức độ của hoạt động để chỉ khoảng thời gian thực hiện mỗi công việc.

Đối với khoảng thời gian dự kiến thực hiện hoạt động có thể sử dụng một công thức để tính thời gian dự kiến:



Trong đó:
PT là thời gian dài nhất hoạt động có thể diễn ra
ET là thời gian ước tính cho hoạt động thực hiện
OT là thời gian ít nhất khi hoạt động diễn ra
ST là thời gian dự kiến và sử dụng ST trên biểu đồ

2. Tại sao biểu đồ Gantt có ý nghĩa?
Biểu đồ Gantt là một cách đơn giản và dễ hiểu để giám sát tiến độ của các hoạt động khi thực hiện dự án/ chương trình

3. Biểu đồ Gantt hỗ trợ như thế nào?
Biểu đồ Gantt hỗ trợ bạn theo 2 cách chính. Đầu tiên, chúng cung cấp cho bạn hình ảnh trực quan về các hoạt động và thời gian thực hiện. Thứ hai, chúng cho phép bạn truyền đạt động tin bằng một cách dễ dàng với các đồng nghiệp khác trong nhóm về trạng thái của dự án/ chương trình.

4. Biểu đồ Gantt được áp dụng ở đâu?
Biểu đồ Gantt được sử dụng cho bất kỳ dự án/ chương trình để xác định tiến độ và làm rõ mục tiêu. Chúng giúp liên kết giữa mọi người/ nguồn lực trong dự án cùng với nhiều hoạt động trong đó.

5. Biểu đồ Gantt có ý nghĩa khi nào?
Khi bạn đang quản lý một chương trình/ dự án có nhiều hoạt động phức tạp, biểu đồ Gantt được khuyên dùng, đặc biệt nếu bạn yêu cầu lao động đầu vào từ các nguồn khác nhau để hoàn thành các công việc này. Nó giúp bạn nắm rõ được mối quan hệ giữa các công việc, ví dụ khi các công việc thực hiện liên tiếp nhau, hoặc có thể được thực hiện song song.

6. Biểu đồ Gantt đem lại lợi ích cho ai?
Biểu đồ Gantt có lợi cho cả những người quản lý chương trình/ dự án và tất cả những ai tham gia thực hiện công việc trong dự án.

Video hướng dẫn Cách tạo biểu đồ Gannt trong Excel:
http://www.tinhoc365.com/gantt2.html

(Sưu tầm)

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.

Điều phối hàng chờ nhiều mức (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, 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.

Điều phối hàng chờ nhiều mức có điều tiết ( Multilevel Feedback Queue Scheduling – MFQS )
• Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
• MFQS đặc trưng bởi các thông số:
- Số mức ( số hàng chờ )
- 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ờ ( chọn mức ) cho tiến trình mới

NguyenChiKien(HLT3) đã viết:
*Công thức tính thời gian chờ của tiến trình Pi
Pi = (Thời gian kết thúc - thời điềm đến) - khoảng CPU

Biểu đồ GANT này chúng ta có thể vẽ thành 1 lưới các ô và tô màu chúng theo từng thời điểm thực thi và lượng Quantum được không? Làm vậy có thể nhìn trực quan hơn và dễ hiểu hơn biểu đổ hiện tại, biểu đồ hiện quá ngắn gọn nên đôi khi sẽ hơi khó hiểu.

LamQuocVu(HLT3) đã viết:Điều phối hàng chờ nhiều mức (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, 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.

Điều phối hàng chờ nhiều mức có điều tiết ( Multilevel Feedback Queue Scheduling – MFQS )
• Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
• MFQS đặc trưng bởi các thông số:
- Số mức ( số hàng chờ )
- 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ờ ( chọn mức ) cho tiến trình mới

theo như bức hình thứ hai về Quantum thì càng có độ ưu tiên thấp hơn thì lượng Quantum làm thấp hơn, phân phối như vậy liệu có được sự hiệu quả khi ưu tiên cao hơn thì được làm ít, thấp hơn làm nhiều, như vậy thời gian thực thi có dài ra? Liệu mình có hiểu sai chăng?

VanPhuAnhTuan95(HLT3) đã viết:

NguyenChiKien(HLT3) đã viết:
*Công thức tính thời gian chờ của tiến trình Pi
Pi = (Thời gian kết thúc - thời điềm đến) - khoảng CPU

Biểu đồ GANT này chúng ta có thể vẽ thành 1 lưới các ô và tô màu chúng theo từng thời điểm thực thi và lượng Quantum được không? Làm vậy có thể nhìn trực quan hơn và dễ hiểu hơn biểu đổ hiện tại, biểu đồ hiện quá ngắn gọn nên đôi khi sẽ hơi khó hiểu.

Đó là cách của thầy Quang, đúng k0 bạn.... , bạn nên nhớ là đề bài vẽ bằng Biểu đồ GANTT mà biểu đồ GANNT thì fải vẽ như thế này thôi... còn cách nào khác hay vẽ theo ý bạn thì mình hỏng biết thầy chấm điểm thế nào thôi... chứ cách nào cũng là biểu diễn quá trình điều phối CPU cả...

Henry Laurence Gantt:

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.

NguyenChiKien(HLT3) đã viết:
*Công thức tính thời gian chờ của tiến trình Pi
Pi = (Thời gian kết thúc - thời điềm đến) - khoảng CPU

để các bạn hiểu rõ hơn mình xin giải thích bảng hỗ trợ
như đề bài ta có:
P1 có thời điểm bắt đầu =3,khoảng CPU là 37 : 3(37)
tương tự ta có P2 : 10(20) và P3:24(14). khoảng chờ q=10ms ta đặt là T=10ms.
-Ta có thời điểm bắt đầu là 3 nên P1 được tiếm quyền. so sánh giữa khoảng CPU : 37> T=10. do đó P1 chạy vời thời lượng min P1(10 ms). chạy hết 10ms,P1 đến vị trí 13 và khoảng CPU giảm 37-10= 27 ms.
-Tại thời điểm là 13,P2 đã đến( Vì thời điểm đến của P2=10 <13 )nên P2 tiếm quyền.so sánh khoảng CPU 20ms>T=10ms
=> P2(10).P2 bắt đầu chạy từ thời điểm P1 kết thúc là 13+10= 23 và khoảng CPU giảm 20-10=10.=>23(10)
-tại thời điểm 23,do P3 chưa đến nên P1 tiếm quyền. khoàng CPU là 27>10=>P1(10).Tương tự như trên ta được 33(17).
-tại thời điểm 33,P2 tiếm quyền(vì P2 chờ ở thời điểm 23). ta được 43(0). lúc này P2 đã chạy xong.
- Tại thời điểm 43,P3 tiếm quyền(vì đang chờ ở thời điểm 24). ta được P3(10) : 53(14-10=4).
-Tại thời điểm 53.P1 tiếm quyền(vì đang chờ ở 33)=> P1(10):63(17-10=7).
-Tại thời điểm 63.P3 tiếm quyền. Lúc này do khoảng CPU của P3 còn lại = 4=>P3(4): 63+4=67(4-4=0). P3 kết thúc.
-Tại thời điểm 67,P1 tiếm quyền và chạy với thời lượng còn lại là 7ms.Ta được P1(7): 71(0).P1 kết thúc.
dựa vào bảng trợ giúp này ta dễ dàng vẽ được biểu đồ GANTT.Chú ý. thời điểm kết thúc của tiến trình này là bắt đầu của tiến trinh tiếp theo

Giới thiệu về sơ đồ Gantt và Henry Laurence Gantt

Sơ đồ ngang Gantt, còn gọi là Sơ đồ Gantt hay biểu đồ Gantt, (tiếng Anh là: Gantt chart), là một dạng thể hiện tiến độ dự án cổ điển nhất, được Henry Gantt phát minh ra vào năm 1910. Tuy là cổ điển nhưng do tính chất đơn giản dễ hiểu của nó mà hiện nay sơ đồ ngang Gantt vẫn được dùng phổ biến trong quản lý dự án, thậm chí còn được cải tiến, dùng trong phần mềm quản lý dự án hiện đại như; Microsoft Project, để chuyển đổi việc thể hiện các dạng tiến độ phức tạp như sơ đồ mạng (dự án).

Henry Laurence Gantt
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ăm1910. 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.

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ăm1893. 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.

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.


[Nguồn: Wikipedia]

Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình Running sang Waiting.
- Khi tiến trình cần thực hiện nhập xuất thì trình điều phối sẽ tìm kiếm một tiến trình khác để câp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.
2. Khi tiến trình chuyển từ Running sang Ready.
- Khi thời gian thực hiện của tiến trình vượt quá thời gian quy định (vì hệ điều hành chia thời gian) thì HĐH sẽ ngừng cấp CPU và đưa tiến trình vào Ready để cấp CPU cho một tiến trình khác. Trường hợp này có sự can thiệp của HĐH để lấy CPU => điều phối có tiếm quyền.
3. Khi tiến trình chuyền từ Waiting sang Ready.
- Sau khi quá trình nhập xuất đã xong, tiến trình lại được đưa vào hàng chờ. Lúc này HĐH sẽ kiểm tra xem có thể tiếp tục đưa tiến trình chờ đó chạy tiếp hay không? Nếu có sẽ cấp CPU cho tiến trình này tiếp tục làm việc. Trường hợp này có sự can thiệp của HĐH => điều phối có tiếm quyền.
4. Khi tiến trình kết thúc công việc.
- Sau khi tiến trình hoàn tất công việc thì tự trả CPU lại cho HĐH, HĐH sẽ tìm một tiến trình thích hợp khác để cấp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.

- Điều phối không tiếm quyền là khi tiến trình giữ CPU cho đến khi kết thúc hoặc chuyển sang trạng thái waiting mà không có sự can thiệp thu hồi CPU của HĐH.
- Điều phối có tiếm quyền là khi HĐH can thiệp để thu hồi CPU để cấp cho một tiến trình khác hoạt động.

A. 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.

B.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.

1.FCFS (First-Come, First-Served Scheduling - Đến trước, phục vụ trước ):
- CPU được cấp phát cho tiến trình đầu tiên trong hàng chờ Ready, 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 không tiếm quyền. Hệ điều hành không thể lấy lại CPU khi đã cấp phát cho tiến trình đến khi tiến trình kết thúc xử lý và trả lại CPU cho HĐH.

- Thời gian chờ trung bình khá lớn.

- Có thể xảy ra hiện tượng tích lũy thời gian chờ, khi các tiến trình có khoảng CPU ngắn đến sau phải chờ đợi một tiến trình có khoảng CPU lớn đến trước kết thúc xử lý.

- Giải thuật này không phù hợp với các hệ phân chia thời gian, vì trong các hệ này, cần cho phép mỗi tiến trình được cấp phát CPU đều đặn trong từng khoảng thời gian nhất định.

Ví dụ: Các bệnh nhân xếp hàng chờ khám bệnh, mỗi người sẽ được cấp phát 1 số thứ tự, người đến trước sẽ được cấp phát số nhỏ hơn người đến sau. Khi đọc số vào khám sẽ đọc từ nhỏ đến lớn, như vậy người đến trước sẽ được khám trước.

2. SJFS (Shortest-Job-First Scheduling - Ngắn hơn, chạy trước):
- Là trường hợp đặc biệt của thuật giải FCFS. Gọi đúng hơn là Shortest-Next-CPU-Burst, nghĩa là nếu tiến trình kế tiếp có khoảng CPU nhỏ nhất sẽ được ưu tiên chạy trước. Trong trường hợp bằng nhau thì dùng thuật giải FCFS. Có 2 phương án:

• Không tiếm quyền: tiến trình hiện hành sẽ được chạy cho đến hết khoảng CPU của nó rồi mới xét đến tiến trình kế tiếp.
  
  Ví dụ: một người đang mua 7 vé tàu ở ga Hoà Hưng. Sau khi mua được 2 vé thì có 1 người cũng đến mua vé, người này mua 3 vé. Sau đó khi mua đến vé thứ 3 thì cũng có một người đến mua 1 vé. Người bán vé sẽ tiếp tục bán cho người đầu tiên đến khi nào đủ 7 vé. Sau đó, người bán vé sẽ bán cho người mua 1 vé, mặc dù người này đến sau cùng nhưng do số vé ít hơn người thứ 2 nên được bán trước. Khi bán xong thì sẽ đến lượt người thứ 2.
  

• Có tiếm quyền: nếu ở thời điểm tiến trình hiện hành đang chạy mà có một tiến trình mới đến và tiến trình này có khoảng CPU nhỏ hơn khoảng CPU còn lại của tiến trình đang chạy thì tiến trình đang chạy sẽ được ngừng lại và thay thế bằng tiến trình mới.
  
  Ví dụ: cũng trong ví dụ trên, nhưng khi bán đến vé thứ 2 cho người đầu tiên thì người thứ 2 xuất hiện, do người này chỉ mua 3 vé và ít hơn số vé còn lại của người đầu tiên là 5 nên người bán vé sẽ ngừng bán cho người đầu tiên và quay sang bán vé cho người thứ 2. Khi người thứ 2 mua được 1 vé thì người thứ 3 xuất hiện, do số vé của người thứ 3 là 1 ít hơn số vé còn lại của người thứ 2 nên người thứ 3 sẽ được ưu tiên bán trước. Khi bán xong 1 vé cho người thứ 3, người bán vé sẽ tiếp tục quay lại bán tiếp 2 vé còn lại của người thứ 2. Sau khi bán xong mới bán 5 vé cho người thứ 1.
  

- Đây là một thuật giải tối ưu, nhưng khó khăn là phải biết ước lượng khoảng CPU kế tiếp.

3 – PS (Priority Scheduling - Điều phối theo độ ưu tiên)
- Mỗi tiến trình được gán cho một số nguyên (priority number) để ấn định độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất (priority number nhỏ 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ể tiếm quyền hay không tiếm quyền. Khi một tiến trình được đưa vào hàng chờ Ready, độ ư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ối với độ ưu tiên có tiếm 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. Còn giải thuật không tiếm quyền sẽ chỉ đơn giản chèn tiến trình mới vào hàng chờ Ready, và tiến trình hiện hành vẫn tiếp tục xử lý cho hết khoảng CPU dành cho nó.

- Tình trạng ‘đói CPU’ (starvation) là một vấn đề chính yếu của các giải thuật sử dụng độ ưu tiên. Các giải thuật này có thể để các tiến trình có độ ưu tiên thấp (priority cao) chờ đơi CPU trong thời gian có thể đến vô hạn ! Để ngăn cản các tiến trình có độ ưu tiên cao chiếm dụng CPU vô thời hạn, bộ điều phối sẽ tăng dần độ ưu tiên của các tiến trình này theo thời gian chờ đợi (ví dụ 15’ lại tang thêm 1 độ). Nếu độ ưu tiên của tiến trình này tang lên cao hơn tiến trình có độ ưu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU. Quá trình này gọi là sự “tăng tuổi” (aging) tiến trình.

4 – RRS (Round Robin Scheduling – Điều phối theo vòng Robin)
- Hàng chờ Ready đượ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 hàng chờ một khoảng thời gian sử dụng CPU gọi là Time quantum (thường từ 10-100 ms). Đây là một giải thuật điều phối như kiểu điều phối FCFS nhưng không tiếm quyền khi đang trong thời gian sử dụng của nó và bị tiếm khi hết thời gian. Khi đó, hệ điều hành sẽ 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 hàng chờ Ready để đợi được cấp CPU trong lượt kế tiếp.

- Nếu có n tiến trình và thời lượng là q, mỗi tiến trình sẽ nhận được 1/n thời gian CPU bao gồm các đoạn không quá q đơn vị thời gian.

• q lớn => RRS là FCFS
  

• q nhỏ => RRS được gọi là thuật giải chia sẻ CPU
  

Vấn đề đáng quan tâm đối với giải thuật RRS là độ dài của quantum. Nếu thời lượng quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu quả. Nhưng nếu sử dụng quantum quá lớn sẽ làm tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống.

Ví dụ: trong 1 nhà hàng chỉ có 1 người bồi bàn và người này sẽ phục vụ cho tất cả các bàn trong 1 khoảng thời gian nhất định. Sau khi hết khoảng thời gian đó, người phục vụ sẽ đi đến bàn kế tiếp. Cứ thế khi đi hết tất cả các bàn thì sẽ quay lại bàn đầu tiên.

5 - MQS (Multilevel Queue Scheduling – Điều phối hàng chờ nhiều mức)
- Ý tưởng chính của giải thuật là phân lớp các tiến trình tùy theo độ ưu tiên của chúng để có cách thức điều phối thích hợp cho từng nhóm. 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ờ bao gồm các tiến trình có cùng độ ưu tiên và được áp dụng một giải thuật điều phối thích hợp để điều phối. Ngoài ra, còn có một giải thuật điều phối giữa các nhóm, thường giải thuật này là giải thuật không tiếm quyền và sử dụng độ ưu tiên cố định. Một tiến trình thuộc về hàng chờ ở cấp ưu tiên i sẽ chỉ được cấp phát CPU khi các hàng chờ ở cấp ưu tiên lớn hơn i đã trống.

- Quan hệ giữa các mức:

• Ưu tiên cố định: Thực hiện hoàn thành tất các các tiến trình ở mức trên rồi mới chuyển xuống mức dưới. Nếu khi đang chạy một 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 bởi tiến trình mới ở mức cao hơn.
  

• 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.
  

Ví dụ: trong 1 nhà ga có 5 cổng bán vé. Cổng 1 có độ ưu tiên cao nhất dành cho các nhân viên của nhà ga. Cổng 2 dành cho người có công cách mạng. Cổng 3 dành cho người già, người khuyết tật. Cổng 4 dành cho học sinh, sinh viên. Cổng 5 dành cho những người không thuộc các đối tượng trên và có độ ưu tiên thấp nhất.

6 - MFQS (Multilevel Feedback Queue Scheduling- Điều phối hàng chờ nhiều mức có điều tiết)
- Đối với thuật giải MQS, một tiến trình sẽ được gán vĩnh viễn với một hàng chờ ở cấp ưu tiên i khi nó được đưa vào hệ thống. Các tiến trình sẽ không di chuyển giữa các hàng chờ. Cách tổ chức này sẽ làm giảm chi phí điều phối, nhưng lại thiếu linh động và có thể dẫn đến tình trạng ‘đói CPU’ cho các tiến trình thuộc về những hàng chờ có độ ưu tiên thấp. Do vậy có thể xây dựng giải thuật điều phối nhiều cấp ưu tiên và xoay vòng. Giải thuật gọi là MFQS sẽ chuyển dần một tiến trình từ hàng chờ có độ ưu tiên cao xuống hàng chờ có độ ưu tiên thấp hơn sau mỗi lần sử dụng CPU (ví dụ tiến trình hướng CPU). Cũng vậy, một tiến trình chờ quá lâu trong các hàng chờ có độ ưu tiên thấp cũng có thể được chuyển dần lên các hàng chờ có độ ưu tiên cao hơn (tiến trình hướng I/O).

- Khi xây dựng một giải thuật điều phối nhiều cấp ưu tiên và xoay vòng cần quyếtđịnh các tham số:

• Số mức (số hàng chờ).
  

• Thuật giải điều phối cho mỗi mức.
  

• Phương pháp nâng cấp tiến trình.
  

• Phương pháp hạ cấp tiến trình.
  

• Phương pháp chọn hàng chờ (chọn mức) cho tiến trình mới.
  

Ví dụ: một nhà ga có 4 cổng bán vé được ưu tiên theo thứ tự cổng 1 > cổng 2 > cổng 3 > cổng 4. Trong những dịp lễ tết, nhà ga sẽ thường đông và mọi người sẽ được xếp vào các cổng, nhưng trong cổng số 3 có 1 cụ già xếp hàng đã lâu và có vẻ rất mệt mỏi, mọi người mới đề nghị ưu tiên cho cụ và cụ già được xếp vào cổng 1 để mua vé.

Ngoài ra còn một giải thuật nữa nhưng không được nhắc đến trong bài học đó là giải thuật điều phối xổ số (Lottery). Ý tưởng chính của giải thuật là phát hành một số vé số và phân phối cho các tiến trình trong hệ thống. Khi đến thời điểm ra quyết định điều phối, sẽ tiến hành chọn 1 vé "trúng giải", tiến trình nào sỡ hữu vé này sẽ được nhận CPU. Giải thuật Lottery cung cấp một giải pháp đơn giản nhưng bảo đảm tính công bằng cho thuật toán điều phối với chi phí thấp để cập nhật độ ưu tiên cho các tiến trình.

Đồng bộ hóa tiến trình là điều khiển công việc của luồng và tiến trình sao cho logic và đáp ứng yêu cầu đặt ra.
Mục đích của đồng bộ hóa tiến trình.
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
ví dụ: bài toán sản xuất tiêu thụ.
một bạn trong lớp lên bảng (tài nguyên dùng chung của lớp) ghi thông tin cá nhân nhưng chưa ghi xong thì bạn khác dưới lớp chụp lại thông tin trên sẽ không đúng. muốn lấy thông tin chính xác thì bạn dưới lớp cần lấy thông tin của bạn trên bảng ghi phải chờ bạn ấy ghi hết thông tin rồi mới chụp ảnh.
- Tránh Deadlock ( hiện tượng kẹt tiến trình).
ví dụ: hiện tượng kẹt xe khi có cảnh sát giao thông điều tiết phân luồng thì sẽ không còn kẹt xe nữa.

- 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 .
Ví dụ: Trong phòng bán vé ở một ga tàu hỏa, sẽ có những thứ tự ưu tiên cho người mua vé, ưu tiên cho người tàn tật, người già, phụ nữ có thai, người đến trước, đến sau...
- Độ ưu tiên của tiến trình do hệ điều hành qui định và có thể bị thay đổi, điều phối với độ ưu tiên có thể độc quyền hay không độc quyền.
- Điều phối với độ ưu tiên không độc quyền sẽ thu hồi tài nguyên, từ các tiến trình hiện hành để cấp cho tiến trình mới với độ ưu tiên cao hơn.
- Điều phối với độ ưu tiên, độc quyền sẽ chèn tiến trình mới vào danh sách tại vị trí phù hợp

Phân biệt thuật giải MQS với thuật giải MFQS

-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 FCFS đến trước phục vụ trước.

*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ụ.
- Giống nhau: Thuật giải Multilevel Queue Scheduling (Điều phối hàng chờ nhiều mức) và Multilevel Feedback Queue Scheduling (Điều phối hàng chờ nhiều mức có điều tiết) cùng sử dụng nhiều mức hàng chờ với độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng thuật giải riêng, ví dụ Round-Robin (RRS) hoặc FCFS.
- Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.
- Ví dụ minh hoạ: Phòng bán vé tàu hoả có thể có nhiều cửa bán vé với mức ưu tiên khác nhau, trong khi chỉ có 1 người bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua vé (các tiến trình) như người mua bình thường, người mua là thương binh, nguời mất sức lao động,...

NguyenBaoLoc70(I22A)

Tổng số bài gửi: 12
Join date: 20/03/2013

Xem lý lịch thành viên Gửi tin nhắn

-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 và không có tiếm quyền:
Giống nhau:
- Được dùng trong đ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:
-không tiếm quyền: sơ đồ chỉ điều chỉ tiến hành trong tình huống 1 và 4 ,tình huoosg 2 và 3 không điều phối được. tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc chuyển sang trạng thái waiting.
-có tiếm quyền: sơ đồ điều phối tiến hành trong cả 4 tình huống.(ta có thể lấy tiến trình nào cũng được)

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ý.

Giới thiệu

Mục tiêu điều phối

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 :

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

Tính hiệu qủa (Efficiency) :

Hệ thống phải tận dụng được CPU 100% thời gian.

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

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 5 34
P2 17 23
P3 24 9
Dùng thuật giải Round-Robin với thời lượng 10 ms để điều phối CPU:
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.

Giải:
a. Biểu đồ Gantt

---| P1 | P1 | P2 | P3 | P1 | P2 | P1 | P2|
5 15 25 35 44 54 64 68 71
b. Thời gian chờ trung bình của các tiến trình:
T(tb)= (T1+T2+…+Tn)/n
T1= (5 – 5)+(15-5)+(44-35)+(64-54)=29
T2=(25-15)+(54-44)+(68-64)=24
T3=(35-25)=10
T(tb)=(29+24+10)/3=21ms

SJFS ( Shortest-Job-First Scheduling )
Có nghĩa là tiến trình có khoảng CPU kế tiếp nhỏ hơn thì được ưu tiên chạy trước, trong trường hợp bằng nhau thì dùng giải thuật FCFS.
Là giải thuật khá tối ưu nhưng phải biết cách ước đoán CPU kế tiếp
SJFS không có tiếm quyền là tiến trình hiện thời được CPU thực hiện đến hết khoảng CPU của nó
SJFS có tiếm quyền là tiến trình mới có next CPU burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế

RRS
Như điều phối FCFS nhưng cho phép tiếm quyền khi tiếng trình đang chạy bị hết thời lượng. Mỗi tiến trình được cấp một thời lượng thưởng từ 10 đến 100 ms, sau khoảng thời gian này nó bị tiếm quyền và bị đưa vào cuối hàng chờ Ready, tiến trình đầu tiên trong hàng chờ Ready được chọn tiếp theo
Nếu có n tiến trình và thời lượng là q, mỗi tiến trình nhận 1/n thời gian CPU bao gồm các đoạn không quá q đơn vị thời gian
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 đến khi tiến trình mới mức độ ưu tiên cao hơn
Phân bổ theo tỉ lệ thời lượng. Ví dụ: 80% thời lượng CPU dành cho Foreground, 20% dành cho Background.

NguyenChiKien(HLT3) đã viết:
*Công thức tính thời gian chờ của tiến trình Pi
Pi = (Thời gian kết thúc - thời điềm đến) - khoảng CPU

Rất chi tiết và dễ hiểu. Thanks, bạn.