Thảo luận Bài 6

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

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

Bài Tập Điều phối CPU (Preemptive SJFS)

Bài gửi  NguyenThiHongYen(I12A) on 5/4/2012, 00:18

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

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

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



Hình đầy đủ:
CLICK VÀO ĐÂY


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

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

Thời gian chờ của P1 = (47-5) -22=20
Thời gian chờ của P2 = (25-10) -15 =0
Thời gian chờ của P3 = (30-20) -5=5

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

NguyenThiHongYen(I12A)

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

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

Về Đầu Trang Go down

Các bài tập về đa luồng

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

HANDLE ProducerHandle[100 ] ;
HANDLE ConsumerHandle[100 ] ;
DWORD ProducerID; // cấp ID cho sản phẩm được tạo mới
DWORD ConsumerID;
for ( int i = 0 ; i < 30 ; i ++)
{
ProducerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Producer, 0, 4, &ProducerID);
ConsumerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Consumer, 0, 0, &ConsumerID);
}
// 2. Đánh thức các luồng
for ( int i = 0 ; i < 30 ; i ++)
{
ResumeThread ( ProducerHandle[ i ] );
ResumeThread ( ConsumerHandle[ i ] ); // đối với các tập luồng ConsumerHandle[ i ] này sau khi khởi tạo sẽ chạy ngay
}
// 3. Tạm ngừng
for ( int i = 0 ; i < 30 ; i ++)
{
SuspendThread(ProducerHandle[ i ]);
SuspendThread(ConsumerHandle[ i ]);
}

Admin
- Giải đúng !
- Hay hơn: Cỡ của các mảng ProducerHandle và ConsumerHandle là 30 (của em "dự phòng" tới 100, nên hơi "tốn" RAM). Mặt khác, ProducerID và ConsumerID cũng nên là các biến mảng !


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

tranvanthien27(I12C)

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

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

Về Đầu Trang Go down

Bài tập về thuật giải Preemptive SJFS

Bài gửi  LeThiMaiPhuongI12A on 5/4/2012, 00:34

Tiến trình Thời điểm đến(ms) CPU-Burst
P15 22
P2 10 15
P3 20 5
Dùng thuật giải Preemptive SJFS để điều phối CPU
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời điểm chờ trung bình của các tiến trình

a.Biểu đồ Gantt.

Tại thời điểm 5ms P1 sẽ được cấp CPU đầu tiên
Tại thời điểm 10ms,P2 đến, do khoảng CPU của P2 nhỏ hơn P1 nên P2 tiếm quyền P1, lúc này CPU được cấp cho P2, và P2 sẽ chạy hết khoảng CPU của nó
Tại thời điểm 25ms, P3 sẽ được cấp CPU vì P3 có khoảng CPU nhỏ hơn P1
Tại thời điểm 30ms P1 sẽ thực hiện tiếp khoảng CPU còn lại của nó
b.Tính thời điểm chờ trung bình của các tiến trình
P1=(47-5)-22=42-22=20ms
P2=(25-10)-15=15-15=0ms
P3=(30-20)-5=10-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8,3ms
Các bạn bổ sung thêm nha

LeThiMaiPhuongI12A

Tổng số bài gửi : 12
Join date : 15/02/2012
Age : 27
Đến từ : Long An

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

Về Đầu Trang Go down

CÁC THUẬT GIẢI ĐIỀU PHỐI CPU (Scheduling Algorithms) !~!~!~!~!~!~!~!

Bài gửi  HoNgocTuan142(I12A) on 5/4/2012, 01:22

Trong bài này mình xin phép giải thích về các thuật giải điều phối CPU, vì đây là một phần rất quan trọng trong nội dung môn học và nhất là chiếm 2 điểm trong bài thi. afro
vì hơi lười nên mình soạn trong Word rồi chụp hình nên các bạn thông cảm Razz

1. Thuật giải đến trước – phục vụ trước FCFS (First come – First Served Scheduling):

- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=0
P2=(24-1)=23
P3=(27-2)=25
Thời gian chờ trung bình: (0+23+25)/3=16 ms
2. Giải thuật ngắn hơn chạy trước SJFS (Shortest Job First Scheduling) không tiếm quyền (Non-Preemptive):

- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=0
P2=(8-2)=6
P3=(7-4)=3
P4=(12-6)=6
Thời gian chờ trung bình: (0+6+3+6)/4=3.75 ms
CHÚ Ý PHẦN QUAN TRỌNG (100% RA THI) lol! lol! lol! lol!

3. Giải thuật ngắn hơn chạy trước SJFS (Shortest Job First Scheduling) có tiếm quyền (Preemptive):

