Cac ban tham khao 1 so cau hoi On tap mon HDH

Cac ban tham khao 1 so cau hoi On tap mon HDH

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

Câu2: So sánh luồng với tiến trình.
Giải:
- Tiến trình (Process) là chuơng trình trong thời gian thực hiện (đặt dưới sự quản lý của HĐH).
- Luồng (Thread) còn gọi là tiến trình nhẹ (LWP-Light Weight Process), một đơn vị cơ bản sử dụng CPU.
- Luồng cũng có thông tin trạng thái như của tiến trình truyền thống (HWP- Heavy Weight Process).
- Tiến trình có thể có một luồng chính với nhiều luồng phụ. Mỗi luồng có khả năng chia sẻ tài nguyên với các luồng khác trong tiến trình.
- Nhiều luồng có thể cùng chung một mã chương trình

Câu 3: Phân biệt đa luồng và đa tiến trình?
Giải:
Giống nhau:
- Đều có thông tin trạng thái
- Luồng cũng là tiến trình nhưng là tiến trình nhẹ (Light Weigh Process)
- Đa luồng hay đa tiến trình có thể liên quan đến một chương trình.
- Chia sẻ tài nguyên cho nhau, tăng tốc tính toán, đảm bảo tính đơn thể.

Khác nhau:
- Do luồng cùng vận hành trong 1 vùng địa chỉ, vì vậy dễ dùng chung tài nguyên hơn đa tiến trình
Ví dụ: mượn đồ trong gia đình dễ mượn đồ hơn của hàng xóm
- Do luồng chung tài nguyên với luồng cha nên việc tạo lập và chuyển đổi ngữ cảnh cũng nhanh hơn tiến trình
Ví dụ: Việc ngăn phòng riêng ra trong nhà thì dễ hơn việc xây thêm một nhà khác.
- Cấp phát tài nguyên bộ nhớ cho tiến trình khá tốn kém.
- Lập trình đa luồng thì dễ hơn lập trình đa tiến trình

Câu 4: Nguyên lý tập luồng.
Giải:
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.

Câu 5: Ứng dụng đèn hiệu.
Giải:
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


Câu 6: Lợi ích của đa luồng.
Giải:
1. 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ề).
2. 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.
3. 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.
4. 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.

Câu 7: Nêu 5 tiêu chí điều phối CPU
Giải:
Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
Thông suất hệ thống (Throughput): Số tiến trình (TT) hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

Câu 8: Phân biệt điều phối có tiếm quyền (Preemtive Scheduling) và không tiếm quyền (Non-Preemtive Scheduling).
Giải:
Giống nhau:
Được dùng trong điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thá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 tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.
- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

Câu 9: Phân biệt tối thiểu độ lệch thời gian đáp ứng và tối thiểu thời gian đáp ứng trung bình.

Câu 10: Phân biệt 2 giải thuật MQS và MFQS. Cho ví dụ minh họa.
Giải:
Giống nhau: 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 toán 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é máy bay 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âu11: Phát biểu bài toán sản xuất tiêu thụ
Giải:
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).

- Thuật giải Producer:
wait(semEmpty);
wait(Mutex);
// Đưa sản phẩm vào Buffer
..........................
signal(semFull);
signal(Mutex);

- Thuật giải Consumer:
wait(semFull);
wait(Mutex);
// Lấy sản phẩm từ Buffer
..........................
signal(semEmpty);
signal(Mutex);

Câu 12: Phân tích khái niệm Critical Section và ứng dụng đèn hiệu semaphore để đảm bảo tính loại trừ tương hỗ về phương diện thời gian và tài nguyên dung chung. Cho ví dụ minh họa.
Giải:
Kết hợp câu 1 và câu 5

Câu 13: Trình bày cách lập trình đồng bộ hóa công việc 3 tiến trình P1, P2, P3 sao cho P1 trước P2, P3 vào cùng lúc.
Giải:
Giả sử P1 có mã S1 , P2 có mã S2 , P3 có mã S3 cần tổ chức như yêu cầu
Ta dùng đèn hiệu như sau:
semaphore synch = 0;
Cấu trúc P1 : Cấu trúc P2 : Cấu trúc P3 :
S1 wait (synch); wait(synch);
signal (synch); S2 S3

Câu 14: Trình bày cách lập trình đồng bộ hóa công việc 3 tiến trình P1, P2, P3 sao cho P1 trước, tới P2 vào rồi mới tới P3 vào.
Giải:
Giả sử P1 có mã S1 , P2 có mã S2 , P3 có mã S3 cần tổ chức như yêu cầu
Ta dùng đèn hiệu như sau:
semaphore synch1 = 0, synch2 = 0;
Cấu trúc P1 : Cấu trúc P2 : Cấu trúc P3 :
S1 wait (synch1); wait(synch2);
signal (synch1); S2 S3
signal(synch2)

Câu 15: Tạo một tập luồng gồm 100 nhà sản xuất và 50 nhà tiêu thụ.
Giải:
// Tạo 100 luồng các nhà sản xuất ở trạng thái Suspend
for(int i = 1; i <= 100; i++)
{
HANDLE ProducerHandlei;
DWORD ProducerIDi;
ProducerHandlei=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Producer, (void *) i, 4, &ProducerIDi);
}

// Tạo 50 luồng các nhà tiêu thụ ở trạng thái Suspend
for(int i = 1; i <= 50; i++)
{
HANDLE ConsumerHandlei;
DWORD ConsumerIDi;
ConsumerHandlei=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)Consumer, 0, 4, &ConsumerIDi);
}