Thảo luận Bài 6

PhamQuangHien_I12A đã viết:

nguyenthingocmai_I12A đã viết:

phamduyI12A đã viết:

nguyenthingocmai_I12A đã viết:

LeThiMaiPhuongI12A đã viết:

Tiến trình	Thời điểm đến(ms)	CPU-Burst
P1	5	22
P2	10	15
P3	20	5

Dùng thuật giải Preemptive SJFS để điều phối CPU
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời điểm chờ trung bình của các tiến trình

a.Biểu đồ Gantt.

Tại thời điểm 5ms P1 sẽ được cấp CPU đầu tiên
Tại thời điểm 10ms,P2 đến, do khoảng CPU của P2 nhỏ hơn P1 nên P2 tiếm quyền P1, lúc này CPU được cấp cho P2, và P2 sẽ chạy hết khoảng CPU của nó
Tại thời điểm 25ms, P3 sẽ được cấp CPU vì P3 có khoảng CPU nhỏ hơn P1
Tại thời điểm 30ms P1 sẽ thực hiện tiếp khoảng CPU còn lại của nó
b.Tính thời điểm chờ trung bình của các tiến trình
P1=(47-5)-22=42-22=20ms
P2=(25-10)-15=15-15=0ms
P3=(30-20)-5=10-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8,3ms
Các bạn bổ sung thêm nha

ví dụ lúc này tại tiến trình P2 thời điểm đến (ms) vẫn là 10 nhưng CPU-Burst (ms) là 20 thì sơ đồ Gantt vẽ thế nào đây bạn?

mình vận chưa hiểu lắm, thời điểm đếm của p3 là 20 nhưng tại sao nó lại nằm ở 25ms??? bạn giải thích dùm mình nhé,cảm ơn nhìu!!!

Thời điểm đến của P2 là 10, của P3 là 20 và tại thời điểm 20 thì lúc này P2 đã chạy được 10ms còn 5ms nữa là xong. Trong khi đó tại thời điểm đến của P3 là 20 cũng có 5ms đáng ra thì P3 sẽ tiếm quyền của P2 nhưng bạn chú ý tới phần lưu ý của thấy: "Trường hợp bằng nhau thì sẽ dùng thuật toán đến trước - phục vụ trước (FCFS)". chính vì vậy mà P2 sẽ được chạy luôn tới hết rồi P3 mới được chạy.

cho mình hỏi tại thời điểm 20ms của Tiến trình P3 sao không vẽ vào biểu đồ gantt-->số 25 trên biểu đồ là tổng của (20+5) hay la (15+10) vậy mình thắc mắc ko hiểu chỗ này cho lắm mong các bạn giải đáp dùm

Theo mình hiểu như thế này:
- Tới thời điểm 20ms là đến thời điểm tiến trình P3 bắt đầu,tiến trình P2 còn 5ms. Tiến trình P2 sẽ được đưa vào hàng đợi Ready cùng với P3,P1. Thì lúc này P1 có thời gian CPU xử lý là 17ms,P2 là 5ms,P3 là 5ms.
Áp dụng thuật giải "Đến trước -Phục vụ trước",nên hệ điều hành sẽ chọn tiến trình P2 tiếp nối ở thời gian 20s và tiến trình P2 sẽ kết thúc ở thời điểm 25ms. Nên số 25 trên biểu đồ là tổng của (20+5).

lethanhsang_I12A đã viết:

Ti?n Trình	Th?i Ði?m Ð?n	Kho?ng CPU (ms)
P1	3	37
P2	10	20
P3	24	14

Dùng thuật toán RRS với thời lượng 10ms dùng CPU
a) Vẽ biểu đồ Gantt
b) Tính thời gian trung bình

Giải:

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
- Thời gian chờ của các tiến trình:
P1 = (74 – 3 – 37) = 34 ms
P2 = (43 – 10 – 20) = 13 ms
P3 = (67 – 24 – 14) = 29 ms
- Thời gian chờ trung bình = (34+13+29) / 3= 25,3 ms

Hình như bài của bạn chưa chính xác vì từ thời điểm 53 đến 63 là P1 chứ ko phải là P2

