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

NguyenThiMai(I22A) 26/4/2013, 16:03

Điều kiện xuất hiện deadlock
Có 4 điều kiện cần để xảy ra tình trạng tắc nghẽn( deadlock):
1. Tiến trình có sử dụng tài nguyên không thể chia sẻ
2. Tiến trình chiếm giữ và yêu cầu thêm tài nguyên
3. Không thu hồi tài nguyên từ các tiến trình đang giữ chúng
4. Tồn tại một chu trình trong đồ thị cấp phát tài nguyên
Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.

NguyenThiMai(I22A) 26/4/2013, 16:04

Các phương pháp ngăn chặn Deadlock
Có 4 phương pháp để ngăn chặn tắc nghẽn: Ngăn chặn hình thành tắc nghẽn, tránh tắc nghẽn, phát hiện tắc nghẽn và hiệu chỉnh tắc nghẽn
1. Ngăn chặn tắc nghẽn:
- Tài nguyên không thể chia sẻ: nhìn chung gần như không thể tránh tình trạng này vì bản chất tài nguyên là có hạn
- Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác
- Không thu hồi tài nguyên :cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khóa và cấp phát trở lại cho các tiến trình khi nó thoát khỏi tình trạng bị khóa.
- Tồn tại một chu kỳ : tránh tạo chu kỳ trong đồ thị bằng cách cấp phát tài nguyên theo một sự phân cấp
2. Tránh tắc nghẽn: là loại bỏ tất cả các cơ hội có thể dẫn đến tắc nghẽn trong tương lai.
3. Phát hiện tắc nghẽn:
4. Hiệu chỉnh tắc nghẽn:
- Đình chỉ hoạt động của các tiến trình liên quan có thể sử dụng 1 trong 2 phương pháp
+ Đình chỉ tất cả tiến trình trong tình trạng tắc nghẽn
+ Đình chỉ từng tiến trình liên quan cho tới khi không còn chu trình nào gây tắc nghẽn
- Thu hồi tài nguyên: Có thể hiệu chỉnh tắc nghẽn bằng cách thu hồi một số tài nguyên từ các tiến trình và cấp phát tài nguyên này cho các tiến trình khác cho tới khi loại bỏ được chu trình tắc nghẽn.

NguyenThiMai(I22A) 26/4/2013, 16:17

Giải thuật nhà băng
Nhiều cấu trúc dữ liệu phải được duy trì để cài đặt giải thuật Banker. Những cấu
trúc dữ liệu này mã hoá trạng thái của hệ thống cấp phát tài nguyên. Gọi n là số quá
trình trong hệ thống và m là số loại tài nguyên trong hệ thống. Chúng ta cần các cấu
trúc dữ liệu sau:
• Available: một vector có chiều dài m hiển thị số lượng tài nguyên sẳn dùng
của mỗi loại. Nếu Available[j]= k, có k thể hiện của loại tài nguyên Rj sẳn
dùng.
• Max: một ma trận n x m định nghĩa số lượng tối đa yêu cầu của mỗi quá
trình. Nếu Max[ i , j ] = k, thì quá trình Pi có thể yêu cầu nhiều nhất k thể
hiện của loại tài nguyên Rj.
• Allocation: một ma trận n x m định nghĩa số lượng tài nguyên của mỗi loại
hiện được cấp tới mỗi quá trình. Nếu Allocation[ i, j ] = k, thì quá trình Pi
hiện được cấp k thể hiện của loại tài nguyên Rj.
• Need: một ma trận n x m hiển thị yêu cầu tài nguyên còn lại của mỗi quá
trình. Nếu Need[ i, j ] = k, thì quá trình Pi có thể cần thêm k thể hiện của loại
tài nguyên Rj để hoàn thành tác vụ của nó. Chú ý rằng, Need[ i, j ] = Max[ i, j ] – Allocation [ i, j ].

dùng thuật giải nhà băng chứng minh trạng thái này an toàn

Tiến trình	Được cấp(ổ đĩa)	tối đa cần(ổ đĩa)
P1	5	10
P2	2	4
P3	2	9

