Bài giảng Hệ điều hành: Giao tiếp giữa các tiến trình

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

106
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài này trình bày về "Giao tiếp giữa các tiến trình" với một số nội dung sau: Một số khái niệm cơ bản, đụng độ (race condition), miền găng (critical section), ngữ cảnh miền găng, giải pháp cho vấn đề miền găng, cấu trúc của các tiến trình, phân loại các giải pháp cho CS, giải thuật,... Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ điều hành: Giao tiếp giữa các tiến trình

KHOA CÔNG NGHỆ THÔNG TIN TRƯỜNG ĐẠI HỌC BÁCH KHOA TP HỒ CHÍ MINH HỆ ĐIỀU HÀNH Giao tiếp giữa các tiến trình
Một số khái niệm cơ bản* 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 toán (xử lý song song) Tính module hóa Tiện lợi 2
Một số khái niệm cơ bản* 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 toà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 3
Đụng độ (race condition) Race condition: tình huống mà nhiều tiến trình cùng truy cập và thao tác dữ liệu chia sẻ một cách đồng thời. Dữ liệu cuối cùng phụ thuộc vào tiến trình cuối cùng. Để ngăn ngừa đụng độ, các tiến trình đồng hành phải được đồng bộ hóa. 4
Đụng độ (race condition) 5
Miền găng (critical section) n tiến trình đấu tranh với nhau để sử dụng một số dữ liệu nào đó. Mỗi tiến trình có một đoạn mã, gọi là miền găng (critical section (CS)), tại đó dữ liệu chia sẻ được truy cập. Vấn đề: bảo đảm rằng khi một tiến trình đang thực thi trong miền găng của nó, không có tiến trình nào khác được quyền thực thi trong miền găng của nó. 6
Ngữ cảnh miền găng Khi một tiến trình thi hành đoạn mã thao tác trên dữ liệu chia sẻ (hay tài nguyên), chúng ta nói rằng tiến trình đó đang trong miền găng của nó. Việc thực thi các miền găng phải có tính duy nhất: tại bất kỳ thời điểm nào, chỉ có duy nhất một tiến trình được quyền thực thi trong miền găng của nó (ngay cả với nhiều bộ xử lý). Vì vậy mỗi tiến trình phải yêu cầu quyền trước khi vào miền găng. 7
Ngữ cảnh miền găng Đoạn mã thể hiện yêu cầu này được gọi làEntry Section (ES). Miền găng (CS) có thể theo sau là Leave/Exit Section (LS). Phần đoạn mã còn lại là Remainder Section (RS). Vấn đề của miền găng là thiết kế một giao thức mà các tiến trình có thể sử dụng để hành động của chúng sẽ không phụ thuộc vào thứ tự mà sự thi hành của chúng được chen vào. 8
Giải pháp cho vấn đề miền găng Có 3 yêu cầu mà một giải pháp đúng cần phải thỏa mãn: 1. Mutual Exclusion: không có 2 tiến trình cùng ở trong miền găng một lúc 2. Progress: Một tiến trình bên ngoà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 3. Bounded Waiting: không có tiến trình nào phải chờ vô hạn để vào miền găng Chỉ cần một trong ba điều kiện trên sai thì giải pháp đưa ra là sai. 9
Cấu trúc của các tiến trình Cấu trúc tổng quát của tiến trình Pi (Pj) do { entry section critical section leave section remainder section } while (1); Lưu ý: Các tiến trình có thể chia sẻ các biến dùng chung để đồng bộ hóa hoạt động của chúng. 10
Phân loại các giải pháp cho CS Giaûi phaùp busy-waiting Alg. 1 & 2, Peterson, Dekker, Bakery, TSL, Interrupt Giaûi phaùp sleep and wake-up Semaphore Monitor 11
Giaûi thuaät 1 Bieán chia seû int turn; /* khôûi ñaàu turn = 0 */ neáu turn = i ⇒ Pi ñöôïc pheùp vaøo critical section Process Pi do { while (turn != i) ; critical section(); turn = j; remainder section(); } while (1); Thoaû maõn mutual exclusion (1) Progress (2) & bounded-waiting (3) ? 12
Giaûi thuaät 1 Process P0: Process P1: do do while(turn !=0 ); while(turn!=1); Critical_Section(); Critical_Section(); turn=1; turn=0; Remainder_Section(); Remainder_Section(); while (1); while (1); Ví duï: P0 coù RS raát lôùn vaø P1 coù RS nhoû. Neáu turn=0, P0 ñöôïc vaøo CS vaø sau ñoù thöïc thi vuøng RS (turn=1). Ñeán P1 vaøo CS vaø sau ñoù thöïc thi RS (turn=0) vaø tìm caùch vaøo CS moät laàn nöõa nhöng yeâu caàu bò töø choái !!! P1 phaûi chôø P0 !!!. 13
Giaûi thuaät 2 Bieán chia seû boolean flag[2]; /* khôûi ñaàu flag [0] = flag [1] = false. */ Neáu flag [i] = true ⇒ Pi saün saøng vaøo critical section Process Pi do { flag[i] = true; while (flag[j]) ; Critical_Section(); flag [i] = false; Remainder_Section(); } while (1); 14
Giaûi thuaät 3 (Peterson) Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2. Process Pi do { flag [i]= true; turn = j; while (flag [j] and turn == j) ; Critical_Section(); flag [i] = false; Remainder_Section(); } while (1); 15
Giaûi thuaät Bakery: N process Tröôùc khi vaøo CS, process Pi nhaän moät con soá. Process naøo giöõ con soá nhoû nhaát thì ñöôïc vaøo CS Tröôøng hôïp Pi vaø Pj cuøng nhaän ñöôïc moät chæ soá: Neáu i < j thì Pi ñöôïc vaøo tröôùc, ngöôïc laïi Pj ñöôïc vaøo tröôùc. Khi ra khoûi CS, Pi ñaët laïi soá cuûa mình baèng 0 Cô cheá caáp soá cho caùc process thöôøng taïo caùc soá theo cô cheá taêng daàn, ví duï 1,2,3,3,3,3,4,5... 16
Leänh TSL (Test-and-Set Lock) Kieåm tra vaø caäp nhaät moät bieán trong moät thao taùc ñôn (atomic) nShared data: bool lock = false; bool TestandSet(bool &target) { nProcess Pi bool rv = target; while (1) target = true; return rv; { } while (TestandSet(lock)) ; Critical_Section; lock = false; Remainder_Section; } 17
Semaphores Là một công cụ đồng bộ hóa được cung cấp bởi HĐH không đòi hỏi “busy waiting”. Một semaphore S là một biến nguyên mà ngoài lệnh khởi tạo ra, chỉ có thể được truy xuất thông qua hai thao tác độc quyền truy xuất và nguyên tố: wait(S) signal(S) 18
Semaphores Truy cập với 2 thao tác wait (S): while S≤ 0 do no-op; S--; signal (S): S++; Để tránh “busy waiting”: khi một tiến trình phải đợi, nó sẽ được đặt vào hàng đợi block. Khi một tiến trình phải đợi một semaphore S, nó sẽ bị block và đặt vào hàng đợi của semaphore tương ứng. Thao tác signal lấy một tiến trình từ trong hàng đợi và đặt nó vào trong danh sách các tiến trình ở trạng thái sẵn sàng. 19
Semaphores Định nghĩa cấu trúc: typedef struct { int value; struct process *L; } semaphore; Giả sử có 2 thao tác cơ bản: Block tạm cho tiến trình chờ. wakeup(P) khôi phục lại sự thi hành của tiến trình bị block P. 20