Ôn tập thi Cuối kỳ

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

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

bổ sung câu 3 _ Bài 7 ĐỒNG BỘ HÓA TIẾN TRÌNH

Bài gửi  dangthihoangly(I12A) on 12/6/2013, 10:24

Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu? Cho ví dụ?
Khái niệm đèn hiệu
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

-Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations
Trình bày 2 ứng dụng của đèn hiệu
+ Ứng dụng 1: Giải quyết vấn đề vùng tương tranh.
Mã của tiến trình Pi bây giờ có cấu trúc:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) { // (Đèn hiệu nhị phân)
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}

Đoạn tương tranh là mã khi thực hiện đoạn mã thì ảnh hưởng đến vùng tranh chấp, các code trong mã khi sử dụng chugn ảnh hưởng đến miền, vùng tranh chấp.
Ví dụ : giả sử có một cây cầu ở đấu cầu có 1 đèn mutex ( có 2 trạng thái xanh và đỏ) 2 ô tô tìm cách lên cầu nhưng trọng tải của cầu chỉ chịu được 1 ô tô khi lên cầu và ô tô khác phải chờ, đoạn qua cầu thuộc đoạn tương tranh, cầu chính là tài nguyên dùng chung, và lệnh qua cầu thuộc đoạn tương tranh.
Chúng ta có thể sử dụng semaphores để giải quyết vấn đề vùng tranh chấp với n tiến trình. N tiến trình chia sẻ 1 biến semaphore, mutex được khởi tạo.
Ứng dụng 2 : Đảm bảo công việc trật tự của các tiến trình.
Chúng ta cũng có thể sử dụng Semaphores để giải quyết vấn đề đồng bộ khác nhau
Thí dụ ,để xem xét hai tiến trình đang thực thi đồng hành : P1 với câu lệnh S1 và P2 với câu lệnh S2. Chúng ta tổ chức sao cho S2 được thực thi chỉ sau khi S1 đã hoàn thành , thực hiện bằng cách P1 và P2 chia sẻ một semaphore chugn Synch được khời tạo 0 và bằng cách chèn các câu lệnh Semaphore synch = 0;
Cấu trúc P1 Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2


Để giải thích cho định nghĩa đèn hiệu mình xin nêu 2 ví dụ sau :
Ví dụ 1 : Có 1 cây câu bắc ngang qua sông .Cây cầu này chỉ chịu tải được 1 xe ô tô vì vậy để tránh trường hợp có nhiều hơn 1 xe ô tô qua cầu thì ta phải đồng bộ hóa quá trình này .Ở đây ta sẽ áp dụng đèn hiệu để giải quyét bài toán này..Đèn hiệu lúc này sẽ có 2 giá trị xanh hoặc đỏ.
Xanh tức trên cầu không có xe nào .
Đỏ tức trên cầu hiện đang có 1 xe ô tô.
Ban đầu thì giá trị đèn hiệu sẽ là màu xanh. Khi có 1 xe ô tô bắt đầu qua cầu thì đèn hiệu lại chuyển sang màu đỏ .Lúc này thì không có xe nào được phép lên cầu cho đến khi xe ô tô đó qua cầu xong tức là đèn hiệu chuyển sang màu xanh
Về mặt lập trình thì sẽ có 3 hàm : wait(S) quacau() signal(s)
Chờ nếu S = 0 và đi nếu S=1
Ví dụ 2 : đèn hiệu còn đươc áp dụng tại các điểm thu phí xe.Tại cá điểm này thì khi thu phí chỉ có duy nhất 1 xe được thu phí trong 1 lúc nên cần có đèn hiệu để báo cho hệ thống biết mà ha cần ngăn xuống

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

câu 3- BÀI 8 : DEADLOCKS

Bài gửi  dangthihoangly(I12A) on 12/6/2013, 10:27

