Thảo luận những vấn đề liên quan đến Thi tốt nghiệp

Nội dung thảo luận:
1. Câu Lý thuyết
2. Câu Lập trình
3. Câu Bài tập

- 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, 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).

- Lập trình: 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), Lập trình đồng bộ hoá với Semaphore.

- Bài tập: 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.

Tham khảo:

Câu 1 (1 điểm)
Phân biệt thuật giải Multilevel Queue Scheduling với Multilevel Feedback Queue Scheduling. Cho các ví dụ minh hoạ.

Trả lời:
- 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,...

Câu 2 (1 điểm)
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.

Trả lời:
- 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);

Câu 3 (1 điểm)
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

Những tài liệu rất có ích. rất cám ơn thầy đã post bài. Còn thêm tài liệu hay....."Bí Quyết" nào nữa, nhờ thầy hướng dẫn ạh.

cám ơn thầy và chúc thầy sức khỏe.

Cám ơn thầy nhiều vì đã giúp tụi em hệ thống hoá lại phần nào để ôn thi tốt nghiệp cho tốt.
chúc thầy nhiều sức khoẻ và chúc các bạn thi thật tốt !

Cám ơn Thầy đã post chi tiết nội dung 2 buổi ôn thi để những bạn ko đi học được đầu đủ vẫn có thể nắm bắt được nội dung.
Hy vọng các bạn ôn tập & thi thật tốt để ko phụ lòng Thầy

Hôm trước đi ôn thầy có đọc cho chúng ta về Điều phối hàng chờ nhiều mức có điều tiết (MFQS).
Độ 0 : quantum =8
Độ 1 : quantum =16
Độ 2: FCFS
Bạn nào có chép thì post lại cho mình nhé, hôm đó chép mà để đâu mất tiu , hôm nay ôn bài ko có để học bài . Cám ơn các bạ bạn trước

phuc1984 đã viết:Hôm trước đi ôn thầy có đọc cho chúng ta về Điều phối hàng chờ nhiều mức có điều tiết (MFQS).
Độ 0 : quantum =8
Độ 1 : quantum =16
Độ 2: FCFS
Bạn nào có chép thì post lại cho mình nhé, hôm đó chép mà để đâu mất tiu , hôm nay ôn bài ko có để học bài . Cám ơn các bạ bạn trước

Đáp án:
- Đây là sơ đồ điều phối CPU của thuật giải MFQS dùng 3 hằng chờ Ready với các độ ưu tiên khác nhau (Độ 0 cao nhất, độ 2 thấp nhất theo quan niệm linux)
- Đầu tiên tiến trình được đưa vào hằng chờ thứ nhất (theo mũi tên đi vào). Khi cần thiết, nó sẽ đưa xuống hằng chờ với độ ưu tiên thấp hơn (theo đường mũi tên xuống dưới). Xong việc, tiến trình được đưa ra khỏi hệ thống (theo đường mũi tên ra ngoài).
- Chú ý: theo sơ đồ này, chỉ có hạ thấp tiến trình (không có đường mũi tên đi lên).
- Với các tiến trình trong hằng chờ độ 0, thuật giải điều phối được áp dụng là Round Robin (RRS) với thời lượng là 8ms (Quantium).
- Với các tiến trình trong hằng chờ độ 1, thuật giải điều phối được áp dụng là Round Robin (RRS) với thời lượng là 16ms (Quantium).
- Với các tiến trình trong hằng chờ độ 2, thuật giải điều phối được áp dụng là FCFS (First Come - First Served)
- Như vậy, ở đây có sự phối hợp của 3 thuật giải khác nhau là MFQS, RRS và FCFS.

Mình làm thử các câu còn lại không biết có đúng không, nhờ thầy và các bạn sửa giúp nhé!

1. So sánh đa luồng với đa tiến trình:

Đa Tiến Trình	Đa Luồng
• Tiến trình là chưong trình trong thời gian thực hiện, đặt dưới sự quản lý của hệ điều hành	• Luồng là tiến trình nhẹ, là đơn vị cơ bản sử dụng CPU
• Mỗi tiến trình dùng mã chưong trình khác nhau.	• Nhiều luồng có thể dùng chung 1 mã chưong trình
• Tiến trình có thể có 1 luồng chính với nhiều luồng phụ.
• 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: o Tạo tiến trình chậm hơn tạo luồng 30 lần o Chuyển ngữ cảnh tiến trình chậm hơn luồng 5 lần	• Luồng có thể dùng chung bộ nhớ với luồng cha và các luồng khác, nên việc tạo lập và chuyển ngữ cảnh cũng nhanh hơn
• Phải dùng các kỹ thuật truyền thông điệp để liên lạc giữa các tiến trình	• Không cần dùng kỹ thuật truyền thông điệp. Do tài nguyên là dùng chung.
• Khó nhân bản	• Dể nhân bản

2. Mục đích của Đồng bộ hoá công việc các tiến trình
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
- Tránh hiện tựong Deadlock ( hiện tựơng kẹt tiến trình)
3. Đoạn tương tranh
1. Giả sử có n tiến trình {P1, P2….Pn-1). Mỗi tiến trình có 1 đoạn mã gọi là đoạn tưong tranh, trong đó tiến trình có thễ truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên dùng chung.
4. Loại trừ tương hỗ
- Mỗi thời điểm chỉ có 1 tiến được phép truy cập và/ hoặc thay đổi tài nguyên dùng chung.
5. Hai ứng dụng của Semaphore (đèn hiệu)
1. Giải quyết vấn đề tương tranh
Mỗi tiến trình P1 bây giờ có cấu trúc.
Typedef int Semaphore;
Semaphore Mutex=1; // đèn hiệu nhị phân
While(1){
Remainder section; // Vùng còn lại
Wait(Mutex); // Vùng đăng nhập
Critical section ; // Vùng tưong tranh
Signal(Mutex) ; // Vùng đăng xuất
Remainder section; // Vùng còn lại
}
2. Giả sử P1 có mã s1, P2 có mã S2, cần tổ chức sao cho P2 chỉ thi hành sau P1.
Ta dùng đèn hiệu sau :
Semaphore synch=0 ;

Cấu trúc P1 .	Cấu trúc P2 .
S1	wait(synch)
Signal(synch)	S2