-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work	≥ Need	--Pi ---	Allocation(i)
3	2	P2	2
5	5	P1	5
10	7	P3	2

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

TranVuSang (I22B) 30/4/2013, 12:40

Tập luồng là 1 tập có nhiều luồng có chức năng giống nhau, bao gồm 1 luồng chính đây là luồng khởi động và nhiều luồng phụ giống nhau có chung mã. Tiến trình cha tạo lập sẵn 1 tập luồng khi khởi động và lúc đầu các luồng ở trạng thái ngủ và luôn luôn sẵn sàng chờ công việc. Khi tiến trình cha nhận thêm 1 yêu cầu thì 1 luồng được đánh thức và đưa vào vận hành ngay, 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 thì tiến trình cha chờ khi có luồng được giải phóng nó sẽ cho luồng đó phục vụ yêu cầu đang chờ. Việc các luồng ngủ như vậy sẽ làm cho CPU nhẹ nhàn hơn và khi được đánh thức nó sẽ vào việc rất nhanh

VD: trong lập trình ngôn ngữ C hàm main() là luồng chính. Khi chúng ta viết code cho nó thì đây là code điều khiển công việc cho luồng chính. Trong quá trình thực thi công việc thì nó có thể phát sinh nhiều luồng phụ khác tùy thuộc vào công việc của nó. Còn nếu nó không phát sinh luồng phụ thì tiến trình này chỉ có 1 luồng duy nhất.
VD:các luồng phụ giống nhau có chung mà: ví dụ 1 tiến trình chỉ toàn gồm các nhà sản xuất, và 1 tiến trình khác chỉ toàn các nhà tiêu thụ.

Ví dụ Web Server: lúc đầu Web Server sẽ có luồng chính của nó ở 1 server nào đó, nó sẽ tạo 100 luồng nhỏ và mỗi luồng nhỏ sẽ phục vụ cho 1 yêu cầu html. Khi có 1 yêu cầu được gửi đến thì luồng chính sẽ đánh thức 1 luồng nào đó để đáp ứng yêu cầu truy vấn trang web theo địa chỉ vừa được gửi tới, một lúc sau 1 trình duyệt nào đó lại gửi 1 địa chỉ khác thì luồng chính lại đánh thức 1 luồng khác để đáp ứng yêu cầu đó. Sau khi đáp ứng yêu cầu thì luồng đó sẽ được xếp vào tập luồng và ở trạng thái ngủ chờ yêu cầu tiếp theo . Nhưng khi tất cả các luồng đều được đánh thức và làm việc thì nếu có 1 yêu cầu mới thì yêu cầu này sẽ không được đáp ứng ngay mà phải chờ vì lúc này server đã bị quá tải, 1 lúc sau khi 1 luồng được giải phóng thì luồng này sẽ đáp ứng cho yêu cầu đang chờ.

VD khác: 1 đội quân được trang bị vũ khí sẵn sàng chiến đấu và chỉ cần nằm ngủ, chờ khi có địch đến, và khi có địch đến thì chỉ cần cử 1 chiến sỉ ra chiến đấu thôi, sau khi chiến đấu xong thì lại quay về ngủ tiếp.

SuspendThread():tạm ngừng công việc của luồng với mục quản cho trước ( làm cho luồng hiện hành chuyển sang trạng thái ngủ)
GetCurrentThread():lấy mục quản của luồng hiện hành. Dùng để truyền tiếp cho hàm SuspendThread.
Sleep(GettickCount()%5000): sau khi luồng hiện hành tiêu thụ xong sản phẩm sẽ ngủ vài giây( từ 0 -> 4999 ms)
GetTickCount: lấy số ms trôi qua kể từ khi hệ điều hành khởi động đến khi gọi hàm này.
ShowBuffer():sẽ đưa nội dung Buffer ra màng hình.
Handle: mục quản dung để điều khiển đối tượng tiến trình.
ID: mã số định danh.
HANDLE ProducerHandle1, ProducerHandle2;// 2 biến này dùng để lưu mục quản của nhà sản xuất thứ nhất và nhà sản xuất thứ 2.
HANDLE ConsumerHandle1, ConsumerHandle2; // 2 biến này dùng để lưu mục quản của nhà tiêu thụ thứ nhất và nhà tiêu thụ thứ 2.

