Thảo luận Bài 6

Trang 8 trong tổng số 11 trang Previous  1, 2, 3 ... 7, 8, 9, 10, 11  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  NguyenCaoTri (I22B) on 30/3/2013, 13:48

NguyenHoangKimVu (I11C) đã viết:
...
P5 chạy tới ms thứ 11 là hết CPU Burst rồi bạn (vì CPU Burst = 5). P1 sẽ chạy tiếp từ ms thứ 11 đến 20.
Biểu đồ lúc đó sẽ thế này.

Thời gian chờ của từng tiến trình thì mình tính như vầy
Thời gian chờ = Thời điểm kết thúc - Thời điểm bắt đầu - CPU Burst
T1 = 20 - 1 - 10 = 9
T2 = 3 - 2 - 1 = 0
T3 = 6 - 3 - 2 = 1
T4 = 5 - 4 - 1 = 0
T5 = 11 - 6 -5 = 1
=> Ttb = (9 + 0 + 1 + 0 + 1)/5 = 2,2 ms

Thanks bạn NguyenHoangKimVu đã chỉ cho mình chỗ bị sai. Có 01 bài khác mình không biết giải.
Mình đã up lên theo link bên dưới.

http://hedieuhanh.forumvi.net/t5362p165-topic#26301



NguyenCaoTri (I22B)

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

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  phamthanhdai(I22B) on 30/3/2013, 14:58

Mình nghĩ để cái bảng trợ giúp như thế này sẽ dễ nhìn và dễ hiểu hơn.
Lúc giải cái bài này trên lớp có 1 số bạn trong đó có mình đã nhầm lẫn về thứ tự chạy của P1,P2,P3

phamthanhdai(I22B)

Tổng số bài gửi : 5
Join date : 11/03/2013
Đến từ : I22B

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

Về Đầu Trang Go down

Bài Tập Giải Thuật SJFS Có Tiếm Quyền

Bài gửi  NguyenCaoDuong(I22B) on 30/3/2013, 15:27

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

Thời điểm đến (ms) Tiến trình CPU-Burst (ms)
6P026
17P145
48P229
Dùng thuật giải SJFS có tiếm quyền điều phối CPU
a/ Vẽ biểu đồ Gantt.
b/ Tính thời gian chờ trung bình của tiến trình.


Giải

a/ Biểu đồ Gantt


b/ Thời gian chờ :
- Thời gian chờ của mỗi tiến trình:
P0=(32-6)-26=0
P1=(77-17)-45=15
P2=(106-48)-29=29

- Thời gian chờ trung bình: (0+15+29)/3=14.66ms

Thầy và các bạn xem dùm em coi có đúng không a. Em cám ơn Thầy và các bạn nhiều.

NguyenCaoDuong(I22B)

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

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

Về Đầu Trang Go down

Các trạng thái của process

Bài gửi  PhamQuocCuong (I22A) on 30/3/2013, 15:50

1. Mô hình đơn giản:


2. Mô hình 3 trạng thái:
Thực thi – Running:
- Đang thực thi (đang sử dụng CPU).
- Chỉ có 1 running process tại 1 thời điểm trên hệ thống đa chương.
Sẵn sàng – Ready:
- Sẵn sàng thực thi, tạm dừng chờ CPU.
- Có nhiều ready process.
- Được quản lý bằng ready queue.
Bị chặn – Blocked:
- Không thể thực thi cho đến khi có biến cố xảy ra.
- Có nhiều ready process.
- Được quản lý bằng blocked queue



Chuyển trạng thái:
 Running -> Blocked(1): chờ biến cố
 Running -> Ready (2): hết thời gian
 Ready - > Running (3): được thực thi
 Blocked -> Ready (4): biến cố xảy ra
Thời điểm chuyển trạng thái:
 Ngắt quãng thời gian – Clock Interrupt.
Dùng để kiểm soát thời gian.
 Ngắt quãng thiết bị - I/O Interrupt.
Liên quan đến thiết bị I/O.
 Lệnh gọi hệ thống, lỗi – System call, trap.
