Lý thuyết hệ điều hành - Chương 4

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

177
lượt xem 11
download

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

Các quá trình đồng thời Vấn đề tranh chấp và tính loại trừ tương hỗ Giải quyết tranh chấp. Phương pháp phần mềm Phương pháp phần cứng Nhờ sự hỗ trợ của hệ điều hành. Các lệnh phần mềm là lệnh đơn vị,Các quá trình đồng thời có thể không đồng bộ nhau.

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết hệ điều hành - Chương 4

Chương 4 ĐỒNG BỘ GIỮA CÁC QUÁ TRÌNH ĐỒNG THỜI -1- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CHƯƠNG 4 : ĐỒNG BỘ GIỮA CÁC QUÁ TRÌNH ĐỒNG THỜI Các quá trình đồng thời  Vấn đề tranh chấp và tính loại trừ tương hỗ  Giải quyết tranh chấp  Phương pháp phần mềm – Phương pháp phần cứng – Nhờ sự hỗ trợ của hệ điều hành – Một số bài toán về đồng bộ  -2- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CÁC QUÁ TRÌNH ĐỒNG THỜI Xử lý đồng thời Xử lý song song   P1 P1 CPU CPU P2 P2 CPU P3 P3 -3- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CẤU TRÚC “parbegin-parend” Dùng để mô tả việc xử lý đồng thời / song song  parbegin Phát biểu 1; Phát biểu 2; ... Phát biểu n parend; Một lệnh chỉ bắt đầu xử lý song song các công việc được nêu  sau đó. Phát biểu sau parbegin-parend chỉ được thực hiện khi mọi  công việc trong parbegin..parend đã kết thúc. -4- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ Tính biểu thức sau: Có thể xử lý song song:   parbegin temp1 := -x; S := -x + 2*y+(x + 2) * (y-1) temp2 := 2*y; temp3 := x+2; Các công việc cần tính tuần tự : temp4:= y-1 parend; –x 1. parbegin 2* y temp5 := temp1 + temp2; 2. temp6 := temp3 * temp4 x+2 3. parend; y –1 S:= temp5 +temp6; 4. -x + 2*y 5. (x + 2) * (y – 1) 6. –x +2*y + (x + 2) * (y – 1) 7. -5- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VẤN ĐỀ TRANH CHẤP Ví dụ 1:  P1: P2: a:=0; a:=10; read(a); 1. 1. parbegin b:=20; a:=a+1; 2. 2. P1; a:=a+b; print(a); 3. 3. P2; print(a); parend 4. Ví dụ 2 :  a:=100; P: Q: parbegin a:=a+1; a:=a+2; P; 1. 1. Q; parend print(a); -6- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
VÍ DỤ 2 -7- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI QUYẾT TRANH CHẤP Nguyên tắc : khi quá trình nào đang thao tác trên tài nguyên thì  quá trình khác phải đợi cho đến khi quá trình đang thao tác hoàn tất công việc  Đảm bảo tính loại trừ tương hỗ (mutual exclusion) trên vùng tranh chấp (critical section) P3 P4 P1 Critical Section P5 P2 Các vấn đề quan tâm : vùng tranh chấp, các thao tác  liên quan và tính loại trừ tương hỗ -8- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT TỔNG QUÁT Mỗi quá trình tham gia vào vùng tranh chấp thực hiện  begin ... enter_mutual_exclusion; critical_section; exit_mutual_exclusion; ... end; enter_mutual_exclusion  if có quá trình đang ở trong vùng tranh chấp then đợi else được phép vào exit_mutual_exclusion  cho phép một trong các quá trình đang đợi (nếu có) được vào vùng tranh cháp. -9- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
NGUYÊN TẮC GIẢI QUYẾT TRANH CHẤP 1. Các lệnh phần mềm là lệnh đơn vị 2. Các quá trình đồng thời có thể không đồng bộ nhau 3. Quá trình ngoài vùng tranh chấp không có quyền cấm quá trình khác xin vào vùng tranh chấp. 4. Quá trình không bị trì hoãn vô hạn định khi xin vào vùng tranh chấp. -10- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
CÁC PHƯƠNG PHÁP GIẢI QUYẾT TRANH CHẤP Các phương pháp hiện thực :  Phần mềm : giải thuật Dekker, Peterson, Bakery – Phần cứng : lệnh testandset – Các cẩu trúc đặc biệt : semaphore, monitor… – Các phương pháp giải quyết tranh chấp có thể là  busy-waiting hay sleep-wakeup: Busy waiting: quá trình vẫn chiếm CPU khi không vào – vùng tranh chấp được để kiểm tra điều kiện. Sleep and Wakeup: ngược lại – -11- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT DEKKER –VERSION1 1; -12- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT DEKKER – VERSION2 -13- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT DEKKER – VERSION3 -14- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT DEKKER – VERSION4 -15- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT DEKKER -16- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT PETERSON -17- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT BAKERY Trước khi vào vùng tranh chấp, mỗi quá trình chọn  cho mình một con số. K quá trình nào giữ k số nhỏ nhất sẽ được vào vùng  tranh chấp. Nếu hai quá trình Pi và Pj giữ hai số bằng nhau thì quá  trình Pi sẽ được vào vùng tranh chấp trước nếu i < j. Các giá trị mà các quá trình có được là một dãy không  giảm: 1,2,3,3,3,3,4,5... -18- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT BAKERY Process i: repeat choosing[i]:=true; number[i]:=max(number[0], number[1], ..., number[n - 1]) +1; choosing[i]:=false; for j:= 0 to n - 1 do begin while choosing[ j] do ; while number[j]≠0 and (number[j], j) < (number[ i],i) do; end; critical section; number[ i]:=0; remainder section; until false; -19- Baøi giaûng moân heä ñieàu haønh Vuõ Leâ Huøng Khoa CNTT – ÑHBK TP. HCM
GIẢI THUẬT BAKERY Ghi chú:  (a,b) < (c,d): if a