Thảo luận Bài 6

Trang 3 trong tổng số 10 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Re: Thảo luận Bài 6

Bài gửi  HuynhMinhChanh(i91C) on 4/4/2012, 22:33

Henry Gantt



Tiểu sử
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.

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 Laurence Gantt đã làm việc như một nhà tư vấn quản lý cũng như nền một trong các kỹ sư cơ khí do thương mại.. Henry Gantt được biết đến, đã xem ông tự đặt tên một cách dễ dàng, tạo lập kế hoạch và theo dõi biểu đồ One creates Gantt Charts to reveal planned and actual project progress. Một tạo ra Gantt Charts để lộ thực tế tiến độ dự án và kế hoạch ngày. quản lý dự án thường được chấp nhận một công cụ này, nó là một sự đổi mới của toàn thế giới vào năm 1920 có ý nghĩa, được thành lập vào Gantt công việc của ông trong khi đóng tàu trong suốt Thế chiến thứ nhất lịch sử thay đổi. mãi mãi, Gantt bảng xếp hạng có sau đó được sử dụng để tiến độ và giám sát dự án xây dựng lớn như đập Hoover bắt đầu vào năm 1931 và các mạng lưới đường cao tốc Eisenhower đưa ra vào năm 1956.
Đóng góp
Trong sự nghiệp của mình như là một nhà tư vấn quản lý, ngoài các biểu đồ Gantt, ông tiếp tục làm nên lịch sử quản lý khoa học của đặt ra "của các nhiệm vụ và hệ thống tiền thưởng. Lý thuyết đằng sau" của công việc và tiền thưởng phương thức thanh toán tiền lương (1901) là nó sẽ tạo ra hiệu quả lao động cao hơn và năng suất bằng cách khen thưởng cho các nhiệm vụ giám sát thông qua biểu đồ Gantt. Trực tiếp chống lại hệ thống phần trả công việc của Taylor, cũng bị xử phạt thực hiện không tốt, Henry Gantt của phương pháp cho phép người lao động để kiếm được mức lương của họ với một tiền thưởng thêm cho việc hoàn thành của họ mục tiêu năng suất. Điều này cho phép người lao động để duy trì một mức lương ổn định trong khi họ đang học tập công việc, và khen thưởng cho họ để tận dụng trình độ này bổ sung.

Nói tóm lại 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.

Trích trong http://vi.wikipedia.org/wiki/Henry_Laurence_Gantt


Được sửa bởi HuynhMinhChanh(i91C) ngày 4/4/2012, 22:36; sửa lần 1.

HuynhMinhChanh(i91C)

Tổng số bài gửi : 47
Join date : 02/03/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập thuật giải round robin

Bài gửi  PhamQuangHien_I12A on 4/4/2012, 22:35

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

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a>thể hiện bằng biểu đồ gant?
b>tính thời gian chờ Tb của các tiến trình?
Giải:
A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuỷên qua tiến trình khác.ở đây là các tiến trình p1,p2,p3

Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)
4. Thời điểm 33: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 )
5. Thời điểm 43: P3 được chạy trước P1 (vì P3 đang chờ trước ở thời điểm 25 còn P1 là 33 )(P2 hết)
6. Thời điểm 53: P1 được tiếm quyền P3 (vì P1 đang chờ ở thời điểm 33 )
6. Thời điểm 63: P3 được tiếm quyền P1 (vì P3 đang chờ ở thời điểm 53 và chạy hết 5s(68s kết thúc))
7. Cuối cùng chỉ còn P1 sẽ chạy hết thời gian còn lại(5s nữa và kết thúc tại 73s).

B/ thời gian chờ trung bình của các tiến trìn[/b]h:
[/u]Theo như công thức:

T(i)=( thờiđiểm kết thúc - thời điểm đến )- t/g dùng CPU

Thời gian chờ của P1 = 73-3-35=35 -> T1
Thời gian chờ của P2 = 43-10-20=13 -> T2
Thời gian chờ của P3 = 68-25-15=28 -> T3

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (35+13+28)/3=76/3=25.33 (ms)


PhamQuangHien_I12A

Tổng số bài gửi : 62
Join date : 22/02/2012
Age : 28
Đến từ : Quãng Ngãi

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  PhamQuangHien_I12A on 4/4/2012, 22:42

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.

PhamQuangHien_I12A