Khi gọi system calls, hay khi có lỗi.
Lỗi truy suất bộ nhớ (Memory Fault)
System Call, trap

3. Mô hình 5 trạng thái:



 New: khối thông tin quản lý process đã được tạo. Process chưa được nạp vào bộ nhớ chính.
 Exit: process đã kết thúc, khối thông tin process vẫn được lưu trữ  cho phép rút trích.
 Chuyển trạng thái:
- NULL -> new
- New -> Ready : Khi số process nạp chưa vượt quá giới hạn.
- Running -> Exit : Process kết thúc xảy ra tương ứng với các tình huống chủ động.

PhamQuocCuong (I22A)

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

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  PhamQuocCuong (I22A) on 30/3/2013, 16:03

HongGiaPhu (I22A) đã viết:Thưa thầy, em có một câu hỏi về giải thuật SJSF (Ngắn hơn chạy trước) được định nghĩa là nếu tiến trình mới đến có khoảng CPU kế tiếp nhỏ hơn so với thời gian chạy còn lại của tiến trình đang vận hành, nó sẽ được ưu tiên chạy thay thế.

Em có một ví dụ nhỏ với 2 tiến trình như thế này:

Lúc đầu tiến trình P1 chạy trước, khi chạy đến mức 3 gặp tiến trình 2 chỉ có khoảng CPU bằng 5, như vậy lúc này tiến trình P1 xếp vào hàng đợi và tiến trình P2 sẽ ưu tiên chạy trước như trong hình dưới đây (do khoảng CPU lúc đầu là 7 so với khoảng CPU của P2 chỉ có 5 nên ưu tiên P2 chạy trước).

hay kết quả sẽ là tiến trình P1 chạy tới mức 3, thì gặp tiến trình P2 có khoảng CPU bằng 5, lúc này khoảng CPU P1 chỉ còn lại 4 tại thời điểm P2 xuất hiện tại mức 3, như vậy tiến trình P1 sẽ chạy luôn do có khoảng CPU còn lại là 4 nhỏ hơn so với khoảng CPU mới nhất của tiến trình P2 là 5 (4 < 5).

=> Vậy trong 2 trường hợp trên trường hợp nào đúng ạ, các bạn cùng tham khảo với nào farao

Theo mình cách làm thứ 2 mới đúng theo phương pháp Very Happy

PhamQuocCuong (I22A)

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

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  TranVuSang (I22B) on 30/3/2013, 17:09

NguyenCaoTri (I22B) đã viết:MỘT BÀI TẬP VÍ DỤ QUÁ KHÓ (Khi hai tiến trình bằng CPU Burst)



I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt
II. Sử dụng thuật giải SJFS (có tiếm quyền) - Vẽ Biểu đồ Gantt

Lời giải đề nghị:

I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt

Giải thích:
Khi T=2ms thì P2 đến còn P1 bị ngắt và quay về hàng đợi Ready => P2 đứng trước P1 trong hàng đợi. Vậy P2 được cấp CPU


II. Sử dụng thuật giải SJFS có tiếm quyền - Vẽ Biểu đồ Gantt

Giải thích: Khi T=2ms thì P2 đến nhưng do P1 đến lúc T=1 nên P1 tiếp tục được chạy


Đây là cách suy nghĩ của mình( Có thể chưa chính xác). Mong được Thầy và các bạn góp ý để mình có thể hiểu chính xác hơn.
bài này cũng khó giống như bài của mình ở trang 11 vậy. các bạn thảo luận giúp mình 2 bài này nha.

TranVuSang (I22B)

Tổng số bài gửi : 53
Join date : 09/03/2013
Age : 27

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  NguyenTuHuy(I22A) on 30/3/2013, 17:38

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 background )

+ Mỗi hàng chờ có thuật giải điều phối riêng
Foreground: RR
Background