Câu 3: Biết vẽ và giải thích cũng như đánh giá trạng thái của đồ thị cấp phát tài nguyên?
Bạn nào có lời giải câu này thì post cho mình với. mình còn thiếu mỗi câu này.

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

Giải thích và đánh giá trạng thái của đồ thị cấp phát tài nguyên

Bài gửi  NguyenTienDat (I22A) on 13/6/2013, 11:37


 a) Giải thích hình vẽ
Tại thời điểm Ti, P1 yêu cầu phiên bản duy nhât của tài nguyên R1 lúc này đã được cấp cho P2.
P1 và P2 có nhu cầu phiên bản duy nhất của tài nguyên R2
b) Có nên giải quyết yêu cầu cấp tài nguyên từ R2 cho P1 hay không? Tại sao?
- Giả sử tại thời điểm Ti + 5 (18h5’): P1 yêu cầu phiên bản duy nhất của tài nguyên R2

- Giả sử tại thời điểm Ti + 10 (18h10’): R2 cấp tài nguyên cho P1, hệ thống rơi vào trạng thái không an toàn

- Tại thời điểm Ti + 15 (18h15’): P2 yêu cầu phiên bản duy nhất của R2 lúc này đã được cấp cho P1 => Xảy ra Deadlock

Vậy không nên giải quyết yêu cầu cấp tài nguyên từ R2 cho P1 vì hệ thông sẽ xảy ra Deadlock

NguyenTienDat (I22A)

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

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

Về Đầu Trang Go down

câu 3 trong đề thi của khoá trước

Bài gửi  NguyenTienDat (I22A) on 15/6/2013, 19:46

Sử dụng Visual C++ 6.0 lập trình đánh thức (Resume Thread) tất cả các luồng sản xuất. Biết rằng mục quản (Handle) của chúng lưu trong mảng khai báo bằng lệnh: 
HANDLE ProducerHandles[50];

Code:
for(int i=0;i<50;i++)
{
    ResumeThread(ProducerHandles[i]);
}

NguyenTienDat (I22A)

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

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

Về Đầu Trang Go down

Cần giúp đỡ

Bài gửi  TranVanDucHieu(I22B) on 17/6/2013, 23:33

bạn nào có cách giải thuật round robin  hay không nhỉ cho minh học hỏi với

TranVanDucHieu(I22B)

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

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

Về Đầu Trang Go down

Re: Ôn tập thi Cuối kỳ

Bài gửi  TranBinhCongLuanI12A on 18/6/2013, 20:12

TranVanDucHieu(I22B) đã viết:bạn nào có cách giải thuật round robin  hay không nhỉ cho minh học hỏi với
http://www.mediafire.com/view/?9luwp40ldq89bun
Trong link này có nè bạn

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

Câu 4: Dùng thuật giải RRS

Bài gửi  dangthihoangly(I12A) on 18/6/2013, 23:11

Các bạn xem., mình làm thế có cần bổ sung hay sai sót gì hok? Pm càng sớm càng tốt nha mấy bạn
Câu 4: 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ìnhThời điểm đến (ms)CPU-Burst (ms)
P1446
P23028
P35133
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
a.       Thể hiện bằng biểu đồ Gantt                                                                                 (1,0 điểm)
b.      Tính thời gian chờ trung bình của các tiến trình  
Bài làm:
Bảng trợ giúp:                                                            
P1
P2
P3
4(46)
24(26)
44(6)
 
70(0)
30(28)
 
 
64(8 )
 
 
98(0)
51(33)
 
 
 
 
90(13)
 
111(0)

Hoặc thể hiện với 4 cột như sau (Cột 1 chứa tiến trình được chọn kế tiếp với khoảng CPU bằng 20 hay nhỏ hơn giá trị này):
T = 20 ms

P1

P2

P3

4(46)

30(28)

51(33)

P1(20)

24(26)

P1(20)

44(6)

P2(20)

64(8 )

P1(6)

70(0)

P3(20)

90(13)

P2(8 )

98(0)

P3(13)

