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

vutanthanh68 (113A) đã viết:

NguyenThiNgocPhuong(113A) đã viết:

vutanthanh68 (113A) đã viết:

NguyenThiNgocPhuong(113A) đã viết:

vutanthanh68 (113A) đã viết:

LeLamThang (113A) đã viết:Đề bài: 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	25
P2	20	15
P3	30	10

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 đồi Gantt.
b. Tính thời gian 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

5

15

25

35

40

50

55

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 = (40  -  5) - 25= 10 ms
        P2 = (55  -  20) - 15= 20 ms
        P3 = (50  -  30) - 10= 10 ms

 ==> Thời gian chờ trung bình  = (10 + 20 + 10)/3=13.3 ms

Thầy và các bạn giải thích dùm mình với.theo như ví dụ trong giáo trình,thì người ta làm lần lượt từ
p1 -> p4.xong mới quay về p1,nhưng ví dụ này thì lại không như thế.đáng lẽ thời điểm số 35 thì p3 phải chạy chứ.sao p1 lại chạy tiếp thế

Chào bạn vutanthanh68 (113A).

Theo như trong giáo trình của thầy có viết: Mỗi tiến trình được cấp một thời lượng CPU (Time QuanTum) thường từ 10-100 mili giây. Sau khoảng thời gian này nó sẽ 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.

Đối với bài tập bạn hỏi:
- Ở mili giây thứ 5 có tiến trình P1 đến .
- P1 thực hiện 10 ms , sau khi P1 thực hiện 10 ms vẫn chưa có tiến trình nào đến nên P1 thực hiện tiếp 10 ms tiếp theo.
- Đến mili giây thứ 20 có P2 đến nhưng P1 chưa thực hiện hết 10ms nên đưa P2 vào hàng chờ Ready.
- P1 thực hiện xong 10 ms tiếp theo đó thì P2 tiếm quyền để thực hiện 10 ms và đưa P1 vào hàng chờ Ready.
- Trong thời gian P2 thực hiện 10 ms, ở thời điểm 30 ms thì P3 đến nên đưa P3 vào cuối hàng chờ Ready (đưa P3 vào hàng chờ Ready đứng sau P1 ).
- Sau khi P2 thực hiện xong 10 ms thì P1 tiếm quyền P2. Đưa P2 vào cuối hàng chờ Ready và P1 thực hiện 5 ms còn lại (vì P1 vào hàng chờ Ready trước P3 nên P1 thực hiện trước).
- Sau khi P1 thực hiện xong 5ms còn lại thì đến P3 thực hiện 10 ms.
- P3 thực hiện xong đến P2.

nếu quay lại hàng chờ ready.dựa vào yếu tố gì.mà ta bắt P3 đứng sau P1;theo giáo trình là đưa vào cuối hàng chờ ready.thì phài đứng sau P3 chứ

Chào bạn vutanthanh68,
Ở thời điểm mili giây 25, P1 bị tiếm quyền và đưa vào hàng chờ Ready. Trong khi lúc này P3 chưa đến và chưa được đưa vào hàng chờ Ready.
Đến mili giây 30 thì P3 đến nên P3 được đưa vào hàng chờ Ready. Lúc này P3 được đưa vào cuối hàng chờ Ready (nghĩa là sau P1 vì P1 đã được đưa vào hàng chờ Ready ở mili giây thứ 25 rồi).

thanks bạn nha.bạn pro quá.hem nào gặp cho minh xin chữ kí nhé.

Cùng nhau trao đổi học tập thôi bạn ơi. Ai có kinh nghiệm gì chia sẻ lẫn nhau.
Thầy tạo ra diễn đàn để chúng ta trao đổi học tập mà.
Mình giải thích có gì thiếu sót hay chưa đúng mong thầy và các bạn góp ý giúp mình.

LeHuynhChiTam (113A) đã viết:

bạn cho mình hỏi cách vẽ biểu đồ dựa vào cách giải mới này với , thanks bạn

TranVanTy(113A) đã viết:

LamVuThai (113A) đã viết:

Dùng giải thuật Round - Robin với thời lượng 10ms để điều phối CPU
a. Thể hiện bằng biểu đồ Gantt
b. Tính thời gian chờ trung bình của các tiến trình

Giải

- Vẽ biểu đồ:


- Tính thời gian trung bình :

P1 = (23 - 13) + (53 - 33) + (67 - 63) = 34
P2 = (13 -10) + (33- 23) = 13
P3 = (43- 24) + (63 - 53) = 29

===> TGTB = (34 + 13 + 29) / 3 = 25.33 ms

Bạn xem cách giải này có được ko ?
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)

công thức tính time chờ của các tiến trình:

P=(thời điểm kết thúc - thời điểm bắt đầu) - khoảng CPU

các bạn áp dụng y chang sẽ ra thôi !!!

LeHuynhChiTam (113A) đã viết:

Cảm ơn bạn, bài giải rất chi tiết , dễ hiểu.

phamanhtuan95(113A) đã viết:

LeHuynhChiTam (113A) đã viết:

bạn cho mình hỏi cách vẽ biểu đồ dựa vào cách giải mới này với , thanks bạn

Bảng này mình lập trong lúc vẽ biểu đồ Gantt luôn bạn ơi

Cảm ơn các bạn, bài viết của các bạn thật là chi tiết, nhờ có diễn đàn mà mình nắm vững kiến thức còn thiếu trong lúc học

Round-robin (RR) là thuật toán lập chương trình (danh mục) cho các tiến trình trong hệ điều hành, được thiết kế đặc biệt cho hệ thống chia sẻ thời gian.
Tương tự như thuật giải FCFS (First-Come First-Served Scheduling) nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các tiến trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time slice) được định nghĩa.
Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi (ở trạng thái sẳn sàng) được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi, cấp phát CPU tới mỗi tiến trình có khoảng thời gian tối đa bằng một định mức thời gian.
Để cài đặt RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi FIFO của các tiến trình. Các tiến trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn tiến trình đầu tiên từ hàng đợi, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gởi tới tiến trình.
Sau đó, một trong hai trường hợp sẽ xảy ra. Tiến trình có 1 chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, tiến trình sẽ tự giải phóng. Sau đó, bộ định thời biểu sẽ xử lý tiến trình tiếp theo trong hàng đợi. Ngược lại, nếu chu kỳ CPU của tiến trình đang chạy dài hơn 1 định mức thời gian thì bộ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và tiến trình được đặt trở lại tại đuôi của hàng đợi. Sau đó, bộ định thời biểu CPU sẽ chọn tiến trình tiếp theo trong hàng đợi.

Nguyên tắc : Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuât điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng
Hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết
Thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng đơi được cấp CPU trong lượt kế tiếp
Ví dụ:

Tiến trình Thời gian đến Khoảng CPU
P1 0 24
P2 1 3
P3 2 3

Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là :
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26,30
Thời gian chờ trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes.
Nếu có n tiến trìh trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ được cấp phát CPU 1/n trong tổng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)đơn vị thời gian trước khi nhận được CPU cho lượt kế tiếp.

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

Mục đích:
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 đó.

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

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

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.

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

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

1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số tiến trình (TT) hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

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.

Bốn tình huống ra quyết định của trình điều phối CPU:
* Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (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 có tiếm quyền(Preemptive Scheduling) và điều phối không tiếm quyền (Non-Preemptive Scheduling)
+ Có tiếm quyền: Điều phối chỉ xảy ra ở thời điểm 1 va 4, không xảy ra điều phối ở thời điểm 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. Trên HĐH hiện đại đa số có tiếm quyền.
+ Không tiếm quyền: Xảy ra trong cả 4 tình huống. Có thể buộc tiến trình đang chạy trả CPU.

việc tiếm quyền trong RRS có sự khác biệt so với Preemptive-SJFS cho nên từ trước tới nay khi nói đến RRS mình rất ít dùng từ "tiếm quyền" mà chỉ quan tâm nhiều nhất đến Ready Queue

_ Vậy tiếm quyền trong RRS & Preemptive-SJFS khác nhau thế nào, chúng ta sẽ so sánh để thấy rõ được vấn đề :

-Round Robin
Khi có 1 tiến trình đến...Tiến trình vừa đến được đưa vào cuối Ready Queue cho dù tiến trình đang thực thi đã hết Time Quantum hay chưa
Xét tiến trình được thực thi kế tiếp, theo... Nội dung của Ready Queue
-Preemptive-SJFS

- Khi có tiến trình mới đến (được khởi tạo), bao giờ cũng được xếp vào Ready Queue. Tiếp theo, trình điều phối (CPU Scheduler) dùng Preemptive SJFS sẽ xét các khoảng CPU (với tiến trình đang Running, tính xem thời gian còn lại của nó là bao nhiêu) để chọn tiến trình phù hợp.
_ Theo bảng so sánh ta thấy rõ một điều, đối với RRS khi một tiến trình mới đến, nó hiển nhiên được đưa vào cuối hàng chờ (Ready Queue) mà không cần quan tâm CPU-Burst của nó hay tiến trình hiện tại đã thực hiện hết Time Quantum hay chưa. Ngược lại đối với Preemptive-SJFS, khi một tiến trình mới đến nếu CPU-Burst của nó là nhỏ nhất(so với tiến trình hiện tại và tất cả các tiến trình đã đến trước đó) thì nó được phép thực thi ngay lập tức.

Ví dụ:

Tiến trình	Thời điểm	CPU - Burst (ms)
P1	3	37
P2	10	20
P3	24	14

Dùng giải thuật Round - Robin với thời lượng 10ms để điều phối CPU
a. Thể hiện bằng biểu đồ Gantt
b. Tính thời gian chờ trung bình của các tiến trình
(mình đã có chỉnh sửa lại đề so với ban đầu mình đã post )
Giải
BIỂU ĐỒ GANTT:
- Điểm lưu ý khi vẽ:
+ Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum) là số q ms nào đó.
+ Hết thời gian q, thì tiến trình hiện tại sẽ bị tiến trình khác tiếm quyền nếu tiến trình mới này có thời điểm đến = hoặc < thời điểm đang xét. Đồng thời tiến trình cũ sẽ được đưa vào hàng đợi Ready
+ Tiến trình đầu tiên trong hàng đợi sẽ được chọn để tiếm quyền kế tiếp
- Vẽ biểu đồ:

- Giải thích:
(lưu ý với thuật toán này mình nhớ xem xét thời điểm đề cho là thời điểm đến của các tiến trình)
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ẽ hok 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
Dựa vào biểu đồ Gantt ta tính thời gian chờ trung bình

THỜI GIAN CHỜ TRUNG BÌNH
Ttb = (T1 + T2 +...+ Tn)/n
(thời gian chờ của mỗi tiến trình = tổng thời gian tiến trình đó bị gián đoạn)

T1 = (3 -3)+ (23 - 13) + (53 - 33) + (67 - 63) = 34
T2 = (13 -10) + (33- 23) = 13
T3 = (43- 24) + (63 - 53) = 29

===> Ttb = (34 + 13 + 29) / 3 = 25.33 ms

NguyenThiNgocPhuong(113A) đã viết:

vutanthanh68 (113A) đã viết:

LeLamThang (113A) đã viết:Đề bài: 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	25
P2	20	15
P3	30	10

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 đồi Gantt.
b. Tính thời gian 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

5

15

25

35

40

50

55

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 = (40  -  5) - 25= 10 ms
        P2 = (55  -  20) - 15= 20 ms
        P3 = (50  -  30) - 10= 10 ms

 ==> Thời gian chờ trung bình  = (10 + 20 + 10)/3=13.3 ms

Thầy và các bạn giải thích dùm mình với.theo như ví dụ trong giáo trình,thì người ta làm lần lượt từ
p1 -> p4.xong mới quay về p1,nhưng ví dụ này thì lại không như thế.đáng lẽ thời điểm số 35 thì p3 phải chạy chứ.sao p1 lại chạy tiếp thế

Chào bạn vutanthanh68 (113A).

Theo như trong giáo trình của thầy có viết: Mỗi tiến trình được cấp một thời lượng CPU (Time QuanTum) thường từ 10-100 mili giây. Sau khoảng thời gian này nó sẽ 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.

Đối với bài tập bạn hỏi:
- Ở mili giây thứ 5 có tiến trình P1 đến .
- P1 thực hiện 10 ms , sau khi P1 thực hiện 10 ms vẫn chưa có tiến trình nào đến nên P1 thực hiện tiếp 10 ms tiếp theo.
- Đến mili giây thứ 20 có P2 đến nhưng P1 chưa thực hiện hết 10ms nên đưa P2 vào hàng chờ Ready.
- P1 thực hiện xong 10 ms tiếp theo đó thì P2 tiếm quyền để thực hiện 10 ms và đưa P1 vào hàng chờ Ready.
- Trong thời gian P2 thực hiện 10 ms, ở thời điểm 30 ms thì P3 đến nên đưa P3 vào cuối hàng chờ Ready (đưa P3 vào hàng chờ Ready đứng sau P1 ).
- Sau khi P2 thực hiện xong 10 ms thì P1 tiếm quyền P2. Đưa P2 vào cuối hàng chờ Ready và P1 thực hiện 5 ms còn lại (vì P1 vào hàng chờ Ready trước P3 nên P1 thực hiện trước).
- Sau khi P1 thực hiện xong 5ms còn lại thì đến P3 thực hiện 10 ms.
- P3 thực hiện xong đến P2.

sau những lời giải thích bây giờ mình đã hiểu

mình đồng ý với cách giải thích này cua lop trưởng

có bạn nào trình bày cách khác không ??

Khi P1 chạy từ 6-26,thì co P2 xuất hiện (thoi điểm 17),trong hàng chờ lúc này co P2.Khi P1 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P1 đưoc đưa và hàng chờ (chỉ co P1 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)

Khi P2 chạy từ 26-46,trong hàng chờ lúc này co P1.Khi P2 chạy hết thoi lưong 20ms thì P1 sẽ chạy và P2 đưoc đưa và hàng chờ (chỉ co P2 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)
Khi P1 chạy từ 46-52,trong hàng chờ lúc này co P2 và P3.Khi P1 chạy xong thì P2 sẽ chạy vì P2 đứng o đầu hàng đoị,kết thúc P1
Khi P2 chạy từ 52-72,trong hàng chờ lúc này co P3.Khi P2 chạy hết thoi lưong 20ms thì P3 sẽ chạy và P2 đưoc đưa và hàng chờ
Khi P3 chạy từ 72-92,trong hàng chờ lúc này co P2.Khi P3 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P3 đưoc đưa và hàng chờ
Tại thoi điểm 92-97,P2 chạy xong
Tại thoi điểm 97-106,P3 chạy xong

Có cần phải giải thích dài dòng không hay chỉ làm ngắn gọn như thầy thôi

TranThiHuyenTrang(113A) đã viết:

Khi P1 chạy từ 6-26,thì co P2 xuất hiện (thoi điểm 17),trong hàng chờ lúc này co P2.Khi P1 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P1 đưoc đưa và hàng chờ (chỉ co P1 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)

Khi P2 chạy từ 26-46,trong hàng chờ lúc này co P1.Khi P2 chạy hết thoi lưong 20ms thì P1 sẽ chạy và P2 đưoc đưa và hàng chờ (chỉ co P2 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)
Khi P1 chạy từ 46-52,trong hàng chờ lúc này co P2 và P3.Khi P1 chạy xong thì P2 sẽ chạy vì P2 đứng o đầu hàng đoị,kết thúc P1
Khi P2 chạy từ 52-72,trong hàng chờ lúc này co P3.Khi P2 chạy hết thoi lưong 20ms thì P3 sẽ chạy và P2 đưoc đưa và hàng chờ
Khi P3 chạy từ 72-92,trong hàng chờ lúc này co P2.Khi P3 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P3 đưoc đưa và hàng chờ
Tại thoi điểm 92-97,P2 chạy xong
Tại thoi điểm 97-106,P3 chạy xong

LeHuynhChiTam (113A) đã viết:

Biểu đồ cần phải mang tính chính xác, tuy không thể chính xác nhưng cũng phải mang tính tương đối. Bạn nên điểu chỉnh độ dài đoạn 50 55 ngắn lại cho chính xác!

nguyenlehuutai(113A) đã viết:Có cần phải giải thích dài dòng không hay chỉ làm ngắn gọn như thầy thôi

TranThiHuyenTrang(113A) đã viết:

Khi P1 chạy từ 6-26,thì co P2 xuất hiện (thoi điểm 17),trong hàng chờ lúc này co P2.Khi P1 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P1 đưoc đưa và hàng chờ (chỉ co P1 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)

Khi P2 chạy từ 26-46,trong hàng chờ lúc này co P1.Khi P2 chạy hết thoi lưong 20ms thì P1 sẽ chạy và P2 đưoc đưa và hàng chờ (chỉ co P2 trong hàng chờ vì toi thoi điểm 48, P3 moi xuất hiện)
Khi P1 chạy từ 46-52,trong hàng chờ lúc này co P2 và P3.Khi P1 chạy xong thì P2 sẽ chạy vì P2 đứng o đầu hàng đoị,kết thúc P1
Khi P2 chạy từ 52-72,trong hàng chờ lúc này co P3.Khi P2 chạy hết thoi lưong 20ms thì P3 sẽ chạy và P2 đưoc đưa và hàng chờ
Khi P3 chạy từ 72-92,trong hàng chờ lúc này co P2.Khi P3 chạy hết thoi lưong 20ms thì P2 sẽ chạy và P3 đưoc đưa và hàng chờ
Tại thoi điểm 92-97,P2 chạy xong
Tại thoi điểm 97-106,P3 chạy xong

Theo mình biết thì không cần giải thích như này đâu..chỉ cần vẽ biểu đồ Gantt với tính giái trị trung bình thôi.