+ 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ượn thời gian CPU nào đó mà có thể lập dị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 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.
vd: Việc phuc56 vụ khách trong nhà hàng:
+ Thực khách sẽ đến gọi thức ăn nước uống.
+mỗi thức ăn và nước uống đều có time chuẩn bị là # nhau
+time đợi trung bình của khách là khác nhau.
+Nếu khách hàng thân quen hoặc đặt bàn trước thì chúng ta ưu tiên trước ( lập lịch với mức độ ưu tiên )
+Còn lại thường thì các nhà hàng sẽ phục vụ theo kiểu FCFS đến trước phục vụ trước.

NguyenTuHuy(I22A)

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

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  NguyenVanSang(I22A) on 30/3/2013, 18:56

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.

NguyenVanSang(I22A)

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

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  NguyenCaoDuong(I22B) on 30/3/2013, 21:29

PhamQuocCuong (I22A) đã viết:
HongGiaPhu (I22A) đã viết:Thưa thầy, em có một câu hỏi về giải thuật SJSF (Ngắn hơn chạy trước) được định nghĩa là nếu tiến trình mới đến có khoảng CPU kế tiếp nhỏ hơn so với thời gian chạy còn lại của tiến trình đang vận hành, nó sẽ được ưu tiên chạy thay thế.

Em có một ví dụ nhỏ với 2 tiến trình như thế này:

Lúc đầu tiến trình P1 chạy trước, khi chạy đến mức 3 gặp tiến trình 2 chỉ có khoảng CPU bằng 5, như vậy lúc này tiến trình P1 xếp vào hàng đợi và tiến trình P2 sẽ ưu tiên chạy trước như trong hình dưới đây (do khoảng CPU lúc đầu là 7 so với khoảng CPU của P2 chỉ có 5 nên ưu tiên P2 chạy trước).

hay kết quả sẽ là tiến trình P1 chạy tới mức 3, thì gặp tiến trình P2 có khoảng CPU bằng 5, lúc này khoảng CPU P1 chỉ còn lại 4 tại thời điểm P2 xuất hiện tại mức 3, như vậy tiến trình P1 sẽ chạy luôn do có khoảng CPU còn lại là 4 nhỏ hơn so với khoảng CPU mới nhất của tiến trình P2 là 5 (4 < 5).

=> Vậy trong 2 trường hợp trên trường hợp nào đúng ạ, các bạn cùng tham khảo với nào farao

Theo mình cách làm thứ 2 mới đúng theo phương pháp Very Happy

Cách làm thứ 2 đúng đó bạn ơi. Vì tại thời điểm 3 ms, p1 đã chạy được 3ms và còn 4 ms nữa thì xong, mà p2 cần tới 5ms do đó HĐH vẫn để cho p1 chạy tiếp.

NguyenCaoDuong(I22B)

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

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

Về Đầu Trang Go down

Chú ý về cách làm bài câu 4 trong bài thi cuối kỳ.

Bài gửi  VANCONGLOI(I22A) on 30/3/2013, 22:12

Kính chào Thầy và các bạn.
Mình xin trình bày ý của thầy về cách làm bài câu 4 trong bài thi cuối kỳ như sau.

NGoài giải bài tập theo công thức ra thì các bạn cần trình bày thêm:

+Bảng trợ giúp
+lý thuyết điều phối ví dụ là theo vòng robin(round robin scheduling -RRS) hay là dạng khác .v.v
+Trình bày ý nghĩa,thuật giải bài giải trên tại sao làm như vậy.

CÓ thể Mình nghe không chính xác, Mong Thầy và các bạn chỉnh sửa và góp ý.
Cảm ơn.

VANCONGLOI(I22A)

Tổng số bài gửi : 22
Join date : 09/03/2013
Age : 26
Đến từ : Bình thuậ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  NguyenHoangKimVu (I11C) on 30/3/2013, 22:20

NguyenCaoTri (I22B) đã viết:MỘT BÀI TẬP VÍ DỤ QUÁ KHÓ (Khi hai tiến trình bằng CPU Burst)



I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt
II. Sử dụng thuật giải SJFS (có tiếm quyền) - Vẽ Biểu đồ Gantt

Lời giải đề nghị:

I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt

Giải thích:
Khi T=2ms thì P2 đến còn P1 bị ngắt và quay về hàng đợi Ready => P2 đứng trước P1 trong hàng đợi. Vậy P2 được cấp CPU