111(0)

 
OR THỂ HIỆN BẢNG TRỢ GIÚP THẾ NÀY:                                                                             
P1
P2
P3
4(46)
24(26)
44(6)
70(0)
30(28)
64(8 )
98(0)
51(33)
90(13)
111(0)
 
 
                    
Biểu đồ Gantt:           
P1
P1
P2
P1
P3
P2
P3
4         24           44            64         70         90          98        111


b. tính thời gian trung bình:
Thời gian chờ của các tiến trình: // Công thức: Tg kết thúc – Thời điểm đến – Khoảng CPU
·         P1 = 70 –( 46 - 4) = 20 (ms)
·         P2 = 98 – (30 – 28) =  40 (ms)
·         P3 = 111 – (51 – 33) = 27 (ms)

Thời gian chờ trung bình của các tiến trình: (20 + 40 + 27) / 3 = 29 ms


Được sửa bởi dangthihoangly(I12A) ngày 18/6/2013, 23:14; sửa lần 1.

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

Bài 5: Dùng thuật giải nhà băng

Bài gửi  dangthihoangly(I12A) on 18/6/2013, 23:13

Không biết có cần giải thích gì trong bài làm nữa Không?
Bài 5:  
Một hệ thống có 6 ổ băng từ và 3 tiến trình với trạng thái cấp phát tài nguyên ở thời điểm Ti như sau:
 
Tiến trình
(Process)
Đã được cấp (số ổ băng)
(Allocation)
Tối đa cần (số ổ băng)
(Max)
P112
P224
P312
 
            Dùng Thuật giải Nhà băng để:
a.       Chứng minh trạng thái này là an toàn                                                                  
b.      Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của P3  
Bài giải:
a.       Công thức: Available = Số máy quét (or ổ băng từ) – Allocation của 3 tiến trình
      Need = Max – Allocation
            Trạng thái ban đầu
Process
(Tiến trình)
Allocation
(Đã được cấp)
Max
(Tối đa cần)
NeedAvailable
P1
P2
P3
1
2
1
2
4
2
1
2
1
6 – (1+2+1)
= 6 – 4
= 2
           
                        Bảng trợ giúp: Tại thời điểm Ti
            Worki  >=       Need i                          Pi         Allocationi
                2                      1                  P1               1
                3                      2                  P2               2    //work này = work dòng 1 + Allocation của dòng 1
                5                      1                  P3               1   //work này = work dòng 2 + Allocation của dòng 2     
            Tìm được chuỗi an toàn: (P1, P2, P3). Do đó, trạng thái tại thời điểm Ti an toàn (Điều phải chứng minh)
 
b.      Có nên đáp ứng………………..cho P3
Request3   <= Need3 vì 1 = 1   // Request = số ổ xin thêm. Đề bài xin thêm 1 ổ
Request3 <= Available3 vì 1 < 2
Suy ra, thỏa 2 điều kiện
Nếu đáp ứng yêu cầu này, ta có Trạng thái mới:
Tiến trìnhAllocationMaxNeedAvailable
P1
P2
P3
1
2
2
2
4
2
1
2
0
6 – (1+2+2)
= 6 – 5
= 1
 
            Bảng trợ giúp: Tại thời điểm Ti
Worki  >=       Need i                          Pi              Allocationi
                 1                   1                    P1                    1
                 2                   2                    P2                    2
                 4                   0                    P3                    2

            Tồn tại chuỗi an toàn : (P1,P2,P3). Vậy có thể thêm 1 ổ cho P3

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

Thuật giải nhà băng.

Bài gửi  NguyenThiMyThoa(I22A) on 19/6/2013, 13:50

Bài 1: Một hệ thống có 3 máy quét hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation= (0,2,1), và Max(2,2,2). Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có đáp ứng được hay không yêu cầu thêm 1 máy nữa của P2.
Giải:

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0+2+1)=0
Tiến trình Đang giữ Max Hệ có 
P1 0 2 0 
P2 2 2 
P3 1 2 

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need 
P1 2
P2 0
P3 1

