Thảo luận Bài 6

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

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

*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

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!

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ế

Mỗi tiến trình được cấp một số nguyên dùng để ấn định mức độ ưu tiên. CPU luôn dành cho tiến trình có độ ưu tiên cao hơn (độ ưu tiên nhỏ hơn phải nhường cho độ ưu tiên cao hơn). Có 2 phương án :
+ Tiếm quyền (preemptive)
+ Không tiếm quyền ( Non – preemptive)
Trường hợp đặc biệt của PS là SJFS có độ ưu tiên :
P= khoảng cách CPU kế tiếp

Điều phối CPU là một tác vụ chọn một quá trình đang chờ từ hàng đợi sẳn sàng
và cấp phát CPU tới nó. CPU được cấp phát tới quá trình được chọn bởi bộ cấp phát.
điều phối đến trước, được phục vụ trước (FCFS) là giải thuật điều phối đơn giản nhất,
nhưng nó có thể gây các quá trình ngắn chờ các quá trình quá trình quá dài. điều phối
ngắn nhất, phục vụ trước (SJF) có thể tối ưu, cung cấp thời gian chờ đợi trung bình
ngắn nhất. Cài đặt định thời SJF là khó vì đoán trước chiều dài của chu kỳ CPU kế
tiếp là khó. Giải thuật SJF là trường hợp đặc biệt của giải thuật điều phối trưng dụng
thông thường. Nó đơn giản cấp phát CPU tới quá trình có độ ưu tiên cao nhất. Cả hai
điều phối độ ưu tiên và SJF có thể gặp phải trở ngại của việc đói tài nguyên

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.

Ở một công ty, các nhân viên lần lượt được phân công đi công tác ở Đà Nẵng, Long An, Cần Thơ.
Không tiếm quyền : Anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Và anh ta lấy xe đi luôn, không có cách nào để công ty điều xe về ngay lập tức để cho người khác đi công tác.
Có tiếm quyền : Cũng anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Đi giữa đường thì anh A ghé vào quán nghĩ ngơi. Ngay lúc đó, công ty có lệnh điều xe về chở anh B đi công tác ở Long An. Xe lập tức quay về và chở anh B đi Long An. Giữa đường, anh B cũng ghé vào quán nghỉ ngơi. Và lúc đó, công ty lại có lệnh điều xe về chở anh C đi công tác ở Cần Thơ. Cứ thế xe được điều động cho 3 anh đi công tác !

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.
1. 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.
2.Đó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.

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.

HANDLE ConsumerHandle[50]; // Khai báo một mảng mục quản với 50 phần tử
DWORD ConsumerID[50]; // Khai báo một mảng số hiệu với 50 phần tử
for(int i=0;i<50;i++) // Cho một vòng for chạy với giá trị của i thay đổi từ 0->49.
Consumerhandle[i]=CreateThread(0,0,
LPTHREAD_START_ROUTINE)Consumer,0,4,ConsumerID[i]); // Hàm CreateThread dùng để thiết lập giá trị mới có số hiệu là ConsumerID[i] với giá trị chạy từ 0->49 và i thay đổi theo dòng lặp for và hàm CreateThread trả về mục quản của luồng mới được tạo và được gán cho phần tử mảng ConsumerHandle[i]. Sau đó Consumer dùng để điều khiển công việc của hàm xuất tương ứng. Số 4 thể hiện luồng này trạng thái ngủ, chờ được đánh thức. Thầy giải thích rằng tại sao dùng số 4 là do thầy tham khảo sách viết thế. Có thể thay đổi số khác, như số 5 chẳng hạn nhưng không chạy.

Mong thầy sữa giùm em và các bạn bổ sung

Với tư cách là một ngành khoa học, quản lý dự án phát triển từ những ứng dụng trong các lĩnh vực khác nhau như xây dựng, kỹ thuật và quốc phòng. Ở Hoa Kỳ, hai ông tổ của quản lý dự án là Henry Gantt, được gọi là cha đẻ của kỹ thuật lập kế hoạch và kiểm soát, người đã cống hiến hiểu biết tuyệt vời của mình bằng việc sử dụng biểu đồ Gantt như là một công cụ quản lý dự án, và Henri Fayol người tìm ra 5 chức năng của quản lý, là cơ sở cho những kiến thức cốt lõi liên quan đến quản lý dự án và quản lý chương trình.

