Bai tham khao on tap thi Tot Nghiep mon HDH

Ôn thi tốt nghiệp
Hệ Điều Hành
Những nội dung trọng tâm:

- Lý thuyết: So sánh Đa luồng với Đa tiến trình, Những ích lợi của công nghệ Đa luồng, Nguyên lý Tập luồng (Thread Pools), Mục đích của Đồng bộ hoá công việc các tiến trình, Đoạn tương tranh, Loại trừ tương hỗ, Hai ứng dụng của Semaphore (đèn hiệu), Lập trình Bài toán Sản xuất-Tiêu thụ dùng semFull-semEmpty-CritSec, Bốn tình huống ra quyết định của trình điều phối CPU, Phân biệt Preemptive Scheduling với Non-Preemptive Scheduling, Điều phối hàng chờ nhiều mức (MQS), Điều phối hàng chờ nhiều mức có điều tiết (MFQS).

- Bài tập: Sử dụng Visual C++ 6.0 để tạo một tập luồng (bằng hàm CreateThread) và đánh thức chúng khi cần thiết (bằng hàm ResumeThread), Thuật giải điều phối CPU (Preemptive SJFS, Round-Robin): Biểu đồ Gantt và tính thời gian chờ trung bình của các tiến trình.
I . Lý thuyết
1. So Sánh đa luồng với đa tiến trình ?
Tieán trình (Process) laø chuông trình trong thôøi gian thöïc hieän (ñaët döôùi söï quaûn lyù cuûa HÑH).
Luoàng (Thread) coøn goïi laø tieán trình nheï (LWP-Light Weight Process), moät ñôn vò cô baûn söû duïng CPU.
Luoàng cuõng coù thoâng tin traïng thaùi nhö cuûa tieán trình truyeàn thoáng (HWP- Heavy Weight Process).
Tieán trình coù theå coù moät luoàng chính vôùi nhieàu luoàng phuï. Moãi luoàng coù khaû naêng chia seû taøi nguyeân vôùi caùc luoàng khaùc trong tieán trình.
Nhieàu luoàng coù theå cuøng chung moät maõ chöông trình

2. Những ích lợi của công nghệ Đa luồng
1. Khaû naêng ñaùp öùng (Responsiveness) toát hôn: Trong khi moät luoàng bò aùch hoaëc quaù baän, luoàng khaùc vaãn vaän haønh bình thöôøng (Luoàng chính cuûa trình duyeät vaãn töông taùc vôùi ngöôøi duøng trong khi döõ lieäu ñöôïc laáy veà).
2. Chia seû taøi nguyeân (Resource Sharing): Theo maëc ñònh, caùc luoàng coù theå duøng chung boä nhôù vaø taøi nguyeân cuûa luoàng cha. Vaøi luoàng cuøng vaän haønh trong 1 vuøng ñòa chæ, do ñoù deã duøng chung taøi nguyeân hôn so vôùi tröôøng hôïp ña tieán trình.
3. Tieát kieäm (Economy): Caáp phaùt boä nhôù vaø taøi nguyeân cho tieán trình laø coâng vieäc toán keùm. Do luoàng chung taøi nguyeân vôùi cha vaø caùc luoàng khaùc, vieäc taïo laäp vaø chuyeån ngöõ caûnh cuõng nhanh hôn (Solaris 2: Taïo tieán trình chaäm hôn 30 laàn, Chuyeån ngöõ caûnh chaäm hôn 5 laàn).
4. Taän duïng ñöôïc theá maïnh cuûa kieán truùc ña xöû lyù: Ña luoàng laøm taêng tính song song treân heä maùy nhieàu CPU. Moãi luoàng coù theå chaïy bôûi CPU rieâng.

3. Nguyên lý Tập luồng (Thread Pools)?
Tập luồng (Thread Pools):
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.
4. Mục đích của Đồng bộ hoá công việc các tiến trình là:
Tận duïng toái ña CPU
Toái ña Coâng suaát vaø Thoâng suaát.
Toái thieåu Toång thôøi gian, Thôøi gian chôø vaø Thôøi gian ñaùp öùng.

5. Đoạn tương tranh, Loại trừ tương hỗ:
Giaû söû coù n tieán trình { P0 , P1 , ... , Pn-1 }. Moãi tieán trình coù ñoaïn maõ goïi laø Ñoaïn töông tranh ( ÑTT ) trong ñoù tieán trình coù theå truy caäp vaø thay ñoåi vuøng nhôù, taäp tin hay taøi nguyeân chung.
Tính Loaïi tröø laãn nhau hay Loaïi tröø töông hoã (Mutual Exclusion) veà phöông dieän thôøi gian: Khi coù 1 tieán trình ñang ôû trong ÑTT cuûa noù thì khoâng coù tieán trình naøo khaùc trong nhoùm cuõng taïi ñoaïn nhö vaäy, nghóa laø: Moãi thôøi ñieåm chæ coù 1 tieán trình ñöôïc pheùp truy caäp vaø/hoaëc thay ñoåi taøi nguyeân chung.
Caùc tieán trình töông tranh coù caáu truùc maõ bao goàm Entry Section (Ñoaïn Ñaêng nhaäp), Critical Section (Ñoaïn Töông tranh), Exit Section (Ñoaïn Ñaêng xuaát) vaø caùc Remainder Section (Ñoaïn Coøn laïi).