DWORD ProducerID1, ProducerID2;
DWORD ConsumerID1, ConsumerID2;

// Tạo 2 luồng sản xuất trong trạng thái ngủ
ProducerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0, 4, &ProducerID1);
4: có nghĩa là luồng mới được tạo sẽ ngủ ngay

ProducerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0, 4, &ProducerID2);
//Tạo 2 luồng tiêu thụ thi hành ngay
ConsumerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0, 0, &ConsumerID1);
0: có nghĩa là luồng mới được tạo sẽ thi hành ngay

ConsumerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0, 0, &ConsumerID2);

ResumeThread: đánh thức luồng với mục quản cho trước.
CloseHandle(Producerhandle1): dùng để hủy luồng với mục quản cho trước. Chấm dứt công việc của nó.
Sleep(1): luồng chính chạy đến gặp lệnh này sẽ ngủ 1 ms rồi sẽ chạy tiếp( khống 1 chút ngừng 1 chút trước khi showbuffer -> kĩ thuật đồng bộ hóa công việc)

TranVuSang (I22B) 30/4/2013, 12:55

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

TrỉnhToQuyen(I12A) 2/5/2013, 22:18

Lần này thầy giới hạn từ bài 5 tới bài 8, bù lại phải trả lời cụ thể hơn những lần trước, có bạn nào giải bài tập round-bin, trình bày làm mẫu, giải thích cụ thể không, để mình biết cách trình bày nữa. bài tập thì làm nhưng không biết giải thích thêm cụ thể thế nào mới đúng được

Admin
- Hiểu về nó thế nào và Nghe/Xem được những gì hữu ích liên quan, thì cứ mạnh dạn viết ra !
- Chú ý: Nêu ví dụ minh hoạ từ đời thường !

NguyenMinhTam(I22B) 3/5/2013, 11:42

Lớp ơi,phần bài tập thì mình hiểu,nhưng phần giải thích chi tiết ,mình sợ ghi sót quá.lớp up bài chi tiết phần giải thích để mình tham khảo với

dangthihoangly(I12A) 3/5/2013, 16:58

Mình đã gọp các câu hỏi và 2 bài tập vào file này rồi. Các bạn vào đó down về xem. Nếu có chỗ nào sai thì pm giúp mình sửa lại nhé.
http://www.mediafire.com/view/?9luwp40ldq89bun
Chúc bạn có kì thi tốt

nguyenthithutrang (I11C) 3/5/2013, 22:42

Thanks ban nhiu nhe

TranVuSang (I22B) 3/5/2013, 23:39

Nói đến đồng bộ hóa tiến trình là nói đến sự chờ đợi của tiến trình này đối với tiến trình kia có nghĩa là công việc của nó bị hãm lại để nó cùng làm việc với 1 tiến trình khác, nhằm đảm bảo tính nhất quán của tài nguyên dùng chung ( tính đúng đắn, tính tuần tự, nối tiếp nhau, trước sau như 1 của các tiến trình ) và tránh được hiện tượng deadlock( hiện tượng kẹt tiến trình )
VD: khi thầy viết lên bảng “ thông dịch ≠ biên dịch “ nhưng thầy chỉ mới viết đến “thông dịch ≠ biên” mà 1 bạn đã vội lấy máy ảnh ra chụp lại mà ko chờ thầy viết xong thì ảnh của bạn chụp chỉ có “thông dịch ≠ biên” thì kết quả này ko có ý nghĩa gì hết.

PhamTuanChinh(I22B) 4/5/2013, 22:25

Cảm ơn bạn nhé. Chúc mọi người thi tốt.

NguyenVanNgoc65(I22A) 5/5/2013, 17:36

