Bài giảng Hệ điều hành - Chương 2: Đồng bộ hóa tiến trình (Lương Minh Huấn)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.78 MB, 72 trang )
TRƯỜNG ĐẠI HỌC SÀI GỊN
CHƯƠNG 2
BÀI: ĐỒNG BỘ HĨA TIẾN TRÌNH
GV: LƯƠNG MINH HUẤN
NỘI DUNG
I.
Tổng quan giao tiếp tiến trình
II. Tài nguyên găng, đoạn găng
III. Vấn đề đồng bộ hóa
IV. Giải pháp phần mềm
V. Các giải pháp phần cứng
VI. Semaphore
VII.Monitors
VIII.Giải pháp trao đổi thơng điệp.
IX. Các ví dụ kinh điển
I. TỔNG QUAN GIAO TIẾP TIẾN TRÌNH
➢Tiến trình độc lập: không ảnh hưởng và không bị ảnh hưởng bởi
việc thực thi của các tiến trình khác.
➢Tiến trình hợp tác (khơng độc lập): có thể ảnh hưởng và bị ảnh
hưởng bởi việc thực thi của các tiến trình khác.
➢Ưu điểm của việc hợp tác tiến trình:
▪ Chia sẻ thơng tin
▪ Tăng tốc tính tốn (xử lý song song): thời gian I/O và thời gian CPU
▪ Tính module hóa
▪ Tiện lợi
HỢP TÁC BẰNG VIỆC CHIA SẺ
➢Các tiến trình sử dụng và cập nhập dữ liệu chia sẻ như các biến,
file và cơ sở dữ liệu dùng chung.
➢Thao tác ghi phải độc lập từng đơi một để ngăn ngừa tình trạng
đụng độ, có thể dẫn đến tính khơng tồn vẹn dữ liệu.
➢Các miền găng dùng để cung cấp sự toàn vẹn dữ liệu.
➢Một tiến trình địi hỏi miền găng phải khơng bị chờ mãi mãi:
deadlock hoặc starvation.
HỢP TÁC BẰNG VIỆC GIAO TIẾP
➢Giao tiếp cung cấp phương cách để đồng bộ hóa nhiều hoạt động.
➢Có khả năng deadlock
▪ Mỗi tiến trình đều chờ thơng điệp từ một tiến trình khác.
➢Có khả năng xảy ra tình trạng đói (starvation)
▪ Hai tiến trình gởi thơng điệp cho nhau trong khi một tiến trình khác
chờ thơng điệp.
CÁC VẤN ĐỀ
➢Tranh chấp
▪ Nhiều tiến trình truy xuất đồng thời một tài ngun mang bản chất
khơng chia sẻ được.
• Vấn đề tranh đoạt điều khiển (race condition)
▪ Kết quả?
• Khó biết, nhưng thường là sai.
▪ Ln ln nguy hiểm?
• Nếu cân nhắc kỹ càng có thể giảm bớt sự nguy hiểm.
CÁC VẤN ĐỀ
➢Phối hợp
▪ Các tiến trình khơng biết tương quan xử lý của nhau để điều chỉnh
hoạt động nhịp nhàng.
• Phối hợp xử lý (Rendez-vous)
▪ Kết quả: khó biết, thường không ăn khớp.
TRANH ĐOẠT ĐIỀU KHIỂN
➢Ai sẽ thắng?
PHỐI HỢP HÀNH ĐỘNG
PHỐI HỢP HÀNH ĐỘNG
II. TÀI NGUYÊN GĂNG – ĐOẠN GĂNG
➢Những tài nguyên có nguy cơ bị hư hỏng, sai lệch khi được hệ điều
hành chia sẻ đồng thời cho nhiều tiến trình được gọi là tài nguyên
găng (critical resource).
➢Tài nguyên găng có thể là thiết bị vật lý hoặc dữ liệu dùng chung
➢Ví dụ:
TÀI NGUYÊN GĂNG
➢Trường hợp chỉ còn 1 vé (SCA=1):
➢Tài nguyên găng là biến SCA đã bị tranh chấp.
ĐOẠN GĂNG
➢Đoạn găng (Critical Section) hay miền găng là đoạn mã có tác
động đến các tài nguyên găng, chỉ cho phép một tiểu trình (tiến
trình) thi hành tại một thời điểm.
▪ Tiểu trình (tiến trình) được gọi là đi vào miền găng.
▪ Loại trừ hỗ tương và miền găng là hai khái niệm cùng một mục đích.
ĐOẠN GĂNG
➢Cấu trúc chương trình khi có đoạn găng
<noncritical section>
<entercritical section> {kiểm tra và xác lập quyền vào đoạn găng}
<critical section>
<exitcritical section> {xác nhận khi rời đoạn găng}
<noncritical section>
III. VẤN ĐỀ ĐỒNG BỘ HĨA
➢Khi có nhiều tiến trình sử dụng tài ngun găng thì phải đồng bộ.
➢Mục đích là để đảm bảo khơng có một tiến trình nằm trong đoạn
găng.
➢Cần thỏa mãn 3 điều kiện:
▪ Loại trừ lẫn nhau (Mutual Exclusion).
▪ Tiến triển (Progress)
▪ Chờ đợi hữu hạn (Bounded waiting).
III. VẤN ĐỀ ĐỒNG BỘ HĨA
➢Mutual Exclusion: Khơng có hai tiến trình cùng ở trong miền
găng cùng lúc.
➢Progess: Một tiến trình tạm dừng bên ngồi miền găng khơng
được ngăn cản các tiến trình khác vào miền găng
➢Bounded Waiting: Khơng có tiến trình nào phải chờ vơ hạn để
được vào miền găng.
CÁC GIẢI PHÁP ĐỒNG BỘ HĨA
➢Nhóm giải pháp Busy Waiting: tiếp tục tiêu thụ CPU trong khi chờ
đợi vào miền găng. Khơng địi hỏi sự trợ giúp của hệ điều hành.
▪ Phần mềm
• Giải pháp của Peterson
• Sử dụng các biến cờ hiệu
• Sử dụng việc kiểm tra luân phiên
▪ Phần cứng
• Cấm ngắt
• Chỉ thị TSL
CÁC GIẢI PHÁP ĐỒNG BỘ HĨA
➢Nhóm giải pháp Sleep wakeup: từ bỏ CPU khi chưa được vào CS
(miền găng). Khi CS trống sẽ được đánh thức để vào CS. Cần
được hệ điều hành hổ trợ.
▪ Semophore
▪ Monitor
▪ Message
IV. GIẢI PHÁP PHẦN MỀM
➢Sử dụng biến cờ hiệu:
IV. GIẢI PHÁP PHẦN MỀM
➢Có thể mở rộng cho n tiến trình.
➢Khơng bảo đảm mutual exclusion.
➢Bản thân đoạn code kiểm tra và dành quyền cũng là miền găng
(CS).
IV. GIẢI PHÁP PHẦN MỀM
➢Kiểm tra luân phiên:
IV. GIẢI PHÁP PHẦN MỀM
IV. GIẢI PHÁP PHẦN MỀM
➢Chỉ dành cho 2 tiến trình
➢Bảo đảm mutual exclusion.
▪ Chỉ có 1 biến turn tại 1 thời điểm, chỉ cho 1 tiến trình vào CS.
➢Khơng bảo đảm progress.
▪ Mở cửa cho tiến trình khác thì tự đóng lấy chính mình.
IV. GIẢI PHÁP PHẦN MỀM
➢Giải pháp Peterson
➢Giải quyết P0, P1 chia sẻ 2 biến chung, kết hợp 2 ý tưởng ở trên.
▪ int turn; //đến phiên ai
▪ int interest[2] = FALSE; //interest[i] = T : Pi muốn vào CS
IV. GIẢI PHÁP PHẦN MỀM