Tổng số bài gửi : 62
Join date : 22/02/2012
Age : 28
Đến từ : Quãng Ngãi

Xem lý lịch thành viên

Về Đầu Trang Go down

Phân biệt 2 giải thuật MQS và MFQS. Cho ví dụ minh họa.

Bài gửi  NguyenHoangThangI12A on 4/4/2012, 22:42

Giống nhau: 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 toán 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é máy bay 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,...
avatar
NguyenHoangThangI12A

Tổng số bài gửi : 34
Join date : 15/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Câu 1: Trình bày giải thuật điều phối ngắn hơn chạy trước (SJFS) (có tiếm quyền)

Bài gửi  NguyenHoangThangI12A on 4/4/2012, 22:48

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).
avatar
NguyenHoangThangI12A

Tổng số bài gửi : 34
Join date : 15/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Câu 2: Giai bài tập bằng thuật giải (Round Robin Scheduling-RRS)

Bài gửi  BuiPhamAnBinh(I12A) on 4/4/2012, 22:48

Tiến trình ++++++ thời điểm đến (ms) ++ CPU-Bust

p1 ............ ........... 5 .............. ............. .. 25

p2 ........... ............ 10 ........... ............ ... 15

p3 ............. ........... 20 .......... ............ ... 10
.

biểu đồ Gantt


RRS với thời lượng = 10 ms

p1((55-5)-25)=25ms
p2((50-10)-15)=25ms
p3((45-20)-10)=15ms
Thời gian chờ TB
(25+25+15)/3 =21.7(ms)


các bạn có phần giải thích nào dể hiểu có thể bổ xung thêm cho bài tập này .thank Very Happy


Được sửa bởi BuiPhamAnBinh(I12A) ngày 4/4/2012, 23:33; sửa lần 2.

BuiPhamAnBinh(I12A)

Tổng số bài gửi : 20
Join date : 16/02/2012
Age : 28

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  letanthanh18(I12A) on 4/4/2012, 22:58

hoanghaiyen đã viết:Chào bạn LePhucHiep(102C) bạn ví dụ bài tập và bài giải khá công phu nhưng bạn có thể giải thích rõ hơn được không ,bài giải chưa cụ thể lắm, cám ơn
Chúc bạn học tốt môn hệ điều hành của thầy
Mình mạn phép xin giải thích giúp bạn LePhucHiep
*Biểu đồ Gantt ( bạn Hiệp đã vẽ )
*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=( 5 - 0 )- 5 = 0
P2=( 7 - 1 ) - 2 = 4
P3=( 9 - 2 ) - 2 = 5
_Thời gian chờ trung bình = ( 0 + 4 + 5 ) / 3 =3 ms


letanthanh18(I12A)

Tổng số bài gửi : 14
Join date : 22/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  HuynhMinhChanh(i91C) on 4/4/2012, 23:04

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

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a>thể hiện bằng biểu đồ gant?
b>tính thời gian chờ Tb của các tiến trình?
Giải:
A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuỷên qua tiến trình khác.ở đây là các tiến trình p1,p2,p3

Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)
4. Thời điểm 33: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 )
5. Thời điểm 43: P3 được chạy trước P1 (vì P3 đang chờ trước ở thời điểm 25 còn P1 là 33 )(P2 hết)
6. Thời điểm 53: P1 được tiếm quyền P3 (vì P1 đang chờ ở thời điểm 33 )
6. Thời điểm 63: P3 được tiếm quyền P1 (vì P3 đang chờ ở thời điểm 53 và chạy hết 5s(68s kết thúc))
7. Cuối cùng chỉ còn P1 sẽ chạy hết thời gian còn lại(5s nữa và kết thúc tại 73s).

B/ thời gian chờ trung bình của các tiến trìn[/b]h:
[/u]Theo như công thức:

T(i)=( thờiđiểm kết thúc - thời điểm đến )- t/g dùng CPU

Thời gian chờ của P1 = 73-3-35=35 -> T1
Thời gian chờ của P2 = 43-10-20=13 -> T2
Thời gian chờ của P3 = 68-25-15=28 -> T3

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (35+13+28)/3=76/3=25.33 (ms)


Cảm ơn bạn về bài viết rất chi tiết. Bạn có thể giải thêm 1 bài tập về thuật toán SJFS để cả lớp cùng tham khảo không ?

HuynhMinhChanh(i91C)