6.Hai ứng dụng của Semaphore (đèn hiệu)
Phương tiện đồng bộ hoá được đề 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).

7. Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 3 đèn hiệu semFull, semEmpty và Mutex.

- Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng.

- Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.

- Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.

- Thuật giải đồng bộ hoá bằng 3 đèn hiệu: semFull (quản lý số sản phẩm có trong bộ đệm, giá trị ban đầu bằng 0), semEmpty (quản lý số khoang còn trống, giá trị ban đầu bằng số khoang của bộ đệm) và Mutex (đảm bảo tính loại trừ tương hỗ, nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/cập nhật tài nguyên dùng chung, giá trị ban đầu bằng 1).

o Thuật giải cho Producer:

wait(semEmpty);

wait(Mutex);

// Đưa sản phẩm vào Buffer
..........................

signal(semFull);

signal(Mutex);

o Thuật giải cho Consumer:

wait(semFull);

wait(Mutex);

// Lấy sản phẩm từ Buffer

..........................

signal(semEmpty);
signal(Mutex);

8. Lập trình Bài toán Sản xuất-Tiêu thụ dùng semFull-semEmpty-CritSec
- Giả sử có bộ nhớ đệm BUFFER bao gồm các khoảng Item được tiến trình Producer lần lược đưa các sản phẩm S1, S2… Sn vào. Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.
- Công việc của Producer phải đồng bộ với Consumer, không được đưa sản phẩm vào khi Buffer đầy và lấy sản phẩm ra khi chưa có .
Buffer









Đồng bộ hóa bằng 2 đèn hiệu ( Semophone)
Ta dùng 2 đèn hiệu SemFull và SemEmpty
SemFull : kiểm tra số Sản phẩm trong bộ đệm.
SemEmpty: Kiểm tra số vùng trống trong bộ đệm.
Hai tác nguyên: Wait và Signal
Producer()
{ // Chờ khi bộ đệm đầy
WaitforSignal(SemFull,INITE)
//Sản xuất sản phẩm
Releave(SemEmpty)
//Bộ đệm đã có Sản phẩm
}
Consumer()
{ // Chờ đến khi có sản phẩm
WaitforSignal(SemEmpty ,INITE)
//tiêu thụ sản phẩm
Releave(SemFull)
//Bộ đệm đã có chổ trống
}

9. Bốn tình huống ra quyết định của trình điều phối CPU
Caùc tình huoáng ra quyeát ñònh cuûa trình ñieàu phoái:
1. Khi tieán trình chuyeån töø Running sang Waiting (chôø I/O, chôø tieán trình con)
2. Khi tieán trình chuyeån töø Running sang Ready (do ngaét xaûy ra)
3. Khi tieán trình chuyeån töø Waiting sang Ready (khi keát thuùc I/O)
4. Khi tieán trình keát thuùc coâng vieäc.
Sô ñoà ñieàu phoái chæ tieán haønh trong tình huoáng 1 vaø 4 ñöôïc goïi laø Ñieàu phoái Khoâng tieám quyeàn (Non-Preemptive): Tieán trình giöõ CPU cho ñeán khi keát thuùc bình thöôøng hoaëc khi chuyeån sang traïng thaùi Waiting (caùch laøm trong Windows 3.1 vaø Macintosh OS). Duøng khi maùy khoâng coù Timer.
Sô ñoà ñieàu phoái tieán haønh trong caû 4 tình huoáng ñöôïc goïi laø Ñieàu phoái Coù tieám quyeàn (Preemptive).

10. Phân biệt Preemptive Scheduling với Non-Preemptive Scheduling
- Giống nhau: cùng điều phối CPU (choïn tieán trình trong Ready Queue ñeå caáp thôøi gian CPU (chuyeån sang traïng thaùi Running)).
- Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.
- Non-Preemptive Scheduling: Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1 , sau đó mới thực hiện tiến trình P2 (caùch laøm trong Windows 3.1 vaø Macintosh OS)
- Preemptive Scheduling : có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình

11. Phân biệt thuật giải Multilevel Queue Scheduling với Multilevel Feedback Queue Scheduling. Cho các ví dụ minh hoạ.

- 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ả 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 mua bình thường, người mua là thương binh, nguời mất sức lao động,...

II . Phần bài tập:
1. Dùng thuật giải Round-Robin
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:

Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để điều phối CPU:

a. Thể hiện bằng biểu đồ Gantt (0,5 điểm)

b. Tính thời gian chờ trung bình của các tiến trình (0,5 điểm)

Trả lời:

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:

- Thời gian chờ của các tiến trình:

P1 = 35 ms

P2 = 2 ms

P3 = 22 ms

Thời gian chờ trung bình = ( 35 2 22 ) / 3 = 59 / 3 = 19,66 ms

2. Dùng thuật giải FJFS có tiếm quyền:
Lưu ý : Nếu các khoảng CPU bằng nhau thì các TT nào có thời điểm đến trước thì chạy trước.


Chúc các bạn thi tốt.