Thảo luận Bài 6

1. First Come First Served (FCFS)
Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO. Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho dến khi kết thúc hoặc bị ngắt.
Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt )chi phí tổ chức thực hiện rất thấp (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là thứ tự của tiến trình trong hàng đợi)
Nhược điểm của thuật toán là thời gian trung bình chờ phục vụ của các tiến trình là như nhau ( không kể tiến trình ngắn hay dài), do đó dẫn tới 3 nhược điểm sau:
- thời gian chờ trung bình sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình.
- nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
- khi có tiến trìn dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.
2. Shortest Job First (SJF)
thuật toán SJC xác định thứ tự ưu tiên thực hiện tiến trình dựa vào tổng thời gian thực hiện tiến trình. Tiến trình nào có tổng thời gian thực hiện ngắn sẽ được ưu tiên phục vụ trước.
Ưu điểm của thuật toán là thời giàn chờ đợi trung bình của các tiến trình ngắn hơn so với SCFS. SJF nhanh chóng loại bỏ các tiến trình ngắn, giảm số lượng các tiến trình trong hàng đợi.
Nhược điểm chính của thuật toán là chế độ phân phối lại giờ CPU cũng được áp dụng trong trường hợp ngắt các tiến trình dài đang thực hiện để phục vụ các tiến trình ngắn hơn mới xuất hiện trong hàng đợi. Nếu tiến trình mới xuất hiện có tổng thời gian thực hiện ngắn nhưng vẫn lớn hơn thời gian cần thiết để thực hiện nốt tiến trình đang thực hiện thì việc ngắt tiến trình là không hợp lý.
3. Round Robin (RR)
- Trong thuật toán này, hệ thông quy định một lượng tử thời gain (time quantum) khoảng từ 10-100 mili giây (ms).
- Mỗi tiến trình trong hàng đợi lần lượt được phân phối một lượng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến trình chưa kết thúc hoặc không rời và trạng thái đợi thì nó được chuyển về cuối hàng đợi.
- Hàng đợi các tiến trình được tổ chức theo kiểu vòng tròn và các tiến trình luôn luôn đảm bảo được phục vụ. khi có tiến trình mới phát sinh, nó sẽ được đưa vào hàng đợi vòng tròn và được đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn hay dài đều có độ ưu tiên phục vụ như nhau.
- Trên thực tế, để đảm bảo độ ưu tiên cho các tiến trình dài, hệ thống sẽ phân chia các tiến trình thành m lớp. Số lần đươc phục vụ và thời gian một lần phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình được phục vụ ki lần và mỗi lần với thời gian qi).
- Nếu sau khoảng thời gian đã được phân phối mà tiến trình chưa kết thúc hoặc không bị ngắt thì nó sẽ được chuyển sang lớp thứ i + 1 ( với ki+1 và qi +1 lớn hơn .). Lượng tử thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp m). Ở đó nó sẽ được phục vụ với lượng tử qm không đổi. Như vậy thứ tự ưu tiên của các tiến trình sẽ tăng dần theo thời gian xếp hàng đợi.
- Ưu điểm của phương pháp phục vụ đồng mức theo lớp sẽ cho phép hệ thông ưu tiên những tiến trình ngắn (vì nó kết thúc sớm) nhưng nó không gây tổn hại lớn cho các tiến trình dài.
- Nhược điểm là do phải thường xuyên phân phối lại giờ CPU nên thời gian chờ đợi trung bình của Round Robin có thể lớn hơn so với FCFS.

AnhDao(I22B) đã viết:

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

Bạn ơi , bạn có thể giải thích jum mình tại sao tính dc P2= 30 - 20 ko?
Và P3 = 50 - 25 ? mình vẫn chưa hỉu ?
Lẽ ra P3 , thời gian chờ là móc 50 , sao lại trừ thêm cho 25 nhỉ?

Mình xin mạn phép giải thích cho bạn như thế này: P3 đến vào ms thứ 20 trong khi đó thằng P1 vẫn còn đang hoạt động đến ms 30 nó mới hết hoại động (Giải thuật RRS cấp cho mỗi tiến trình 20ms theo đề để hoạt động) khi đó P3 phải chờ trong 10ms nên P2 = 30-20 = 10ms. Còn P3 thì đến vào ms thứ 25 nên nó phải chờ thằng P1 hoạt động xong rồi tới P2 hoạt động xong thì nó mới chạy đồng nghĩa với việc khi đó P1 còn 5ms nữa mới hết công việc còn P2 thì chạy hết thời gian cho phép là 20ms. Khi đó bạn có thể cộng 2 thời gian đó lại là ra thời gian chờ của P3.
p\s: Không bít mình giải thích vậy bạn có hiểu không, nếu chưa hiểu thì hãy comment lại để mình với các bạn khác có thể giúp bạn hiểu thêm.

BuiTrongHung41(I11C) đã viết:Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 5 34
P2 17 23
P3 24 9
Dùng thuật giải Round-Robin với thời lượng 10 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt.
b. Tính thời gian chờ trung bình của các tiến trình.

Giải:
a. Biểu đồ Gantt

---| P1 | P1 | P2 | P3 | P1 | P2 | P1 | P2|
5 15 25 35 44 54 64 68 71
b. Thời gian chờ trung bình của các tiến trình:
T(tb)= (T1+T2+…+Tn)/n
T1= (5 – 5)+(15-5)+(44-35)+(64-54)=29
T2=(25-15)+(54-44)+(68-64)=24
T3=(35-25)=10
T(tb)=(29+24+10)/3=21ms

