Giáo trình môn Nguyên lý hệ điều hành

BỘ TÀI NGUYÊN VÀ MÔI TRƯỜNG HÀ NỘI TRƯỜNG ĐẠI HỌC TÀI NGUYÊN VÀ MÔI TRƯỜNG HÀ NỘI -------o0o-------- ThS. Vũ Văn Huân GIÁO TRÌNH NGUYÊN LÝ HỆ ĐIỀU HÀNH (Dành cho sinh viên hệ Cao đẳng) HÀ NỘI, 2011 1 LỜI NÓI ĐẦU Máy tính điện tử ra đời vào những năm 40 của thế kỷ trước. Ban đầu, phạm vi sử dụng máy tính còn rất hạn hẹp, đa phần chỉ nhằm phục vụ mục đích nghiên cứu khoa học. Để vận hành hệ thống cần phải sử dụng các công cụ phần cứng đặc biệt và thao tác vận hành rất phức tạp. Cùng phát triển song song với sự phát triển của kỹ thuật điện tử, các thế hệ máy tính về sau được cải tiến ngày càng một tinh vi hơn, có tốc độ xử lý nhanh hơn, kích thước nhỏ gọn hơn, tiêu tốn ít năng lượng hơn và đã làm nên một cuộc cách mạng trong lĩnh vực xử lý, tính toán, điều khiển tự động,. Với các thế hệ máy tính này đòi hỏi phải có sự điều khiển, vận hành một cách tự động để phá huy hiệu quả của nó một cách tối ưu nhất. Như vậy, cần phải có một chương trình phần mềm đảm bảo việc giải quyết các vấn đề nói trên. Đó chính là các hệ điều hành máy tính. Hệ điều hành là một tập hợp các phần mềm hệ thống điều khiển mọi hoạt động của máy tính và tạo môi trường giao diện giữa người sử dụng và máy tính. Vì vậy, hệ điều hành rất quen thuộc với mọi người sử dụng, tất cả mọi người sử dụng khi làm việc với máy tính cần phải biết thao tác với một hệ điều hành cụ thể. Hiểu biết, nẵm vững nguyên lý hoạt động của hệ điều hành để từ đó có thể khai thác các hệ điều hành cụ thể một cách có hiệu quả là một nhu cầu thực tế không thể thiếu được đối với các cán bộ phụ trách kỹ thuật và quản lý các hệ thống máy tính. Cuốn giáo trình “Nguyên lý hệ điều hành” được biên soạn theo đề cương môn học Nguyên lý hệ điều hành của trường Đại học Tài nguyên và Môi trường Hà Nội xây dựng. Nội dung của giáo trình đề cập một cách hệ thống những kiến thức cơ bản và chuyên sâu thuộc nội dung các kiến thức về phần mềm hệ thống. Nó cung cấp cho người học những kiến thức chung nhất về hệ điều hành máy tính, giúp người học nắm bắt được những nguyên lý cơ bản và nguyên tắc làm việc của một hệ điều hành máy tính tổng quát, từ đó áp dụng để làm việc tốt với các hệ điều hành cụ thể trên thực tế, hiểu và xử lý được các vấn đề có thể xảy ra trong hệ thống. Đồng thời nắm bắt được xu hướng phát triển các hệ điều hành mới trong tương lai. Nội dung chính của giáo trình được trình bày trong 8 chương: Chương 1: Tổng quan về hệ điều hành Chương 2: Quản lý tiến trình Chương 3: Lập lịch cho CPU Chương 4: Quản lý bộ nhớ trong Chương 5: Quản lý bộ nhớ ngoài Chương 6: Quản lý thiết bị Chương 7: Bảo vệ và an toàn hệ thống 2 Chương 8: Hệ điều hành đa xử lý Trong quá trình biên soạn tác giả đã chắt lọc những kiến thức cơ bản nhất, nhằm giúp người đọc dễ dàng tiếp cận được với môn học. Tuy nhiên do những hạn chế nhất định, chắc chắn giáo trình không tránh hỏi các thiếu sót, vì vậy rất mong nhận được các đóng góp, góp ý của đồng nghiệp và bạn đọc để giáo trình được hoàn thiện hơn. Tác giả xin gửi lời cảm ơn chân thành tới các đồng nghiệp trong khoa Công nghệ thông tin, trường Đại học Tài nguyên và Môi trường Hà Nội đã tạo điều kiện và đóng góp nhiều ý kiến quý báu để giáo trình này được hoàn thiện. Tác giả Th.S Vũ Văn Huân 3 DANH SÁCH CÁC TỪ VIẾT TẮT CPU Central Processing Unit MIPS Million Instruction Per Second PCB Page Control Block TS Test and Set FCFS First come First Served SSTF Shortest Seek Time First SJF Shortest Job First SRT Short Remain Time RR Round Robin MLQ Multi Level queue MLFQ Multi Level Feedback Queues SCB Segment Control Block FIFO First In First Out LRU Last Recently Used LFU Last Frequently Used MFU Most Frequently Used VRC Vertical Redundancy Check LRC Longitudinal Redundancy Check SPOOL Simultaneous Perpheral Operations On Line ACL Accsess Control List CSMA Carrier Sence Multiple Access LBT Listen Before Talk CSMA/CD Carrier Sence Multiple Access with Detection Collission LWT Listen While Talk FTP File Transfer Protocol CS Critical Section OSI International Organization for Standardization 4 DANH MỤC CÁC HÌNH VẼ Hình 1.1: Mối quan hệ giữa hệ điều hành và các lớp trong hệ thống ..................... 8 Hình 1.2: Sơ đồ thực hiện lời gọi hệ thống .............................................................. 15 Hình 1.3: Cấu trúc đơn giản của một monolithic system ......................................... 15 Hình 1.4: Hệ thống phân lớp của hệ điều hành UNIX ............................................. 16 Hình 1.5: Mô hình hệ thống; a) Không có máy ảo; b) Có máy ảo ........................... 18 Hình 1.6: Mô hình Client – Server ........................................................................... 19 Hình 1.7: Cấu trúc của WINDOWS NT .................................................................. 20 Hình 2.1: Mô tả tiến trình ......................................................................................... 23 Hình 2.2: Các trạng thái của một tiến trình .............................................................. 27 Hình 3.1: Các trạng thái của tiến trình liên quan đến giờ CPU ............................... 43 Hình 3.2: Sơ đồ thực hiện tiến trình ......................................................................... 43 Hình 3.3: Sơ đồ tổ chức hàng đợi các tiến trình ...................................................... 44 Hình 3.4: Phạm vi áp dụng của Long –Term Scheduler và Short – term Scheduler 45 Hình 3.5: Phạm vi áp dụng của Medium – term scheduler ...................................... 45 Hình 3.6: Tổ chức hàng đợi các tiến trình trong MLQ ............................................ 49 Hình 3.7: Tổ chức hàng đợi các tiến trình trong MLFQ .......................................... 49 Hình 4.1: Quá trình sinh địa chỉ ............................................................................... 55 Hình 4.2: Cấu trúc tuyến tính ................................................................................... 57 Hình 4.3: Cấu trúc động ........................................................................................... 57 Hình 4.4: Cấu trúc Overlay ...................................................................................... 58 Hình 4.5: Bộ nhớ phân hoạch cố định ...................................................................... 60 Hình 4.6: Bộ nhớ phân hoạch động........................................................................... 62 Hình 4.7: Tổ chức lại bộ nhớ ................................................................................... 62 Hình 4.8: Sơ đồ swapping ........................................................................................ 63 Hình 4.9: Các modul (segment) chương trình.......................................................... 65 Hình 4.10: Ánh xạ chương trình sang bộ nhớ vật lý ................................................ 65 Hình 4.11: Các trang chương trình ........................................................................... 65 Hình 4.12: Bộ nhớ vật lý và ánh xạ các trang chương trình .................................... 65 Hình 4.13: Sơ đồ kết hợp phân trang – phân đoạn ................................................... 68 Hình 4.14: Bảng trang với một số trang trên bộ nhớ phụ ........................................ 71 Hình 4.15: Các giai đoạn xử lý lỗi trang .................................................................. 72 Hình 4.16: Cấu trúc một phần tử trong bảng trang .................................................. 72 Hình 4.17: Cấu trúc một phần tử trong bảng trang .................................................. 76 Hình 5.1: Mô tả không gian đĩa từ ........................................................................... 79 Hình 5.2: Sơ đồ cấp phát liên tục ............................................................................. 81 Hình 5.3: Sơ đồ cấp phát liên kết ............................................................................. 82 Hình 5.4: Sơ đồ cấp phát theo chỉ số ....................................................................... 82 Hình 5.5: Thuật toán lập lịch FCFS ......................................................................... 83 Hình 5.6: Thuật toán lập lịch SSTF ......................................................................... 84 5 Hình 5.7: Thuật toán lập lịch Scan ........................................................................... 84 Hình 5.8: Thuật toán lập lịch C- Scan ...................................................................... 84 Hình 5.9: Thuật toán lập lịch Clook ......................................................................... 85 Hình 5.10: Thuật toán lập lịch C- Clook .................................................................. 85 Hình 5.11: Thư mực một cấp ................................................................................... 87 Hình 5.12: Thư mục hai mức ................................................................................... 87 Hình 5.13: Cấu trúc cây ........................................................................................... 88 Hình 5.14: Cấu trúc thư mục đồ thị không chu trình ............................................... 89 Hình 5.15: Kiến trúc hệ thống quản lý tập tin .......................................................... 89 Hình 5.16: Kích thước Cluster phụ thuộc vào kích thước Volume ......................... 92 Hình 7.1: Miền bảo vệ ............................................................................................... 104 Hình 7.2: Ma trận quyền truy nhập ........................................................................... 104 Hình 7.3: Cơ chế hoạt động của virus ....................................................................... 110 Hình 8.1: Một số cấu trúc kiểu điểm – điểm ............................................................. 119 Hình 8.2: Một số cấu trúc kiểu điểm – nhiều điểm ................................................... 119 Hình 8.3: Mô hình OSI .............................................................................................. 120