Vậy phải cố học thôi mấy bạn ạ!

LeThiKimNgan67(I11C) 7/5/2013, 10:10

Tập luồng:
1. Tiến trình cha tạo lập sẵn một tập luồng khi khởi động.
2. Các luồng trong tập luồng luôn sẵn sàng chờ công việc.
3. 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.
4. Phục vụ xong, luồng được đưa trả về tập luồng.
5. 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.

Ví dụ 1: Trong một lớp học, sẽ có một thầy giáo (tiến trình cha) và sẽ có nhiều học sinh gọi là (tập luồng)
Mọi học sinh luôn sẵn sàng nghe lời, mệnh lệnh của thầy giáo (sẵn sang chờ công việc)
Khi có cuộc thi học sinh giỏi do trường tô chức, ngày đầu tiên thi môn Văn thì thầy giáo sẽ chọn những học sinh giỏi môn Văn (một luồng) đi ra thi, tranh giải với lớp khác (luồng được đánh thức và đưa ra vận hành)
Trong khi đó, ngày thứ hai thi môn Toán( nhận thêm yêu cầu), thầy giáo sẽ cử nhóm học sinh giỏi môn Toán (một luồng) ra thi để giành chiến thắng (luồng được đánh thức và đưa ra vận hành). Sau khi thi xong và chiến thắng, giành được giải, tất cả học sinh giỏi đó về lớp học (luồng được trả về tập luồng)

Ví dụ 2: Trong một doanh trại quân đội sẽ có một tướng lĩnh (tiến trình cha) và sẽ có một đội binh (tập luồng).
Đội binh này sẽ sẵn sang chiến đấu khi có mệnh lệnh (sẵn sàng chờ công việc).
Khi có một tên địch đột nhập, Tướng lĩnh sẽ điều binh sĩ 1 (một luồng) đi bắt tên địch (một luồng được đánh thức và đưa vào vận hành).
Trong khi đó, lại có thêm một tên địch khác đột nhập (nhận thêm một yêu cầu), Tướng lĩnh sẽ điều binh sĩ 2 (một luồng) đi bắt địch (một luồng khác được đánh thức và đưa vào vận hành).
Sau khi bắt địch xong, binh sĩ sẽ trở về doanh trại (luồng được trả về tập luồng).

LeThiKimNgan67(I11C) 7/5/2013, 10:49

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 Running sang Waiting.
- Khi tiến trình cần thực hiện nhập xuất thì trình điều phối sẽ tìm kiếm một tiến trình khác để câp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.
2. Khi tiến trình chuyển từ Running sang Ready.
- Khi thời gian thực hiện của tiến trình vượt quá thời gian quy định (vì hệ điều hành chia thời gian) thì HĐH sẽ ngừng cấp CPU và đưa tiến trình vào Ready để cấp CPU cho một tiến trình khác. Trường hợp này có sự can thiệp của HĐH để lấy CPU => điều phối có tiếm quyền.
3. Khi tiến trình chuyền từ Waiting sang Ready.
- Sau khi quá trình nhập xuất đã xong, tiến trình lại được đưa vào hàng chờ. Lúc này HĐH sẽ kiểm tra xem có thể tiếp tục đưa tiến trình chờ đó chạy tiếp hay không? Nếu có sẽ cấp CPU cho tiến trình này tiếp tục làm việc. Trường hợp này có sự can thiệp của HĐH => điều phối có tiếm quyền.
4. Khi tiến trình kết thúc công việc.
- Sau khi tiến trình hoàn tất công việc thì tự trả CPU lại cho HĐH, HĐH sẽ tìm một tiến trình thích hợp khác để cấp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.

