Bài giảng Nguyên lí hệ điều hành - Chương 2: Quản lý tiến trình

ó tiến trình chờ đợi và nếu tài nguyên găng được giải phóng, thì tài nguyên găng phải phục vụ ngay cho tiến trình đang chờ đợi. 9 Công cụ điều độ Công cụ điều độ: 2 loại: Cấp cao: do hệ thống đảm nhiệm, nằm ngoài tiến trình được điều độ, Cấp thấp: cài đặt ngay vào trong tiến trình được điều độ. Các giải thuật điều độ cấp thấp: 3 lớp giải thuật: Phương pháp khoá trong, Phương pháp kiểm tra và xác lập, Kỹ thuật đèn báo. 10 $2 – CÁC GIẢI THUẬT ĐIỀU ĐỘ 2.1 Phương pháp khoá trong: Nguyên lý: Mỗi tiến trình (TT) đặt tương ứng tài nguyên găng với 1 biến  G, TT dùng biến này để đánh dấu việc mình đang sử dụng tài nguyên găng, Trước khi vào đoạn găng TT phải kiểm tra biến tương ứng của các TT khác và chỉ vào đoạn găng khi không có TT nào đang sử dụng tài nguyên găng. 11 Phương pháp khoá trong Môi trường ví dụ: Xét trường hợp: 2 tiến trình, Mỗi TT có một đoạn găng ở đầu, 1 tài nguyên găng với khả năng phục vụ:1, Các tiến trình lặp vô hạn. Tránh nhầm lẫn giữa 2 khái niệm: Sơ đồ nguyên lý: nêu ý tưởng chung, Giải thuật điều độ: sơ đồ hành động để đảm bảo điều độ. 12 SƠ ĐỒ NGUYÊN LÝ Var c 1 , c 2 : Integer ; BEGIN c 1 := 0 ; c 2 := 0 ; PARBEGIN TT 1 : Repeat TT 2 : Repeat While c 2 0 do ; While c 1 0 do ; c 1 := 1 ; c 2 := 1 ; { Đoạn găng TT 1 } { Đoạn găng TT 1 } c 1 := 0 ; c 2 := 0 ; { Phần còn lại của TT 1 } { Phần còn lại của TT 1 } Until false ; Until false PAREND END . Có khả năng cả 2 TT cùng vào đoạn găng 13 SƠ ĐỒ NGUYÊN LÝ 14 SƠ ĐỒ NGUYÊN LÝ Nguyên nhân không đáp ứng yêu cầu điều đô: Kiểm tra và Xác lập – 2 công việc riêng biệt, Khoảng cách thời gian giữa 2 công việc, Giữa 2 công việc: Processor có thể bị chuyển sang công việc khác. 1968: Dekker công bố giải thuật điều độ, kết nối Kiểm tra và Xác lập thành một khối. 15 Giải thuật Dekker 16 Giải thuật Dekker Đặc điểm: Không đòi hỏi công cụ đặc biệt  áp dụng được trong mọi môi trường (hệ thống và ngôn ngữ LT), Phức tạp, độ phức tạp tăng khi số tiến trình tăng, Tồn tại hiện tượng chờ đợi tích cực. Nguyên nhân: Không cục bộ hoá biến trong tiến trình, Mỗi TT phải tự Kiểm tra và xác lập.. 17 2.2 KIỂM TRA VÀ XÁC LẬP (TEST and SET) Cơ sở: dùng lệnh máy TS có từ các máy tính thế hệ III trở đi. 18 TEST and SET IBM 360/370:  1 lệnh TS ( mã 92H), IBM PC: Nhóm lệnh BTS (Binary Test and Set): L:= G ¬G G ¬G G:= 1 0 1 0 19 TEST and SET Sơ đồ điều độ: 20 TEST and SET Đặc điểm: Đơn giản, độ phức tạp không tăng khi số tiến trình tăng. Nguyên nhân: Cục bộ hoá biến và tính liên tục của KT & XL, Tồn tại hiện tượng chờ đợi tích cực. Nguyên nhân: Mỗi TT phải tự đưa mình vào đoạn găng. 21 2.3 KỸ THUẬT ĐÈN BÁO Dijsktra đề xuất 1972. Đề xuất: Mỗi tài nguyên găng được đặt tương ứng với một biến nguyên đặc biệt S (Semaphore), Ban đầu: S ← Khả năng phục vụ t.ng. găng,  2 lệnh máy P(S) và V(S) thay đổi giá tri của S, mỗi lệnh làm 2 công việc và làm một cách liên tục. 22 KỸ THUẬT ĐÈN BÁO Nội dung lệnh P(S): 	* Dec(s); 	** If S < 0 then Đưa TT đi xếp hàng. Nội dung lệnh V(S):	 	* Inc(s); 	** If S  0 then Kích hoạt TT đang xếp hàng. 23 KỸ THUẬT ĐÈN BÁO Thực hiện: Vì nhiều lý do, không thể chế tạo MT với 2 lệnh trên, Lệnh P(S), V(S)  thủ tục tương ứng. Đảm bảo tính liên tục: 24 KỸ THUẬT ĐÈN BÁO Sơ đồ điều độ: 25 Semaphore nhị phân: Phần lớn các tài nguyên găng có khả năng phục vụ = 1  S nhị phân. P(S): If s = 0 then Xếp_hàng Else s := 0; V(S): If dòng_xếp_hàng  NULL then Kích_hoạt Else s := 1; Vấn đề đặt tên các thủ tục P và V. KỸ THUẬT ĐÈN BÁO 26 2.4– CÔNG CỤ ĐIỀU ĐỘ CẤP CAO Đoạn găng quy ước, Biến điều kiện quy ước, Monitor hỗ trợ điều độ: cung cấp giá trị cho biến điều kiện quy ước. Monitor đóng vai trò vỏ bọc bảo vệ ngăn cách giữa tài nguyên găng và công cụ truy nhập tới nó. 27 $3 - BẾ TẮC và CHỐNG BẾ TẮC Khái niệm bế tắc (Deadlock): Cùng chờ đợi, Vô hạn nếu không có tác động từ bên ngoài. Sẽ không có bế tắc nếu TT A bắt đầu đủ sớm hay đủ muộn. 28 BẾ TẮC và CHỐNG BẾ TẮC 3.1 Điều kiện xuất hiện bế tắc: hội đủ đồng thời 4 điều kiện:  tài nguyên găng, Có sự xếp hàng chờ đợi, Không phân phối lại tài nguyên,  hiện tượng chờ đợi vòng tròn. 3.2 Chống bế tắc: 3 lớp giải thuật Phòng ngừa, Dự báo và tránh, Nhận biết và khắc phục. 29 Phòng ngừa Điều kiện áp dụng: Xác xuất xuất hiện bế tắc lớn, Các biện phápTổn thất lớn. Biện pháp: tác động lên một hoặc một số điều kiện gây bế tắc để 4 điều kiện không xuất hiện đồng thời. Các giải pháp: được áp dụng để nâng cao hiệu quả của hệ thống. 30 Phòng ngừa Chống tài nguyên găng: Bố sung TN vật lí Tổ chức hệ thống tài nguyên lô gíc, 2 mức truy nhập, SPOOL. Chống xếp hàng chờ đợi: Chế độ phân phối sơ bộ, Trước khi ngắt TT: lưu trạng thái (Dump), Công cụ: Điểm gác (Control Points), Điểm ngắt (Break Points) 31 Phòng ngừa Đặt điểm gác: Cố định trong CT, Theo tác nhân ngoài (vd: thời gian) Ứng dụng: Hiệu chỉnh CT, Thực hiện các CT dài, Với toàn bộ hệ thống: Hibernating. 32 Phòng ngừa Phân phối lại tài nguyên: Các tài nguyên quan trọng (Bộ nhớ, Processor . . .) luôn luôn được phân phối lại, Chủ yếu: chỉ cần lưu ý các tài nguyên riêng, Hệ thống tài nguyên lô gíc: giảm nhu cầu phân phối lại. Để phân phối lại: Lưu và khôi phục trạng thái tài nguyên. 33 Phòng ngừa Chống chờ đợi vòng tròn: Phân lớp tài nguyên, tạo thành hệ thống phân cấp, Nguyên tắc phân phối: Khi chuyển lớp - phải giải phóng tài nguyên lớp cũ. 34 DỰ BÁO VÀ TRÁNH Điều kiện môi trường: Xác xuất xẩy ra bế tắc nhỏ, Tổn thất (nếu có bế tắc) – lớn. Mỗi lần phân phối một tài nguyên: kiểm tra xem việc phân phối này có thể dẫn đến nguy cơ bế tắc cho một số tiến trình nào đó hay không và là những tiến trình nào? 35 DỰ BÁO VÀ TRÁNH Giải thuật tiêu biểu: “Người chủ ngân hàng”. Giả thiết: Xét 1 loại tài nguyên, số lượng  tstb, n tiến trình, Maxi, Ffoii, Kti – boolean, True – chắc chắn kết thúc được, False – trong trường hợp ngược lại. 36 DỰ BÁO VÀ TRÁNH 37 DỰ BÁO VÀ TRÁNH Tiêu chuẩn dự báo: ngặt, Dựa vào Kti  biết các TT có nguy cơ bế tắc, Xử lý trước khi TT bị bế tắc. Đặc điểm giải thuật: Đơn giản, Input: Maxi – tin cậy, Mỗi loại tài nguyên  thủ tục, Mỗi lần phân phối  kiểm tra. 38 NHẬN BIẾT VÀ KHẮC PHỤC Điều kiện áp dụng: Xác xuất xẩy ra bế tắc bé, Tổn thất (nếu có bế tắc) – bé. Định kỳ kiểm tra các TT chờ đợi để phát hiện bế tắc, Áp dụng với phần lớn OS trong thực tế, Do OP đảm nhiệm. 39 NHẬN BIẾT VÀ KHẮC PHỤC Lệnh OP  các nhóm lệnh phục vụ nhận biết và khắc phục, Nhóm lệnh xem trạng thái (Display Status), Nhóm lệnh tác động lên dòng xếp hàng TT, Nhóm lệnh tác động lên TT, Quan trọng: các lệnh huỷ tiến trình, Các biện pháp hỗ trợ và ngăn chặn tự động. 40 $4 – QUẢN LÝ PROCESSOR Mục đích: Giảm thời gian chết của Processor  nâng cao hiệu quả hệ thống, Vai trò thiết bị trung tâm: liên kết các bộ phận đọc lập (cứng và mềm) thành hệ thống hoạt động đồng bộ. Trong phần này: xét hoạt động của 1 CPU. 41 4.1 – PROCESSOR LÔ GÍC 42 CÁC TRẠNG THÁI CƠ BẢN CỦA TIẾN TRÌNH Đặc trưng các loại trạng thái, Vấn đề cần giải quyết: 3 loại. 43 4.2 VẤN ĐỀ LẬP LỊCH 44 VẤN ĐỀ a) Liên quan tới dòng TT sẵn sàng: Cách tổ chức phục vụ dòng xếp hàng? 45 VẤN ĐỀ Trình tự phục vụ tác động lên thời gian chờ đợi trung bình tw : giả thiết – 3 TT : 46 VẤN ĐỀ Thời gian thực hiện tiến trình: Không đẩy ra (Non-preemptive), (Xử lý theo lô) Có đẩy ra (Preemptive) (Phân chia thời gian) Lượng tử thời gian: 0.03”  0.2”. 47 VẤN ĐỀ c) Thời điểm đưa TT chờ đợi trở lại sẵn sàng? Cơ chế sự kiện và ngắt. 48 4.3 - ĐIỀU ĐỘ THỰC HIỆN TT TT  thứ tự ưu tiên phục vụ, Yêu cầu: tw  min. TT kết thúc. Chế độ: Một dòng xếp hàng, Nhiều dòng xếp hàng. 49 Chế độ một dòng xếp hàng a) FCFS (First come – First served): + Tổ chức: Ưu tiên ngoài Ưu tiên xếp hàng Phục vụ + Đánh giá: Đơn giản,  TT kết thúc được, Không cần input bổ sung, Tw – lớn, Non-Preemtipve. 50 Chế độ một dòng xếp hàng b) SJN (Shortest Job – Next): Thời gian thực hiện ít  ưu tiên cao, Tw giảm, TT dài có nguy cơ không kết thúc được, Khó dự báo thời điểm phục vụ TT, Non-Preemtipve, Input: Thời gian thực hiện TT. 51 Chế độ một dòng xếp hàng c) SRT (Shortest Remaining Time): Thứ tự ưu tiên phục vụ: xác định theo lượng thời gian còn lại cần thiết để kết thúc TT, tw giảm mạnh, Các đặc trưng khác: tương tự như SJN, TT dài càng có nguy cơ không kết thúc được! Ở các chế độ Non-Preemtipve: cần có tlim  huỹ TT hoặc đưa về thứ tự ưu tiên thấp nhất. 52 Chế độ một dòng xếp hàng d) RR (Round Robin): Preemtipve,  TT - kết thúc đươc, Khả năng đối thoại với TT, Ưu tiên thích đáng với TT dài: phân lớp phục vụ với t lớn hơn. 53 Chế độ nhiều dòng xếp hàng 54 $5 - GỌI TIẾN TRÌNH TT có thể cạnh tranh hoặc tương tác với nhau, Mối quan hệ tương tác: tuần tự hoặc song song, Xác lập quan hệ: Lời gọi, Cơ chế xử lý sự kiện (Sẽ xét ở chương sau), Các cách gọi: Trong phạm vi một hệ thống, Giữa các hệ thống: RI (Remote Invocation), RPC (Remote Procedure Call), Lý thuyết chung: RMI (Remote Methods Invocation) 55 GỌI TIẾN TRÌNH Sơ đồ gọi: Không đối xứng, Đối xứng. Kỹ thuật truyền tham số: Theo giá trị, Theo địa chỉ, CR (Call by Copy/Restore). 56 GỌI TIẾN TRÌNH Thông tin tối thiểu để lưu và khôi phục TT: Nội dung các thanh ghi, Địa chỉ lệnh, Vùng bộ nhớ RAM liên quan, Vùng bộ nhớ phục vụ của hệ thống, Các sự kiện chưa xử lý. Phân biệt sơ đồ gọi đối xứng và đệ quy. 57 $6 - NGẮT và XỬ LÝ NGẮT 6.1 Định nghĩa ngắt (Interrupt): Cơ chế Sự kiện và Ngắt: từ MT thế hệ III, IBM 360/370 – 7 loại sự kiện, IBM PC – 256 loại sự kiện. 58 6.2 PHÂN LOẠI NGẮT Ngắt trong và ngắt ngoài, Ngắt trong: /0, tràn ô, . . . Ngắt ngoài: I/O Int, Timer, . . . Ngắt chắn được và không chắn được: Chắn được: i/o Int, Không chắc được: Timer Int. Ngắt cứng và ngắt mềm. 59 6.3 XỬ LÝ NGẮT 60 CT con và CT xử lý ngắt 61 6.4 - Xử lý ngắt trong IBM PC Ngắt  Pointer (4 bytes), Véc tơ ngắt = {Pointers} (1 KB), Khối bộ nhớ xử lý ngắt, Nét đặc biệt:  các ngắt | Pointer  Bảng tham số (Int 11, 1E, 41, . . .), Ngắt KT CT – Int 20, Ngắt thường trú CT Int 27, Ngắt R/W đĩa theo địa chỉ tuyệt đối – Int 25, 26,  ngắt tương ứng với việc bấm phím (Int 05, 1B), Ngăt OS mô phỏng xử lý các sự kiện (Int 21), Một số sự kiện: dành cho user tạo ngắt mềm  Lập trình hướng sự kiện (EOP).