Tổng số bài gửi : 47
Join date : 02/03/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Tiểu sử về Henry Laurence Gantt

Bài gửi  NguyenNgocDuy(I12A) on 4/4/2012, 23:05


Henry Gantt


Tiểu sử
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.

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 Laurence Gantt đã làm việc như một nhà tư vấn quản lý cũng như nền một trong các kỹ sư cơ khí do thương mại.. Henry Gantt được biết đến, đã xem ông tự đặt tên một cách dễ dàng, tạo lập kế hoạch và theo dõi biểu đồ One creates Gantt Charts to reveal planned and actual project progress. Một tạo ra Gantt Charts để lộ thực tế tiến độ dự án và kế hoạch ngày. quản lý dự án thường được chấp nhận một công cụ này, nó là một sự đổi mới của toàn thế giới vào năm 1920 có ý nghĩa, được thành lập vào Gantt công việc của ông trong khi đóng tàu trong suốt Thế chiến thứ nhất lịch sử thay đổi. mãi mãi, Gantt bảng xếp hạng có sau đó được sử dụng để tiến độ và giám sát dự án xây dựng lớn như đập Hoover bắt đầu vào năm 1931 và các mạng lưới đường cao tốc Eisenhower đưa ra vào năm 1956.
Đóng góp
Trong sự nghiệp của mình như là một nhà tư vấn quản lý, ngoài các biểu đồ Gantt, ông tiếp tục làm nên lịch sử quản lý khoa học của đặt ra "của các nhiệm vụ và hệ thống tiền thưởng. Lý thuyết đằng sau" của công việc và tiền thưởng phương thức thanh toán tiền lương (1901) là nó sẽ tạo ra hiệu quả lao động cao hơn và năng suất bằng cách khen thưởng cho các nhiệm vụ giám sát thông qua biểu đồ Gantt. Trực tiếp chống lại hệ thống phần trả công việc của Taylor, cũng bị xử phạt thực hiện không tốt, Henry Gantt của phương pháp cho phép người lao động để kiếm được mức lương của họ với một tiền thưởng thêm cho việc hoàn thành của họ mục tiêu năng suất. Điều này cho phép người lao động để duy trì một mức lương ổn định trong khi họ đang học tập công việc, và khen thưởng cho họ để tận dụng trình độ này bổ sung.

Nói tóm lại 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.
avatar
NguyenNgocDuy(I12A)

Tổng số bài gửi : 17
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

PHÂN BIỆT HAI GIẢI THUẬT MQS VÀ MFQS - CHO VÍ DỤ

Bài gửi  huynhvanhung(I12A) on 4/4/2012, 23:07

GIỐNG NHAU : thuật giải MQS (Multilevel Queue Scheduling) điều phối hàng chờ nhiều mức - MFQS (Multilevel Feedback Queue Scheduling) điều phối hàng chờ nhiều mức có điều tiến , 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) SJFS .
KHÁC NHAU : MFQS 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 so với MQS.


Multilevel Queue Scheduling - MQS

việc phục vụ thực khách trong nhà hàng

Thực khách sẽ đến và gọi món ăn , nước uống ....
Mỗi một thức ăn nước uống đều có thời gian chuẩn bị khác nhau.
Thời gian trung bình đợi của thực khách là khác nhau
Nếu trường hợp khách hàng quen thân và có đặt bàn trước thì 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ì nhà hàng sẽ phục vụ theo kiểu FJFS , đến trước thì phục vụ trước.


Multilevel Feedback Queue Scheduling - MFQS

Phòng bán vé tàu hỏa có thể có nhiều cửa bán vé với mức độ ưu tiên khác nhau , trong khi chỉ có một người là bán vé (1 CPU) phải luân phiên qua lại giữa các cửa để phục vụ cho đủ loại thành phần mua vé (các tiến trình ) như : người mua bình thường, là thương binh, công nhân , sinh viên ....



MONG CÁC BẠN ĐÓNG GÓP THÊM .... Very Happy Very Happy Very Happy
avatar
huynhvanhung(I12A)

Tổng số bài gửi : 43
Join date : 17/02/2012
Age : 29
Đến từ : TP.HCM

Xem lý lịch thành viên

Về Đầu Trang Go down

Giải đề thi năm ngoái (Giải thuật Round Robin)

Bài gửi  quicly_I111c on 4/4/2012, 23:11

