Giáo trình Hệ điều hành - Đại học Phan Thiết

Nội dung text: Giáo trình Hệ điều hành - Đại học Phan Thiết

1. TRƯỜNG ĐẠI HỌC PHAN THIẾT KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH HỆ ĐIỀU HÀNH LƯU HÀNH NỘI BỘ
2. MỤC LỤC Chƣơng 1. Tổng quan về hệ điều hành 11 1.1. Khái niệm về hệ điều hành 11 1.2. Phân loại hệ điều hành 12 1.2.1. Hệ thống xử lý theo lô 12 1.2.2. Hệ thống xử lý theo lô đa chƣơng 13 1.2.3. Hệ thống chia sẻ thời gian 13 1.2.4. Hệ thống song song 14 1.2.5. Hệ thống phân tán 14 1.2.6. Hệ thống xử lý thời gian thực 15 1.3. Cấu trúc hệ điều hành 16 1.3.1. Các thành phần của hệ thống 16 1.4. Các dịch vụ của hệ điều hành 20 1.5. Lời gọi hệ thống 20 1.6. Cấu trúc hệ thống 21 1.6.1. Cấu trúc đơn giản 21 1.6.2. Cấu trúc theo lớp 23 1.6.3. Mô hình Client-Server 26 1.7. Lịch sử phát triển hệ điều hành 28 1.7.1. Thế hệ 1 (1945 – 1955) 28 1.7.2. Thế hệ 2 (1955 – 1965) 28 1.7.3. Thế hệ 3 (1965 – 1980) 29 1.7.4. Thế hệ 4 (1980 - ) 29 1.7.5. Câu hỏi củng cố bài học 29 1.7.6. Bài tập 30 Chƣơng 2. Các mô hình xử lý đồng hành 31 2.1. NHU CẦU XỬ LÝ ĐỒNG HÀNH 31 1
3. 2.1.1. Tăng hiệu suất sử dụng CPU 31 2.1.2. Tăng tốc độ xử lý 32 2.2. Khái niệm tiến trình(thread) và mô hình đa tiến trình(multithread) 33 2.2.1. Nguyên lý chung : 33 2.2.2. Kernel thread và user thread 34 2.3. Tóm tắt và bài tập 35 2.3.1. Củng cố bài học 36 2.3.2. Bài tập 36 Chƣơng 3. Quản lý tiến trình 37 3.1. Tổ chức quản lý tiến trình 37 3.1.1. Các trạng thái của tiến trình 37 3.1.2. Tiến trình mới tạo đƣợc đƣa vào hệ thống 38 3.2. Chế độ xử lý của tiến trình 38 3.2.1. Thao tác trên tiến trình 40 3.2.2. Cấp phát tài nguyên cho tiến trình 42 3.2.3. Định danh tài nguyên 42 3.2.4. Các mục tiêu của kỹ thuật cấp phát : 43 Chƣơng 4. Điều phối tiến trình 43 4.1. Giới thiệu 44 4.1.1. Mục tiêu điều phối 44 4.1.2. Các đặc điểm của tiến trình 44 4.2. Điều phối không độc quyền và điều phối độc quyền (preemptive/nopreemptive) 46 4.3. Tổ chức điều phối 47 4.3.1. Các danh sách sử dụng trong quá trình điều phối. 47 4.3.2. Các cấp độ điều phối 49 4.3.3. Chiến lƣợc FIFO 50 4.3.4. Chiến lƣợc phân phối xoay vòng (Round Robin) 51 2
4. 4.4. Điều phối với độ ƣu tiên 52 4.4.1. Chiến lƣợc công việc ngắn nhất (Shortest-job-first SJF) 54 4.5. Quản lý tiến trình-Tóm tắt 55 4.5.1. Câu hỏi cũng cố bài học 55 4.5.2. Bài tập 55 Chƣơng 5. Liên lạc giữa các tiến trình và vấn đề đồng bộ hóa 59 5.1. LIÊN LẠC GIỮA CÁC TIẾN TRÌNH 59 5.1.1. Nhu cầu liên lạc giữa các tiến trình 59 5.1.2. Các vấn đề nảy sinh trong việc liên lạc giữa các tiến trình 59 5.2. Cơ chế thông tin liên lạc 60 5.2.1. Tín hiệu (Signal) 60 5.2.2. Pipe 62 5.2.3. Vùng nhớ chia sẻ 63 5.3. Trao đổi thông điệp (Message) 64 5.4. Sockets 65 5.5. Nhu cầu đồng bộ hóa(synchronisation) 67 5.5.1. Yêu cầu độc quyền truy xuất (Mutual exclusion) 67 5.5.2. Yêu cầu phối hợp (Synchronization) 67 5.6. Bài toán đồng bộ hoá 67 5.6.1. Vấn đề tranh đoạt điều khiển (race condition) 67 5.6.2. Miền găng (critical section) 68 5.7. Tóm tắt 69 5.7.1. Củng cố bài học 69 5.7.2. Bài tập 70 Chƣơng 6. Các giải pháp đồng bộ hóa 74 6.1. Giải pháp « busy waiting » 74 6.1.1. Các giải pháp phần mềm 74 6.1.2. Sử dụng việc kiểm tra luân phiên : 75 3
5. 6.2. Giải pháp của Peterson 76 6.3. Các giải pháp phần cứng 77 6.3.1. Cấm ngắt: 77 6.3.2. Chỉ thị TSL (Test-and-Set): 77 6.3.3. Các giải pháp “Sleep and wakeup” 78 6.4. Semaphore 79 6.4.1. Tổ chức truy xuất độc quyền với Semaphores: 81 6.4.2. Tổ chức đồng bộ hóa với Semaphores: 81 6.5. Monitors 82 6.6. Trao đổi thông điệp 85 6.7. Các vấn đề cổ điển của đồng bộ hoá 86 6.7.1. Vấn đề Ngƣời sản xuất – Ngƣời tiêu thụ (Producer-Consumer) 86 6.7.2. Monitor 88 6.7.3. Trao đổi thông điệp 90 6.8. Mô hình Readers-Writers 91 6.8.1. Trao đổi thông điệp 94 Chƣơng 7. Tắc nghẽn (Deadlock) 96 7.1. Định nghĩa: 96 7.2. Điều kiện xuất hiện tắc nghẽn 97 7.3. Đồ thị cấp phát tài nguyên 97 7.4. Các phƣơng pháp xử lý tắc nghẽn 98 7.5. Ngăn chặn tắc nghẽn 98 7.6. Tránh tắc nghẽn 99 7.6.1. Một số khái niệm cơ sở 99 7.7. Phát hiện tắc nghẽn 103 7.7.1. Giải thuật phát hiện tắc nghẽn 103 7.8. Hiệu chỉnh tắc nghẽn 103 Chƣơng 8. Quản lý bộ nhớ 105 4
6. 8.1. Mô hình Linker_Loader 107 8.2. Mô hình Base &Bound 107 8.3. Phân mảnh ngoại vi 109 8.4. Cấp phát không liên tục 110 8.4.1. Phân đoạn (Segmentation) 110 8.4.2. Cơ chế MMU trong kỹ thuật phân đoạn: 111 8.4.3. Chuyển đổi địa chỉ: 111 8.4.4. Cài đặt bảng phân đoạn: 112 8.5. Phân trang ( Paging) 115 8.5.1. Cơ chế MMU trong kỹ thuật phân trang: 116 8.5.2. Chuyển đổi địa chỉ: 116 8.5.3. Cài đặt bảng trang 117 8.6. Tổ chức bảng trang: 119 8.6.1. Bảo vệ: 120 8.6.2. Chia sẻ bộ nhớ trong cơ chế phân trang: 121 8.7. Phân đoạn kết hợp phân trang (Paged segmentation) 122 8.7.1. Cơ chế MMU trong kỹ thuật phân đoạn kết hợp phân trang: 123 8.7.2. Chuyển đổi địa chỉ: 123 8.8. Quản lý bộ nhớ-Tóm tắt 124 8.8.1. Một số cách tiếp cận tổ chức bộ nhớ chính 124 8.8.2. Củng cố bài học 125 8.8.3. Bài Tập 125 Chƣơng 9. Bộ nhớ ảo 128 9.1. Dẫn nhập 128 9.2. Định nghĩa 128 9.3. Cài đặt bộ nhớ ảo 129 9.4. Phân trang theo yêu cầu ( demand paging) 129 9.5. Cơ chế phần cứng : 130 5
7. 9.6. Thay thế trang 132 9.7. Sự thi hành phân trang theo yêu cầu 133 9.8. Các thuật toán thay thế trang 133 9.8.1. Thuật toán FIFO 134 9.8.2. Thuật toán tối ƣu 135 9.8.3. Thuật toán « Lâu nhất chƣa sử dụng » ( Least-recently-used LRU) 136 9.9. Các thuật toán xấp xỉ LRU 137 9.9.1. Thuật toán với các bit reference phụ trợ 137 9.9.2. Thuật toán « cơ hội thứ hai » 138 9.9.3. Thuật toán « cơ hội thứ hai » nâng cao (Not Recently Used - NRU) 139 9.10. Các thuật toán thống kê 140 9.11. Cấp phát khung trang 140 9.11.1. Số khung trang tối thiểu: 140 9.12. Trì trệ toàn bộ hệ thống (Thrashing) 141 9.13. Mô hình « tập làm việc » (working set) 142 9.14. Tần suất xảy ra lỗi trang 144 9.15. Bộ nhớ ảo-Tóm tắt 144 9.15.1. Củng cố bài học 145 9.15.2. Bài Tập 145 Chƣơng 10. Hệ thống quản lý tập tin 149 10.1. CÁC KHÁI NIỆM CƠ BẢN 149 10.1.1. Bộ nhớ ngoài 149 10.1.2. Tập tin và thƣ mục 149 10.2. Hệ thống quản lý tập tin 150 10.3. Mô hình tổ chức và quản lý các tập tin 150 10.3.1. Tập tin : 150 10.3.2. Thƣ mục : 155 10.4. Các chức năng 157 6
8. 10.4.1. Tập tin : 157 10.4.2. Thƣ mục : 158 10.5. Câu hỏi kiểm tra kiến thức 158 Chƣơng 11. Các phƣơng pháp cài đặt hệ thống quản lý tập tin 159 11.1. BẢNG QUẢN LÝ THƢ MỤC, TẬP TIN 159 11.1.1. Khái niệm 159 11.2. Bảng phân phối vùng nhớ 160 11.2.1. Khái niệm 160 11.2.2. Các phƣơng pháp 160 11.2.3. Danh sách liên kết sử dụng index : 162 11.2.4. I-nodes : 162 11.3. Tập tin chia sẻ 163 11.4. Quản lý đĩa 164 11.5. Kích thƣớc khối 165 11.6. Lƣu giữa các khối trống 165 11.7. Độ an toàn của hệ thống tập tin 166 11.7.1. Quản lý khối bị hỏng 166 11.8. Backup 166 11.9. Tính không đổi của hệ thống tập tin 167 11.10. Câu hỏi kiểm tra kiến thức 168 11.11. Bài tập 168 Chƣơng 12. Giới thiệu một số hệ thống tập tin 170 12.1. MS-DOS 170 12.1.1. Đặc điểm 170 12.1.2. Cài đặt 170 12.2. Windows95 173 12.2.1. Bộ quản lý cài đặt hệ thống tập tin (IFS) 173 12.2.2. Bộ điều khiển mô tả kiểu (TSD) 175 7
9. 12.2.3. Hỗ trợ tên tập tin dài :(LFN) 178 12.2.4. Đặc điểm của NTFS 179 12.2.5. Cấu trúc tập tin và volume của NTFS 179 12.3. Hệ thống tập tin của Unix : 181 12.3.1. Cài đặt hệ thống tập tin của Unix 183 12.4. Bài tập 184 Chƣơng 13. Hệ thống quản lý nhập-xuất 186 13.1. KHÁI NIỆM VỀ HỆ THỐNG QUẢN LÝ NHẬP/XUẤT 186 13.2. Phần cứng nhập-xuất 187 13.2.1. Thiết bị I/O 187 13.2.2. Tổ chức của chức năng I/O 188 13.2.3. DMA (Direct Memory Access) 191 13.3. Phần mềm nhập xuất 191 13.3.1. Kiểm soát ngắt 192 13.3.2. Điều khiển thiết bị (device drivers) 192 13.4. Phần mềm nhập/xuất độc lập thiết bị 193 13.5. Phần mềm nhập/xuất phạm vi ngƣời sử dụng 194 Chƣơng 14. Giới thiệu một số hệ thống I-O 195 14.1. HỆ THỐNG I/O ĐĨA 195 14.1.1. Các thuật toán đọc đĩa 196 14.1.2. Lựa chọn thuật toán lập lịch : 199 14.2. Hệ thống I-O chuẩn (terminals) 201 14.2.1. Phần cứng terminal 201 14.2.2. Terminal ánh xạ bộ nhớ 203 14.2.3. Phần mềm nhập 205 14.2.4. Phần mềm xuất 206 14.3. Cài đặt đồng hồ 207 14.3.1. Phần cứng đồng hồ 207 8
10. 14.3.2. Phần mềm đồng hồ 208 14.4. Câu hỏi kiểm tra kiến thức 209 14.5. Bài tập 210 Chƣơng 15. Bảo vệ an toàn hệ thống 211 15.1. Mục tiêu bảo vệ hệ thống (Protection) 211 15.2. Miền bảo vệ (Domain of Protection ) 212 15.2.1. Khái niệm 212 15.2.2. Cấu trúc của miền bảo vệ 212 15.2.3. Mối liên kết giữa một tiến trình và một miền bảo vệ có thể tĩnh hay động : 213 15.3. Ma trận quyền truy xuất ( Access matrix) 213 15.4. Bảng toàn cục 217 15.4.1. Danh sách quyền truy xuất ( Access control list _ ACL) 217 15.4.2. Danh sách tiềm năng của miền bảo vệ (Capability list – C_List) 218 15.5. Cơ chế khóa và chìa 219 15.6. An toàn hệ thống (Security) 220 15.6.1. Các vấn đề về an toàn hệ thống 220 15.6.2. Mối đe dọa từ các chƣơng trình 221 Chƣơng 16. Hệ điều hành windowns NT 222 16.1. LỊCH SỬ 222 16.2. MỤC TIÊU THIẾT KẾ 222 16.3. CÁC THÀNH PHẦN HỆ THỐNG 223 16.4. KIẾN TRÚC HỆ ĐIỀU HÀNH WindowsNT 224 16.5. CÁC MODULE QUẢN LÝ CỦA WindowsNT 224 16.6. Hệ thống tập tin 226 16.7. Quản lý nhập xuất 227 Chƣơng 17. Hệ điều hành Linux -Giới thiệu 228 17.1. GIỚI THIỆU 228 9
11. 17.2. Tổ chức hệ thống 229 17.2.1. Hệ thống tập tin 229 17.2.2. „hệ thống tập tin mở rộng thế hệ 2‟ EXT2 231 17.3. Điều khiển thiết bị 231 17.4. Quản lý tiến trình 233 17.5. Quản lý bộ nhớ 234 17.6. Câu hỏi kiểm tra kiến thức 234 10
12. CHƢƠNG 1. TỔNG QUAN VỀ HỆ ĐIỀU HÀNH Bài học này cung cấp cho chúng ta một cái nhìn tổng quát về những nguyên lý cơ bản của hệ điều hành. Chúng ta bắt đầu với việc xem xét mục tiêu và các chức năng của hệ điều này, sau đó khảo sát các dạng khác nhau của chúng cũng nhƣ xem xét quá trình phát triển qua từng giai đoạn. Các phần này đƣợc trình bày thông qua các nội dung nhƣ sau: Bài học này giúp chúng ta hiểu đƣợc hệ điều hành là gì, có cấu trúc ra sao. Hệ điều hành đƣợc phân loại theo những tiêu chuẩn nào. Quá trình phát triển của hệ điều hành phụ thuộc vào những yếu tố nào. Bài học này đòi hỏi những kiến thức về : kiến trúc máy tính. 1.1. Khái niệm về hệ điều hành Hệ điều hành là một chương trình hay một hệ chương trình hoạt động giữa ngƣời sử dụng (user) và phần cứng của máy tính. Mục tiêu của hệ điều hành là cung cấp một môi trƣờng để ngƣời sử dụng có thể thi hành các chƣơng trình. Nó làm cho máy tính dể sử dụng hơn, thuận lợi hơn và hiệu quả hơn. Hệ điều hành là một phần quan trọng của hầu hết các hệ thống máy tính. Một hệ thống máy tính thƣờng đƣợc chia làm bốn phần chính : phần cứng, hệ điều hành, các chƣơng trình ứng dụng và ngƣời sử dụng. Phần cứng bao gồm CPU, bộ nhớ, các thiết bị nhập xuất, đây là những tài nguyên của máy tính. Chương trình ứng dụng nhƣ các chƣơng trình dịch, hệ thống cơ sở dữ liệu, các trò chơi, và các chƣơng trình thƣơng mại. Các chƣơng trình này sử dụng tài nguyên của máy tính để giải quyết các yêu cầu của ngƣời sử dụng. Hệ điều hành điều khiển và phối hợp việc sử dụng phần cứng cho những ứng dụng khác nhau của nhiều ngƣời sử dụng khác nhau. Hệ điều hành cung cấp một môi trƣờng mà các chƣơng trình có thể làm việc hữu hiệu trên đó. Hệ điều hành có thể đƣợc coi nhƣ là bộ phân phối tài nguyên của máy tính. Nhiều tài nguyên của máy tính nhƣ thời gian sử dụng CPU, vùng bộ nhớ, vùng lƣu trữ tập tin, thiết bị nhập xuất v.v đƣợc các chƣơng trình yêu cầu để giải quyết vấn đề. Hệ điều hành hoạt động nhƣ một bộ quản lý các tài nguyên và phân phối chúng cho các chƣơng trình và ngƣời sử dụng khi cần thiết. Do có rất nhiều yêu cầu, hệ điều hành phải giải quyết vấn đề tranh chấp và phải quyết định cấp phát tài nguyên cho những yêu cầu theo thứ tự nào để hoạt động của máy tính là hiệu quả nhất. Một hệ điều 11
13. hành cũng có thể đƣợc coi nhƣ là một chƣơng trình kiểm soát việc sử dụng máy tính, đặc biệt là các thiết bị nhập xuất. Tuy nhiên, nhìn chung chƣa có định nghĩa nào là hoàn hảo về hệ điều hành. Hệ điều hành tồn tại để giải quyết các vấn đề sử dụng hệ thống máy tính. Mục tiêu cơ bản của nó là giúp cho việc thi hành các chƣơng trình dễ dàng hơn. Mục tiêu thứ hai là hỗ trợ cho các thao tác trên hệ thống máy tính hiệu quả hơn. Mục tiêu này đặc biệt quan trọng trong những hệ thống nhiều ngƣời dùng và trong những hệ thống lớn(phần cứng + quy mô sử dụng). Tuy nhiên hai mục tiêu này cũng có phần tƣơng phản vì vậy lý thuyết về hệ điều hành tập trung vào việc tối ƣu hóa việc sử dụng tài nguyên của máy tính. 1.2. Phân loại hệ điều hành 1.2.1. Hệ thống xử lý theo lô Bộ giám sát thƣờng trực : Khi một công việc chấm dứt, hệ thống sẽ thực hiện công việc kế tiếp mà không cần sự can thiệp của ngƣời lập trình, do đó thời gian thực hiện sẽ mau hơn. Một chƣơng trình, còn gọi là bộ giám sát thƣờng trực đƣợc thiết kế để giám sát việc thực hiện dãy các công việc một cách tự động, chƣơng trình này luôn luôn thƣờng trú trong bộ nhớ chính. Hệ điều hành theo lô thực hiện các công việc lần lƣợt theo những chỉ thị định trƣớc. CPU và thao tác nhập xuất : CPU thƣờng hay nhàn rỗi do tốc độ làm việc của các thiết bị nhập xuất (thƣờng là thiết bị cơ) chậm hơn rất nhiều lần so với các thiết bị điện tử. Cho dù là một CPU chậm nhất, nó cũng nhanh hơn rất nhiều lần so với thiết bị nhập xuất. Do đó phải có các phƣơng pháp để đồng bộ hóa việc hoạt động của CPU và thao tác nhập xuất. Xử lý off_line : Xử lý off_line là thay vì CPU phải đọc trực tiếp từ thiết bị nhập và xuất ra thiết bị xuất, hệ thống dùng một bộ lưu trữ trung gian. CPU chỉ thao thác với bộ phận này. Việc đọc hay xuất đều đến và từ bộ lƣu trữ trung gian. Spooling : Spool (simultaneousperipheraloperationon-line) là đồng bộ hóa các thao tác bên ngoài on-line. Cơ chế này cho phép xử lý của CPU là on-line, sử dụng đĩa để lƣu các dữ liệu nhập cũng nhƣ xuất. 12
14. 1.2.2. Hệ thống xử lý theo lô đa chương Khi có nhiều công việc cùng truy xuất lên thiết bị, vấn đề lập lịch cho các công việc là cần thiết. Khía cạnh quan trọng nhất trong việc lập lịch là khả năng đa chƣơng. Đa chương (multiprogram) gia tăng khai thác CPU bằng cách tổ chức các công việc sao cho CPU luôn luôn phải trong tình trạng làm việc .Ý tƣởng nhƣ sau : hệ điều hành lƣu giữ một phần của các công việc ở nơi lƣu trữ trong bộ nhớ . CPU sẽ lần lƣợt thực hiện các phần công việc này. Khi đang thực hiện, nếu có yêu cầu truy xuất thiết bị thì CPU không nghỉ mà thực hiện tiếp công việc thứ hai Với hệ đa chƣơng hệ điều hành ra quyết định cho ngƣời sử dụng vì vậy, hệ điều hành đa chương rất tinh vi. Hệ phải xử lý các vấn đề lập lịch cho công việc, lập lịch cho bộ nhớ và cho cả CPU nữa. 1.2.3. Hệ thống chia sẻ thời gian Hệ thống chia sẻ thời gian là một mở rộng logic của hệ đa chƣơng. Hệ thống này còn đƣợc gọi là hệ thống đa nhiệm (multitasking). Nhiều công việc cùng đƣợc thực hiện thông qua cơ chế chuyển đổi của CPU nhƣ hệ đa chƣơng nhƣng thời gian mỗi lần chuyển đổi diễn ra rất nhanh. Hệ thống chia sẻ đƣợc phát triển để cung cấp việc sử dụng bên trong của một máy tính có giá trị hơn. Hệ điều hành chia sẻ thời gian dùng lập lịch CPU và đa chƣơng để cung cấp cho mỗi ngƣời sử dụng một phần nhỏ trong máy tính chia sẻ. Một chƣơng trình khi thi hành đƣợc gọi là một tiến trình. Trong quá trình thi hành của một tiến trình, nó phải thực hiện các thao tác nhập xuất và trong khoảng thời gian đó CPU sẽ thi hành một tiến trình khác. Hệ điều hành chia sẻ cho phép nhiều ngƣời sử dụng chia sẻ máy tính một cách đồng bộ do thời gian chuyển đổi nhanh nên họ có cảm giác là các tiến trình đang đƣợc thi hành cùng lúc. Hệ điều hành chia sẻ phức tạp hơn hệ điều hành đa chƣơng. Nó phải có các chức năng: quản trị và bảo vệ bộ nhớ, sử dụng bộ nhớ ảo. Nó cũng cung cấp hệ thống tập tin truy xuất on-line Hệ điều hành chia sẻ là kiểu của các hệ điều hành hiện đại ngày nay. 13
15. 1.2.4. Hệ thống song song Ngoài các hệ thống chỉ có một bộ xử lý còn có các hệ thống có nhiều bộ xử lý cùng chia sẻ hệ thống đƣờng truyền dữ liệu, đồng hồ, bộ nhớ và các thiết bị ngoại vi. Các bộ xử lý này liên lạc bên trong với nhau . Có nhiều nguyên nhân xây dựng dạng hệ thống này. Với sự gia tăng số lƣợng bộ xử lý, công việc đƣợc thực hiện nhanh chóng hơn, Nhƣng không phải theo đúng tỉ lệ thời gian, nghĩa là có n bộ xử lý không có nghĩa là sẽ thực hiện nhanh hơn n lần. Hệ thống với máy nhiều bộ xử lý sẽ tối ƣu hơn hệ thống có nhiều máy có một bộ xử lý vì các bộ xử lý chia sẻ các thiết bị ngoại vi, hệ thống lƣu trữ, nguồn và rất thuận tiện cho nhiều chƣơng trình cùng làm việc trên cùng một tập hợp dữ liệu. Một lý do nữa là độ tin cậy. Các chức năng đƣợc xử lý trên nhiều bộ xử lý và sự hỏng hóc của một bộ xử lý sẽ không ảnh hƣởng đến toàn bộ hệ thống. Hệ thống đa xử lý thông thƣờng sử dụng cách đa xử lý đối xứng, trong cách này mỗi bộ xử lý chạy với một bản sao của hệ điều hành, những bản sao này liên lạc với nhau khi cần thiết. Một số hệ thống sử dụng đa xử lý bất đối xứng, trong đó mỗi bộ xử lý đƣợc giao một công việc riêng biệt Một bộ xử lý chính kiểm soát toàn bộ hệ thống, các bộ xử lý khác thực hiện theo lệnh của bộ xử lý chính hoặc theo những chỉ thị đã đƣợc định nghĩa trƣớc. Mô hình này theo dạng quan hệ chủ tớ. Bộ xử lý chính sẽ lập lịch cho các bộ xử lý khác. Một ví dụ về hệ thống xử lý đối xứng là version Encore của UNIX cho máy tính Multimax. Hệ thống này có hàng tá bộ xử lý. Ƣu điểm của nó là nhiều tiến trình có thể thực hiện cùng lúc . Một hệ thống đa xử lý cho phép nhiều công việc và tài nguyên đƣợc chia sẻ tự động trong những bộ xử lý khác nhau. Hệ thống đa xử lý không đồng bộ thƣờng xuất hiện trong những hệ thống lớn, trong đó hầu hết thời gian hoạt động đều dành cho xử lý nhập xuất. 1.2.5. Hệ thống phân tán Hệ thống này cũng tƣơng tự nhƣ hệ thống chia sẻ thời gian nhƣng các bộ xử lý không chia sẻ bộ nhớ và đồng hồ, thay vào đó mỗi bộ xử lý có bộ nhớ cục bộ riêng. Các bộ xử lý thông tin với nhau thông qua các đƣờng truyền thông nhƣ những bus tốc độ cao hay đƣờng dây điện thoại. Các bộ xử lý trong hệ phân tán thƣờng khác nhau về kích thƣớc và chức năng. Nó có thể bao gồm máy vi tính, trạm làm việc, máy mini, và những hệ thống máy lớn. Các 14
16. bộ xử lý thƣờng đƣợc tham khảo với nhiều tên khác nhau nhƣ site, node, computer v.v tùy thuộc vào trạng thái làm việc của chúng. Các nguyên nhân phải xây dựng hệ thống phân tán là: Chia sẻ tài nguyên : Một ngƣời sử dụng A có thể sử dụng máy in laser của ngƣời sử dụng B và ngƣời sử dụng B có thể truy xuất những tập tin của A. Tổng quát, chia sẻ tài nguyên trong hệ thống phân tán cung cấp một cơ chế để chia sẻ tập tin ở vị trí xa, xử lý thông tin trong một cơ sở dữ liệu phân tán, in ấn tại một vị trí xa, sử dụng những thiết bị ở xa đểõ thực hiện các thao tác. Tăng tốc độ tính toán : Một thao tác tính toán đƣợc chia làm nhiều phần nhỏ cùng thực hiện một lúc. Hệ thống phân tán cho phép phân chia việc tính toán trên nhiều vị trí khác nhau để tính toán song song. An toàn : Nếu một vị trí trong hệ thống phân tán bị hỏng, các vị trí khác vẫn tiếp tục làm việc. Thông tin liên lạc với nhau :Có nhiều lúc , chƣơng trình cần chuyển đổi dữ liệu từ vị trí này sang vị trí khác. Ví dụ trong hệ thống Windows, thƣờng có sự chia sẻ và chuyển dữ liệu giữa các cửa sổ. Khi các vị trí đƣợc nối kết với nhau trong một hệ thống mạng, việc trao đổi dữ liệu diễn ra rất dễ. Ngƣời sử dụng có thể chuyển tập tin hay các E_mail cho nhau từ cùng vị trí hay những vị trí khác. 1.2.6. Hệ thống xử lý thời gian thực Hệ thống xử lý thời gian thựcđƣợc sử dụng khi có những đòi hỏi khắt khe về thời gian trên các thao tác của bộ xử lý hoặc dòng dữ liệu, nó thƣờng đƣợc dùng điều khiển các thiết bị trong các ứng dụng tận hiến (dedicated). Máy tính phân tích dữ liệu và có thể chỉnh các điều khiển giải quyết cho dữ liệu nhập. Một hệ điều hành xử lý thời gian thực phải đƣợc định nghĩa tốt, thời gian xử lý nhanh. Hệ thống phải cho kết quả chính xác trong khoảng thời gian bị thúc ép nhanh nhất. Có hai hệ thống xử lý thời gian thực là hệ thống thời gian thực cứng và hệ thống thời gian thực mềm Hệ thống thời gian thực cứng là công việc đƣợc hoàn tất đúng lúc. Lúc đó dữ liệu thƣờng đƣợc lƣu trong bộ nhớ ngắn hạn hay trong ROM. Việc xử lý theo thời gian thực sẽ xung đột với tất cả hệ thống liệt kê ở trên. Dạng thứ hai là hệ thống thời gian thực mềm, mỗi công việc có một độ ƣu tiên riêng và sẽ đƣợc thi hành theo độ ƣu tiên đó. Có một số lĩnh vực áp dụng hữu hiệu phƣơng pháp này là multimedia hay thực tại ảo. 15
17. 1.3. Cấu trúc hệ điều hành 1.3.1. Các thành phần của hệ thống a. Quản lý tiến trình Một chƣơng trình không thực hiện đƣợc gì cả nếøu nhƣ nó không đƣợc CPU thi hành. Một tiến trình là một chƣơng trình đang đƣợc thi hành, nhƣng ý nghĩa của nó còn rộng hơn. Một công việc theo lô là một tiến trình. Một chƣơng trình ngƣời dùng chia sẻ thời gian là một tiến trình, một công việc của hệ thống nhƣ soopling xuất ra máy in cũng là một tiến trình. Một tiến trình phải sử dụng tài nguyên nhƣ thời gian sử dụng CPU, bộ nhớ, tập tin, các thiết bị nhập xuất để hoàn tất công việc của nó. Các tài nguyên này đƣợc cung cấp khi tiến trình đƣợc tạo hay trong quá trình thi hành. Khi tiến trình đƣợc tạo, nó sử dụng rất nhiều tài nguyên vật lý và luận lý.cũng nhƣ một số khởi tạo dữ liệu nhập. Ví dụ , khảo sát tiến trình hiển thị trạng thái của tập tin lên màn hình. Đầu vào của tiến trình là tên tập tin, và tiến trình sẽ thực hiện những chỉ thị thích hợp, thực hiện lời gọi hệ thống để nhận đƣợc những thông tin mong muốn và hiển thị nó lên màn hình. Khi tiến trình kết thúc, hệ điềûu hành sẽ tái tạo lại các tài nguyên có thể đƣợc dùng lại Một tiến trình là hoạt động (active) hoàn toàn-ngƣợc lại với một tập tin trên đĩa là thụ động (passive)-với một bộ đếm chƣơng trình cho biết lệnh kế tiếp đƣợc thi hành.Việc thi hành đƣợc thực hiện theo cơ chế tuần tự , CPU sẽ thi hành từ lệnh đầu đến lệnh cuối. Một tiến trình đƣợc coi là một đơn vị làm việc của hệ thống. Một hệ thống có thể có nhiều tiến trình cùng lúc , trong đó một số tiến trình là của hệ điều hành, một số tiến trình là của ngƣời sử dụng. các tiến trình này có thể diễn ra đồng thời. Vai trò của hệ điều hành trong việc quản lý tiến trình là : Tạo và hủy các tiến trình của ngƣời sử dụng và của hệ thống. Ngƣng và thực hiện lại một tiến trình. Cung cấp cơ chế đồng bộ tiến trình. Cung cấp cách thông tin giữa các tiến trình. Cung cấp cơ chế kiểm soát deadlock(khái niệm này sẽ đƣợc trình bày trong chƣơng II). 16
18. b. Quản lý bộ nhớ chính : Trong hệ thống máy tính hiện đại, bộ nhớ chính là trung tâm của các thao tác, xử lý. Bộ nhớ chính có thể xem nhƣ một mảng kiểu byte hay kiểu word. Mỗi phần tử đều có địa chỉ. Đó là nơi lƣu dữ liệu đƣợc CPU truy xuất một cách nhanh chóng so với các thiết bị nhập/xuất. CPU đọc những chỉ thị từ bộ nhớ chính. Các thiết bị nhập/xuất cài đặt cơ chế DMA(xem chƣơng IV) cũng đọc và ghi dữ liệu trong bộ nhớ chính. Thông thƣờng bộ nhớ chính chứa các thiết bị mà CPU có thể định vị trực tiếp. Ví dụ CPU truy xuất dữ liệu từ đĩa, những dữ liệu này đƣợc chuyển vào bộ nhớ qua lời gọi hệ thống nhập/xuất. Một chƣơng trình muốn thi hành trƣớc hết phải đƣợc ánh xạ thành địa chỉ tuyệt đối và nạp vào bộ nhớ chính.Khi chƣơng trình thi hành, hệ thống truy xuất các chỉ thị và dữ liệu của chƣơng trình trong bộ nhớ chính. Ngay cả khi tiến trình kết thúc , dữ liệu vẫn còn trong bộ nhớ cho đến khi một tiến trình khác đƣợc ghi chồng lên. Để tối ƣu hóa quá trình hoạt động của CPU và tốc độ của máy tính, một số tiến trình đƣợc lƣu giữ trong bộ nhớ. Có rất nhiều kế hoạch quản trị bộ nhớ do có nhiều ứng dụng bộ nhớ khác nhau và hiệu quả của các thuật toán phụ thuộc vào tùy tình huống cụ thể. Lựa chọn một thuật toán cho một hệ thống đƣợc mô tả trƣớc phụ thuộc vào nhiều yếu tố, đặc biệt là phần cứng của hệ thống. Hệ điều hành có những vai trò nhƣ sau trong việc quản lý bộ nhớ chính : Lƣu giữ thông tin về các vị trí trong bộ nhớ đã đƣợc sử dụng và ai sử dụng. Quyết định tiến trình nào đƣợc nạp vào bộ nhớ chính, khi bộ nhớ đã có thể dùng đƣợc. Cấp phát và thu hồi bộ nhớ khi cần thiết. c. Quản lý bộ nhớ phụ : Mục tiêu chính của hệ thống máy tính là thi hành chƣơng trình. Những chƣơng trình với dữ liệu truy xuất của chúng phải đƣợc đặt trong bộ nhớ chính trong suốt quá trình thi hành. Nhƣng bộ nhớ chính quá nhỏ để có thể lƣu giữ mọi dữ liệu và chƣơng trình, ngoài ra dữ liệu sẽ mất khi không còn đƣợc cung cấp năng lƣợng. Hệ thống máy tính ngày nay cung cấp hệ thống lưu trữ phụ. Đa số các máy tính đều dùng đĩa để lƣu trữ cả chƣơng trình và dữ liệu. Hầu nhƣ tất cả chƣơng trình : chƣơng trình dịch, hợp ngữ, thủ tục, trình soạn thảo, định dạng đều đƣợc lƣu trữ trên đĩa cho tới khi nó đƣợc thực hiện, nạp vào trong bộ nhớ chính và cũng sử dụng đĩa để chứa dữ liệu và kết quả xử lý. Vì vậy một bộ quản lý hệ thống đĩa rất quan trọng cho hệ thống máy tính. 17
19. Vai trò của hệ điều hành trong việc quản lý đĩa : Quản lý vùng trống trên đĩa. Định vị lƣu trữ. Lập lịch cho đĩa. Vì hệ thống đĩa đƣợc sử dụng thƣờng xuyên, nên nó phải đƣợc dùng hiệu quả.Tốc độ của toàn bộ hệ thống tuỳ thuộc rất nhiều vào tốc độ truy xuất đĩa. d. Quản lý hệ thống nhập xuất : Một trong những mục tiêu của hệ điều hành là che dấu những đặc thù của các thiết bị phần cứng đối với ngƣời sử dụng thay vào đó là một lớp thân thiện hơn, ngƣời sử dụng dể thao tác hơn. Một hệ thống nhập/xuất bao gồm : Hệ thống buffer caching. Giao tiếp điều khiển thiết bị (device drivers) tổng quát. Bộ điều khiển cho các thiết bị phần cứng. Chỉ có device driver mới hiểu đến cấu trúc đặc thù của thiết bị mà nó mô tả. e. Quản lý hệ thống tập tin : Hệ thống quản lý tập tin là thành phần rõ ràng nhất trong hệ điều hành. Máy tính có thể lƣu trữ thông tin trong nhiều dạng thiết bị vật lý khác nhau : băng từ, đĩa từ, , đĩa quang, Mỗi dạng có những đặc thù riêng về mặt tổ chức vật lý. Mỗi thiết bị có một bộ kiểm soát nhƣ bộ điều khiển đĩa (disk driver) và có những tính chất riêng. Những tính chất này là tốc độ, khả năng lƣu trữ, tốc độ truyền dữ liệu và cách truy xuất. Để cho việc sử dụng hệ thống máy tính thuận tiện, hệ điều hành cung cấp một cái nhìn logic đồng nhất về hệ thống lƣu trữ thông tin. Hệ điều hành định nghĩa một đơn vị lƣu trữ logic là tập tin. Hệ điều hành tạo một ánh xạ từ tập tin đến vùng thông tin trên đĩa và truy xuất những tập tin này thông qua thiết bị lƣu trữ. Một tập tin là một tập hợp những thông tin do ngƣời tạo ra nó xác định. Thông thƣờng một tập tin đại diện cho một chƣơng trình và dữ liệu. Dữ liệu của tập tin có thể là số, là ký tự, hay ký số. Tập tin thƣờng có dạng tự do, nhƣ tập tin văn bản, nhị phân (là tập tin chứa dãy các bit). (Xem bài VIII) Vai trò của hệ điều hành trong việc quản lý tập tin : Tạo và xoá một tập tin. Tạo và xoá một thƣ mục 18
20. Hỗ trợ các thao tác trên tập tin và thƣ mục. Ánh xạ tập tin trên hệ thống lƣu trữ phụ. Backup tập tin trên các thiết bị lƣu trữ. f. Hệ thống bảo vệ : Trong một hệ thống nhiều ngƣời sử dụng và cho phép nhiều tiến trình diễn ra đồng thời, các tiến trình phải đƣợc bảo vệ đối với những hoạt động khác.Do đó, hệ thống cung cấp cơ chế để đảm bảo rằng tập tin, bộ nhớ, CPU, và những tài nguyên khác chỉ đƣợc truy xuất bởi những tiến trình có quyền. Ví dụ, bộ nhớ đảm bảo rằng tiến trình chỉ đƣợc thi hành trong phạm vi địa chỉ của nó. Bộ thời gian đảm bảo rằng không có tiến trình nào độc chiếm CPU. Cuối cùng các thiết bị ngoại vi cũng đƣợc bảo vệ. Hệ thống bảo vệ là một cơ chế kiểm soát quá trình truy xuất của chƣơng trình, tiến trình, hoặc ngƣời sử dụng với tài nguyên của hệ thống. Cơ chế này cũng cung cấp cách thức để mô tả lại mức độ kiểm soát. Hệ thống bảo vệ cũng làm tăng độ an toàn khi kiểm tra lỗi trong giao tiếp giữa những hệ thống nhỏ bên trong. g. Hệ thống cơ chế dòng lệnh : Một trong những phần quan trọng của chƣơng trình hệ thống trong một hệ điều hành là cơ chế dòng lệnh, đó là giao tiếp giữa ngƣời sử dụng và hệ điều hành. Một số hệ điều hành đặt cơ chế dòng lệnh bên trong hạt nhân, số khác nhƣ MS-DOS và UNIX thì xem hệ điều hành nhƣ là một chƣơng trình đặt biệt, đƣợc thi hành khi các công việc bắt đầu hoặc khi ngƣời sử dụng login lần đầu tiên. Các lệnh đƣa vào hệ điều hành thông qua bộ điều khiển lệnh. Trong các hệ thống chia sẻ thời gian một chƣơng trình có thể đọc và thông dịch các lệnh điều khiển đƣợc thực hiện một cách tự động. Chƣơng trình này thƣờng đƣợc gọi là bộ thông dịch điều khiển card, cơ chế dòng lệnh hoặc Shell. Chức năng của nó rất đơn giản đó là lấy lệnh kế tiếp và thi hành. Mỗi hệ điều hành sẽ có những giao tiếp khác nhau, dạng đơn giản theo cơ chế dòng lệnh, dạng thân thiện với ngƣời sử dụng nhƣ giao diện của Macintosh có các biểu tƣợng, cửa sổ thao tác dùng chuột. Các lệnh có quan hệ với việc tạo và quản lý các tiến trình, kiểm soát nhập xuất, quản lý bộ lƣu trữ phụ, quản lý bộ nhớ chính, truy xuất hệ thống tập tin và cơ chế bảo vệ. 19
21. 1.4. Các dịch vụ của hệ điều hành Hệ điều hành cung cấp một môi trƣờng để thi hành các chƣơng trình, bằng cách cung cấp các dịch vụ cho chƣơng trình và cho ngƣời sử dụng. Các dịch vụ này trên mỗi hệ thống là khác nhau nhƣng cũng có những lớp chung. Các dịch vụ này giúp cho các lập trình viên thuận tiện hơn và việc lập trình dể dàng hơn. Thi hành chương trình: hệ thống phải có khả năng nạp chƣơng trình vào bộ nhớ và thi hành nó. Chƣơng trình phải chấm dứt thi hành theo cách thông thƣờng hay bất thƣờng (có lỗi). Thao tác nhập xuất : Một chƣơng trình thi hành có thể yêu cầu nhập xuất. Nhập xuất này có thể là tập tin hay thiết bị. Đối với thiết bị có một hàm đặc biệt đƣợc thi hành. Để tăng hiệu quả, ngƣời sử dụng không truy xuất trực tiếp các thiết bị nhập xuất mà thông qua cách thức do hệ điều hành cung cấp. Thao tác trên hệ thống tập tin . Thông tin : có nhiều tình huống một tiến trình cần trao đổi thông tin với một tiến trình khác. Có hai cách thực hiện: Một là thực hiện thay thế tiến trình trên cùng máy tính, hai là thay thế tiến trình trên hệ thống khác trong hệ thống mạng. Thông tin có thể đƣợc cài đặt qua chia sẻ bộ nhớ, hoặc bằng kỹ thuật chuyển thông điệp. Việc chuyển thông tin đƣợc thực hiện bởi hệ điều hành. Phát hiện lỗi: hệ điều hành phải có khả năng báo lỗi. Lỗi xảy ra có thể do CPU, bộ nhớ, trong thiết bị nhập xuất, hay trong các chƣơng trình. Đối với mỗi dạng lỗi, hệ điều hành sẽ có cách giải quyết tƣơng ứng. 1.5. Lời gọi hệ thống Lời gọi hệ thống cung cấp một giao tiếp giữa tiến trình và hệ điều hành. Lời gọi này cũng nhƣ các lệnh hợp ngữ. Một số hệ thống cho phép lời gọi hệ thống đƣợc thực hiện từ cấp lập trình ngôn ngữ cấp cao, nhƣ các hàm và lời gọi hàm. Nó có thể phát sinh lời gọi từ các thủ tục hay gọi trực tiếp trong dòng. Để hiểu quá trình hoạt động của lời gọi hệ thống chúng ta cùng khảo sát một chƣơng trình nhỏ dùng để đọc dữ liệu từ một tập tin chép qua tập tin khác. Dữ liệu nhập đầu tiên của của chƣơng trình là tên của hai tập tin : tập tin nhập và tập tin xuất. Tên này đƣợc mô tả bằng nhiều cách tùy thuộc vào thiết kế hệ điều hành nhƣ : chƣơng trình yêucầu ngƣời sử dụng cho biết tên của hai tập tin, họ cũng có thể cung cấp bằng cách lựa chọn với chuột. Khi có tên của hai tập tin, chƣơng trình mở tập tin nhập và tạo tập tin xuất. Mỗi thao tác này đƣợc thực hiện bởi những lời gọi hệ 20
22. thống khác. Cũng có những trƣờng hợp phát sinh lỗi : Khi chƣơng trình mở tập tin nhập, có thể xảy ra trƣờng hợp không có tập tin có tên nhƣ mô tả hoặc tập tin bị cấm truy cập. Trong trƣờng hợp này chƣơng trình phải xuất thông điệp lên màn hình. Nếu tập tin nhập tồn tại, phải tạo tập tin mới. Hệ thống phải kiểm tra tiếp xem đã có tập tin xuất tồn tại không và sẽ có những lời gọi hệ thống tƣơng ứng để giải quyết hoặc là hủy tiến trình, hai là xóa tập tin đã tồn tại và tạo tập tin mới. Sau khi đã thiết lập xong tập tin, hệ thống tiếp tục tạo vòng lặp đọc dữ liệu từ tập tin nhận và ghi lên tập tin xuất. Mỗi bƣớc đều có kiểm tra lỗi. Sau khi chép xong, chƣơng trình sẽ đóng hai tập tin lại (dùng một lời gọi hệ thống khác), xuất thông báo lên màn hình (dùng lời gọi hệ thống) cuối cùng chấm dứt chƣơng trình (lời gọi hệ thống cuối cùng). Trong các ngôn ngữ lập trình cấp cao, ngƣời sử dụng không cần quan tâm đến chi tiết mà chỉ cần thông qua các hàm hay các lệnh để thực hiện.Lời gọi hệ thống có thể diễn ra theo một cách khác. Kiểu và khối lƣợng thông tin tùy thuộc vào hệ thống và lúc gọi. Có ba phƣơng pháp đƣợc sử dụng để chuyển tham số cho hệ điều hành. Cách đơn giản nhất là chuyển tham số vào thanh ghi. Nếu có nhiều tham số, nó sẽ đƣợc lƣu trữ trong khối hoặc bảng trong bộ nhớ. Cách cuối cùng là dùng cơ chế stack. Lời gọi hệ thống có thể đƣợc chia thành các loại : kiểm soát tiến trình, thao tác tập tin, thao tác thiết bị, thông tin. 1.6. Cấu trúc hệ thống 1.6.1. Cấu trúc đơn giản Cấu trúc này trong một số hệ thống thƣơng mại và không có cấu trúc đƣợc định nghĩa tốt. Thông thƣờng hệ điều hành bắt đầu là một hệ thống nhỏ, đơn giản và có giới hạn. MS-DOS là một hệ điều hành có cấu trúc đơn giản, nó cung cấp những chức năng cần thiết nhất trong một không gian nhỏ nhất do sự giới hạn của phần cứng mà nó chạy trên đó và không chia thành những đơn thể rõ rệt. 21
23. Hình 1.1. Cấu trúc của MS-DOS Mặc dù MS-DOS có cấu trúc nhƣng giữa giao diện và chức năng không có sự phân chia rõ rệt. Các chƣơng trình ứng dụng có thể truy xuất trực tiếp các thủ tục nhập xuất cơ bản và ghi trực tiếp lên màn hình hay bộ điều khiển đĩa. Một hệ điều hành cũng có cấu trúc đơn giản là UNIX với những version đầu tiên. Cấu trúc của nó chỉ bao gồm hai phần : hạt nhân và các chƣơng trình hệ thống. Hạt nhân đƣợc chia thành một chuỗi giao tiếp và device driver(bộ điều khiển thiết bị, xem bài XI). 22
24. Những gì dƣới lời gọi hệ thống và trên phần cứng là hạt nhân. Hạt nhân cung cấp hệ thống tập tin, lập lịch CPU, quản trị bộ nhớ và những chức năng hệ điều hành khác thông qua lời gọi hệ thống. Tóm lại là toàn bộ chức năng của hệ thống đƣợc kết hợp trong một lớp. Những chƣơng trình hệ thống dùng những lời gọi hệ thống đƣợc hỗ trợ bởi hạt nhân để cung cấp những chức năng hữu ích nhƣ biên dịch và thao tác tập tin. Lời gọi hệ thống định nghĩa một giao tiếp lập trình cho UNIX, đó là tập hợp những chƣơng trình hệ thống thông thƣờng trong đó có định nghĩa giao tiếp với ngƣời sử dụng. 1.6.2. Cấu trúc theo lớp Những version mới của UNIX đƣợc thiết kế để sử dụng phần cứng phức tạp hơn, do đó hệ điều hành đƣợc chia thành nhiều phần nhỏ hơn. Bằng cách sử dụng kỹ thuật topdown, những chức năng và đặc tính của hệ thống đƣợc chia làm nhiều thành phần nhỏ. Che dấu thông tin, không cho chƣơng trình của ngƣời sử dụng có thể cài đặt những hàm truy xuất cấp thấp , thay vào đó là những lớp giao tiếp bên trong. Hệ điều hành đƣợc chia thành nhiều lớp. Lớp dƣới cùng là phần cứng, lớp trên cùng là giao tiếp với ngƣời sử dụng. Lớp hệ điều hành đƣợc cài đặt thành những đối tƣợng trừu tƣợng. Thông thƣờng một lớp của hệ điều hành bao gồm một số cấu trúc 23
25. dữ liệu và các hàm có thể đƣợc gọi bởi lớp ở trên và bản thân nó gọi những chức năng của lớp bên dƣới. Mỗi lớp cài đặt chỉ sử dụng những thao tác do lớp dƣới cung cấp. Một lớp cũng không cần biết hệ điều hành đƣợc cài đặt nhƣ thế nào, nó chỉ cần biết những thao tác này làm gì thôi. Cấu trúc lớp này lần đầu tiên đƣợc thiết kế và áp dụng cho hệ điều hành THE (Technische Hogeschool Eindhoven). Hệ thống này đƣợc chia thành sáu lớp nhƣ hình sau: Lớp dƣới cùng là phần cứng, lớp kế tiếp cài đặt lập lịch CPU, lớp tiếp theo cài đặt quản lý bộ nhớ. Bộ nhớ ở đây là bộ nhớ ảo. Lớp tiếp nữa chứa device driver cho các thao tácvới màn hình. Lớp kế là tổ chức buffer cho việc nhập xuất thiết bị. Cuối cùng là chƣơng trình của ngƣời sử dụng.Các ví dụ khác nhƣ cấu trúc lớp của hệ điều 24
26. hành VENUS và OS/2 Hình 1.6 Cấu trúc lớp của OS/2Máy ảo Thông thƣờng, một hệ thống máy tính bao gồm nhiều lớp. Phần cứng ở lớp thấp nhất. Hạt nhân ở lớp kế dùng các chỉ thị của phần cứng để tạo một tập hợp các lời gọi hệ thống. Các chƣơng trình hệ thống có thể sử dụng hoặc là các lời gọi hệ thống hoặc là các chỉ thị của phần cứng. Vì vậy nó xem phần cứng và lời gọi hệ thống nhƣ cùng lớp. Một số hệ thống có tổ chức sao cho các chƣơng trình ứng dụng có thể gọi dễ dàng các chƣơng trình hệ thống. Mặc dù chƣơng trình hệ thống ở lớp cao hơn các phần khác nhƣng chƣơng trình ứng dụng có thể xem mọi phần dƣới nó là một phần của máy. Lớp ứng dụng này sử dụng một khái niệm là máy ảo. Ví dụ hệ điều hành máy ảo của IBM. Bằng cách sử dụng lập lịch cho CPU và kỹ thuật bộ nhớ ảo, một hệ điều hành có thể tạo nhiều tiến trình phức ảo, mỗi cái sẽ thực hiện trên một bộ xử lý và bộ nhớ riêng. Những tiến trình này có những đặc điểm riêng nhƣ lời gọi hệ thống và hệ thống tập tin không đƣợc cung cấp phần cứng trực tiếp. Tài nguyên của hệ thống đƣợc chia sẻ để tạo những máy ảo. Lập lịch CPU chia sẻ CPU cho các ngƣời sử dụng. Spooling và hệ thống tập tin đƣợc chia thành những card đọc ảo và máy in ảo. Một terminal cung cấp các chức năng tạo các thao tác màn hình ảo. Vấn đề phức tạp nhất của máy ảo là hệ thống đĩa. Giả sử hệ thống chỉ có ba bộ điều khiển đĩa nhƣng có tới bảy máy ảo. Nhƣ vậy không thể gán cho mỗi máy ảo một bộ điều khiển đĩa và giải pháp là xây dựng hệ thống đĩa ảo. Mặc dù khái niệm máy ảo rất hữu ích nhƣng khó cài đặt. Máy ảo phải thực hiện ở hai dạng: dạng giám sát (monitor) và dạng ngƣời sử dụng. Ngoài ra máy ảo còn phải giải quyết các vấn đề về vận chuyển dữ liệu và thời gian. 25
27. 1.6.3. Mô hình Client-Server Khuynh hƣớng của các hệ điều hành hiện đại là chuyển dần các đoạn mã của hệ thống lên những lớp cao hơn và bỏ dần các chức năng trong hạt nhân, chỉ còn lại một hạt nhân tối thiểu. Cách tiếp cận là cài đặt hầu hết những chức năng của hệ điều hành trong các xử lý của ngƣời sử dụng. Để yêu cầu một dịch vụ, nhƣ đọc một khối từ tập tin, một xử lý của ngƣời sử dụng (còn đƣợc gọi là tiến trình client) sẽ gửi những yêu cầu đó cho một xử lý của bộ phận dịch vụ (còn đƣợc gọi là tiến trình server). Sau đó, nó sẽ thực hiện và gửi kết quả trở lại. Trong mô hình này, chức năng của hạt nhân chỉ là kiểm soát quá trình thông tin giữa client và server. Bằng cách chia hệ điều hành thành những phần nhỏ, mỗi phần chỉ kiểm soát một mặt của hệ thống nhƣ các dịch vụ về tập tin, tiến trình, terminal, bộ nhớ, mỗi phần sẽ gọn hơn và dể quản lý hơn. Hơn nữa, tất cả server thực hiện nhƣ những tiến trình ở mức độ ngƣời dùng (user-mode) không phải ở mức độ hạt nhân (kernel-mode), nên nó không truy xuất trực tiếp phần cứng. Do đó, nếu server tập tin bị lỗi, các dịch vụ về tập tin có thể bị hỏng nhƣng nó thƣờng không gây ảnh hƣởng đến toàn bộ hệ thống. 26
28. Một ƣu điểm khác của mô hình client-server là nó có thể tƣơng thích dể dàng với mô hình hệ thống phân tán. Nếu một client giao tiếp với một server bằng cách gửi những thông điệp, họ không biết là khi nào thông điệp đó đang đƣợc xử lý cục bộ tại máy hay đƣợc gửi vào mạng đến server trên một máy từ xa. Khi client quan tâm đến, một yêu cầu đƣợc gửi đi và một trả lời đáp ứng diễn ra nhƣ nhau. 27
29. 1.7. Lịch sử phát triển hệ điều hành 1.7.1. Thế hệ 1 (1945 – 1955) Vào khoảng giữa thập niên 1940, Howard Aiken ở Havard và John von Neumann ở Princeton, đã thành công trong việc xây dựng máy tính dùng ống chân không. Những máy này rất lớn với hơn 10000 ống chân không nhƣng chậm hơn nhiều so với máy rẻ nhất ngày nay. Mỗi máy đƣợc một nhóm thực hiện tất cả từ thiết kế, xây dựng lập trình, thao tác đến quản lý. Lập trình bằng ngôn ngữ máy tuyệt đối, thƣờng là bằng cách dùng bảng điều khiển để thực hiện các chức năng cơ bản. Ngôn ngữ lập trình chƣa đƣợc biết đến và hệ điều hành cũng chƣa nghe đến. Vào đầu thập niên 1950, phiếu đục lổ ra đời và có thể viết chƣơng trình trên phiếu thay cho dùng bảng điều khiển. 1.7.2. Thế hệ 2 (1955 – 1965) Sự ra đời của thiết bị bán dẫn vào giữa thập niên 1950 làm thay đổi bức tranh tổng thể. Máy tính trở nên đủ tin cậy hơn. Nó đƣợc sản xuất và cung cấp cho các khách hàng. Lần đầu tiên có sự phân chia rõ ràng giữa ngƣời thiết kế, ngƣời xây dựng, ngƣời vận hành, ngƣời lập trình, và ngƣời bảo trì. Để thực hiện một công việc (một chƣơng trình hay một tập hợp các chƣơng trình), lập trình viên trƣớc hết viết chƣơng trình trên giấy (bằng hợp ngữ hay FORTRAN) sau đó đục lỗ trên phiếu và cuối cùng đƣa phiếu vào máy. Sau khi thực hiện xong nó sẽ xuất kết quả ra máy in. Hệ thống xử lý theo lôra đời, nó lƣu các yêu cầu cần thực hiện lên băng từ, và hệ thống sẽ đọc và thi hành lần lƣợt. Sau đó, nó sẽ ghi kết quả lên băng từ xuất và cuối cùng ngƣời sử dụng sẽ đem băng từ xuất đi in. Hệ thống xử lý theo lô hoạt động dƣới sự điều khiển của một chƣơng trình đặc biệt là tiền thân của hệ điều hành sau này. Ngôn ngữ lập trình sử dụng trong giai đoạn này chủ yếu là FORTRAN và hợp ngữ. 28
30. 1.7.3. Thế hệ 3 (1965 – 1980) Trong giai đoạn này, máy tính đƣợc sử dụng rộng rãi trong khoa học cũng nhƣ trong thƣơng mại. Máy IBM 360 là máy tính đầu tiên sử dụng mạch tích hợp (IC). Từ đó kíchthƣớc và giá cả của các hệ thống máy giảm đáng kể và máy tính càng phỗ biến hơn. Các thiết bị ngoại vi dành cho máy xuất hiện ngày càng nhiều và thao tác điều khiển bắt đầu phức tạp. Hệ điều hành ra đời nhằm điều phối, kiểm soát hoạt động và giải quyết các yêu cầu tranh chấp thiế bị. Chƣơng trình hệ điều hành dài cả triệu dòng hợp ngữ và do hàng ngàn lập trình viên thực hiện. Sau đó, hệ điều hành ra đời khái niệm đa chương. CPU không phải chờ thực hiện các thao tác nhập xuất. Bộ nhớ đƣợc chia làm nhiều phần, mỗi phần có một công việc (job) khác nhau, khi một công việc chờ thực hiện nhập xuất CPU sẽ xử lý các công việc còn lại. Tuy nhiên khi có nhiều công việc cùng xuất hiện trong bộ nhớ, vấn đề là phải có một cơ chế bảo vệ tránh các công việc ảnh hƣởng đến nhau. Hệ điều hành cũng cài đặt thuộc tính spool. Giai đoạn này cũng đánh dấu sự ra đời của hệ điều hành chia sẻ thời gian nhƣ CTSS của MIT. Đồng thời các hệ điều hành lớn ra đời nhƣ MULTICS, UNIX và hệ thống các máy mini cũng xuất hiện nhƣ DEC PDP-1. 1.7.4. Thế hệ 4 (1980 - ) Giai đoạn này đánh dấu sự ra đời của máy tính cá nhân, đặc biệt là hệ thống IBM PC với hệ điều hành MS-DOS và Windows sau này. Bên cạnh đó là sự phát triển mạnh của các hệ điều hành tựa Unix trên nhiều hệ máy khác nhau nhƣ Linux. Ngoài ra, từ đầu thập niên 90 cũng đánh dấu sự phát triển mạnh mẽ của hệ điều hành mạng và hệ điều hành phân tán.Bài tập tự giải 1.7.5. Câu hỏi củng cố bài học 1. Hệ điều hành là gì? 2. Có mấy loại hệ điều hành ? Việc phân loại này dựa trên những tiêu chuẩn nào ? 3. Nêu các thành phần chính của hệ điều hành và chức năng của mỗi thành phần này. 4. So sánh các cấu trúc khác nhau của hệ điều hành. Ƣu khuyết điểm củ mỗi loại cấu trúc. 29
31. 5. Quá trình phát triển của hệ điều hành phụ thuộc vào những yếu tố nào. 1.7.6. Bài tập 1. Hệ điều hành là : a. Một chƣơng trình b. Một chƣơng trình hay hệ chƣơng trình c. Một thiết bị d. ROM-BIOS 2. Một hệ điều hành bao gồm : a. Hệ thống quản lý ttin, I/O b. Hệ thống quản lý ttrình, bộ nhớ c. a và b d. a, b, c đều sai 3. Hệ điều hành MS-DOS có cấu trúc : a. Đơn thể b. Hạt nhân c. Lớp d. Máy ảo 30
32. CHƢƠNG 2. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH Hầu hết các hệ điều hành hiện đại đều cho phép ngƣời dùng thi hành nhiều công việc đồng thời trên cùng một máy tính. Nhu cầu xử lý đồng hành (concurrency) này xuất phát từ đâu, và hệ điều hành cần phải tổ chức hỗ trợ nhƣ thế nào cho các môi trƣờng đa nhiệm (multitask) nhƣ thế ? Đó là nội dung chúng ta sẽ tìm hiểu trong bài này. 2.1. NHU CẦU XỬ LÝ ĐỒNG HÀNH Có 2 động lực chính khiến cho các hệ điều hành hiện đại thƣờng hỗ trợ môi trƣờng đa nhiệm (multitask) trong đó chấp nhận nhiều tác vụ thực hiện đồng thời trên cùng một máy tính : 2.1.1. Tăng hiệu suất sử dụng CPU Phần lớn các tác vụ (job) khi thi hành đều trải qua nhiều chu kỳ xử lý (sử dụng CPU) và chu kỳ nhập xuất (sử dụng các thiết bị nhập xuất) xen kẽ nhƣ sau : Nếu chỉ có 1 tiến trình duy nhất trong hệ thống, thì vào các chu kỳ IO của tác vụ, CPU sẽ hoàn toàn nhàn rỗi. Ý tƣởng tăng cƣờng số lƣợng tác vụ trong hệ thống là để tận dụng CPU : nếu tác vụ 1 xử lý IO, thì có thể sử dụng CPU để thực hiện tác vụ 2 a. Tác vụ 1 Tác vụ 31
33. 2.1.2. Tăng tốc độ xử lý Một số bài toán có bản chất xử lý song song nếu đƣợc xây dựng thành nhiều module hoạt động đồng thời thì sẽ tiết kiệm đƣợc thời gian xử lý. Ví dụ : Xét bài toán tính giá trị biểu thức kq = a*b + c*d . Nếu tiến hành tính đồng thời (a*b) và (c*d) thì thời gian xử lý sẽ ngắn hơn là thực hiện tuần tự.Trong các trƣờng hợp đó, cần có một mô hình xử lý đồng hành thích hợp. Trên máy tính có cấu hình nhiều CPU, hỗ trợ xử lý song song (multiprocessing) thật sự, điều này sẽ giúp tăng hiệu quả thi hành của hệt thống đáng kể.Khái niệm tiến trình(Process) và mô hình đa tiến trình(multiprocess) Để hỗ trợ sự đa chƣơng, máy tính phải có khả năng thực hiện nhiều tác vụ đồng thời. Nhƣng việc điều khiển nhiều hoạt động song song ở cấp độ phần cứng là rất khó khăn. Vì thế các nhà thiết kế hệ điều hành đề xuất một mô hình song song gỉa lặp bằng cách chuyển đổi bộ xử lý qua lại giữa các chƣơng trình để duy trì hoạt động của nhiều chƣơng trình cùng lúc, điều này tạo cảm giác có nhiều hoạt động đƣợc thực hiện đồng thời. Trong mô hình này, tất cả các phần mềm trong hệ thống đƣợc tổ chức thành một số những tiến trình (process). Tiến trình là một chƣơng trình đang xử lý, sỡ hữu một con trỏ lệnh, tập các thanh ghi và các biến. Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên – nhƣ CPU, bộ nhớ chính, các tập tin và thiết bị nhập/ xuất. Cần phân biệt hai khái niệm chương trình và tiến trình. Một chƣơng trình là một thực thể thụ động, chứa đựng các chỉ thị điều khiển máy tính để tiến hành một tác vụ nào đó ; khi cho thực hiện các chỉ thị này, chƣơng trình chuyển thành tiến trình, là một thực thể hoạt động, với con trỏ lệnh xác định chỉ thị kế tiếp sẽ thi hành, kèm theo tập các tài nguyên phục vụ cho hoạt động của tiến trình. Về mặt ý niệm, có thể xem nhƣ mỗi tiến trình sỡ hữu một bộ xử lý ảo cho riêng nó, nhƣng trong thực tế, chỉ có một bộ xử lý thật sự đƣợc chuyển đổi qua lại giữa các tiến trình. Sự chuyển đổi nhanh chóng này đƣợc gọi là sự đa chương(multiprogramming) . Hệ điều hành chịu trách nhiệm sử dụng một thuật toán điều phối để quyết định thời điểm cần dừng hoạt động của tiến trình đang xử lý để phục vụ một tiến trình khác, và lựa chọn tiến trình tiếp theo sẽ đƣợc phục vụ. Bộ phận thực hiện chức năng này của hệ điều hành đƣợc gọi là bộ điều phối 32
34. (scheduler). 2.2. Khái niệm tiến trình(thread) và mô hình đa tiến trình(multithread) Trong hầu hết các hệ điều hành, mỗi tiến trình có một không gian địa chỉ và chỉ có một dòng xử lý. Tuy nhiên, có nhiều tình huống ngƣời sử dụng mong muốn có nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ, và các dòng xử lý này hoạt động song song tƣơng tự nhƣ các tiến trình phân biệt (ngoại trừ việc chia sẻ không gian địa chỉ). Ví dụ : Một server quản lý tập tin thỉnh thoảng phải tự khóa để chờ các thao tác truy xuất đĩa hoàn tất.Nếu server có nhiều dòng xử lý, hệ thống có thể xử lý các yêu cầu mới trong khi một dòng xử lý bị khoá. Nhƣ vậy việc thực hiện chƣơng trình sẽ có hiệu quả hơn. Điều này không thể đạt đƣợc bằng cách tạo hai tiến trình server riêng biệt vì cần phải chia sẻ cùng một vùng đệm, do vậy bắt buộc phải chia sẻ không gian địa chỉ. Chính vì các tình huống tƣơng tự, ngƣời ta cần có một cơ chế xử lý mới cho phép có nhiều dòng xử lý trong cùng một tiến trình. Ngày nay đã có nhiều hệ điều hành cung cấp một cơ chế nhƣ thế và gọi là tiểu trình(threads). 2.2.1. Nguyên lý chung : Một tiểu trình là một đơn vị xử lý cơ bản trong hệ thống . Mỗi tiểu trình xử lý tuần tự đoạn code của nó, sỡ hữu một con trỏ lệnh, tập các thanh ghi và một vùng nhớ stack riêng. Các tiểu trình chia sẻ CPU với nhau giống nhƣ cách chia sẻ giữa các tiến trình: một tiểu trình xử lý trong khi các tiểu trình khác chờ đến lƣợtù. Một tiểu 33
35. trình cũng có thể tạo lập các tiến trình con, và nhận các trạng thái khác nhau nhƣ một tiến trình thật sự. Một tiến trình có thể sỡ hữu nhiều tiểu trình. Các tiến trình tạo thành những thực thể độc lập. Mỗi tiến trình có một tập tài nguyên và một môi trƣờng riêng (một con trỏ lệnh, một Stack , các thanh ghi và không gian địa chỉ ). Các tiến trình hoàn toàn độc lập với nhau, chỉ có thể liên lạc thông qua các cơ chế thông tin giữa các tiến trình mà hệ điều hành cung cấp. Ngƣợc lại, các tiểu trình trong cùng một tiến trình lại chia sẻ một không gian địa chỉ chung , điều này có nghĩa là các tiểu trình có thể chia sẻ các biến toàn cục của tiến trình. Một tiểu trình có thể truy xuất đến cả các stack của những tiểu trình khác trong cùng tiến trình. Cấu trúc này không đề nghị một cơ chế bảo vệ nào, và điều này cũng không thật cần thiết vì các tiểu trình trong cùng một tiến trình thuộc về cùng một sỡ hữu chủ đã tạo ra chúng trong ý định cho phép chúng hợp tác với nhau. Các tiểu trình trong cùng một tiểu trình Phân bổ thông tin lƣu trữ Cấu trúc mô tả tiến trình và tiểu trình 2.2.2. Kernel thread và user thread Khái niệm tiểu trình có thể đƣợc cài đặt trong kernel của Hệ điều hành, khi đó đơn vị cơ sở sử dụng CPU để xử lý là tiểu trình, Hệ điều hành sẽ phân phối CPU cho các 34
36. tiểu trình trong hệ thống. Tuy nhiên đối với một số hệ điều hành, khái niệm tiểu trình chỉ đƣợc hỗ trợ nhƣ một đối tƣợng ngƣời dùng, các thao tác tiểu trình đƣợc cung cấp kèm theo do một bộ thƣ viện xử lý trong chế độ ngƣời dùng không đặc quyền (user mode). Lúc này Hệ điều hành sẽ chỉ biết đến khái niệm tiến trình, do vây cận co cơ chế để liên kết các tiểu trình cùng một tiến trình với tiến trình cha trong kernel_ đối tƣợng này đôi lúc đƣợc gọi là LWP (lightweight process). 2.3. Tóm tắt và bài tập Tiến trình là một chƣơng trình đang hoạt động. Để sử dụng hiệu quả CPU, sự đa chƣơng cần đƣợc đƣa vào hệ thống Sự đa chƣơng đƣợc tổ chức bằng cách lƣu trữ nhiều tiến trình trong bộ nhớ tại một thời điểm, và điều phối CPU qua lại giữa các tiến trình trong hệ thống. 35
37. Mô hình đa tiểu trình cho phép mỗi tiến trình có thể tiến hành nhiều dòng xử lý đồng thời trong cùng một không gian địa chỉ nhằm thực hiện tác vụ hiệu qủa hơn trong một số trƣờng hợp. 2.3.1. Củng cố bài học Các câu hỏi cần trả lời đƣợc sau bài học này : 1. Tại sao các hệ điều hành hiện đại hỗ trợ môi trƣờng đa nhiệm ? 2. Phân biệt multitask, multiprogramming và multiprocessing. 3. Khái niệm tiến trình đƣợc xây dựng nhằm mục đích gì ? 4. Sự khác biệt, mối quan hệ giữa tiến trình và tiểu trình ? 2.3.2. Bài tập Bài 1. Nhiều hệ điều hành không cho phép xử lý đồng hành. Thảo luận về các phức tạp phát sinh khi hệ điều hành cho phép đa nhiệm ? Tìm một số ứng dụng thích hợp với mô hình đa tiến trình; và một số ứng dụng thích hợp với mô hình đa tiểu trình. 36
38. CHƢƠNG 3. QUẢN LÝ TIẾN TRÌNH Trong bài này chúng ta sẽ tìm hiểu chức năng quản lý tiến trình của Hệ điều hành: làm thế nào để phân chia CPU cho các tiến trình ? Theo vết xử lý của tiến trình ? Và các thao tác trên tiến trình ? 3.1. Tổ chức quản lý tiến trình 3.1.1. Các trạng thái của tiến trình Trạng thái của tiến trình tại một thời điểm đƣợc xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó. Trong quá trình sống, một tiến trình thay đổi trạng thái do nhiều nguyên nhân nhƣ : phải chờ một sự kiện nào đó xảy ra, hay đợi một thao tác nhập/ xuất hoàn tất, buộc phải dừng hoạt động do đã hết thời gian xử lý Tại một thời điểm, một tiến trình có thể nhận trong một các trạng thái sau đây : Mới tạo : tiến trình đang đƣợc tạo lập. Running : các chỉ thị của tiến trình đang đƣợc xử lý. Blocked : tiến trình chờ đƣợc cấp phát một tài nguyên, hay chờ mộtsự kiện xảy ra . Ready : tiến trình chờ đƣợc cấp phát CPU để xử lý. Kết thúc : tiến trình hoàn tất xử lý. Hình 2.2 Sơ đồ chuyển trạng thái giữa các tiến trình Tại một thời điểm, chỉ có một tiến trình có thể nhận trạng thái running trên một bộ xử lý bất kỳ. Trong khi đó, nhiều tiến trình có thể ở trạng thái blocked hay 37
39. ready.Các cung chuyển tiếp trong sơ đồ trạng thái biễu diễn sáu sự chuyển trạng thái có thể xảy ra trong các điều kiện sau : 3.1.2. Tiến trình mới tạo được đưa vào hệ thống 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 Tiến trình kết thúc Tiến trình yêu cầu một tài nguyên nhƣng chƣa đƣợc đáp ứng vì tài nguyên chƣa sẵn sàng để cấp phát tại thời điểm đó ; hoặc tiến trình phải chờ một sự kiện hay thao tác nhập/ xuất. Bộ điều phối chọn một tiến trình khác để cho xử lý . Tài nguyên mà tiến trình yêu cầu trở nên sẵn sàng để cấp phát ; hay sự kiện hoặc thao tác nhập/xuất tiến trình đang đợi hoàn tất. 3.2. Chế độ xử lý của tiến trình Để đảm bảo hệ thống hoạt động đúng đắn, hệ điều hành cần phải đƣợc bảo vệ khỏi sự xâm phạm của các tiến trình. Bản thân các tiến trình và dữ liệu cũng cần đƣợc bảo vệ để tránh các ảnh hƣởng sai lạc lẫn nhau. Một cách tiếp cận để giải quyết vấn đề là phân biệt hai chế độ xử lý cho các tiến trình : chế độ không đặc quyền và chế độ đặc quyền nhờ vào sự trợ giúp của cơ chế phần cứng. Tập lệnh của CPU đƣợc phân chia thành các lệnh đặc quyền và lệnh không đặc quyền. Cơ chế phần cứng chỉ cho phép các lệnh đặc quyền đƣợc thực hiện trong chế độ đặc quyền. Thông thƣờng chỉ có hệ điều hành hoạt động trong chế độ đặc quyền, các tiến trình của ngƣời dùng hoạt động trong chế độ không đặc quyền, không thực hiện đƣợc các lệnh đặc quyền có nguy cơ ảnh hƣởng đến hệ thống. Nhƣ vậy hệ điều hành đƣợc bảo vệ. Khi một tiến trình ngƣời dùng gọi đến một lời gọi hệ thống, tiến trình của hệ điều hành xử lý lời gọi này sẽ hoạt động trong chế độ đặc quyền, sau khi hoàn tất thì trả quyền điều khiển về cho tiến trình ngƣời dùng trong chế độ không đặc quyền. 38
40. Hình vẽ 2.3 Hai chế độ xử lýCấu trúc dữ liệu khối quản lý tiến trình Hệ điều hành quản lý các tiến trình trong hệ thống thông qua khối quản lý tiến trình (process control block -PCB). PCB là một vùng nhớ lƣu trữ các thông tin mô tả cho tiến trình, với các thành phần chủ yếu bao gồm : Định danh của tiến trình (1) : giúp phân biệt các tiến trình Trạng thái tiến trình (2): xác định hoạt động hiện hành của tiến trình. Ngữ cảnh của tiến trình (3): mô tả các tài nguyên tiến trình đang trong quá trình, hoặc để phục vụ cho hoạt động hiện tại, hoặc để làm cơ sở phục hồi hoạt động cho tiến trình, bao gồm các thông tin về: Trạng thái CPU: bao gồm nội dung các thanh ghi, quan trọng nhất là con trỏ lệnh IP lƣu trữ địa chỉ câu lệnh kế tiếp tiến trình sẽ xử lý. Các thông tin này cần đƣợc lƣu trữ khi xảy ra một ngắt, nhằm có thể cho phép phục hồi hoạt động của tiến trình đúng nhƣ trƣớc khi bị ngắt. Bộ xử lý: dùng cho máy có cấu hình nhiều CPU, xác định số hiệu CPU mà tiến trình đang sử dụng. Bộ nhớ chính: danh sách các khối nhớ đƣợc cấp cho tiến trình. Tài nguyên sử dụng: danh sách các tài mguyên hệ thống mà tiến trình đang sử dụng. Tài nguyên tạo lập: danh sách các tài nguyên đƣợc tiến trình tạo lập. Thông tin giao tiếp (4): phản ánh các thông tin về quan hệ của tiến trình với các tiến trình khác trong hệ thống : 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 lập . Độ ưu tiên : giúp bộ điều phối có thông tin để lựa chọn tiến trình đƣợc cấp CPU. Thông tin thống kê (5): đây là những thông tin thống kê về hoạt động của tiến trình, nhƣ thời gian đã sử dụng CPU,thời gian chờ. Các thông tin này có thể có ích 39
41. cho công việc đánh giá tình hình hệ thống và dự đoán các tình huống tƣơng lai. Hình vẽ 2.4 Khối mô tả tiến trình 3.2.1. Thao tác trên tiến trình Hệ điều hành cung cấp các thao tác chủ yếu sau đây trên một tiến trình : Tạo lập tiến trình (create) Kết thúc tiến trình (destroy) tạm dừng tiến trình (suspend) tái kích hoạt tiến trình (resume) thay đổi độ ƣu tiên tiến trình a. Tạo lập tiến trình 40
42. Trong quá trình xử lý, một tiến trình có thể tạo lập nhiều tiến trình mới bằng cách sử dụng một lời gọi hệ thống tƣơng ứng. Tiến trình gọi lời gọi hệ thống để tạo tiến trình mới sẽ đƣợc gọi là tiến trình cha, tiến trình đƣợc tạo gọi là tiến trình con. Mỗi tiến trình con đến lƣợt nó lại có thể tạo các tiến trình mới quá trình này tiếp tục sẽ tạo ra một cây tiến trình. Hình vẽ 2.5 Một cây tiến trình trong hệ thống UNIX Các công việc hệ điều hành cần thực hiện khi tạo lập tiến trình bao gồm : định danh cho tiến trình mới phát sinh đƣa tiến trình vào danh sách quản lý của hệ thống xác định độ ƣu tiên cho tiến trình tạo PCB cho tiến trình cấp phát các tài nguyên ban đầu cho tiến trình Khi một tiến trình tạo lập một tiến trình con, tiến trình con có thể sẽ đƣợc hệ điều hành trực tiếp cấp phát tài nguyên hoặc đƣợc tiến trình cha cho thừa hƣởng một số tài nguyên ban đầu. Khi một tiến trình tạo tiến trình mới, tiến trình ban đầu có thể xử lý theo một trong hai khả năng sau : Tiến trình cha tiếp tục xử lý đồng hành với tiến trình con. 41
43. Tiến trình cha chờ đến khi một tiến trình con nào đó, hoặc tất cả các tiến trình con kết thúc xử lý. Các hệ điều hành khác nhau có thể chọn lựa các cài đặt khác nhau để thực hiện thao tác tạo lập một tiến trình. b. Kết thúc tiến trình Một tiến trình kết thúc xử lý khi nó hoàn tất chỉ thị cuối cùng và sử dụng một lời gọi hệ thống để yêu cầu hệ điều hành hủy bỏ nó. Đôi khi một tiến trình có thể yêu cầu hệ điều hành kết thúc xử lý của một tiến trình khác. Khi một tiến trình kết thúc, hệ điều hành thực hiện các công việc : thu hồi các tài nguyên hệ thống đã cấp phát cho tiến trình hủy tiến trình khỏi tất cả các danh sách quản lý của hệ thống hủy bỏ PCB của tiến trình Hầu hết các hệ điều hành không cho phép các tiến trình con tiếp tục tồn tại nếu tiến trình cha đã kết thúc. Trong những hệ thống nhƣ thế, hệ điều hành sẽ tự động phát sinh một loạt các thao tác kết thúc tiến trình con. 3.2.2. Cấp phát tài nguyên cho tiến trình Khi có nhiều ngƣời sử dụng đồng thời làm việc trong hệ thống, hệ điều hành cần phải cấp phát các tài nguyên theo yêu cầu cho mỗi ngƣời sử dụng. Do tài nguyên hệ thống thƣờng rất giới hạn và có khi không thể chia sẻ, nên hiếm khi tất cả các yêu cầu tài nguyên đồng thời đều đƣợc thỏa mãn. Vì thế cần phải nghiên cứu một phƣơng pháp để chia sẻ một số tài nguyên hữu hạn giữa nhiều tiến trình ngƣời dùng đồng thời. Hệ điều hành quản lý nhiều loại tài nguyên khác nhau (CPU, bộ nhớ chính, các thiết bị ngoại vi ), với mỗi loại cần có một cơ chế cấp phát và các chiến lƣợc cấp phát hiệu qủa. Mỗi tài nguyên đƣợc biễu diễn thông qua một cấu trúc dữ liệu, khác nhau về chi tiết cho từng loại tài nguyên, nhƣng cơ bản chứa đựng các thông tin sau : 3.2.3. Định danh tài nguyên Trạng thái tài nguyên : đây là các thông tin mô tả chi tiết trạng thái tài nguyên : phần nào của tài nguyên đã cấp phát cho tiến trình, phần nào còn có thể sử dụng ? Hàng đợi trên một tài nguyên : danh sách các tiến trình đang chờ đƣợc cấp phát tài nguyên tƣơng ứng. 42
44. Bộ cấp phát : là đoạn code đảm nhiệm việc cấp phát một tài nguyên đặc thù. Một số tài nguyên đòi hỏi các giải thuật đặc biệt (nhƣ CPU, bộ nhớ chính, hệ thống tập tin), trong khi những tài nguyên khác (nhƣ các thiết bị nhập/xuất) có thể cần các giải thuật cấp phát và giải phóng tổng quát hơn. Hình 2.6 Khối quản lý tài nguyên 3.2.4. Các mục tiêu của kỹ thuật cấp phát : Bảo đảm một số lƣợng hợp lệ các tiến trình truy xuất đồng thời đến các tài nguyên không chia sẻ đƣợc.Cấp phát tài nguyên cho tiến trình có yêu cầu trong một khoảng thời gian trì hoãn có thể chấp nhận đƣợc. Tối ƣu hóa sự sử dụng tài nguyên. Để có thể thõa mãn các mục tiêu kể trên, cần phải giải quyết các vấn đề nảy sinh khi có nhiều tiến trình đồng thời yêu cầu một tài nguyên không thể chia sẻ. CHƢƠNG 4. ĐIỀU PHỐI TIẾN TRÌNH Trong môi trƣờng đa chƣơng, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thƣờng xuyên để nhiều ngƣời sử dụng có thể tƣơng tác cùng lúc với từng chƣơng trình trong quá trình xử lý. Để thực hiện đƣợc mục tiêu này, hệ điều hành phải lựa chọn tiến trình đƣợc xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác 43
45. điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình đƣợc chọn bởi bộ điều phối để xử lý. 4.1. Giới thiệu 4.1.1. Mục tiêu điều phối Bộ điều phối không cung cấp cơ chế, mà đƣa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lƣợc khác nhau để thực hiện việc điều phối, nhƣng tựu chung cần đạt đƣợc các mục tiêu sau : Sự công bằng ( Fairness) : Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để đƣợc cấp phát CPU Tính hiệu qủa (Efficiency) : Hệ thống phải tận dụng đƣợc CPU 100% thời gian. Thời gian đáp ứng hợp lý (Response time) : Cực tiểu hoá thời gian hồi đáp cho các tƣơng tác của ngƣời sử dụng Thời gian lƣu lại trong hệ thống ( Turnaround Time) : Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô. Thông lƣợng tối đa (Throughput ) : Cực đại hóa số công việc đƣợc xử lý trong một đơn vị thời gian.Tuy nhiên thƣờng không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó. 4.1.2. Các đặc điểm của tiến trình Điều phối hoạt động của các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ điều hành khi giải quyết phải xem xét nhiều yếu tố khác nhau để có thể đạt đƣợc những mục tiêu đề ra. Một số đặc tính của tiến trình cần đƣợc quan tâm nhƣ tiêu chuẩn điều phối : 44
46. a. Tính hƣớng xuất / nhập của tiến trình ( I/O-boundedness): Khi một tiến trình nhận đƣợc CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình nhƣ thế thƣờng bao gồm nhiều lƣợt sử dụng CPU , mỗi lƣợt trong một thời gian khá ngắn. b. Tính hƣớng xử lý của tiến trình ( CPU-boundedness): Khi một tiến trình nhận đƣợc CPU, nó có khuynh hƣớng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình nhƣ thế thƣờng bao gồm một số ít lƣợt sử dụng CPU , nhƣng mỗi lƣợt trong một thời gian đủ dài. c. Tiến trình tƣơng tác hay xử lý theo lô : Ngƣời sử dụng theo kiểu tƣơng tác thƣờng yêu cầu đƣợc hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ đƣợc xử lý theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận đƣợc. d. Độ ƣu tiên của tiến trình : Các tiến trình có thể đƣợc phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ ƣu tiên cao hơn) cần đƣợc ƣu tiên hơn. e. Thời gian đã sử dụng CPU của tiến trình : Một số quan điểm ƣu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận đƣợc CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ƣu tiên chọn chúng. f. Thời gian còn lại tiến trình cần để hoàn tất : Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng cách cho các tiến trình cần ít thời gian nhất để hoàn tất đƣợc thực hiện trƣớc. Tuy nhiên đáng tiếc là rất hiếm khi biết đƣợc tiến trình cần bao nhiêu thời gian nữa để kết thúc xử lý. 45
47. 4.2. Điều phối không độc quyền và điều phối độc quyền (preemptive/nopreemptive) Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi CPU giữa các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo nguyên lý độc quyền hoặc không độc quyền. Điều phối độc quyền : Nguyên lý điều phối độc quyền cho phép một tiến trình khi nhận đƣợc CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định điều phối CPU sẽ xảy ra trong các tình huống sau: Khi tiến trình chuyển từ trạng thái đang xử lý(running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc ). Khi tiến trình kết thúc. Các giải thuật độc quyền thƣờng đơn giản và dễ cài đặt. Tuy nhiên chúng thƣờng không thích hợp với các hệ thống tổng quát nhiều ngƣời dùng, vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến trình này có thể giữ CPU một thời gian không xác định, có thể ngăn cản những tiến trình còn lại trong hệ thống có một cơ hội để xử lý. Điều phối không độc quyền : Ngƣợc với nguyên lý độc quyền, điều phối theo nguyên lý không độc quyền cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận đƣợc CPU, nó vẫn đƣợc sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhƣng một tiến trình khác có độ ƣu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Nhƣ vậy là 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ý. Các quyết định điều phối xảy ra khi : Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc ). Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái ready ( ví dụ xảy ra một ngắt). Khi tiến trình chuyển từ trạng thái chờ (blocked) sang trạng thái ready ( ví dụ một thao tác nhập/xuất hoàn tất). Khi tiến trình kết thúc. 46
48. Các thuật toán điều phối theo nguyên tắc không độc quyền ngăn cản đƣợc tình trạng một tiến trình độc chiếm CPU, nhƣng việc tạm dừng một tiến trình có thể dẫn đến các mâu thuẫn trong truy xuất, đòi hỏi phải sử dụng một phƣơng pháp đồng bộ hóa thích hợp để giải quyết.Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có thể xảy ra tình trạng các tác vụ cần thời gian xử lý ngắn phải chờ tác vụ xử lý với thời gian rất dài hoàn tất! Nguyên lý điều phối độc quyền thƣờng chỉ thích hợp với các hệ xử lý theo lô. Đối với các hệ thống tƣơng tác(time sharing), các hệ thời gian thực (real time),cần phải sử dụng nguyên lý điều phối không độc quyền để các tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện điều phối theo nguyên lý không độc quyền đòi hỏi những cơ chế phức tạp trong việc phân định độ ƣu tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình. 4.3. Tổ chức điều phối 4.3.1. Các danh sách sử dụng trong quá trình điều phối. Hệ điều hành sử dụng hai loại danh sách để thực hiện điều phối các tiến trình là danh sách sẵn sàng (ready list) và danh sách chờ đợi(waiting list). Khi một tiến trình bắt đầu đi vào hệ thống, nó đƣợc chèn vào danh sách các tác vụ (job list). Danh sách này bao gồm tất cả các tiến trình của hệ thống. Nhƣng chỉ các tiến trình đang thƣờng trú trong bộ nhớ chính và ở trạng thái sẵn sàng tiếp nhận CPU để hoạt động mới đƣợc đƣa vào danh sách sẵn sàng. Bộ điều phối sẽ chọn một tiến trình trong danh sách sẵn sàng và cấp CPU cho tiến trình đó. Tiến trình đƣợc cấp CPU sẽ thực hiện xử lý, và có thể chuyển sang trạng thái chờ khi xảy ra các sự kiện nhƣ đợi một thao tác nhập/xuất hoàn tất, yêu cầu tài nguyên chƣa đƣợc thỏa mãn, đƣợc yêu cầu tạm dừng Khi đó tiến trình sẽ đƣợc chuyển sang một danh sách chờ đợi. Hệ điều hành chỉ sử dụng một danh sách sẵn sàng cho toàn hệ thống, nhƣng mỗi một tài nguyên ( thiết bị ngoại vi ) có một danh sách chờ đợi riêng bao gồm các tiến trình đang chờ đƣợc cấp phát tài nguyên đó. 47
49. Hình 2.9 Các danh sách điều phối Quá trình xử lý của một tiến trình trải qua những chu kỳ chuyển đổi qua lại giữa danh sách sẵn sàng và danh sách chờ đợi. Sơ đồ dƣới đây mô tả sự điều phối các tiến trình dựa trên các danh sách của hệ thống. Thoạt đầu tiến trình mới đƣợc đặt trong danh sách các tiến trình sẵn sàng (ready list), nó sẽ đợi trong danh sách này cho đến khi đƣợc chọn để cấp phát CPU và bắt đầu xử lý. Sau đó có thể xảy ra một trong các tình huống sau : Tiến trình phát sinh một yêu cầu một tài nguyên mà hệ thống chƣa thể đáp ứng, khi đó tiến trình sẽ đƣợc chuyển sang danh sách các tiến trình đang chờ tài nguyên tƣơng ứng. Tiến trình có thể bị bắt buộc tạm dừng xử lý do một ngắt xảy ra, khi đó tiến trình đƣợc đƣa trở lại vào danh sách sẵn sàng để chờ đƣợc cấp CPU cho lƣợt tiếp theo. 48
50. Hình 2.10 Sơ đồ chuyển đổi giữa các danh sách điều phối Trong trƣờng hợp đầu tiên, tiến trình cuối cùng sẽ chuyển từ trạng thái blocked sang trạng thái ready và lại đƣợc đƣa trở vào danh sách sẵn sàng. Tiến trình lặp lại chu kỳ này cho đến khi hoàn tất tác vụ thì đƣợc hệ thống hủy bỏ khỏi mọi danh sách điều phối. 4.3.2. Các cấp độ điều phối Thực ra công việc điều phối đƣợc hệ điều hành thực hiện ở hai mức độ : điều phối tác vụ (job scheduling) và điều phối tiến trình ( process scheduling). a. Điều phối tác vụ Quyết định lựa chọn tác vụ nào đƣợc đƣa vào hệ thống, và nạp những tiến trình của tác vụ đó vào bộ nhớ chính để thực hiện. Chức năng điều phối tác vụ quyết định mức độ đa chƣơng của hệ thống ( số lƣợng tiến trình trong bộ nhớ chính). Khi hệ thống tạo lập mộttiến trình, hay có một tiến trình kết thúc xử lý thì chức năng điều phối tác vụ mới đƣợc kích hoạt. Vì mức độ đa chƣơng tƣơng đối ổn định nên chức năng điều phối tác vụ có tần suất hoạt động thấp . Để hệ thống hoạt động tốt, bộ điều phối tác vụ cần biệt tính chất của tiến trình là hướng nhập xuất (I/O bounded) hay hướng xử lý ( CPU bounded). Một tiến trình đƣợc gọi là hướng nhập xuất nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác nhập xuất. Ngƣợc lại một tiến trình đƣợc gọi là hướng xử lý nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác tính toán. Để cân bằng hoạt động của CPU và các thiết bị ngoại vi, bộ điều phối tác vụ nên lựa chọn các tiến trình để nạp vào bộ nhớ sao cho hệ thống là sự pha trộn hợp lý giữa các tiến trình hướng nhập xuất và các tiến trình hướng xử lý b. Điều phối tiến trình Chọn một tiến trình ở trạng thái sẵn sàng ( đã đƣợc nạp vào bộ nhớ chính, và có đủ tài nguyên để hoạt động ) và cấp phát CPU cho tiến trình đó thực hiện. Bộ điều phối tiến trình có tần suất hoạt động cao, sau mỗi lần xảy ra ngắt ( do đồng hồ báo giờ, do các thiết bị ngoại vi ), thƣờng là 1 lần trong khoảng 100ms. Do vậy để nâng cao hiệu suất của hệ thống, cần phải tăng tốc độ xử lý của bộ điều phối tiến trình. Chức 49
51. năng điều phối tiến trình là một trong chức năng cơ bản, quan trọng nhất của hệ điều hành. Trong nhiều hệ điều hành, có thể không có bộ điều phối tác vụ hoặc tách biệt rất ít đối với bộ điều phối tiến trình. Một vài hệ điều hành lại đƣa ra một cấp độ điều phối trung gian kết hợp cả hai cấp độ điều phối tác vụ và tiến trình Hình 2.11 Cấp độ điều phối trung gianCác chiến lƣợc điều phối 4.3.3. Chiến lược FIFO Nguyên tắc : CPU đƣợc cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình đƣợc đƣa vào hệ thống sớm nhất. Đây là thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU đƣợc cấp phát cho tiến trình, CPU chỉ đƣợc tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập/xuất. Hình 2.12 Điều phối FIFO Ví dụ : 50
52. Thứ tự cấp phát CPU cho các tiến trình là : thời gian chờ đợi đƣợc xử lý là 0 đối với P1, (24 -1) với P2 và (24+3-2) với P3. Thời gian chờ trung bình là ( 0+23+25)/3 = 16 milisecondes. Thảo luận : Thời gian chờ trung bình không đạt cực tiểu, và biến đổi đáng kể đối với các giá trị về thời gian yêu cầu xử lý và thứ tự khác nhau của các tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện tƣợng tích lũy thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) phải chờ đợi một tiến trình có yêu cầu thời gian dài kết thúc xử lý.Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, trong các hệ này, cần cho phép mỗi tiến trình đƣợc cấp phát CPU đều đặn trong từng khoảng thời gian. 4.3.4. Chiến lược phân phối xoay vòng (Round Robin) Nguyên tắc : Danh sách sẵn sàng đƣợc xử lý nhƣ một danh sách vòng, bộ điều phối lần lƣợt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trƣớc khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chƣa hoàn tất, tiến trình đƣợc đƣa trở lại vào cuối danh sách sẵn sàng để đợi đƣợc cấp CPU trong lƣợt kế tiếp. Ví dụ : 51
53. Hình 2.13 Điều phối Round Robin Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là : Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes.Nếu có n tiến trìh trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ đƣợc cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian trƣớc khi nhận đƣợc CPU cho lƣợt kế tiếp. Thảo luận : Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của quantum. Nếu thời lƣợng quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu qủa. Nhƣng nếu sử dụng quantum quá lớn sẽ làm tăng. 4.4. Điều phối với độ ƣu tiên Nguyên tắc : Mỗi tiến trình đƣợc gán cho một độ ƣu tiên tƣơng ứng, tiến trình có độ ƣu tiên cao nhất sẽ đƣợc chọn để cấp phát CPU đầu tiên. Độ ƣu tiên có thể đƣợc định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ƣu tiên nội tại sử dụng các đại lƣợng có thể đo lƣờng để tính toán độ ƣu tiên của tiến trình, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ Độ ƣu tiên cũng có thể đƣợc gán từ bên ngoài dựa vào 52
54. các tiêu chuẩn do hệ điều hành nhƣ tầm quan trọng của tiến trình, loại ngƣời sử dụng sỡ hữu tiến trình Giải thuật điều phối với độ ƣu tiên có thể theo nguyên tắc độc quyền hay không độc quyền. Khi một tiến trình đƣợc đƣa vào danh sách các tiến trình sẵn sàng, độ ƣu tiên của nó đƣợc so sánh với độ ƣu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phối với độ ƣu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ƣu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó. Ví dụ : (độ ƣu tiên 1 > độ ƣu tiên 2> độ ƣu tiên 3) Sử dụng thuật giải độc quyền, thứ tự cấp phát CPU nhƣ sau : Sử dụng thuật giải không độc quyền, thứ tự cấp phát CPU nhƣ sau : Thảo luận : Tình trạng „đói CPU‟ (starvation) là một vấn đề chính yếu của các giải thuật sử dụng độ ƣu tiên. Các giải thuật này có thể để các tiến trình có độ ƣu tiên thấp chờ đọi CPU vô hạn ! Để ngăn cản các tiến trình có độ ƣu tiên cao chiếm dụng CPU vô thời hạn, bộ điều phối sẽ giảm dần độ ƣu tiên của các tiến trình này sau mỗi ngắt đồng hồ. Nếu độ ƣu tiên của tiến trình này giảm xuống thấp hơn tiến trình có độ ƣu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU.Quá trình này gọi là sự „lão hóa‟ (aging) tiến trình. 53
55. 4.4.1. Chiến lược công việc ngắn nhất (Shortest-job-first SJF) Nguyên tắc : Đây là một trƣờng hợp đặc biệt của giải thuật điều phối với độ ƣu tiên. Trong giải thuật này, độ ƣu tiên p đƣợc gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU đƣợc tự do, nó sẽ đƣợc cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới đƣợc đƣa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý. Ví dụ : Sử dụng thuật giải SJF độc quyền, thứ tự cấp phát CPU nhƣ sau: Sử dụng thuật giải SJF không độc quyền, thứ tự cấp phát CPU nhƣ sau: 54
56. Thảo luận : Giải thuật này cho phép đạt đƣợc thời gian chờ trung bình cực tiểu. Khó khăn thực sự của giải thuật SJF là không thể biết đƣợc thời gian yêu cầu xử lý còn lại của tiến trình ? Chỉ có thể dự đoán giá trị này theo cách tiếp cận sau : gọi tn là độ dài của thời gian xử lý lần thứ n, τ n+1 là giá trị dự đoán cho lần xử lý tiếp theo. Với hy vọng giá trị dự đoán sẽ gần giống với các giá trị trƣớc đó, có thể sử dụng công thức: τ n+1 = α tn + (1-α )τ n Trong công thức này,tn chứa đựng thông tin gần nhất ; τ n chứa đựng các thông tin quá khứ đƣợc tích lũy. Tham số α ( 0 ≤ α ≤ 1) kiểm soát trọng số của hiện tại gần hay quá khứ ảnh hƣởng đến công thức dự đóan. 4.5. Quản lý tiến trình-Tóm tắt Trong suốt chu trình sống, tiến trình chuyển đổi qua lại giữa các trạng thái ready, running và blocked. Bộ điều phối của hệ điều hành chịu trách nhiệm áp dụng một gỉai thuật điều phối thích hợp để chọn tiến trình thích hợp đƣợc sử dụng CPU, và bộ phân phối sẽ chuyển giao CPU cho tiến trình này. Các giải thuật điều phối thông dụng : FIFO, RoundRobin, điều phối với độ ƣu tiên, SJF, Multilevel Feedback 4.5.1. Câu hỏi cũng cố bài học Các câu hỏi cần trả lời đƣợc sau bài học này : 1. Thông tin lƣu trữ trong PCB và TCB ? 2. Tổ chức điều phối tiến trình ? 3. Phân tích ƣu, khuyết của các chiến lƣợc điều phối 4.5.2. Bài tập Bài 1. Xét tập các tiến trình sau (với thời gian yêu cầu CPU và độ ƣu tiên kèm theo) : 55
57. Giả sử các tiến trình cùng đƣợc đƣa vào hệ thống tại thời điểm 0 a)Cho biết kết quả điều phối hoạt động của các tiến trình trên theo thuật toán FIFO; SJF; điều phối theo độ ƣu tiên độc quyền (độ ƣu tiên 1 > 2 > ); và RR (quantum=2). b) Cho biết thời gian lƣu lại trong hệ thống (turnaround time) của từng tiến trình trong từng thuật toán điều phối ở câu a. c) Cho biết thời gian chờ trong hệ thống (waiting time) của từng tiến trình trong từng thuật toán điều phối ở câu a. d) Thuật toán điều phối nào trong các thuật toán ở câu a cho thời gian chờ trung bình là cực tiểu ? Bài 2. Giả sử có các tiến trình sau trong hệ thống : Sử dụng nguyên tắc điều phối độc quyền và các thông tin có đƣợc tại thời điểm ra quyết định để trả lời các câu hỏi sau đây : 56
58. a) Cho biết thời gian lƣu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối FIFO. b) Cho biết thời gian lƣu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối SJF. c) Thuật toán SJF dự định cải tiến sự thực hiện của hệ thống , nhƣng lƣu ý chúng ta phải chọn điều phối P1 tại thời điểm 0 vì không biết rằng sẽ có hai tiến trình ngắn hơn vào hệ thống sau đó . Thử tính thời gian lƣu lại trung bình trong ệ thống nếu để CPU nhàn rỗi trong 1 đơn vị thời gian đầu tiên và sau đó sử dụng SJF để điều phối. Lƣu ý P1 vàP2 sẽ phải chờ trong suốt thời gian nhàn rỗi này, do vậy thời gian chờ của chúng tăng lên. Thuật toán điều phối này đƣợc biết đến nhƣ điều phối dựa trên thông tin về tƣơng lai. Bài 3. Phân biệt sự khác nhau trong cách tiếp cận để ƣu tiên cho tiến trình ngắn trong các thuật toán điều phối sau : a) FIFO. b) RR c) Điều phối với độ ƣu tiên đa cấp Bài 4. Cho biết hai ƣu điểm chính của mô hình đa tiểu trình so với đa tiến trình. Mô tả một ứng dụng thích hợp vớ mô hình đa tiểu trình và một ứng dụng khác không thích hợp. Bài 5. Mô tả các xử lý hệ điều hành phải thực hiện khi chuyển đổi ngữ cảnh giữa : a)các tiến trình b)các tiểu trình Bài 6. Xác định thời lƣợng quantum q là một nhiệm vụ khó khăn. Giả sử chi phí trung bình cho một lần chuyển đổi ngữ cảnh là s, và thời gian trung bình một tiến trình hƣớng nhập xuất sử dụng CPU trƣớc khi phát sinh một yêu cầu nhập xuất là t ( t>>s). Thảo luận các tác động đến sự thực hiện của hệ thống khi chọn q theo các quy tắc sau : a) q bất định b) q lớn hơn 0 1 ít c)q = s d) s t 57
59. Bài 7. Giả sử một hệ điều hành áp dụng giải thuật điều phối multilevel feedback với 5 mức ƣu tiên (giảm dần). Thời lƣợng quantum dành cho hàng đợi cấp 1 là 0,5s. Mỗi hàng đợi cấp thấp hơn sẽ có thời lƣợng quantum dài gấp đôi hàng đợi ứng với mức ƣu tiên cao hơn nó. Một tiến trình khi vào hệ thống sẽ đƣợc đƣa vào hàng đợi mức cao nhất, và chuyển dần xuống các hàng đợi bên dƣới sau mỗi lƣợt sử dụng CPU. Một tiến trình chỉ có thể bị thu hồi CPU khi đã sử dụng hết thời lƣợng quantum dành cho nó. Hệ thống có thể thực hiện các tác vụ xử lý theo lô hoặc tƣơng tác, và mỗi tác vụ lại có thể hƣớng xử lý hay hƣớng nhập xuất. a)Giải thích tại sao hệ thống này hoạt động không hiệu quả ? b)Cần phải thay đổi (tối thiểu) nhƣ thế nào để hệ thống điều phối các tác vụ với những bản chất khác biệt nhƣ thế tốt hơn ? 58
60. CHƢƠNG 5. LIÊN LẠC GIỮA CÁC TIẾN TRÌNH VÀ VẤN ĐỀ ĐỒNG BỘ HÓA Các tiến trình trên nguyên tắc là hoàn toàn độc lập, nhƣng thực tế có thể nhƣ thế không ? Trong bài này chúng ta sẽ tìm hiểu lý do các tiến trình có nhu cầu liên lạc, các cơ chế hỗ trợ việc liên lạc này cũng nhƣ những vấn đề đặt ra khi các tiến trình trao đổi thông tin với nhau. 5.1. LIÊN LẠC GIỮA CÁC TIẾN TRÌNH 5.1.1. Nhu cầu liên lạc giữa các tiến trình Trong môi trƣờng đa chƣơng, một tiến trình không đơn độc trong hệ thống , mà có thể ảnh hƣởng đến các tiến trình khác , hoặc bị các tiến trình khác tác động. Nói cách khác, các tiến trình là những thực thể độc lập , nhƣng chúng vẫn có nhu cầu liên lạc với nhau để : Chia sẻ thông tin: nhiều tiến trình có thể cùng quan tâm đến những dữ liệu nào đó, do vậy hệ điều hành cần cung cấp một môi trƣờng cho phép sự truy cập đồng thời đến các dữ liệu chung. Hợp tác hoàn thành tác vụ: đôi khi để đạt đƣợc một sự xử lý nhanh chóng, ngƣời ta phân chia một tác vụ thành các công việc nhỏ có thể tiến hành song song. Thƣờng thì các công việc nhỏ này cần hợp tác với nhau để cùng hoàn thành tác vụ ban đầu, ví dụ dữ liệu kết xuất của tiến trình này lại là dữ liệu nhập cho tiến trình khác Trong các trƣờng hợp đó, hệ điều hành cần cung cấp cơ chế để các tiến trình có thể trao đổi thông tin với nhau. 5.1.2. Các vấn đề nảy sinh trong việc liên lạc giữa các tiến trình Do mỗi tiến trình sỡ hữu một không gian địa chỉ riêng biệt, nên các tiến trình không thể liên lạc trực tiếp dễ dàng mà phải nhờ vào các cơ chế do hệ điều hành cung cấp. Khi cung cấp cơ chế liên lạc cho các tiến trình, hệ điều hành thƣờng phải tìm giải pháp cho các vấn đề chính yếu sau : Liên kết tường minh hay tiềm ẩn (explicit naming/implicit naming) : tiến trình có cần phải biết tiến trình nào đang trao đổi hay chia sẻ thông tin với nó ? Mối liên kết đƣợc gọi là tƣờng minh khi đƣợc thiết lập rõ ràng , trực tiếp giữa các tiến trình, và là tiềm ẩn khi các tiến trình liên lạc với nhau thông qua một qui ƣớc ngầm nào 59
61. đó.Liên lạc theo chế độ đồng bộ hay không đồng bộ (blocking / non-blocking): khi một tiến trình trao đổi thông tin với một tiến trình khác, các tiến trình có cần phải đợi cho thao tác liên lạc hoàn tất rồi mới tiếp tục các xử lý khác ? Các tiến trình liên lạc theo cơ chế đồng bộ sẽ chờ nhau hoàn tất việc liên lạc, còn các tiến trình liên lạc theo cơ chế nonblocking thì không. Liên lạc giữa các tiến trình trong hệ thống tập trung và hệ thống phân tán: cơ chế liên lạc giữa các tiến trình trong cùng một máy tính có sự khác biệt với việc liên lạc giữa các tiến trình giữa những máy tính khác nhau? Hầu hết các hệ điều hành đƣa ra nhiều cơ chế liên lạc khác nhau, mỗi cơ chế có những đặc tính riêng, và thích hợp trong một hoàn cảnh chuyên biệt. 5.2. Cơ chế thông tin liên lạc 5.2.1. Tín hiệu (Signal) Giới thiệu: Tín hiệu là một cơ chế phần mềm tƣơng tự nhƣ các ngắt cứng tác động đến các tiến trình. Một tín hiệu đƣợc sử dụng để thông báo cho tiến trình về một sự kiện nào đó xảy ra. Có nhiều tín hiệu đƣợc định nghĩa, mỗi một tín hiệu có một ý nghĩa tƣơng ứng với một sự kiện đặc trƣng. Ví dụ : Một số tín hiệu của UNIX 60
62. Mỗi tiến trình sỡ hữu một bảng biễu diễn các tín hiệu khác nhau. Với mỗi tín hiệu sẽ có tƣơng ứng một trình xử lý tín hiệu (signal handler) qui định các xử lý của tiến trình khi nhận đƣợc tín hiệu tƣơng ứng. Các tín hiệu đƣợc gởi đi bởi : Phần cứng (ví dụ lỗi do các phép tính số học) Hạt nhân hệ điều hành gởi đến một tiến trình ( ví dụ lƣu ý tiến trình khi có một thiết bị nhập/xuất tự do). Một tiến trình gởi đến một tiến trình khác ( ví dụ tiến trình cha yêu cầu một tiến trình con kết thúc) Ngƣời dùng ( ví dụ nhấn phím Ctl-C để ngắt xử lý của tiến trình) 61
63. Khi một tiến trình nhận một tín hiệu, nó có thể xử sự theo một trong các cách sau : Bỏ qua tín hiệu Xử lý tín hiệu theo kiểu mặc định Tiếp nhận tín hiệu và xử lý theo cách đặc biệt của tiến trình. Hình 3.1 Liên lạc bằng tín hiệu Thảo luận: Liên lạc bằng tín hiệu mang tính chất không đồng bộ, nghĩa là một tiến trình nhận tín hiệu không thể xác định trƣớc thời điểm nhận tính hiệu. Hơn nữa các tiến trình không thể kiểm tra đƣợc sự kiện tƣơng ứng với tín hiệu có thật sự xảy ra ? Cuối cùng, các tiến trình chỉ có thể thông báo cho nhau về một biến cố nào đó, mà không trao đổi dữ liệu theo cơ chế này đƣợc. 5.2.2. Pipe Giới thiệu: Một pipe là một kênh liên lạc trực tiếp giữa hai tiến trình : dữ liệu xuất của tiến trình này đƣợc chuyển đến làm dữ liệu nhập cho tiến trình kia dƣới dạng một dòng các byte. Khi một pipe đƣợc thiết lập giữa hai tiến trình, một trong chúng sẽ ghi dữ liệu vào pipe và tiến trình kia sẽ đọc dữ liệu từ pipe. Thứ tự dữ liệu truyền qua pipe đƣợc bảo toàn theo nguyên tắc FIFO. Một pipe có kích thƣớc giới hạn (thƣờng là 4096 ký tự) 62
64. Hình 3.2 Liên lạc qua pipe Một tiến trình chỉ có thể sử dụng một pipe do nó tạo ra hay kế thừa từ tiến trình cha. Hệ điều hành cung cấp các lời gọi hệ thống read/write cho các tiến trình thực hiện thao tác đọc/ghi dữ liệu trong pipe. Hệ điều hành cũng chịu trách nhiệm đồng bộ hóa việc truy xuất pipe trong các tình huống: Tiến trình đọc pipe sẽ bị khóa nếu pipe trống, nó sẽ phải đợi đến khi pipe có dữ liệu để truy xuất. Tiến trình ghi pipe sẽ bị khóa nếu pipe đầy, nó sẽ phải đợi đến khi pipe có chỗ trống để chứa dữ liệu. Thảo luận: Liên lạc bằng pipe là một cơ chế liên lạc một chiều (unidirectional), nghĩa là một tiến trình kết nối với một pipe chỉ có thể thực hiện một trong hai thao tác đọc hoặc ghi, nhƣng không thể thực hiện cả hai. Một số hệ điều hành cho phép thiết lập hai pipe giữa một cặp tiến trình để tạo liên lạc hai chiều. Trong những hệ thống đó, có nguy cơ xảy ra tình trạng tắc nghẽn (deadlock) : một pipe bị giới hạn về kích thƣớc, do vậy nếu cả hai pipe nối kết hai tiến trình đều đầy(hoặc đều trống) và cả hai tiến trình đều muốn ghi (hay đọc) dữ liệu vào pipe(mỗi tiến trình ghi dữ liệu vào một pipe), chúng sẽ cùng bị khóa và chờ lẫn nhau mãi mãi ! Cơ chế này cho phép truyền dữ liệu với cách thức không cấu trúc. Ngoài ra, một giới hạn của hình thức liên lạc này là chỉ cho phép kết nối hai tiến trình có quan hệ cha-con, và trên cùng một máy tính. 5.2.3. Vùng nhớ chia sẻ Giới thiệu: Cách tiếp cận của cơ chế này là cho nhiều tiến trình cùng truy xuất đến một vùng nhớ chung gọi là vùng nhớ chia sẻ(shared memory).Không có bất kỳ hành vi truyền dữ liệu nào cần phải thực hiện ở đây, dữ liệu chỉ đơn giản đƣợc đặt vào một vùng nhớ mà nhiều tiến trình có thể cùng truy cập đƣợc. Với phƣơng thức này, các tiến trình chia sẻ một vùng nhớ vật lý thông qua trung gian không gian địa chỉ của chúng. Một vùng nhớ chia sẻ tồn tại độc lập với các tiến trình, và khi một tiến trình muốn truy xuất đến vùng nhớ này, tiến trình phải kết gắn vùng nhớ chung đó vào không gian địa chỉ riêng của từng tiến trình, và thao tác trên đó nhƣ một vùng nhớ riêng của mình. 63
65. Hình 3.3 Liên lạc qua vùng nhớ chia sẻ Thảo luận:. Đây là phƣơng pháp nhanh nhất để trao đổi dữ liệu giữa các tiến trình. Nhƣng phƣơng thức này cũng làm phát sinh các khó khăn trong việc bảo đảm sự toàn vẹn dữ liệu (coherence) , ví dụ : làm sao biết đƣợc dữ liệu mà một tiến trình truy xuất là dữ liệu mới nhất mà tiến trình khác đã ghi ? Làm thế nào ngăn cản hai tiến trình cùng đồng thờighi dữ liệu vào vùng nhớ chung ? Rõ ràng vùng nhớ chia sẻ cần đƣợc bảo vệ bằng những cơ chế đồng bộ hóa thích hợp Một khuyết điểm của phƣơng pháp liên lạc này là không thể áp dụng hiệu quả trong các hệ phân tán , để trao đổi thông tin giữa các máy tính khác nhau. 5.3. Trao đổi thông điệp (Message) Giới thiệu: Hệ điều hành còn cung cấp một cơ chế liên lạc giữa các tiến trình không thông qua việc chia sẻ một tài nguyên chung , mà thông qua việc gởi thông điệp. Để hỗ trợ cơ chế liên lạc bằng thông điệp, hệ điều hành cung cấp các hàm IPC chuẩn (Interprocess communication), cơ bản là hai hàm: Send(message) : gởi một thông điệp Receive(message) : nhận một thông điệpNếu hai tiến trình P và Q muốn liên lạc với nhau, cần phải thiết lập một mối liên kết giữa hai tiến trình, sau đó P, Q sử dụng các hàm IPC thích hợp để trao đổi thông điệp, cuối cùng khi sự liên lạc chấm dứt mối liên kết giữa hai tiến trình sẽ bị hủy. Có nhiều cách thức để thực hiện sự liên kết giữa hai tiến trình và cài đặt các theo tác send /receive tƣơng ứng : liên lạc trực tiếp hay gián tiếp, liên lạc đồng bộ hoặc không đồng bộ , kích thƣớc thông điệp là cố định hay không Nếu các tiến trình liên lạc theo kiểu liên kết tƣờng minh, các hàm Send và Receive sẽ đƣợc cài đặt với tham số : 64
66. Send(destination, message) : gởi một thông điệp đến destination Receive(source,message) : nhận một thông điệp từ source Thảo luận: Đơn vị truyền thông tin trong cơ chế trao đổi thông điệp là một thông điệp, do đó các tiến trình có thể trao đổi dữ liệu ở dạng có cấu trúc. 5.4. Sockets Giới thiệu: Một socket là một thiết bị truyền thông hai chiều tƣơng tự nhƣ tập tin, chúng ta có thể đọc hay ghi lên nó, tuy nhiên mỗi socket là một thành phần trong một mối nối nào đó giữa các máy trên mạng máy tính và các thao tác đọc/ghi chính là sự trao đổi dữ liệu giữa các ứng dụng trên nhiều máy khác nhau. Sử dụng socket có thể mô phỏng hai phƣơng thức liên lạc trong thực tế : liên lạc thƣ tín (socket đóng vai trò bƣu cục) và liên lạc điện thoại (socket đóng vai trò tổng đài) . Các thuộc tính của socket: Domaine: định nghĩa dạng thức địa chỉ và các nghi thức sử dụng. Có nhiều domaines, ví dụ UNIX, INTERNET, XEROX_NS, Type: định nghĩa các đặc điểm liên lạc: a) Sự tin cậy b) Sự bảo toàn thứ tự dữ liệu c) Lặp lại dữ liệu d) Chế độ nối kết e) Bảo toàn giới hạn thông điệp f) Khả năng gởi thông điệp khẩnĐể thực hiện liên lạc bằng socket, cần tiến hành các thao tác :: *Tạo lập hay mở một socket *Gắn kết một socket với một địa chỉ Liên lạc : có hai kiểu liên lạc tùy thuộc vào chế độ nối kết: a) Liên lạc trong chế độ không liên kết : liên lạc theo hình thức hộp thƣ: *hai tiến trình liên lạc với nhau không kết nối trực tiếp *mỗi thông điệp phải kèm theo địa chỉ ngƣời nhận. Hình thức liên lạc này có đặc điểm đƣợc : 65
67. *ngƣời gởi không chắc chắn thông điệp của học đƣợc gởi đến ngƣời nhận, *một thông điệp có thể đƣợc gởi nhiều lần, *hai thông điệp đƣợ gởi theo một thứ tự nào đó có thể đến tay ngƣời nhận theo một thứ tự khác. Một tiến trình sau khi đã mở một socket có thể sử dụng nó để liên lạc với nhiều tiến trình khác nhau nhờ sử hai primitive send và receive. b) Liên lạc trong chế độ nối kết: Một liên kết đƣợc thành lập giữa hai tiến trình. Trƣớc khi mối liên kết này đƣợc thiết lập, một trong hai tiến trình phải đợi có một tiến trình khác yêu cầu kết nối.Có thể sử dụng socket để liên lạc theo mô hình client-serveur. Trong mô hình này, server sử dụng lời gọi hệ thống listen và accept để nối kết với client, sau đó , client và server có thể trao đổi thông tin bằng cách sử dụng các primitive send và receive. *Hủy một socket Ví dụ : Trong nghi thức truyền thông TCP, mỗi mối nối giữa hai máy tính đƣợc xác định bởi một port, khái niệm port ở đây không phải là một cổng giao tiếp trên thiết bị vật lý mà chỉ là một khái niệm logic trong cách nhìn của ngƣời lập trình, mỗi port đƣợc tƣơng ứng với một số nguyên dƣơng. Hình 3.4 Các socket và port trong mối nối TCP. Hình 3.4 minh họa một cách giao tiếp giữa hai máy tính trong nghi thức truyền thông TCP. Máy A tạo ra một socket và kết buộc (bind) socket nầy với một port X (tức là một số nguyên dƣơng có ý nghĩa cục bộ trong máy A), trong khi đó máy B tạo một socket khác và móc vào (connect) port X trong máy A. Thảo luận: Cơ chế socket có thể sử dụng để chuẩn hoá mối liên lạc giữa các tiến trình vốn không liên hệ với nhau, và có thể hoạt động trong những hệ thống khác nhau. 66
68. 5.5. Nhu cầu đồng bộ hóa(synchronisation) Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây: 5.5.1. Yêu cầu độc quyền truy xuất (Mutual exclusion) Các tài nguyên trong hệ thống đƣợc phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lƣợng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thƣờng có nguồn gốc từ một trong hai nguyên nhân sau đây: Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ. Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán đƣợc do hoạt động của các tiến trình trên tài nguyên ảnh hƣởng lẫn nhau. Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình đƣợc quyền truy xuất một tài nguyên không thể chia sẻ. 5.5.2. Yêu cầu phối hợp (Synchronization) Nhìn chung, mối tƣơng quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trƣớc, vì điều này phụ thuộc vào nhiều yếu tố động nhƣ tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình đƣợc cấp phát bộ xử lý Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Nhƣ ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó 5.6. Bài toán đồng bộ hoá 5.6.1. Vấn đề tranh đoạt điều khiển (race condition) Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lƣu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản: 67
69. if (taikhoan - tienrut >=0)taikhoan = taikhoan - tienrut; else error(« khong the rut tien ! »); Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống nhƣ sau : Sau khi đã kiểm tra điều kiện (taikhoan - tienrut >=0) và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2. P2 kiểm tra cùng điều kiện trên, nhận đƣợc kết quả là 400 (do P1 vẫn chƣa rút tiền) và rút 400. Giá trị của taikhoan đƣợc cập nhật lại là 400. Khi P1 đƣợc tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0)-vì đã kiểm tra trong lƣợt xử lý trƣớc- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại đƣợc cập nhật thành -100. Tình huống lỗi xảy ra ! Các tình huống tƣơng tự nhƣ thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống- đƣợc gọi là các tình huống tranh đoạt điều khiển (race condition) . 5.6.2. Miền găng (critical section) Để ngăn chặn các tình huống lỗi có thể nảy sinh khi các tiến trình truy xuất đồng thời một tài nguyên không thể chia sẻ, cần phải áp đặt một sự truy xuất độc quyền trên tài nguyên đó : khi một tiến trình đang sử dụng tài nguyên, thì những tiến trình khác không đƣợc truy xuất đến tài nguyên. Đoạn chƣơng trình trong đó có khả năng xảy ra các mâu thuẫn truy xuất trên tài nguyên chung đƣợc gọi là miền găng (critical section). Trong ví dụ trên, đoạn mã : if (taikhoan - tienrut >=0) taikhoan = taikhoan - tienrut; của mỗi tiến trình tạo thành một miền găng. Có thể giải quyết vấn đề mâu thuẫn truy xuất nếu có thể bảo đảm tại một thời điểm chỉ có duy nhất một tiến trình đƣợc xử lý lệnh trong miền găng. 68
70. Một phƣơng pháp giải quyết tốt bài toán miền găng cần thõa mãn 4 điều kiện sau :Không có hai tiến trình cùng ở trong miền găng cùng lúc. Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng nhƣ về số lƣợng bộ xử lý trong hệ thống. 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 vào miền găng. 5.7. Tóm tắt Một số tiến trình trong hệ thống có nhu cầu trao đổi thông tin để phối hợp hoạt động, do mỗi tiến trình có một không gian địa chỉ độc lập nên viêc liên lạc chỉ có thể thực hiện thông qua các cơ chế do hệ điều hành cung cấp. Một số cơ chế trao đổi thông tin giữa các tiến trình : Tín hiệu : thông báo sự xảy ra của một sự kiện Pipe : truyền dữ liệu không cấu trúc Vùng nhớ chia sẻ : cho phép nhiều tiến trình truy cập đến cùng một vùng nhớ Trao đổi thông điệp : truyền dữ liệu có cấu trúc, có thể vận dụng trong các hệ phân tán Socket : chuẩn hoán việc liên lạc giữa các hệ thống khác biệt Khi các tiến trình trao đổi thông tin, chia sẻ tài nguyên chung, cần phải đồng bộ hoá hoạt động của chúng chủ yếu do yêu cầu độc quyền truy xuất hoặc phối hợp hoạt động. Miền găng là đoạn lệnh trong chƣơng trình có khả năng phát sinh mâu thuẫn truy xuất. Để không xảy ra mâu thuẫn truy xuất, cần đảm bảo tại một thời điểm chỉ có một tiến trình đƣợc vào miền găng. 5.7.1. Củng cố bài học Các câu hỏi cần trả lời đƣợc sau bài học này : 1. Các cơ chế trao đổi thông tin : tình huống sử dụng, ƣu, khuyết ? 69
71. 2. Các yêu cầu đồng bộ hoá ? 5.7.2. Bài tập Phân tích các bài toán sau đây và xác định những yêu cầu đồng bộ hoá, miền găng : Bài 1.Bài toán Tạo phân tử H 2 O Đồng bộ hoạt động của một phòng thí nghiệm sử dụng nhiều tiến trình đồng hành sau để tạo các phân tử H2O: MakeH() // Mỗi tiến trình MakeH tạo 1 nguyên tử H{ Make-Hydro();} MakeO() // Mỗi tiến trình MakeO tạo 1 nguyên tử O{ Make-Oxy();} MakeWater() /* Tiến trình MakeWater hoạt động đồng hành với các tiến trình MakeH, MakeO, chờ có đủ 2 H và 1 O để tạo H2O */{ while (T) Make-Water(); //Tạo 1 phân tử H2O} Bài 2.Bài toán Cây cầu cũ Để tránh sụp đổ, ngƣời ta chỉ có cho phép tối đa 3 xe lƣu thông đồng thời qua một cây cầu rất cũ. Hãy xây dựng thủ tục ArriveBridge(int direction) và ExitBridge() kiểm soát giao thông trên cầu sao cho : Tại mỗi thời điểm, chỉ cho phép tối đa 3 xe lƣu thông trên cầu. Tại mỗi thời điểm, chỉ cho phép tối đa 3 xe lƣuthông cùng hƣớng trên cầu. Mỗi chiếc xe khi đến đầu cầu sẽ gọi ArriveBridge(direction) để kiểm tra điều kiện lên cầu, và khi đã qua cầu đƣợc sẽ gọi ExitBridge() để báo hiệu kết thúc. Giả sử hoạt động của mỗi chiếc xe đƣợc mô tả bằng một tiến trình Car() sau đây: Car(int direction) /* direction xác định hƣớng di chuyển của mỗi chiếc xe.*/ { RuntoBridge(); // Đi về phía cầuArriveBridge(direction); PassBridge(); // Qua cầuExit Bridge();RunfromBridge(); // Đã qua cầu } Bài 3. Bài toán Qua sông 70
72. Để vƣợt qua sông, các nhân viên Microsof và các Linux hacker cùng sử dụng một bến sông và phải chia sẻ một số thuyền đặc biệt. Mỗi chiếc thuyền này chỉ cho phép chở 1lần 4 ngƣời, và phải có đủ 4 ngƣời mới khởi hành đƣợc. Để bảo đảm an toàn cho cả 2 phía, cần tuân thủ các luật sau : a. Không chấp nhận 3 nhân viên Microsoft và 1 Linux hacker trên cùng một chiếc thuyền. b. Ngƣợc lại, không chấp nhận 3 Linux hacker và 1 nhân viên Microsoft trên cùng một chiếc thuyền. c. Tất cả các trƣờng hợp kết hợp khác đều hợp pháp. d. Thuyền chỉ khởihành khi đã có đủ 4 hành khách. Cần xây dựng 2 thủ tục HackerArrives() và EmployeeArrives() đƣợc gọi tƣơng ứng bởi 1 hacker hoặc 1 nhân viên khi họ đến bờ sông để kiểm tra điều kiện có cho phép họ xuống thuyền không ? Các thủ tục này sẽ sắp xếp những ngƣời thích hợp có thể lên thuyền. Những ngƣời đã đƣợc lên thuyền khi thuyền chƣa đầy sẽ phải chờ đến khi ngƣời thứ 4 xuống thuyền mới có thể khởi hành qua sông. (Không quan tâm đến số lƣơng thuyền hay việc thuyền qua sông rồi trở lại Xem nhƣ luôn có thuyền để sắp xếp theo các yêu cầu hợp lệ) Giả sử hoạt động của mỗi hacker đƣợc mô tả bằng một tiến trình Hacker() sau đây: Hacker(){ RuntoRiver(); // Đi đến bờ sôngHackerArrives (); // Kiểm tra điều kiện xuống thuyềnCrossRiver(); // Khởi hành qua sông } và hoạt động của mỗi nhân viên đƣợc mô tả bằng một tiến trình Employee() sau đây: Employee(){ RuntoRiver(); // Đi đến bờ sôngEmployeeArrives (); // Kiểm tra điều kiện xuống thuyềnCrossRiver(); // Khởi hành qua sông } Bài 4. Bài toán Điều phối hành khách xe bus 71