câu 1: BỐN TÌNH HUỐNG RA QUYẾT ĐỊNH CỦA TRÌNH ĐIỀU PHỐI VÀ PHÂN BIỆT ĐIỀU PHỐI KHÔNG TIẾM QUYỀN VÀ ĐIỀU PHỐI CÓ TIẾM QUYỀN.
_ 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
2.Khi tiến trình chuyển từ Running sang Ready
3.Khi tiến trình chuyển từ Waiting sang Ready
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: 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 khong co Time
* 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
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
Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn No-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
-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 p3 cứ như vậy nó sẽ thực hiện xong các tiến trình

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
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
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 (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.
Ví dụ về biểu đồ Gantt

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

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
Tiến trình Thời điểm đến Khoảng CPU

Tiến trình	Thời điểm đến	Khoảng CPU
P1	3	35
P2	10	20
P3	25	15

Hãy dùng thuật giải Round Robin (RR) với thời lượng 10ms để đ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?[table border="1"]


a/ Biểu đồ gant:


b/ Thời gian chờ:
p1 = 73 - 3 - 35 = 35
p2 = 43 - 10 - 20 = 13
p3 = 68 - 25 - 15 = 28
Thời gian chờ trung bình = (Thời điểm kết thúc - Thời điểm đến - Thời gian dùng CPU) / Số tiến trình
= (35 + 13 + 28) / 3= 25,3333 ms

Các thuật giải căn bản trong điều phối CPU

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.

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.

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 )
Vấn đề Ach vô hạn định ( Starvation ) : Tiến trình với độ ưu tiên thấp có thể bị “Bỏ đói” và không bao giờ được thực hiện.
Giải pháp Tăng tuổi ( Aging ) – Tăng độ ưu tiên theo thời gian chờ đợi (Ví dụ: cứ 15 ‘ lại được tăng thêm 1 độ ).

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 milli 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.
Đánh giá:
q lớn ==> RRS = FCFS
q nhỏ ==> RRS được gọi là thuật giải Chia sẻ CPU.

tranvanthien27(I12C) đã viết:

lethanhsang_I12A đã viết:

Ti?n Trình	Th?i Ði?m Ð?n	Kho?ng CPU (ms)
P1	3	37
P2	10	20
P3	24	14

Dùng thuật toán RRS với thời lượng 10ms dùng CPU
a) Vẽ biểu đồ Gantt
b) Tính thời gian trung bình

Giải:

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
- Thời gian chờ của các tiến trình:
P1 = (74 – 3 – 37) = 34 ms
P2 = (43 – 10 – 20) = 13 ms
P3 = (67 – 24 – 14) = 29 ms
- Thời gian chờ trung bình = (34+13+29) / 3= 25,3 ms

Hình như bài của bạn chưa chính xác vì từ thời điểm 53 đến 63 là P1 chứ ko phải là P2

uhm, thank bạn lúc làm trên giấy vẽ vô máy lại sai. Mình xin sửa lại biểu đồ:

Biểu đồ Gantt - Gantt Diagram

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.
TIP Đố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.