Bạn có thể giải thích thêm một tí về cách tính thời gian chờ trung bình không?
Mình nghĩ hoài mà ko hiểu lắm. Nhìn vào mấy bài của các bạn trên này thì mỗi bạn một đáp án, ko biết đáp án nào là đúng nữa.
Mong các bạn giúp đỡ nhé.

Một hệ thống có 5 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 FJFS (có tiếm quyền) để đ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.




T1=(12-2) + (1-1) = 10
T2= 0
T3 = (5-4) + (2-2) = 1
T4 = 0
T5= 6-5= 1
Ttb= (10 +0 +1 +0 +1)/5 = 12/5 =2,4ms

Mong Thầy và các bạn cho ý kiến

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

mình vẫn chưa hiểu lắm về thời gian chờ trung bình của thuật giải này, các bạn có thể nói rõ hơn chút về thời gian chờ trung bình. cám ơn các bạn

AnhDao(I22B) đã viết:

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

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

Bài của bạn mình xin dc bổ sung như những j mình nge dc từ Thầy nhé :
+ 2 số 0 trong lệnh : ko học nên các bạn đường quan tâm nhé, bít cách nó làm như vậy thôi
+ số 0 trước số 4 : thể hiện giá trị được truyền cho hàm
+ số 4 : thể hiện luồng mới được tạo sẽ vận hành theo code , nó báo cho người sử dụng bít luồng này trong trạng thái ngủ, và chờ được đánh thức

Cám ơn bạn đã bổ sung nhé

TruongMinhTriet(I22B) đã viết:

AnhDao(I22B) đã viết:

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

Bạn ơi , bạn có thể giải thích jum mình tại sao tính dc P2= 30 - 20 ko?
Và P3 = 50 - 25 ? mình vẫn chưa hỉu ?
Lẽ ra P3 , thời gian chờ là móc 50 , sao lại trừ thêm cho 25 nhỉ?

Mình xin mạn phép giải thích cho bạn như thế này: P3 đến vào ms thứ 20 trong khi đó thằng P1 vẫn còn đang hoạt động đến ms 30 nó mới hết hoại động (Giải thuật RRS cấp cho mỗi tiến trình 20ms theo đề để hoạt động) khi đó P3 phải chờ trong 10ms nên P2 = 30-20 = 10ms. Còn P3 thì đến vào ms thứ 25 nên nó phải chờ thằng P1 hoạt động xong rồi tới P2 hoạt động xong thì nó mới chạy đồng nghĩa với việc khi đó P1 còn 5ms nữa mới hết công việc còn P2 thì chạy hết thời gian cho phép là 20ms. Khi đó bạn có thể cộng 2 thời gian đó lại là ra thời gian chờ của P3.
p\s: Không bít mình giải thích vậy bạn có hiểu không, nếu chưa hiểu thì hãy comment lại để mình với các bạn khác có thể giúp bạn hiểu thêm.

Mình làm phiền bạn xíu nữa nhé , sao mình vẫn còn mơ hồ bạn T ạ, mình nhìn trong biểu đồ mình thấy :
- P2 đến vào mốc thời gian 30 , trừ đi 10 giây khoảng tjan chờ phía trc , phải bằng 20 chứ?

Theo cách tính mình hỉu là như sau :
+ P1 chờ 10ms mới thực hiện, vậy nó sẽ là : 10+(65-30)
+P2 đến vào mốc 30 , Vậy là : (30-10ms chờ)+(75-50)
+P3 đến vào mốc 50,mình cũng trừ đi 10s chờ , vậy là : (50-10)
Hức hà, mình hỉu sao nói vậy nhé , mong các bạn thương tình chỉ dẫn

TruongTranThanhTu(I22B) đã viết:

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

mình vẫn chưa hiểu lắm về thời gian chờ trung bình của thuật giải này, các bạn có thể nói rõ hơn chút về thời gian chờ trung bình. cám ơn các bạn

chào bạn . Theo mình hỉu là thế này, mình ghi cách mình làm lun nhé
+P1 mình lấy mốc đầu của P1 sau, trừ mốc cuối của P1 trước : 11 - 9 = 9
+P2 tương tự : 5 -4 = 1
+P3 : mốc bắt đầu là 4, thời gian chờ 4 ms : 4-4=0
+P4:mốc bắt đầu là 7, thời gian chờ 5 ms : 7-5 = 2

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

cách chạy biểu đồ Gantt:
- Thời điểm 0-2: P1 chạy
- Thời điểm 2-4: P2 chạy vi khi đó P1 chạy được 2 còn 5 ( 7-2=5> P2 = 4)
- Thời điểm 4-5: P3 chạy vì P3 = 1 < P2 = ( 4-2=2)
- Sau đó P2 chạy tiếp vì P2=2< P4=4 < P1=5
- Rồi P4 chạy vì P4=4 < P1=5
Cuối cùng P1 chạy.

HoangThanhThien(I22B) đã viết:

AnhDao(I22B) đã viết:

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

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