II. Sử dụng thuật giải SJFS có tiếm quyền - Vẽ Biểu đồ Gantt

Giải thích: Khi T=2ms thì P2 đến nhưng do P1 đến lúc T=1 nên P1 tiếp tục được chạy


Đây là cách suy nghĩ của mình( Có thể chưa chính xác). Mong được Thầy và các bạn góp ý để mình có thể hiểu chính xác hơn.
Mình cũng đang thắc mắc ở vấn đề này. Cùng thời điểm đến và cùng CPU Burst thì không biết giải quyết thế nào? Đề thi mà ra vậy chắc cũng hoang mang lắm. Mong Thầy giải đáp giúp

NguyenHoangKimVu (I11C)

Tổng số bài gửi : 62
Join date : 25/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  NguyenThiThom(I22A) on 30/3/2013, 23:37

PhamQuocCuong (I22A) đã viết:
HongGiaPhu (I22A) đã viết:Thưa thầy, em có một câu hỏi về giải thuật SJSF (Ngắn hơn chạy trước) được định nghĩa là nếu tiến trình mới đến có khoảng CPU kế tiếp nhỏ hơn so với thời gian chạy còn lại của tiến trình đang vận hành, nó sẽ được ưu tiên chạy thay thế.

Em có một ví dụ nhỏ với 2 tiến trình như thế này:

Lúc đầu tiến trình P1 chạy trước, khi chạy đến mức 3 gặp tiến trình 2 chỉ có khoảng CPU bằng 5, như vậy lúc này tiến trình P1 xếp vào hàng đợi và tiến trình P2 sẽ ưu tiên chạy trước như trong hình dưới đây (do khoảng CPU lúc đầu là 7 so với khoảng CPU của P2 chỉ có 5 nên ưu tiên P2 chạy trước).

hay kết quả sẽ là tiến trình P1 chạy tới mức 3, thì gặp tiến trình P2 có khoảng CPU bằng 5, lúc này khoảng CPU P1 chỉ còn lại 4 tại thời điểm P2 xuất hiện tại mức 3, như vậy tiến trình P1 sẽ chạy luôn do có khoảng CPU còn lại là 4 nhỏ hơn so với khoảng CPU mới nhất của tiến trình P2 là 5 (4 < 5).

=> Vậy trong 2 trường hợp trên trường hợp nào đúng ạ, các bạn cùng tham khảo với nào farao

Theo mình cách làm thứ 2 mới đúng theo phương pháp Very Happy
Mình nghĩ trường hợp 2 đúng ak.

NguyenThiThom(I22A)

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

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  NguyenThiThom(I22A) on 30/3/2013, 23:44

NguyenHoangKimVu (I11C) đã viết:
NguyenCaoTri (I22B) đã viết:MỘT BÀI TẬP VÍ DỤ QUÁ KHÓ (Khi hai tiến trình bằng CPU Burst)



I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt
II. Sử dụng thuật giải SJFS (có tiếm quyền) - Vẽ Biểu đồ Gantt

Lời giải đề nghị:

I. Sử dụng thuật giải RRS với thời lượng = 1ms - Vẽ Biểu đồ Gantt

Thầy nói trên thực tế sẽ không xảy ra trường hợp như ví dụ: hihi
Giải thích:
Khi T=2ms thì P2 đến còn P1 bị ngắt và quay về hàng đợi Ready => P2 đứng trước P1 trong hàng đợi. Vậy P2 được cấp CPU


II. Sử dụng thuật giải SJFS có tiếm quyền - Vẽ Biểu đồ Gantt

Giải thích: Khi T=2ms thì P2 đến nhưng do P1 đến lúc T=1 nên P1 tiếp tục được chạy


Đây là cách suy nghĩ của mình( Có thể chưa chính xác). Mong được Thầy và các bạn góp ý để mình có thể hiểu chính xác hơn.
Mình cũng đang thắc mắc ở vấn đề này. Cùng thời điểm đến và cùng CPU Burst thì không biết giải quyết thế nào? Đề thi mà ra vậy chắc cũng hoang mang lắm. Mong Thầy giải đáp giúp