Lưu ý: Nếu bạn có một dự án với một vài mục tiêu, biểu đồ Gantt có thể giúp bạn chỉ ra mối quan hệ giữa tiến độ và mục tiêu. Bạn có thể đặt mã mầu cho tiến độ thực hiện và sử dụng biểu đồ Gantt là cơ sở để cập nhật dự á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 (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.

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

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


Đ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

Thư viện Win32 API (Application Programming Inteface) là bộ thư viện MSDN lớn của Microsoft.
API có thể xem là ngôn ngữ giao tiếp giữa ứng dụng với hệ điều hành. Nhà lập trình viết các hàm gọi để “móc” với API, API “ra lệnh” cho máy tính làm việc. Có thể xem một API như một module của chương trình để chạy tác vụ nào đó.

Dưới đây là các hàm cơ bản:
- SetThreadPriority: Có chức năng thiết lập giá trị ưu tiên cho một luồng
- CreateThread: Tạo một luồng để thực thi trong địa chỉ lời gọi tiến trình
- ExitThread: Dùng để kêt thúc một luồng
- GetCurrentThread: Có chức năng trả về mục quản tạm cho luồng hiện tại
- TerminateThread:Có chức năng ngắt luồng

Admin
Chưa đủ !

Cho tập tập hợp các tiến trình sau:


Giải:

a/Round Robin



Thời gian chờ:
P1: 1 + 5 + 2 + 1 = 9
P2: 2 – 1 = 1
P3: 5 – 2.5 = 2.5
P4: 7 – 3 = 4
P5: 8 + 2 + 2 – 4.5 = 7.5
Thời gian chờ trung bình = 25/5 = 5

b/Thuật giải có tiếm quyền


Thời gian chờ:
P1: 0
P2: 10 – 9 = 1
P3: 16 – 2.5 = 13.5
P4: 18 – 3 = 5
P5: 11 – 4.5 = 6.5
Thời gian chờ trung bình = 44/5 = 8.8

c/Thuật giải không có tiếm quyền


Thời gian chờ:
P1: 1 + 7 = 8
P2: 0
P3: 9.5 – 2.5 = 7
P4: 18 – 3 = 15
P5: 0
Thời gian chờ trung bình = 25/5 = 5

Admin
Không hợp với đề thi !

tranvanthien27(I12C) đã viết:

lethanhsang_I12A đã viết:

Ti?n Trình	Th?i Ði?m Ð?n	Kho?ng CPU (ms)
P1	3	37
P2	10	20
P3	24	14

Dùng thuật toán RRS với thời lượng 10ms dùng CPU
a) Vẽ biểu đồ Gantt
b) Tính thời gian trung bình

Giải:

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
- Thời gian chờ của các tiến trình:
P1 = (74 – 3 – 37) = 34 ms
P2 = (43 – 10 – 20) = 13 ms
P3 = (67 – 24 – 14) = 29 ms
- Thời gian chờ trung bình = (34+13+29) / 3= 25,3 ms

Hình như bài của bạn chưa chính xác vì từ thời điểm 53 đến 63 là P1 chứ ko phải là P2

Theo mình nghĩ như thế này các bạn xem có đúng ko nha hi
|//|--P1--|--P2--|--P1--|--P2--|--P3--|--P1--|--P3--|--P1--|
0 3 -----13----- 23----33----43----- 53 --- 63------67----74


b/ Thời gian chờ của
P1= 74 - 3 - 37 = 34 ms
P2= 43 - 10 - 20 =13 ms
P3= 67 - 24 -14 =19 ms

Thời gian chờ trung bình = (34 + 13 + 19 )/3 =25.33 ms[/quote]

