8/25/2014 1 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 1 Chương 4: Process Schronization – Đồng bộ giữa các tiến trình Hiểu biết vấn đề đồng bộ giữa các tiến trình, các giải pháp đồng bộ. Làm bài tập, viết chương trình mô phỏng các giải pháp đồng bộ. 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 2 Nội dung  Nhu cầu đồng bộ hóa (synchronisation)  Vấn đề đồng bộ  Giải pháp « busy waiting »  Các giải pháp « SLEEP and WAKEUP »  Semaphore  Monitors  Trao đổi thông điệp 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 3 1. Nhu cầu đồng bộ hóa  Trong hệ thống, nhiều tiến trình liên lạc với nhau  HĐH luôn cần cung cấp những cơ chế đồng bộ hóa để bảo đảm hoạt động đồng thời của các tiến trình không tác động sai lệch đến nhau  Việc tác động sai lệch do:  Yêu cầu độc quyền truy xuất  Yêu cầu phối hợp 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 4 1.1. Yêu cầu độc quyền truy xuất  Tài nguyên trong hệ thống phân 2 loại:  Tài nguyên chia sẻ: cho phép nhiều tiến trình đồng thời truy xuất  Tài nguyên không thể chia sẻ: tại một thời điểm chỉ có một tiến trình sử dụng  Không thể chia sẻ do:  Đặc điểm phần cứng  Nhiều tiến trình đồng thời sử dụng tài nguyên này sẽ gây ra kết quả không dự đoán trước được  Giải pháp:  HĐH cần đảm bảo vấn đề độc quyền truy xuất tài nguyên: tại một thời điểm chỉ cho phép một tiến trình sử dụng tài nguyên 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 5 1.2. Yêu cầu phối hợp đồng bộ  Các tiến trình trong hệ thống hoạt động độc lập, thường không đồng bộ  Khi có nhiều tiến trình phối hợp hoàn thành một tác vụ có thể dẫn đến yêu cầu đồng bộ:  Tiến trình này sử dụng kết quả của tiến trình kia  Cần hoàn thiện các tiến trình con mới có thể hoàn thiện tiến trình cha 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 6 2. Vấn đề đồng bộ(1)  x:=x+1;  x:=x-1 •x khởi tạo = 1 •x được chia sẻ giữa 2 tiến trình •Giá trị của X là bao nhiêu sau khi cả 2 tiến trình hoàn thành?  Bài toán 1: Tiến trình tăng x lên 1 Tiến trình giảm x đi 1 8/25/2014 2 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 7 2. Vấn đề đồng bộ(2) x:=x+1; dịch thành 1. Load RegAx, x 2. tăng RegAx 3. Save x, RegAx x:=x-1; compiles to 1. Load RegAx, x 2. giảm RegAx 3. Save x, RegAx Nếu giá trị ban đầu của x là 1, sau khi thực hiện các bước trên, x sẽ có giá trị 0 (chỉ = 1 khi 2 tiến trình lần lượt thực hiện: P1 xong, P2 mới thực hiện) P1 P2 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 8 2. Vấn đề đồng bộ(3)  Bài toán 2:  Khách hàng có tài khoản 800K, cần thực hiện yêu cầu rút 400K. Việc thực hiện yêu cầu thông qua tiến trình P1  Ở một vị trí khác, Hacker có được mật khẩu của khách hàng, truy nhập vào tài khoản khách hàng yêu cầu rút 700K. Việc thực hiện yêu cầu hacker thông qua tiến trình P2  Cả P1, P2 đều truy nhập vào biến dùng chung là account của khách hàng; mỗi tiến trình rút tiền có biến require(số tiền cần rút)  Cả 2 tiến trình P1, P2 đều có đoạn rút tiền và cập nhật tài khoản: if (account >= require) account -= require; else printf(“Error”); 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 9 2. Vấn đề đồng bộ(4)  Bài toán 2(tiếp)  Tình huống nảy sinh:  P1 kiểm tra thấy account > require nên thực hiện đoạn code trên để rút tiền nhưng chưa cập nhật tài khoản( chưa thực hiện lệnh account -= require) do hết thời gian sử dụng CPU được phân phối cho nó  P2 kiểm tra điều kiện vẫn thỏa mãn( account vẫn = 800K) nên nó thực hiện việc rút tiền. Giả sử P2 được phân phối đủ thời gian sử dụng CPU, cập nhật account = 100K và kết thúc  P1 quay lại thực hiện( vì đã kiểm tra điều kiện từ lần trước) nốt công việc và cập nhật account = -300 => tình huống lỗi  Giải pháp:  Áp dụng cơ chế truy xuất độc quyền trên tài nguyên đó (account): khi một tiến trình đang sử dụng tài nguyên thì các tiến trình khác không được sử dụng 25-Aug-14 HuongPv - Khoa CNTT - HvKTMM 10 2. Vấn đề đồng bộ(5): đoạn găng  Critical session(- critical region đoạn găng, miền găng)  Trong ví dụ trên, tiến trình P1, P2 đều bao gồm chuỗi các lệnh riêng và các lệnh thực hiện rút tiền: …//các lệnh kết nối, lệnh kiểm tra if (account >= require) a