NguyenThiThom(I22A)

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

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

Về Đầu Trang Go down

câu 1 : Trình bày 4 tình huống ra quyết định của trình điều phối.Phân biệt điều phối có tiếm quyền và điều phối không tiếm quyền

Bài gửi  phungvanduong24(I12A) on 31/3/2013, 00:28

* 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

phungvanduong24(I12A)

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

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

Về Đầu Trang Go down

câu 4 : Trình bày thuật giải điều phối CPU với hàng chờ nhiều mức (so sánh thuật giải MQS với thuật giải MFQS)

Bài gửi  phungvanduong24(I12A) on 31/3/2013, 00:35

Đ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

phungvanduong24(I12A)

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

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

Về Đầu Trang Go down

câu 3 : giải bài tập điều phối cpu bằng giải thuật RRS vòng RoudRobin

Bài gửi  phungvanduong24(I12A) on 31/3/2013, 00:50

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:
TT Thời điểm đến (ms) CPU-Burst (ms)
P1 4 46
P2 30 28
P3 51 33
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
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/ Thể hiện bằng biểu đồ Gantt

-----+----P1--+---P1----+---P2-----+-P1--+----P3----+--P2--+-- P3----
-----|----------|----------|-----------|------|------------|-------|---------|
0--- 4--------24------- 44 ------- 64 --- 70 --------- 90 ----98 ------111

b/
P1 = (70-4)-46=20
P2= (98-30)-28=40
P3= (111-51)-33=27
TG chờ TB =(P1+P2+P3)= 87/3=29 (ms)

phungvanduong24(I12A)

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

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

Về Đầu Trang Go down

Nếu P1 và P3 có cùng thời điểm đến thì sẽ như thế nào?

Bài gửi  TranVuSang (I22B) on 31/3/2013, 00:57

Giả sử chúng ta có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:


Thời lượng điều phối CPU = 20ms
Bảng trợ giúp



Với bài toán như thế này thì theo các bạn P1 sẽ được chạy trước hay P3 sẽ được ưu tiên chạy trước?
Điều này chỉ có thể xảy ra trên lý thuyết và nó là 1 câu hỏi hốc búa mà có bạn sẽ cho là P1 chạy trước cũng có bạn sẽ cho là P3 chạy trước, và mình cũng đã có 1 bài giống thế này và mình đã cho P1 chạy trước. Tuy nhiên trong thực tế thì điều này không thể xảy ra được. Vì 1 tiến trình đang được xếp vào hàng chờ Ready thì không thể có 1 tiến trình khác cũng được xếp vào hàng chờ Ready ở cùng thời điểm đó. Trên thực tế các tiến trình sẽ lệch nhau vài mili giây, có thể P1 có thời điểm đến là mili giây thứ 25 còn P3 trễ hơn1 hoặc 2 mili giây gì đó chứ không thể có chuyện P1 và P3 được xếp vào hàng chờ Ready cùng 1 lúc được. Trên thực tế các tiến trình có thời điểm đến là khác nhau.

TranVuSang (I22B)

Tổng số bài gửi : 53
Join date : 09/03/2013
Age : 27

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

Về Đầu Trang Go down

Vẽ hình bằng công cụ đơn giản.

Bài gửi  TranVuSang (I22B) on 31/3/2013, 01:54

Chào các bạn, mấy bữa nay mình thấy có nhiều bạn không vẽ biểu đồ Gantt và các bảng được. Hôm nay mình xin giới thiệu 1 công cụ đơn giản để giúp các bạn vẽ hình được tốt hơn.

Công cụ mình sử dụng là Paint.



Các bạn khởi động chương trình lên và chúng ta sẽ có giao diện như thế này



Để vẽ 1 đường thẳng thì chúng ta chọn công cụ line.




















Chúc tất cả các bạn thành công

TranVuSang (I22B)

Tổng số bài gửi : 53
Join date : 09/03/2013
Age : 27

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

Về Đầu Trang Go down

bài tập :

Bài gửi  lekhanhhoa(I22B) on 31/3/2013, 14:56

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:


Dùng thuật giải Round-Robin với thời lượng bằng 20 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.[/quote]

Giải:


lekhanhhoa(I22B)

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

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  NguyenCaoDuong(I22B) on 31/3/2013, 21:28

phungvanduong24(I12A) đã 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:
TT Thời điểm đến (ms) CPU-Burst (ms)
P1 4 46
P2 30 28
P3 51 33
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
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/ Thể hiện bằng biểu đồ Gantt

-----+----P1--+---P1----+---P2-----+-P1--+----P3----+--P2--+-- P3----
-----|----------|----------|-----------|------|------------|-------|---------|
0--- 4--------24------- 44 ------- 64 --- 70 --------- 90 ----98 ------111

b/
P1 = (70-4)-46=20
P2= (98-30)-28=40
P3= (111-51)-33=27
TG chờ TB =(P1+P2+P3)= 87/3=29 (ms)

Ban ơi, hình như biểu đồ Gantt của bạn không đúng đó. Bạn coi lại thời điểm 64 ms nha.

NguyenCaoDuong(I22B)

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

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  NguyenCaoDuong(I22B) on 31/3/2013, 22:44

xuantri27 (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:
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14
Biểu Đồ Gantt?
Thời gian chờ trung bình?
Bài Giải


a. Biểu Đồ Gantt
P1 P2 P1 P2 P3 P1 P3 P1
3.....13.....23....33.....43.....53.....63...67....74

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

Giải thích :

Theo đề bài này thì CPU bắt đầu cấp phát cho 3 tiến trình P1, P2, P3 là thời điểm 3 và hàng đợi Ready là P1 P2 P3

+ Tại thời điểm 3, P1 đứng đầu hàng đợi Ready, như vậy P1 được chọn cho vận hành.

+ Vì q=10ms nên tại thời điểm 13, P1 tạm dừng vận hành và bị đẩy về cuối hành đợi Ready P2 P3 P1.

Như vậy P2 lúc này đứng đầu hàng đợi và xét lại thì thấy thời điểm đến của P2 là 10 < 13, nên P2 được phép tiếm quyền kế tiếp để vận hành.

+ Vì q=10ms nên đến thời điềm 23, P2 phải tạm dừng cho tiến trình khác vận hành và P2 bị đẩy về cuối hàng đợi P3 P1 P2.

Lúc này ta thấy P3 đứng đầu hàng đợi nhưng thời điểm đến của P3 là 24 > 23 (là thời điểm đang xét) nghĩa là tại thời điểm này P3 chưa có nhu cầu để vận hành, nên P3 sẽ ko tiếm quyền P2. P3 sẽ bị đẩy về cuối hàng đợi. Hàng đợi lúc này là P1 P2 P3. Do P1 được đẩy lên đầu nên P1 được phép tiếm quyền kế tiếp tại thời điểm 23 này.

+ Cứ sau 10ms, ta lại xét để cho vận hành tiến trình kế tiếp là tiến trình nào.
Tại thời điểm 33, P1 tạm dừng và bị đẩy về cuối hàng đợi Ready P2 P3 P1, P2 đứng đầu hàng đợi sẽ lên tiếm quyền kế tiếp.

+ Tại thời điểm 43, sau khi P2 vận hành 10ms thì lúc này P2 cũng vừa vận hành xong. Vì vậy P2 sẽ không nằm trong hàng đợi Ready. Ta có hàng đợi là P3 P1 Ta thấy lúc này P3 mới bắt đầu vận hành vì nó đã có nhu cầu vận hành từ lúc thời điểm 24.

+ Thời điểm 53, P3 tạm dừng và đưa vào cuối hàng đợi P1 P3.

Đồng thời P1 sẽ được ưu tiên lên tiếm quyền tiếp tục vận hành

+Thời điểm 63, P1 tạm dừng, P3 lên tiếm quyền và nó chỉ cần thêm 4ms nữa là P3 vận hành xong tiến trình của nó. Lúc này nó cũng hok còn nằm trong hàng đợi. Hàng đợi chỉ còn có P1.

+ Do đó tại thời điểm 67, P1 được vận hành và nó vận hành hết 7ms nữa là thời gian còn lại cần cho P1.

Mọi người cho ý kiến cái
Bài giải của bạn theo mình đúng rồi đó, mình vẽ biểu đồ Gantt với tính mấy lần cũng giống với bạn . Thank bạn nhiều nha.

NguyenCaoDuong(I22B)

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

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  VoMinhDien(I22B) on 1/4/2013, 10:26

NguyenCaoDuong(I22B) đã viết:
phungvanduong24(I12A) đã 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:
TT Thời điểm đến (ms) CPU-Burst (ms)
P1 4 46
P2 30 28
P3 51 33
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
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/ Thể hiện bằng biểu đồ Gantt

-----+----P1--+---P1----+---P2-----+-P1--+----P3----+--P2--+-- P3----
-----|----------|----------|-----------|------|------------|-------|---------|
0--- 4--------24------- 44 ------- 64 --- 70 --------- 90 ----98 ------111

b/
P1 = (70-4)-46=20
P2= (98-30)-28=40
P3= (111-51)-33=27
TG chờ TB =(P1+P2+P3)= 87/3=29 (ms)

Ban ơi, hình như biểu đồ Gantt của bạn không đúng đó. Bạn coi lại thời điểm 64 ms nha.
Theo mình thì bạn nên làm theo thầy giảng là cần phải vẽ thêm bản trợ giúp để có thể tính chính xác thời gian chờ, vẽ đúng biểu đồ grant.

VoMinhDien(I22B)

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

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

Về Đầu Trang Go down

Bổ sung bài tập

Bài gửi  phuquoccuong(I22A) on 1/4/2013, 13:22

Câu 1:
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 3 37
P21020
P32414
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
Trả lời:
a. Thể hiện bằng biểu đồ Gantt:

bản trợ giúp
P1 P2P3
3(37)10(20)24(14)
13(27)23(10)53(4)
33(17)43(0)67(0)
63(7)
74(0)
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=(74-3)-37=71-37=34 ms
P2=(43-10)-20=33-20=13 ms
P3=(67-24)-14=43-14=29 ms
- Thời gian chờ trung bình =(34+13+29)/3 = 76/3 = 25,33 ms
Câu 2:
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 47
P22315
P34528
Dùng thuật giải Round-Robin với thời lượng bằng 20 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
Trả lời:
a. Thể hiện bằng biểu đồ Gantt:

bản trợ giúp
P1 P2P3
5(47)23(15)45(28)
25(27)40(0)80(8 )
60(7)95(0)
87(0)
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 =(87-5)-47= 82-47= 35 ms
P2 =(40-23)-15= 17-15 = 2 ms
P3 =(95-45)-28= 50-28= 22 ms
- Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

Admin
Trình bày Đẹp và Chuyên nghiệp !

phuquoccuong(I22A)

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

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

Về Đầu Trang Go down

Vì sao hệ điều hành phải có chức năng điều phối CPU. Năm tiêu chí điều phối CPU

Bài gửi  nguyenhoanglam_I22B on 1/4/2013, 13:35

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.

nguyenhoanglam_I22B

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

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  NguyenThiMai(I22A) on 1/4/2013, 16:31

Câu 1: Trình bày 4 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
* 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 không tiếm quyền (Non-Preemptive Scheduling) và điều phối có tiếm quyền(Preemptive Scheduling)
- Giống nhau: được dùng tring điều phối CPU(chọn tiến trình trong Ready Queue để cấp thời gian CPU(chuyển sang trạng thái Running)).
- Khác nhau:
+ Không tiếm quyền: Điều phối chỉ xảy ra ở tình huống 1 và 4, không xảy ra điều phối ở tình huống 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.
+ Có tiếm quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến trình đang chạy, không cho độc chiếm CPU

NguyenThiMai(I22A)

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

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 Today at 14:51


Sponsored content


Về Đầu Trang Go down

Trang 8 trong tổng số 11 trang Previous  1, 2, 3 ... 7, 8, 9, 10, 11  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