Bài của bạn mình xin dc bổ sung như những j mình nge dc từ Thầy nhé :
+ 2 số 0 trong lệnh : ko học nên các bạn đường quan tâm nhé, bít cách nó làm như vậy thôi
+ số 0 trước số 4 : thể hiện giá trị được truyền cho hàm
+ số 4 : thể hiện luồng mới được tạo sẽ vận hành theo code , nó báo cho người sử dụng bít luồng này trong trạng thái ngủ, và chờ được đánh thức

Cám ơn bạn đã bổ sung nhé

Cám ơn hai bạn nhe. Có một số thứ Thầy giải thích nhanh quá mình không nghe kịp nhưng nhờ có 2 bạn diễn giải và bổ sung nên cũng bắt đầu hiểu một ít rồi. Thank hai bạn nhiều.

Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.

Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.

1. Giới thiệu

1.1. Mục tiêu điều phối

Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau :

a) Sự công bằng ( Fairness) :

Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

b) Tính hiệu qủa (Efficiency) :

Hệ thống phải tận dụng được CPU 100% thời gian.

c) Thời gian đáp ứng hợp lý (Response time) :

Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

d) Thời gian lưu lại trong hệ thống ( Turnaround Time) :

Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

e) Thông lượng tối đa (Throughput ) :

Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.

1.2. Các đặc điểm của tiến trình

Điều phối hoạt động của các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ điều hành khi giải quyết phải xem xét nhiều yếu tố khác nhau để có thể đạt được những mục tiêu đề ra. Một số đặc tính của tiến trình cần được quan tâm như tiêu chuẩn điều phối :

a) Tính hướng xuất / nhập của tiến trình ( I/O-boundedness):

Khi một tiến trình nhận được CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình như thế thường bao gồm nhiều lượt sử dụng CPU , mỗi lượt trong một thời gian khá ngắn.

b) Tính hướng xử lý của tiến trình ( CPU-boundedness):

Khi một tiến trình nhận được CPU, nó có khuynh hướng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình như thế thường bao gồm một số ít lượt sử dụng CPU , nhưng mỗi lượt trong một thời gian đủ dài.

c) Tiến trình tương tác hay xử lý theo lô :

Người sử dụng theo kiểu tương tác thường yêu cầu được hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ được xử lý theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận được.

d) Độ ưu tiên của tiến trình :

Các tiến trình có thể được phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ ưu tiên cao hơn) cần được ưu tiên hơn.

e) Thời gian đã sử dụng CPU của tiến trình :

Một số quan điểm ưu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên chọn chúng.

f) Thời gian còn lại tiến trình cần để hoàn tất :

Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng cách cho các tiến trình cần ít thời gian nhất để hoàn tất được thực hiện trước. Tuy nhiên đáng tiếc là rất hiếm khi biết được tiến trình cần bao nhiêu thời gian nữa để kết thúc xử lý.

1.3. Điều phối không độc quyền và điều phối độc quyền (preemptive/nopreemptive)

Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi CPU giữa các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo nguyên lý độc quyền hoặc không độc quyền.

Điều phối độc quyền : Nguyên lý điều phối độc quyền cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định điều phối CPU sẽ xảy ra trong các tình huống sau:

Khi tiến trình chuyển từ trạng thái đang xử lý(running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc…).

Khi tiến trình kết thúc.

Các giải thuật độc quyền thường đơn giản và dễ cài đặt. Tuy nhiên chúng thường không thích hợp với các hệ thống tổng quát nhiều người dùng, vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến trình này có thể giữ CPU một thời gian không xác định, có thể ngăn cản những tiến trình còn lại trong hệ thống có một cơ hội để xử lý.

Điều phối không độc quyền : Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không độc quyền cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận được CPU, nó vẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng một tiến trình khác có độ ưu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Như vậy là tiến trình có thể bị tạm dừng hoạt động bất cứ lúc nào mà không được báo trước, để tiến trình khác xử lý. Các quyết định điều phối xảy ra khi :

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc…).

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái ready ( ví dụ xảy ra một ngắt).

Khi tiến trình chuyển từ trạng thái chờ (blocked) sang trạng thái ready ( ví dụ một thao tác nhập/xuất hoàn tất).

Khi tiến trình kết thúc.

Các thuật toán điều phối theo nguyên tắc không độc quyền ngăn cản được tình trạng một tiến trình độc chiếm CPU, nhưng việc tạm dừng một tiến trình có thể dẫn đến các mâu thuẫn trong truy xuất, đòi hỏi phải sử dụng một phương pháp đồng bộ hóa thích hợp để giải quyết.

Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có thể xảy ra tình trạng các tác vụ cần thời gian xử lý ngắn phải chờ tác vụ xử lý với thời gian rất dài hoàn tất! Nguyên lý điều phối độc quyền thường chỉ thích hợp với các hệ xử lý theo lô.

Đối với các hệ thống tương tác(time sharing), các hệ thời gian thực (real time),cần phải sử dụng nguyên lý điều phối không độc quyền để các tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện điều phối theo nguyên lý không độc quyền đòi hỏi những cơ chế phức tạp trong việc phân định độ ưu tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình.

2. Tổ chức điều phối

2.1. Các danh sách sử dụng trong quá trình điều phối.

Hệ điều hành sử dụng hai loại danh sách để thực hiện điều phối các tiến trình là danh sách sẵn sàng (ready list) và danh sách chờ đợi(waiting list).

