Noi dung on tap

Admin Age : 53 Joined : 08 May 2007 Posts : 191

Bài 4: Khái niệm tiến trình, Mô hình chuyển trạng thái của tiến trình, Khối kiểm soát tiến trình (PCB - Process Control Block), Sự luân chuyển CPU giữa 2 tiến trình, Short-Time Scheduler và Long-Time Scheduler, Bài toán Sản xuất-Tiêu thụ (Producer-Consumer)

Bài 5: So sánh Process với Thread, Những ưu điểm của Đa luồng (Multithreading), Tập luồng (Thread Pulls), Lập trình đa luồng trong Windows (các hàm API như CreateThread, ResumeThread, SuspendThread, GetCurrentThread, Sleep,...)

Bài 6: Các tiêu chí điều phối CPU, Phân biệt Điều phối CPU không tiếm quyền với Điều phối CPU có tiếm quyền, Các thuật giải điều phối CPU: FCFS, SJFS (có tiếm quyền, không có tiếm quyền), Round-Robin (có thời điểm đến như được Ứng dụng trợ giúp giải bài tập hỗ trợ)

Bài 7: Khái niệm Đồng bộ hoá tiến trình và lý do phải đồng bộ hoá công việc các tiến trình đồng hành (đang cùng chạy, cùng dùng chung CPU), Khái niệm Vùng tương tranh (Critical Section) và Tính loại trừ lẫn nhau (Mutual Exclusion), Phương tiện đồng bộ hoá (Semaphore, Binary Semaphore) và các hàm API (CreateSemaphore, WaitForSingleObject, WaitForMultipleObjects,...), Bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 2 đèn hiệu semFull và semEmpty, Bài toán Hiền triết cùng ăn (Dining-Philosophers) với thuật giải Dẫn đến deadlock và Không dẫn đến deadlock (với cả 2 bài toán kinh điển này, cần xem và hiểu kỹ các lệnh trong chương trình thực thi viết bằng Visual C++ 6.0)

Bài tập: Thuật giải điều phối CPU dùng SJFS có tiếm quyền và Round-Robin có thời điểm đến (Vẽ biểu đồ Gantt và Tính thời gian chờ trung bình của các tiến trình)

Đề thi gồm: 6 câu lý thuyết (mỗi câu 1 điểm) và 2 câu bài tập (mỗi câu 2 điểm)

Joined : 01 Jul 2007 Posts : 6

: Giả sử một hệ thống có 5 tiến trình cùng đến vào 1 thời điểm với tính chất sau:
Tiến trình Độ ưu tiên Khoảng CPU (số giây)
P1 3 10
P2 1 1
P3 3 2
P4 4 1
P5 2 5
a) Vẽ 4 biểu đồ Gantt tương ứng với các thuật giải điều phối SJFS (có tiếm quyền) và RRS (với thời lượng = 1).
b) Tính thời gian chờ trung bình của các tiến trình cho mỗi thuật giải.
c) Thuật giải nào tốt nhất về phương diện thời gian chờ trung bình?
Giải đáp: Theo đề bài, các tiến trình có độ ưu tiên (Priority Scheduling- PS ), thì tiến trình nào có độ ưu tiên nhỏ nhất sẽ được chạy trước. Và SJFS là dạng đặc biệt của PS với độ ưu tiên là khoảng CPU kế tiếp.Vậy ta có
biểu đồ 1: Điều phối theo độ ưu tiên:Theo độ ưu tiên và chạy hết khoảng CPU
P2 P5 P3 P1 P4
0 1 6 8 18 19
*Thời gian chờ trung bình: 8 + 0 + 6 + 18 + 1 = 33/5 = 6.6

biểu đồ 2: Điều phối SJFS không tiếm quyền: đến trước phục vụ trước và khoảng CPU ngắn nhất.P2 và P4 đến cùng thời điểm( đề bài) cùng khoảng CPU nhưng P2 ưu tiên
P2 P4 P3 P5 P1
0 1 2 4 9
*Thời gian chờ trung bình: 9 + 0 + 2 + 1 + 4 = 16/5 = 1.2

biểu đồ 3: Điều phối SJFS có tiếm quyền: giống như biểu đồ 2, chắc tại P2 và P4 có dạng đặc biệt. ( sai?, đúng?)

biểu đồ 4:Điều phối RSS: 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. (theo đề bài thời lượng 1 giây)

