Bài giảng Hệ điều hành - Đỗ Tuấn Anh

152 80386 - PENTUM z G = 0 - Chếđộmô đun, đơnvị tínhkíchthước khối–Byte € L = 220 = 1 MB. z G = 1 - Chếđộphân trang, đơnvị tính kích thướckhối–trang (4 KB) € L = 220 P = 220×212 = 232 = 4 GB. z D = 0 - Chếđộdữ liệu16 bit, z D = 1 - Chếđộdữ liệu32 bit. 153 80386 - PENTUM z Địachỉ tuyến tính: 48 bits. z Khả năng: z Vậtlý: AR – 32 bits 32 z Vph= 2 z = 4GB 13 1 32 z Lô gic: Vlg=2 ×2 ×2 z =246 z = 26×240 z = 64 TB 154 80386 - PENTUM z Chếđộkếthợpmôđun – phân trang: z Phân phốibộ nhớ: 155 IV – QUẢN LÝ TIẾN TRÌNH (PROCESS) z 1 - Định nghĩa tiếntrình: z 2 – Phân loại: kế tiếp và song song, z Tiến trình song song: z 156 Phân loại 157 Phân loại z a) Độclập: Bảovệ thông tin, z b)Quan hệ thông tin: z Tiếntrìnhnhận: Tồntại? Ởđâu? Giai đoạn nào? z Cơ chế truyền tin: z Hòm thư, z I/O Ports, z Monitor/ 158 Phân loại z c) Phân cấp: z Tài nguyên cho tiếntrìnhcon: z Hệ thống QL tài nguyên tập trung: từ hệ thống, z 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, z QL phân tán: Tiếntrìnhchínhphảikết thúc sau tiếntrìnhcon € POST, WAIT. z d) Đồng mức: z Sử dụng chung theo nguyên tắclầnlượt, z Các hệ thống mô phỏng, trò chơi, . . . 159 3 - BIỂU DIỄN TIẾN TRÌNH SONG SONG z Giả thiết: S1, S2, . . ., Sn – các công việc thựchiện song song (Trên 1 hoặcnhiều máy). 1 2 n 160 BIỂU DIỄN z 2 cách mô tả phổ biến: PARBEGIN COBEGIN S1 ;S1 ; S2; S2; . . . . . . . . . . . . . . Sn Sn PAREND; COEND; Các công việcSi đượcmôtả chính xác bằng một ngôn ngữ lậptrìnhcụ thể. 161 4 – TÀI NGUYÊN GĂNG và ĐOẠN GĂNG z Tài nguyên găng: Khả năng phụcvụđồng thời bị hạnchế, thông thường - bằng 1. z Ví dụ: Máy in, quá trình bán vé máy bay . . . z Đoạngăng (chỗ hẹp) củatiếntrình, z Điều độ tiến trình qua đoạngăng: Tổ chứccho mọitiến trình qua đượcchổ hẹpcủamình. z Giảithuật điều độ phải đảmbảo4 yêucầu. 162 Yêu cầu z i) Đảmbảotàinguyêngăng không phảiphục vụ quá khả năng củamình, z ii) Không để tiếntrìnhnằmvôhạn trong đoạn găng, z iii) Nếucóxếp hàng chờ thì sớmhay muộntiến trình cũng qua được đoạngăng, z iv) Nếucótiếntrìnhchờđợivànếu tài nguyên găng đượcgiải phóng, thì tài nguyên găng phải phụcvụ ngay cho tiếntrìnhđang chờđợi. 163 Công cụđiều độ z Công cụđiều độ: 2 loại: z Cấpcao: do hệ thống đảmnhiệm, nằm ngoài tiến trình được điều độ, z Cấpthấp: cài đặt ngay vào trong tiếntrìnhđược điều độ. z Các giảithuật điều độ cấpthấp: 3 lớpgiảithuật: z Phương pháp khoá trong, z Phương pháp kiểmtravàxáclập, z Kỹ thuật đèn báo. 164 5 – CÁC GIẢI THUẬT ĐIỀU ĐỘ CẤP THẤP z Phương pháp khoá trong: z Nguyên lý: z Mỗitiến trình (TT) đặttương ứng tài nguyên găng với1 biến ∈ G, z TT dùng biến này để đánh dấuviệcmìnhđang sử dụng tài nguyên găng, z Trướckhivàođoạngăng TT phảikiểmtrabiến tương ứng của các TT khác và chỉ vào đoạngăng khi không có TT nào đang sử dụng tài nguyên găng. 165 Phương pháp khoá trong z Môi trường ví dụ: Xét trường hợp: z 2 tiến trình, z MỗiTT cómột đoạngăng ởđầu, z 1 tài nguyên găng vớikhả năng phụcvụ:1, z Các tiếntrìnhlặpvôhạn. z Tránh nhầmlẫngiữa 2 khái niệm: z Sơđồnguyên lý: nêu ý tưởng chung, z Giảithuật điều độ: sơđồhành động để đảmbảo điều độ. 166 zSBEGINƠ ĐỒ NGUYÊN LÝ z Ban đầu k = 0; khoá mở z PARBEGIN z tt1: while k = 1 do; <-chờđợitíchcực z k := 1; z z k := 0; z z tt2 : while k = 1 do; <-chờđợitíchcực z k := 1; z z k := 0; z z PAREND z END 167 KIỂM TRA VÀ XÁC LẬP (TEST and SET) z Cơ sở: dùng lệnh máy TS có từ các máy tính thế hệ III trởđi. 168 TEST and SET z IBM 360/370: ∃ 1 lệnh TS ( mã 92H), z IBM PC: Nhóm lệnh BTS (Binary Test and Set): L:= G ¬G G ¬G G:= 1 0 1 0 169 TEST and SET z Sơđồđiều độ: 170 TEST and SET Đặc điểm: z Đơngiản, độ phứctạp không tăng khi số tiến trình tăng. Nguyên nhân: Cụcbộ hoá biếnvà tính liên tụccủaKT & XL, z Tồntạihiệntượng chờđợi tích cực. Nguyên nhân: MỗiTT phải tựđưamìnhvàođoạngăng. 171 KỸ THUẬT ĐÈN BÁO(Semaphore) z Dijsktra đề xuất 1972. z Đề xuất: z Mỗitàinguyêngăng được đặttương ứng với một biến nguyên đặcbiệtS(Semaphore), z Ban đầu: S ← Khả năng phụcvụ t.ng. găng, z ∃ 2 lệnh máy P(S) và V(S) thay đổigiátri củaS, mỗilệnh làm 2 công việc và làm mộtcáchliên tục. 172 KỸ THUẬT ĐÈN BÁO z Nội dung lệnh P(S): * Dec(s); ** If S < 0 then ĐưaTT đixếp hàng. z Nội dung lệnh V(S): * Inc(s); ** If S ≤ 0 then Kích hoạtTT đang xếp hàng. 173 KỸ THUẬT ĐÈN BÁO z Thựchiện: z Vì nhiều lý do, không thể chế tạoMT với2 lệnh trên, z Lệnh P(S), V(S) € thủ tục tương ứng. z Đảmbảotínhliêntục: 174 KỸ THUẬT ĐÈN BÁO z Sơđồđiều độ: 175 KỸ THUẬT ĐÈN BÁO Semaphore nhị phân: z Phầnlớn các tài nguyên găng có khả năng phụcvụ = 1 € S nhị phân. z P(S): If s = 0 then Xếp_hàng Else s := 0; z 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ụcP vàV. 176 6 – CÔNG CỤ ĐIỀU ĐỘ CẤP CAO z Đoạngăng quy ước, z Biến điềukiệnquyước, z Monitor hỗ trợđiều độ: cung cấpgiátrị cho biến điềukiệnquyước. z Monitor đóng vai trò vỏ bọcbảovệ ngăncách giữa tài nguyên găng và công cụ truy nhập tớinó. 177 7 - BẾ TẮC và CHỐNG BẾ TẮC z Khái niệmbế tắc (Deadlock): z Cùng chờđợi, z Vô hạnnếu không có tác động từ bên ngoài. z Sẽ không có bế tắcnếu TT A bắt đầu đủ sớm hay đủ muộn. 178 BẾ TẮC và CHỐNG BẾ TẮC z Điềukiệnxuấthiệnbế tắc: hội đủ đồng thời 4 điềukiện: z ∃ tài nguyên găng, z Có tổ chứcxếphàngchờđợi, z Không phân phốilại tài nguyên, z ∃ hiệntượng chờđợivòngtròn. z Chống bế tắc: 3 lớpgiảithuật: z Phòng ngừa, z Dự báovàtránh, z Nhậnbiếtvàkhắcphục. 179 Phòng ngừa z Điềukiệnápdụng: z Xác xuấtxuấthiệnbế tắclớn, z Các biện phápTổnthấtlớn. z Biện pháp: tác động lên mộthoặcmộtsốđiều kiện gây bế tắc để 4 điềukiện không xuấthiện đồng thời. z Các giải pháp: đượcápdụng để nâng cao hiệu quả củahệ thống. 180 Phòng ngừa z Chống tài nguyên găng: z Tổ chứchệ thống tài nguyên lô gíc, z 2 mứctruynhập, z SPOOL. z Chống xếp hàng chờđợi: z Chếđộphân phốisơ bộ, z Trước khi ngắtTT: lưutrạng thái (Dump), z Công cụ: z Điểm gác (Control Points), z Điểmngắt (Break Points) 181 Phòng ngừa z Đặt điểmgác: z Cốđịnh trong CT, z Theo tác nhân ngoài (vd: thờigian) z Ứng dụng: z Hiệuchỉnh CT, z ThựchiệncácCT dài, z Vớitoànbộ hệ thống: Hibernating. 182 Phòng ngừa z Phân phốilại tài nguyên: z Các tài nguyên quan trọng (Bộ nhớ, Processor . . .) luôn luôn được phân phốilại, z Chủ yếu: chỉ cầnlưu ý các tài nguyên riêng, z Hệ thống tài nguyên lô gíc: giảmnhucầu phân phối lại. z Để phân phốilại: Lưuvàkhôiphụctrạng thái tài nguyên. 183 Phòng ngừa z Chống chờđợi vòng tròn: z Phân lớp tài nguyên, tạo thành hệ thống phân cấp, z Nguyên tắc phân phối: Khi chuyểnlớp-phảigiải phóng tài nguyên lớpcũ. 184 DỰ BÁO VÀ TRÁNH z Mỗilần phân phốimột tài nguyên: kiểmtraxem việc phân phốinàycóthể dẫn đến nguy cơ bế tắcchomộtsố tiến trình nào đó hay không và là những tiến trình nào? z Điềukiệnmôitrường: z Xác xuấtxẩyrabế tắcnhỏ, z Tổnthất(nếucóbế tắc) – lớn. 185 DỰ BÁO VÀ TRÁNH z Giảithuậttiêubiểu: “Ngườichủ ngân hàng”. z Giả thiết: z Xét 1 loại tài nguyên, số lượng € tstb, z n tiến trình, z Maxi, z Ffoii, z Kti – boolean, z True – chắcchắnkết thúc được, z False – trong trường hợpngượclại. 186 DỰ BÁO VÀ TRÁNH 187 DỰ BÁO VÀ TRÁNH z Tiêu chuẩndự báo: ngặt, z DựavàoKti € biết các TT có nguy cơ bế tắc, z Xử lý trước khi TT bị bế tắc. z Đặc điểmgiảithuật: z Đơngiản, z Input: Maxi –tin cậy, z Mỗiloại tài nguyên ⇔ thủ tục, z Mỗilầnphânphối € kiểmtra. 188 NHẬN BIẾT VÀ KHẮC PHỤC z Định kỳ kiểm tra các TT chờđợi để phát hiện bế tắc, z Điềukiệnápdụng: z Xác xuấtxẩyrabế tắc bé, z Tổnthất(nếucóbế tắc) – bé. z Áp dụng vớiphầnlớn OS trong thựctế, z Do OP đảmnhiệm. 189 NHẬN BIẾT VÀ KHẮC PHỤC z Lệnh OP € các nhóm lệnh phụcvụ nhậnbiết và khắcphục, z Nhóm lệnh xem trạng thái (Display Status), z Nhóm lệnh tác động lên dòng xếp hàng TT, z Nhóm lệnh tác động lên TT, z Quan trọng: các lệnh huỷ tiếntrình, z Các biện pháp hỗ trợ và ngănchặntựđộng. 190 8 - GỌI TIẾN TRÌNH z TT có thể cạnh tranh hoặctương tác với nhau, z Mối quan hệ tương tác: tuầntự hoặc song song, z Xác lậpquanhệ: z Lờigọi, z Cơ chế xử lý sự kiện(Sẽ xét ở chương sau), z Các cách gọi: z Trong phạmvi mộthệ thống, z Giữacáchệ thống: z RI (Remote Invocation), z RPC (Remote Procedure Call), z Lý thuyết chung: RMI (Remote Methods Invocation) 191 GỌI TIẾN TRÌNH z Sơđồgọi: z Không đốixứng, z Đốixứng. z Kỹ thuậttruyềnthamsố: z Theo giá trị, z Theo địachỉ, z CR (Call by Copy/Restore). 192 GỌI TIẾN TRÌNH z Thông tin tốithiểu để lưuvàkhôiphục TT: z Nội dung các thanh ghi, z Địachỉ lệnh, z Vùng bộ nhớ RAM liên quan, z Vùng bộ nhớ phụcvụ củahệ thống, z Các sự kiệnchưaxử lý. z Phân biệtsơđồgọi đốixứng và đệ quy. 193 V – QUẢN LÝ PROCESSOR z Mục đích: Giảmthời gian chếtcủa Processor € nâng cao hiệuquả hệ thống, z Vai trò thiếtbị trung tâm: liên kếtcácbộ phận đọclập(cứng và mềm) thành hệ thống hoạt động đồng bộ. z Trong phần này: xét hoạt động của 1 CPU. 194 1 – PROCESSOR LÔ GÍC 195 2 – CÁC TRẠNG THÁI CƠ BẢN CỦA TIẾN TRÌNH TT TT CT Sẵn sàng Thực hiện TT Chờ đợi z Đặctrưng các loạitrạng thái, z Vấn đề cầngiảiquyết: 3 loại. 196 VẤN ĐỀ TT TT CT Sẵn sàng Thực hiện TT Chờ đợi 197 VẤN ĐỀ a) Liên quan tới dòng TT sẵn sàng: Cách tổ chứcphụcvụ dòng xếp hàng? 198 VẤN ĐỀ z Trình tự phụcvụ tác động lên thời gian chờ đợi trung bình tw : giả thiết – 3 TT : 1 2 3 199 VẤN ĐỀ z Thờigianthựchiện tiếntrình: z Không đẩyra(Non- preemptive), 2 chế độ phục vụ (Xử lý theo lô) z Có đẩyra(Preemptive) TT TT (Phân chia thCTờigian) KT Sẵn sàng Thực hiện Lượng tử thời gian: 0.03” ÷ 0.2”. TT Chờ đợi 200 VẤN ĐỀ z c) Thời điểm đưa TT chờđợitrở lạisẵn sàng? Cơ chế sự kiện và ngắt. Thời điểm? TT TT CT Sẵn sàng Thực hiện TT Chờ đợi 201 3 - ĐIỀU ĐỘ THỰC HIỆN TT z TT ⇔ thứ tựưutiênphụcvụ, z Yêu cầu: z tw € min. z TT kếtthúc. z Chếđộ: z Một dòng xếp hàng, z Nhiều dòng xếp hàng. 202 Chếđộmột dòng xếphàng z a) FCFS (First come – First served): z Đơngiản, z ∀ TT kết thúc được, z Không cần input bổ sung, z Tw – lớn, z Non-Preemtipve. 203 Chếđộmột dòng xếphàng z b) SJN (Shortest Job – Next): z Thờigianthựchiệnít€ ưutiêncao, z Tw giảm, z TT dài có nguy cơ không kếtthúcđược, z Khó dự báo thời điểmphụcvụ TT, z Non-Preemtipve, z Input: ThờigianthựchiệnTT. 204 Chếđộmột dòng xếphàng z c) SRT (Shortest Remaining Time): z Thứ tựưutiênphụcvụ: xác định theo lượng thờigiancòn lạicầnthiết để kết thúc TT, z tw giảmmạnh, z Các đặctrưng khác: tương tự như SJN, z TT dài càng có nguy cơ không kết thúc được! z Ở các chếđộNon-Preemtipve: cầncótlim € huỹ TT hoặc đưavề thứ tựưutiênthấpnhất. 205 Chếđộmột dòng xếphàng z d) RR (Round Robin): t z (lư Preemtipve, t ợ hờ ng i g t ian ử z ∀ TT - kếtthúc ) đươc, 10% 10% 10% z Khả năng đốithoại Bổ sung TT mới với TT, 10% 10% z Ưutiênthíchđáng với TT dài: phân 10% 10% lớpphụcvụ với t 10% 10% lớnhơn. 10% 206 Chếđộnhiều dòng xếphàng 207 4 - NGẮT và XỬ LÝ NGẮT z Định nghĩangắt (Interrupt): z Cơ chế Sự kiện và Ngắt: từ MT thế hệ III, z IBM 360/370 – 7 loạisự kiện, z IBM PC – 256 loạisự kiện. 208 PHÂN LOẠI NGẮT z Ngắt trong và ngắt ngoài, z Ngắt trong: /0, tràn ô, . . . z Ngắt ngoài: I/O Int, Timer, . . . z Ngắtchắn được và không chắn được: z Chắn được: i/o Int, z Không chắc được: Timer Int. z Ngắtcứng và ngắtmềm. 209 XỬ LÝ NGẮT Mức xử lý I Mức xử lý II 210 CT con và CT xử lý ngắt 211 5 - Xử lý ngắt trong IBM PC z Ngắt ⇔ Pointer (4 bytes), z Véc tơ ngắt = {Pointers} (1 KB), z Khốibộ nhớ xử lý ngắt, z Nét đặcbiệt: z ∃ các ngắt| Pointer € Bảng tham số (Int 11, 1E, 41, . . .), z Ngắt KT CT – Int 20, Ngắtthường trú CT Int 27, z NgắtR/W đĩatheođịachỉ tuyệt đối – Int 25, 26, z ∃ ngắttương ứng vớiviệcbấm phím (Int 05, 1B), z NgătOS môphỏng xử lý các sự kiện (Int 21), z Mộtsố sự kiện: dành cho user tạongắtmềm € Lậptrình hướng sự kiện(EOP). 212 VI - CẤU HÌNH và QUẢN LÝ HỆ THỐNG z 1 - Hệ thống nhiều Processors. z Các loạicấuhình: z Cấuhìnhphâncấp, z Liên kết linh hoạt, z Đẳng cấu, z Quảnlýtiếntrình: z S – tài nguyên găng, z TS € S € điều độ, z Đảmbảotoànvẹnchứcnăng và toàn vẹncấu hình. 213 CẤU HÌNH và QUẢN LÝ HỆ THỐNG z 2 - Bảovệ hệ thống: z Nguy cơ: z Mấthoặchỏng dữ liệu, z Sử dụng tài nguyên vớimục đích xấu, z Truy nhập không đăng ký, z Dò rỉ thông tin. z Cơ chế bảovệ: z Nguyên lý ngănchặn, z Nguyên lý cho phép. z Giảithuậtvàbiệnphápbảovệ: linh hoạt, thường xuyên thay đổi. 214 CẤU HÌNH và QUẢN LÝ HỆ THỐNG z 3 – Thiếtkế và xây dựng hệ thống: z Nguyên lý tập trung: WINDOWS, UNIX, OS IBM, . . . z Nguyên lý “Thử và sai”: LINUX: z Không có đề xuấthướng chung, z Mã nguồnmở cho phép mọingườinghiêncứu, bổ sung sửa đổi, z Phát triểntheonguyênlýtựđiềuchỉnh, z Giao diện: User tự trang bị. 215 4 - Hệ thống của Microsoft z . 216