Giải thích:
1) Tại thời điểm 5ms tiến trình P1 (CPU-Burst=22ms) xuất hiện, tiến trình P1 thực thi được khoảng 5ms thì tiến trình P2 (CPU-Burst=15ms) đến.
2) Tiến trình P1 phải nhường CPU lại cho tiến trình P2 (nghĩa là tiến trình P1 còn lại 17ms chưa được thực thi), tiến trình P2 thực thi được 15ms thì tiến trình P3 (CPU-Burst=5ms) đến (nghĩa là P2 còn 5ms chưa được thực thi) lúc này CPU-Burst của P2 còn lại và CPU-Burst của P3 bằng nhau và bé hơn CPU-Burst của P1, nên tiến trình nào nhỏ hơn và đến trước thì làm trước.
3) Tiến trình P2 làm tiếp 5ms còn lại.
4) CPU được nhường cho tiến trình P3 (CPU-Burst=5ms). Sau khi tiến trình P3 thực thi xong thì không có tiến trình nào tới nữa. quay lại thực hiện tiếp tiến trình P1 (còn 17ms).
5) Sơ đồ Gantt hoàng chỉnh cho bài toán trên.
- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=(17-5)-22=20
P2=(25-10)-15=0ms
P3=(30-20)-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8.33ms


Được sửa bởi HoNgocTuan142(I12A) ngày 5/4/2012, 17:26; sửa lần 1.
avatar
HoNgocTuan142(I12A)

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

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

Về Đầu Trang Go down

Bài Tập 1 (Về đa luồng)

Bài gửi  maidangvu_I12A on 5/4/2012, 01:31

Lập trình bằng Visual C++ 6.0, để tạo tập luồng gồm 30 luồng sản xuất và 30 luồng tiêu thụ
Code:
#include <stdio.h>
#include <conio.h>
#include <windows.h>

int count_Producer;
int count_Consumer;

void Producer()  //Luồng phụ sản xuất
{
   while(1)
   {
      count_Producer++;
      Sleep(1000);  //Nghỉ 1000ms = 1 giây
   }
}
void Consumer()    //Luồng phụ tiêu thụ
{
   while(1)
   {
      count_Consumer++;
      Sleep(1000);  //Nghỉ 1000ms = 1 giây
   }
}

void main()
{
   HANDLE ProducerHandle[30];  //Mảng gồm 30 phần tử chứa mục quản của các luồng sản xuất
   HANDLE ConsumerHandle[30];  //Mảng gồm 30 phần tử chứa mục quản của các luồng tiêu thụ
   DWORD ProducerID[30];  //Mảng gồm 30 phần tử chứa ID của các luồng sản xuất
   DWORD ConsumerID[30];  //Mảng gồm 30 phần tử chứa ID của các luồng tiêu thụ
   count_Producer=0;
   count_Consumer=0;
  //Vòng lặp để tạo tuần tự các luồng sản xuất và các luồng tiêu thụ
   for(int i=0;i<30;i++)
   {
      //Tạo luồng Sản xuất thứ i trong trạng thái ngủ
      ProducerHandle[i]=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0,4,&ProducerID[i]);
      //Tạo luồng Tiêu thụ thứ i trong trạng thái ngủ
      ConsumerHandle[i]=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0,4,&ConsumerID[i]);
   }
}


Được sửa bởi maidangvu_I12A ngày 5/4/2012, 02:05; sửa lần 1.

maidangvu_I12A

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

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

Về Đầu Trang Go down

Cùng chung thắc mắc về bài tập thuật giải Round Robin

Bài gửi  TaThucCuongI12C on 5/4/2012, 01:35

Mình cũng chưa hiểu bài tập về thuật giải "Round Robin" mà bạn HuynhMinhChanh(i91C) và bạn LeQuocKhanh-11H1010059 đang thắc mắc.

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


Nếu theo lý thuyết trong slide thì :
Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 milli 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.

Vậy sau khi P2 tiếm quyền P1 thì P3 sẽ tiếm quyền P2. Nhưng bài giải lại là P1 tiếm quyền P2 trước P3??? Shocked

Với 1 bài khác và theo cách giải thích của bạn PhamQuangHien_I12A thì:


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

Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 3 35
P2 10 20
P3 25 15

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

A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuyển qua tiến trình khác.ở đây là các tiến trình p1,p2,p3



Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)

Nếu sử dụng cách giải thích này cho bài đầu thì cũng không đúng vì P3 ở bài đầu đang chờ ở thời điểm 20 nên đáng lý phải được tiếm quyền trước P1 Sad

Vậy thuật giải này phải giải thích thế nào mới chính xác Question Bạn nào biết giải thích cho mọi người cùng hiểu với. Thanks nhiều!!! scratch scratch scratch



Được sửa bởi TaThucCuongI12C ngày 5/4/2012, 01:55; sửa lần 1.

TaThucCuongI12C

Tổng số bài gửi : 13
Join date : 15/02/2012
Age : 29
Đến từ : I12A

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  TaThucCuongI12C on 5/4/2012, 01:53

HoNgocTuan142(I12A) đã viết:Trong bài này mình xin phép giải thích về các thuật giải điều phối CPU, vì đây là một phần rất quan trọng trong nội dung môn học và nhất là chiếm 2 điểm trong bài thi. afro
vì hơi lười nên mình soạn trong Word rồi chụp hình nên các bạn thông cảm Razz