Cả hai ông Gantt và Fayol đều được biết đến như là những học trò, theo trường phái lý thuyết quản lý theo khoa học, của Frederick Winslow Taylor. Thuyết Taylor là nguyên mẫu đầu tiên cho các công cụ quản lý dự án hiện đại, bao gồm cả cấu trúc phân chia công việc (WBS) và phân bổ nguồn lực.

Những năm 1950, đánh dấu sự bắt đầu của kỷ nguyên quản lý dự án hiện đại. Quản lý dự án đã được chính thức công nhận là một ngành khoa học phát sinh từ ngành khoa học quản lý. Một lần nữa, tại Hoa Kỳ, trước những năm 1950, các dự án đã được quản lý trên một nền tảng đặc biệt bằng cách sử dụng chủ yếu là biểu đồ Gantt (Gantt Charts), cùng các kỹ thuật và các công cụ phi chính thức. Tại thời điểm đó, hai mô hình toán học để lập tiến độ của dự án đã được phát triển. "Phương pháp Đường găng" (tiếng Anh là Critical Path Method, viết tắt là CPM) phát triển ở liên doanh giữa công ty Dupont và công ty Remington Rand để quản lý các dự án bảo vệ thực vật và hóa dầu. Và "Kỹ thuật đánh giá và xem xét chương trình (dự án)" (tiếng Anh là Program Evaluation and Review Technique hay viết tắt là PERT), được phát triển bởi hãng Booz-Allen & Hamilton thuộc thành phần của Hải quân Hoa Kỳ (hợp tác cùng với công ty Lockheed) trong chương trình chế tạo tên lửa Polaris trang bị cho tàu ngầm. Những thuật toán này đã lan rộng một cách nhanh chóng sang nhiều doanh nghiệp tư nhân.

Năm 1969, viện Quản lý Dự án (PMI) đã được thành lập để phục vụ cho lợi ích của kỹ nghệ quản lý dự án. Những tiền đề của viện Quản lý dự án (PMI) là những công cụ và kỹ thuật quản lý dự án được chia sẻ bằng nhau giữa các ứng dụng phổ biến trong những dự án từ ngành công nghiệp phần mềm cho tới ngành công nghiệp xây dựng. Trong năm 1981, ban giám đốc viện Quản lý dự án (PMI) đã cho phép phát triển hệ lý thuyết, tạo thành cuốn sách Hướng dẫn về những kiến thức cốt lõi trong Quản lý dự án (PMBOK Guide). Cuốn sách này chứa các tiêu chuẩn và nguyên tắc chỉ đạo về thực hành được sử dụng rộng rãi trong toàn bộ giới quản lý dự án chuyên nghiệp.

BuiTrongHung41(I11C) đã viết: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

bạn tính thời gian chờ trung bình trên không đúng theo mình kết quả phải tính là:
thời gian chờ của:
- p1=(44-25)+(64-54)=29
- p2=(25-17)+(54-35)+(68-64)=31
- p3=35-24=11
vậy thời gian chờ TB=(29+31+11)/3=23,67 ms

mong thầy và các bạn cho ý kiến

1. Trình bày thuật giải điều phối FCFS.
Đế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. (Vd: nộp bài kiểm tra cho Thầy: thì lần lượt nhóm từng 5 người lên theo thứ tự trên bảng -> 5 tiếp người tiếp theo sẽ chờ trong khoảng thời gian hơi lâu)
* Quy tắc FIFO (First-In, First-Out):
- Nguyên tắc :
+ Processor đượ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.
+ FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processor cho đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
VD: Việc phục vụ khách trong nhà hàng. Thực khách sẽ đến và gọi món ăn cho mình. Mỗi món ăn cần thời gian chuẩn bị khác nhau

2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn  Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )

3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): 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ế (Shortest Remaining First).

4. Trình bày thuật giải điều phối RRS.
- Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng.
- Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 mili giây. Sau khoảng thời gian này, nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready. Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
- 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.

5. Trình bày thuật giải điều phối 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.

6. Trình bày thuật giải điều phối MFQS.
- Như MQS 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, 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

TruongMinhTriet(I22B) đã viết:Cách 1: Dùng giải thuật RRS