a/ Biểu đồ Gannt
|//|--P1--|--P2--|--P1--|--P3--|--P2--|--P1--|
0 5 -----15----- 25----35----45----- 50 --- 55


b/ Thời gian chờ của
P1= 55 - 25 - 5 = 25
P2= 50 - 15 - 10 =25
P3= 45-20-10=15

Thời gian chờ trung bình = (25 + 25+ 5)/3 = 21.6 ms

quicly_I111c

Tổng số bài gửi : 20
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Giải thích về cách vẽ biểu đồ Gantt, sử dụng thuật giải Round Robin Scheduling

Bài gửi  maidangvu_I12A on 4/4/2012, 23:15

Giả sử trong hàng chờ Ready có 3 tiến trình:









Mong các bạn và thầy góp ý!!!

maidangvu_I12A

Tổng số bài gửi : 28
Join date : 28/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  TranThaoUyen127(I92C) on 4/4/2012, 23:22

TranThiNgocQuynh(I12C) đã viết:Giống nhau:
Thuật giải điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling) và thuật giải điều phối hàng chờ nhiều mức có điều tiết (Multilevel Feedback Queue Scheduling) cùng sử dụng nhiều hàng chờ có độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng cách điều phối khác nhau như điều phối theo vòng Robin (Round Robin Scheduling) hay First Come First Served (FCFS)

Khác nhau:

Thuật giải điều phối hàng chờ nhiếu mức có điều tiết (MFQS) có tính mềm dẻo, uyển chuyển hơn, cho phép điều phối tiến trình từ hàng chờ này sang hàng chờ khác (hạ mức độ ưu tiên xuống)

Ví dụ minh họa:
Phòng bán vé tàu hỏa ở ga Hòa Hưng có nhiều cửa bán vé với mức độ ưu tiên khác nhau, có cửa dành cho những người trong hệ thống (công nhân viên phục vụ trong ga), có cửa dành riêng cho thương binh, người tàn tật...Chỉ có 1 cô bán ve (CPU) phải liên tục di chuyển giữa các cửa để phục vụ cho khách mua vé.
Với trường hợp MQS thì khách mua vé thuộc loại nào thì đứng yên ở cứa đó chờ tới lượt để được mua vé.
Với trường hợp MFQS thì người sếp hàng mua vé có thể được chuyển sang cửa khác mua vé (nếu cửa đang đứng quá đông), để đảm bảo chất lượng phục vụ là tốt nhất.
cho mình bổ sung thêm điểm khác nhau giữa MQS và MFQS:
- MQS thì tiến trình được xếp ở mức nào thì ở nguyên mức đó không được chuyển sang mức khác -> cố định không uyển chuyển.

TranThaoUyen127(I92C)

Tổng số bài gửi : 22
Join date : 28/10/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  NgoPhuQuoc_I12C on 4/4/2012, 23:27

Đề Bài: 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 Thời gian sử dụng CPU(CPU-Burst)
P1 525
P2 1015
P3 20 10

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

Trả lời:
A/ biểu đồ Gantt:


Nếu không thấy rõ hình thì xem Link này:
CLICK

Giải thích biểu đồ Gantt:
- T từ 0->5 chưa có tiến trình nào đến
- T=5 có P1 đến sử dụng 10ms, thời gian chiếm CPU còn lại là 15 ms.
- T=15 thì có P2 đến. Vì thời gian sử dụng CPU(CPU-Burst) của P2 là 15, sử dụng được 10ms còn lại là 5 ms.

- T=25, P3 đến, nhưng CPU-Burst của P1 cao hơn nên P1 được ưu tiên. CPU-Burst của P1 còn 5 ms.

-T=35, lúc này P3 có CPU-Burst cao nhất(10 ms) nên P3 được ưu tiên.
*vì tiến trình hiện hành bị tiếm quyền sẽ được đưa về sau cùng nên P1 ở sau cùng, kế đó là P2. Vì vậy:
-T=45, P2 được quyền sử dụng CPU.
-T=50, P1 được quyền sử dụng CPU.


B/ Thời gian chờ trung bình của các tiến trình:
công thức:
T(i)=( thời điểm kết thúc - thời điểm đến ) - thời gian dùng CPU