Work >= Need(i) P(i) Allocation(i)
0 0 P2 2 
2 1 P3 1
3 2 P1 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.


Bai 2: 

Một hệ thống có 3 máy quét hình và 2 tiến trình P1,P2 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation(1,1) và Max(2,2). Dùng thuật giải nhà băng để: 

a) Chứng minh trạng thái an toàn 
b) Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy nữa P2 ./.



Giải: 
a) Allocation=(1,1), Max=(2,2);
Available=3-(1+1)=1;
Ta có: Need(i)=Max(i)-Allocation(i)
=> p1=(2-1)=1; p2=(2-1)=1;
Work >= Need(i) P(i ) Allocation
1 1 p1 1
2 1 p2 1
. Tồn tại chuỗi an toàn=.
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
b)
Request(2)<=Need(2) vì 1<=1
Request(2)<=Available vì 1<=1
Trạng thái mới:
Allocation(1,1+1)(vì thêm 1 máy nữa nên cộng thêm 1)
Available=3-(1+1+1)=0
Need(i):
p1 1
p2 0
Work >= Need(i) P(i) Allocation
0 0 p2 2
2 1 p1 1
Tồn tại trạng thái an toàn=
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

các bạn tham khảo them nhé.
chúc các bạn thi tốt

NguyenThiMyThoa(I22A)

Tổng số bài gửi : 12
Join date : 15/03/2013
Age : 26
Đến từ : 12H1010134

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

Về Đầu Trang Go down

Thuật giả RRS

Bài gửi  NguyenThiMyThoa(I22A) on 19/6/2013, 13:55

dangthihoangly(I12A) đã viết:Không biết có cần giải thích gì trong bài làm nữa Không?
Bài 5:  
Một hệ thống có 6 ổ băng từ và 3 tiến trình với trạng thái cấp phát tài nguyên ở thời điểm Ti như sau:
 
Tiến trình
(Process)
Đã được cấp (số ổ băng)
(Allocation)
Tối đa cần (số ổ băng)
(Max)
P112
P224
P312
 
            Dùng Thuật giải Nhà băng để:
a.       Chứng minh trạng thái này là an toàn                                                                  
b.      Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của P3  
Bài giải:
a.       Công thức: Available = Số máy quét (or ổ băng từ) – Allocation của 3 tiến trình
      Need = Max – Allocation
            Trạng thái ban đầu
Process
(Tiến trình)
Allocation
(Đã được cấp)
Max
(Tối đa cần)
NeedAvailable
P1
P2
P3
1
2
1
2
4
2
1
2
1
6 – (1+2+1)
= 6 – 4
= 2
           
                        Bảng trợ giúp: Tại thời điểm Ti
            Worki  >=       Need i                          Pi         Allocationi
                2                      1                  P1               1
                3                      2                  P2               2    //work này = work dòng 1 + Allocation của dòng 1
                5                      1                  P3               1   //work này = work dòng 2 + Allocation của dòng 2     
            Tìm được chuỗi an toàn: (P1, P2, P3). Do đó, trạng thái tại thời điểm Ti an toàn (Điều phải chứng minh)
 
b.      Có nên đáp ứng………………..cho P3
Request3   <= Need3 vì 1 = 1   // Request = số ổ xin thêm. Đề bài xin thêm 1 ổ
Request3 <= Available3 vì 1 < 2
Suy ra, thỏa 2 điều kiện
Nếu đáp ứng yêu cầu này, ta có Trạng thái mới:
Tiến trìnhAllocationMaxNeedAvailable
P1
P2
P3
1
2
2
2
4
2
1
2
0
6 – (1+2+2)
= 6 – 5
= 1
 
            Bảng trợ giúp: Tại thời điểm Ti
