Các câu hỏi và lời giải chương 7

Các câu hỏi và lời giải chương 7

7.1. Tại sao cần phải đồng bộ hoá công việc các tiến trình?
a. Ví dụ mức vĩ mô.
b. Ví dụ mức vi mô.
Giải:
Mục đích của đồng bộ hoá công việc các tiến trình là đảm bảo Tính nhất quán của tài nguyên dùng chung và Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).




7.2. Cấu trúc mã của tiến trình tương tranh.
Giải:
while (1)
{
Remainder section
Entry section
Critical section
Exit section
Remainder section
}

7.3. Định nghĩa đèn hiệu với 2 tác nguyên Wait và Signal.
Giải:
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề 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.4. Sử dụng Đèn hiệu nhị phân Mutex để đảm bảo tính loại trừ lẫn nhau.
Giải:
typedef int semaphore;
semaphore mutex = 1; // Binary Semaphore
while (1)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}

7.5. Sử dụng Đèn hiệu Synch để đồng bộ 2 tiến trình.
Giải:
Xét hai process: P1 và P2
Yêu cầu: lệnh S1 trong P1 cần được thực thi trước lệnh S2 trong P2
Định nghĩa semaphore “synch” dùng đồng bộ
Khởi động semaphore:
synch.value= 0
Để đồng bộ hoạt động theo yêu cầu, P1 phải định nghĩa như sau:
S1;
signal(synch);
Và P2 định nghĩa như sau:
wait(synch);
S2;

7.6. Thực thi Đèn hiệu có hàng chờ.
Giải:
- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm cho các tiến trình có thể tự khóa mình (Block Itseft) và chuyển sang trạng thái waiting, sau đó xếp vào hàng chờ của đèn hiệu. Trình điếu phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.
- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựa chọn và đánh thức bằng lệnh WakeUp(P) để chuyển P từ trạng thái Waiting sang trạng thái Ready. Lúc này trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào thuật giải cụ thể.

7.7. Phát biểu bài toán Sản Xuất – Tiêu Thụ. Sử dụng đèn hiệu để đồng bộ hoá.
Giải:
Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0.
– Dữ liệu chia sẻ:
SEMAPHORE full, empty, mutex;
– Khởi tạo:
full = 0;
empty = BUFFER_SIZE;
mutex = 1;



















7.8. Phát biểu bài toán Dining-Philosophers.
Giải:
Có 5 triết gia ngồi ăn trên một bàn tròn và suy nghĩ
Mỗi người cần 2 chiếc đũa để ăn
Trên bàn chỉ có 5 chiếc đũa xếp xoay vòng và xen kẽ mỗi người.
Người nào cầm đủ hai chiếc đũa sẽ được ăn.
Bài toán này minh hoạ sự khó khăn trong việc phân phối tài nguyên giữa các process sao cho không xảy ra deadlock và starvation

7.9. Phân tích thuật giải sai bài toán Dining-Philosophers (dẫn đến Deadlock).
Giải:
Dữ liệu chia sẻ:
semaphore chopstick[5];
Khởi đầu các biến đều là: 1.
while (1)
{
wait(chopstick[i])
wait(chopstick[(i+1) % 5 ] )
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5] );
…
think
…
}
Giải pháp trên có thể gây ra deadlock
Khi tất cả triết gia đói bụng cùng lúc và đồng thời cầm một chiếc đũa bên tay trái  deadlock
Có thể xảy ra trường hợp ách vô hạn định (starvation).

7.10. Phân tích thuật giải đúng bài toán Dining-Philosophers (dùng đèn hiệu).
Giải:


7.11. Những phương tiện đồng bộ hoá trong Windows NT/2000/XP/2003.
Giải:
HANDLE s;
s = CreateSemaphore(0, n, max, t); //t là tên đèn hiệu hoặc để giá trị 0.
WaitForSingleObject(s, timeout); //timeout = INFINITE hoặc số mili giây chờ.
RealeaseSemaphore(s, 1, NULL);

7.12. Những phương tiện đồng bộ hoá trong UNIX/Linux.
Giải:
sem_t s;
sem_init(&s, 0, n);
sem_wait(&s);
sem_post(&s);

Bạn ơi, bạn có thể uoload file lên host luôn ko bạn, chứ bạn để như vậy thì một số hình bạn post lên không thấy được và một số ký tự bị mã hóa hoặc không thể hiển thị lên được.