Theo mình thấy ở bài vòng Robin có lẽ thầy cố ý làm sai chỗ này (Thầy chơi gài bẫy Suspect Suspect Suspect ):
thay mình hiểu là làm P1->P2->P3 rồi quay lại P1->P2->(P3 xong) quay lại ->P1...
thầy lại để P1->P2->P1 rồi mới tới P3->P2->P1
có phải vậy không?? các bạn cho ý kiến nha. Sleep Sleep Sleep Sleep Sleep Sleep Sleep Sleep
nếu hình ảnh có vấn đề các bạn vào download luôn file Word của mình up lên
http://www.mediafire.com/?917krfzt6qgrt7x

Thanks bạn vì bài viết chất lượng. Nhưng nếu cách giải thích của bạn về bài Round Robin là đúng thì bài của bạn PhamQuangHien_I12A giải sai chăng???

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

Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 3 35
P2 10 20
P3 25 15

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

A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuyển qua tiến trình khác.ở đây là các tiến trình p1,p2,p3



Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)

Còn nếu cả 2 bài đều đúng thì chắc hẳn bài giải trên lớp của thầy có vấn đề. Có lẽ thầy "cố tình bẫy" xem các bạn có phát hiện không? Vì mình và vài bạn cũng thắc mắc bài này nhưng thầy nói lên forum thảo luận để bữa sau thầy giải thích. Hixxhixx Rolling Eyes

TaThucCuongI12C

Tổng số bài gửi : 13
Join date : 15/02/2012
Age : 29
Đến từ : I12A

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

Về Đầu Trang Go down

Re: TaThucCuongI12C

Bài gửi  maidangvu_I12A on 5/4/2012, 02:16

TaThucCuongI12C đã viết:
HoNgocTuan142(I12A) đã viết:Trong bài này mình xin phép giải thích về các thuật giải điều phối CPU, vì đây là một phần rất quan trọng trong nội dung môn học và nhất là chiếm 2 điểm trong bài thi. afro
vì hơi lười nên mình soạn trong Word rồi chụp hình nên các bạn thông cảm Razz


Theo mình thấy ở bài vòng Robin có lẽ thầy cố ý làm sai chỗ này (Thầy chơi gài bẫy Suspect Suspect Suspect ):
thay mình hiểu là làm P1->P2->P3 rồi quay lại P1->P2->(P3 xong) quay lại ->P1...
thầy lại để P1->P2->P1 rồi mới tới P3->P2->P1
có phải vậy không?? các bạn cho ý kiến nha. Sleep Sleep Sleep Sleep Sleep Sleep Sleep Sleep
nếu hình ảnh có vấn đề các bạn vào download luôn file Word của mình up lên
http://www.mediafire.com/?917krfzt6qgrt7x

Thanks bạn vì bài viết chất lượng. Nhưng nếu cách giải thích của bạn về bài Round Robin là đúng thì bài của bạn PhamQuangHien_I12A giải sai chăng???

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

Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 3 35
P2 10 20
P3 25 15

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

A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuyển qua tiến trình khác.ở đây là các tiến trình p1,p2,p3



Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)

Còn nếu cả 2 bài đều đúng thì chắc hẳn bài giải trên lớp của thầy có vấn đề. Có lẽ thầy "cố tình bẫy" xem các bạn có phát hiện không? Vì mình và vài bạn cũng thắc mắc bài này nhưng thầy nói lên forum thảo luận để bữa sau thầy giải thích. Hixxhixx Rolling Eyes
Bạn có thể tham khảo cách giải thích của mình về thuật giải Round- Robin và góp ý cho mình.
http://hedieuhanh.forumvi.net/t4338p60-topic#19789

maidangvu_I12A

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

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

Về Đầu Trang Go down

Giải thuật Round-robin

Bài gửi  nguyenthingocmai_I12A on 5/4/2012, 07:55

Theo mình hểu bài giải của thầy là đúng vì:
- Ví dụ trong slide bài giảng không có thời điểm đến chính vì vậy mà tất cả các tiến trình đều được hiểu thời điểm đến xuất phát từ 0.
- Bài tập trong đề thi của thầy thì có thời điểm đến cho mỗi tiến trình chính vì vậy mà bài giải của thầy không sai. Tại thời điểm P2 tiếm quyền P1 thì lúc này P1 được đẩy về cuối hàng đợi Ready. Nhưng các bạn chú ý tại thời điểm P2 tiếm quyền P1 thì lúc này P3 vẫn chưa có mặt (dựa vào thời điểm đến để xác định sự có mặt và chưa có mặt). Chính vì vậy mà P1 được xếp sau P2 theo vòng Robin, Hàng chờ Ready là P2, P1. Sau thời lượng 10ms của tiến trình P2 thì theo vòng Robin thì P1 tiếm quyền và vào thời điểm đó thì P3 đã có mặt trong hàng chờ. Vậy nên P2 được xếp sau P3. Và lúc này hàng chờ Ready là P1, P3, P2. Cứ thế tiếp tục là giống bài giải của thầy.
Đó là cách hiểu của mình mong thầy và các bạn cho ý kiến nếu mình hiểu sai.