Worki  >=       Need i                          Pi              Allocationi
                 1                   1                    P1                    1
                 2                   2                    P2                    2
                 4                   0                    P3                    2

            Tồn tại chuỗi an toàn : (P1,P2,P3). Vậy có thể thêm 1 ổ cho P3
cảm ơn bạn nha. Mình đang thắt mắc chỗ work. Giờ thì mình đã hiểu rõ hơn.
Chúc cả nhà thi tốt
i

NguyenThiMyThoa(I22A)

Tổng số bài gửi : 12
Join date : 15/03/2013
Age : 26
Đến từ : 12H1010134

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

Về Đầu Trang Go down

Thuật giả RRS

Bài gửi  NguyenThiMyThoa(I22A) on 19/6/2013, 14:01

TranBinhCongLuanI12A đã viết:
TranVanDucHieu(I22B) đã viết:bạn nào có cách giải thuật round robin  hay không nhỉ cho minh học hỏi với
http://www.mediafire.com/view/?9luwp40ldq89bun
Trong link này có nè bạn
Cảm ơn bạn nha

NguyenThiMyThoa(I22A)

Tổng số bài gửi : 12
Join date : 15/03/2013
Age : 26
Đến từ : 12H1010134

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

Về Đầu Trang Go down

Ôn tập thi Cuối kỳ

Bài gửi  VANCONGLOI(I22A) on 20/6/2013, 01:26

VoMinhThang(I22B) đã viết:Một hệ thống có 10 máy quét và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng các vector Allocation (3,1,1) và Max (9,4,8 ).
Dùng thuật giả nhà băng để
a. Chứng minh trạng thái này an toàn
b. Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process---Allocation---Max---Need---Available
P1----------3-----------9--------6---------5
P2----------1-----------4--------3
P3----------1-----------8--------7


Bảng trợ giúp:
Work >=---Needi---Pi---Allocation
5-------------3------P2---1
6-------------6------P1---3
9-------------7------P3---1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn
b.
Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3
Gọi yêu cầu là Request3. Ta có Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process---Allocation---Max---Need---Available
P1---------3------------9-------6--------4
P2---------1------------4-------3
P3---------2------------8-------6


Bảng trợ giúp:
Work >=-----Needi---Pi---Allocation
4--------------3-------P2---1
5--------------?-------?-----?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn.

Chúc các bạn thi thật tốt

bài của bạn rất chi tiết,cám ơn bạn nhiều.

VANCONGLOI(I22A)

Tổng số bài gửi : 22
Join date : 09/03/2013
Age : 26
Đến từ : Bình thuận

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

Về Đầu Trang Go down

Ôn tập thi cuối kỳ

Bài gửi  VANCONGLOI(I22A) on 20/6/2013, 02:24

dangthihoangly(I12A) đã viết:Các bạn xem., mình làm thế có cần bổ sung hay sai sót gì hok? Pm càng sớm càng tốt nha mấy bạn
Câu 4: 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ìnhThời điểm đến (ms)CPU-Burst (ms)
P1446
P23028
P35133
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
a.       Thể hiện bằng biểu đồ Gantt                                                                                 (1,0 điểm)
b.      Tính thời gian chờ trung bình của các tiến trình  
Bài làm:
Bảng trợ giúp:                                                            
P1
P2
P3
4(46)
24(26)
44(6)
 
70(0)
30(28)
 
 
64(8 )
 
 
98(0)
51(33)
 
 
 
 
90(13)
 
111(0)

Hoặc thể hiện với 4 cột như sau (Cột 1 chứa tiến trình được chọn kế tiếp với khoảng CPU bằng 20 hay nhỏ hơn giá trị này):
T = 20 ms

P1

P2

P3

4(46)

30(28)

51(33)

P1(20)

24(26)

P1(20)

44(6)

P2(20)

64(8 )

P1(6)

70(0)

P3(20)

90(13)

P2(8 )

98(0)

P3(13)

