Bài giảng Điều độ các tiến trình - Nguyễn Thị Thùy Linh

ĐIỀU ĐỘ CÁC TIẾN TRÌNH TRƯỜNG ĐH ĐỒNG THÁP KHOA SP TOÁN - TIN Bài giảng Gỉang viên : Nguyễn Thị Thùy Linh Email: nttlinh@dthu.edu.vn 2 NỘI DUNG 1. Các khái niệm. 2. Tiêu chí cho việc lập lịch biểu. 3. Các giải thuật lập lịch biểu. 4. Lập lịch biểu đa xử lý. 5. Lập lịch biểu thời gian thực. 6. Đánh giá giải thuật. 3 Các khái niệm  Kỹ thuật đa chương giúp cho việc sử dụng CPU đạt hiệu năng cao nhất.  Chu kỳ CPU + chờ đợi I/O, sự thực thi của 1 quá trình bao gồm một chu kỳ là: sử dụng CPU để thực thi và chờ đợi I/O.  Sự phân bố sử dụng CPU. 4 Bộ định thời CPU  Chọn một trong số các quá trình sẵn sàng trong bộ nhớ và giao CPU cho nó thực thi.  Quyết định lập lịch biểu cho CPU diễn ra khi một quá trình:  Chuyển từ trạng thái Running sang trạng thái Waiting.  Chuyển từ trạng thái Running sang trạng thái Ready.  Chuyển từ trạng thái Waiting sang trạng thái Ready.  Kết thúc  Việc lập lịch biểu theo kiểu như trên được gọi là không ưu tiên.  Tất cả giải pháp lập lịch biểu khác gọi là có ưu tiên 5 Dispatcher  Module dispatcher giao cho CPU một quá trình được chọn ra bởi bộ lập lịch biểu ngắn kỳ, bao gồm:  Chuyển ngữ cảnh.  Chuyển sang chế độ người dùng  Nhảy tới vị trí của chương trình người dùng để khởi động lại chương trình đó.  Độ trễ dispatch, là thời gian một dispatcher bỏ ra để ngưng một quá trình và khởi động một quá trình khác 6 Dispatcher (tt) 7 Tiêu chí cho việc lập lịch biểu  Hiệu suất sử dụng CPU, nghĩa là giữ CPU luôn bận rộn nếu có thể.  Năng lực truyền qua (Throughput), là số lượng quá trình hoàn thành việc thực thi trên mỗi đơn vị thời gian  Thời gian xoay vòng (hoàn lại,hòan thành) – Turnaround time, là lượng thời gian thực thi một quá trình=Thời gian chờ đợi để được tải vào bộ nhớ + Chờ đợi trong hàng đợi sẵn sàng + Thực thi bởi CPU và thao tác vào ra  Thời gian chờ đợi: lượng thời gian một tiến trình đã bỏ ra khi nằm trong hàng đợi sẵn sàng 8 Tiêu chí cho việc lập lịch biểu (tt)  Thời gian đáp ứng: lượng thời gian từ lúc một yêu cầu được đệ trình cho đến khi tín hiệu trả lời đầu tiên được sản sinh (môi trường chia thời gian). 9 Tiêu chí tối ưu hóa  Hiệu suất sử dụng CPU tối đa.  Năng lực truyền qua tối đa.  Thời gian xoay vòng tối thiểu.  Thời gian chờ đợi tối thiểu.  Thời gian đáp ứng tối thiểu. 10 Giải thuật First – Come, First – Served (FCFS) Giả sử các quá trình xuất hiện theo thứ tự: P1, P2, P3, biểu đồ Gantt cho việc sắp lịch biểu là  Thời gian chờ của P1 = 0ms, P2 = 24ms, P3 = 27ms  Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17ms Process Thg sử dụng CPU (ms) P1 24 P2 3 P3 3 P1 P2 P3 0 24 27 30 11 Giải thuật FCFS (tt)  Giả sử các quá trình xuất hiện theo thứ tự: P2, P3, P1, biểu đồ Gantt cho việc sắp lịch biểu là  Thời gian chờ của P1 =6ms, P2 = 0ms, P3 = 3ms  Cải thiện được đáng kể so với trường hợp trước  Tránh “tác động nối đuôi”: quá trình ngắn nằm sau quá trình dài P2 P3 P1 0 3 6 30 12 Giải thuật Shortest – Job – First (SJF)  Kết hợp với mỗi quá trình độ dài thời gian mà nó sẽ sử dụng CPU lần kế tiếp. Sử dụng độ dài này để lập lịch trình cho quá trình với thời gian ngắn nhất.  Có hai phương thức thực hiện giải thuật:  Không trưng dụng (độc quyền): một CPU khi được giao cho một quá trình, nó không thể bị lấy lại để giao cho quá trình khác có thời gian ngắn hơn (ưu tiên hơn) đến khi quá trình này sử dụng CPU xong.  Trưng dụng (không độc quyền): nếu một quá trình mới đến có thời gian sử dụng CPU ngắn hơn thời gian thực hiện còn lại của quá trình đang thực hiện (có độ ưu tiên cao hơn), thì giao CPU cho quá trình mới đến.  SJF là tối ưu nhất vì nó tạo ra thời gian chờ đợi trung bình ngắn nhất. 13 Giải thuật SJF không trưng dụng  Theo SJF (không trưng dụng)  Thời gian chờ đợi trung bình: (0 + 6 + 3 + 7)/4 = 4ms Process Thời điểm đến Thg sử dụng CPU(ms) P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 P1 P3 P2 P4 0 7 8 12 16 14 Giải thuật SJF có trưng dụng Theo SJF có trưng dụng  Thời gian chờ đợi trung bình: ((0 + 9) + (0 + 1) + 0 + 2) / 4 = 3ms Process Thời điểm đến Thg sử dụng CPU(ms) P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 15 Xác định độ dài thời gian sử dụng CPU kế tiếp  Chỉ có thể ước lượng độ dài.  Độ dài ước lượng được tính dựa trên độ dài thời gian sử dụng CPU lần trước đó, theo công thức TB số mũ: 1. tn là thời gian sử dụng CPU thực tế lần thứ n. 2. T n + 1 là thời gian sử dụng CPU lần thứ n + 1 3. , 0 <=  <= 1 4. Định nghĩa: T n + 1 =  tn + ( 1 - ) T n Nhận xét:  Nếu  = 0  T n + 1 = T n (không tính đến lịch sử)  Nếu  = 1 -> T n + 1 = tn (chỉ tính đến lần sử dụng CPU trước đó) 16 Lập lịch biểu theo kiểu có ưu tiên  Một chỉ số ưu tiên được gán cho mỗi quá trình.  CPU sẽ được cấp cho quá trình nào có độ ưu tiên cao nhất (nghĩa là có chỉ số ưu tiên thấp nhất). Cách này có thể sử dụng hình thức: Trưng dụng hoặc không Trưng dụng.  SJF là kiểu lập lịch biểu có ưu tiên, nơi mà độ ưu tiên là thời gian ước tính sử dụng CPU lần trước đó.  Vấn đề Statvation (chết đói) sẽ xảy ra đối với những quá trình có độ ưu tiên thấp.  Giải pháp: đặt thời hạn cho quá trình, khi thời hạn trôi đi thì độ ưu tiên cũng tăng theo. 17 Giải thuật ưu tiên không trưng dụng Theo u tien (ưu tiên không trưng dụng)  Thời gian chờ đợi trung bình = (0+5+11+6)/4=5,5ms Process Thời điểm đến Thg sử dụng CPU(ms) ưu tiên P1 0.0 7 2 P2 2.0 4 1 P3 4.0 1 3 P4 5.0 4 1 P1 P2 P4 P3 0 7 11 15 16 18 Giải thuật Ưư tiên trưng dụng Theo u tien (ưu tiên trưng dụng)  Thời gian chờ đợi trung bình =(8+0+11+1)/4=5,0ms Process Thời điểm đến Thg sử dụng CPU(ms) ưu tiên P1 0.0 7 2 P2 2.0 4 1 P3 4.0 1 3 P4 5.0 4 1 P1 P2 P4 P1 P3 0 2 6 10 15 16 19 Giải thuật Round Robin (RR)  Mỗi quá trình sẽ được CPU phục vụ một đơn vị thời gian nhỏ (thông thường là từ 10 – 100 ms). Sau khoảng thời gian này CPU sẽ được giao cho quá trình khác.  Nếu quá trình đang nằm trong hàng đợi Ready và phổ thời gian của nó là q, thì mỗi quá trình sẽ nhận được 1/n tổng thời gian của CPU, thời gian phục vụ của CPU tối đa là q  không có quá trình nào đợi quá (n – 1)q.  Hiệu năng:  q lớn  FIFO  q nhỏ  q đủ lớn, do ta quan tâm đến thời gian chuyển ngữ cảnh, nếu không thời gian phí tổn sẽ cao. 20 Round Robin (tt) P1 arrives P1 1 P2 arrives P3 arrives 2 1 2 1 2 3 1 2 3 2 2 P3 terminates P1 terminates P2 terminates Process Thời điểm đến Thg sử dụng CPU P1 0.0 7 P2 3.0 14 P3 6.0 3 3 21 Phổ thời gian chuyển ngữ cảnh Phải chọn q vừa đủ lớn  Tại sao phổ thời gian q trong giải thuật Round Robin phải được chọn là đủ lớn?  Nếu q nhỏ thì thời gian chuyển ngữ cảnh nhiều  Nếu q lớn thì Round Robin trở thành FCFS 23 Hàng đợi đa cấp  Hàng đợi Ready được chia thành những hàng đợi đặc biệt:  Các quá trình chạy ở chế độ giao tiếp, tương tác (foreground, interactive)  Các quá trình chạy ở chế độ nền, dạng bó hay theo lô (background, batch)  Mỗi hàng đợi có giải thuật lập lịch biểu riêng  Foreground – RR  Background - FCFS  Thống nhất việc lập lịch biểu giữa các hàng đợi  Lập lịch biểu với độ ưu tiên cố định (phục vụ cho hàng đợi Foreground trước rồi mới đến Background)  Thời gian trượt, mỗi hàng đợi nhận được một khoảng thời gian nào đó của CPU rồi đến lượt nó lập lịch biểu cho các quá trình nằm trong nó.  Ví dụ: 80% cho RR và 20% cho FCFS 24 Hàng đợi đa cấp (tt) 25 Hàng đợi phản hồi đa cấp  Cho phép một quá trình có thể di chuyển giữa các hàng đợi khác nhau.  Bộ định thời biểu phản hồi đa cấp có thể định nghĩa bằng những tham số sau:  Số hàng đợi  Giải thuật lập lịch biểu cho từng hàng đợi  Phương thức sử dụng để quyết định khi nào nâng cấp một quá trình.  Phương thức sử dụng để quyết định khi nào hạ cấp một quá trình.  Phương thức sử dụng để quyết định nên đặt quá trình này vào hàng đợi nào, khi nào quá trình này cần được phục vụ. 26 Hàng đợi phản hồi đa cấp (tt)  Ví dụ có 4 hàng đợi:  Q0 : có phổ thời gian là 10ms  Q1 : có phổ thời gian là 20ms  Q2 : có phổ thời gian là 40ms Q3 : FCFS  Ta có thể lập lịch như sau:  Một công việc bước vào Q0 mà ở đó nó sẽ được phục vụ theo kiểu FCFS. Khi nó đạt được CPU, công việc sẽ nhận được 10 ms, nếu không hoàn thành trong 10ms nó sẽ được chuyển sang Q1  Tại Q1 công việc vẫn được phục vụ theo kiểu FCFS và sẽ nhận thêm 20ms, nếu vẫn chưa hoàn thành thì nó sẽ được chuyển sang Q2 và sẽ được nhận thêm 40ms. Nếu vẫn chưa hoàn thành thì nó sẽ được chuyển sang Q3 27 Hàng đợi phản hồi đa mức (tt) quantum=10 quantum=20 quantum=40 FCFS Process 28 Định thời đa xử lý  Định thời sẽ phức tạp hơn khi có nhiều vi xử lý => Chú ý đến sự đồng nhất giữa các CPU.  Mỗi CPU có một hàng đợi sản sằng riêng.  Có thể sử dụng một hàng đợi sẳn sàng dùng chung cho các CPU.  Mỗi CPU có một bộ lập lịch biểu riêng.  Đề cử một CPU lập lịch biểu. 29 Lập lịch biểu thời gian thực  Hệ thống thời gian thực cứng: yêu cầu phải hoàn thành công việc tới hạn chỉ trong một khoảng thời gian được đảm bảo.  Hệ thống thời gian thực mềm: yêu cầu rằng các quá trình tới hạn nhận được thứ tự ưu tiên thông qua các quá trình dự đoán khác. 30 Độ trễ Dispatch 31 Lập lịch biểu thời gian thực  Hệ thống thời gian thực cứng: yêu cầu phải hoàn thành công việc tới hạn chỉ trong một khoảng thời gian được đảm bảo.  Hệ thống thời gian thực mềm: yêu cầu rằng các quá trình tới hạn nhận được thứ tự ưu tiên thông qua các quá trình dự đoán khác. 32 Bài tập 1  Cho tập các quá trình như sau: Lập biểu đồ Gannt minh họa sự thực hiện cho các quá trình trên với các giải thuật: FCFS, SJF không trưng dụng, RR (với q = 10) Tính thời gian chờ trung bình và số lần chuyển ngữ cảnh của từng giải thuật. Process Thg sử dụng CPU P1 24 P2 7 P3 11 P4 4 P5 15 33 Bài tập 2  Cho tập các quá trình như sau: Lập biểu đồ Gannt minh họa sự thực hiện cho các quá trình trên với các giải thuật: FCFS, SJF không độc quyền, giải thuật theo độ ưu tiên có trưng dụng, RR (q = 10) Tính thời gian chờ trung bình và số lần chuyển ngữ cảnh của từng giải thuật. Giải thuật nào có tiêu chí tối ưu nhất? Process Thời điểm đến Thg sử dụng CPU(ms) Độ ưu tiên P1 0.0 14 1 P2 1.0 14 1 P3 3.0 3 2 P4 5.0 10 3 P5 9.0 9 2 BÀI TẬP 3 Cho tập các quá trình như trong bảng. Có ba hàng đợi: Q0, Q1 và Q2 với phổ thời gian phục vụ như trong hình dưới. Hãy lập biểu đồ Gannt để minh họa sự thực thi của các quá trình với giải thuật: hàng đợi phản hồi đa cấp và Tính thời gian chờ trung bình. Process Thời điểm đến Thg sử dụng CPU P1 0.0 50 P2 2.0 4 P3 4.0 15 P4 5.0 30 quantum=10 quantum=25 FCFS Process ĐỒNG BỘ HÓA QUÁ TRÌNH TRƯỜNG ĐH ĐỒNG THÁP KHOA SP TOÁN - TIN Bài giảng Hệ điều hành Chủ đề Giảng viên : Nguyễn Thị Thùy Linh 36 NỘI DUNG 36 1. Cơ sở cho việc đồng bộ hóa. 2. Vấn đề miền tương trục (Critical section). 3. Giải pháp:“chờ đợi bận” 4. Đồng bộ hóa bằng phần cứng. 5. Giải pháp:“SLEEP and WAKEUP” 6. Hiệu báo Semaphore. 7. Các bài toán cổ điển về đồng bộ hóa 8. Monitors. 9. Đồng bộ hóa trong Solaris và Windows 2000 37 Cơ sở cho việc đồng bộ hóa 37  Trong hệ thống máy tính, các quá trình (QT) thường không hoạt động riêng lẻ.  Trong một số trường hợp chúng phải giao tiếp nhau hoặc trao đổi số liệu cho nhau  Ngoài ra, các QT còn có thể cạnh tranh nhau để sử dụng một số tài nguyên: bộ nhớ, CPU, tập tin hoặc các thiết bị ngoại vi  Các QT có thể quan hệ nhau theo hai hướng  Cạnh tranh việc sử dụng các tài nguyên  Hợp tác một cách đồng bộ để tránh mất dữ liệu hay ghi chồng dữ liệu.  Truy cập cạnh tranh trên dữ liệu được chia sẻ có thể gây tình trạng không nhất quán dữ liệu. 38 Cơ sở cho việc đồng bộ hóa (tt) 38  Việc duy trì sự nhất quán dữ liệu đòi hỏi các cơ chế đảm bảo sự thực thi một cách có thứ tự của các quá trình có hợp tác với nhau.  Tình trạng đua tranh (race condition), xảy ra khi các QT đang làm việc với nhau dùng chung một kho dữ liệu, và mỗi quá trình có thể đọc/ghi lên nó. 4 5 6 7 8 P1 P2 In = 4 Out = 6 39 Tình trạng đua tranh (race condition) 39  Là tình trạng mà vài QT cùng truy cập và thay đổi lên dữ liệu được chia sẻ.  Giá trị cuối cùng của dữ liệu phụ thuộc vào QT hoàn thành cuối cùng.  Để giải quyết tình trạng này, các QT đua tranh phải được đồng bộ hóa. 40 NỘI DUNG 40 1. Cơ sở cho việc đồng bộ hóa. 2. Vấn đề miền tương trục (Critical section). 3. Giải pháp:“chờ đợi bận” 4. Đồng bộ hóa bằng phần cứng. 5.Giải pháp:“SLEEP and WAKEUP” 6.Hiệu báo Semaphore. 7. Các bài toán cổ điển về đồng bộ hóa 8. Monitors. 9. Đồng bộ hóa trong Solaris và Windows 2000 41 Vấn đề miền tương trục (Critical Section) 41  Critical Section (miền tương trục, tuần tự, tới hạn)  Tất cả các QT đang cạnh tranh để sử dụng dữ liệu được chia sẻ.  Mỗi quá trình có một đoạn mã lệnh, gọi là miền tuần tự(CS), m à trong đó có hành động truy cập dữ liệu được chia sẻ.  Vấn đề: đảm bảo rằng khi một QT đang chạy trong miền tuần tự, không có một quá trình nào khác được phép chạy trong miền tuần tự của nó.  Cần phải thiết kế một giao thức mà các QT có thể dùng để cộng tác. 42 Các yêu cầu cho giải pháp miền tuần tự phải thoả mãn 3 yêu cầu 42  Loại trừ hỗ tương (Mutual Exclusion): nếu QT pi đang thực hiện trong miền tương trục thi không có QT nào đang được thực thi trong miền tương trục của nó.  Tiến triển (progress): nếu không có QT nào thực thi trong miền tương trục của nó và có một vài QT muốn vào miền tương trục thì việc lựa chọn một QT cho vào miền tương trục là không thể bị trì hoãn vô hạn (nghĩa là QT đang chạy ngoài MTT thì không thể khóa những QT khác)  Chờ đợi có giới hạn (bounded wait): giới hạn số lần QT khác được được phép đi vào MTT(nghĩa là không một QT nào phải chờ đợi vô hạn để có thể bước vào MTT của nó) 43 Giải pháp loại trừ các ngắt (Disabling Interupts) 43  Mỗi QT có thể  Loại trừ tất cả các ngắt ngay sau khi đi vào MTT của nó.  Những ngắt đã bị loại trừ, thì không thể xuất hiện ngắt đồng hồ, nên CPU không thể giao cho QT khác.  Phục hồi ngắt ngay trước khi nó rời khỏi MTT.  Ưu điểm: chỉ thuận tiện cho phần nhân của hệ điều hành, khi cần loại bỏ một số ngắt tương ứng với một chỉ thị nào đó khi có cập nhật biến và các bảng liệt kê.  Khuyết điểm:  Nếu một QT nào đó khóa đi các ngắt và không bật nó trở lại thì hệ thống sẽ kết thúc.  Nếu máy tính có nhiều CPU thì việc loại bỏ ngắt chỉ có tác động đến 1 CPU đã thực hiện chỉ thị đó. 44 NỘI DUNG 44 1. Cơ sở cho việc đồng bộ hóa. 2. Vấn đề miền tương trục (Critical section). 3. Giải pháp:“chờ đợi bận” 4. Đồng bộ hóa bằng phần cứng. 5. Hiệu báo Semaphore. 6. Các bài toán cổ điển về đồng bộ hóa 7. Monitors. 8. Đồng bộ hóa trong Solaris và Windows 2000 45 Giải pháp “chờ đợi bận” giải quyết cho 2 quá trình 45  Có 2 QT P0 và P1  Cấu trúc tổng quát của Pi (QT còn lại là Pj). Các QT chia sẻ nhau biến dùng chung turn để đồng bộ hóa hành động của chúng. 46 Dùng biến khóa 46 CS P1 Lock =0 CS P2 Lock = 1 P1 CS P2 Lock = 0 P1 47 Chờ đợi bận – Giải thuật 1 47  Hai QT sẽ sử dụng một biến dùng chung: turn Khởi tạo turn = 0 hoặc 1 Nếu turn = 0 => pi được phép vào vùng CS int turn = 0; turn = i; // QT Pi có thể bước vào MTT của nó  Cấu trúc của Pi Do { While (turn != i); Critical section Turn = j remainder section; } while(1); Thỏa mãn loại trừ hổ tương nhưng không tiến triển. Do tiến trình kia không sẳn sàng bước vào miền tương trục. 48 Chờ đợi bận – Giải thuật 2 48  Dùng biến mảng để lưu lại trạng thái của QT boolean flag[2]; khởi tạo flag[0] = flag[1] = false; flag[i] = true, Pi sẵn sàng vào MTT  Cấu trúc của Pi Do { flag[i] = true; while(flag[j]); Critical section Flag[i] = false; remainder section; } while(1) ; Thỏa mãn loại trừ hổ tương nhưng không tiến triển. Chẳng hạn khi một tiến trình bị trưng dụng. 49 Chờ đợi bận – Giải thuật 3 (Peterson) 49  Kết hợp biến chia sẻ được dùng trong giải thuật 1 và giải thuật 2: int turn ; //biến turn bằng 0 hoặc 1, dùng để xét QT nào đang được xét vào MTT boolean flag[2]; //để lưu lại trạng thái của QT, dùng để quản lý QT có muốn vào MTT hay không? Giá trị ban đầu flag[0]=flag[1] = false, Muốn vào MTT thì flag[i] = true, không muốn vào là flag[i] = false. 50 Chờ đợi bận – Giải thuật 3 (Peterson) 50  Cấu trúc của Pi Do { flag[i] = true; Turn = j; while(flag[j] && turn == j); Critical section Flag[i] = false; remainder section; } while(1); Thỏa mãn 3 điều kiện Giải pháp nhiều quá trình • Giải thuật Bakery giải quyết vấn đề miền tuần tự cho n quá trình. Giải thuật này được phát triển cho môi trường phân tán. Do { Choosing[i]=true; Number[i]=max(number[0],number[i],,number[n-1])+1; Choosing[i]=false; For (j=0;j<n;j++) { while (choosing[j]); while ((number[j]!=0)&&((number[j],j)<(number[i],i))); } Critical section Number[i] = 0; } while(1); 51 Boolean choosing[n]; Int number[n]; Giải thuật trên đáp ứng đầy đủ các vấn đề của miền tuần tự 52 NỘI DUNG 52 1. Cơ sở cho việc đồng bộ hóa. 2. Vấn đề miền tương trục (Critical section). 3. Giải pháp:“chờ đợi bận” 4. Đồng bộ hóa bằng phần cứng. 5.Giải pháp:“SLEEP and WAKEUP” 6.Hiệu báo Semaphore. 7. Các bài toán cổ điển về đồng bộ hóa 8. Monitors. 9. Đồng bộ hóa trong Solaris và Windows 2000 Đồng bộ hóa bằng phần cứng • Vấn đề CS có thể được giải quyết đơn giản trong môi trường chỉ có 1 bxl • 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. • Khi đó các quá trình được thi hành theo thứ tự không trưng dụng, không có quá trình nào chen vào. Vì thế không có sự thay đổi nào trên các biến được chia sẻ • Giải pháp này không khả thi trên môi trường có nhiều bộ xử lý vì: • Vô hiệu quá các ngắt trên đa bộ xử lý mất nhiều thời gian khi một thông điệp truyền qua tất cả bộ xử lý. • Việc truyền thông điệp này bịi trì hoãn khi đi vào CS và tính hiệu quả của hệ thống giảm. 53 Cài đặt loại trừ hổ tương với TestAndSet Boolean TestAndSet(boolean &target) { boolean rv=target; target = true; Return rv; } Do { while(TestAndSet(lock)); Critical section lock = false; remainder section; } while(1); 54 Cài đặt loại trừ hổ tương với Swap Void Swap(boolean &a,boolean &b) { boolean temp=a; a=b; b=temp; } Do { Key = true; While (key==true) Swap(lock,key); Critical section lock = false; remainder section; } while(1); 55 Giải thuật này không thoả mãn yêu cầu chờ đợi có giới hạn. Loại trừ hổ tương chờ đợi có giới hạn với TestAndSet T h ỏ a m ã n t ấ t c ả c á c y ê u c ầ u c ủ a C S Do { Waiting[i] = true; Key = true; While (waiting[i] && key) Key = TestAndSet(lock); Waiting[i] = false; Critical section J=(i+1)%n; While ((j!=i) && !waiting [j]) j=(j+1)%n; If (j ==i); lock=false; Else waiting[j]=false; remainder section; } while(1); 56 57 NỘI DUNG 57 1. Cơ sở cho việc đồng bộ hóa. 2. Vấn đề miền tương trục (Critical section). 3. Giải pháp:“chờ đợi bận” 4. Đồng bộ hóa bằng phần cứng. 5. Giải pháp:“SLEEP and WAKEUP” 6.Hiệu báo Semaphore. 7. Các bài toán cổ điển về đồng bộ hóa 8. Monitors. 9. Đồng bộ hóa trong Solaris và Windows 2000 Giải pháp “SLEEP