Admin
Em hiểu đúng !

nguyenthingocmai_I12A

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

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

Về Đầu Trang Go down

Phân biệt thuật giải MFQS và MQS? Vì dụ mình hoa từ đời thường?

Bài gửi  nguyenthingocmai_I12A on 5/4/2012, 08:18

MFQS( Multilevel Feedback Queue Scheduling): điều phối hàng chờ nhiều mức có điều tiết.
MQS( Multilevel Queue Scheduling): điều phối hàng chờ nhiều mức.
Giống nhau: MFQS và MQS cùng có nhiều hàng đợi Ready và mỗi hàng đợi có nhiều độ ưu tiên.
Khác nhau:
- MFQS: có độ uyển chuyển hơn, có thể điều tiết hàng đợi Ready theo mứa độ ưu tiên khác nhau.
- MQS: không có độ uyển chuyển, khi tiến trình nào đó đã được đặt vào mức độ ưu tiên nào rồi thì nó sẽ cố định tại mức đó không thể thay đổi được.
VD: Quy trình bán vé ga tàu: có 5 cửa bán vé
- MQS: 5 cửa bán vé đó mỗi cửa đó có 1 độ ưu tiên khác nhau. Tại mỗi cửa có 1 lượng khách theo độ ưu tiên đó. Ví dụ tại cửa số 1 có nhiều khách mà cửa số 5 có ít khách thì MQS vẫn không điều tiết để đẩy một ít khách qua cho cửa số 5 để giảm tải công việc cho cửa số 1.
- MFQS: cũng ví dụ như trên nhưng MFQS sẽ điều phối khách của cửa 1 di chuyển qua cửa 5 để giảm tải bớt.

nguyenthingocmai_I12A

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

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

Về Đầu Trang Go down

Tổng hợp các thuật giải điều phối

Bài gửi  NguyenPhuocNguyen (I12A) on 5/4/2012, 08:20

1/ 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/ 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 với 2 phương án:
o Có tiếm quyền (Preemptive)
o 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/ 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 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/ Thuật giải điều phối RRS:
- Như điều phối 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 ms (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/ Thuật giải điều phối MQS:
- Hàng chờ Ready được phân cấp thành nhiều mức độ ưu tiên khác nhau.
o 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.
o Ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
o Ưu tiên cố định: Xong hết các tiến trình 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à sản 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).
o Phân bổ theo tỷ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foregroupnd, 20% cho Background.

6/ Thuật giải điều phối MFQS:
- 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ố:
o Số mức (Số hàng chờ)
o Thuật giải điều phối cho mỗi mức
o Phương thức nâng cấp tiến trình
o Phương thức hạ cấp tiến trình
o Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới.

NguyenPhuocNguyen (I12A)

Tổng số bài gửi : 25
Join date : 15/02/2012
Age : 27
Đến từ : Đà Lạt

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  nguyenthimao_I12A on 5/4/2012, 08:21

BuiPhamAnBinh(I12A) đã viết:Tiến trình ++++++ thời điểm đến (ms) ++ CPU-Bust

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

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

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

biểu đồ Gantt


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

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


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

+ Thời điểm 5: P1 bắt đầu chạy 10 ms
+ Thời điểm 15: P2 tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
+ Thời điểm 25: P1 tiếm quyền P2 (vì P1 đang chờ ở thời điểm 15, P3 đang chờ ở thời điểm 20=> P1 chay trước)
+ Thời điểm 35: P3 tiếm quyền P1 (vì P3 đang chờ ở thời điểm 20, P2 đang chờ ở thời điểm 25 => P3 được chạy trước)Và kết thúc P3 tại 45(Đủ 10)
+ Thời điểm 45: P2 tiếm quyền P3 (vì P2 đang chờ ở thời điểm 25, P1 đang chờ ở thời điểm 35 => P2 được chạy trước)Và kết thúc P3 tại 50(Đủ 15)
+ Thời điểm 50: P1 vào thực hiện hết 5s còn lại và kết thúc tại 55

Tính thời gian trung bình:
Ap dụng công thức: T(i)= thờiđiểm kết thúc - thời điểm đến - t/g dùng CPU
P1 = (55 - 5 - 25) = 25
P2 = (50 - 10 - 15) = 25
P3 = (45 - 20 - 10) = 15

=>T(tb) = (25 + 25 + 15)/3 = 21,666ms

nguyenthimao_I12A

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

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

Về Đầu Trang Go down

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

Bài gửi  BuiPhamAnBinh(I12A) on 5/4/2012, 08:31

TaThucCuongI12C đã viết:Mình cũng chưa hiểu bài tập về thuật giải "Round Robin" mà bạn HuynhMinhChanh(i91C) và bạn LeQuocKhanh-11H1010059 đang thắc mắc.

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


Nếu theo lý thuyết trong slide thì :
Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 milli 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.

Vậy sau khi P2 tiếm quyền P1 thì P3 sẽ tiếm quyền P2. Nhưng bài giải lại là P1 tiếm quyền P2 trước P3??? Shocked