111(0)

 
OR THỂ HIỆN BẢNG TRỢ GIÚP THẾ NÀY:                                                                             
P1
P2
P3
4(46)
24(26)
44(6)
70(0)
30(28)
64(8 )
98(0)
51(33)
90(13)
111(0)
 
 
                    
Biểu đồ Gantt:           
P1
P1
P2
P1
P3
P2
P3
4         24           44            64         70         90          98        111


b. tính thời gian trung bình:
Thời gian chờ của các tiến trình: // Công thức: Tg kết thúc – Thời điểm đến – Khoảng CPU
·         P1 = 70 –( 46 - 4) = 20 (ms)
·         P2 = 98 – (30 – 28) =  40 (ms)
·         P3 = 111 – (51 – 33) = 27 (ms)

Thời gian chờ trung bình của các tiến trình: (20 + 40 + 27) / 3 = 29 ms


mình thì làm theo như trên lơp với cái mẫu bảng trợ giúp thứ 3 tính từ trên xuống.

VANCONGLOI(I22A)

Tổng số bài gửi : 22
Join date : 09/03/2013
Age : 26
Đến từ : Bình thuận

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

Về Đầu Trang Go down

thuật giải nhà băng

Bài gửi  TranVuSang (I22B) on 21/6/2013, 10:38

Một hệ thống có 10 máy quét hình và 3 tiến trình P1,P2,P3 với trạng thái cấp phát tài nguyên ở thời diểm Ti thể hiện bằng các vectơ sau : Allocation=( 3,1,1 ) và Max=( 9,4,8 ). Dùng thuật giải nhà băng để.
a/ Chứng minh trạng thái này an toàn(1đ)
b/ Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy của P3
 
a/ Chứng minh trạng thái an toàn.
_
 
Process
Allocation
Max
Need
Available
P1
3
9
6
10 - (3+1+1) = 10-5 = 5
P2
1
4
3
 
P3
1
8
7
 
 
_Bảng trợ giúp
Work >=
Need i
P i
Allocation i
5
3
P2
1
6
6
P1
3
9
7
P3
1
 
Tìm được chuỗi an toàn = { P2, P1, P3}
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn
b/Có nên đáp ứng yêu cầu xin thêm 1 máy của P3?
_Request3=1 <= Need3=7 vì 1<=7
_Request3=1 <= Available=5 vì 1<=5
_Trạng thái mới
Process
Allocation
Max
Need
Available
P1
3
9
6
5 - 1 = 4
P2
1
4
3
 
P3
2
8
6
 
 
_Tìm chuỗi an toàn
Work >=
Need i
P i
Allocation i
4
3
P2
1
5
?
?
?
 
Không tồn tại chuỗi an toàn, do đó không nên đáp ứng yêu cầu trên của P3
 
Thầy cho em hỏi ở câu b.Ở bảng trạng thái mới thay vì mình viết là 5 -1 = 4 thì mình có thể viết là 10 – ( 3 +1 +2 ) = 4 được không ạh.
Với lại câu a và câu b mình có nên vẽ đường cong từ  số 5 ở Available xuống số 5 ở bảng trợ giúp trong cột Work trong bài thi không vậy thầy.


Được sửa bởi TranVuSang (I22B) ngày 21/6/2013, 16:59; sửa lần 2.

TranVuSang (I22B)

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

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

Về Đầu Trang Go down

câu 3 bài 8 DeaLock

Bài gửi  TranBinhCongLuanI12A on 21/6/2013, 11:21

Sơ đồ 1 thì xem cho biết thôi vì sơ đồ này là của bài 4. 
Sơ đồ 2 là của Câu 3 : Biết vẽ và giải thích được đồ thị cấp phát tài nguyên . trong bài 8 
Thầy sẽ cho ra 1 câu về đồ thị nên mấy bạn xem qua đồ thị này. sẽ có ích cho các bạn.

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

Câu 2_ bài 5 Tập luồng

Bài gửi  TranBinhCongLuanI12A on 21/6/2013, 11:24