Khi một tiến trình bắt đầu đi vào hệ thống, nó được chèn vào danh sách các tác vụ (job list). Danh sách này bao gồm tất cả các tiến trình của hệ thống. Nhưng chỉ các tiến trình đang thường trú trong bộ nhớ chính và ở trạng thái sẵn sàng tiếp nhận CPU để hoạt động mới được đưa vào danh sách sẵn sàng.

Bộ điều phối sẽ chọn một tiến trình trong danh sách sẵn sàng và cấp CPU cho tiến trình đó. Tiến trình được cấp CPU sẽ thực hiện xử lý, và có thể chuyển sang trạng thái chờ khi xảy ra các sự kiện như đợi một thao tác nhập/xuất hoàn tất, yêu cầu tài nguyên chưa được thỏa mãn, được yêu cầu tạm dừng ...Khi đó tiến trình sẽ được chuyển sang một danh sách chờ đợi.

Hệ điều hành chỉ sử dụng một danh sách sẵn sàng cho toàn hệ thống, nhưng mỗi một tài nguyên ( thiết bị ngoại vi ) có một danh sách chờ đợi riêng bao gồm các tiến trình đang chờ được cấp phát tài nguyên đó.


Quá trình xử lý của một tiến trình trải qua những chu kỳ chuyển đổi qua lại giữa danh sách sẵn sàng và danh sách chờ đợi. Sơ đồ dưới đây mô tả sự điều phối các tiến trình dựa trên các danh sách của hệ thống.

Thoạt đầu tiến trình mới được đặt trong danh sách các tiến trình sẵn sàng (ready list), nó sẽ đợi trong danh sách này cho đến khi được chọn để cấp phát CPU và bắt đầu xử lý. Sau đó có thể xảy ra một trong các tình huống sau :

Tiến trình phát sinh một yêu cầu một tài nguyên mà hệ thống chưa thể đáp ứng, khi đó tiến trình sẽ được chuyển sang danh sách các tiến trình đang chờ tài nguyên tương ứng.

Tiến trình có thể bị bắt buộc tạm dừng xử lý do một ngắt xảy ra, khi đó tiến trình được đưa trở lại vào danh sách sẵn sàng để chờ được cấp CPU cho lượt tiếp theo.


Trong trường hợp đầu tiên, tiến trình cuối cùng sẽ chuyển từ trạng thái blocked sang trạng thái ready và lại được đưa trở vào danh sách sẵn sàng. Tiến trình lặp lại chu kỳ này cho đến khi hoàn tất tác vụ thì được hệ thống hủy bỏ khỏi mọi danh sách điều phối.

2.2. Các cấp độ điều phối

Thực ra công việc điều phối được hệ điều hành thực hiện ở hai mức độ : điều phối tác vụ (job scheduling) và điều phối tiến trình ( process scheduling).

a) Điều phối tác vụ

Quyết định lựa chọn tác vụ nào được đưa vào hệ thống, và nạp những tiến trình của tác vụ đó vào bộ nhớ chính để thực hiện. Chức năng điều phối tác vụ quyết định mức độ đa chương của hệ thống ( số lượng tiến trình trong bộ nhớ chính). Khi hệ thống tạo lập một tiến trình, hay có một tiến trình kết thúc xử lý thì chức năng điều phối tác vụ mới được kích hoạt. Vì mức độ đa chương tương đối ổn định nên chức năng điều phối tác vụ có tần suất hoạt động thấp .

Để hệ thống hoạt động tốt, bộ điều phối tác vụ cần biệt tính chất của tiến trình là hướng nhập xuất (I/O bounded) hay hướng xử lý ( CPU bounded). Một tiến trình được gọi là hướng nhập xuất nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác nhập xuất. Ngược lại một tiến trình được gọi là hướng xử lý nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác tính toán. Để cân bằng hoạt động của CPU và các thiết bị ngoại vi, bộ điều phối tác vụ nên lựa chọn các tiến trình để nạp vào bộ nhớ sao cho hệ thống là sự pha trộn hợp lý giữa các tiến trình hướng nhập xuất và các tiến trình hướng xử lý

b) Điều phối tiến trình

Chọn một tiến trình ở trạng thái sẵn sàng ( đã được nạp vào bộ nhớ chính, và có đủ tài nguyên để hoạt động ) và cấp phát CPU cho tiến trình đó thực hiện. Bộ điều phối tiến trình có tần suất hoạt động cao, sau mỗi lần xảy ra ngắt ( do đồng hồ báo giờ, do các thiết bị ngoại vi...), thường là 1 lần trong khoảng 100ms. Do vậy để nâng cao hiệu suất của hệ thống, cần phải tăng tốc độ xử lý của bộ điều phối tiến trình. Chức năng điều phối tiến trình là một trong chức năng cơ bản, quan trọng nhất của hệ điều hành.

Trong nhiều hệ điều hành, có thể không có bộ điều phối tác vụ hoặc tách biệt rất ít đối với bộ điều phối tiến trình. Một vài hệ điều hành lại đưa ra một cấp độ điều phối trung gian kết hợp cả hai cấp độ điều phối tác vụ và tiến trình