Với 1 bài khác và theo cách giải thích của bạn PhamQuangHien_I12A thì:


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

Tiến Trình Thời điểm đến (ms) CPU-Burst
P1 3 35
P2 10 20
P3 25 15

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

A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuyển qua tiến trình khác.ở đây là các tiến trình p1,p2,p3



Giải Thích Biểu Đồ:
1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)

Nếu sử dụng cách giải thích này cho bài đầu thì cũng không đúng vì P3 ở bài đầu đang chờ ở thời điểm 20 nên đáng lý phải được tiếm quyền trước P1 Sad

Vậy thuật giải này phải giải thích thế nào mới chính xác Question Bạn nào biết giải thích cho mọi người cùng hiểu với. Thanks nhiều!!! scratch scratch scratch

"Khi P3 được vào, P1 vẫn đang chờ nên P3 đứng sau P1 và P1 chạy trước rồi tới P3 chạy, như vậy mới đúng. " đây là lời giải thích của bạn HuynhPhuong (I11C) khóa trước mong giải quyết cho bạn phần nào

BuiPhamAnBinh(I12A)

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

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

Về Đầu Trang Go down

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

Bài gửi  nguyenthaihiep (I11C) on 5/4/2012, 08:34

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

nguyenthaihiep (I11C)

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

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

Về Đầu Trang Go down

Phân biệt thuật giải Multilevel Queue Scheduling với Multilevel Feedback Queue Scheduling.

Bài gửi  LeThanhTung (I11C) on 5/4/2012, 08:52

- Giống nhau: Thuật giải Multilevel Queue Scheduling (Điều phối hàng chờ nhiều mức) và Multilevel Feedback Queue Scheduling (Điều phối hàng chờ nhiều mức có điều tiết) cùng sử dụng nhiều mức hàng chờ với độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng thuật giải riêng, ví dụ Round-Robin (RRS) hoặc FCFS.
- Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.

LeThanhTung (I11C)

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

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

Về Đầu Trang Go down

Những tiêu chí điều phối CPU

Bài gửi  LeThanhTung (I11C) on 5/4/2012, 08:56

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.

LeThanhTung (I11C)

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

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

Về Đầu Trang Go down

Đề thi mẫu tối 4/4/2012

Bài gửi  TranHuyCuong17 (I12A) on 5/4/2012, 08:59

Mình uplên cho bạn nào chép ko kịp
Code:

http://t4ghcm.org.vn/upload/images/vn/quang-cao/upload/cau2.jpg
http://t4ghcm.org.vn/upload/images/vn/quang-cao/upload/cau3.jpg
http://t4ghcm.org.vn/upload/images/vn/quang-cao/upload/cau4.jpg
avatar
TranHuyCuong17 (I12A)

Tổng số bài gửi : 37
Join date : 16/02/2012
Age : 29
Đến từ : DLY™

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  nguyenthimao_I12A on 5/4/2012, 09:09

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

Tiến trình thời điểm đến Thời gian sử dụng CPU(CPU-Burst)
P1 525
P2 1015
P3 20 10

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

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


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

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

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

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


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

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

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


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



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

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

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

Theo ý của mình thì bạn đã hiểu sai
Vì ngay thời điểm 25 sau khi P2 vừa thực hiện xong 10s thì phải đến lượt P1 chứ không phải P3
Và P1 sẽ thực hiện 10s sau đó kết thúc tại 35 lúc này mới tới P3(lí do P1 trước P3 vì P1 tại thời điểm đó đang chờ ở 15 còn P3 đang chờ ở 20 nên P1 được thực hiện trước)
Sau đó P3 sẽ kết thúc 10s của mình tại thời điểm là 45
Tiếp đến là P2 và kết thúc tại 50 rùi sau cùng là P1 và kết thúc tại 55

=>T(tb) = (25 + 25 + 15)/3 = 21,666ms

nguyenthimao_I12A

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

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

Về Đầu Trang Go down

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

Bài gửi  TranThiNgocQuynh(I12C) on 5/4/2012, 09:18

LeThiMaiPhuongI12A đã viết:
Tiến trình Thời điểm đến(ms) CPU-Burst
P15 22
P2 10 15
P3 20 5
Dùng thuật giải Preemptive SJFS để điều phối CPU
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời điểm chờ trung bình của các tiến trình

a.Biểu đồ Gantt.

Tại thời điểm 5ms P1 sẽ được cấp CPU đầu tiên
Tại thời điểm 10ms,P2 đến, do khoảng CPU của P2 nhỏ hơn P1 nên P2 tiếm quyền P1, lúc này CPU được cấp cho P2, và P2 sẽ chạy hết khoảng CPU của nó
Tại thời điểm 25ms, P3 sẽ được cấp CPU vì P3 có khoảng CPU nhỏ hơn P1
Tại thời điểm 30ms P1 sẽ thực hiện tiếp khoảng CPU còn lại của nó
b.Tính thời điểm chờ trung bình của các tiến trình
P1=(47-5)-22=42-22=20ms
P2=(25-10)-15=15-15=0ms
P3=(30-20)-5=10-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8,3ms
Các bạn bổ sung thêm nha

