Giáo trình Hệ điều hành Giáo dục từ xa - Chương 5: Đồng bộ hoá quá trình - Nguyễn Phú Trường

Nội dung text: Giáo trình Hệ điều hành Giáo dục từ xa - Chương 5: Đồng bộ hoá quá trình - Nguyễn Phú Trường

1. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Do đó, nó tiếp tục vòng lặp trong câu lệnh while cho đến khi Pi rời khỏi vùng tương trục Pi. Giải thuật trên đảm bảo rằng yêu cầu về tiến trình, chờ đợi có giới hạn và đảm bảo sự công bằng, vì các quá trình đi vào miền tương trục dựa trên cơ sở tới trước được phục vụ trước. V.1.3 Phần cứng đồng bộ hoá Như các khía cạnh khác của phần mềm, các đặc điểm phần cứng có thể làm các tác vụ lập trình dễ hơn và cải tiến tính hiệu quả của hệ thống. Trong phần này, chúng ta trình bày một số chỉ thị phần cứng đơn giản sẳn dùng trên nhiều hệ thống và trình bày cách chúng được dùng hiệu quả trong việc giải quyết vấn đề miền tương trục. boolean TestAndSet( boolean &target){ boolean rv = target; target = true; return rv; } Hình 0-7 Định nghĩa của chỉ thị TestAndSet Vấn đề miền tương trục có thể được giải quyết đơn giản trong môi trường chỉ có một bộ xử lý nếu chúng ta cấm các ngắt xảy ra khi một biến chia sẻ đang được thay đổi. Trong cách này, chúng ta đảm bảo rằng chuỗi chỉ thị hiện hành có thể được cho phép thực thi trong thứ tự không trưng dụng. Không có chỉ thị nào khác có thể chạy vì thế không có bất cứ sự thay đổi nào có thể được thực hiện trên các biến được chia sẻ. Tuy nhiên, giải pháp này là không khả thi trong một môi trường có nhiều bộ xử lý. Vô hiệu hoá các ngắt trên đa bộ xử lý có thể mất nhiều thời gian khi một thông điệp muốn truyền qua tất cả bộ xử lý. Việc truyền thông điệp này bị trì hoãn khi đi vào miền tương trục và tính hiệu quả của hệ thống bị giảm. Do đó nhiều máy cung cấp các chỉ thị phần cứng cho phép chúng ta kiểm tra hay thay đổi nội dung của một từ (word) hay để thay đổi nội dung của hai từ tuân theo tính nguyên tử (atomically)-như là một đơn vị không thể ngắt. Chúng ta có thể sử dụng các chỉ thị đặc biệt này để giải quyết vấn đề miền tương trục trong một cách tương đối đơn giản. Chỉ thị TestAndSet có thể được định nghĩa như trong hình V.-7. Đặc điểm quan trọng của chỉ thị này là việc thực thi có tính nguyên tử. Do đó, nếu hai chỉ thị TestAndSet được thực thi cùng một lúc (mỗi chỉ thị trên một CPU khác nhau), thì chúng sẽ được thực thi tuần tự trong thứ tự bất kỳ. do{ while (TestAndSet(lock)); Critical section lock:= false remainder section } while (1); Hình 0-8: Cài đặt loại trừ hỗ tương với TestAndSet Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 89
2. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Cấu trúc dữ liệu thông thường là: boolean waiting[n]; boolean lock; Cấu trúc dữ liệu này được khởi tạo tới false. Để chứng minh rằng loại trừ hỗ tương được thoả, chúng ta chú ý rằng quá trình Pi có thể đưa vào miền tương trục chỉ nếu hoặc waiting[i] ==false hay key == false. Giá trị của key có thể trở thành false chỉ nếu TestAndSet được thực thi. Đối với quá trình đầu tiên, để thực thi TestAndSet sẽ tìm key == false; tất cả quá trình khác phải chờ. Biến waiting[i] có thể trở thành false chỉ nếu quá trình khác rời khởi miền tương trục của nó; chỉ một waiting[i] được đặt false, duy trì yêu cầu loại trừ hỗ tương. Để chứng minh yêu cầu tiến trình được thoả, chúng ta chú ý rằng các đối số được hiện diện cho việc loại trừ hỗ tương cũng áp dụng được ở đây, vì thế một quá trình thoát khỏi miền tương trục hoặc đặt lock bằng false hay đặt waiting[j] bằng false. Cả hai trường hợp đều cho phép một quá trình đang chờ để đi vào miền tương trục được xử lý. Để chứng minh yêu cầu chờ đợi được giới hạn được thoả, chúng ta chú ý rằng khi một quá trình rời miền tương trục của nó, nó duyệt qua mảng waiting trong thứ tự tuần hoàn (i + 1, i + 2, , n – 1, 0, , i - 1). Nó định rõ quá trình đầu tiên trong thứ tự này mà thứ tự đó ở trong phần đi vào (waiting[j] == true) khi quá trình tiếp theo đi vào miền tương trục. Bất cứ quá trình nào đang chờ để đi vào miền tương trục sẽ thực hiện n – 1 lần. Tuy nhiên, đối với người thiết kế phần cứng, cài đặt các chỉ thị nguyên tử TestAndSet trên bộ đa xử lý không là tác vụ thử nghiệm. Những giải pháp trên đều phải thực hiện một vòng lặp để kiểm tra liệu nó có được phép vào miền tương trục hay không. Nếu điều kiện chưa thoả, quá trình phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc quá trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền tương trục như thế được gọi là các giải pháp chờ đợi bận “busy waiting”. Lưu ý, việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy quá trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hoá là nên tránh các giải pháp chờ đợi bận. V.2 Các giải pháp “SLEEP and WAKEUP” Để loại bỏ các bất tiện của của giải pháp chờ đợi bận, chúng ta có thể tiếp cận theo hướng cho một quá trình chưa đủ điều kiện vào miền tương trục chuyển sang trạng thái nghẽn, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái quá trình. Hai thủ tục cơ bản SLEEP và WAKEUP thường được sử dụng cho mục đích này. SLEEP là một lời gọi hệ thống có tác dụng làm “nghẽn” (blocked) hoạt động của quá trình gọi nó và chờ đến khi được một tiến trình khác “đánh thức”. Lời gọi hệ thống WAKEUP nhận một tham số duy nhất: quá trình sẽ được kích hoạt trở lại (đặt về trạng thái sẳn sàng). Ý tưởng sử dụng SLEEP và WAKEUP như sau: khi một quá trình chưa đủ điều kiện vào miền tương trục, nó gọi SLEEP để tự khoá đến khi có một quá trình khác gọi WAKEUP để giải phóng nó. Một quá trình gọi WAKEUP khi ra khỏi miền tương trục để đánh thức một quá trình đang chờ, tạo cơ hội cho quá trình này vào miền tương trục. int busy; // 1 nếu miền tương trục đang bị chiếm int blocked; // đếm số lượng quá trình đang bị khoá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 91
3. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Những sửa đổi đối với giá trị integer của semaphore trong các thao tác wait và signal phải được thực thi không bị phân chia. Nghĩa là khi một quá trình sửa đổi giá trị semaphore, không có quá trình nào cùng một lúc có thể sửa đổi cùng biến semaphore đó. Ngoài ra, trong trường hợp của biến wait(S), kiểm tra giá trị integer của S (S ≤ 0) và sửa đổi có thể của nó (S ) cũng phải được thực thi mà không bị ngắt. .V.2.1.1 Cách dùng Chúng ta có thể sử dụng semaphores để giải quyết vấn đề miền tương trục với n quá trình. N quá trình chia sẻ một biến semaphore, mutex (viết tắt từ mutual exclusion) được khởi tạo 1. Mỗi quá trình Pi được tổ chức như được hiển thị trong hình dưới đây. do{ wait(mutex) critical section Signal(mutex) remainder section }while(1); Hình 0-13 Cài đặt loại trừ hỗ tương với semaphores Chúng ta cũng sử dụng semaphores để giải quyết các vấn đề đồng bộ khác nhau. Thí dụ, để xem xét hai quá trình đang thực thi đồng hành: P1 với câu lệnh S1 và P2 với câu lệnh S2. Giả sử chúng ta yêu cầu rằng S2 được thực thi chỉ sau khi S1 hoàn thành. Chúng ta có thể hoàn thành cơ chế này một cách dễ dàng bằng cách P1 và P2 chia sẻ một semaphore chung synch, được khởi tạo 0 và bằng cách chèn các câu lệnh: S1; signal(sync); vào quá trình P1 và các câu lệnh: wait(synch); S2; vào trong quá trình P2. Vì synch được khởi tạo 0. P2 sẽ thực thi S2 chỉ sau khi P1 nạp signal(synch) mà sau đó là S1; .V.2.1.2 Cài đặt Nhược điểm chính của các giải pháp loại trừ hỗ tương trong phần V.-5.1 và của semaphore được cho ở đây là tất cả chúng đều đòi hỏi sự chờ đợi bận.Để giải quyết yêu cầu cho việc chờ đợi bận, chúng ta có thể hiệu chỉnh định nghĩa của các thao tác wait và signal của semaphore. Khi một quá trình thực thi thao tác wait và nhận thấy rằng nếu giá trị của semaphore không dương, nó phải chờ. Tuy nhiên, thay vì chờ đợi bận, quá trình có thể nghẽn chính nó. Thao tác nghẽn đặt quá trình vào một hàng đợi gắn liền với semaphore và trạng thái quá trình được chuyển tới trạng thái chờ. Sau đó, điều khiển được chuyển tới bộ định thời biểu và bộ định thời biểu chọn một quá trình khác để thực thi. Một quá trình bị nghẽn chờ trên biến semaphore nên được khởi động lại khi quá trình khác thực thi thao tác signal. Quá trình được khởi động lại bởi thao tác wakeup và chuyển quá trình từ trạng thái chờ sang trạng thái sẳn sàng. Sau đó, quá trình này được đặt vào hàng đợi sẳn sàng. (CPU có thể hay không thể được chuyển từ quá trình đang chạy tới quá trình sẳn sàng mới nhất phụ thuộc vào giải thuật định thời biểu CPU). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 93
4. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Trong môi trường đa xử lý, ngăn chặn ngắt không thể thực hiện được. Các chỉ thị từ các quá trình khác nhau (chạy trên các bộ xử lý khác nhau) có thể được chen vào trong cách bất kỳ. Nếu phần cứng không cung cấp bất cứ các chỉ thị đặc biệt nào, chúng ta có thể tận dụng các giải pháp phần cứng phù hợp cho vấn đề vùng tương trục (phần V.-4), ở đó các vùng tương trục chứa cá thủ tục wait và signal. Vấn đề quan trọng là chúng ta không xoá hoàn toàn chờ đợi bận, với định nghĩa này cho các thao tác wait và signal. Dĩ nhiên là chúng ta xoá chờ đợi bận từ việc đi vào vùng tương trục của chương trình ứng dụng. Ngoài ra, chúng ta hạn chế việc chờ đợi bận chỉ các miền tương trục với thao tác wait và signal và các vùng này là ngắn (nếu được mã hợp lý, chúng nên không quá 10 chỉ thị). Do đó, miền tương trục hầu như không bao giờ bị chiếm và sự chờ đợi bận rất hiếm khi xảy ra và sau đó chỉ cho thời gian ngắn. Một trường hợp hoàn toàn khác xảy ra với những chương trình ứng dụng có miền tương trục dài (vài phút hay thậm chí vài giờ) hay có thể hầu như luôn bị chiếm. Trong trường hợp này, chờ đợi bận là cực kỳ kém hiệu quả. .V.2.1.3 Sự khoá chết (deadlocks) và đói tài nguyên Cài đặt semaphore với một hàng đợi có thể dẫn đến trường hợp hai hay nhiều quá trình đang chờ không hạn định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Sự kiện đặt ra là sự thực thi của thao tác signal. Khi một trạng thái như thế xảy ra, những quá trình này được nói là bị khoá chết. Để hiển thị điều này, chúng ta xét một hệ thống chứa hai quá trình P0 và P1, mỗi truy xuất hai semaphore, S và Q, được đặt giá trị 1. P0 P1 wait(S); wait(Q); wait(Q); wait(S); . . . . signal(S); signal(Q); Signal(Q); signal(S); Giả sử rằng P0 thực thi wait(S) và sau đó P1 thực thi wait(Q). Khi P0 thực thi wait(Q), nó phải chờ cho đến khi P1 thực thi signal(Q). Tương tự, khi P1 thực thi wait(S), nó phải chờ cho tới khi P0 thực thi signal(S). Vì các thao tác signal này không thể được thực thi nên P0 và P1 bị khoá chết. Chúng ta nói rằng một tập hợp các quá trình trong trạng thái khoá chết khi mọi quá trình trong tập hợp đang chờ một sự kiện được gây ra chỉ bởi một quá trình khác trong tập hợp. Những sự kiện mà chúng ta quan tâm chủ yếu ở đây là việc chiếm tài nguyên và giải phóng tài nguyên. Tuy nhiên, các loại sự kiện khác cũng có thể dẫn đến việc khoá chết. Chúng ta sẽ xem trong chương VI. Trong chương đó, chúng ta sẽ mô tả các cơ chế khác nhau để giải quyết vấn đề khoá chết. Một vấn đề khoá chết liên quan tới khoá chết là nghẽn hay đói tài nguyên không hạn định (indefinite blocking or starvation), ở đó các quá trình chờ đợi không hạn định trong semaphore. Nghẽn không hạn định có thể xảy ra nếu chúng ta thêm vào và lấy ra các quá trình từ danh sách được nối kết với một semaphore trong thứ tự vào sau ra trước (LIFO). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 95
5. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 } . . . procedure Pn ( ){ } { mã khởi tạo } } Hình 0-14 Cú pháp của monỉtor Biểu diễn kiểu monitor không thể được dùng trực tiếp bởi các quá trình khác nhau. Do đó, một thủ tục được định nghĩa bên trong một monitor chỉ có thể truy xuất những biến được khai báo cục bộ bên trong monitor đó và các tham số chính thức của nó. Tương tự, những biến cục bộ của monitor có thể được truy xuất chỉ bởi những thủ tục cục bộ. Xây dựng monitor đảm bảo rằng chỉ một quá trình tại một thời điểm có thể được kích hoạt trong monitor. Do đó, người lập trình không cần viết mã ràng buộc đồng bộ hoá như hình V-15 dưới đây: Hình 0-15 Hình ảnh dưới dạng biểu đồ của monitor Tuy nhiên, xây dựng monitor như được định nghĩa là không đủ mạnh để mô hình hoá các cơ chế đồng bộ. Cho mục đích này, chúng ta cần định nghĩa các cơ chế đồng bộ hoá bổ sung. Những cơ chế này được cung cấp bởi construct condition. Người lập trình có thể định nghĩa một hay nhiều biến của kiểu condition: condition x, y; Chỉ những thao tác có thể gọi lên trên các biến điều kiện là wait và signal. Thao tác Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 97
6. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trình phải thực thi wait(mutex) trước khi đi vào monitor và phải thực thi signal(mutex) sau khi rời monitor. Vì quá trình đang báo hiệu phải chờ cho đến khi quá trình được bắt đầu lại rời hay chờ, một biến semaphore bổ sung next được giới thiệu, được khởi tạo 0 trên quá trình báo hiệu có thể tự tạm dừng. Một biến số nguyên next_count cũng sẽ được cung cấp để đếm số lượng quá trình bị tạm dừng trên next. Do đó, mỗi thủ tục bên ngoài F sẽ được thay thế bởi wait(mutex); . . . thân của F if (next_count > 0) signal(next); else signal(mutex); Loại trừ hỗ tương trong monitor được đảm bảo. Bây giờ chúng ta mô tả các biến điều kiện được cài đặt như thế nào. Đối với mỗi biến điều kiện x, chúng ta giới thiệu một biến semaphore x_sem và biến số nguyên x_count, cả hai được khởi tạo tới 0. Thao tác x.wait có thể được cài đặt như sau: x_count++; if ( next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count ; Thao tác x.signal() có thể được cài đặt như sau: if ( x_count > 0){ next_count++; signal(x_sem); wait(next); next_count ; } Cài đặt này có thể áp dụng để định nghĩa của monitor được cho bởi cả hai Hoare và Brinch Hansen. Tuy nhiên, trong một số trường hợp tính tổng quát của việc cài đặt là không cần thiết và yêu cầu có một cải tiến hiệu quả hơn. Bây giờ chúng ta sẽ trở lại chủ đề thứ tự bắt đầu lại của quá trình trong monitor. Nếu nhiều quá trình bị trì hoãn trên biến điều kiện x và thao tác x.signal được thực thi bởi một vài quá trình thì thứ tự các quá trình bị trì hoãn được thực thi trở lại như thế nào? Một giải pháp đơn giản là dùng thứ tự FCFS vì thế quá trình chờ lâu nhất sẽ được thực thi tiếp trước. Tuy nhiên, trong nhiều trường hợp, cơ chế định thời biểu như thế là không đủ. Cho mục đích này cấu trúc conditional-wait có thể được dùng; nó có dạng x.wait(c); ở đây c là một biểu thức số nguyên được định giá khi thao tác wait được thực thi. Giá trị c, được gọi là số ưu tiên, được lưu với tên quá trình được tạm dừng. Khi x.signal được thực thi, quá trình với số ưu tiên nhỏ nhất được thực thi tiếp. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 99
7. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Một giải pháp có thể đối với vấn đề trên là chứa các thao tác truy xuất tài nguyên trong monitor ResourceAllocation. Tuy nhiên, giải pháp này sẽ dẫn đến việc định thời được thực hiện dựa theo giải thuật định thời monitor được xây dựng sẳn hơn là được viết bởi người lập trình. Để đảm bảo rằng các quá trình chú ý đến thứ tự hợp lý, chúng ta phải xem xét kỹ tất cả chương trình thực hiện việc dùng monitor ResourceAllocation và những tài nguyên được quản lý của chúng. Có hai điều kiện mà chúng ta phải kiểm tra để thiết lập tính đúng đắn của hệ thống. Đầu tiên, các quá trình người dùng phải luôn luôn thực hiện các lời gọi của chúng trên monitor trong thứ tự đúng. Thứ hai, chúng ta phải đảm bảo rằng một quá trình không hợp tác không đơn giản bỏ qua cổng (gateway) loại trừ hỗ tương được cung cấp bởi monitor và cố gắng truy xuất trực tiếp tài nguyên được chia sẻ mà không sử dụng giao thức truy xuất. Chỉ nếu hai điều kiện này có thể được đảm bảo có thể chúng ta đảm bảo rằng không có lỗi ràng buộc thời gian nào xảy ra và giải thuật định thời sẽ không bị thất bại. Mặc dù việc xem xét này có thể cho hệ thống nhỏ, tĩnh nhưng nó không phù hợp cho một hệ thống lớn hay động. Vấn đề kiểm soát truy xuất có thể được giải quyết chỉ bởi một cơ chế bổ sung khác. VI Các bài toán đồng bộ hoá nguyên thuỷ Trong phần này, chúng ta trình bày một số bài toán đồng bộ hoá như những thí dụ về sự phân cấp lớn các vấn đề điều khiển đồng hành. Các vấn đề này được dùng cho việc kiểm tra mọi cơ chế đồng bộ hoá được đề nghị gần đây. Semaphore được dùng cho việc đồng bộ hoá trong các giải pháp dưới đây. VI.1 Bài toán người sản xuất-người tiêu thụ Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. 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. Mã cho người quá trình sản xuất được hiển thị trong hình V.-18: do{ sản xuất sản phẩm trong nextp wait(empty); wait(mutex); thêm nextp tới vùng đệm signal(mutex); signal(full); } while (1); Hình 0-18 Cấu trúc của quá trình người sản xuất Mã cho quá trình người tiêu thụ được hiển thị trong hình dưới đây: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 101
8. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Thao tác viết được thực hiện signal(wrt); Hình 0-20 Cấu trúc của quá trình viết Mã của quá trình đọc được hiển thị như hình V.-21: wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); Thao tác đọc được thực hiện wait(mutex); readcount ; if (readcount == 0) signal(wrt); signal(mutex); Hình 0-21 Cấu trúc của bộ đọc Chú ý rằng, nếu bộ viết đang ở trong miền tương trục và n bộ đọc đang chờ thì một bộ đọc được xếp hàng trên wrt, và n-1 được xếp hàng trên mutex. Cũng cần chú ý thêm, khi một bộ viết thực thi signal(wrt) thì chúng ta có thể thực thi tiếp việc thực thi của các quá trình đọc đang chờ hay một quá trình viết đang chờ. Việc chọn lựa này có thể được thực hiện bởi bộ định thời biểu. VI.3 Bài toán các triết gia ăn tối Có năm nhà triết gia, vừa suy nghĩ vừa ăn tối. Các triết gia ngồi trên cùng một bàn tròn xung quanh có năm chiếc ghế, mỗi chiếc ghế được ngồi bởi một triết gia. Chính giữa bàn là một bát cơm và năm chiếc đũa được hiển thị như hình VI-22: VII VIII IX X XI XII Hình 0-22 Tình huống các triết gia ăn tối Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 103
9. Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 XIII Tóm tắt Một tập hợp các quá trình tuần tự cộng tác chia sẻ dữ liệu, loại trừ hỗ tương phải được cung cấp. Một giải pháp đảm bảo rằng vùng tương trục của mã đang sử dụng chỉ bởi một quá trình hay một luồng tại một thời điểm. Các giải thuật khác tồn tại để giải quyết vấn đề miền tương trục, với giả thuyết rằng chỉ khoá bên trong việc lưu trữ là sẳn dùng. Sự bất lợi chủ yếu của các giải pháp được mã hoá bởi người dùng là tất cả chúng đều yêu cầu sự chờ đợi bận. Semaphore khắc phục sự bất lợi này. Semaphores có thể được dùng để giải quyết các vấn đề đồng bộ khác nhau và có thể được cài đặt hiệu quả, đặc biệt nếu phần cứng hỗ trợ các thao tác nguyên tử. Các bài toán đồng bộ khác (chẳng hạn như bài toán người sản xuất-người tiêu dùng, bài toán bộ đọc, bộ ghi và bài toán các triết gia ăn tối) là cực kỳ quan trọng vì chúng là thí dụ của phân lớp lớn các vấn đề điều khiển đồng hành. Vấn đề này được dùng để kiểm tra gần như mọi cơ chế đồng bộ được đề nghị gần đây. Hệ điều hành phải cung cấp phương tiện để đảm bảo chống lại lỗi thời gian. Nhiều cấu trúc dữ liệu được đề nghị để giải quyết các vấn đề này. Các vùng tương trục có thể được dùng để cài đặt loại trừ hỗ tương và các vấn đề đồng bộ an toàn và hiệu quả. Monitors cung cấp cơ chế đồng bộ cho việc chia sẻ các loại dữ liệu trừu tượng. Một biến điều kiện cung cấp một phương thức cho một thủ tục monitor khoá việc thực thi của nó cho đến khi nó được báo hiệu tiếp tục. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 105