Câu 2: Trình bày nguyên lý tập luồng và ứng dụng. Cho vd minh họa ( trên máy tính và từ đời thường)
Nguyên lý tập luồng :
- Tiến trình cha tạo lập sẵn một tập luồng khi khởi động.
- Các luồng trong tập luồng luôn sẵn sàng chờ công việc.
- Khi tiến trình cha (ví dụ Web Server) nhận thêm một yêu cầu, một luồng được đánh thức và đưa vào vận hành.
- Phục vụ xong, luồng được đưa trả về tập luồng.
- Nếu số yêu cầu lớn hơn số luồng trong tập, tiến trình cha chờ đến khi có luồng được giải phóng.

Ứng Dụng:
- Khả năng đáp ứng (Responsiveness) tốt hơn: Trong khi một luồng bị ách hoặc quá bận, luồng khác vẫn vận hành bình thường (Luồng chính của trình duyệt vẫn tương tác với người dùng trong khi dữ liệu được lấy về).
- Chia sẻ tài nguyên (Resource Sharing): Theo mặc định, các luồng có thể dùng chung bộ nhớ và tài nguyên của luồng cha. Vài luồng cùng vận hành trong 1 vùng địa chỉ, do đó dễ dùng chung tài nguyên hơn so với trường hợp đa tiến trình.
- Tiết kiệm (Economy): Cấp phát bộ nhớ và tài nguyên cho tiến trình là công việc tốn kém. Do luồng chung tài nguyên với cha và các luồng khác, việc tạo lập và chuyển ngữ cảnh cũng nhanh hơn (Solaris 2: Tạo tiến trình chậm hơn 30 lần, Chuyển ngữ cảnh chậm hơn 5 lần).
- Tận dụng được thế mạnh của kiến trúc đa xử lý: Đa luồng làm tăng tính song song trên hệ máy nhiều CPU. Mỗi luồng có thể chạy bởi CPU riêng.
Ví dụ : Duy trì 1 đội quân 100 người được đào tạo kỉ càng,trang bị đầy đủ, khi có địch đến thì tùy theo tình hình sẽ điều lính ra .

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

code đề thi giữa kì của lớp I12A khóa 2011 năm học 2012

Bài gửi  TranBinhCongLuanI12A on 21/6/2013, 11:32

Giải thích đoạn code sau:
Handle SemEmpty, SemFull;
SemEmpty = CreateSemaphore (0,40,50,'SE1');
SemFull = CreateSemaphore (0,0,50,'SF1');
SemEmpty.Waitone();
SemFull.Release();

Giải:
Handle SemEmpty, SemFull; // khai báo 2 đèn hiệu SemEmpty và SemFull có kiểu dữ liệu Handle. Mục quản của các đèn hiệu vừa khởi tạo được đưa vào biến SemEmpty , SemFull.

SemEmpty = CreateSemaphone (0,40,50,'SE1'); // khởi tạo đèn hiệu SemEmpty với giá trị khởi đầu là 40, giá trị max là 50, có tên là SE1

SemFull = CreateSemaphone (0,0,50,'SF1');// khởi tạo đèn hiệu SemFull  ới giá trị khởi đầu là 0, giá trị max là 50, có tên là SF1

SemEmpty.Waitone();//kiểm tra xem đèn hiệu SemEmpty có giá trị >=1 thỏa điều kiện thì giảm đi 1

SemFull.Release();//tăng giá trị đèn hiệu SemFull lên 1

Admin
Đoạn mã trên lẫn lộn giữa VC++ 6.0 và VC# .NET !

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

thêm 1 câu liên quan đến code

Bài gửi  TranBinhCongLuanI12A on 21/6/2013, 11:35

Sử dụng Visual C++6.0 để lập trình đánh thức (ResumeThread) tất cả các luồng sản xuất với mảng khai bảo bằng lệnh:
              HANDLE ProducerHandle[50]
Giải:

HANDLE ProducerHandle[50];
for (int i = 0; i<50; i++)
{
     ResumeThread(ProducerHandle[i]);
}

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

