Bài giảng Nguyên lý hệ điều hành
Mục lục
Chương 1. TỔNG QUAN VỀ HỆ ĐIỀU HÀNH .5
1.1. KHÁI NIỆM VỀ HỆ ĐIỀU HÀNH.5
1.2. PHÂN LOẠI HỆ ĐIỀU HÀNH.6
1.2.1. Hệ thống xử lý theo lô .6
1.2.2. Hệ thống xử lý theo lô đa chương .6
1.2.3. Hệ thống chia sẻ thời gian.7
1.2.4. Hệ thống song song.7
1.2.5. Hệ thống phân tán.8
1.2.6. Hệ thống xử lý thời gian thực.8
Chương 2. LUỒNG VÀ TIẾN TRÌNH.10
2.1. NHU CẦU XỬ LÝ ĐỒNG THỜI.10
2.1.1. Tăng hiệu suất sử dụng CPU .10
2.1.2. Tăng tốc độ xử lý .10
2.2. KHÁI NIỆM TIẾN TRÌNH(PROCESS) VÀ MÔ HÌNH ĐA TIẾN TRÌNH
(MULTIPROCESS).10
2.3. KHÁI NIỆM LUỒNG (THREAD) VÀ MÔ HÌNH ĐA LUỒNG
(MULTITHREAD).11
2.3.1. Nguyên lý chung: .12
2.3.2. Phân bổ thông tin lưu trữ.12
2.3.3. Kernel thread và user thread .13
Chương 3. LẬP LỊCH TIẾN TRÌNH.14
3.1. Tổ chức quản lý tiến trình .14
3.1.1. Các trạng thái của tiến trình.14
3.1.2. Chế độ xử lý của tiến trình.15
3.1.3. Cấu trúc dữ liệu khối quản lý tiến trình.15
3.1.4. Thao tác trên tiến trình.16
3.1.4.1. Tạo lập tiến trình.16
3.1.4.2. Kết thúc tiến trình.17
3.1.5. Cấp phát tài nguyên cho tiến trình.17
3.2. Lập lịch tiến trình.18
3.2.1. Giới thiệu.19
3.2.1.1. Mục tiêu lập lịch.19
3.2.1.2. Các đặc điểm của tiến trình.19
3.2.1.3. Điều phối không độc quyền và điều phối độc quyền
(preemptive/nopreemptive).20
3.2.2.1. Các danh sách sử dụng trong quá trình lập lịch.21
3.2.2.2. Các cấp độ lập lịch.22
3.2.3. Các thuật toán lập lịch.23
3.2.3.1. Chiến lược FIFO.23
3.2.3.2. Lập lịch xoay vòng (Round Robin).24
3.2.3.3. Lập lịch với độ ưu tiên.25
3.2.3.4. Chiến lược công việc ngắn nhất (Shortest-job-first SJF).26
3.2.3.5. Chiến lược điều phối với nhiều mức độ ưu tiên.27
3.2.3.6. Chiến lược lập lịch Xổ số (Lottery).28
Chương 4. TRUYỀN THÔNG VÀ ĐỒNG BỘ TIẾN TRÌNH .29
Faculty Of IT 1 KMA
Bài giảng: Nguyên Lý Hệ Điều Hành
4.1. LIÊN LẠC TIẾN TRÌNH .29
4.1.1. Nhu cầu liên lạc tiến trình.29
4.1.2. Các vấn đề nảy sinh trong việc liên lạc tiến trình.29
4.2. Các Cơ Chế Thông Tin Liên lạc.30
4.2.1. Tín hiệu (Signal).30
4.2.2. Pipe.31
4.2.3. Vùng nhớ chia sẻ.32
4.2.4. Trao đổi thông điệp (Message).32
4.2.5. Sockets.33
4.3. Nhu cầu đồng bộ hóa (synchronisation).34
4.3.1. Yêu cầu độc quyền truy xuất (Mutual exclusion) .34
4.3.2. Yêu cầu phối hợp (Synchronization).34
4.3.3. Bài toán đồng bộ hoá .35
4.3.3.1. Vấn đề tranh đoạt điều khiển (race condition).35
4.3.3.2. Miền găng (critical section).35
4.4. CÁC GIẢI PHÁP ĐỒNG BỘ HOÁ.37
4.4.1. Giải pháp « busy waiting ».37
4.4.1.1. Sử dụng các biến cờ hiệu(simaphore).37
4.4.1.2. Sử dụng việc kiểm tra luân phiên .37
4.4.1.3. Giải pháp của Peterson .38
4.4.1.4. Cấm ngắt: .38
4.4.1.5. Chỉ thị TSL (Test-and-Set) .39
4.4.2. Các giải pháp « SLEEP and WAKEUP ».39
4.4.2.1. Semaphore.41
4.4.2.2. Monitors.42
4.4.2.3. Trao đổi thông điệp.44
Chương 5. VẤN ĐỀ KHOÁ CHẾT (DEADLOCK).46
5.1. Mô hình hệ thống .46
5.2. Đặc điểm deadlock .47
5.2.1. Những điều kiện cần thiết gây ra deadlock .47
5.2.2. Đồ thị cấp phát tài nguyên .47
5.3. Các phương pháp xử lý deadlock .50
5.4. Ngăn chặn deadlock .51
5.4.1. Loại trừ hỗ tương .51
5.4.2. Giữ và chờ cấp thêm tài nguyên .51
5.4.3. Không đòi lại tài nguyên từ quá trình đang giữ chúng .52
5.4.4. Tồn tại chu trình trong đồ thị cấp phát tài nguyên .53
5.5. Tránh deadlock .53
5.5.1. Trạng thái an toàn .54
5.5.2. Giải thuật đồ thị cấp phát tài nguyên .54
5.5.3. Giải thuật của Banker .56
5.5.3.1. Giải thuật an toàn .57
5.5.3.2. Giải thuật yêu cầu tài nguyên .58
Chương 6: QUẢN LÝ BỘ NHỚ TRONG.59
6.1. Ngữ cảnh liên kết bộ nhớ.59
6.2. Không gian địa chỉ lôgic và không gian địa chỉ vật lý.60
6.3. Cấp phát liên tục.60
6.3.1. Mô hình Linker_Loader.60
6.3.2. Mô hình Base &Bound.61
6.4. Cấp phát không liên tục.63
6.4.1. Phân đoạn (Segmentation) .63
6.4.2. Phân trang ( Paging).66
6.4.3. Phân đoạn kết hợp phân trang (Paged segmentation).72
6.5. Bộ nhớ ảo.74
6.5.1. Cơ chế bộ nhớ ảo.74
6.5.1.1. Định nghĩa.74
6.5.1.2. Cài đặt bộ nhớ ảo.75
6.5.2. Thay thế trang.77
6.5.2.1. Sự thi hành phân trang theo yêu cầu.77
6.5.2.2. Các thuật toán thay thế trang.78
Chương 7. HỆ THỐNG QUẢN LÝ TẬP TIN.83
7.1. CÁC KHÁI NIỆM CƠ BẢN.83
7.1.1. Bộ nhớ ngoài .83
7.1.2. Tập tin và thư mục .83
7.1.3. Hệ thống quản lý tập tin.83
7.2. MÔ HÌNH TỔ CHỨC VÀ QUẢN LÝ CÁC TẬP TIN.84
7.2.1. Mô hình .84
7.2.1.1. Tập tin.84
7.2.1.2. Thư mục: .87
7.2.2. Các chức năng .89
7.2.2.1. Tập tin.89
7.2.2.2. Thư mục.89
7.3. CÁC PHƯƠNG PHÁP CÀI ĐẶT HỆ THỐNG QUẢN LÝ TẬP TIN.91
7.3.1. Bảng quản lý tệp tin, thư mục.91
7.3.1.1. Khái niệm .91
7.3.1.2. Cài đặt.91
7.3.2. Bảng phân phối vùng nhớ.92
7.3.2.1. Khái niệm .92
7.3.2.2. Các phương pháp.92
7.3.3. Tệp tin chia sẻ.94
7.3.4. Độ an toàn của hệ thống quản lý tệp tin.95
7.3.4.1. Quản lý khối bị hỏng .95
7.3.4.2. Sao lưu.96
7.3.4.3. Tính không đổi của hệ thống tệp tin .96
Chương 8. HỆ THỐNG QUẢN LÝ NHẬP/XUẤT.98
8.1. KHÁI NIỆM VỀ HỆ THỐNG QUẢN LÝ NHẬP/XUẤT.98
8.2. PHẦN CỨNG NHẬP/XUẤT.99
8.2.1. Thiết bị I/O .99
8.2.2. Tổ chức của chức năng I/O .99
8.2.3. Bộ điều khiển thiết bị .100
8.2.4. DMA (Direct Memory Access) .101
8.3. PHẦN MỀM NHẬP/XUẤT.102
Faculty Of IT 3 KMA
Bài giảng: Nguyên Lý Hệ Điều Hành
8.3.1. Kiểm soát ngắt .102
8.3.2. Điều khiển thiết bị (device drivers) .103
8.3.3. Phần mềm nhập/xuất độc lập thiết bị .103
8.3.4. Phần mềm nhập/xuất phạm vi người sử dụng .104
Chương 9. GIỚI THIỆU MỘT SỐ HỆ THỐNG I/O.105
9.1. HỆ THỐNG I/O ĐĨA.105
9.1.1. Phần cứng đĩa.105
9.1.2. Các thuật toán đọc đĩa .105
9.1.2.1. Lập lịch FCFS.106
9.1.2.2. Lập lịch SSTF (shortest-seek-time-first).106
9.1.2.3. Lập lịch SCAN.106
9.1.2.4. Lập lịch C-SCAN.107
9.1.2.5. Lập lịch LOOK.107
9.1.2.6. Lựa chọn thuật toán lập lịch:.108
9.1.3. Quản lý lỗi.108
9.1.4. RAM Disks.108
9.1.5. Interleave .109
9.2. HỆ THỐNG I/O CHUẨN (terminals).110
9.2.1. Phần cứng terminal.110
9.2.2. Terminal ánh xạ bộ nhớ.111
9.2.3. Phần mềm nhập.112
9.2.4. Phần mềm xuất.113
9.3. CÀI ĐẶT ĐỒNG HỒ.114
9.3.1. Phần cứng đồng hồ.114
9.3.2. Phần mềm đồng hồ .115
Chương 10. BẢO VỆ VÀ AN TOÀN HỆ THỐNG.117
10.1. Mục tiêu bảo vệ hệ thống (Protection).117
10.2. Miền bảo vệ (Domain of Protection).117
10.2.1. Khái niệm.117
10.2.2. Cấu trúc của miền bảo vệ .118
10.3. Ma trận quyền truy xuất ( Access matrix).119
i nào giá trị bằng 0, bộ điều khiển đồng hồ sẽ yêu cầu bộ lập lịch thiết lập giá trị cho một tiến trình khác. Chức năng thứ ba là kế toán việc sử dụng CPU. Cách thức chính xác nhất là sử dụng một bộ timer thứ hai, khác với timer hệ thống. Bộ timer thứ hai khởi động khi tiến trình bắt đầu và khi tiến trình kết thúc, timer này sẽ cho biết thời gian tiến trình đã thực hiện. Phần lớn hệ thống cần thiết thiết lập timer. Gọi là watchdog timer. Ví dụ, để sử dụng đĩa mềm, hệ thống phải khởi động motor và chờ khoảng 500msec đạt được tốc độ. Vì vậy, ý tưởng tốt là phải sử dụng watchdog timer để chờ cho thao tác I/O tiếp theo, vào khoảng 3 giây, không tắt motor. Faculty Of IT 116 KMA Bài giảng: Nguyên Lý Hệ Điều Hành CHƯƠNG 10. BẢO VỆ VÀ AN TOÀN HỆ THỐNG An toàn và bảo vệ hệ thống là chức năng khoông thể thiếu của các hệ điều hành hiện đại. Trong bài học này, chúng ta sẽ làm quen với các khái niệm về tổ chức an toàn hệ thống, cũng như các cơ chế bảo vệ hỗ trợ việc triển khai các chiến lược này. 10.1. Mục tiêu bảo vệ hệ thống (Protection) Mục tiêu của việc bảo vệ hệ thống là: - Bảo vệ chống lỗi của tiến trình : khi có nhiều tiến trình cùng hoạt động, lỗi của một tiến trình j phải được ngăn chặn không cho lan truyền trên hệ thống làm ảnh hưởng đến các tiến trình khác. Đặc biệt , qua việc phát hiện các lỗi tiềm ẩn trong các thành phần của hệ thống có thể tăng cường độ tin cậy hệ thống ( reliability) . - Chống sự truy xuất bất hợp lệ : Bảo đảm các bộ phận tiến trình sử dụng tài nguyên theo một cách thức hợp lệ được qui định cho nó trong việc khai thác các tài nguyên này . Vai trò của bộ phận bảo vệ trong hệ thống là cung cấp một cơ chế để áp dụng các chiến lược quản trị việc sử dụng tài nguyên . Cần phân biệt khái niệm cơ chế và chiến lược: - Cơ chế : xác định làm thế nào để thực hiện việc bảo vệ, có thể có các cơ chế phần mềm hoặc cơ chế phần cứng. - Chiến lược : quyết định việc bảo vệ được áp dụng như thế nào : những đối tượng nào trong hệ thống cần được bảo vệ, và các thao tác thích hợp trên các đối tượng này Để hệ thống có tính tương thích cao , cần phân tách các cơ chế và chiến lược được sử dụng trong hệ thống. Các chiến lược sử dụng tài nguyên là khác nhau tùy theo ứng dụng, và thường dễ thay đổi . Thông thường các chiến lược được lập trình viên vận dụng vào ứng dụng của mình để chống lỗi truy xuất bất hợp lệ đến các tài nguyên, trong khi đó hệ thống cung cấp các cơ chế giúp người sử dụng có thể thực hiện được chiến lược bảo vệ của mình. 10.2. Miền bảo vệ (Domain of Protection) 10.2.1. Khái niệm Một hệ thống máy tính được xem như một tập các đối tượng (objects). Một đối tượng có thể là một bộ phận phần cứng ( CPU, bộ nhớ, ổ đĩa...) hay một thực thể phần mềm ( tập tin, chương trình, semaphore...). Mỗi đối tượng có một định danh duy nhất để phân biệt với các đối tượng khác trong hệ thống, và chỉ được truy xuất đến thông qua các thao tác được định nghĩa chặt chẽ và được qui định ngữ nghĩa rõ ràng. Các thao tác có thể thực hiện được trên một đối tượng được xác định cụ thể tùy vào đối tượng. Để có thể kiểm soát được tình hình sử dụng tài nguyên trong hệ thống, hệ điều hành chỉ cho phép các tiến trình được truy xuất đến các tài nguyên mà nó có quyền sử dụng, hơn nữa tiến trình chỉ được truy xuất đến các tài nguyên cần thiết trong thời điểm Faculty Of IT 117 KMA Bài giảng: Nguyên Lý Hệ Điều Hành hiện tại để nó hoàn thành tác vụ (nguyên lý need-to-know) nhăm hạn chế các lỗi truy xuất mà tiến trình có thể gây ra trong hệ thống. Mỗi tiến trình trong hệ thống đều hoạt động trong một miền bảo vệ (protection domain) nào đó. Một miền bảo vệ sẽ xác định các tài nguyên ( đối tượng) mà những tiến trình hoạt động trong miền bảo vệ này có thể sử dụng, và các thao tác hợp lệ các tiến trình này có thể thực hiện trên những tài nguyên đó. Ví dụ : 10.2.2. Cấu trúc của miền bảo vệ Các khả năng thao tác trên một đối tượng được gọi là quyền truy xuất (access right). Một miền bảo vệ là một tập các quyền truy xuất, mỗi quyền truy xuất được định nghĩa bởi một bộ hai thứ tự . Các miền bảo vệ khác nhau có thể giao nhau một số quyền truy xuất : Hình 10.2.2-1. Hệ thống với 3 miền bảo vệ 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 : - Liên kết tĩnh : trong suốt thời gian sống của tiến trình, tiến trình chỉ hoạt động trong một miền bảo vệ . Trong trường hợp tiến trình trải qua các giai đoạn xử lý khác nhau, ở mỗi giai đoạn tiến trình có thể thao tác trên những tập tài nguyên khác nhau bằng các thao tác khác nhau. Tuy nhiên, nếu sử dụng liên kết tĩnh, rõ ràng là ngay từ đầu miền bảo vệ đã phải đặc tả tất cả các quyền truy xuất qua các giai đoạn cho tiến trình , điều này có thể khiến cho tiến trình có dư quyền trong một giai đoạn nào đó, và vi phạm nguyên lý need-to-know. Để có thể tôn trọng nguyên lý này, khi đó cần phải có khả năng cập nhật nội dung miền bảo vệ để có thể phản ánh các quyền tối thiểu của tiến trình trong miền bảo vệ tại một thời điểm! - Liên kết động : cơ chế này cho phép tiến trình chuyển từ miền bảo vệ này sang miền bảo vệ khác trong suốt thời gian sống của nó. Để tiếp tục tuân theo nguyên lý need-to-know, thay vì sửa đổi nội dung của miền bảo vệ, có thể tạo ra các miền bảo vệ mới với nội dung thay đổi qua từng giai đoạn xử lý của tiến trình, và chuyển tiến trình sang hoạt động trong miền bảo vệ phù hợp theo từng thời điểm. Một miền bảo vệ có thể được xây dựng cho: - Một người sử dụng : trong trường hợp này, tập các đối tượng được phép truy xuất phụ thuộc vào định danh của người sử dụng, miền bảo vệ được chuyển khi thay đổi người sử dụng. - Một tiến trình : trong trường hợp này, tập các đối tượng được phép truy xuất phụ thuộc vào định danh của tiến trình, miền bảo vệ được chuyển khi quyền điều khiển được chuyển sang tiến trình khác. Faculty Of IT 118 KMA Bài giảng: Nguyên Lý Hệ Điều Hành - Một thủ tục : trong trường hợp này, tập các đối tượng được phép truy xuất là các biến cục bộ được định nghĩa bên trong thủ tục, miền bảo vệ được chuyển khi thủ tục được gọi. 10.3. Ma trận quyền truy xuất ( Access matrix) Một cách trừu tượng, có thể biểu diễn mô hình bảo vệ trên đây như một ma trận quyền truy xuất ( access matrix). Các dòng của ma trận biễu diễn các miền bảo vệ và các cột tương ứng với các đối tượng trong hệ thống. Phần tử acess[i,j] của ma trận xác định các quyền truy xuất mà một tiến trình hoạt động trong miền bảo vệ Di có thể thao tác trên đối tượng Oj. object Domain F1 F2 F3 Máy in D1 đọc đọc D2 in D3 đọc xử lý D4 đọc ghi đọc Ghi Hình 10.3-1. Ma trận quyền truy xuất Cơ chế bảo vệ được cung cấp khi ma trận quyền truy xuất được cài đặt ( với đầy đủ các thuộc tính ngữ nghĩa đả mô tả trên lý thuyết), lúc này người sử dụng có thể áp dụng các chiến lược bảo vệ bằng cách đặc tả nội dung các phần tử tương ứng trong ma trận _ xác định các quyền truy xuất ứng với từng miền bảo vệ , và cuối cùng, hệ điều hành sẽ quyết định cho phép tiến trình hoạt động trong miền bảo vệ thích hợp. Ma trận quyền truy xuất cũng cung cấp một cơ chế thích hợp để định nghĩa và thực hiện một sự kiểm soát nghiêm nhặt cho cả phương thức liên kết tĩnh và động các tiến trình với các miền bảo vệ : Có thể kiểm soát việc chuyển đổi giữa các miền bảo vệ nếu quan niệm miền bảo vệ cũng là một đối tượng trong hệ thống, và bổ sung các cột mô tả cho nó trong ma trận quyền truy xuất. Khi đó tiến trình được phép chuyển từ miền bảo vệ Di sang miền bảo vệ Dj nếu phần tử access(i,j) chứa đựng quyền « chuyển » ( switch). object domain F1 F2 F3 Máy in D1 D2 D3 D4 D1 đọc đọc chuyển D2 in chuyển chuyển D3 đọc xử lý D4 đọc ghi đọc ghi chuyển Hình 10.3-2. Ma trận quyền truy xuất với domain là một đối tượng Faculty Of IT 119 KMA Bài giảng: Nguyên Lý Hệ Điều Hành Có thể kiểm soát việc sửa đổi nội dung ma trận (thay đổi các quyền truy xuất trong một miền bảo vệ) nếu quan niệm bản thân ma trận cũng là một đối tượng. Các thao tác sửa đổi nội dung ma trận được phép thực hiện bao gồm : sao chép quyền ( copy), chuyển quyền ( transfer), quyền sở hữu (owner), và quyền kiểm soát (control) - Copy: nếu một quyền truy xuất R trong access[i,j] được đánh dấu là R* thì có thể sao chép nó sang một phần tử access[k,j] khác ( mở rộng quyền truy xuất R trên cùng đối tượng Oj nhưng trong miền bảo vệ Dk ). - Transfer : nếu một quyền truy xuất R trong access[i,j] được đánh dấu là R+ thì có thể chuyển nó sang một phần tử access[k,j] khác ( chuyển quyền truy xuất R+ trên đối tượng Oj sang miền bảo vệ Dk ). - Owner : nếu access[i,j] chứa quyền truy xuất owner thì tiến trình hoạt động trong miền bảo vệ Di có thể thêm hoặc xóa các quyền truy xuất trong bất kỳ phần tử nào trên cột j (có quyền thêm hay bớt các quyền truy xuất trên đối tượng Oj trong những miền bảo vệ khác). - Control : nếu access[i,j] chứa quyền truy xuất control thì tiến trình hoạt động trong miền bảo vệ Di có thể xóa bất kỳ quyền truy xuất nào trong các phần tử trên dòng j (có quyền bỏ bớt các quyền truy xuất trong miền bảo vệ Dj). object domain F1 F2 F3 D1 xử lý ghi+ D2 xử lý đọc* xử lý D3 xử lý (a) object domain F1 F2 F3 D1 xử lý D2 xử lý đọc* xử lý D3 xử lý đọc ghi+ (b) Hình 10.3-3. Ma trận quyền truy xuất với quyền copy , transfer (a) trước, (b) sau cập nhật object domain F1 F2 F3 D1 owner xử lý Ghi D2 đọc* owner đọc* owner ghi* Faculty Of IT 120 KMA Bài giảng: Nguyên Lý Hệ Điều Hành D3 xử lý (a) object domain F1 F2 F3 D1 owner xử lý D2 owner đọc* ghi* đọc* owner ghi* D3 ghi (b) Hình 10.3-4. Ma trận quyền truy xuất với quyền owner (a) trước, (b) sau cập nhật object domain F1 F2 F3 Máy in D1 D2 D3 D4 D1 đọc đọc chuyển D2 in chuyển control chuyển D3 đọc xử lý D4 ghi Ghi chuyển Hình 10.3-5. Ma trận quyền truy xuất đã sửa đổi nội dung so với H5.3 nhờ quyền control Faculty Of IT 121 KMA
File đính kèm:
Bài giảng Nguyên lý hệ điều hành.pdf