Thời gian chờ của P1 = (55-5) -25=25
Thời gian chờ của P2 = (50-10) -15 =25
Thời gian chờ của P3 = (45-20) -10=15

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (25+25+15)/3=21.6 ms

Admin
Dựa vào tiêu chí CPU-Burst cao là không phù hợp với RRS !


NgoPhuQuoc_I12C

Tổng số bài gửi : 13
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

So sánh MQS (Multilevel Queue Scheduling) và MFQS (Multilevel Feedback Queue Scheduling)

Bài gửi  DoanNgocDan(I12A) on 4/4/2012, 23:32

-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ụ.
avatar
DoanNgocDan(I12A)

Tổng số bài gửi : 33
Join date : 17/02/2012
Age : 29
Đến từ : DakLak

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  TranThiNgocQuynh(I12C) on 4/4/2012, 23:36

HuynhMinhChanh(i91C) đã viết:Em chào thầy,mong thầy giải đáp giúp em :

Đề thi thầy cho như sau : Sử dụng Thuật Toán Round Robin với thời lượng 10ms để điều phối CPU
Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 5 25
P2 10 15
P3 20 10

Sơ đồ Gantt bài giải :





Em có một số lý luận như sau :
- Về bài giảng trên lớp : Thầy giảng thì Round Robin điều phối CPU dựa theo nguyên lý xoay vòng, khi 1 tiến trình bị tiếm quyền, thì nó sẽ được đưa vào cuối của hàng queue . Mà cơ chế của Queue là FIFO (First In First Out).
=> P1 sau khi thực hiện xong quantum đầu tiên thì sẽ chuyển xuống cuối hàng đợi (sau P3).
- Tiếp theo P2 thực hiện xong phần quantum (10ms) đầu tiên và sẽ chuyển xuống hàng đợi (sau P1 ở trên).
- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.
Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Nếu theo lý luận của em, thì em đã làm khác so với bài giải của thầy, em nghĩ e có chỗ nào đó bị sai, mong thầy và các bạn giải đáp thắc mắc trên của em, và cho em biết lỗi sai của em nằm ở đâu, để em có thể hoàn thiện kiến thức hơn.

Cảm ơn thầy về bài giảng hôm nay.


Mình giải thích theo cách của mình hiểu, bạn xem qua rồi bổ sung thêm nhé.

Do thời điểm đến của P1 là 5ms nên P1 sẽ được cấp CPU đầu tiên với thời lượng cấp CPU là 10ms. Trong khi CPU đang được cấp cho P1 thì tiến trình P2 đến ở thời điểm 10ms nên được đưa vào hàng chờ Ready. Sau thời lượng CPU 10ms thì P1 bị tiếm quyền CPU (bị tiếm quyền tại thời điểm 15ms) và được đưa vào cuối hàng chờ Ready. Lúc này trong hàng chờ Ready có các tiến trình P1, P2 (thứ tự từ cuối hàng chờ lên đầu hàng chờ) .
- Tại thời điểm 15ms CPU sẽ chọn tiến trình P2 để cấp tiếp CPU, trong khi P2 đang được cấp CPU thì tại thời điểm 20ms tiến trình P3 xuất hiện và được đưa vào hàng chờ Ready (trong hàng chờ Ready lúc này gồm các tiến trình P3, P1).
- Tại thời điểm 25ms tiến trình P2 bị tiếm quyền và được đưa vào cuối hàng chờ Ready (P2, P3, P1), tiến trình P1 trong hàng chờ Ready được cấp CPU.
- Tại thời điểm 35ms tiến trình P1 bị tiếm quyền và được đưa vào cuối hàng chờ Ready (P1, P2, P3), tiến trình P3 trong hàng chờ Ready được cấp CPU.
- Tại thời điểm 45ms, tiến trình P3 hoàn tất xong công việc. Trong hàng chờ Ready còn các tiến trình (P1, P2), HĐH chọn tiến trình P2 để cấp CPU.
- Tai thời điểm 50ms tiến trình P2 đã hoàn tất xong công việc nên trả CPU cho hệ điều hành, HĐH chọn tiến trình P1 trong hàng chờ Ready để cấp CPU.
- Tại thời điểm 55ms tiến trình P1 cũng hoàn tất xong công việc.

b) 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 = (55 - 5) - 25 = 25ms
P2 = (50 - 10) - 15 = 25ms
P3 = (45-20) - 10 = 15ms
+ Thời gian chờ trung bình: (25 + 25 + 15)/3 = 21.6ms