- Điều phối không tiếm quyền là khi tiến trình giữ CPU cho đến khi kết thúc hoặc chuyển sang trạng thái waiting mà không có sự can thiệp thu hồi CPU của HĐH.
- Điều phối có tiếm quyền là khi HĐH can thiệp để thu hồi CPU để cấp cho một tiến trình khác hoạt động.
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ếng quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến đang chạy, không cho độc chiếm CPU
Vd :
Ở một công ty, các nhân viên lần lượt được phân công đi công tác ở Đà Nẵng, Long An, Cần Thơ.
Không tiếm quyền : Anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Và anh ta lấy xe đi luôn, không có cách nào để công ty điều xe về ngay lập tức để cho người khác đi công tác.
Có tiếm quyền : Cũng anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Đi giữa đường thì anh A ghé vào quán nghĩ ngơi. Ngay lúc đó, công ty có lệnh điều xe về chở anh B đi công tác ở Long An. Xe lập tức quay về và chở anh B đi Long An. Giữa đường, anh B cũng ghé vào quán nghỉ ngơi. Và lúc đó, công ty lại có lệnh điều xe về chở anh C đi công tác ở Cần Thơ. Cứ thế xe được điều động cho 3 anh đi công tác !

TranBinhCongLuanI12A 10/5/2013, 15:18

Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một
lúc trong hệ thống:
1) Loại trừ tương hỗ(Mutual exclusion): ít nhất một tài nguyên phải được giữ trong chế độ
không chia sẻ; nghĩa là: chỉ một quá trình tại cùng một thời điểm có thể sử
dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình
yêu cầu phải tạm dừng cho đến khi tài nguyên được giải phóng.
2) Giữ và chờ cấp thêm tài nguyên (Hold and wait): quá trình phải đang giữ ít nhất một tài
nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi
quá trình khác.
3) Không có ưu tiên (No preemption): Các tài nguyên
không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý
bởi quá trình đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên (Circular wait): một tập hợp các quá
trình {P0, P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên
được giữ bởi P1, P1 đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ
tài nguyên đang được giữ bởi quá trình P0.

TranBinhCongLuanI12A 10/5/2013, 15:23

Hay quá!

NguyenVanTu(I22A) 15/5/2013, 09:01

Thanks bạn nhiều nhe!

NguyenMinhTam(I22B) 15/5/2013, 15:56

thank bạn nhiều nha

NguyenCaoDuong(I22B) 20/5/2013, 12:48

Cám ơn bạn nhiều.

TrỉnhToQuyen(I12A) 22/5/2013, 01:02

Thanks bạn nhiều

NguyenThiThom(I22A) 29/5/2013, 16:47

thanks bạn Very Happy

TrỉnhToQuyen(I12A) 9/6/2013, 22:10

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ì Need1 = 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

LeThanhQuang (I22B) 10/6/2013, 12:47

Thanks bạn nhiều nhiều....

HuynhHuuTai(I22A) 10/6/2013, 16:58

còn 2 tuần là chúng ta lên đường đi thi rồi dù 2 môn thi trước là bao rắc rối nhưng vẫn vào đây học hỏi môn này Very Happy

chuẩn bị tinh thần cho ngày 23/6 . Chúc mọi người thi tốt.

dangthihoangly(I12A) 12/6/2013, 10:04

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

- Ví dụ minh hoạ: Phòng bán vé tàu hoả ga Hòa Hưng có 5 cửa bán vé, và các người mua vé được xếp vào 5 cửa để chờ mua vé.
- Cửa số 1: dành cho những người system
- Cửa số 2: dành cho những người thương binh - mất sức lao động.
- Cửa số 3: dành cho những người bình thường.
- Cửa số 4: dành cho những người ưu tiên ở mức độ thấp hơn.
- và Cửa số 5: dành cho sinh viên - học sinh.

có thể có nhiều cửa bán vé với mức ưu tiên khác nhau, trong khi chỉ có 1 người bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua vé (các tiến trình) như người system (là người nhà họ hàng của ga Hòa Hưng), người mua bình thường, người mua là thương binh, nguời mất sức lao động,...(chỉ có 1 cô bán vé phải chạy đi chạy lại giữa 5 cửa)
Các bạn tham khảo và cho ý kiến thêm nhé

Sponsored content

Ôn tập thi Cuối kỳ