ví dụ về MQS
ga tàu có 2 cửa bán vé cửa sô 1 dành cho những người có công như thương bệnh binh, bà mẹ việt nam anh hùng. cửa số 2 dành cho những người bình thường như sinh viên, học sinh. lúc đó có 2 cô bán vé cho hai cửa bán vé này, nhưng một cô có việc phải về. cô còn lại ở lại bán vé nhưng cô này luôn bán vé ưu tiên cho cửa số 1 hơn là cửa số 2, mỗi lần không có khách ở ô cửa số 1 cô ta lại chạy sang cửa số 2 để bán, nhưng khi cửa số 1 có khách thì cô ta ngay lập tức qua ô cửa số 1 để bán vé cho dù ô cửa số 2 khách đang đông và đang chờ.
ví dụ về MFQS
cũng hai ô cửa bán vé trên, nhưng xảy ra trường hợp tại ô cửa số 2 một vị khách có việc gấp cần được mua vé thì vị khách này sẽ được chuyển qua ô cửa số 1 để được mua vé

*Multilevel Queue Scheduling - MQS

-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-Quan hệ giữa các mức:
+ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

* Multilevel Feedback Queue Scheduling - MFQS

-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+Thuật giải điều phối cho mỗi mức.
+Phương thức nâng cấp tiến trình.
+Phương thức hạ cấp tiến trình.
+Phương thức chọn hàng chờ cho tiến trình mới.

Ví dụ: Trong ga tàu có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ cửa 2: cho thương binh, Mẹ VNAH.
+ cửa 3: cho những người bình thường, khách vảng lai.
+ cửa 4: khách có độ ưu tiên thấp hơn.
+ cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.
ĐỘ ƯU TIÊN HẠ TỪ TRÊN XUỐNG, KHÔNG CÓ SỰ ƯU TIÊN TỪ MỨC DƯỚI ĐI NGƯỢC LÊN MỨC TRÊN.

Admin
Không phải lúc nào cũng vậy ! Tuỳ từng hệ thống cụ thể thôi !

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?
a. 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.
b. 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.
c. 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, …).
d. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
e. 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.

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

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

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

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

5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.

6. Trình bày thuật giải điều phối MFQS.
- Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
- MFQS đặc trưng bởi các thông số:
+ Số mức (số hàng chờ)
+ Thuật giải điều phối cho mỗi mức
+ Phương thức nâng cấp tiến trình
+ Phương thức hạ cấp tiến trình
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới

Các ví dụ minh họa về thuật giải:
Thuật giải FCFS : Xếp hàng chờ khám bệnh, người nào đến trước thì được khám trước, đến sau thì khám sau.
Thuật giải SJFS (không tiếm quyền): Xếp hàng đợi mua vé tàu ở ga Hòa Hưng, Anh A đến trước mua 7 vé, sau khi mua được 2 vé thì anh B xuất hiện (Anh B dự định mua 4 vé) nhưng quầy vé sẽ vẫn tiếp tục bán cho anh A hết 7 vé rồi mới bán 4 vé cho anh B...
Thuật giải SJFS (có tiếm quyền): Giống như ví dụ trên như khi bán được 2 vé cho anh A thì anh B xuất hiện mua 4 vé thì lúc này quầy bán vé sẽ dừng lại, anh A qua bên phòng đợi bên cạnh chờ, quầy bán vé sẽ bán cho anh B nhưng khi bán anh B được 1 vé thi anh C xuất hiện mua 1 vé thì quầy lại tiếp tục dừng bán vé cho anh B và Anh B qua phòng chờ. Quầy bán vé bán 1 vé cho anh C rồi quầy sẽ xem xét anh B còn mua 3 vé, anh A còn mua 5 vé thì quầy sẽ phụ vụ anh B. Sau khi bán hết cho anh B quầy lại tiếp tục phục vụ trở lại anh A số vé còn lại.
Thuật giải vòng Robin: Trong nhà hàng chỉ có 1 anh bồi bàn và anh bồi bàn đó sẽ phụ vụ cho mỗi bàn trong nhà hàng là 20ms, chạy qua lại giữa các bàn nên mỗi bàn có cảm giác là mình được anh bồi bàn phục vụ riêng cho mình.
Thuật giải MQS : Tai một nhà ga có 5 cỏng bán vé. Cổng 1 chỉ ưu tiên bán vé cho những người làm trong nhà ga. Cổng 2 bán chỉ ưu tiên bán vé cho người có công cách mạng. Cổng 3 ưu tiên bán cho người già yếu, bệnh tật. Cổng 4 bán cho những người khác. Cổng 5 bán cho sinh viên. Nếu người nào mua vé thì ra ngoài theo cổng đó luôn.
Thuật giải MFQS :Nhà ga có 3 cổng , cổng 0 bắt buộc tất cả mọi người mua vé phải đi qua, nếu mua vé xong thì sẽ ra ngoài theo cổng đó, nếu quá đông thì những người chưa mua được vé sẽ đẩy xuống cổng 1 và xong thì sẽ ra theo cổng đó. Nếu vẫn chưa mua được thì sẽ đẩy xuống cổng 2 và xong thì ra ngoài. Tuy nhiên vẫn có trường hợp nâng cấp đưa người mua vé cổng 2 trở về cổng 1 mua vé nhưng tuyệt đối không có việc nâng cấp đưa người mua vé từ cổng 1 trở lại cổng 0.