Admin
- Giải thích đúng !
- Tuy nhiên, mấy chỗ tô đỏ ở trên chưa hay: Nên xếp ngược lại từ trái sang phải và xét lấy tiến trình đầu tiên trong danh sách !


TranThiNgocQuynh(I12C)

Tổng số bài gửi : 14
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  DoanNgocDan(I12A) on 4/4/2012, 23:42

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.
avatar
DoanNgocDan(I12A)

Tổng số bài gửi : 33
Join date : 17/02/2012
Age : 29
Đến từ : DakLak

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  TranThaoUyen127(I92C) on 4/4/2012, 23:43

HuynhMinhChanh(i91C) đã viết:Em chào thầy,mong thầy giải đáp giúp em :

Đề thi thầy cho như sau : Sử dụng Thuật Toán Round Robin với thời lượng 10ms để điều phối CPU
Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 5 25
P2 10 15
P3 20 10

Sơ đồ Gantt bài giải :





Em có một số lý luận như sau :
- Về bài giảng trên lớp : Thầy giảng thì Round Robin điều phối CPU dựa theo nguyên lý xoay vòng, khi 1 tiến trình bị tiếm quyền, thì nó sẽ được đưa vào cuối của hàng queue . Mà cơ chế của Queue là FIFO (First In First Out).
=> P1 sau khi thực hiện xong quantum đầu tiên thì sẽ chuyển xuống cuối hàng đợi (sau P3).
- Tiếp theo P2 thực hiện xong phần quantum (10ms) đầu tiên và sẽ chuyển xuống hàng đợi (sau P1 ở trên).
- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.
Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Nếu theo lý luận của em, thì em đã làm khác so với bài giải của thầy, em nghĩ e có chỗ nào đó bị sai, mong thầy và các bạn giải đáp thắc mắc trên của em, và cho em biết lỗi sai của em nằm ở đâu, để em có thể hoàn thiện kiến thức hơn.

Cảm ơn thầy về bài giảng hôm nay.




Em cũng cùng suy nghĩ với bạn. Xin thầy giải đáp cho chúng em rõ hơn!

TranThaoUyen127(I92C)

Tổng số bài gửi : 22
Join date : 28/10/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Phân biệt điều phối có tiếm quyền và không tiến quyền.

Bài gửi  quicly_I111c on 4/4/2012, 23:45

 CPU bắt được tiến trình đang chiếm CPU (ở Win 3.1x) thời đó CPU chưa có timer cứng. (không tiếm quyền). Do đó, HĐH không bắt được chương trình trả lại CPU.
VD: Ở Ga Hòa Hưng, quầy bán vé. Có 2 người mua.
Người 1: Mua 3 vé
Người 2: Mua 1 vé
Người 1 sẽ mua hết số vé cần mua mà không phải nhường hoặc chờ (không tiếm quyền) được mua đến cùng, tương tự cho đến người thứ 2.
 Các CPU hiện đại thì bắt được (tiếm quyền).
VD: Ở Ga Hòa Hưng, có 3 người mua vé lần lượt theo thứ tự 1,2,3. Người số 1 đến trước.
Người 1: Mua 3 vé
Người 2: Mua 1 vé
Người thứ nhất mua được 1 vé, sau đó người 2 mua 1 vé, trong lúc đó người số 1 đi uống café chờ mua số vé còn lại (bị tiếm quyền). Sau khi người 1 mua xong, người 2 quay lại quầy và được mua mua hết 2 vé còn lại.

quicly_I111c

Tổng số bài gửi : 20
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập về tạo, đánh thức và tạm ngừng luồng

Bài gửi  letanthanh18(I12A) on 4/4/2012, 23:51

// 1.Tập luồng gồm 30 luồng sản xuất và 30 luồng tiêu thụ
HANDLE ProducerHandle[30] ; // Dùng chứa Mục quản của các luồng được tạo mới
HANDLE ConsumerHandle[30] ;
DWORD ProducerID[30]; // Dùng chứa ID của các luồng được tạo mới
DWORD ConsumerID[30];
for ( int i = 0 ; i < 30 ; i ++)
{
ProducerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Producer, 0, 4, &ProducerID[i]);
ConsumerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Consumer, 0, 4, &ConsumerID[30]);
}
// 2. Đánh thức các luồng
for ( int i = 0 ; i < 30 ; i ++)
{
ResumeThread ( ProducerHandle[ i ] );
ResumeThread ( ConsumerHandle[ i ] );
}
// 3. Tạm ngừng
for ( int i = 0 ; i < 30 ; i ++)
{
SuspendThread ( ProducerHandle[ i ] );
SuspendThread ( ConsumerHandle[ i ] );
}