Help my về tiếm quyền và không tiếm quyền

Bài gửi  TranVanDucHieu(I22B) on 21/6/2013, 19:32

Khi  nào mình giải bài theo kiểu tiếm quyền và khi nào mình sẽ giải theo không tiếm quyền ?? mình chưa hỏi

TranVanDucHieu(I22B)

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

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

Về Đầu Trang Go down

Re: Ôn tập thi Cuối kỳ

Bài gửi  NguyenThiThom(I22A) on 22/6/2013, 00:29

TranVanDucHieu(I22B) đã viết:Khi  nào mình giải bài theo kiểu tiếm quyền và khi nào mình sẽ giải theo không tiếm quyền ?? mình chưa hỏi
BT điều phối theo vòng Robin (RRS) là có tiếm quyền ak. hi

NguyenThiThom(I22A)

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

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

Về Đầu Trang Go down

Ôn tập thi Cuối kỳ

Bài gửi  TrieuDucMinh(I22A) on 22/6/2013, 17:22

Cám ơn các bạn đã chia sẽ trong topic này. Qua topic này mình đã vững tâm chờ ngày mai thi. Chúc các bạn ngày mai thi tốt và đạt được kết quả như mong muốn. "Hệ điều hành muôn năm".

TrieuDucMinh(I22A)

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

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

Về Đầu Trang Go down

thuật giải Round Robin

Bài gửi  NguyenThiBichTram (I22A) on 22/6/2013, 17:29

PhamThiThao (I22B) đã 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

Câu b theo mình bạn giải bị sai rồi, mình chỉnh lại mong các bạn cho ý kiến.
b. Thời gian chờ trung bình : Ti = (Thời điểm kết thúc – Thời điểm đến) – Khoảng CPU 
Thời gian chờ trung bình của từng tiến trình:
• P1 = (68 - 5) – 34 = 63 - 5 = 29(ms)
• P2 = (71 - 17) – 23 = 54 - 23 = 31(ms)
• P3 = (44 - 24) – 9 = 20 - 9 = 11(ms)
Thời gian chờ trung bình : (29 + 31 + 11) / 3 = 71/3 = 23,667 (ms)




NguyenThiBichTram (I22A)

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

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

Về Đầu Trang Go down

Lời giải thích cho btap dùng thuật giải RRB

Bài gửi  TranBinhCongLuanI12A on 22/6/2013, 17:47

Lời giải thích khá chi tiết và đầy đủ

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử
dụng CPU như sau:
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14
Biểu Đồ Gantt?
Thời gian chờ trung bình?
Bài Giải

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

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

Giải thích :

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

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

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

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

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

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

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

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

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

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

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

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

TranBinhCongLuanI12A

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

Xem lý lịch thành viên http://www.2dollarmayman.com

Về Đầu Trang Go down

Trạng thái an toàn và chuỗi an toàn

Bài gửi  dangthihoangly(I12A) on 22/6/2013, 17:57

- Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
- Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
- Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
- Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
- Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.
 

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

khá chi tiết nhỉ

Bài gửi  dangthihoangly(I12A) on 22/6/2013, 17:58

TranBinhCongLuanI12A đã viết:Lời giải thích khá chi tiết và đầy đủ

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử
dụng CPU như sau:
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14
Biểu Đồ Gantt?
Thời gian chờ trung bình?
Bài Giải

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

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

Giải thích :

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

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

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

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

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

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

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

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

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

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

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

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

dangthihoangly(I12A)

Tổng số bài gửi : 64
Join date : 10/03/2012
Age : 26
Đến từ : Quang ngai

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

Về Đầu Trang Go down

Re: Ôn tập thi Cuối kỳ

Bài gửi  Sponsored content Today at 14:52


Sponsored content


Về Đầu Trang Go down

Trang 5 trong tổng số 6 trang Previous  1, 2, 3, 4, 5, 6  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