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

Nội dung text: Bài giảng Nguyên lý hệ điều hành - Chương 2: Quản lý tiến trình - Đỗ Văn Uy

1. Phân loại A a A a A A a I B b B b B B b b C c C c C C c c I Z z Z z Z Z z z Độc lập Quan hệ Phân Đồng mức thông cấp tin 2
2. Phân loại • c) Phân cấp: • Tài nguyên cho tiến trình con: – Hệ thống QL tài nguyên tập trung: từ hệ thống, – Hệ thống QL tài nguyên phân tán: từ vốn tài nguyên tiến trình chính, • QL phân tán: Tiến trình chính phải kết thúc sau tiến trình con  POST, WAIT. • d) Đồng mức: • Sử dụng chung theo nguyên tắc lần lượt, • Các hệ thống mô phỏng, trò chơi, . . . 4
3. BIỂU DIỄN • 2 cách mô tả phổ biến: PARBEGIN COBEGIN S1 ; S1 ; S2; S2; . . . . . . . . . . . . . . Sn Sn PAREND; COEND; Các công việc Si được mô tả chính xác bằng một ngôn ngữ lập trình cụ thể. 6
4. Yêu cầu • i) Đảm bảo tài nguyên găng không phải phục vụ quá khả năng của mình, • ii) Không để tiến trình nằm vô hạn trong đoạn găng, • iii) Nếu có xếp hàng chờ thì sớm hay muộn tiến trình cũng qua được đoạn găng, • iv) Nếu có 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. 8
5. $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. 10
6. SƠ ĐỒ NGUYÊN LÝ Var c1, c2:Integer; BEGIN c1:=0; c2 := 0; PARBEGIN TT1: Repeat TT2:Repeat While c2 0 do ; c1 := 1; c2 := 1; {Đoạn găng TT1} {Đoạn găng TT1} c1 := 0; c2 := 0; {Phần còn lại của TT1} {Phần còn lại của TT1} Until false; Until false PAREND END. Có khả năng cả 2 TT cùng vào đoạn găng 12
7. 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. 14
8. 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 16
9. 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 18
10. 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. 20
11. 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. 22
12. KỸ THUẬT ĐÈN BÁO Var s:Integerl BEGIN S=1 • Sơ đồ điều độ: s := 1; PARBEGIN TT1 vào TT1:Repeat -1 TT1 chờ P(s); 0 {Đoạn găng TT1} V(s); TT2 vào 0 {Phần còn lại TT1} Until false; TT2:Repeat P(s); -1 {Đoạn găng TT2} TT2 chờ 0 V(s); {Phần còn lại TT2} TT1 vào Until false PAREND END. 24
13. 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ó. 26
14. 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. 28
15. 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) 30
16. 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. 32
17. 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? 34
18. DỰ BÁO VÀ TRÁNH {Đánh giá} ts := tstb; Flag := true; {Thống kê} While flag do For i := 1 to n do begin flag := false; begin for i := 1 to n do clai[i] := max[i] - ffoi[i]; if not kt[i] and (clai[i] tstb then Kh_An_Toan; 36
19. 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. 38
20. $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. 40
21. CÁC TRẠNG THÁI CƠ BẢN CỦA TIẾN TRÌNH TT TT CT KT Sẵn sàng Thực hiện TT Chờ đợi • Đặc trưng các loại trạng thái, • Vấn đề cần giải quyết: 3 loại. 42
22. 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? Tiêu chuẩn đánh giá: - Cực tiểu hoá thời gian chờ đợi trung bình, - Đảm bảo TT kết thúc được. TT TT CT KT Sẵn sàng Thực hiện TT Chờ đợi 44
23. VẤN ĐỀ • Thời gian thực hiện tiến trình: – Không đẩy ra (Non- 2 chế độ phục vụ preemptive), (Xử lý theo lô) – Có đẩy ra (Preemptive) TT TT CT KT (Phân chia thời gian) Sẵn sàng Thực hiện Lượng tử thời gian: 0.03”  0.2”. TT Chờ đợi 46
24. 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. 48
25. 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. 50
26. Chế độ một dòng xếp hàng • d) RR (Round t (lư th ợ Robin): ờ ng i g t ia ử – Preemtipve, n) 10% –  TT - kết thúc 10% 10% Bổ sung đươc, TT mới 10% 10% – Khả năng đối thoại với TT, 10% 10% – Ưu tiên thích đáng 10% 10% với TT dài: phân lớp 10% phục vụ với t lớn hơn. 52
27. $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) 54
28. 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. 56
29. 6.2 PHÂN LOẠI NGẮT • Ngắt trong và ngắt ngoài, ALU Ngắt Sự kiện D trong A e c d o d d r e – 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. 58
30. CT con và CT xử lý ngắt CT xử lý sự kiện n iệ k T C ự T S T b c ị h l l n í a g n C ắ h t Iret Ret c CT con i phụ Khô Cơ chế CT con Cơ chế xử lý ngắt 60