1: Khi tiến trình chuyển từ Running sang Waiting( chờ I/O hoặc tiến trình con ). Khi tiến trình đang chạy mà tiến trình có nhu cầu nhập xuất hoặc 1 tiến trình con thì HĐH sẽ quyết định xem là tiến trình nào sẽ thay thế tiến trình đang chạy
2: Khi tiến trình chuyển từ Running sang Ready( do ngắt xảy ra ). Do thời gian mà tiến trình sử dụng CPU đã hết nên ngắt xảy ra và nó ko được dùng CPU nữa và HĐH sẽ chọn 1 tiến trình khác thay thế tiến trình đang chạy.
3: Khi tiến trình chuyển từ Waiting sang Ready( khi kết thúc I/O ). Lúc này HĐH sẽ quyết định là tiến trình nào sẽ được chạy tiếp tùy theo thứ tự tiến trình trong Ready.
4: Khi tiến trình kết thúc công việc. Lúc này HĐH sẽ chọn tiến trình thay thế tiến trình đã kết thúc công việc của nó.
Phân biệt điều phối có tiếm quyền và điều phối không tiếm quyền:
Điều phối không tiếm quyền có nghĩa là khi 1 tiến trình đang sử dụng CPU thì HĐH không thể bắt nó dừng công việc của nó lại được, không thể bắt nó trả lại CPU được. Nó chỉ trả lại CPU khi nó kết thúc công việc của nó hoặc nó phải thực hiện thao tác nhập xuất thì lúc này HĐH mới có thể điều tiến trình khác vào sử dụng CPU.
Điều phối có tiếm quyền là khi 1 tiến trình đang chạy mà HĐH cảm thấy có 1 tiến trình nào đó cần dùng CPU trước thì HĐH sẽ can thiệp vào tiến trình đang chạy bắt nó phải dừng lại và trả lại CPU cho tiến trình khác làm việc trước thì đây là điều phối có tiếm quyền.
Trình điều phối chỉ xảy ra ở trường hợp 2 và 3 hoặc 1 và 4 là trình điều phối không tiếm quyền, còn trình điều phối xảy ra ở cả 4 trường hợp có nghĩa là ở bất cứ tình huống nào HĐH cũng có thể vào cuộc và bắt tiến trình đang chạy nhường CPU thì đó là điều phối có tiếm quyền.
VD: 1 bếp lửa đang nấu khoai lan, nấu được 1 nữa thời gian rồi mà mình bổng nhiên muốn đi tắm nước nóng thế là mình bắt nồi khoai xuống và bắt ấm nước lên, ấm nước đang nấu như thế nhưng bổng nhiên mình lại đói bụng và muốn ăn cơm và mình bắt ấm nước xuống và bắt nồi cơm lên. Đây là điều phối có tiếm quyền. Trường hợp nồi cơm đang sôi mà chúng ta lại muốn đi tắm nước nóng thì chúng ta ko thể bắt nồi cơm xuống mà bắt ấm nước lên được vì nếu làm vậy nồi cơm sẽ bị hỏng ngay không ngon và lúc này nồi cơm đã độc chiếm bếp lửa. Đây là điều phối không tiếm quyền. Tất nhiên là mình vẫn có thể bắt nồi cơm xuống và bắt ấm nước lên nhưng ở đây mình đang ví dụ về điều phối ko tiếm quyền nên để nồi cơm độc chiếm bếp lửa luôn.

Các HĐH hiện đại được lập trình theo mô hình có tiếm quyền để nó có thể can thiệp vào bất cứ 1 tiến trình nào mà nó cảm thấy là cần thiết.
Mong các bạn góp ý thêm.

Bài giải:

cách tính theo hình


thời gian chờ:
P1: 0+(65-30)=35
P2:(30-20)+(75-50)=35
P3:50-25=25
thời gian chờ trung bình: (35+35+25)/3=31,6ms

xin thầy và mọi người cho ý kiến là có thể làm cách này được không?

Time Quantum được hệ thống kiểm soát 20ms.chia là các khoảng 20ms thới gian xử lý của 1 tiến trình.
Khi P1 chạy đến ms thứ 20, sẽ ngắt, đưa vào hàng đợi. P2 bắt đầu chạy. khi đến ms thứ 25, P3 xin được chạy.
Vì hiện giờ cpu giành thời gian xử lý tiến trình P2, nên P3 vào hàng đợi, vá P1 đến trước nên P3 xếp sau.
khi P2 chạy được 20ms sẽ bị ngắt và đưa P1 vào. tiếp tục đến khi hoành tất các tiến trình.

cách này P3 sẽ bị xếp chờ lâu. nhưng trung bình thời gian chờ nhanh hơn 1 chút.

Giống nhau:

Được dùng trong đ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:

- Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.

- Non-Preemptive Scheduling: Có nghĩa là khi tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.

- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

NguyenCaoDuong(I22B) đã viết:

HoangThanhThien(I22B) đã viết:

AnhDao(I22B) đã viết:

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

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

Bài của bạn mình xin dc bổ sung như những j mình nge dc từ Thầy nhé :
+ 2 số 0 trong lệnh : ko học nên các bạn đường quan tâm nhé, bít cách nó làm như vậy thôi
+ số 0 trước số 4 : thể hiện giá trị được truyền cho hàm
+ số 4 : thể hiện luồng mới được tạo sẽ vận hành theo code , nó báo cho người sử dụng bít luồng này trong trạng thái ngủ, và chờ được đánh thức

