Đề thi tốt nghiệp Môn Hệ Điều Hành đợt 2 năm 2010

Mình vừa được 1 ông anh mới thi xong tốt nghiệp cho mình đề thi này, nên mình post lên cho các bạn cùng kham khảo.

Câu 1: Phân tích khái niệm Critical Section và ứng dụng Semaphore để đảm bảo tính loại trừ tương hổ về phương diện thời gian, với tài nguyên dùng chung. ho Ví dụ minh họa.

Câu 2: Biết rằng, chương trình thực thi bài toán Producer-Consumer viết bằng VC++ 6.0 có sử dụng đối tượng CritSec theo mẫu:


CRITICAL_SECTION critSec;
InitializeCriticalSection(&critSec);
EnterCricalSection(&critSec);
// Đoạn tương tranh (miền găng)
LeaveCriticalSection(&critSec);
DeleteCriticalSection(&critSec);

Hãy chuyển đoạn mã trên sang cách dùng Semaphore.

Câu 3: 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 CPU-Burst
P1 0 30
P2 15 13
P3 20 6

Bài toán sử 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 gian chờ trung bình của các tiến trình

Và mình xin được phép trả lời câu 3 của bài này như sau, nếu có sai thì nhờ thầy và các bạn sửa giúp mình nhé:
a/ Biểu đồ Gannt

...P1...........P2.............P3.................P2.....................P1.......
|-------|----------|------------|-------------|-----------------|
0........15...........20...............26................34.....................49

b/ Thời gian chờ trung bình:
P1: 0+34-15=19
P2:0+26-20=6
P3=0

t=(19+6+0)/3=25/3

Admin
Chính xác "Tuyệt đối". Chúc mừng em ! Nhưng nên "Chia" để có kết quả cuối cùng (mà chia "sai" thì mấy điểm nhỉ?)

Mình vừa giải thử Câu 3, và có cùng đáp án với bạn greatpoet85. Cám ơn bạn đã post đề thi.
Mình đang giải thử Câu 1 và Câu 2, khi nào xong mình sẽ up lên cho mọi người cùng xem nhé!

greatpoet85 đã viết:Và mình xin được phép trả lời câu 3 của bài này như sau, nếu có sai thì nhờ thầy và các bạn sửa giúp mình nhé:
a/ Biểu đồ Gannt

...P1...........P2.............P3.................P2.....................P1.......
|-------|----------|------------|-------------|-----------------|
0........15...........20...............26................34.....................49

b/ Thời gian chờ trung bình:
P1: 0+34-15=19
P2:0+26-20=6
P3=0

t=(19+6+0)/3=25/3

Admin
Chính xác "Tuyệt đối". Chúc mừng em ! Nhưng nên "Chia" để có kết quả cuối cùng (mà chia "sai" thì mấy điểm nhỉ?)

Thanks ban nhieu nha!

Câu1: Khái niệm đoạn tương tranh, loại trừ lẫn nhau.
Giải:
- Giả sử có n tiến trình { P0 , P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên chung.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

* Ứng dụng đèn hiệu.

Giải quyết vấn đề Đoạn Tương Tranh.
Mã của tiến trình Pi 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
}
Giả sử P1 có mã S1 , P2 có mã S2 , cần tổ chức sao cho S2 chỉ thi hành sau S1 .
Ta dùng đèn hiệu như sau:
semaphore synch = 0;
Cấu trúc P1 : Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2

Bạn ơi còn đề môn Thuật giải và web nữa,up lên luôn đi,cho mọi người tham khảo.Thanks bạn nhìu

Đề thi Tốt nghiệp môn Thuật Giải

Câu 1.
Trong một ứng dụng tin học để quản lý nhân viên của 1 công ty , cấu trúc dữ liệu gồm: mã số (code) , tuổi (age), và tên (name), được lưu trữ bởi một danh sách liên kết đơn
a. Viết một giải thuật đệ qui, in ra tên của các nhân viên có tuổi bằng h. (0.5d)
b. Viết giải thuật tính tuổi trung bình của các nhân viên trong công ty. (0.5d)

Câu 2.
a. Cho đồ thị vô hướng G(V,E). Viết một giải thuật tính bậc của một đỉnh v của đồ thị G (1d)
b. Tính độ phức tạp (theo O-lớn ) của giải thuật đã viết ở câu a. (0.5d)

Câu 3.
a. Viết giải thuật thực hiện theo tác PARTITION(A,p,r) trả về q để phân hoạch mảng A[p....r] thành 2 mảng con A[p.....q-1] và A[q+1...r] có các phần tử tương ứng lớn hơn hoặc bằng A[q] và nhỏ hơn A[q]. (0.5d)
b.Tính độ phức tạp của giải thuật trong trường hợp xấu nhất. (0.5d)

Còn môn công cụ Web thì khá đơn giản nhưng do dài quá nên mình sẽ post lên sau nha

greatpoet85 đã viết:Đề thi Tốt nghiệp môn Thuật Giải

hay wa minh fai giai thu moi dc
thank nhiu nhan

@greatpoet85: bài thuật giải thì bạn nên lập topic khác nhé, topic này mình thấy nên tập trung đề môn HĐH thôi, như thế sẽ dễ cho mọi người theo dõi hơn.
Thân

greatpoet85 đã viết:Và mình xin được phép trả lời câu 3 của bài này như sau, nếu có sai thì nhờ thầy và các bạn sửa giúp mình nhé:
a/ Biểu đồ Gannt

...P1...........P2.............P3.................P2.....................P1.......
|-------|----------|------------|-------------|-----------------|
0........15...........20...............26................34.....................49

b/ Thời gian chờ trung bình:
P1: 0+34-15=19
P2:0+26-20=6
P3=0

t=(19+6+0)/3=25/3

Admin
Chính xác "Tuyệt đối". Chúc mừng em ! Nhưng nên "Chia" để có kết quả cuối cùng (mà chia "sai" thì mấy điểm nhỉ?)

Thanks ban greatpoet85 da cung cap duoc nhung de thi, dong thoi cho dap an dung nua./

Cảm ơn bạn đã cung cấp bài tập và đáp án nữa

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

Cám ơn các bạn đã post bài

Mình cũng giải thử Câu 3, mà mình cũng thấy nó có chung đáp án với greatpoet85. mình Cám ơn bạn đã post đề thi nhiều nha,tại vì khi mình nhìn vô thấy câu ba tah6y1 nó wen nên mình giải thử một câu thử nó có giống đáp án ko ,nhưng mình thấy nó giống hiiiii

Kinh te Tin Kinh te

cám ơn bạn nhiều nha.....