Hệ điều hành - Chương 3: Quản lý các quá trình đồng thời

Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhChương 3Quản lý các quá trình đồng thờiKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhMục đích và yêu cầuMụ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 quanKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhNội dungKhái niệm cơ bảnBài toán “ Critical-Section”Các giải pháp phần mềmĐồng bộ bằng phần cứngSemaphoreKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhKhái niệm cơ bảnKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhBounded Buffer (t,t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhRace ConditionKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhVí dụ về Condition Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCritical SectionKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCritical Section và Mutual ExclusionKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCấu trúc tổng quátKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhRàng buộc của bài toán tranh chấpKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhPhân loại giải phápKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải pháp phần mềmKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 1Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 1(t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 2Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 3 (Peterson)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật Peterson-2 processKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 3: Tính đúng đắnKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật 3: Tính đúng đắn (t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhTrường hợp process bị “chết”Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật Bakery: N processKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiải thuật Bakery: N process(t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhTừ software đến hardwareKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCấm ngắtKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhDùng các lệnh đặc biệtKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhLệnh test – and – set(TSL)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhLệnh test – and – set(t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhThảo luận lệnh test-and-setCũ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”.Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhGiả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 WAKEUPSLEEP : 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).Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCấu trúc chương trình trong SLEEP and WAKEUPInt busy // 1 nếu CS bị chiếmInt 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();}Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhSemaphoreĐượ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 schỉ có hai thao tác được định nghĩa trên semaphoreDown(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)0Up(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ýKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiện thực SemaphoreKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiện thực Semaphore (t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiện thực Semaphore (t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiện thực Mutex với SemephoreKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhĐồng bộ process bằng SemaphoreKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhNhận xétKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhNhận xét (t.t)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhDeadlock và StarvationKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCác loại semaphoreKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiện thực counting semaphore (S) bằng Binary SemaphoreCấu trúc dữ liệubinary-semaphore S1, S2;Int C;Khởi tạo:S1 = 1S2 = 0C = initial value of semaphore SKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhHiệ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);Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí MinhCâu hỏiNắm được các giải thuật và semaphore