Admin
- Đã sửa lại lời giải trên cho đúng hơn.
- Với CreateThread, không cần chi tiết như:
ProducerHandle[i]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Producer, 0, 4, &ProducerID[i])
mà chỉ yêu cầu đơn giản thôi:
ProducerHandle[i]=CreateThread(Producer, 4, &ProducerID[i])





letanthanh18(I12A)

Tổng số bài gửi : 14
Join date : 22/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  tranvanthien27(I12C) on 4/4/2012, 23:56

NgoPhuQuoc_I12C đã viết:Đề Bài: 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 Thời gian sử dụng CPU(CPU-Burst)
P1 525
P2 1015
P3 20 10

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

Trả lời:
A/ biểu đồ Gantt:


Nếu không thấy rõ hình thì xem Link này:
CLICK

Giải thích biểu đồ Gantt:
- T từ 0->5 chưa có tiến trình nào đến
- T=5 có P1 đến sử dụng 10ms, thời gian chiếm CPU còn lại là 15 ms.
- T=15 thì có P2 đến. Vì thời gian sử dụng CPU(CPU-Burst) của P2 là 15, sử dụng được 10ms còn lại là 5 ms.

- T=25, P3 đến, nhưng CPU-Burst của P1 cao hơn nên P1 được ưu tiên. CPU-Burst của P1 còn 5 ms.

-T=35, lúc này P3 có CPU-Burst cao nhất(10 ms) nên P3 được ưu tiên.
*vì tiến trình hiện hành bị tiếm quyền sẽ được đưa về sau cùng nên P1 ở sau cùng, kế đó là P2. Vì vậy:
-T=45, P2 được quyền sử dụng CPU.
-T=50, P1 được quyền sử dụng CPU.


B/ Thời gian chờ trung bình của các tiến trình:
công thức:
T(i)=( thời điểm kết thúc - thời điểm đến ) - thời gian dùng CPU

Thời gian chờ của P1 = (55-5) -25=25
Thời gian chờ của P2 = (50-10) -15 =25
Thời gian chờ của P3 = (45-20) -10=15

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (25+25+15)/3=21.6 ms


Em có cách giải khác. Mong Thầy và các bạn xem có đúng ko. Cảm ơn Thầy và các bạn nhiều
A/ biểu đồ Gantt:



B/ Thời gian chờ trung bình của các tiến trình:
công thức:
T(i)=( thời điểm kết thúc - thời điểm đến ) - thời gian dùng CPU

Thời gian chờ của P1 = (55-5) -25=25
Thời gian chờ của P2 = (50-10) -15 =25
Thời gian chờ của P3 = (35-20) -10=5

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (25+25+0)/3=18.3 ms

Admin
Sai ! Xem giải thích trong 1 bài trước !



Được sửa bởi tranvanthien27(I12C) ngày 5/4/2012, 09:35; sửa lần 4.

tranvanthien27(I12C)

Tổng số bài gửi : 62
Join date : 15/02/2012
Age : 27
Đến từ : Tuy Hòa - Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  tranvanthien27(I12C) on 5/4/2012, 00:03

HuynhMinhChanh(i91C) đã viết:Em chào thầy,mong thầy giải đáp giúp em :

Đề thi thầy cho như sau : Sử dụng Thuật Toán Round Robin với thời lượng 10ms để điều phối CPU
Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 5 25
P2 10 15
P3 20 10

Sơ đồ Gantt bài giải :





Em có một số lý luận như sau :
- Về bài giảng trên lớp : Thầy giảng thì Round Robin điều phối CPU dựa theo nguyên lý xoay vòng, khi 1 tiến trình bị tiếm quyền, thì nó sẽ được đưa vào cuối của hàng queue . Mà cơ chế của Queue là FIFO (First In First Out).
=> P1 sau khi thực hiện xong quantum đầu tiên thì sẽ chuyển xuống cuối hàng đợi (sau P3).
- Tiếp theo P2 thực hiện xong phần quantum (10ms) đầu tiên và sẽ chuyển xuống hàng đợi (sau P1 ở trên).
- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.
Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Nếu theo lý luận của em, thì em đã làm khác so với bài giải của thầy, em nghĩ e có chỗ nào đó bị sai, mong thầy và các bạn giải đáp thắc mắc trên của em, và cho em biết lỗi sai của em nằm ở đâu, để em có thể hoàn thiện kiến thức hơn.