cám ơn các bạn đã up .minh đang tham khảo có gì xin chỉ giáo dùm

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.

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

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ố tiến trình (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.

Giống nhau: Cùng có nhiều hàng đợi Ready và có độ ưu tiên khác nhau,
Mỗi tiến trình đều có thuật giải riêng,
Khác nhau:
- MFQS thì linh động hơn MQS cho phép HĐH điều phối các tiến trình sang mức khác(cao hơn hoặc thấp hơn, từ ưu tiên sang hết ưu tiên). Trong khi, MQS thì chỉ phân cấp theo những độ ưu tiên nhất định rùi dựa theo đó mà thực hiện ko có sự thay đổi khi cần thiết,
- MQS có mức độ ưu tiên cố định, MFQS thì có thể thay đỗi mức độ ưu tiên,
- MFQS có hình thức chọn tiến trình nào cấp thiết cần được dùng CPU trước từ đó năng mức ưu tiên cho nó

Các hàm cơ bản trong thư viện Win32 API:
– CreateThread: Khởi tạo luồng
– SuspendThread: Tạm dừng/ngưng một luồng (tăng biến đếm số
lần suspend)
– ResumeThread: Tiếp tục một luồng bị tạm dừng (giảm biến đếm số
lần suspend).
– SetThreadPriority: Thiết lập mức độ ưu tiến của luồng (tương đối
so với mức độ ưu tiên của process) ( LOW, BELOW LOW or HIGH)
– GetThreadPriority: Lấy mức độ ưu tiên của luồng.
- GetCurrentThread: Có chức năng trả về mục quản tạm cho luồng hiện tại
- TerminateThread:Có chức năng ngắt luồng
- ExitThread: Dùng để kêt thúc một luồng

Admin
- Đầy đủ, nhưng cần cho biết các tham số tương ứng và ví dụ sử dụng cụ thể !
- Bài 7 sẽ giới thiệu thêm một số hàm đồng bộ hoá nữa.

lethanhsang_I12A đã viết:Các hàm cơ bản trong thư viện Win32 API:
– CreateThread: Khởi tạo luồng
– SuspendThread: Tạm dừng/ngưng một luồng (tăng biến đếm số
lần suspend)
– ResumeThread: Tiếp tục một luồng bị tạm dừng (giảm biến đếm số
lần suspend).
– SetThreadPriority: Thiết lập mức độ ưu tiến của luồng (tương đối
so với mức độ ưu tiên của process) ( LOW, BELOW LOW or HIGH)
– GetThreadPriority: Lấy mức độ ưu tiên của luồng.
- GetCurrentThread: Có chức năng trả về mục quản tạm cho luồng hiện tại
- TerminateThread:Có chức năng ngắt luồng
- ExitThread: Dùng để kêt thúc một luồng

Admin
- Đầy đủ, nhưng cần cho biết các tham số tương ứng và ví dụ sử dụng cụ thể !
- Bài 7 sẽ giới thiệu thêm một số hàm đồng bộ hoá nữa.

Em xin cảm ơn thầy đã cho ý kiến, em xin bổ sung thêm

• CreateThread: Khởi tạo luồng
  CreateThread(
  lpThreadAttributes, //thuộc tính của luồng.
  dwStackSize, //kích cỡ của stack
  lpStartAddress,// địa chỉ bắt đầu.
  lpParameter, //tham số
  dwCreationFlags, //cờ hiệu tạo thành (điều khiển sự tạo thành của luồng)
  lpThreadId //chỉ số của luồng
  );
  vd: ProducerHandle1=CreateThread(0, 0, (LPTHREAD_START_ROUTINE)Producer,
  0, 4, &ProducerID1);

• SetThreadPriority: Thiết lập mức độ ưu tiến của luồng (tương đối so với mức độ ưu tiên của process) ( LOW, BELOW LOW or HIGH)
  SetThreadPriority(
  hThread,// mục quản của luồng
  nPriority // giá trị ưu tiên
  );
  VD: SetThreadPriority(GetCurrentThread(), THREAD_MODE_BACKGROUND_BEGIN)
  

• GetThreadPriority: Lấy mức độ ưu tiên của luồng.
  GetThreadPriority(
  hThread // mục quản của luồng
  );
  vd: GetThreadPriority(GetCurrentThread());

• SuspendThread: Tạm dừng/ngưng một luồng (tăng biến đếm số
  lần suspend)
  SuspendThread(
  HANDLE hThread // mục quản luồng cần tạm ngưng
  );
  vd: SuspendThread(GetCurrentThread());
  Hàm GetCurrentThread() dùng để lấy Mục Quản của luồng hiện hành.
  Hàm SuspendThread(n) dùng để tạm dừng công việc của luồng có Mục Quản mà hàm GetCurrentThread() đã lấy .

• ResumeThread: Tiếp tục một luồng bị tạm dừng (giảm biến đếm số
  lần suspend).
  ResumeThread(
  HANDLE hThread // mục quản luồng cần tiếp tục lại
  );
  vd:ResumeThread(ProducerHandle1)

• TerminateThread:Có chức năng ngắt luồng
  TerminateThread(
  HANDLE hThread, // luồng cần ngắt
  DWORD dwExitCode // mã ngắt của luồng
  );
  vd: TerminateThread (hThread, 0);
  

• Hàm CloseHandle(n) dùng để đóng luồng có Mục Quản là n lại.
  vd: CloseHandle(ProducerHandle1);

• Sleep: đình chỉ thời gian thực thi luồng trong khoảng thời gian quy định
  Sleep(
  dwMilliseconds // thời gian luồng ngủ (tính bằng ms)
  );
  vd:Sleep(2000);
  

• ExitThread: Dùng để kêt thúc một luồng
  ExitThread(
  dwExitCode // mã kết thúc luồng, dùng hàm GetExitCodeThread(hThread,lpExitCode// biến 32bit) để lấy
  );
  vd: ExitThread(GetExitCodeThread(GetCurrentThread(), 0))

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.

4 tình huống ra quyết định
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. 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 được trong cả 4 tình huống