Thời gian trung bình: ((0+35)+(10+25)+25)/4 = 23,75 (ms)

Cách này do e tự nghỉ ra không bít có đúng hay không nữa: e kết hợp giữa SJFS có tiến quyền với RRS.


Thời gian trung bình: (0 + 20 + 10 + 25 + 0)/4 = 13,75 (ms)

Không bít cách e hiểu và làm có đúng hay không mong thầy có e ý kiến để sửa sai, e xin cảm ơn.

kết hợp luôn à

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

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

ví dụ bai tập:

* 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.5ms
* 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 ms

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.
[sửa]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.
[sửa]Đó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.

Bổ sung so sánh MQS (Multilevel Queue Scheduling ) và MFQS(Multilevel Feedback Queue Scheduling):
Giống nhau:
MQS và MFQS đều điều phối CPU với nhiều hàng chờ.
Khác nhau : MFQS có điều tiết, có phần mềm dẻo hơn MQS

Gantt charts
Main article: Gantt chart


A Gantt chart showing three kinds of schedule dependencies (in red) and percent complete indications.
Gantt created many different types of charts.[7] He designed his charts so that foremen or other supervisors could quickly know whether production was on schedule, ahead of schedule, or behind schedule. Modern project management software includes this critical function even now.
Gantt (1903) describes two types of balances:[8]
the "man’s record", which shows what each worker should do and did do, and
the "daily balance of work", which shows the amount of work to be done and the amount that is done.
Gantt gives an example with orders that will require many days to complete. The daily balance has rows for each day and columns for each part or each operation. At the top of each column is the amount needed. The amount entered in the appropriate cell is the number of parts done each day and the cumulative total for that part. Heavy horizontal lines indicate the starting date and the date that the order should be done. According to Gantt, the graphical daily balance is "a method of scheduling and recording work". In this 1903 article, Gantt also describes the use of:
"production cards" for assigning work to each operator and recording how much was done each day.
In his 1916 book "Work, Wages, and Profits" [9] Gantt explicitly discusses scheduling, especially in the job shop environment. He proposes giving to the foreman each day an "order of work" that is an ordered list of jobs to be done that day. Moreover, he discusses the need to coordinate activities to avoid "interferences". However, he also warns that the most elegant schedules created by planning offices are useless if they are ignored, a situation that he observed.
In his 1919 book "Organizing for Work" [10] Gantt gives two principles for his charts:
one, measure activities by the amount of time needed to complete them;
two, the space on the chart can be used to represent the amount of the activity that should have been done in that time.
Gantt shows a progress chart that indicates for each month of the year, using a thin horizontal line, the number of items produced during that month. In addition, a thick horizontal line indicates the number of items produced during the year. Each row in the chart corresponds to an order for parts from a specific contractor, and each row indicates the starting month and ending month of the deliveries. It is the closest thing to the Gantt charts typically used today in scheduling systems, though it is at a higher level than machine scheduling.
Gantt’s machine record chart and man record chart are quite similar, though they show both the actual working time for each day and the cumulative working time for a week. Each row of the chart corresponds to an individual machine or operator. These charts do not indicate which tasks were to be done, however.
A novel method of displaying interdependencies of processes to increase visibility of production schedules was invented in 1896 by Karol Adamiecki, which was similar to the one defined by Gantt in 1903. However, Adamiecki did not publish his works in a language popular in the West; hence Gantt was able to popularize a similar method, which he developed around the years 1910–1915, and the solution became attributed to Gantt. With minor modifications, what originated as the Adamiecki's chart is now more commonly referred to as the Gantt Chart.[11][12]

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 (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 không tiếm quyền và điều phối có 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.
Trong điều phối không tiếm quyền, trong thời gian 1 tiến trình đang thực hiện thì hệ điều hành không thể lấy CPU của tiến trình để cho tiến trình khác có khoảng CPU kế tiếp ít hơn sử dụng, mà phải chờ tiến trình đó thực hiện xong mới đến tiến trình kế tiếp.

- Đ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 được. Trong điều phối có tiếm quyền, hệ điều hành có thể lấy lại CPU của 1 tiến trình để cho tiến trình khác sử dụng.

Định nghĩa và mục đích điều phí tiến trình

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 đó.