Cảm ơn thầy về bài giảng hôm nay.


Mình xin vẽ lại sơ đồ Gantt theo ý của bạn. Mong thầy và các bạn xem có đúng không



tranvanthien27(I12C)

Tổng số bài gửi : 62
Join date : 15/02/2012
Age : 27
Đến từ : Tuy Hòa - Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập chia luồng bằng thuật giải SJFS

Bài gửi  ĐoànMinhQuangI12A on 5/4/2012, 00:09

Bài tập chia luồng bằng thuật giải SJFS
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 đếnCPU-Burst
P1 5 22
P2 10 15
P3 20 5
Dùng thuật giải SJFS có tiếm quyền điều phối CPU

a/ Biểu đồ Gantt


- P1: thời điểm đến 5ms, CPU-burst 22ms.
o Sử dụng CPU đến mili giây thứ 10(thời điểm đến P2) bị tiếm quyền do CPU-burst P1 còn lại > CPU-burst P2 (22-5>15). P1 được đưa vào hàng chờ.
- P2: thời điểm đến 10ms, CPU-burst 15ms.
o Sử dụng CPU đến mili giây thứ 20(thời điểm đến P3) do CPU-burst P2 còn lại = CPU-burst P3(5=5). Áp dụng thuật giải FCFS chọn P2 tiếp tục sử dụng CPU.
- P3: thời điểm 25ms, CPU-burst 5ms sử dụng CPU đến kết thúc P3.
- P1: thời điểm 30ms, CPU-burst còn lại 17ms sử dụng CPU đến khi kết thúc P1.
b/ Thời gian chờ trung bình
- P1 = 47 – 5 – 22 = 20
- P2 = 25 – 10 – 15 = 5
- P3 = 30 – 25 – 5 = 0
Thời gian trung bình (P1 + P2 + P3)/3 = (20 + 5 + 0)/3= 8.3ms

ĐoànMinhQuangI12A

Tổng số bài gửi : 31
Join date : 15/02/2012
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

So Sánh MQS với MFQS

Bài gửi  tranvanthien27(I12C) on 5/4/2012, 00:13

- Giống nhau: Thuật giải MQS (Điều phối hàng chờ nhiều mức) và MFQS (Đ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ụ MFQS dùng thuật giải Round-Robin (RRS) hoặc MQS dùng thuật giải FCFS.

- Khác nhau: MFQS 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 MQS.

Ví dụ minh họa:
Phòng bán vé tàu hỏa ở ga Hòa Hưng có nhiều cửa bán vé với mức độ ưu tiên khác nhau, có cửa dành cho những người trong hệ thống (công nhân viên phục vụ trong ga), có cửa dành riêng cho thương binh, người tàn tật...Chỉ có 1 cô bán vé (CPU) phải liên tục di chuyển giữa các cửa để phục vụ cho khách mua vé.
Với trường hợp MQS thì khách mua vé thuộc loại nào thì đứng yên ở cứa đó chờ tới lượt để được mua vé.
Với trường hợp MFQS thì người xếp hàng mua vé có thể được chuyển sang cửa khác mua vé (nếu cửa đang đứng quá đông), để đảm bảo chất lượng phục vụ là tốt nhất.


Được sửa bởi tranvanthien27(I12C) ngày 5/4/2012, 10:15; sửa lần 2.

tranvanthien27(I12C)

Tổng số bài gửi : 62
Join date : 15/02/2012
Age : 27
Đến từ : Tuy Hòa - Phú Yên

Xem lý lịch thành viên

Về Đầu Trang Go down

Bổ sung: Phân biệt thuật giải MQS với thuật giải MFQS

Bài gửi  quicly_I111c on 5/4/2012, 00:16

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

quicly_I111c

Tổng số bài gửi : 20
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 6

Bài gửi  Sponsored content


Sponsored content


Về Đầu Trang Go down

Trang 3 trong tổng số 10 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9, 10  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết