Bài giảng Hệ điều hành (Operating Systems) - Nguyễn Phan Trung - Chương 3: Quản lý các quá trình đồng thời

Chương 3 Quản lý các quá trình đồng thời Mục đích và yêu cầu Mục đích: Hiểu được các quá trình thực thi đồng thời và “Critical-Section” Hiểu được các nguyên lý cơ bản trong giải quyết tranh chấp bằng phần mềm, phần cứng và Semaphore. Yêu cầu: Áp dụng lý thuyết để thực hiện được một số bài tập liên quan Nội dung Khái niệm cơ bản Bài toán “ Critical-Section” Các giải pháp phần mềm Đồng bộ bằng phần cứng Semaphore Khái niệm cơ bản Bounded Buffer (t,t) Race Condition Ví dụ về Condition Critical Section Critical Section và Mutual Exclusion Cấu trúc tổng quát Ràng buộc của bài toán tranh chấp Phân loại giải pháp Giải pháp phần mềm Giải thuật 1 Giải thuật 1(t.t) Giải thuật 2 Giải thuật 3 (Peterson) Giải thuật Peterson-2 process Giải thuật 3: Tính đúng đắn Giải thuật 3: Tính đúng đắn (t.t) Trường hợp process bị “chết” Giải thuật Bakery: N process Giải thuật Bakery: N process(t.t) Từ software đến hardware Cấm ngắt Dùng các lệnh đặc biệt Lệnh test – and – set(TSL) Lệnh test – and – set(t.t) Thảo luận lệnh test-and-set Cũng giống như các giải pháp phần cứng khác. TSL giảm nhẹ công việc lập trình để giải quyết vấn đề, nhưng lại không dễ dàng để cài đặt TLS sao cho được xử lý một cách không thể phân chia, nhất là trên máy với cấu hình nhiều bộ xử lý. Các giải pháp buộc quá trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào CS như thế được gọi các giải pháp “ busy waiting”. Việc kiểm tra tốn nhiều thời gian sử dụng CPU do vậy quá trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hoá nên tránh các giải pháp “ busy waiting”. Giải pháp “SLEEP and WAKEUP” Để loại bỏ các bất tiện của “busy waiting”. Chúng ta có thể tiếp cận theo hướng cho một quá trình chưa đủ cond vào CS chuyển sang trạng thái blocked, từ bỏ quyền sử dụng CPU. Để phục vụ điều này cần hai thủ tục do Os cung cấp là SLEEP and WAKEUP SLEEP : tạm dừng hoạt của quá trình (Blocked) gọi nó và chờ đến khi được một quá trình khác “đánh thức”. WAKEUP: nhận một tham số duy nhất: quá trình sẽ được tái kích hoạt (đặt về trạng thái ready). Cấu trúc chương trình trong SLEEP and WAKEUP Int busy	 // 1 nếu CS bị chiếm Int blocked 	// số lượng quá trình đang bị khoá While {true} { if (busy) { 	blocked = blocked +1; 	sleep(); 	} 	else busy =1; 	 	critical-section(); 	 	busy =0; 	if (blocked) { 	wakeup(process); 	blocked = blocked -1;	 	} 	 	Non critical- section(); } Semaphore Được Dijkstra đề xuất vào năm 1965. một semaphore s là một biến cố có các thuộc tính sau: Một giá trị nguyên dương e(s) Một hàng đợi f(s) lưu danh sách các quá trình đang bị khoá (chờ) trên semaphore s chỉ có hai thao tác được định nghĩa trên semaphore Down(s): giảm giá trị của semaphore đi 1 nếu semaphore có giá trị e(s)>0, và tiếp tục xử lý. Ngược lại, nếu e(s)0 Up(s): tăng giá trị của semaphore s lên 1 nếu có 1 hoặc nhiều quá trình đang chờ trên semaphore s, bi khoá bởi thao tác down. Thì hệ thống sẽ chọn một trong các quá trình này để kết thúc thao tác Down và cho tiếp tục xử lý Hiện thực Semaphore Hiện thực Semaphore (t.t) Hiện thực Semaphore (t.t) Hiện thực Mutex với Semephore Đồng bộ process bằng Semaphore Nhận xét Nhận xét (t.t) Deadlock và Starvation Các loại semaphore Hiện thực counting semaphore (S) bằng Binary Semaphore Cấu trúc dữ liệu binary-semaphore S1, S2; Int C; Khởi tạo: S1 = 1 S2 = 0 C = initial value of semaphore S Hiện thực counting semaphore (S) bằng Binary Semaphore (t.t) Tác vụ wait(S) Wait(S1); C--; If (C<0) { Signal(S1); Wait(S2); } Signal(S1); Tác vụ signal(S) Wait(S1); C++ If (C<=0) Signal(S2): Else Signal(S1); Câu hỏi Nắm được các giải thuật và semaphore