Bạn ơi, cho mình hỏi:
Tại thời điểm 20ms, lẽ ra tiến trình P2 sẽ bị tiếm quyền bởi tiến trình P3, nhưng do khoảng thời gian dùng CPU còn lại của P2 là 5ms bằng với khoảng thời gian dùng CPU của tiến trình P3 là 5ms, mà tiến trình P2 đến trước so với tiến trình P3. Theo thuật giải FCFS, HDH sẽ cấp tiếp CPU cho tiến trình P2.
Mình hiểu như vậy có đúng chưa ? Bạn góp ý cho mình với.

TranThiNgocQuynh(I12C)

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

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

Về Đầu Trang Go down

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

Bài gửi  nguyenthimao_I12A on 5/4/2012, 09:30

HoNgocTuan142(I12A) đã viết:Trong bài này mình xin phép giải thích về các thuật giải điều phối CPU, vì đây là một phần rất quan trọng trong nội dung môn học và nhất là chiếm 2 điểm trong bài thi. afro
vì hơi lười nên mình soạn trong Word rồi chụp hình nên các bạn thông cảm Razz

1. Thuật giải đến trước – phục vụ trước FCFS (First come – First Served Scheduling):

- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=0
P2=(24-1)=23
P3=(27-2)=25
Thời gian chờ trung bình: (0+23+25)/3=16 ms
2. Giải thuật ngắn hơn chạy trước SJFS (Shortest Job First Scheduling) không tiếm quyền (Non-Preemptive):

- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=0
P2=(8-2)=6
P3=(7-4)=3
P4=(12-6)=6
Thời gian chờ trung bình: (0+6+3+6)/4=3.75 ms
CHÚ Ý PHẦN QUAN TRỌNG (100% RA THI) lol! lol! lol! lol!

3. Giải thuật ngắn hơn chạy trước SJFS (Shortest Job First Scheduling) có tiếm quyền (Preemptive):

Giải thích:
1) Tại thời điểm 5ms tiến trình P1 (CPU-Burst=22ms) xuất hiện, tiến trình P1 thực thi được khoảng 5ms thì tiến trình P2 (CPU-Burst=15ms) đến.
2) Tiến trình P1 phải nhường CPU lại cho tiến trình P2 (nghĩa là tiến trình P1 còn lại 17ms chưa được thực thi), tiến trình P2 thực thi được 15ms thì tiến trình P3 (CPU-Burst=5ms) đến (nghĩa là P2 còn 5ms chưa được thực thi) lúc này CPU-Burst của P2 còn lại và CPU-Burst của P3 bằng nhau và bé hơn CPU-Burst của P1, nên tiến trình nào nhỏ hơn và đến trước thì làm trước.
3) Tiến trình P2 làm tiếp 5ms còn lại.
4) CPU được nhường cho tiến trình P3 (CPU-Burst=5ms). Sau khi tiến trình P3 thực thi xong thì không có tiến trình nào tới nữa. quay lại thực hiện tiếp tiến trình P1 (còn 17ms).
5) Sơ đồ Gantt hoàng chỉnh cho bài toán trên.
- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=(17-5)-22=20
P2=(25-10)-15=0ms
P3=(30-20)-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8.33ms

4. Giải thuật điều phối theo vòng Robin RRS (Round Robin Scheduling):

Thời điểm Tiến Trình CPU-Burst (ms) Thời Lượng(ms)
5 P1 25 10
10 P2 15
20 P3 10
Sơ đồ Gantt:

Giải thích:
1) Tiến trình P1 (CPU-Burst=25ms) xuất hiện tại thời điểm ms thứ 5 và sau đó 5ms (ms thứ 10) tiến trình P2 tới. nhưng tiến trình P1 được quyền sử dụng CPU trong 10sm thì mới trả CPU cho tiến trình khác nên ms thứ 15 tiến trình P2 mới nhận lại CPU từ P1. Vậy P1 còn 15ms chưa thực thi.
2) Tiến trình P2 (CPU-Burst=15ms) chiếm giữ CPU trong vòng 10ms thì tiến trình P3 tới. P2 phải nhường CPU cho P3. Vậy P2 còn lại 5ms chưa thực thi.
3) Tiến trình P3 (CPU-Burst=10ms) chiếm giữ CPU trong 10ms thì xong công việc và không có tiến trình mới nào tới nữa nên CPU lại được nhường về P1 sử dụng.
4) Tiến trình P1 chiếm giữ CPU trong 10ms thì phải nhường lại cho P2. Vậy tiến trình P1 còn 5ms chưa thực thi.
5) Tiến trình P2 chiếm giữ CPU và thực thi xong 5ms còn lại thì nhường CPU lại P1.
6) Tiến trình P1 thực hiện nốt 5ms còn lại. Sơ đồ Gantt hoàn thành.
- Thời gian chờ:
Thời gian chờ của mỗi tiến trình:
P1=(55-5)-25=25
P2=(50-10)-15=25ms
P3=(45-20)-10=15ms
Thời gian chờ trung bình: (25+25+15)/3= 21.6 ms

Theo mình thấy ở bài vòng Robin có lẽ thầy cố ý làm sai chỗ này (Thầy chơi gài bẫy Suspect Suspect Suspect ):
thay mình hiểu là làm P1->P2->P3 rồi quay lại P1->P2->(P3 xong) quay lại ->P1...
thầy lại để P1->P2->P1 rồi mới tới P3->P2->P1
có phải vậy không?? các bạn cho ý kiến nha. Sleep Sleep Sleep Sleep Sleep Sleep Sleep Sleep
nếu hình ảnh có vấn đề các bạn vào download luôn file Word của mình up lên
http://www.mediafire.com/?917krfzt6qgrt7x

Thầy không sai, mà do bạn hiểu sai đó

Vì ngay thời điểm 25 sau khi P2 vừa thực hiện xong 10s thì phải đến lượt P1 chứ không phải P3
Và P1 sẽ thực hiện 10s sau đó kết thúc tại 35 lúc này mới tới P3(lí do P1 trước P3 là vì P1 tại thời điểm đó P1 đang chờ ở 15 còn P3 ở thời điểm 20 mới đến nên P1 được thực hiện trước)




nguyenthimao_I12A

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

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

Về Đầu Trang Go down

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

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

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

Tiến trình thời điểm đến Thời gian sử dụng CPU(CPU-Burst)
P1 525
P2 1015
P3 20 10

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

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


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

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

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

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


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

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

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


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



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

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

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

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


Cảm ơn Thầy ! Em đã xem giải thích của thầy và cũng đã hiểu rồi

tranvanthien27(I12C)

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

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

Về Đầu Trang Go down

trả lời bạn!

Bài gửi  nguyenthingocmai_I12A on 5/4/2012, 09:40

TranThiNgocQuynh(I12C) đã viết:
LeThiMaiPhuongI12A đã viết:
Tiến trình Thời điểm đến(ms) CPU-Burst
P15 22
P2 10 15
P3 20 5
Dùng thuật giải Preemptive SJFS để điều phối CPU
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời điểm chờ trung bình của các tiến trình

a.Biểu đồ Gantt.

Tại thời điểm 5ms P1 sẽ được cấp CPU đầu tiên
Tại thời điểm 10ms,P2 đến, do khoảng CPU của P2 nhỏ hơn P1 nên P2 tiếm quyền P1, lúc này CPU được cấp cho P2, và P2 sẽ chạy hết khoảng CPU của nó
Tại thời điểm 25ms, P3 sẽ được cấp CPU vì P3 có khoảng CPU nhỏ hơn P1
Tại thời điểm 30ms P1 sẽ thực hiện tiếp khoảng CPU còn lại của nó
b.Tính thời điểm chờ trung bình của các tiến trình
P1=(47-5)-22=42-22=20ms
P2=(25-10)-15=15-15=0ms
P3=(30-20)-5=10-5=5ms
Thời gian chờ trung bình: (20+0+5)/3=8,3ms
Các bạn bổ sung thêm nha

Bạn ơi, cho mình hỏi:
Tại thời điểm 20ms, lẽ ra tiến trình P2 sẽ bị tiếm quyền bởi tiến trình P3, nhưng do khoảng thời gian dùng CPU còn lại của P2 là 5ms bằng với khoảng thời gian dùng CPU của tiến trình P3 là 5ms, mà tiến trình P2 đến trước so với tiến trình P3. Theo thuật giải FCFS, HDH sẽ cấp tiếp CPU cho tiến trình P2.
Mình hiểu như vậy có đúng chưa ? Bạn góp ý cho mình với.

Bạn hiểu đúng rồi đó!
Thuật giải SJFS có tiếm quyền trong trường hợp bằng nhau thì nó sẽ dùng thuật giải FCFS.

nguyenthingocmai_I12A

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

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

Về Đầu Trang Go down

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

Bài gửi  TaThucCuongI12C on 5/4/2012, 09:47

maidangvu_I12A đã viết:


nguyenthimao_I12A đã viết:
Thầy không sai, mà do bạn hiểu sai đó

Vì ngay thời điểm 25 sau khi P2 vừa thực hiện xong 10s thì phải đến lượt P1 chứ không phải P3
Và P1 sẽ thực hiện 10s sau đó kết thúc tại 35 lúc này mới tới P3(lí do P1 trước P3 là vì P1 tại thời điểm đó P1 đang chờ ở 15 còn P3 ở thời điểm 20 mới đến nên P1 được thực hiện trước)


Admin: Ở thời điểm 15, P1 hết thời lượng và được xếp vào cuối Ready Queue, tức là sau P2 (lúc đó P3 chưa đến), P2 ở đầu hàng chờ nên được chọn chuyển sang trang thái Running !

- Tiếp theo P2 thực hiện xong phần quantum (10ms) đầu tiên và sẽ chuyển xuống hàng đợi (sau P1 ở trên).
Admin: Ở thời điểm 25 khi P2 hết thời lượng, HĐH sẽ chọn P1 vì P1 ở đầu hàng chờ (khi P3 đến ở thời điểm 20, P1 đã trong đó rồi, nên P3 xếp sau P1) !

- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.
Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

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

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

Admin
Xem kỹ giải thích trên. Mọi người hay sai chính ở chỗ em nêu !

Cám ơn thầy và các bạn. Giờ thì em đã hiểu. Smile


Được sửa bởi TaThucCuongI12C ngày 5/4/2012, 10:10; sửa lần 3.

TaThucCuongI12C

Tổng số bài gửi : 13
Join date : 15/02/2012
Age : 29
Đến từ : I12A

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

Về Đầu Trang Go down

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

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

tranvanthien27(I12C) đã viết:
HANDLE ProducerHandle[100 ] ;
HANDLE ConsumerHandle[100 ] ;
DWORD ProducerID; // cấp ID cho sản phẩm được tạo mới
DWORD ConsumerID;
for ( int i = 0 ; i < 30 ; i ++)
{
ProducerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Producer, 0, 4, &ProducerID);
ConsumerHandle[ i ]=CreateThread(0,0, (LPTHREAD_START_ROUTINE)Consumer, 0, 0, &ConsumerID);
}
// 2. Đánh thức các luồng
for ( int i = 0 ; i < 30 ; i ++)
{
ResumeThread ( ProducerHandle[ i ] );
ResumeThread ( ConsumerHandle[ i ] ); // đối với các tập luồng ConsumerHandle[ i ] này sau khi khởi tạo sẽ chạy ngay
}
// 3. Tạm ngừng
for ( int i = 0 ; i < 30 ; i ++)
{
SuspendThread(ProducerHandle[ i ]);
SuspendThread(ConsumerHandle[ i ]);
}

Admin
- Giải đúng !
- Hay hơn: Cỡ của các mảng ProducerHandle và ConsumerHandle là 30 (của em "dự phòng" tới 100, nên hơi "tốn" RAM). Mặt khác, ProducerID và ConsumerID cũng nên là các biến mảng !

Cảm ơn Thầy ! Em xin sửa lại tí

HANDLE ProducerHandle[30 ] ;
HANDLE ConsumerHandle[30 ] ;
DWORD ProducerID[ 30]; // cấp ID cho sản phẩm được tạo mới
DWORD ConsumerID[30 ];
for ( int i = 0 ; i < 30 ; i ++)
{
ProducerHandle[ i ]=CreateThread(Producer, 4, &ProducerID[i]);
ConsumerHandle[ i ]=CreateThread(Consumer, 0, &ConsumerID[i]));
}
// 2. Đánh thức các luồng
for ( int i = 0 ; i < 30 ; i ++)
{
ResumeThread ( ProducerHandle[ i ] );
ResumeThread ( ConsumerHandle[ i ] ); // đối với các tập luồng ConsumerHandle[ i ] này sau khi khởi tạo sẽ chạy ngay
}
// 3. Tạm ngừng
for ( int i = 0 ; i < 30 ; i ++)
{
SuspendThread(ProducerHandle[ i ]);
SuspendThread(ConsumerHandle[ i ]);
}

tranvanthien27(I12C)

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

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

Về Đầu Trang Go down

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

Bài gửi  TranTrungTinh(I12A) on 5/4/2012, 10:00

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

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

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





Em có một số lý luận như sau :
- Về bài giảng trên lớp : Thầy giảng thì Round Robin điều phối CPU dựa theo nguyên lý xoay vòng, khi 1 tiến trình bị tiếm quyền, thì nó sẽ được đưa vào cuối của hàng queue . Mà cơ chế của Queue là FIFO (First In First Out).
=> P1 sau khi thực hiện xong quantum đầu tiên thì sẽ chuyển xuống cuối hàng đợi (sau P3).
Admin: Ở thời điểm 15, P1 hết thời lượng và được xếp vào cuối Ready Queue, tức là sau P2 (lúc đó P3 chưa đến), P2 ở đầu hàng chờ nên được chọn chuyển sang trang thái Running !

- Tiếp theo P2 thực hiện xong phần quantum (10ms) đầu tiên và sẽ chuyển xuống hàng đợi (sau P1 ở trên).
Admin: Ở thời điểm 25 khi P2 hết thời lượng, HĐH sẽ chọn P1 vì P1 ở đầu hàng chờ (khi P3 đến ở thời điểm 20, P1 đã trong đó rồi, nên P3 xếp sau P1) !

- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.
Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

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

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

Admin
Xem kỹ giải thích trên. Mọi người hay sai chính ở chỗ em nêu !

Em cám ơn Thầy, em cũng bị sai chỗ này! Sad

Admin
Lần này, phải rút kinh nghiệm đấy. Chúc em thành công !


Dạ em cám ơn Thầy, lần này em sẽ không để bị sai như vậy nữa!


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

TranTrungTinh(I12A)

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

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

Về Đầu Trang Go down

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

Bài gửi  Sponsored content


Sponsored content


Về Đầu Trang Go down

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

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


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