Bài giảng Nguyên lý hệ điều hành - Đại học Đà Nẵng

138 trang phuongnguyen 13151

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nguyên lý hệ điều hành - Đại học Đà Nẵng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_nguyen_ly_he_dieu_hanh.pdf

Nội dung text: Bài giảng Nguyên lý hệ điều hành - Đại học Đà Nẵng

ĐẠI HỌC ĐÀNẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN NGUYÊN LÝ HỆ ĐIỀU HÀNH Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 1 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG Giới thiệu Nội dung giáo trình CHƯƠNG 1. MỞ ĐẦU CHƯƠNG 2. TIẾN TRÌNH CHƯƠNG 3. VÀO/RA CHƯƠNG 4. QUẢN LÝ BỘ NHỚ CHƯƠNG 5. HỆ THỐNG FILE Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 2 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các vấn đề 1. Khái niệm hệđiềuhành 2. Chức năng của hệ điều hành 3. Vị trí của hệ điều hành 4. Các thành phần của hệ điều hành 5. Cấu trúc của hệ điều hành Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 3 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Khái niệm hệđiềuhành Hệđiều hành (HĐH) là phần gắn bó trực tiếp với phần cứng và là môi trường cho các chương trình ứng dụng chạy trên nó. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 4 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Chức năng của hệ điềuhành ¾ Quảnlývàphânphối tài nguyên 1 cách hợplý ¾ Giả lậpmộtmáytínhmở rộng và tạogiaodiên tiệnlợivớingườisử dụng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 5 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Tài nguyên ¾ Tài nguyên phần cứng - Bộ xử lý - Bộ nhớ - Các thiết bị nhập xuất ¾ Tài nguyên phần mềm Các file, chương trình dùng chung, Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 6 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Vị trí của hệ điềuhành Các CT ứng dụng Các CT ứng dụng Các CT tiện ích Các CT NNLT, CTDịch, tiện Hệđiều hành ích Phần HỆ ĐIỀU HÀNH cứng Ngôn ngữ máy Phần Micro Programming cứng Các thiết bị vật lý Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 7 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành ¾ Quản lý tiến trình ¾ Quản lý bộ nhớ ¾ Quản lý nhập xuất ¾ Quản lý tậptin ¾ Hệ thống bảo vệ ¾ Hệ thông dịch lệnh (Shell) ¾ Quản lýGiáo m trìnhạ ngNguyên lý Hệ điều hành - 10/2/2007 8 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Quản lý tiến trình ¾ Tạo lập, huỷ bỏ một tiến trình ¾ Tạm dừng, tái kích hoạt một tiến trình ¾ Cung cấp các cơ chế trao đổi thông tin giữa các tiến trình ¾ Cung cấp cơ chế đồng bộ hoá các tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 9 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Quản lý bộ nhớ ¾ Cấp phát và thu hồivùngnhớ cho tiến trình khi cần thiết ¾ Ghi nhậntìnhtrạng bộ nhớ chính: vùng đã cấp phát, vùng còn có thể sử dụng ¾ Quyết định tiến trình nào được nạp vào bộ nhớ chính khi có một vùng nhớ trống. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 10 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Quản lý nhập xuất ¾ Gửi các lệnh điều khiển đến các thiết bị ¾ Tiếp nhận các ngắt ¾ Xử lý lỗi Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 11 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Quản lý tập tin ¾ Tạo lập, huỷ bỏ một tập tin. ¾ Tạo lập và huỷ bỏ một thư mục. ¾ Cung cấp các thao tác xử lý tập tin và thư mục. ¾ Tạo lập quan hệ tương ứng giữa tập tin và bộ nhớ phụ chứa nó. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 12 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Hệ thống bảo vệ ¾ Xây dựng cơ chế bảo vệ thích hợp. Trong trường hợp nhiều người cùng sử dụng đồng thời các tiến trình. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 13 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Hệ thông dịch lệnh (Shell) ¾ Đóng vai trò giao diện giữa NSD và HĐH ¾ Các lệnh được chuyển đến HĐH dưới dạng chỉ thị điều khiển. ¾Shell nhận lệnh và thông dịch lệnh để HĐH có xử lý tương ứng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 14 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Các thành phần của hệ điềuhành Quản lý mạng ¾ Một hệ thống phân bố nhiều bộ xử lý với các bộ nhớ độc lập. ¾ Các tiến trình trong hệ thống có thể kết nốivới nhau qua mạng truyền thông. ¾ Việc truy xuất đến tài nguyên mạng thông qua các trình điềukhiểngiaotiếpmạng. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 15 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Cấu trúc của hệ điềuhành ¾ Hệ thống nguyên khối (Monolithic System) ¾ Hệ thống phân lớp (Layer System) ¾ Máy ảo (Virtual Machine) ¾ Mô hình Client-Server (Client-Server Model) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 16 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống nguyên khối ¾ Cấutrúc HĐH được xem là ko cấu trúc ¾ HĐH được xây dựng dựa trên tập hợp các thủ tục riêng lẻ. ¾ Mỗi thủ tục có thể gọi lẫn nhau khi cần ¾ CT ứng dụng có thể truy xuất đến thủ tục cấp thấp, phần cứng. Do vậy HĐH khó kiểm soát và bảo vệ hệ thống ¾ Khi xây dựng thủ tục phải định nghĩa rõ tham số đầu vào, tham số đầu ra Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 ¾HĐH thiếutínhchủđộng trong việcquảnlýmôi17 Trần Hồ Thủy Tiên trường. (tính chất tĩnh, chỉ được kích hoạt khi cần)
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống nguyên khối Ví dụ: Cấu trúc MSDOS Chương trình ứng dụng Chương trình hệ thống thường trú Drivers MSDOS Drivers ROM-BIOS Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 18 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống nguyên khối ¾ Hoạt động củabộ xử lý được chia làm 2 chếđộ -Chế độ Kernel: chạy thực hiện các thủ tục của HĐH (lờigọihệ thống) -Chế độ User: chạy thực hiện các CT của NSD Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 19 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống nguyên khối ¾Khi HĐH khởi động tất cả các lời gọi hệ thống đều được nạp và định vị vào RAM. ¾HĐH tạo bảng Dispatch gồm các Slot, mỗi Slot là một con trỏ trỏ đến Đ/C đầu của mộtCT phục vụ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 20 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống phân lớp ¾ Hệ thống được xây dựng bởi nhiều lớp. ¾ Mỗi lớp được xây dựng dựa trên các lớp bên trong ¾ Lớp trong cùng (lớp 0): phần cứng ¾ Lớp ngoài cùng (lớp N): giao diện với NSD ¾ Mỗi lớp là một đối tượng trừu tượng (dữ liệu+thao tác xử lý dữ liệu). ¾ Mỗi lớpcóthể gọi các thủ tục của các lớp bên trong Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 21 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Hệ thống phân lớp Ví dụ: hệ thống THE (Technische Hogeschool Eidhoven) thiết kế năm 1968 Lớp 5: Chương trình ứng dụng Lớp 4: Quản lý bộ đệm cho thiết bị nhập/xuất Lớp 3: Trình điều khiển thao tác console Lớp 2: Quản lý bộ nhớ Lớp 1: Điều phối CPU Lớp 0: Phần cứng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 22 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Máy ảo Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 23 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Mô hình Client-Server ¾ HĐH bao gồm nhiều tiến trình đóng vai trò Server với các chức năng chuyên biệt. ¾ Phần hạt nhân HĐH đóng vai trò giao tiếp giữa tiến trình Client và tiến trình Server. ¾ Chỉ có phần hạt nhân cực nhỏ phụ thuộc vào phần cứng. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 24 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Mô hình Client-Server Tiến Tiến Server Server Server trình trình quản lý quản lý quản lý Client Client tiến đầu bộ nhớ trình cuối Hạt nhân Message Phần cứng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 25 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 1. MỞ ĐẦU Mô hình Client-Server Ví dụ: Cấu trúc Windows NT OS/2 Win32 OS/2 Win32 Subsystem Subsystem Executive Services Object Security Virtual Process I/O Manager Monitor Memory Manager Manager Kernel Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 26 Trần Hồ Thủy TiênHardware
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các vấn đề 1. Các khái niệm 2. Mô hình trạng thái 3. Thao tác trên tiến trình 4. Điều phối tiến trình 5. Đồng bộ hoá tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 27 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm ¾ Tiến trình (Process): chương trình đang thực hiện ¾ Mỗi tiến trình có một tập tài nguyên và môi trường riêng (con trỏ lệnh, Stack, thanh ghi, không gian địa chỉ) ¾ Các tiến trình hoàn toàn độc lập với nhau, có thể liên lạc thông qua các cơ chế truyền tin giữa các tiến trình. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 28 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm ¾ Tiến trình hệ thống: được sinh ra khi thực hiện các lời gọi hệ thống ¾ Tiến trình của người sử dụng: được sinh ra khi thực thi CT của NSD Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 29 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm ¾Có2loại tiến trình: -Tiến trình kế tiếp: thời điểm bắt đầu của tiến trình này nằm sau thời điểm kết thúc của tiến trình kia -Tiến trình song song: thời điểm bắt đầu của tiến trình này nằm trước thời điểm kết thúc của tiến trình kia Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 30 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm s1>=f0 P0 P1 s0>=f1 0s0 f0 s1 f1 t s1<=f0 P0 P1 s0<=f1 0s0 s1 f0 f1 t Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 31 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm ¾ HĐH quản lý tiến trình thông qua khối quản lý tiến trình (Process Control Block:PCB) ¾ PCB: vùng nhớ lưu trữ các thông tin mô tả cho tiến trình như: • Định danh của tiến trình: phân biệt giữa các tiến trình. • Trạng thái tiến trình: hoạt động hiện hành của tiến trình. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 32 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm • Ngữ cảnh của tiến trình: - Trạng thái CPU: nội dung các thanh ghi (IP). Lưu trữ nội dung thanh ghi khi xảy ra ngắt. - Bộ xử lý: xác định số hiệu CPU mà tiến trình đang sử dụng (máy có cấuhìnhnhiềuCPU). - Bộ nhớ chính: danh sách các vùng nhớ được cấp cho tiến trình. - Tài nguyên sử dụng: danh sách các tài nguyên hệ thống mà tiến trình đang sử dụng. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 - Tài nguyên tạo lập: danh sách các tài nguyên 33được Trần Hồ Thủy Tiên tiến trình tạo lập.
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm • Thông tin giao tiếp: - Tiến trình cha: tiến trình tạo lập tiến trình này - Tiến trình con: các tiến trình do tiến trình này tạo ra - Độ ưu tiên: thông tin giúp bộ điều phối lựa chọn tiến trình được cấp CPU • Thông tin thống kê về hoạt động của tiến trình: - Thời gian sử dụng CPU - Thời gian chờ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 34 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm Khối quản lý tiến trình 1 PID Status 2 Ready List/WaitingList CPU-State-Rec Processor 3 Main store Unit1 Unit2 Resource RCB1 RCB2 Created resource RCB1 RCB2 Parent PCB 4 Progeny Priority PCB1 PCB2 PCB3 CPU time 5 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 35 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Các khái niệm ¾ Tiểu trình (Threads): một đơn vị xử lý cơ bản của hệ thống. ¾ Một tiểu trình cũng có thể tạo lập các tiến trình con ¾ Một tiến trình có thể sở hữu nhiều tiểu trình ¾ Các tiểu trình trong cùng một tiến trình có thể: - Chia sẻ một không gian địa chỉ. - Truy xuất đến các Stack của nhau Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 36 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Mô hình trạng thái Các trạng thái của tiến trình • Mới tạo: tiến trình đang được tạo lập. • Running: tiến trình đang được xử lý. • Ready: tiến trình đang sẵn sàng, chờ cấpCPU để xử lý • Blocked: tiến trình bị chặn, không thể tiếp tục. • Kết thúc: tiến trình hoàn tất xử lý. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 37 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Mô hình trạng thái Sơ đồ chuyển trạng thái của tiến trình Mới tạo Kết thúc 5 1 3 Ready Running 2 6 4 Blocked Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 38 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Mô hình trạng thái Sơ đồ chuyển trạng thái của tiến trình (1) Tiến trình mới tạo lập được đưa vào hệ thống. (2) Bộđiều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU. (3) Tiến trình kết thúc, bộ điều phối thu lại CPU. (4) Tiến trình yêu cầu tài nguyên nhưng chưa được đáp ứng, hoặc phải chờ một sự kiện hay thao tác nhập/xuất. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 39 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Mô hình trạng thái Sơ đồ chuyển trạng thái của tiến trình (5) Bộđiều phối chọn một tiến trình khác để xử lý. (6) Tài nguyên mà tiến trình yêu cầu đã sẵn sàng để cấp phát, hay sự kiện, thao tác nhập/xuất tiến trình đang đợi hoàn tất. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 40 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Thao tác trên tiến trình Tạo lập tiến trình - Một tiến trình có thể tạo lập nhiều tiến trình mới - Tiến trình tạo ra tiến trình mới gọi là tiến trình cha - Tiến trình mới được tạo ra gọi là tiến trình con - Tiến trình con đến lượt lại tạo ra một loạt các tiến trình con của nó, Quá trình này tiếp tục sẽ tạo thành cây tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 41 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Thao tác trên tiến trình Tạo lập tiến trình - Khi tạo lập tiến trình,HĐH cần thực hiện: 9 Định danh cho tiến trình (PID) 9 Đưa tiến trình vào danh sách quản lý của hệ thống 9 Xác định độ ưu tiên của tiến trình 9 Tạo khối quản lý tiến trình (PCB) 9 Cấp phát tài nguyên ban đầu cho tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 42 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Thao tác trên tiến trình Kết thúc tiến trình Khi tiến trình kết thúc, HĐH thực hiện: - Thu hồi các tài nguyên của hệ thống đã cấp phát cho tiến trình - Huỷ tiến trình khỏi tất cả các danh sách quản lý của hệ thống - Huỷ bỏ PCB của tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 43 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Mục tiêu điều phối Tiêu chuẩn điều phối Điều phối không độc quyền, điều phối độc quyền Đồng hồ ngắt giờ Độ ưu tiên của tiến trình Tổ chức điều phối Các chiến lược điều phối Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 44 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Mục tiêu điều phối - Sự công bằng giữa các tiến trình - Tính hiệu quả (tậndụng 100% thờigiansử dụng CPU) - Cực tiểu hoá thời gian lưu lại trong hệ thống - Thời gian đáp ứng hợp lý (cựctiểuhoáthờigian hồi đáp cho các tương tác củaNSD) - Thông lượng tối đa (cực đại hoá số công việc được Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 xử lý trong một thời gian cố định) 45 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Tiêu chuẩn điều phối (đặc điểmcủatiếntrình) - Tính hướng xuất/nhập của tiến trình - Tính hướng xử lý của tiến trình - Tiến trình tương tác hay xử lý theo lô - Độ ưu tiên của tiến trình - Thời gian đã sử dụng CPU của tiến trình - Thời gian còn lại tiến trình cần để hoàn tất Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 46 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Điều phối độc quyền - Tiến trình khi nhận được CPU thì có độc quyền sử dụng cho đến khi tiến trình hoàn tất hay tự nguyện giải phóng CPU - Quyết định điều phối CPU xảy ra khi: + Tiến trình chuyển từ trạng thái Running sang Blocked + Tiến trình kết thúc Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 - Giải thuật đơn giản, dễ cài đặt nhưng ngăn c47ản các tiến trình cònTrầ nl ạHiồ Thtrongủy Tiên hệ thống có cơ hội để xử lý
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Điều phối không độc quyền - Tiến trình có thể bị tạm dừng hoạt động bất cứ lúc nào mà không được báo trước, để tiến trình khác xử lý. (khi có một tiến trình khác có độ ưu tiên cao hơn về quyền dành sử dụng CPU) - Quyết định điều phối CPU xảy ra khi: + Tiến trình chuyển từ trạng thái Running sang Blocked +Tiến trình chuyển từ trạng thái Running sang Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 48 Ready Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Điều phối không độc quyền + Tiến trình chuyển từ trạng thái blocked sang Ready + Tiến trình kết thúc - Ngăn cản được tình trạng các tiến trình độc chiếm CPU, nhưng việc tam dừng một tiến trình dẫn đến các mâu thuẫn trong truy xuất. Đòi hỏi phương pháp đồng bộ hoá thích hợp Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 49 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Đồng hồ ngắt thời gian - Bộđếm thời gian qui định một thông số thời gian t thích hợp ứng với một lượt cấp CPU cho một tiến trình - Sau một khoảng thời gian t sẽ xảy ra một ngắt báo hiệu hết thời gian sử dụng CPU của tiến trình hiện hành. HĐH sẽ thu hồi CPU và bộ điều phối sẽ quyết định tiến trình nào sẽ được cấp phát. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 50 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Độ ưu tiên của tiến trình - Độ ưu tiên của tiến trình: giá trị giúp phân định tầm quan trọng của các tiến trình - Độ ưu tiên tĩnh: + Được gán sẵn cho tiến trình khi mới được ta ra + Không thay đổi - Độ ưu tiên động: thay đổi theo thời gian và môi trường xử lý của tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 51 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Tổ chức điều phối - Danh sách sẵn sàng (Ready List) - Danh sách chờ đợi (Waiting List) - Các danh sách chờ đợi riêng cho từng tài nguyên (thiếtbị ngoạivi) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 52 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Tổ chức điều phối Ready List CPU I/O waitingList Yêu cầu Hết quyền sử dụng Ngắt Đợi một ngắt Sơ đồ chuyển đổi giữa các danh sách điều phối Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 53 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Chiến lược điều phối - Thuật toán FIFO - Thuật toán Round Robin (xoay vòng) - Thuật toán SJF (Shortest-Job-First) - Thuật toán sử dụng độ ưu tiên Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 54 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Chiến lược điều phối Ready List C B A CPU Điều phối FIFO Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 55 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Chiến lược điều phối Ready List A C B A CPU Điều phối Round Robin Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 56 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Điều phối tiến trình Tổ chức điều phối - Danh sách sẵn sàng (Ready List) - Danh sách chờ (Waiting List) - Các danh sách chờ riêng cho từng tài nguyên (thiết bị ngoạivi) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 57 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Nhu cầu đồng bộ hoá - Yêu cầu truy xuất độc quyền - Yêu cầu phối hợp Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 58 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Miền găng (Critical Section) - Vấn đề tranh đoạt điều khiển if (taikhoan-tienrut)>=0 taikhoan=taikhoan-tienrut; else error ( >); - Khái niệm miền găng: Đoạn chGiáoươ trìnhng Nguyên trình lý H ệ cóđiều hành kh ả- năng xảy ra các mâu 10/2/2007 59 thuẫn truy xuTrầấn tH ồtrênThủy Tiên tài nguyên chung
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Miền găng (Critical Section) - Điều kiện giải quyết tốt bài toán miền găng: • Không có 2 tiến trình cùng ở trong miền găng • Không phụ thuộc vào tốc độ của tiến trình • Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng • Không có tiến trình nào phải chờ vô hạn để được Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 vào miền găng. 60 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Sử dụng biến khoá - Dùng biến lock chung cho các tiến trình - Nếu lock==1 thì khoá, không cho tiến trình vào miền găng. Chờ cho đến khi lock==0 - Nếu lock==0 thì cho tiến trình vào miền găng, đặt lock==1 để khoá không cho các tiến trình khác vào miền găng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 61 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Sử dụng biến khoá - Giải thuật sử dụng biến khoá để đồng bộ while (1) { while (lock==1);// wait lock=1; critical_section(); lock=0; Noncritical_section(); Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 62 } Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình - Giải thuật sử dụng biến khoá để đồng bộ while (1) { while (lock==1);// wait lock=1; critical_section(); lock=0; non_critical_section(); } Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 63 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH CHƯƠNG 5. HỆ THỐNG FILE Đồng bộ hoá tiến trình - Ví dụ: Áp dụng giải thuật sử dụng biến khoá để đồng bộ while (1) { t=t*2; while (lock==1);// wait lock=1; for (s=0,i=0;i<=t;i++) s+=i; printf(“s=%i”,s); lock=0; Giáo trìnhbreak; Nguyên lý Hệ điều hành - 10/2/2007 64 Trần Hồ Thủy Tiên }
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾Kiểm tra luân phiên - Các tiến trình muốn đi vào miền găng thì được gắn nhãn 0|1 - Sử dụng biến turn để chỉ thứ tự luân phiên. - Nếu turn==0: tiến trình có nhãn 0 được vào miền găng - Nếu turn==1: tiến trình có nhãn 1 được vào miền Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 găng 65 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾Kiểm tra luân phiên - Giải thuật của tiến trình có nhãn 0 while (1) { while (turn != 0);// wait critical_section(); turn=1; non_critical_section(); Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 66 } Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾Kiểm tra luân phiên - Giải thuật của tiến trình có nhãn 1 while (1) { while (turn != 1);// wait critical_section(); turn=0; non_critical_section(); Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 67 } Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Giải pháp Peterson #define N 2 // Chỉ 2 tiến trình int turn=0, interested[N]={0,0}; void enter_region(int process) // Vào ĐG { int other=1-process;//other là tiến trình đối của process interested[prcess]=1; turn=process; while ((turn==process)&&interested[other]==1);//chờ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 68 } Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Giải pháp Peterson void leave_region(int process) // Ra khỏi ĐG { interested[prcess]=0; } Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 69 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Giải pháp Sleep and Wakeup - Sử dụng 2 thủ tục: sleep và wakeup - Khi tiến trình chưa đủ điều kiện để vào miền găng, nó goi sleep để tự khoá đến khi một tiến trình khác gọi wakeup để đánh thức nó. - Tiến trình khi ra khỏi miền găng sẽ gọi wakeup để đánh thức tiến trình khác. - int busy;// 1: nếu miền găng đang bận, 0:không bận Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 70 - int blocked;//đếTrmần H sồốTh ủlyượ Tiênng tiến trình đang bị khoá
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Đồng bộ hoá tiến trình Giải pháp ¾ Giải pháp Sleep and Wakeup Giải thuật: while (1) { busy=0; if (busy) { if (blocked) { blocked=blocked+1; wakeup(process); sleep(); blocked=blocked-1; } } else busy=1; noncritical_section(); Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 71 critical_section();Trần Hồ Th ủy Tiên }
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn Thuật toán: Sử dụng các cấu trúc dữ liệu sau: int allocation[numprocs,numresources]; //allocation[p,r] số lượng tài nguyên r thực sự cấp phát cho p int max[numprocs,numresources]; // max[p,r] nhu cầu tối đa của tiến trình p về tài nguyên r int need[numprocs,numresources]; //need[p,r]=max[p,r]-allocation[p,r] int available[numresources] Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 72 //available[r] sTrốầ nl ượHồ Thngủy tàiTiên nguyên r còn tự do
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn Thuật toán: int word[numresouces]=available; int finish[numproces]=false; 1. Tìm i sao cho a. finish[i]==false; b. need[i,j]<=word[j]; với mọi tài nguyên j nếu không có i như thế, đến bước 3 2. Word[j]=word[j]+allocation[i,j]; finish[i]=true; đến bước 1; Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 3. Nếu finish[i]==true với mọi i thì hệ thống ở trạng thái73 an Trần Hồ Thủy Tiên toàn. Ngược lại hệ thống bị tắc nghẽn
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn ví dụ: giả sử tình trạng hiện hành của hệ thống được mô tảởbảng dưới. Nếu tiến trình P2 yêu cầu cấp 4 R1, 1 R3. Hãy cho biết yêu cầu này có thể đáp ứng mà không xảy ra tình trạng tắt nghẽn Max Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 4 1 2 P2 6 1 3 2 1 1 P3 3 1 4 2 1 1 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 P4 4 2 2 0 0 2 74 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn ví dụ: Available[1]=4, Available[3]=2 đủ để thoả mãn yêu cầu của P2, ta có Need Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 2 2 1 0 0 0 1 1 P2 0 0 1 6 1 2 P3 1 0 3 2 1 1 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 P4 4 2 0 0 0 2 75 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn ví dụ: Need Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 2 2 1 0 0 6 2 3 P2 0 0 0 0 0 0 P3 1 0 3 2 1 1 P4 4 2 0 0 0 2 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 76 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn ví dụ: Need Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 0 0 0 0 0 0 7 2 3 P2 0 0 0 0 0 0 P3 1 0 3 2 1 1 P4 4 2 0 0 0 2 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 77 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn Ví dụ: Need Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 0 0 0 0 0 0 9 3 4 P2 0 0 0 0 0 0 P3 0 0 0 0 0 0 P4 4 2 0 0 0 2 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 78 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn Ví dụ: Need Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 0 0 0 0 0 0 9 3 6 P2 0 0 0 0 0 0 P3 0 0 0 0 0 0 P4 0 0 0 0 0 0 Trạng thái kết quả là an toàn, có thể cấp phát. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 79 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 2. TIẾN TRÌNH Xác định trạng thái an toàn Bài tập: Max Allocation Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 4 1 2 P2 6 1 3 2 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 Tiến trình P2 yêu cầu 4 R1, 1 R3. Hãy cho biết yêu cầu này có thể đáp ứng mà đảm bảo không xảy ra Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 80 tình trạng tắt nghTrần ẽHnồ Th hayủy Tiên không?
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Các vấn đề 1. Khái niệm 2. Không gian địa chỉ và không gian vật lý 3. Cấp phát liên tục 4. Cấp phát không liên tục 5. Bộ nhớảo Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 81 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Khái niệm ¾ Bộ nhớ là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài. ¾ Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ. ¾ Việc trao đổi với môi trường ngoài thông qua thao tác đọc, ghi dữ liệu vào một địa chỉ cụ thể trong bộ nhớ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 82 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Khái niệm ¾Hệ điều hành thực hiện: - Sự tương ứng giữa địa chỉ logic và địa chỉ vật lý - Quản lý bộ nhớ vật lý - Chia sẻ thông tin - Bảo vệ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 83 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Không gian địa chỉ và không gian vật lý - Địa chỉ logic (địachỉảo): các địa chỉ do bộ xử lý tạo ra. - Địa chỉ vật lý: địa chỉ thực tế mà trình quản lý bộ nhớ nhìn thấy và thao tác. - Không gian địa chỉ: tập hợp tất cả các địa chỉảo phát sinh bởi một chương trình. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 84 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Không gian địa chỉ và không gian vật lý - Không gian vật lý: tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉảo. - MMU (Memory Management Unit): một cơ chế phần cứng chuyển đổi địa chỉảo thành địa chỉ vật lý. - Chương trình của NSD chỉ thao tác trên địa chỉảo. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 85 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ đơn chương Các hệ thống đa chương với phân vùng cố định Các hệ thống đa chương với phân vùng động Các hệ thống đa chương với kỹ thuật “Swapping” Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 86 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ đơn chương 0xFFF Tiến trình người dùng Hệ điều hành 0 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Tổ chức bộ nhớ trong hệ thống đơn chương 87 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đơnchương - Sử dụng thanh ghi giới hạn: địa chỉ cao nhất của vùng nhớ được cấp cho HĐH - Tất cả các địa chỉ được tiến trình NSD truy xuất đến sẽ được so sánh với nội dung thanh ghi giới hạn. +Nếu lớn hơn: hợp lý. + Ngược lại:một ngắt sẽ được phát sinh báo sự truy xuất bất hợp lý. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 88 - Tại một thờiTr đầni ểHồmTh ủchy Tiênỉ có một chương trình được xử lý.
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đơnchương Ví dụ:Trong HĐH MSDOS, một lúc chỉ thực thi được một lệnh. Khi NSD gõ lệnh lập tức lệnh đó được thực hiện và sau khi hoàn tất, con trỏ xuất hiện sau dấu nhắc đợi lệnh chờ NSD gõ lệnh tiếp theo. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 89 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định - Bộ nhớ được chia thành các phân vùng (kích thước khác hay bằng nhau) - Các tiến trình có nhu cầu bộ nhớ sẽ được lưu trữ vào hàng đợi. - Sử dụng nhiều hàng đợi - Sử dụng một hàng đợi Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 90 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định Partition 4 500K Partition 3 200K Partition 1 100K Hệ điều hành 0 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Phân vùng cố định nhiều hàng đợi 91 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định Partition 4 500K Partition 3 200K Partition 1 100K Hệ điều hành 0 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Phân vùng cố định một hàng đợi 92 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định nhiều hàng đợi - Mỗi phân vùng có một hàng đợi - Mỗi tiến trình mới được tạo lập sẽ được đưa vào hàng đợi của phân vùng có kích thước nhỏ nhất đủ để thoả mãn nhu cầu chứa nó. - Các hàng đợi của một số phân vùng trống, đầy. Các tiến trình phải chờ được cấp phát bộ nhớ. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 93 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định một hàng đợi - Tất cả các tiến trình được đặt trong một hàng đợi. - Khi có một phân vùng tự do, tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng này cho xử lý. - Kích thước của tiến trình không đúng bằng kích thước của phân vùng tự do ⇒ phân mảnh nộivi - Mức độ đa chương bị giới hạn bởi số lượng phân Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 94 vùng Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định một hàng đợi - Giải quyết2vấn đề của đa chương: sự tái định vị, sự bảo vệ Ví dụ:giả sử chương trình truy xuất đến địa chỉ 100 (địa chỉ tương đối), ct được nạp vào phân vùng 1 địa chỉ bắt đầu 100k, thì địa chỉ truy xuất là (100k+100) - Tái định vị vào thời điểm nạp chương trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 95 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định một hàng đợi - Sử dụng các thanh ghi đặc biệt: phần cứng • Thanh ghi nền (Base Register) • Thanh ghi giới hạn (Limit Register) - Khi một tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được nạp, nạp vào thanh ghi giới hạn kích thước của tiến trình. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 96 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định một hàng đợi - Địa chỉảo được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạmvi phân vùng cấp cho nó. - Địa chỉ vật lý=địa chỉảo+địa chỉ trong thanh ghi nền. - Sử dụng thanh ghi nền là có thể di chuyển các chương trình trong bộ nhớ sau khi chúng bắt đầu Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 xử lý. Chỉ cần nạp lại thanh ghi nền. 97 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng cố định ¾ Phân vùng cố định một hàng đợi Limit Base Register Register Địa chỉ yes Địa chỉ ảo vật lý CPU < + Bộ nhớ no Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Địa chỉ có lỗi 98 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng động - Xảy ra hiện tượng phân mảnh ngoạivi - Kỹ thuật“dồn bộ nhớ”: kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục ⇒ Các tiến trình có thể bị di chuyển. ⇒ Kích thước tiến trình tăng trưởng trong quá trình xử lý mà không còn vùng nhớ trống gần kề (dời chỗ tiến trình, cấp phát dư). Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 99 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng động C C C B B D A A A A A HĐH HĐH HĐH HĐH HĐH Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Cấp phát các phân vùng động 100 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng động - Giải pháp cấp phát động ¾ Quản lý bằng một bảng các bit ¾ Quản lý bằng danh sách Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 101 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng động ¾ Quản lý bằng một bảng các bit ABCD 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 102 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với phân vùng động ¾ Quản lý bằng danh sách ABCD 0 46 91114 P 0 4 H 4 2 P 6 3 P 9 2 P 14 4 H 11 3 Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 103 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với kỹ thuật “Swapping” Vùng nhớ Swap out dành cho P1 NSD Swap in P2 HĐH Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 104 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát liên tục Các hệ thống đa chương với kỹ thuật “Swapping” - Chuyển một tiến trình đang ở trạng thái chờ nằm sang bộ nhớ phụ. (swap out) - Khi đến lượt nó sẽ được mang trở lại bộ nhớ chính để tiếp tục xử lý. (swap in) - Xảy ra hiện tượng phân mảng ngoạivi. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 105 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang Phân đoạn Phân đoạn kết hợp phân trang Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 106 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Ý tưởng ¾ Cơ chế MMU ¾ Chuyển đổi địa chỉ ¾ Cài đặt bảng trang ¾ Tổ chức bảng trang Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 107 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Ý tưởng - Bộ nhớ vật lý: chia thành các khối (khung trang) có kích thước bằng nhau. - Không gian địa chỉ: chia thành các khối (trang) có kích thước trùng bằng khung trang. - Khi cần nạp một tiến trình để xử lý, các trang của tiến trình sẽ được nạp vào các khung trang còn trống. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 108 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Ý tưởng - Tiến trình có kích thước N trang, sẽ yêu cầuN khung trang tự do. Page 1 Page 0 Page 1 Page 0 Page 2 Page 3 Page 3 Page 2 Không gian địa chỉ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Không gian vật lý 109 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Cơ chế MMU(Memory Management Unit) - Cơ chế phần cứng hỗ trợ chuyển đổi địa chỉ trong cơ chế phân trang (bảng trang). - Mỗi phân tử trong bảng trang: địa chỉ bắt đầu lưu trữ trang tương ứng trong bộ nhớ vật lý;số hiệu khung trang tương ứng. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 110 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Chuyển đổi địa chỉ - Địa chỉ phát sinh bởiCPUgồm2phần: p,d + p: số hiệu trang + d: địa chỉ tương đối - Địa chỉ vật lý=địa chỉ bắt đầu của trang + d. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 111 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Chuyển đổi địa chỉ Địa chỉ Địa chỉ vật lý logic Bộ nhớ CPU P d f d vật lý Bảng trang p f Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 112 TrầCn ơHồchThếủyph Tiênần cứng hỗ trợ phân trang
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Cài đặt bảng trang - Sử dụng tập các thanh ghi: bảng trang có kích thước nhỏ. - Lưu trữ trong bộ nhớ,sử dụng thanh ghi nền(PTBR) để lưu địa chỉ bắt đầu bảng trang. (Page Table Basic Register) - Sử dụng bộ nhớ kết hợp (TLB), mỗi thanh ghi trong bộ nhớ gồm: (Translation Lookaside Buffers) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 • từ khoá: số hiệu trang 113 Trần Hồ Thủy Tiên • giá trị:số hiệu khung trang
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Cài đặt bảng trang Địa chỉ Địa chỉ vật lý logic Bộ nhớ CPU P d f d vật lý Bảng trang p f PTBR + Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 114 Trần Hồ Thủy Tiên Cơ chế phân trang sử dụng PTBR
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Cài đặt bảng trang Địa chỉ Địa chỉ vật lý logic Bộ nhớ CPU P d f d vật lý Bảng trang p f p f Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 TLB 115 Trần CHồơThchủyế Tiênphân trang sử dụng TLB
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Tổ chức bảng trang - Mỗi HĐHcómột cách tổ chức bảng trang. Đa số các HĐHcấp cho mỗi tiến trình một bảngtrang - Nếu không gian địa chỉ có dung lượng quá lớn. Bảng trang đòi hỏi một vùng nhớ quá lớn. Có 2 giải pháp: • Phân trang đa cấp. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 116 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang ¾ Tổ chức bảng trang • Phân trang đa cấp Phân chia bảng trang thành các phần nhỏ,bản thân bảng trang cũng sẽ được phân trang Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 117 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân trang Page 1 ¾ Tổ chức bảng trang 1 Page 500 500 Page 501 501 Page 900 900 Bảng trang cấp1 Bảng trang cấp2 Bộ nhớ vật lý Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 Bảng trang nhị cấp 118 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Ý tưởng ¾ Cơ chế MMU ¾ Chuyển đổi địa chỉ ¾ Cài đặt bảng phân đoạn ¾ Chia sẻ phân đoạn Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 119 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Ý tưởng - Không gian địa chỉ:tập các phân đoạn(segments) có kích thước khác nhau, có liên hệ logic với nhau - Mỗi phân đoạn: - Mỗi địa chỉ logic: Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 120 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn Mô hình phân ¾ Ý tưởng đoạn bộ nhớ Bảng ký hiệu Stack CT chính CT con Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 121 TrKhôngần Hồ Th gianủy Tiên địa chỉ Không gian vật lý
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Cơ chế MMU - Sử dụng bảng phân đoạn: • Thanh ghi nền: địa chỉ vật lý nơi bắt đầu của phân đoạn • Thanh ghi giới hạn: chiều dài của phân đoạn Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 122 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Chuyển đổi địa chỉ - Mỗi địa chỉ logic: • s: số hiệu phân đoạn • d: địa chỉ tương đối offset, có giá trị từ 0 đến độ dài phân đoạn. - Địa chỉ vật lý=d+ giá trị chứa trong thanh ghi nền Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 123 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Chuyển đổi địa chỉ s limit base Bảng phân CPU sd đoạn Bộ đúng < + nhớ vật lý sai Lỗi địa chỉ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 124 Cơ chế phầTrn ầcnứ Hngồ Th hủyỗ Tiêntrợ kỹ thuật phân đoạn
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Cài đặt bảng phân đoạn - Sử dụng tập các thanh ghi: bảng phân đoạn có kích thước nhỏ. - Lưu trữ trong bộ nhớ:bảng phân đoạn có kích thước lớn • Thanh ghi nền bảng phân đoạn (STBR) để lưu địa chỉ bắt đầu bảng phân đoạn (Segment Table Basic Register) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 125 • Thanh ghi đặTrc ầtnả HồkíchThủy Tiên thước bảng phân đoạn (STLR)
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Cài đặt bảng phân đoạn 6700 Segment 1 6300 limit base 4700 Bảng ký Segment 1 Segment 2 1400 hiệu 1000 4300 Stack Segment 2 400 6300 Segment 3 CT chính 3200 CT con Segment 3 400 4300 2400 Segment 0 1100 3200 Segment 0 Giáo trình Nguyên lý Hệ điều hành - 1400 10/2/2007 Không gian địa chỉ 126 Trần Hồ Thủy Tiên Hệ thống phân đoạn Không gian vật lý
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Cài đặt bảng phân đoạn STBR + s đúng limit base STLR < Bảng phân CPU sd đoạn Bộ đúng < + nhớ vật lý sai Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 127 Trần HLồ Thỗiủ địy Tiêna chỉ
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Chia sẻ phân đoạn - Khả năng chia xẻởmức phân đoạn: chia xẻ các chương trình con. - Mỗi tiến trình có một bảng phân đoạn riêng. - Một phân đoạn được chia xẻ khi các phần tử trong bảng phân đoạn của hai tiến trình khác nhau cùng truy xuất đến một địa chỉ vật lý giống nhau Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 128 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn ¾ Chia sẻ phân đoạn Bảng phân đoạnp1 43062 limit base Không gian địa chỉ p1 editor 0 25286 43062 68348 editor 1 4425 68348 Data 1 72773 Segment 0 Bảng phân đoạnp2 data1 limit base 90003 editor Data 2 Segment 1 0 25286 43062 Segment 0 98853 8850 90003 data1 1 Giáo trìnhSegment Nguyên lý H1ệ điều hành - 10/2/2007 129 Trần Hồ Thủy Tiên Không gian địa chỉ p2
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn kết hợp phân trang ¾ Ý tưởng ¾ Cơ chế MMU ¾ Chuyển đổi địa chỉ Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 130 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn kết hợp phân trang ¾ Ý tưởng - Không gian địa chỉ:tập hợp các phân đoạn. - Mỗi phân đoạn: chia thành nhiều - Tiến trình được đưa vào hệ thống, HĐHsẽ cấp phát cho tiến trình các trang cần thiết để chứa đủ các phân đoạn của tiến trình Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 131 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn kết hợp phân trang ¾ Ý tưởng Bảng ký hiệu Stack CT chính CT con Không gian địa chỉ Không gian vật lý Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 132 TrMôần Hồ hìnhThủy Tiên phân đoạn kết hợp phân trang
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn kết hợp phân trang ¾ Chuyển đổi địa chỉ - Mỗi địa chỉ: • S: số hiệu phân đoạn • P: số hiệu trang • D: địa chỉ tương đối Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 133 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Cấp phát không liên tục Phân đoạn kết hợp phân trang ¾ Cơ chế MMU Bảng phân đoạn Bảng trang của s s một phân đoạn limit base p + f CPU s p d f d Cơ chế Giáophầ trìnhn c ứNguyênng phân lý Hệ đđiềouạ hànhn - 10/2/2007 Bộ nhớ v134ật lý kết hợp Trphânần Hồ trangThủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Bộ nhớảo - Nếu đặt toàn thể không gian địa chỉ vào bộ nhớ vật lý thì kích thước của chương trình bị giới hạn bởi kích thước bộ nhớ. - Nạp từng phần của chương trình. - Tại một thời điểm, chỉ nạp vào bộ nhớ vật lý các chỉ thị và dữ liệu củactcần thiết cho việc thi hành lệnh ở thời điểm đó. Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 135 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 4. QUẢN LÝ BỘ NHỚ Bộ nhớảo - Bộ nhớảo: kỹ thuật cho phép xử lý một tiến trình k0 được nạp toàn bộ vào bộ nhớ vật lý. - Bộ nhớảo: mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đông nhất. - NSD làm việc với địa chỉảo. Việc chuyển đổi sang địa chỉ vật lý do HĐH đảm nhiệm bằng cơ chế phần cứng Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 136 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 5. HỆ THỐNG FILE Mô hình Client-Server ¾ Hệ thống nguyên khối (Monolithic System) ¾ Hệ thống phân lớp (Layer System) ¾ Máy ảo (Virtual Machine) ¾ Mô hình Client-Server (Client-Server Model) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 137 Trần Hồ Thủy Tiên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀNẴNG CHƯƠNG 5. HỆ THỐNG FILE Mô hình Client-Server ¾ Hệ thống nguyên khối (Monolithic System) ¾ Hệ thống phân lớp (Layer System) ¾ Máy ảo (Virtual Machine) ¾ Mô hình Client-Server (Client-Server Model) Giáo trình Nguyên lý Hệ điều hành - 10/2/2007 138 Trần Hồ Thủy Tiên