Cám ơn bạn đã bổ sung nhé

Cám ơn hai bạn nhe. Có một số thứ Thầy giải thích nhanh quá mình không nghe kịp nhưng nhờ có 2 bạn diễn giải và bổ sung nên cũng bắt đầu hiểu một ít rồi. Thank hai bạn nhiều.

Không có gì bạn ơi cùng nhau phát triển

NguyenBacHoi(I22B) đã viết: Giống nhau:

Được dùng trong đ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:

- Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.

- Non-Preemptive Scheduling: Có nghĩa là khi tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.

- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

Khó hiễu một chút bạn à, mong bạn nói rõ đc ko

NguyenQuocHuy (I22B) đã viết:

HuynhDucQuang(I22B) đã viết:Hình hơi to, các bạn có thể open image in new tab.

cách chạy biểu đồ Gantt:
- Thời điểm 0-2: P1 chạy
- Thời điểm 2-4: P2 chạy vi khi đó P1 chạy được 2 còn 5 ( 7-2=5> P2 = 4)
- Thời điểm 4-5: P3 chạy vì P3 = 1 < P2 = ( 4-2=2)
- Sau đó P2 chạy tiếp vì P2=2< P4=4 < P1=5
- Rồi P4 chạy vì P4=4 < P1=5
Cuối cùng P1 chạy.

- P1 sẽ bắt đầu hoạt động tại giây thứ 0 nhưng mới
- P1 chạy được 2s thì P2 nhảy vào bắt đầu tiến trình của mình lúc này P1 sẽ tạm dừng lại để nhường CPU cho P2 (vì p2 có lượng CPU ít hơn P1 nên được ưu tiên dùng CPU)
=> Như vậy ở thời điểm giây thứ 4 P1 còn 5s để kết thúc tiến trình
- P2 chạy được 2s thì P3 nhảy vào bắt đầu tiến trinh của mình lúc này p2 sẽ tạm dừng để nhường CPU cho P3 (vì p3 có lượng CPU ít hơn P2 nên được ưu tiên dùng CPU)
=> Như vậy ở thời điểm giây thứ 4 P2 còn 2s nữa để kết thúc tiến trình
- P3 CPU =1 và hoàn tất tiến trình của mình ở giây thứ 5
=> P3 kết thúc tiến trình
- Tiếp theo CPU sẽ xem xét lượng CPU của tiến trình thấp nhất trong 3 tiến trình còn lại là P1=5, P2=2, P4=4 để đươc ưu tiên chạy trước, như vậy tiến trình P2=2 là thấp nhất sẽ được bắt đầu chạy tiếp tiến trình ở giây thứ 5 và hoàn tất ở giây thứ 7
=> P2 kết thúc tiến trình
- Tiếp theo CPU sẽ ưu tiên lượng sử dụng CPu thấp hơn trong 2 tiến trình P1=5 và P4=4 để ưu tiên bắt đầu chạy trước tiến trình, P4=4 thấp hơn P1=5 sẽ được ưu tiên chạy trước và kết thúc ở giây thứ 11
=> P4 kết thúc tiến trình
- Ở giây thứ 11 chỉ còn lại tiến trình P1=5 tiếp tục hoạt động và hoàn tất tiến trình của mình ở giây thứ 16
=> P1 kết thúc tiến trình

Biểu Đồ Gantt




Thời gian chờ trung bình:

T = [ ( 22 - 3 ) + 0 + ( 11 - 6 ) + ( 17 - 13 ) + ( 31 - 8 ) + 0 ] / 5
T = ( 19 + 0 + 5 + 4 + 23 ) / 5
T = 10,2 ms


_Bản chất của thuật giải SJFS 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 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ế.
_Với bài tập này thì tại thời điểm 0 xuất hiện tiến trình P1 thì P1 được chạy trước do ko có tiến trình nào nữa ở thời điểm 0.
_Tiến trình P1 chạy được 3ms thì xuất hiện tiến trình P2 và lúc này P1 đã chạy được 3ms và thời gian còn lại của nó là 9ms so với khoảng CPU kế tiếp của P2 là 8ms vậy P2 được ưu tiên chạy trước và HĐH bắt P1 phải dừng lại để P2 sử dụng CPU.
_P2 chạy được 3ms, tới thời điểm ms thứ 6 thì P3 xuất hiện, lúc này khoảng thời gian còn lại của P2 là 5 so với khoảng CPU kế tiếp của P3 là 7 vậy thời gian còn lại của P2 nhỏ hơn nên P2 được chạy tiếp.
_Đến ms thứ 8 thì P4 xuất hiện lúc này khoảng thời gian còn lại của P2 là 3ms so với khoảng CPU kế tiếp của P4 là 9ms vậy P2 có thời gian còn lại nhỏ hơn nên P2 chạy tiếp và đến ms thứ 11 thì P2 chạy xong tiến trình của nó.
_Bây giờ trong hàng đợi còn có P1=9ms, P3=7ms, P4=9ms vậy P3 có số ms nhỏ nhất nên P3 được ưu tiên chạy trước.
_P3 chạy được 2ms thì P5 xuất hiện. Lúc này thời gian còn lại của P3 là 5ms trong khi khoảng CPU kế tiếp của P5 là 4ms, nên lúc này P5 được ưu tiên chạy trước P3. Tại thời điểm này thì chưa thấy xuất hiện tiến trình nào khác nên HĐH sẽ sắp xếp thứ tự sử dụng CPU của P1=9ms, P3=5ms, P4=9ms, P5=4ms. Số ms của tiến trình nào nhỏ hơn sẽ được ưu tiên chạy trước, trong trường hợp này ta thấy P1=9ms và P4=9ms vậy HĐH sẽ chọn P1 chạy trước P4 vì P1 vào trước P4.
_Vậy thứ tự chạy tiếp theo sẽ là P5->P3->P1->P4

Thời gian chờ trung bình.
_Lúc đầu P1 được chạy trước nhưng do từ ms thứ 3 đến ms thứ 22 nó phải nhường CPU cho tiến trình khác nên thời gian chờ của P1 là 22-3.
_P2 vào từ ms thứ 3 và nó hoàn thành công việc của nó luôn mà ko chờ bất cứ 1 tiến trình nào hết nên thời gian chờ của nó là 0.
_P3 xuất hiện ở thời điểm ms thứ 6 nhưng mãi đến ms thứ 11 nó mới được sử dụng CPU nhưng sử dụng được 2ms thì nó lại phải nhường CPU cho P5 ở ms thứ 13 và mãi đến ms thứ 17 nó mới được chạy tiếp đến ms thứ 22 nó mới hoàn thành công việc của nó vậy tổng thời gian chờ của P3 sẽ là:
(11-6) + (17-13)
_P4 xuất hiện ở ms thứ 8 nhưng mãi đến ms thứ 31 nó mới được chạy vậy thời gian chờ của P4 sẽ là : 31-8.
_P5 xuất hiện ở ms thứ 13 và khi xuất hiện nó chạy ngay mà không chờ bất cứ 1 tiến trình nào hết nên thời gian chờ của nó là 0.
Vậy thời gian chờ trung bình = tổng thời gian chờ của từng tiến trình chia cho số tiến trình.
VD:

Ở thời điểm 0h ta nấu nồi khoai lan(thời gian nấu là 60 phút), nấu được 15 phút ta muốn ăn cơm (thời gian nấu của nồi cơm là 30 phút) và ta cho nồi khoai lan xuống và bắt nồi cơm lên, nấu cơm được 1 phút bổng nhiên ta muốn nấu nước để đi tắm(thời gian nấu nước là 10 phút) và thế là ta bắt nồi cơm xuống và bắt ấm nước lên, sau 10 phút ấm nước đã sôi ta bắt ấm nước xuống và bắt nồi cơm lên, nồi cơm đã nấu được 1 phút rồi và giờ chỉ cần nấu thêm 29 phút nữa là cơm chính và khi cơm chính ta cho nồi cơm xuống và bắt nồi khoai lan lên nấu tiếp 45 phút nữa là xong.

Các bạn tham khảo và góp ý dùm mình bài này nha. Thank

NguyenCaoTri (I22B) đã viết:Một hệ thống có 5 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 FJFS (có tiếm quyền) để đ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.




T1=(12-2) + (1-1) = 10
T2= 0
T3 = (5-4) + (2-2) = 1
T4 = 0
T5= 6-5= 1

Ttb= (10 +0 +1 +0 +1)/5 = 12/5 =2,4ms

Mong Thầy và các bạn cho ý kiến

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

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




Sử dụng thuật giải RRS với thời lượng = 20ms

Biểu đồ Gantt:




Thời gian chờ trung bình:[ 57 + 15 + ( 17 + 33 + 4 ) + ( 27 + 33 ) ] / 4 = 46,5ms

Giải thích:
_Thời điểm 0 P1 xuất hiện và sử dụng CPU . Sau 20ms vẫn chỉ có P1 trong hàng đợi nên P1 tiếp tục được sử dụng CPU.
_Đến ms thứ 25 thì P2 xuất hiện và đến ms 40 thì P3 xuất hiện nhưng vì P2 đến trước nên ưu tiên thực hiện P2, nên đến ms 40 thì P1 phải nhường CPU cho P2. P2 chỉ sử dụng CPU có 17ms là xong công việc.
_Sau khi P2 thực hiện xong công việc ở ms thứ 57 thì P4 cũng đã xuất hiện trong hàng đợi nhưng vì P3 đến trước nên P4 phải sử dụng CPU sau khi P3 đã sử dụng qua 1 lượt. Vì thế từ ms thứ 57 P3 sử dụng CPU đến ms 77 thì nhường CPU lại cho P4.
_P4 sử dụng CPU từ ms 77 đến ms 97 sau đó P4 trả CPU lại cho P1 thực hiện tiếp quá trình của nó. Lúc này P1 tiếp tục sử dụng CPU từ ms 97 đến ms 110 sau đó trả CPU cho P3 sử dụng. Vì P2 đã thực hiện xong công việc của nó nên ta ko xét nó ở đây nữa.
_P3 sử dụng CPU từ ms 110 đến ms 130 thì đến P4 sử dụng từ ms 130 đến ms 134 rồi trả CPU lại cho P3. Vì P1 đã xong công việc của nó và bây giờ chỉ còn lại P3 và P3 sử dụng CPU để giải quyết toàn bộ công việc của nó.

Cái này mình tự thêm vào thời gian xuất hiện của các tiến trình mong Thầy và các bạn cho ý kiến. Thank