P1 P2 P3 P4 P5 P1 P3 P5 P1 P3 P5 P1 P5 P1 P5 P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 19
*thời gian chờ trung bình: (0+4+2+2+1+1) + 1 + (2+3+2) + 3 + (4+2+2+1+1) = 31/5 = 6.2
Như vậy: SJFS ( tiếm quyền hay không tiếm quyền ?) ngắn nhất

Joined : 01 Jul 2007 Posts : 6

Bài 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 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ươn án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm).

Bài giải:
Nhận xét: p1 chạy hết thời lượng 20ms, nhưng p2 chưa xuất hiện, chạy thêm nửa chừng 10 ( tức thời điểm 30) p2 yêu cầu nhưng vẫn phải chờ p1 chạy hết 20ms, lúc đó p2 mới được chạy.Khi p2 chạy được 11 ms (tức thời điểm 51 ) p3 yêu cầu,nhưng phải chờ p2, nên sắp vào hàng chờ sau p1. p2 xong tới p1 chạy
P1 P1 P2 P1 P3 P2 P3
0 4 24 44 64 70 90 98 111
*Thời gian chờ trung bình: (0+20) + (10+6+20) + (19+ Cool

= 83/3 = 27.7
Xin Thầy và các bạn sữa sai.

Joined : 21 Aug 2007 Posts : 4

Xin chào Thầy !
Em đăng ký mãi đến nay mới vào được. Mừng hết biết Laughing

Admin Age : 53 Joined : 08 May 2007 Posts : 191

Bạn Thành cần chạy Ứng dụng trợ giúp giải bài tập để kiểm tra lời giải của mình (có link ở cuối mỗi trang trình bày một ví dụ điều phối CPU):

Bạn Hùng mãi mới vào được là chuyện bình thường.

Nhiều bạn vẫn chưa vượt qua được trở ngại ban đầu.

Đơn giản như vậy nhưng cũng phải cố gắng đấy.

Joined : 01 Jul 2007 Posts : 6

chương trình đó không tính được bài có thêm độ ưu tiên, thời lượng CPU và đến cung thời điểm. xin thầy chỉ đãn
Bạn nào chạy được thuât toán Robin , xin test thử. và nếu chạy được, chắc chắn trong máy bạn có file MSFLXGRD.OCX trong thư mục cài VB6, hãy copy nó, đưa lên mạng cho các bạn khác lấy về, chép vào chung thư mục với thuật toán vòng robin, and Run...hi hi

Admin Age : 53 Joined : 08 May 2007 Posts : 191

Cứ làm bài như đã hướng dẫn: Không quan tâm đến Độ ưu tiên.

Lấy thành phần bị thiếu về, giải nén và đưa vào thư mục chứa Ứng dụng giải bài tập:
http://uploadingit.com/files/153620_fywxd/MSFLXGRD.zip

Chắc ăn hơn: Cài Visual Studio 6.0.

Joined : 01 Jul 2007 Posts : 6

Xin cám ơn Thầy, và em xin phép trình bày cách hiểu cua em về diều phối CPU, vì thú thật với thầy là em đang có dự tính sẽ viết chương trinh vẽ biểu đồ Gantt, nên em xin trình bày cách tính của em,xin thầy và các bạn chỉ dẫn các sai sót. Sau này, đây sẽ là các điều kiện trong chương trình xét và tính toán vẽ biểu đồ.

Thưa Thầy, em xin trình bày cách hiểu của em về Các thuật giải điều phối
CPU như sau:

1.
Đến
trước - Phục vụ trước (First-Come, First-Served Scheduling - FCFS):

a.
Các
tiến trình được thực hiện theo thứ tụ và hết khoảng CPU của nó.

2.
Ngắn hơn-Chạy trước (Shortest-Job-First
Scheduling-SJFS):

a.
Đến cùng
thời điểm: Khoảng CPU nhỏ hơn thì được chạy trước

b.
SJFS không tiếm quyền: tiến trình được thực hiện hết khoảng
CPU của nó

c.
SJFS tiếm quyền : tiến trình mới đến có khoảng CPU ngắn hơn sẽ được chạy trước
tiến trình đang chờ chạy.

3.
Điều
phối theo độ ưu tiên (Priority Scheduling- PS )

a.
Mỗi
tiến trình được cấp1 số ấn định độ ưu tiên. .Cùng đến 1 thời
điểm, độ ưu tiên nhỏ nhất sẽ chạy
trước.

b.
SJFS không tiếm quyền: cùng độ ưu tiên nhưng ngắn hơn được chạy
trước và chạy hết khoảng CPU của nó.

c. SJFS
tiếm quyền: cùng độ ưu tiên, tiến
trình mới đến có khoảng CPU kế tiếp nhỏ hơn so với thời gian 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ế.

4. Điều phối theo vòng Robin (Round Robin
Scheduling- RRS):

a. Mỗi tiến trình được cấp 1 thời lượng CPU
(Time Quantum), Tới trước phục vụ trước. Nhưng hết thời
lương CPU thì bị tiếm quyền. Và đưa vào cuối hàng chờ Ready. Tiến
trình đầu tiên trong hàng chờ Ready được chọn chạy kế tiếp.

b. Nếu đến cùng thời điểm, xét độ ưu
tiên. Cùng độ ưu tiên, xét khoảng CPU. Tất
cả các tiến trình sau khi chạy hết thời lượng CPU(Time
Quantum) đều bị xếp cuối
cùng trong hàng đợi, bất chấp khoảng CPU là bao nhiêu.

5. Điều phối hàng chờ nhiều mức.(không vẽ Gantt về cái này)
Xin cám ơn thầy và các bạn.

Admin Age : 53 Joined : 08 May 2007 Posts : 191

Bạn Công Thành về cơ bản hiểu đúng các thuật giải điều phối CPU.

Với SJFS có tiếm quyền, cần trình bày lại cho rõ: Nếu tiến trình mới đến có khoảng CPU (thời gian dùng CPU) nhỏ hơn Khoảng còn lại của tiến trình đang chạy (đang dùng CPU) thì được ưu tiên chọn chạy (tiến trình đang chạy sẽ bị tiếm quyền sử dụng CPU, bị tạm ngừng và được đưa trở về hàng chờ Ready)

Không cần quan tâm đến Độ ưu tiên.

Chỉ chú ý giải 2 loại bài tập: SJFS có tiếm quyền và Round-Robin (có thời điểm đến)

Tuy nhiên, do làm bài tập dễ sai (sai một chút có thể mất điểm luôn), các em chú ý học Lý thuyết theo Hướng dẫn ôn tập.

Joined : 01 Jul 2007 Posts : 6

Dạ, em cám ơn Thầy đã chỉ dẫn

Joined : 21 Aug 2007 Posts : 4

Thưa Thầy.

Nếu là vòng roundbind có tiếm quyền và có thời điểm đến thì quan tâm cả 3 vấn đề Thời lượng, thời điểm đến và khoảng chạy.
Trường hợp 1: nếu khoảng chạy còn mà hết thời luợng thì bị tiếm quyền và bị đẩy vào hàng chờ Ready
Trường hợp 2: nếu thời lượng còn mà khoảng chạy hết thì cũng bị tiếm quyền
Trường hợp 3: nếu thời lượng còn, khoảng chạy cũng đang còn. mà thời điểm đến của tiến trình kế nằm trong khoảng này cũng bị tiếm quyền

em xin trình bày cách hiểu của em, mong Thầy góp ý

Admin Age : 53 Joined : 08 May 2007 Posts : 191

Hoan nghênh bạn Hùng cũng vào cuộc.

Tuy nhiên, với Trường hợp 3 chưa chính xác lắm: Nếu khoảng chạy (thời lượng, ví dụ 20 ms) còn mà có tiến trình mới xuất hiện, thì tiến trình đang chạy không bị tiếm quyền sử dụng CPU, mà cứ làm cho đến hết khoảng chạy thì mới tạm ngừng để tiến trình kế tiếp vào cuộc (không nhất thiết phải là tiến trình mới xuất hiện)

Thày vẫn nhấn mạnh: Đừng sa vào Bài tập vì dễ sai, Cần tập trung học Lý thuyết (đâu có nhiều nhặn gì)

Joined : 21 Aug 2007 Posts : 4

xin cám ơn thầy nhiều lắm, em đang bị lủng củn chổ vòng robin. giờ em đã thông

Joined : 21 Aug 2007 Posts : 4

Thưa Thay Tuan truong hop nay ngo qua em ko hieu thay giai thich gium Question

Guest

Chương trình giải bài tập làm đúng đấy:

Ô thứ hai chỉ rộng 2 ms nên hẹp quá, vẽ không nổi thôi.

Ô thứ 3 trống vì đến thời điểm 30 mới xuất hiện P2 (trong khi P1 đã hoàn tất)