Tất cả các giải pháp mà chúng tôi đã thấy cho đến bây giờ đều nhằm cung cấp sự mutual exclusion với busy waiting. Tuy nhiên, việc chờ đợi bận rộn không phải là cách phân bổ tài nguyên tối ưu vì nó khiến CPU luôn bận rộn trong việc kiểm tra tình trạng của vòng lặp while liên tục mặc dù quá trình đang đợi phần quan trọng sẵn có.
Tất cả cơ chế đồng bộ hóa với chế độ busy waiting cũng đang gặp phải vấn đề priority inversion đó là luôn có khả năng quay lock bất cứ khi nào có một quá trình có mức độ ưu tiên cao hơn phải đợi bên ngoài phần quan trọng vì cơ chế dự định thực hiện lower priority process xử lý trong critical section.
Các bài viết liên quan:
Tuy nhiên những vấn đề này cần một giải pháp thích hợp mà không cần busy waiting và priority inversion.
Sleep và Wake (Nhà sản xuất Vấn đề người tiêu dùng)
Hãy xem xét mô hình cơ bản là Sleep và Wake. Giả sử rằng chúng ta có hai lệnh gọi hệ thống là Sleep và Wake . Quá trình gọi là ngủ sẽ bị chặn trong khi quá trình gọi sẽ được đánh thức.
Có một ví dụ phổ biến được gọi là vấn đề người tiêu dùng của nhà sản xuất , đây là vấn đề phổ biến nhất mô phỏng cơ chế Sleep và Wake .
Khái niệm về giấc Sleep và Wake rất đơn giản. Nếu phần quan trọng không trống thì quá trình sẽ chuyển sang trạng thái ngủ. Nó sẽ được đánh thức bởi quá trình khác hiện đang thực hiện bên trong phần quan trọng để quá trình có thể vào bên trong phần quan trọng.
Trong vấn đề người tiêu dùng của nhà sản xuất, chúng ta hãy nói rằng có hai quy trình, một quy trình viết một cái gì đó trong khi quy trình kia đọc cái đó. Quá trình đang viết một cái gì đó được gọi là nhà sản xuất trong khi quá trình đang đọc được gọi là người tiêu dùng .
Để đọc và ghi, cả hai đều sử dụng một bộ đệm. Đoạn mã mô phỏng cơ chế Sleep và Wake để cung cấp giải pháp cho vấn đề người tiêu dùng của nhà sản xuất được hiển thị bên dưới.
#define N 100 //maximum slots in buffer
#define count=0 //items in the buffer
void producer (void)
{
int item;
while(True)
{
item = produce_item(); //producer produces an item
if(count == N) //if the buffer is full then the producer will sleep
Sleep();
insert_item (item); //the item is inserted into buffer
countcount=count+1;
if(count==1) //The producer will wake up the
//consumer if there is at least 1 item in the buffer
wake-up(consumer);
}
}
void consumer (void)
{
int item;
while(True)
{
{
if(count == 0) //The consumer will sleep if the buffer is empty.
sleep();
item = remove_item();
countcount = count - 1;
if(count == N-1) //if there is at least one slot available in the buffer
//then the consumer will wake up producer
wake-up(producer);
consume_item(item); //the item is read by consumer.
}
}
}
Nhà sản xuất sản xuất vật phẩm và chèn nó vào bộ đệm. Giá trị của số lượng biến toàn cục đã tăng lên ở mỗi lần chèn. Nếu bộ đệm được lấp đầy hoàn toàn và không còn chỗ trống thì nhà sản xuất sẽ ngủ, nếu không nó sẽ tiếp tục chèn.
Về phía người tiêu dùng, giá trị của số lượng đã giảm đi 1 ở mỗi lần tiêu dùng. Nếu bộ đệm trống tại bất kỳ thời điểm nào thì người tiêu dùng sẽ ngủ ngược lại, nó tiếp tục tiêu thụ các mặt hàng và giảm giá trị của số lượng đi 1.
Người tiêu dùng sẽ được nhà sản xuất đánh thức nếu có ít nhất 1 mặt hàng có sẵn trong bộ đệm sẽ được tiêu thụ. Người sản xuất sẽ được người tiêu dùng đánh thức nếu có sẵn ít nhất một chỗ trống trong bộ đệm để nhà sản xuất có thể ghi chỗ đó.
Chà, vấn đề nảy sinh trong trường hợp khi người tiêu dùng sử dụng thuốc ngay trước khi họ chuẩn bị đi ngủ. Bây giờ người tiêu dùng không ngủ cũng không tiêu dùng. Vì nhà sản xuất không nhận thức được thực tế là người tiêu dùng không thực sự ngủ nên họ tiếp tục đánh thức người tiêu dùng trong khi người tiêu dùng không phản hồi vì họ không ngủ.
Điều này dẫn đến sự lãng phí của các cuộc gọi hệ thống. Khi người tiêu dùng được lên lịch một lần nữa, nó sẽ ngủ vì nó đã chuẩn bị ngủ khi nó được gọi trước.
Nhà sản xuất tiếp tục ghi vào bộ đệm và nó sẽ được lấp đầy sau một thời gian. Nhà sản xuất cũng sẽ ngủ vào thời điểm đó và lưu ý rằng người tiêu dùng sẽ đánh thức họ khi có một chỗ trống trong bộ đệm.
Người tiêu dùng cũng đang ngủ và không biết rằng nhà sản xuất sẽ đánh thức họ.
Đây là một dạng bế tắc mà cả nhà sản xuất và người tiêu dùng đều không hoạt động và chờ đợi nhau để đánh thức họ. Đây là một vấn đề nghiêm trọng cần được giải quyết.
Sử dụng Flags để giải quyết vấn đề này
Một bit cờ có thể được sử dụng để giải quyết vấn đề này. Nhà sản xuất có thể thiết lập bit khi nó gọi thức dậy vào lần đầu tiên. Khi người tiêu dùng đã lên lịch, nó sẽ kiểm tra bit.
Người tiêu dùng bây giờ sẽ biết rằng nhà sản xuất đã cố gắng đánh thức họ và do đó họ sẽ không ngủ và chuyển sang trạng thái sẵn sàng để tiêu thụ bất cứ thứ gì do nhà sản xuất sản xuất.
Giải pháp này chỉ áp dụng cho một cặp người sản xuất và người tiêu dùng, điều gì sẽ xảy ra nếu có n người sản xuất và n người tiêu dùng. Trong trường hợp đó, cần phải duy trì một số nguyên có thể ghi lại bao nhiêu cuộc gọi đánh thức đã được thực hiện và bao nhiêu người tiêu dùng không cần ngủ. Biến số nguyên này được gọi là semaphore. Chúng ta sẽ thảo luận chi tiết hơn về semaphore ở phần sau.
