Giáo trình Hệ điều hành (Operating System) - Ninh Hải Xuân

Nội dung text: Giáo trình Hệ điều hành (Operating System) - Ninh Hải Xuân

1. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CƠ SỞ THÀNH PHỐ HỒ CHÍ MINH KHOA CƠNG NGHỆ THƠNG TIN W”X GIÁO TRÌNH HỆ ĐIỀU HÀNH (OPERATING SYSTEM) .EDU.VN BIÊN SOẠN NINH XUÂN HẢI - HUỲNH TRỌNG THƯA NĂM 2008
2. LỜI MỞ ĐẦU Hệ Điều Hành (Operating Systems) là một thành phần khơng thể thiếu trong một hệ thống máy tính. Một máy tính mặc dù đắt tiền, cấu hình cao nhưng nếu khơng cĩ hệ điều hành thì hầu như khơng thể sử dụng được. Hệ điều hành điều khiển mọi hoạt động của máy tính, giúp việc sử dụng máy tính trở nên đơn giản, dễ dàng và hiệu qủa hơn rất nhiều. Do vậy mơn học “Hệ điều hành” là mơn học quan trọng và rất cần thiết trong chương trình đào tạo chuyên nghành tin học ở hệ cao đẳng và kỹ sư. Giáo trình “Hệ điều hành” được biên soạn theo chương trình đào tạo chuyên nghành tin học ở hệ cao đẳng và kỹ sư của Bộ giáo dục và đào tạo. Giáo trình được chia thành 6 chương, chương 1, 2, 3, 4 do giảng viên Ninh Xuân Hải biên soạn, chương 5, 6 do giảng viên Huỳnh Trọng Thưa biên soạn. Tuy rằng chúng tơi đã cĩ nhiều cố gắng trong cơng tác biên soạn nhưng chắc chắn giáo trình vẫn cịn nhiều thiếu sĩt, nên rất mong được bạn đọc cũng như các đồng nghiệp đĩng gĩp ý kiến để giáo trình ngày càng hồn thiện, nhằm mục đích phục vụ tốt hơn cho việc dạy và học tin học đang ngày càng phát triển ở nước ta. Mọi sự gĩp ý hoặc thắc mắc xin gởi về địa chỉ Email: hainx@ptithcm.edu.vn hoặc htthua@ptithcm.edu.vn. Ngày 21 Tháng 11 Năm 2008 GV. biên soạn Ninh Xuân Hải - Huỳnh Trọng Thưa .EDU.VN 2
3. CHƯƠNG I GIỚI THIỆU HỆ ĐIỀU HÀNH Chương “GIỚI THIỆU VỀ HỆ ĐIỀU HÀNH ” sẽ giới thiệu và giải thích các vấn đề sau: 1.1 Hệ điều hành là gì, các khái niệm của hệ điều hành. 1.2 Lịch sử phát triển của hệ điều hành 1.3 Các loại hệ điều hành 1.4 Các dịch vụ của hệ điều hành. 1.5 Cấu trúc của hệ điều hành 1.6 Nguyên lý thiết kế hệ điều hành 1.1 CÁC KHÁI NIỆM 1.1.1 Hệ điều hành là gì? Hệ điều hành (operating systems) là chương trình đĩng vai trị trung gian giữa người sử dụng và phần cứng của máy tính. Hệ điều hành che dấu sự phức tạp, đa dạng của phần cứng, giúp việc sử dụng máy tính trở nên đơn giản, hiệu quả. Nhiệm vụ của hệ điều hành là quản lý tài nguyên của máy tính, thực thi các chương trình ứng dụng, hỗ trợ các chức năng mạng, vv 1.1.2 Các thành phần của một hệ thống máy tính Một hệ thống máy tính được chia thành 4 thành phần sau: phần cứng, hệ điều hành, chương trình ứng dụng/chương trình hệ thống, người sử dụng. + Phần cứng (hardware) : CPU, bộ nhớ, các thiết bị nhập/xuất, + Hệ điều hành (operating systems): điều khiển và phối hợp việc sử dụng phần cứng cho nhiều ứng dụng với nhiều người sử dụng khác nhau. + Chương trình ứng dụng và chương trình hệ thống (system and applications programs): là các chương trình giải quyết những vấn đề của người sử dụng như là chương trình dịch, hệ quản trị cơ sở dữ liệu, chương trình trị chơi, chương trình thương mại, + Người sử dụng (user): người sử dụng hoặc máy tính. .EDU.VN Hình 1.1: Các thành phần của một hệ thống máy tính 3
4. 1.1.3 Các thành phần của một hệ thống nhập/xuất Một hệ thống nhập/xuất gồm ba thành phần sau: + Hệ thống bộ nhớ đệm (buffer-caching system) + Chương trình điều khiển thiết bị (Drivers for specific hardware devices). + Chương trình giao tiếp với chương trình điều khiển thiết bị (A general device-driver interface). Chương trình giao tiếp với chương trình điều khiển thiết bị Chương trình điều khiển thiết bị Hệ thống bộ nhớ đệm Hình 1.2: Các thành phần của một hệ thống nhập/xuất 1.1.4 Các thành phần của hệ điều hành Hệ điều hành gồm cĩ ba thành phần sau: + Bộ cấp phát tài nguyên (Resource allocator): Quản lý và cấp phát tài nguyên. + Chương trình kiểm sốt (Control program): Kiểm sốt việc thực thi chương trình và kiểm sốt hoạt động của các thiết bị nhập/xuất. + Phần nhân (Kernel): là chương trình “lõi” của hệ điều hành, được thực thi trước tiên và tồn tại trong bộ nhớ cho đến khi tắt máy (các chương trình khác gọi là chương trình ứng dụng). Bộ cấp phát tài nguyên Chương trình kiểm sốt Phần nhân Hình 1.3: Các thành phần của hệ điều hành 1.2 LỊCH SỬ PHÁT TRIỂN CỦA HỆ ĐIỀU HÀNH + Giai đoạn 1 (1945 – 1955): đã cĩ máy tính lớn nhưng chưa cĩ hệ điều hành. + Giai đoạn 2 (1956 – 1965): hệ thống xử lý theo lơ (Batch systems) + Giai đoạn 3 (1966 – 1980): hệ thống xử lý đa chương (Multiprogramming systems) , hệ thống xử lý đa nhiệm (Multitasking systems). + Giai đoạn 4 (1981 - 2007 ): hệ thống đa xử lý (Multiprocessor systems), hệ thống xử lý phân tán (Distributed systems), hệ thống xử lý thời gian thực (Real-time systems), hệ thống nhúng (Embedded systems). 1.3 PHÂN LOẠI HỆ THỐNG MÁY TÍNH Một hệ thống máy tính gồm hai phần là hệ điều hành và phần cứng tương ứng để thực thi hệ điều hành. .EDU.VN1.3.1 Hệ thống xử lý theo lơ (Batch Systems) Đây là hệ điều hành đầu tiên, thơ sơ nhất. Đối với hệ điều hành này thì tại một thời điểm chỉ cĩ một cơng việc trong bộ nhớ, khi thực hiện xong một cơng việc, cơng việc khác sẽ được tự động nạp vào và cho thực thi. Hệ điều hành cĩ một chương trình, gọi là bộ giám sát, thường trú trong bộ nhớ chính, giám sát việc thực hiện dãy các cơng việc theo thứ tự và tự động. 4
5. Cách bố trí bộ nhớ của hệ điều hành xử lý theo lơ như sau: phần bộ nhớ ở địa chỉ thấp dành cho hệ điều hành, phần cịn lại dành cho một chương trình của người dùng. Hình 1.4: mơ hình tổ chức bộ nhớ của hệ điều hành xử lý theo lơ Xem một ví dụ về cách thức làm việc với hệ thống xử lý theo lơ: - Lập trình viên mang phiếu ghi chương trình đến máy 1401 - Máy sẽ đọc chương trình từ phiếu và ghi chương trình vào băng từ - Lập trình viên đem băng từ tới máy 7094 để thực hiện tính tốn và kết qủa được ghi vào băng từ - Lập trình viên đem băng từ chứa kết qủa tới máy 1402 để in Hình 1.5: ví dụ về cách thức xử lý cơng việc với hệ điều hành xử lý theo lơ 1.3.2 Hệ thống xử lý đa chương (MultiProgramming Systems) Tại một thời điểm cĩ nhiều cơng việc trong bộ nhớ và khi một cơng việc đang thực hiện, nếu cĩ yêu cầu nhập/xuất thì CPU khơng nghỉ mà hệ điều hành sẽ chuyển sang thực hiện cơng việc khác. Ví dụ trong bộ nhớ hiện cĩ ba chương trình thực hiện ba cơng việc. Nếu cơng việc 1 yêu cầu nhập/xuất thì cơng việc 1 tạm ngừng, cơng việc 2 (hoặc cơng việc 3) sẽ được thực hiện. Khi thao tác nhập/xuất của cơng việc 1 xong thì cơng việc 1 sẽ được thực hiện tiếp, cơng việc 2 sẽ tạm ngừng, .EDU.VN Hình 1.6: mơ hình tổ chức bộ nhớ của hệ thống xử lý đa chương 5
6. * Các chức năng của hệ điều hành trong hệ thống xử lý đa chương + Lập lịch CPU (CPU scheduling): chọn một trong những cơng việc trong bộ nhớ cho thực thi (cho sử dụng CPU). Khi chọn cần tránh trường hợp một cơng việc chờ trong bộ nhớ quá lâu. + Quản lý bộ nhớ (Memory management): cần phải quản lý phần bộ nhớ nào đã cấp phát và cấp cho cơng việc nào (bộ nhớ cấp phát cho mỗi cơng việc phải riêng biệt), phần bộ nhớ nào chưa cấp, khi một cơng việc thực thi xong cần thu hồi phần bộ nhớ đã cấp cho cơng việc đĩ. Nếu một cơng việc truy xuất đến phần bộ nhớ đã cấp cho cơng việc khác thì phải ngăn cấm. Nếu bộ nhớ bị phân mảnh quá nhiều, cần dồn bộ nhớ, vv + Cấp phát thiết bị (Allocation of devices): tình trạng thiết bị rảnh hay khơng rảnh, thiết bị đã cấp cho cơng việc nào, cơng việc nào cần đưa vào hàng đợi để chờ. Thiết bị nào cĩ thể dùng chung và tối đa bao nhiêu cơng việc sử dụng chung thiết bị cùng lúc, thiết bị nào khơng thể dùng chung, và phải tránh bị tắc nghẽn (các cơng việc chờ vơ hạn để được cấp tài nguyên). + Cung cấp các hàm xử lý nhập/xuất (I/O routines): Các hàm nhập/xuất sẽ che dấu sự phức tạp và đa dạng của các thiết bị nhập/xuất, quản lý việc sử dụng chung các thiết bị nhập/xuất. 1.3.3 Hệ thống xử lý đa nhiệm (Multitasking Systems) Hệ thống xử lý đa nhiệm là hệ thống mở rộng của hệ thống xử lý đa chương. Đối với hệ điều hành trong hệ thống xử lý đa nhiệm, việc chuyển đổi cơng việc khơng chờ cơng việc đang thực thi cĩ yêu cầu nhập/xuất, mà khi cơng việc đang thực thi hết thời gian qui định sử dụng CPU thì việc chuyển đổi cơng việc cũng sẽ xảy ra. Mỗi cơng việc được thực hiện luân phiên qua cơ chế chuyển đổi CPU, thời gian mỗi lần chuyển đổi diễn ra rất nhanh nên người sử dụng cĩ cảm giác là các cơng việc đang được thi hành cùng lúc. Hệ thống xử lý đa nhiệm cịn gọi là hệ thống chia xẻ thời gian (Time-Sharing Systems). Ví dụ hệ thống cĩ mơt CPU và hiện cĩ ba cơng việc A, B, C trong bộ nhớ. Ba cơng việc này sẽ được thực hiện luân phiên: cơng việc A thực hiện trong khoảng thời gian q (quantum) thì tạm ngừng, đến lượt cơng việc B thực hiện trong khoảng thời gian q, rồi đến lượt cơng việc C. Sau đĩ lại đến lượt A, lặp lại việc thực thi các cơng việc cho đến khi tất cả các cơng việc hồn tất. task C B A time Hình 1.7: các cơng việc A,B,C sử dụng cpu luân phiên trong hệ thống xử lý đa nhiệm .EDU.VN1.3.4 Hệ thống đa xử lý (Multiprocessor Systems) Máy tính cĩ nhiều bộ xử lý cùng chia xẻ hệ thống đường truyền dữ liệu, đồng hồ, bộ nhớ và các thiết bị ngoại vi. Mỗi CPU sẽ thực hiện một cơng việc và khi đĩ các cơng việc sẽ thực sự diễn ra đồng thời. Hệ thống đa xử lý cịn gọi là hệ thống xử lý song song (Parallel Systems). 6
7. Hình 1.7: mơ hình hệ thống đa xử lý: cĩ nhiều cpu nhưng sử dụng chung bộ nhớ * Ưu điểm của hệ thống đa xử lý + Sự hỏng hĩc của một bộ xử lý sẽ khơng ảnh hưởng đến tồn bộ hệ thống. + Hệ thống sẽ thực hiện rất nhanh do thực hiện các cơng việc đồng thời trên các bộ xử lý khác nhau + Việc liên lạc giữa các cơng việc dễ dàng bằng cách sử dụng bộ nhớ dùng chung. * Phân loại hệ thống đa xử lý + Hệ thống đa xử lý đối xứng (Symmetric MultiProcessing (SMP)): mỗi bộ xử lý chạy với một bản sao của hệ điều hành và các bộ xử lý là ngang cấp. Các hệ điều hành hiện nay đều hỗ trợ SMP. + Hệ thống đa xử lý bất đối xứng (Asymmetric multiprocessing): Cĩ một bộ xử lý chính (master processor) kiểm sốt, phân việc cho các bộ xử lý khác (slave processors). 1.3.5 Hệ thống xử lý phân tán (Distributed Operating Systems) Tương tự như hệ thống đa xử lý nhưng mỗi bộ xử lý cĩ bộ nhớ riêng. Các bộ xử lý liên lạc với nhau thơng qua các đường truyền dẫn mạng. Mạng LAN, WAN với hệ điều hành Windows, UNIX chính là các hệ thống xử lý phân tán. * Phân loại hệ thống xử lý phân tán: cĩ hai loại + Peer-to-peer: hệ thống mạng ngang hàng, các máy tính ngang cấp, khơng cĩ máy nào đĩng vai trị quản lý tài nguyên dùng chung. + Client-server: cĩ một máy đĩng vai trị quản lý các tài nguyên dùng chung gọi là máy server (máy chủ), các máy khác gọi là máy client (máy khách). Client muốn sử dụng tài nguyên dùng chung phải được server cấp quyền. Mơ hình hệ thống client-server: .EDU.VN Hình 1.8: mơ hình hệ thống xử lý phân tán * Ưu điểm của hệ thống xử lý phân tán + Dùng chung tài nguyên: máy in, tập tin + Tăng tốc độ tính tốn: phân chia cơng việc để tính tốn trên nhiều vị trí khác nhau + An tồn: Nếu một vị trí bị hỏng, các vị trí khác vẫn tiếp tục làm việc. + Truyền thơng tin dễ dàng: download/upload file, gởi/nhận mail, 7
8. 1.3.6 Hệ thống xử lý thời gian thực (Real-Time Systems) Hệ thống sẽ cho kết quả chính xác trong khoảng thời gian nhanh nhất. Hệ thống thường dùng cho những ứng dụng chuyên dụng như là hệ thống điều khiển trong cơng nghiệp. * Các loại hệ thống xử lý thời gian thực + Hệ thống xử lý thời gian thực cứng (Hard real-time): các cơng việc được hồn tất đúng thời điểm qui định. + Hệ thống xử lý thời gian thực mềm (Soft real-time): mỗi cơng việc cĩ một độ ưu tiên riêng và sẽ được thi hành theo độ ưu tiên. 1.3.7 Hệ thống nhúng (Embedded Systems) Hệ điều hành được nhúng trong các thiết bị gia dụng, các máy trị chơi, Do các thiết bị gia dụng cĩ bộ nhớ ít, bộ xử lý tốc độ thấp, kích thước màn hình nhỏ nên hệ điều hành này cần đơn giản, nhỏ gọn, cĩ tính đặc trưng cho từng thiết bị. Ví dụ hệ điều hành dùng cho máy PDAs (Personal Digital Assistants), Mobil phones, Hệ thống nhúng cịn được gọi là hệ thống cầm tay (Handheld Systems). 1.4 CÁC DỊCH VỤ CỦA HỆ ĐIỀU HÀNH Hệ điều hành thơng thường cần cung cấp các dịch vụ sau: - Quản lý tiến trình - Quản lý bộ nhớ chính (RAM) - Quản lý bộ nhớ phụ (DISK) - Quản lý hệ thống nhập xuất - Quản lý hệ thống tập tin - Bảo vệ hệ thống - Hệ thống dịng lệnh - Quản lý mạng - Các lời gọi hệ thống (system calls). 1.4.1 Dịch vụ quản lý tiến trình (Process Management) Tiến trình là một chương trình đang thi hành. Trong bộ nhớ, tại một thời điểm cĩ thể cĩ nhiều tiến trình, 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. Khi tiến trình được tạo ra hoặc đang thi hành sẽ được hệ điều hành cung cấp các tài nguyên để tiến trình hoạt .EDU.VNđộng như là CPU, bộ nhớ, tập tin, các thiết bị nhập/xuất Khi tiến trình kết thúc, hệ điều hành sẽ thu hồi lại các tài nguyên đã cấp phát. Một tiến trình khi thực thi lại cĩ thể tạo ra các tiến trình con và hình thành cây tiến trình. * Các chức năng của dịch vụ quản lý tiến trình + Tạo và hủy các tiến trình của người sử dụng và của hệ điều hành. 8
9. + Tạm ngưng và thực hiện lại một tiến trình. + Cung cấp cơ chế đồng bộ các tiến trình. + Cung cấp cơ chế liên lạc giữa các tiến trình. + Cung cấp cơ chế kiểm sốt tắc nghẽn. 1.4.2 Dịch vụ quản lý bộ nhớ chính (Main Memory Management) Tại một thời điểm, trong bộ nhớ chính cĩ thể cĩ nhiều tiến trình, hệ điều hành cần phải quản lý phần bộ nhớ đã cấp cho mỗi tiến trình để tránh xung đột. * Các chức năng của dịch vụ quản lý bộ nhớ chính + Lưu giữ thơng tin về các vị trí trong bộ nhớ đã sử dụng và tiến trình nào đang sử dụng. + Quyết định chọn tiến trình để nạp vào bộ nhớ chính khi bộ nhớ chính cĩ chỗ trống. + Cấp phát bộ nhớ cho tiến trình và thu hồi bộ nhớ khi tiến trình thực thi xong. 1.4.3 Dịch vụ quản lý bộ nhớ phụ (Secondary Management) Để lưu trữ dữ liệu lâu dài, dữ liệu cần lưu trên đĩa dạng tập tin, ngồi ra đĩa cịn lưu giữ các tiến trình khi bộ nhớ RAM khơng cịn đủ, vùng nhớ này gọi là bộ nhớ ảo. * Các chức năng của dịch vụ quản lý bộ nhớ phụ + Quản lý vùng trống trên đĩa (Free space management) + Xác định vị trí cất giữ dữ liệu (Storage allocation). + Lập lịch cho đĩa (Disk scheduling). 1.4.4 Dịch vụ quản lý hệ thống nhập/xuất (I/O System Management) Hệ điều hành cần che dấu những đặc thù của các thiết bị phần cứng, bằng cách cung cấp các chức năng xử lý nhập xuất đơn giản, khơng phụ thuộc vào chi tiết của mỗi loại thiết bị. 1.4.5 Dịch vụ quản lý hệ thống tập tin (File Management) 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 như băng từ, đĩa từ, đĩa quang, Mỗi dạng cĩ cĩ khả năng lưu trữ, tốc độ truyền dữ liệu và cách truy xuất khác nhau. Hệ điều hành cần đồng nhất cách truy xuất hệ thống lưu trữ, định nghĩa một đơn vị lưu trữ là tập tin. .EDU.VN* Các chức năng của dịch vụ quản lý hệ thống tập tin + Hỗ trợ các thao tác trên tập tin và thư mục (tạo/xem/xố/sao chép/di chuyển/đổi tên). + Ánh xạ tập tin trên hệ thống lưu trữ phụ. + Sao lưu tập tin trên các thiết bị lưu trữ. 9
10. 1.4.6 Dịch vụ bảo vệ hệ thống (Protection System) Hệ điều hành cần cung cấp cơ chế để đảm bảo rằng tài nguyên chỉ được truy xuất bởi những tiến trình cĩ quyền. Ví dụ đảm bảo rằng tiến trình chỉ được thi hành trong phạm vi địa chỉ của nĩ hoặc đảm bảo rằng khơng cĩ tiến trình nào độc chiếm CPU 1.4.7 Lời gọi hệ thống (system call) Lời gọi hệ thống là tập lệnh do hệ điều hành cung cấp dùng để giao tiếp giữa tiến trình của người dùng và hệ điều hành, lời gọi hệ thống cịn gọi là ngắt. Các lời gọi hệ thống cĩ thể được chia thành các loại như là tập lệnh quản lý tiến trình, tập lệnh quản lý tập tin, tập lệnh quản lý thiết bị, tập lệnh dùng để liên lạc giữa các tiến trình. Mỗi lời gọi hệ thống cĩ một số hiệu duy nhất dùng để phân biệt lời gọi này với lời gọi khác. Các địa chỉ nơi chứa mã lệnh của các ngắt (lời gọi hệ thống) được lưu trong một bảng gọi là bảng vectơ ngắt. Khi tiến trình dùng lời gọi hệ thống, cần cung cấp tham số cho lời gọi hệ thống. Cĩ ba phương pháp mà tiến trình dùng để chuyển tham số cho hệ điều hành: - Chuyển tham số vào thanh ghi - Lưu trữ tham số trong một bảng trong bộ nhớ và ghi địa chỉ bảng vào thanh ghi - Lưu trữ tham số vào stack và tham số được lấy ra bởi hệ điều hành . Ví dụ chuyển địa chỉ bảng X (bảng chứa các tham số) vào thanh ghi, gọi ngắt 13. Ngắt 13 là lời gọi hệ thống do hệ điều hành cung cấp. Hình 1.9: truyền tham số dạng bảng cho ngắt 13 .EDU.VN Quản lý tiến trình Lời gọi hàm Mơ tả Pid=fork() Tạo một tiến trình con giống tiến trình cha Pid=waitpid(pid, &statloc, options) Đợi một tiến trình con kết thúc Exit(status) Kết thúc việc thực thi tiến trình và trả về trạng thái 10
11. Quản lý Tập tin Lời gọi hàm Mơ tả Fd=open(file,how, ) Mở một file để đọc, ghi hoặc cả hai S=close(fd) Đĩng một file đã mở trước đĩ N=read(fd,buffer,nbytes) Đọc dữ liệu từ file vào vùng đệm N= write(fd,buffer,nbytes) Ghi dữ liệu từ buffer vào file Position=lseek(fd,offset,whence) Di chuyển con trỏ file S=stat(name,&buf) Lấy thơng tin trạng thái của file Quản lý Hệ thống file và thư mục Lời gọi hàm Mơ tả S=mkdir(name,mode) Tạo thư mục mới S=rmdir(name) Xĩa thư mục rỗng S=link(name1,name2) Tạo một đối tượng mới name2 trỏ vào đối tượng name1 trước đĩ S=unlink(name) Xĩa đối tượng thư mục S=mount(special,name,flag) Kích hoạt hệ thống file S=unmount(special) Ngừng kích hoạt hệ thống file Hình 1.10: Một số lời gọi hệ thống 1.4.8 Hệ thống thơng dịch dịng lệnh (Command-Interpreter System) Là tập lệnh cơ bản cùng trình thơng dịch lệnh để người sử dụng giao tiếp với hệ điều hành. Các lệnh cơ bản như lệnh quản lý tiến trình, quản lý nhập xuất, quản lý bộ nhớ chính, quản lý bộ nhớ phụ, quản lý tập tin và các lệnh bảo vệ hệ thống Các lệnh trong hệ thống thơng dịch dịng lệnh thực ra cũng sẽ gọi các các lời gọi hệ thống. 1.4.9 Quản lý mạng (Networking) Cung cấp các chức năng phân quyền, chia xẻ tài nguyên mạng, liên lạc giữa các tiến trình trên mạng, .EDU.VN1.5 CẤU TRÚC HỆ ĐIỀU HÀNH 1.5.1 Cấu trúc đơn giản Hệ điều hành khơng được chia thành những lớp (phần) rõ rệt, một lớp cĩ thể gọi hàm thuộc bất kỳ lớp nào khác. Hệ điều hành này đơn giản, dễ thiết kế, dễ cài đặt nhưng khĩ bảo vệ, khĩ mở rộng, và khĩ nâng cấp. Ví dụ hệ điều hành MSDOS là hệ điều hành cĩ cấu trúc đơn giản: chương trình 11
12. ứng dụng cĩ thể truy xuất trực tiếp các hàm nhập/xuất trong ROM BIOS để ghi trực tiếp lên màn hình hay bộ điều khiển đĩa. Hình 1.11: Cấu trúc của hệ điều hành MS-DOS (cấu trúc đơn giản) Hệ điều hành UNIX phiên bản đầu tiên cũng cĩ cấu trúc đơn giản và được chia thành hai phần: phần system calls và phần kernel. Phần kernel cung cấp tất cả các dịch vụ của hệ điều hành. Các phần cĩ thể gọi lẫn nhau. Hình 1.12: cấu trúc của hệ điều hành UNIX phiên bản đầu tiên (cấu trúc đơn giản) .EDU.VN 1.5.2 Cấu trúc phân lớp Hệ điều hành được chia thành nhiều lớp, mỗi lớp được xây dựng dựa vào những lớp thấp hơn. Lớp dưới cùng là phần cứng, lớp trên cùng là lớp giao tiếp với người sử dụng. Mỗi lớp chỉ sử dụng những hàm do lớp dưới cung cấp. Hạt nhân ở lớp kế lớp phần cứng, dùng các lệnh của phần cứng để tạo các lời gọi hệ thống. 12
13. Xem mơ hình phân lớp ở hình 1.12: Lớp M thừa kế một số hàm của lớp M-1 và cĩ thể cĩ thêm một số hàm của riêng mình. Những hàm mà lớp M-1 đặt thuộc tính ẩn thì lớp M khơng được thừa kế. Hình 1.13: mơ hình cấu trúc phân lớp Tầng Chức năng 5 Thao tác 4 Chương trình người dung 3 Quản lý Xuất/Nhập 2 Truyền thơng Thao tác-Tiến trình 1 Quản lý bộ nhớ 0 Đa chương Hình 1.14: cấu trúc phân lớp của hệ điều hành THE 1.5.3 Cấu trúc máy ảo Với hệ điều hành máy ảo, một máy được giả lập thành nhiều máy, tài nguyên của hệ thống như là CPU, bộ nhớ, đĩa, được chia xẻ để tạo các máy ảo. Mỗi máy ảo được cơ lập với máy ảo khác nên tài nguyên dùng chung được bảo vệ nhưng cũng dẫn đến việc khơng được chia xẻ tài nguyên trực tiếp. .EDU.VN 13
14. Hình 1.15: Mơ hình cấu trúc máy ảo 1.5.4 Cấu trúc Client-Server Hệ điều hành được chia thành nhiều phần (gọi là các tiến trình server), mỗi tiến trình thực hiện một dịch vụ như là dịch vụ quản lý tập tin, quản lý tiến trình, quản lý bộ nhớ, Các tiến trình yêu cầu (gọi là tiến trình client) sẽ gửi yêu cầu đến một tiến trình server, tiến trình server thực hiện và gửi kết quả trở lại cho tiến trình client. Hạt nhân chỉ cĩ nhiệm vụ kiểm sốt quá trình liên lạc giữa các tiến trình client và server. * Ưu điểm của cấu trúc client-server + Hạt nhân rất nhỏ, chỉ gồm các lệnh cơ bản, nên dễ bảo vệ, dễ nâng cấp. + Mỗi dịch vụ của hệ điều hành do một tiến trình server đảm nhận, các tiến trình này độc lập với nhau nên khi một tiến trình server bị lỗi, hệ thống vẫn hoạt động. + Các tiến trình server được thực hiện ở chế độ người dùng (user-mode), khơng phải ở chế độ hạt nhân (kernel-mode), nên khơng truy xuất trực tiếp phần cứng. + Cấu trúc client-server rất thích hợp với mơ hình hệ thống phân tán. Các tiến trình server cĩ thể thực thi ở các máy khác nhau. .EDU.VN Hình 1.17: Mơ hình hệ điều hành client-server trên một máy 14
15. Hình 1.18: Mơ hình hệ điều hành client-server trên nhiều máy 1. 6 NGUYÊN LÝ THIẾT KẾ HỆ ĐIỀU HÀNH + Hệ điều hành cần dễ viết, dễ sửa lỗi, dễ nâng cấp (nên viết hệ điều hành bằng ngơn ngữ cấp cao vì dễ viết và dễ sửa lỗi hơn là viềt bằng ngơn ngữ assembly). + Hệ điều hành cần dễ cài đặt, dễ bảo trì, khơng cĩ lỗi và hiệu qủa. + Hệ điều hành cần dễ sử dụng, dễ học, an tồn, cĩ độ tin cậy cao và thực hiện nhanh. + Hệ điều hành cần cĩ tính khả chuyển cao (thực hiện được trên một nhĩm các phần cứng khác nhau). + Hệ điều hành cần cĩ chương trình SYSGEN (System Generation) thu thập thơng tin liên quan đến phần cứng để thiết lập cấu hình hệ điều hành cho phù hợp với mỗi máy tính. TĨM TẮT Một hệ thống máy tính gồm cĩ phần cứng, hệ điều hành và các chương trình ứng dụng. Hệ điều hành giúp cho việc sử dụng máy tính hiệu quả, đơn giản hơn. Hệ điều hành cĩ nhiều loại nhưng thơng dụng là loại hệ điều hành đa nhiệm, phân tán. Hệ điều hành cung cấp các dịch vụ cơ bản như dịch vụ quản lý tiến trình, dịch vụ quản lý bộ nhớ, dịch vụ quản lý tập tin, dịch vụ quản lý nhập/xuất, và một tập các lời gọi hệ thống (ngắt). Hệ điều hành cần thiết kế sao cho dễ sửa lỗi, dễ cài đặt, dễ bảo trì, khơng cĩ lỗi, dễ sử dụng, dễ học, độ tin cậy cao, thực hiện nhanh và cĩ tính khả chuyển cao. CÂU HỎI – BÀI TẬP 1. Nêu mục đích chung của hệ điều hành 2. Phân biệt hệ thống đa chương và hệ thống đa nhiệm 3. Nêu các vấn đề mà hệ thống đa chương/đa nhiệm cần giải quyết 3. Phân biệt hệ thống đa nhiệm và hệ thống đa xử lý .EDU.VN4. Phân biệt hệ thống đa xử lý và hệ thống xử lý phân tán 5. Nêu mục đích của hệ thống bộ nhớ đệm (buffer-caching system) trong hệ thống nhập/xuất 6. Chương trình điều khiển thiết bị (Drivers for specific hardware devices) do hệ điều hành cung cấp hay do hãng sản xuất thiết bị cung cấp? 7. Chương trình giao tiếp với chương trình điều khiển thiết bị (general device-driver interface) do hệ điều hành hay do hãng sản xuất hay do ngơn ngữ lập trình hay do người lập trình cung cấp? 15
16. 8. Phần nhân (kernel) của hệ điều hành MS-DOS gồm những chương trình nào? 9. Nêu khuyết điểm của hệ điều hành cĩ cấu trúc đơn giản. TÀI LIỆU THAM KHẢO [1]. Gary J. Nutt, University of Colorado. Centralized And Distributed Operating Systems. Second Edition, 2000. [2]. Robert Switzer. Operating Systems, A Practical Approach. Prentice-Hall International, Inc. 1993. [3]. Andrew S. Tanenbaum. Modern Operating Systems. Prentice-Hall International, Inc. Second Edition, 2001. [4]. Abraham Silberschatz & Peter Baer Galvin. Operating System concepts. John Wiley & Sons, Inc. Fifth Edition, 1999. [5]. H. M. Deitel. Operating Systems. Addison-Wesley Inc. Second Edition, 1999. [6] Cẩm nang lập trình hệ thống cho máy vi tính IBM-PC tập 1 và 2, tác giả Michael Tischer. [7]. Trần Hạnh Nhi & Lê Khắc Nhiên Ân & Hồng Kiếm. Giáo trình hệ điều hành (tập 1 & 2). ĐHKHTN 2000. .EDU.VN 16
17. CHƯƠNG 2 QUẢN LÝ NHẬP/XUẤT VÀ QUẢN LÝ HỆ THỐNG TẬP TIN Chương “QUẢN LÝ NHẬP/XUẤT VÀ QUẢN LÝ HỆ THỐNG TẬP TIN” sẽ giới thiệu và giải thích các vấn đề sau: 2.1. Quản lý nhập/xuất 2.1.1 Phân loại và đặc tính của thiết bị nhập/xuất 2.1.2 Bộ điều khiển thiết bị nhập/xuất 2.1.3 Các chương trình thực hiện nhập/xuất và tổ chức hệ thống nhập/xuất 2.1.4 Cơ chế nhập/xuất và cơ chế DMA 2.1.5 Các thuật tốn lập lịch di chuyển đầu đọc 2.1.6 Hệ số đan xen và ram disk 2.2 Quản lý hệ thống tập tin 2.2.1 Các khái niệm về đĩa cứng, tập tin, thư mục, bảng thư mục 2.2.2 Các phương pháp cài đặt hệ thống tập tin. 2.2.3 Phương pháp quản lý danh sách các khối trống 2.2.4 Phương pháp quản lý sự an tồn của hệ thống tập tin 2.2.5 Giới thiệu một số hệ thống tập tin: MSDOS/Windows, UNIX. 2.1. QUẢN LÝ NHẬP/XUẤT 2.1.1 Phân loại và đặc tính của thiết bị nhập/xuất * Phân loại thiết bị nhập/xuất: + Thiết bị khối: thơng tin được đọc/ghi theo từng khối cĩ kích thước cố định và cĩ địa chỉ xác định, ví dụ đĩa là một thiết bị khối. + Thiết bị tuần tự: thơng tin được gửi/nhận theo dãy tuần tự các bit, khơng cĩ địa chỉ, ví dụ màn hình, bàn phím, máy in, card mạng, chuột là thiết bị tuần tự. + Thiết bị khác: cĩ một số các thiết bị khơng phù hợp với hai loại trên, ví dụ đồng hồ khơng là thiết bị khối, cũng khơng là thiết bị tuần tự. * Đặc tính của thiết bị nhập/xuất: .EDU.VN+ Tốc độ truyền dữ liệu: ví dụ bàn phím : 0.01 KB/s, chuột 0.02 KB/s + Dung lượng lưu trữ, thời gian truy xuất một đơn vị dữ liệu. + Cơng dụng: dùng để nhập hay xuất + Đơn vị truyền dữ liệu: truyền theo khối hoặc ký tự + Biểu diễn dữ liệu: điều này tùy thuộc vào từng thiết bị cụ thể. + Tình trạng lỗi: nguyên nhân gây ra lỗi, cách mà thiết bị báo lỗi 17
18. Hình 2.1: thời gian truy xuất và dung lượng của một số thiết bị nhập/xuất 2.1.2 Bộ điều khiển thiết bị nhập/xuất (I/O controller) Là phần cứng điều khiển trực tiếp thiết bị nhập/xuất, CPU khơng thể truy xuất trực tiếp thiết bị nhập/xuât mà phải thơng qua bộ điều khiển thiết bị, dùng hệ thống đường truyền gọi là bus. Ví dụ bộ điều khiển màn hình đọc các ký tự cần hiển thị trong bộ nhớ và điều khiển các tia của CRT (ống phĩng điện tử của màn hình) để xuất ký tự trên màn hình. Thiết bị nhập/xuất và bộ điều khiển phải tuân theo cùng chuẩn giao tiếp như chuẩn ANSI, IEEE hay ISO Bộ điều khiển thiết bị nhập/xuất cĩ thể điều khiển được nhiều thiết bị, ví dụ một bộ điều khiển màn hình (video controller) cĩ thể điều khiển nhiều màn hình. Hình 2.2: CPU truy xuất các thiết bị nhập/xuât thơng qua bộ điều khiển thiết bị Mỗi bộ điều khiển cĩ một số thanh ghi để liên lạc với CPU, các thanh ghi này được gán một địa chỉ xác định như là một phần của bộ nhớ chính, gọi là ánh xạ bộ nhớ nhập/xuất. Ví dụ: Bộ điều khiển Địa chỉ nhập/xuất Vectơ ngắt nhập/xuất (địa chỉ của các thanh ghi) .EDU.VN Đồng hồ 040 - 043 8 Bàn phím 060 - 063 9 RS232 phụ 2F8 - 2FF 11 Đĩa cứng 320 - 32F 13 18
19. Máy in 378 - 37F 15 Màn hình mono 380 - 3BF - Màn hình màu 3D0 - 3DF - Đĩa mềm 3F0 - 3F7 14 RS232 chính 3F8 - 3FF 12 Hình 2.3: bảng địa chỉ các thanh ghi của một số bộ điều khiển nhập/xuất. CPU thực hiện nhập/xuất bằng cách ghi lệnh, cùng các tham số lên các thanh ghi của bộ điều khiển, sau đĩ CPU sẽ thực hiện cơng việc khác. Khi bộ điều khiển thực hiện xong, sẽ phát sinh một ngắt để báo hiệu cho CPU biết và đến lấy kết quả (kết quả cũng được bộ điều khiển lưu trong các thanh ghi). 2.1.3 Các chương trình thực hiện nhập/xuất và tổ chức hệ thống nhập/xuất * Các chương trình thực hiện nhập/xuất: + Chương trình nhập/xuất của người dùng (user program): thực hiện các lời gọi đến chương trình nhập/xuất độc lập thiết bị. + Chương trình nhập/xuất độc lập thiết bị: cịn gọi là lời gọi hệ thống nhập/xuất hoặc ngắt nhập/xuất, do hệ điều hành cung cấp, chương trình nhập/xuất độc lập thiết bị cung cấp một giao tiếp đồng nhất cho chương trình nhập/xuất của người dùng. + Chương trình điều khiển thiết bị (Device drivers): do hệ điều hành hoặc nhà sản xuất thiết bị cung cấp, chương trình này phụ thuộc vào thiết bị, sẽ nhận những yêu cầu nhập/xuất của chương trình nhập/xuất độc lập thiết bị. Nếu device driver đang bận, yêu cầu đĩ sẽ được đưa vào hàng đợi, ngược lại nĩ sẽ thực hiện ngay yêu cầu, bằng cách chuyển lệnh vào thanh ghi của bộ điều khiển thiết bị (I/O controller). .EDU.VN Hình 2.4: Sự giao tiếp giữa các chương trình thực hiện nhập/xuất 19
20. * Tổ chức hệ thống nhập/xuất Hệ thống quản lý nhập/xuất được phân chia thành 5 lớp là: tiến trình người dùng (user processes), chương trình nhập/xuất độc lập thiết bị (device-independent software), chương trình điều khiển thiết bị (device drivers), chương trình kiểm sốt ngắt (interrupt handlers), phần cứng (hardware). Mỗi lớp cĩ chức năng riêng và cĩ thể giao tiếp với lớp khác. Hình 2.5: mơ hình phân lớp của hệ thống quản lý nhập/xuất + Tiến trình người dùng (user processes): định dạng nhập/xuất, thực hiện lời gọi nhập/xuất. + Chương trình nhập/xuất độc lập thiết bị (Device-independent software): đặt tên, bảo vệ, tổ chức khối, tổ chức bộ đệm, cấp phát, + Chương trình điều khiển thiết bị (Device driver): thiết lập giá trị các thanh ghi thiết bị, kiểm tra trạng thái thiết bị, + Chương trình kiểm sốt ngắt (Interrupt handlers): thơng báo cho chương trình điều khiển thiết bị khi thao tác nhập/xuất hồn tất. + Phần cứng nhập/xuất (I/O Hardware): thực hiện thao tác nhập/xuất Ví dụ tiến trình người dùng (user processes) muốn đọc một khối dữ liệu trên đĩa, sẽ gởi yêu cầu nhập/xuất đến chương trình nhập/xuất độc lập thiết bị (device-independent software), chương trình này sẽ tìm kiếm khối trong bộ đệm nhập/xuất, nếu khối cần đọc chưa cĩ trong bộ đệm, nĩ sẽ gọi chương trình điều khiển thiết bị (device driver). Chương trình điều khiển thiết bị gửi yêu cầu đến đĩa cứng và tiến trình người dùng sẽ tạm ngưng cho đến khi thao tác đọc đĩa hồn tất, đĩa sẽ phát sinh một ngắt thơng báo đã đọc xong, gởi tín hiệu ngắt cho chương trình kiểm sốt ngắt. Chương trình kiểm sốt ngắt ghi nhận trạng thái của thiết bị và đánh thức tiến trình của người .EDU.VNdùng để tiếp tục thực hiện. 20
21. Hình 2.6: khi thao tác đọc đĩa hồn tất, bộ điều khiển đĩa sẽ phát sinh một ngắt. 2.1.4 Cơ chế nhập/xuất và cơ chế DMA * Cơ chế nhập/xuất: - Bộ xử lý phát sinh một lệnh I/O đến các thiết bị I/O, sau đĩ chờ cho đến khi thao tác I/O hồn tất rồi mới tiếp tục xử lý, hoặc: - Bộ xử lý phát sinh một lệnh I/O đến các thiết bị I/O, sau đĩ tiếp tục việc xử lý cho tới khi nhận được một ngắt từ thiết bị I/O báo là đã hồn tất nhập/xuất, bộ xử lý tạm ngưng việc xử lý hiện tại để chuyển qua xử lý ngắt, hoặc: - Sử dụng cơ chế DMA * Cơ chế DMA (Direct Memory Access): Xét quá trình đọc đĩa, CPU gửi cho bộ điều khiển đĩa (disk controller) lệnh đọc đĩa và các thơng số như địa chỉ trên đĩa của khối, địa chỉ trong bộ nhớ RAM nơi sẽ cất khối đọc được, số byte cần đọc, sau đĩ CPU tiếp tục xử lý cơng việc khác. Bộ điều khiển sẽ đọc khối trên đĩa, từng bit cho tới khi tồn bộ khối được đưa vào buffer của bộ điều khiển (local buffer). Tiếp theo bộ điều khiển phát ra một ngắt để báo cho CPU biết là thao tác đọc đã hồn tất. CPU đến lấy dữ liệu trong buffer chuyển vào bộ nhớ chính (RAM) bằng cách tạo một vịng lặp đọc lần lượt từng byte. Thao tác này làm lãng phí thời gian của CPU. Để tối ưu, bộ điều khiển thường được cung cấp thêm khả năng truy xuất bộ nhớ trực tiếp (DMA). Nghĩa là sau khi bộ điều khiển đã đọc tồn bộ dữ liệu từ thiết bị vào buffer của nĩ, bộ điều khiển chuyển byte đầu tiên vào bộ nhớ chính tại địa chỉ được mơ tả bởi địa chỉ bộ nhớ DMA. Sau đĩ nĩ tăng địa chỉ DMA và giảm số bytes phải chuyển. Quá trình này lặp lại cho tới khi số bytes phải chuyển bằng 0, và bộ điều khiển tạo một ngắt. Như vậy bộ điều khiển tự chuyển khối vào trong bộ nhớ chính. .EDU.VN Hình 2.7: Cơ chế DMA 21
22. 2.1.5 Các thuật tốn lập lịch di chuyển đầu đọc Để truy xuất các khối trên đĩa, trước tiên phải di chuyển đầu đọc đến track thích hợp, thao tác này gọi là seek và thời gian để hồn tất thao tác này gọi là seek time. Một khi đã đến đúng track, cịn phải chờ cho đến khi khối cần thiết đến dưới đầu đọc, thời gian chờ này gọi là latency time. Cuối cùng là chuyển dữ liệu từ đĩa vào bộ nhớ chính, thời gian này gọi là transfer time. Tổng thời gian cho dịch vụ đĩa chính là tổng của ba khoảng thời gian trên (seek time + latency time + transfer time). Trong đĩ seek time và latency time là mất nhiều thời gian nhất, do đĩ để giảm thiểu thời gian truy xuất, hệ điều hành cần đưa ra các thuật tốn lập lịch dời đầu đọc sao cho tối ưu. Hình 2.8: mơ hình đĩa cứng 2.1.5.1 Thuật tốn FCFS (first-come, first-served) Thuật tốn sẽ dời đầu đọc theo thứ tự đúng với thứ tự các khối cần đọc, thuật tốn dễ lập trình nhưng chưa tốt. Ví dụ cần phải đọc các khối theo thứ tự như sau: 98, 183, 37, 122, 14, 124, 65, và 67. Giả sử hiện tại đầu đọc đang ở vị trí 53, thuật tốn sẽ dời đầu đọc lần lượt đi qua các khối 53, 98, 183, 37, 122, 14, 124, 65, và 67 Hình 2.9: Các bước di chuyển đầu đọc theo thuật tốn FCFS 2.1.5.2 Thuật tốn SSTF (shortest-seek-time-first) Thuật tốn sẽ di chuyển đầu đọc lần lượt đến các khối cần đọc theo vị trí gần với vị trí hiện hành của đầu đọc nhất. Ví dụ cần đọc các khối như sau: 98, 183, 37, 122, 14, 124, 65, và 67. Giả sử hiện tại đầu đọc đang ở vị trí 53, thuật tốn sẽ dời đầu đọc lần lượt đi qua các khối 53, 65, 67, 37, 14, 98, 122, 124 và 183. .EDU.VN Hình 2.10: Các bước di chuyển đầu đọc theo thuật tốn SSTF 22
23. 2.1.5.3 Thuật tốn SCAN Thuật tốn sẽ di chuyển đầu đọc về một phía của đĩa và từ đĩ di chuyển qua phía kia. Ví dụ cần đọc các khối như sau: 98, 183, 37, 122, 14, 124, 65, và 67. Giả sử hiện tại đầu đọc đang ở vị trí 53, đầu đọc lần lượt đi qua các khối: 53, 37, 14, 65, 67, 98, 122, 124 và 183 Hình 2.11: Các bước di chuyển đầu đọc theo thuật tốn SCAN 2.1.5.4 Thuật tốn C-SCAN Thuật tốn này tương tự như thuật tốn SCAN, chỉ khác là khi nĩ di chuyển đến một đầu nào đĩ của đĩa, nĩ sẽ lập tức trở về đầu bắt đầu của đĩa. Lấy lại ví dụ trên, khi đĩ thứ tự truy xuất các khối sẽ là 53, 65, 67, 98, 122, 124, 183, 14, 37 Hình 2.12: Các bước di chuyển đầu đọc theo thuật tốn C-SCAN Thuật tốn SCAN và C-SCAN thích hợp cho những hệ thống phải truy xuất dữ liệu khối lượng lớn. Thuật tốn lập lịch phụ thuộc vào số khối và kiểu khối cần truy xuất, ví dụ nếu số khối cần truy xuất là liên tục thì FCFS là thuật tốn tốt. 2.1.6 Hệ số đan xen và Ram Disks * Hệ số đan xen (Interleave) Bộ điều khiển đĩa phải thực hiện hai chức năng là đọc/ghi dữ liệu và chuyển dữ liệu vào hệ thống. Để đồng bộ hai chức năng này, các sector được đánh số sao cho các sector cĩ số hiệu liên tiếp nhau khơng nằm kế bên nhau mà cĩ một khoảng cách, khoảng cách này được xác định bởi quá .EDU.VNtrình format đĩa và gọi là hệ số đan xen. Hình 2.13: (a) interleave=0, (b) interleave=1, (c) interleave=2 23
24. Ví dụ giả sử hệ thống cĩ 17 sector/track, và interleave = 4 thì các sector được bố trí theo thứ tự như sau: 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Cách đọc lần lượt như sau : Lần 1: 1, 2, 3, 4, 5 Lần 2: 6, 7, 8, 9, 10 Lần 3: 11, 12, 13, 14, 15 Lần 4: 16, 17 Như vậy sau bốn lần thứ tự các sector đọc được vẫn là từ 1 đến 17 * Ram disk: Hệ điều hành cĩ thể dùng một phần của bộ nhớ chính để lưu trữ các khối đĩa, phần bộ nhớ này gọi là Ram Disk . Ram Disk cũng được chia làm nhiều khối, mỗi khối cĩ kích thước bằng kích thước của khối trên đĩa. Khi driver nhận được lệnh đọc/ghi khối, sẽ tìm trong bộ nhớ Ram Disk vị trí của khối, và thực hiện việc đọc/ ghi trong đĩ thay vì từ đĩa . RAM disk cĩ ưu điểm là cho phép truy xuất nhanh, khơng phải chờ quay hay tìm kiếm, thích hợp cho việc lưu trữ những chương trình hay dữ liệu được truy xuất thường xuyên. 2.2 QUẢN LÝ HỆ THỐNG TẬP TIN 2.2.1 Đĩa cứng, tập tin, thư mục 2.2.1.1 Đĩa cứng (hard disk) Đĩa cứng được định dạng thành các vịng trịn đồng tâm gọi là rãnh (track), mỗi rãnh được chia thành nhiều phần bằng nhau gọi là cung (sector). Một khối (cluster) gồm một hoặc nhiều cung và dữ liệu được đọc/ghi theo đơn vị khối. Việc sử dụng đơn vị khối để tăng hiệu quả trong việc đọc/ghi và giảm chi phí quản lý số địa chỉ trên đĩa. Ngồi ra khi đĩa cứng lớn, cĩ thể chia thành nhiều phân vùng (partition), mỗi phân vùng gồm một số từ trụ (cyclinder) liên tiếp. Một từ trụ là tập hợp các rãnh cùng bán kính. sector track Hình 2.14: mơ hình tổ chức đĩa .EDU.VN2.2.1.2 File (tập tin) File là một tập hợp thơng tin được đặt tên và lưu trữ trên đĩa. File là đơn vị lưu trữ thơng tin nhỏ nhất trên đĩa của hệ điều hành. File cĩ thể lưu trữ chương trình hay dữ liệu, file cĩ thể là dãy tuần tự các byte khơng cấu trúc hoặc cĩ cấu trúc dịng (kết thúc bằng kí tự enter), hoặc cấu trúc mẫu tin cĩ chiều dài cố định hay thay đổi. Cấu trúc file do hệ điều hành hoặc chương trình qui định. File cĩ thể truy xuất tuần tự (đọc các byte theo thứ tự từ đầu file), hoặc truy xuất ngẫu nhiên (đọc/ghi tại một vị trí bất kỳ trong file). 24
25. * Thuộc tính file (file attributes) Thuộc tính của file là các thơng tin liên quan đến file, số thuộc tính của file tùy theo hệ điều hành, nhưng thường thì file cĩ các thuộc tính sau: + Tên file (file name) Tên file dùng để phân biệt file này với file khác, UNIX phân biệt tên file chữ thường với tên file chữ hoa nhưng WINDOWS thì khơng phân biệt. Trong UNIX tên file cĩ thể cĩ nhiều phân cách (ví dụ prog.c.Z), WINDOWS chỉ cĩ một phân cách. Hệ điều hành dùng phần mở rộng để nhận dạng kiểu của file và các thao tác cĩ thể thực hiện trên kiểu file đĩ, ví dụ phần mở rộng là *.exe, *.com thì hệ điều hành hiểu là file kiểu nhị phân cĩ thể thực thi nhưng nếu khơng thực thi được thì là do cấu trúc file khơng đúng qui định của file *.exe, *.com. + Kiểu file (file type) Cĩ hai loại file là file văn bản và file nhị phân. File văn bản chứa các dịng văn bản cuối dịng cĩ ký tự xuống dịng (kí tự enter). File nhị phân gồm dãy các byte, cĩ cấu trúc tùy theo chương trình tạo ra file. Ví dụ file .com, .exe, .wav, .bmp, . hệ điều hành chỉ thực thi được file .com, .exe nếu nĩ cĩ cấu trúc đúng qui định. + Vị trí file: Danh sách các khối (cluster) trên đĩa đã cấp cho file. + Kích thước file: Kích thước hiện thời, kích thước tối đa của file tính bằng bytes/words/blocks, + Ngày giờ tạo file, người tạo file: Ngày, giờ tạo file; ngày, giờ cập nhật file gần nhất; ngày, giờ sử dụng file sau cùng, người tạo file. + Loai file: file ẩn, chỉ đọc, hệ thống, lưu trữ, file/thư mục + Bảo vệ file: Dùng account (username, password), owner/creator hoặc dùng quyền đã cấp cho user, group trên file hay thư mục, gồm các quyền sau: quyền đọc (Read), ghi (Write), xĩa (Delete), thực thi (Execute), liệt kê (List), thêm (Append) Thuộc tính Ý nghĩa Protection Ai cĩ thể truy xuất file và bằng cách nào Password Mật khẩu cần cĩ để truy xuất file Creator ID của người tạo file Owner Người sở hữu hiện tại Read-only flag 0: cho phép đọc/ghi; 1: chỉ cho phép đọc Hidden flag 0: bình thường; 1: khơng xuất hiện khi liệt kê System flag 0: file bình thường, 1: file hệ thống Archive flag 0: đã backup, 1: cần được backup. ASCII/binary flag 0: file dùng mã ASCII, 1: file dùng mã nhị phân Random Access flag 0: chỉ cho phép truy xuất tuần tự; 1: cho phép truy xuất ngẫu Temporary flag 0: bình thường, 1: file bị hủy khi tiến trình kết thúc Lock flags 0 : khơng khĩa, khác 0: khĩa Record length Số bytes trong một mẫu tin Key position offset của khĩa trong từng mẫu tin .EDU.VNKey length Số byte của khĩa trong mẫu tin Creation time Ngày giờ tạo file Time of last access Ngày giờ truy xuất file gần nhất Time of last change Ngày giờ cập nhật nội dung file gần nhất Current size Số byte của file Maximum size Số bytes tối đa cho phép của file Hình 2.15: Một số thuộc tính của file/thư mục 25
26. * Các thao tác trên file Hệ điều hành cần cung cấp các các lời gọi hệ thống (system call) xử lý file như là: tạo/xĩa/mở/đĩng/đọc/ghi/thêm/dời con trỏ file/lấy thuộc tính/đặt thuộc tính/đổi tên file, + Tạo file (create): Ghi một mục chứa thơng tin file vào cấu trúc thư mục và tìm một khối trống cấp cho file. + Xĩa file (delete): Tìm tên file trong cấu trúc thư mục, giải phĩng tất cả khối đĩa mà file chiếm giữ, xố mục tương ứng trong cấu trúc thư mục. + Mở file (open): Khi lần đầu tiên file được truy xuất, thơng tin về file được đọc từ cấu trúc thư mục và lưu vào bảng open-files trong bộ nhớ. Nếu file chưa đĩng, thì những lần truy xuất sau sẽ khơng phải tìm thơng tin về file trong cấu trúc thư mục nữa mà lấy trong bảng open-files. Thao tác mở file sẽ trả về chỉ mục trong bảng open-files + Đĩng file (close): Ghi mục tương ứng trong bảng open-files vào cấu trúc thư mục, và hủy mục này trong bảng open-files. + Đọc file (read): Tìm tên file trong cấu trúc thư mục, biết được vị trí lưu trữ file, đọc file vào bộ nhớ, dùng một con trỏ đọc (read pointer) để ghi nhận vị trí cho lần đọc kế tiếp. + Ghi file (write): Tìm tên file trong cấu trúc thư mục, lấy được số hiệu khối nhớ đầu tiên cấp phát cho file, ghi dữ liệu của file vào vị trí này, dùng một con trỏ ghi (write pointer) để ghi nhận vị trí cho lần ghi kế tiếp. + Ghi thêm vào cuối (append) + Lấy thuộc tính (get attribute) + Đặt thuộc tính (set attribute) + Đổi tên file (rename) 2.2.1.3 Cấu trúc thư mục (Directory Structure) * Khái niệm Cấu trúc thư mục là cấu trúc dùng để quản lý tất cả các file trên đĩa. Cấu trúc thư mục cũng được ghi trên đĩa và gồm nhiều mục (Directory Entry), mỗi mục lưu thơng tin của một file. Thơng thường thơng tin file gồm cĩ thuộc tính file và danh sách các số hiệu khối đĩa lưu trữ file. Khi một file được truy xuất, hệ điều hành tìm tên file trong cấu trúc thư mục, nếu tìm thấy sẽ lấy thuộc tính và các số hiệu khối lưu trữ file đưa vào một bảng trong bộ nhớ (bảng open-files), các lần sau khi truy xuất file hoặc thay đổi thơng tin file thì khơng cần truy xuất đĩa mà truy xuất bảng open-files trong bộ nhớ chính và sẽ nhanh hơn nhiều. Hệ điều hành cũng cần cung cấp các lời gọi hệ thống để thao tác trên thư mục tương tự như đối với file. Các thao tác trên thư mục cĩ thể là: Create, Delete, Open, Close, Read, Rename, Link, Unlink, mục 0 mục 1 . mục n TenFile ThuocTinh ViTriLuuTru Cấu trúc thư mục Một mục trong cấu trúc thư mục .EDU.VN Dir Structure Files F 1 F 2 F 3 F4 F n Hình 2.16: mơ hình cấu trúc thư mục, mỗi mục trong cấu trúc thư mục quản lý một file hoặc thư mục con 26
27. * Cấu trúc thư mục + Thư mục một cấp: (Single Level Directory) Cấu trúc thư mục sẽ chứa thuộc tính của tất cả các file của tất cả người dùng. Cấu trúc này đơn giản nhưng gây ra khĩ khăn do đặt tên file khơng được trùng nhau và người sử dụng khơng thể phân nhĩm cho file cũng như tìm kiếm chậm khi số lương file nhiều. Hình 2.17: cấu trúc thư mục một cấp + Thư mục hai cấp: (Two Level Directory) Sự bất tiện chủ yếu của thư mục một cấp là nhầm lẫn về tên file giữa những người dùng. Giải pháp là tạo thư mục riêng (user file directory:UFD) cho mỗi user. Mỗi UFD cĩ cấu trúc giống nhau nhưng chỉ quản lý file của một user, như vậy các user cĩ thể cĩ file cùng tên nhưng user chỉ được truy xuất các file trong thư mục của user đĩ. Giải pháp này tìm kiếm file nhanh hơn, nhưng vẫn khơng cĩ khả năng nhĩm file. Trong hình 2.5, user1 muốn truy xuất file test thì sử dụng đường dẫn: user1/test. Hình 2.18: cấu trúc thư mục hai cấp + Thư mục đa cấp: (Tree-Structured Directory) Cĩ một thư mục gọi là thư mục gốc (root directory) và trong đĩ cĩ các thư mục con. Mỗi user cĩ thể tạo những thư mục con riêng, trong mỗi thư mục con chứa file và cĩ thể chứa thư mục con khác. Cấu trúc này cho phép user cĩ thể truy xuất đến file của user khác thơng qua quyền được cấp và cho phép tìm kiếm hiệu quả hơn, cũng như cĩ khả năng phân nhĩm file. .EDU.VN Hình 2.19: cấu trúc thư mục đa cấp 27
28. Hệ điều hành cĩ thể chia đĩa cứng thành nhiều phân vùng (partition), mỗi phân vùng gồm nhiều từ trụ (cyclinder) liên tiếp, hoặc tập hợp nhiều đĩa cứng thành một phân vùng. Mỗi phân vùng sẽ cĩ cấu trúc thư mục riêng để quản lý các tập tin trong phân vùng đĩ. Hình 2.20: tổ chức phân vùng đĩa * Bảng thư mục (Directory Table) Bảng thư mục là một dạng cài đặt bằng dãy một chiều của cấu trúc thư mục (Directory Structure). Bảng thư mục cĩ nhiều mục (directory entry), mỗi mục lưu trữ thơng tin của một file/thư mục, thơng tin file gồm thuộc tính của file và địa chỉ trên đĩa của tồn bộ file hoặc số hiệu của khối đầu tiên chứa file hoặc là số I-node của file. Mỗi đĩa cĩ một bảng thư mục gọi là bảng thư mục gốc, cài đặt ở phần đầu của đĩa và cĩ thể cĩ nhiều bảng thư mục con. Ví dụ: + Mỗi mục trong bảng thư mục của hệ điều hành MSDOS/WINDOWS (FAT) chỉ lưu số hiệu khối đầu tiên của mỗi file/thư mục. Khi đĩ để biết số hiệu các khối cịn lại của file/thư mục, hệ điều hành sẽ dùng bảng cấp phát file (bảng FAT). Hình 2.21: cấu trúc một mục trong bảng thư mục của MSDOS/WINDOWS (FAT) + Mỗi mục trong bảng thư mục của hệ điều hành CP/M chứa tất cả các số hiệu khối chứa file/thư mục, khi đĩ khơng cần dùng bảng cấp phát file (bảng FAT) .EDU.VN Hình 2.22: cấu trúc một mục trong bảng thư mục của CP/M 28
29. + Mỗi mục trong bảng thư mục của hệ điều hành UNIX lưu số hiệu I-node Hình 2.23: cấu trúc một mục trong bảng thư mục của UNIX 2.2.2 Cài đặt hệ thống quản lý file Việc cài đặt hệ thống quản lý file phụ thuộc vào việc hệ điều hành chọn phương pháp cấp phát khối nhớ cho file là liên tục hay khơng liên tục. 2.2.2.1 Cấp phát khối nhớ liên tục Khi cấp phát khối nhớ liên tục, để cài đặt hệ thống quản lý file, hệ điều hành chỉ cần dùng bảng thư mục, mỗi mục trong bảng thư mục ngồi những thuộc tính thơng thường của file, cần cĩ thêm thơng tin về số hiệu khối bắt đầu (start) và số khối đã cấp cho file (length). Phương pháp này dễ cài đặt, dễ thao tác vì tồn bộ file được đọc từ các khối liên tiếp trên đĩa khơng cần định vị lại, nhưng cĩ khuyết điểm là file khơng thể phát triển và cĩ thể gây ra lãng phí do sự phân mảnh trên đĩa. Hình 2.24: Bảng thư mục trong mơ hình cấp phát liên tục 2.2.2.2 Cấp phát khối nhớ khơng liên tục Khi cấp phát khối nhớ liên tục, để cài đặt hệ thống quản lý file, hệ điều hành sử dụng bảng thư mục và cần phải sử dụng thêm một trong các cấu trúc sau: danh sách liên kết, bảng chỉ mục, bảng cấp phát file, bảng I-Nodes. .EDU.VN 2.2.2.2.1 Danh sách liên kết: Mỗi mục trong bảng thư mục chứa số hiệu của khối đầu tiên (start) và số hiệu của khối kết thúc (end), mỗi khối trên đĩa dành một số byte đầu hoặc cuối (thường là 4 bytes) để lưu số hiệu khối kế tiếp của file, phần cịn lại của khối sẽ lưu dữ liệu của file. Phương pháp này khơng bị lãng phí do phân mảnh ngoại vi, nhưng truy xuất ngẫu nhiên chậm và rất khĩ bảo vệ các số hiệu khối của File. 29
30. Hình 2.25: mơ hình cấp phát khơng liên tục, sử dụng danh sách liên kết 2.2.2.2.2 Bảng chỉ mục (index table): Mỗi file cĩ một bảng chỉ mục chiếm một hoặc vài khối, bảng chỉ mục chứa tất cả các số hiệu khối của một file. Khi đĩ một mục trong bảng thư mục sẽ lưu số hiệu khối chứa bảng chỉ mục của file. Phương pháp này dễ bảo vệ các bảng chỉ mục, nghĩa là bảo vệ được các số hiệu khối của file nhưng tốn nhiều khối nhớ để lưu các bảng chỉ mục. Ví dụ đĩa cứng cĩ dung lượng 32 GB, kích thước 1 khối là 512 Bytes. Hỏi kích thước một bảng chỉ mục là bao nhiêu nếu muốn quản lý file cĩ kích thước lớn nhất là 256K? 32 GB=25 x 210 x 210 KB = 225 KB = 216 khối => cĩ 216 địa chỉ trên đĩa => mỗi phần tử bảng chỉ mục cần 2 byte. File kích thước 256KB = 256 x 1024 byte = 512 khối => bảng chỉ mục cần cĩ 512 phần tử => một bảng chỉ mục chiếm hai khối! Hình 2.26: mơ hình cấp phát khơng liên tục, sử dụng bảng chỉ mục .EDU.VN 2.2.2.2.3 Bảng cấp phát file (FAT: File Allocation Table) Nếu mỗi mục trong bảng thư mục chỉ chứa số hiệu của khối đầu tiên, thì số hiệu các khối cịn lại của file sẽ được lưu trong một bảng gọi là bảng cấp phát file (bảng FAT). Phương pháp này dễ bảo vệ các số hiệu khối đã cấp cho file, truy xuất file ngẫu nhiên dễ dàng hơn, kích thước file dễ mở rộng nhưng bảng FAT bị giới hạn bởi kích thước bộ nhớ dành cho nĩ. Đây chính là cách mà hệ điều hành MSDOS, OS/2, Windows (FAT) sử dụng để quản lý File. 30
31. Ví dụ: Giả sử file test.txt được lưu trữ lần lượt ở 3 khối trên đĩa cĩ số hiệu là: 217, 618, 339. Số hiệu khối đầu là 217 ghi trong một mục của bảng thư mục, các số hiệu khối tiếp theo là 618, 339 ghi trong bảng cấp phát file. Hình 2.27: mơ hình cấp phát khơng liên tục, sử dụng bảng FAT Ví dụ: Giả sử file A và file B được cấp phát gồm các khối theo thứ tự sau: file A: 4, 7, 2, 10, 12 ; file B: 6, 3, 11, 14. Khi đĩ trong bảng thư mục sẽ cĩ một mục lưu tên file A và số hiệu khối đầu của file A là 4. Tương tự cĩ một mục lưu tên file B và số hiệu khối đầu của file B là 6. Các số hiệu khối tiếp theo của file A và file B lưu trong bảng cấp phát file (fat) Bảng thư mục: (A, 4) (B, 6) Entry của A Entry của B Bảng FAT : .EDU.VN Hình 2.28: mơ hình cấp phát khơng liên tục, sử dụng bảng FAT, cĩ hai file 31
32. 2.2.2.2.4 Bảng I-nodes: Mỗi file được quản lý bằng một cấu trúc gọi là I-node, mỗi I-node gồm hai phần: phần thứ nhất lưu trữ thuộc tính file, phần thứ hai gồm 13 phần tử: 10 phần tử đầu chứa 10 số hiệu khối đầu tiên của file, phần tử thứ 11 chứa số hiệu khối chứa bảng single, phần tử thứ 12 chứa số hiệu khối chứa bảng double, phần tử thứ 13 chứa số hiệu khối chứa bảng triple. Trong đĩ mỗi phần tử của bảng triple chứa số hiệu khối chứa bảng double, mỗi phần tử của bảng double chứa số hiệu khối chứa bảng single và mỗi phần tử của bảng single chứa số hiệu khối dữ liệu tiếp theo cấp cho file. Ghi chú: Hệ điều hành Unix sử dụng cấu trúc này và số phần tử của phần thứ hai, khơng nhất thiết là 13 mà cĩ thể thay đổi tùy phiên bản của UNIX Hình 2.29: cấu trúc một I-node trong bảng I-nodes * Phương pháp tổ chức quản lý đĩa bằng I-nodes: + MBR(Master Boot Record): là sector đầu tiên chứa thơng tin về đĩa. + Partion Table: bảng phân vùng chứa các thơng tin về mỗi phân vùng. Một phân vùng được tổ chức thành các phần sau: boot block, super block, free space mgmt, i- nodes, root dir, files and directories. Trong đĩ I-nodes là bảng I-nodes gồm nhiều mục, mỗi mục gọi là một i-node, chứa một cấu trúc i-node ghi thơng tin của một file. Mỗi mục của bảng thư mục gốc (root dir) ghi tên file và số hiệu i-nodes của file. Phương pháp này tương đối linh động và hiệu quả khi qủan lý những hệ thống file lớn. .EDU.VN Hình 2.30: mơ hình cấp phát khơng liên tục, sử dụng bảng I-nodes tổng quát 32
33. Ví dụ hệ điều hành muốn đọc file /usr/ast/mbox, trước tiên tìm tên thư mục “usr” trong bảng thư mục gốc (root dir), và nhận thấy thư mục “usr” cĩ i-nodes là 6. Tiếp theo truy xuất phần tử i-node thứ 6 trong bảng i-nodes, lấy được số hiệu khối đầu của “usr” là 132, khối này sẽ chứa bảng thư mục con (sub dir) của “usr”. Tiếp theo tìm tên thư mục “ast” trong bảng thư mục con của “usr”, và tìm được thư mục “ast” cĩ i-nodes là 26. Tiếp theo truy xuất phần tử i-node thứ 26 trong bảng i-nodes, lấy được số hiệu khối đầu của “ast” là 406, khối này sẽ chứa bảng thư mục con của “ast”. Tiếp theo tìm tên file “mbox” trong bảng thư mục con này, và tìm được file “mbox” cĩ i-nodes là 60. Truy xuất phần tử i-node thứ 60 trong bảng i-nodes, lấy được các số hiệu khối của file “mbox”. Hình 2.31: mơ hình cấp phát khơng liên tục, sử dụng bảng I-nodes chi tiết 2.2.3. Quản lý các khối trống Cĩ hai phương pháp mà hệ điều hành thường sử dụng để quản lý các khối trống là sử dụng danh sách liên kết hoặc vector bit. 2.2.3.1 Danh sách liên kết Mỗi nút trong danh sách liên kết (dslk) là một khối chứa một bảng gồm các số hiệu khối trống, phần tử cuối của bảng lưu số hiệu khối tiếp theo trong danh sách. Ví dụ: Giả sử khối đầu tiên trong dslk là khối 2. Trong khối 2 lưu các số 75, 53, 70, 59 là các số hiệu khối trống, các khối 3 là khối chứa bảng các số hiệu khối trống tiếp theo Hệ điều hành chỉ cần biết số hiệu khối đầu tiên của danh sách liên kết. 0 1 2 3 4 0 1 2 3 4 75 53 70 59 3 35 47 79 39 4 Khối 2 Khối 3 Ví dụ: Một đĩa 20M, dùng khối cĩ kích thước 1 K. Để quản lý đĩa này, nếu đĩa hồn tồn trống .EDU.VNthì DSLK cần bao nhiêu khối (số nút tối đa của dslk)? Giải: 10 15 20M= 20x 2 khối ~ 2 khối => cần dùng 16 bit=2 byte để lưu một số hiệu khối => 1 khối=1024 byte lưu được 511 số hiệu khối trống 10 => để quản lý đĩa cĩ 20M hồn tồn trống, dslk cần 20x 2 / 511 ~ 40 khối ! 33
34. Nhận xét: Tốn khá nhiều khối nhớ cho dslk nếu đĩa hồn tồn trống, nhưng sẽ ít tốn khối nhớ cho dslk nếu đĩa gần đầy. Hình 2.32: Quản lý danh sách các khối trống sử dụng danh sách liên kết. Ví dụ: Giả sử khối đĩa 1KB và một sơ hiệu khối đĩa là 32 bit thì một khối đĩa cĩ thể ghi được 256 -1 số hiệu khối đĩa trống Hình 2.33: Quản lý danh sách các khối trống sử dụng danh sách liên kết và vector bit. 2.2.3.2 Dùng vector bit (dãy bít) Bit thứ i = 1 là khối thứ i trống, bit thứ i = 0 là khối thứ i đã sử dụng. Vector bit được lưu trên một hoặc nhiều khối đĩa, khi cần sẽ đọc vào bộ nhớ để xử lý nhanh. Vector bit ít tốn khối nhớ hơn là .EDU.VNdslk nhưng kích thước vector bit là cố định và hệ điều hành cần đồng bộ vector bit trong bộ nhớ và vector bit trên đĩa. Ví dụ: xét lại ví dụ trên, nếu dùng vector bit, hãy tính kích thứơc vector bit. HD: Đĩa 20M cĩ 20 x 210 khối nên kích thước vector bit là 20 x 210 bit = 20 x 210 /8/ 210 KB ~ 3 khối. 34
35. 2.2.4. Quản lý sự an tồn của hệ thống tập tin 2.2.4.1 Quản lý khối bị hỏng + Dùng phần mềm: dùng một file chứa các danh sách các khối hỏng. + Dùng phần cứng: dùng một sector trên đĩa để lưu giữ danh sách các khối bị hỏng. Khi bộ kiểm sốt đĩa thực hiện lần đầu tiên, nĩ đọc danh sách khối bị hỏng vào bộ nhớ, từ đĩ khơng cho truy cập những khối hỏng. 2.2.4.2 Sao lưu file (Backup) File trên đĩa mềm được sao lưu bằng cách chép lại tồn bộ qua một đĩa khác. Dữ liệu trên đĩa cứng nhỏ thì được sao lưu trên các băng từ. Đối với đĩa cứng lớn, việc sao lưu cĩ thể tiến hành như sau: chia đĩa cứng làm hai phần một phần chứa dữ liệu gốc và một phần chứa bản sao. Mỗi khi thực hiện sao lưu, phần dữ liệu gốc sẽ được chép sang phần sao lưu. Hình 2.34: sao lưu dữ liệu 2.2.5 Giới thiệu một số hệ thống tập tin 2.2.5.1 Hệ thống tập tin của MSDOS/Windows (FAT) Hệ điều hành MSDOS hoặc Windows (sử dụng hệ thống FAT) sẽ quản lý hệ thống tập tin thơng qua ba cấu trúc sau: Boot Sector, bảng FAT, bảng ROOT DIR. + Boot sector Ở sector đầu tiên, track 0, side 0 của đĩa mềm, đối với đĩa cứng thì vị trí này là bảng partition, rồi mới tới boot sector của partition thứ nhất, đối với các partition khác, boot sector là sector đầu tiên. Boot sector chứa bảng tham số đĩa BPB (Bios Parameter Block) và chứa đoạn mã boot dùng để nạp các file hệ thống, boot sector hợp lệ phải cĩ giá trị AA55 ở offset 1FE. Trên máy IBM PC sau khi thực hiện thao tác POST (Power On Self Test), ROM BIOS tìm boot sector hợp lệ, đọc boot .EDU.VNsector vào địa chỉ 0X7C00, gán CS=0000h, IP=7C00h và cho thực thi lệnh đầu tiên trong boot sector (lệnh JMP). Boot sector cĩ cấu trúc như sau: 35
36. Offset(hex) Size(byte) Content Giải thích 00 3 JMP Lệnh nhảy đến đầu đoạn mã boot 03 8 Version Phiên bản hệ điều hành 0B 2 SectSiz số byte /một sector, thường là 512 (đây là bắt đầu của BPB) 0D 1 ClustSize số sector / một cluster (khác 0) 0E 2 ResSecs số sector dành riêng trước bảng FAT, tính luơn boot sector (đối với FAT12, FAT16 =1, FAT32=20h) 10 1 FatCnt số bảng FAT (thường là 2) 11 2 RootSiz Số mục trong bảng ROOT DIR 13 2 TotSecs Tổng số sector trên đĩa hay trên một partition ( 65535) 24 4 BigFatSize Số sector /một bảng FAT (>65535) 1D (kết thúc BPB) 1E đầu đoạn mã boot 1FF cuối đoạn mã boot Hình 2.35: Cấu trúc boot sector. + Bảng FAT Sau boot sector là bảng FAT (File Allocation Table), thường cĩ hai bảng FAT để an tồn. Mỗi mục của FAT quản lý một khối (cluster) dữ liệu ( khối dữ liệu được đánh số bắt đầu từ 2). Hai mục đầu tiên của bảng FAT chứa thơng tin mơ tả loại đĩa. Kích thước khối được lưu trong boot sector thơng thường từ 1 đến 8 sector. Cĩ ba loại FAT là FAT 12 và FAT 16, FAT 32. FAT 12 (mỗi mục trong bảng FAT12 cĩ kích thước là 12 bit) cĩ thể quản lý được 212 = 4096 khối, FAT 16 cĩ thể quản lý 216 = 64 K khối, FAT 32 cĩ thể quản lý 232 =4G khối trên một partition. Các giá trị .EDU.VNcĩ thể cĩ trong một entry của bảng FAT. (0)000 Cluster cịn trống (0)002 - (F)FEF Cluster chứa dữ liệu của File, giá trị này là số hiệu cluster kế. (F)FF0 - (F)FF6 Dành riêng, khơng dùng 36
37. (F)FF7 Cluster hỏng (F)FF8 - (F)FFF Cluster cuối cùng của chuỗi (kết thúc file) Hình 2.36: Cấu trúc một mục (entry) trong bảng fat. + Bảng ROOT DIR (bảng thư mục gốc) Bảng ROOT DIR nằm ngay sau FAT, và mỗi mục của bảng DIR là 32 byte. Khi hệ thống mở một File/ thư mục, MS-DOS tìm tên File/thư mục trong bảng ROOT DIR, lấy số hiệu khối đầu đã cấp cho file/thư mục và tìm các số hiệu khố9i tiếp theo trong bảng FAT. Boot sector Bảng FAT1 Bảng FAT2 Bảng DIR DATA Kích thước Thuộc tính 8 byte Tên File 3 byte Phần mở rộng 1 byte Thuộc tính : A – D – V – S - H - R 10 byte Dành riêng để sử dụng sau này. 2 byte Giờ : 5 bit cho giờ, 6 bit cho phút, 5 bit cho giây (thieu 1, nên lưu đơn vị 2 giây) 2 byte Ngày : 7 bit cho năm (từ 1980), 4 bit cho tháng, 5 bit cho ngày. 2 byte Số hiệu khối đầu tiên của file 4 byte Kích thước File Hình 2.37: Cấu trúc một mục trong bảng ROOT DIR/ SUB DIR Giá trị của byte thuộc tính: 1 : File chỉ đọc (Read Only) 2 : File ẩn (Hidden) .EDU.VN4 : File hệ thống (System) 8 : nhãn đĩa (Volume) 16 : thư mục con (Directory) 32 : File chưa được sao lưu (Archive) 37
38. Ví dụ: Xét đĩa 1.4MB, được format dưới hệ điều hành MS-DOS/WINDOWS (FAT12) gồm cĩ 2880 sector (1.4MB=>1.4*1024*1024/512=2880 sector), và 1 khối (cluster) = 1 sector nên mỗi mục của bảng FAT chỉ cần 12 bit. Sector đầu tiên là boot sector, bao gồm bảng tham số vật lý của đĩa và chương trình khởi động của hệ điều hành. 18 sector tiếp theo là FAT (FAT12), gồm 2 bảng, mỗi bảng 9 sector (cĩ 3072 mục, nếu 8 sector thì khơng đủ để quản lý 2880 khối). Ba bytes đầu tiên của mỗi bảng FAT lưu số hiệu loại đĩa (240, 255, 255). 14 sector kế tiếp chứa bảng thư mục gốc (bảng ROOT DIR). Các sector cịn lại dùng để lưu dữ liệu, cluster đánh số từ 2. Số sector 1 9 9 14 Cịn lại Lưu trữ Boot sector FAT12 FAT12 DIR DATA Cấu trúc một mục trong bảng ROOT DIR Byte 0-7 8-10 11 12-21 22-23 24-25 26-27 28-31 Lưu Tên Phần mở ADVSHR Dành Giờ Ngày Số hiệu Kích trữ File rộng riêng khối đầu thước File Bảng DIR= 14 sector = 7168 byte = 224 entry (mỗi entry 32 byte), 1 sector=16 entry Đĩa 1.44MB ở thư mục gốc cĩ tối đa 224 file hoặc thư mục con. Nếu file cĩ kích thứơc file =0 thì số hiệu khối đầu = 0. Kí tự đầu của tên file cĩ giá trị là 0 (trống), dấu chấm (dành riêng cho DOS), 0xE5 (file đã bị xĩa: khi xĩa file, DOS sẽ điền kí tự 0xE5 vào kí tự đầu của file). + Cấu trúc bảng FAT Byte 0,1,2 3,4,5 4606,4607 Lưu trữ e0,e1 (số hiệu đĩa) e2,e3 e3070, e3071 Bảng FAT12 = 9 sector = 4608 bytes = 3072 entry (mỗi entry 12 bit) - Đọc/ghi FAT 12 Ví dụ: ghi vào entry 2 giá trị F2Ah và entry 3 giá trị BC5h. Do byte 0,1,2 lưu số hiệu đĩa, nên entry 2 sẽ được ghi vào byte thứ 3,4 và entry 3 sẽ được ghi vào byte thứ 4,5 . Cách ghi như sau: Byte 0 1 2 3 4 5 Giá trị (số hiệu đĩa ) 2A 5F BC unsigned char fat[512*9]; //mảng chứa bảng fat đọc từ đĩa void WriteFat (unsigned new_fat, unsigned k) // ghi giá trị new_fat vào entry thứ k = 2,3, ,3071 { unsigned i=k*3/2; //entry k sẽ được ghi vào byte thứ i và i+1 if (k%2==0)// k chẵn .EDU.VN { //đặt 8 bít cuối của new_fat vào byte thứ i fat[i] = new_fat&0x0FF; //đặt 4 bít cao của new_fat vào 4 bít cuối của byte thứ i+1 fat[i+1] = (fat[i+1]&0xF0) | (new_fat>>8); } else //k lẻ 38
39. { //đặt 8 bít cao vào vào byte thứ i+1 fat[i+1]=new_fat>>4; //đặt 4 bít thấp vào 4 bít cao của byte thứ i fat[i]=((new_fat&0xF) luu vao byte i=10 và i+1=11 9 10 11 AB CD EF (trước khi ghi) AB BD 1A (sau khi ghi) unsigned ReadFat (unsigned k) // Đọc giá trị của entry thứ k (k>=2) { unsigned i=k*3/2; //entry thứ k ở byte thứ i, i+1 unsigned val_fat=(fat[i+1] >4; return val_fat; } - Đọc/ghi giờ, phút, giây time (2 byte)= 5 bit giờ, 6 bit phút, 5 bit giây (thieu 1, nên lưu đơn vị 2 giây) - Ghi : time=(h >1) - Đọc: h=(time>>11); m=(time>>5)&0x3F; s=(time&0x1F) >9) + 1980 ; m=(date>>5)&0xF ; d=date&0x1F ; 2.2.5.2 Hệ thống tập tin của Windows NT Sử dụng hệ thống NTFS, kích thước File tối đa trong NTFS là 232 cluster. Cấu trúc volume của .EDU.VNNTFS như sau: partition boot sector, Master File Table, các file hệ thống, vùng dữ liệu. + Partition boot sector: là sector khởi động của partition (<= 16 sector) gồm các thơng tin về cấu trúc của volume, cấu trúc của hệ thống File và mã nguồn khởi động. + Master File Table (MFT): lưu các thơng tin về tất cả file và thư mục trên volume NTFS này cũng như danh sách các khối trống. MFT được tổ chức thành nhiều dịng, mỗi dịng lưu những 39
40. thuộc tính cho một file hoặc một thư mục trên volume. Nếu kích thước file nhỏ thì tồn bộ nội dung của file được lưu trong dịng này. + Các file hệ thống: cĩ kích thước khoảng 1Mb bao gồm: . MFT2: bản sao của MFT . Log file: thơng tin dùng cho việc phục hồi. . Cluster bitmap: biểu diễn thơng tin lưu trữ của các cluster . Bảng định nghĩa thuộc tính: định nghĩa các kiểu thuộc tính hỗ trợ cho volume. Kiểu thuộc tính Mơ tả Thơng tin chuẩn Bao gồm các thuộc tính truy xuất (chỉ đọc, đọc/ghi, ), nhãn thời gian, chỉ số liên kết Danh sách thuộc tính sử dụng khi tất cả thuộc tính vượt quá 1 dịng của MFT Tên File Mơ tả an tồn thơng tin về người sở hữu và truy cập Dữ liệu Chỉ mục gốc dùng cho thư mục Chỉ mục định vị dùng cho thư mục thơng tin volume như tên version và tên volume Bitmap hiện trạng các dịng trong MFT Hình 2.38: Các kiểu thuộc tính của File và thư mục trong Windows NTFS 2.5.3. Hệ thống file của UNIX Hệ thống File của UNIX thơng thường được cài đặt trên đĩa gồm các khối theo thứ tự sau: khối boot, khối đặc biệt, I-nodes, các khối dữ liệu. + Khối boot: chứa mã khởi động của hệ thống. + Khối super block : chứa thơng tin về tồn bộ hệ thống file, bao gồm: - Kích thước của tồn bộ hệ thống file. - Địa chỉ của khối dữ liệu đầu tiên. - Số lượng khối trống và danh sách khối trống. .EDU.VN- Số lượng I-node trống và danh sách I-node trống. - Ngày super block được cập nhật sau cùng. - Tên của hệ thống file. Nếu khối này bị hỏng, hệ thống file sẽ khơng truy cập được. Cĩ rất nhiều trình ứng dụng sử dụng thơng tin lưu trữ trong super block, vì vậy một bản sao super block được đặt trong RAM để tăng 40
41. tốc độ truy xuất đĩa. Việc cập nhật super block sẽ được thực hiện ngay trong RAM và sau đĩ mới ghi xuống đĩa. Các I-node được đánh số từ 1, mỗi I-node cĩ độ dài là 64 byte và mơ tả cho một file duy nhất, chứa thuộc tính và địa chỉ các khối lưu trữ trên đĩa của file. Tất cả file và thư mục được lưu trữ ở các khối dữ liệu. TĨM TẮT + Thiết bị nhập/xuất cĩ thể phân thành các loại như là thiết bị khối, thiết bị tuần tự, thiết bị khác. Đặc tính của thiết bị nhập/xuất là tốc độ truyền dữ liệu, cơng dụng, đơn vị truyền dữ liệu, cách biểu diễn dữ liệu, tình trạng lỗi + Mỗi thiết bị nhập/xuất cần cĩ bộ điều khiển thiết bị, thiết bị và bộ điều khiển phải tuân theo cùng chuẩn giao tiếp. CPU khơng thể truy xuất trực tiếp thiết bị nhập/xuât mà phải thơng qua bộ điều khiển thiết bị, mỗi bộ điều khiển cĩ một số thanh ghi để liên lạc với CPU + Các chương trình thực hiện nhập/xuất gồm cĩ chương trình nhập/xuất của người dùng, chương trình nhập/xuất độc lập thiết bị, chương trình điều khiển thiết bị. + Hệ thống quản lý nhập/xuất được tổ chức thành 5 lớp: chương trình nhập/xuất của người dùng, chương trình nhập/xuất độc lập thiết bị, chương trình điều khiển thiết bị, chương trình kiểm sốt ngắt, phần cứng. Mỗi lớp cĩ chức năng riêng và cĩ thể giao tiếp với lớp khác. + Cơ chế nhập/xuất: bộ xử lý phát sinh một lệnh I/O đến các thiết bị I/O, sau đĩ chờ cho đến khi thao tác I/O hồn tất rồi mới tiếp tục xử lý, hoặc bộ xử lý phát sinh một lệnh I/O đến các thiết bị I/O, sau đĩ tiếp tục việc xử lý cho tới khi nhận được một ngắt từ thiết bị I/O báo là đã hồn tất nhập/xuất, bộ xử lý tạm ngưng việc xử lý hiện tại để chuyển qua xử lý ngắt, hoặc sử dụng cơ chế DMA + Cơ chế DMA: bộ điều khiển thường được cung cấp thêm khả năng truy xuất bộ nhớ trực tiếp (DMA). Nghĩa là sau khi bộ điều khiển đã đọc tồn bộ dữ liệu từ thiết bị vào buffer của nĩ, bộ điều khiển tự chuyển dữ liệu vào trong bộ nhớ chính. + Cơ chế truy xuất đĩa: đầu đọc được di chuyển đến track thích hợp, và chờ cho đến khi khối cần đọc đến dưới đầu đọc, đọc dữ liệu từ đĩa vào bộ nhớ chính, hệ điều hành cần đưa ra các thuật tốn lập lịch dời đầu đọc sao cho tối ưu. Các thuật tốn lập lịch di chuyển đầu đọc: FCFS, SSTF, SCAN, C-SCAN + Hệ số đan xen: Trên đĩa các sector số hiệu liên tiếp nhau khơng nằm kế bên nhau mà cĩ một khoảng cách nhất định, khoảng cách này được xác định bởi quá trình format đĩa và gọi là hệ số đan xen. Mục đích của hệ số đan xen là để đồng bộ hai thao tác đọc/ghi dữ liệu và chuyển dữ liệu vào hệ thống .EDU.VN+ RAM disk là một phần của bộ nhớ chính để lưu trữ các khối đĩa. RAM disk truy xuất rất nhanh, thích hợp cho việc lưu trữ những chương trình hay dữ liệu được truy xuất thường xuyên. + Đĩa cứng được tổ chức thành các vịng trịn đồng tâm gọi là rãnh (track), mỗi rãnh được chia thành nhiều phần bằng nhau gọi là cung (sector). Một khối (cluster) gồm 1 hoặc nhiều cung và dữ liệu được đọc/ghi theo đơn vị khối. 41
42. + File là một tập hợp các thơng tin được đặt tên và lưu trữ trên đĩa. File cĩ thể lưu trữ chương trình hay dữ liệu, file cĩ thể là dãy tuần tự các byte khơng cấu trúc hoặc cĩ cấu trúc dịng, hoặc cấu trúc mẫu tin cĩ chiều dài cố định hay thay đổi. File cĩ thể truy xuất tuần tự, hoặc truy xuất ngẫu nhiên. + Thuộc tính của file là thơng tin của file, thường cĩ các thuộc tính sau: tên file, kiểu file, vị trí file, kích thước file, ngày giờ tạo file, người tạo file, loai file, bảo vệ file. + Các thao tác trên file gồm cĩ tạo/xĩa/mở/đĩng/đọc/ghi/thêm/dời con trỏ file/lấy thuộc tính/đặt thuộc tính/đổi tên file + Cấu trúc thư mục là cấu trúc dùng để quản lý tất cả các file trên đĩa. Cấu trúc thư mục cũng được ghi trên đĩa và gồm nhiều mục, mỗi mục lưu thơng tin của một file. + Cấu trúc thư mục cĩ các loại sau: thư mục một cấp, thư mục hai cấp, thư mục đa cấp. + Hệ điều hành cĩ thể chia đĩa cứng thành nhiều phân vùng hoặc tập hợp nhiều đĩa cứng thành một phân vùng. Mỗi phân vùng sẽ cĩ cấu trúc thư mục riêng để quản lý các tập tin trong phân vùng đĩ. + Các thao tác trên thư mục tương tự như đối với file và gồm cĩ: Create, Delete, Open, Close, Read, Rename, Link, Unlink, + Bảng thư mục là một dạng cài đặt của cấu trúc thư mục. Bảng thư mục cĩ nhiều mục, mỗi mục lưu trữ thơng tin của một file, thơng tin file gồm thuộc tính của file và địa chỉ trên đĩa của tồn bộ file hoặc số hiệu của khối đầu tiên chứa file hoặc là số I-node của file. Mỗi đĩa cĩ một bảng thư mục gọi là bảng thư mục gốc, cài đặt ở phần đầu của đĩa và cĩ thể cĩ nhiều bảng thư mục con. + Cĩ thể cài đặt hệ thống quản lý file theo phương pháp cấp phát khối nhớ cho file là liên tục hay khơng liên tục. + Để cài đặt hệ thống quản lý file theo phương pháp cấp phát khối nhớ cho file là liên tục, chỉ cần dùng bảng thư mục, mỗi mục trong bảng thư mục ngồi những thuộc tính thơng thường của file, cần cĩ thêm thơng tin về số hiệu khối bắt đầu (start) và số khối đã cấp cho file (length). + Để cài đặt hệ thống quản lý file theo phương pháp cấp phát khối nhớ cho file là khơng liên tục, sử dụng bảng thư mục và sử dụng thêm một trong các cấu trúc sau: danh sách liên kết/bảng chỉ mục/bảng cấp phát file/cấu trúc I-Nodes. - Cấu trúc danh sách liên kết: mỗi mục trong bảng thư mục chứa số hiệu của khối đầu tiên và số hiệu của khối kết thúc , mỗi khối trên đĩa dành một số byte đầu để lưu số hiệu khối kế tiếp của file, phần cịn lại của khối sẽ lưu dữ liệu của file. - Bảng chỉ mục: mỗi file cĩ một bảng chỉ mục chiếm một hoặc vài khối, bảng chỉ mục chứa tất cả các số hiệu khối của một file. Một mục trong bảng thư mục sẽ lưu số hiệu khối chứa bảng chỉ mục của file. - Bảng cấp phát file: nếu mỗi mục trong bảng thư mục chỉ chứa số hiệu của khối đầu tiên, thì số hiệu các khối cịn lại của file sẽ được lưu trong một bảng gọi là bảng cấp phát file. - Cấu trúc I- node: mỗi file được quản lý bằng một cấu trúc gọi là cấu trúc I-node, mỗi I-node gồm hai phần: phần thứ nhất lưu trữ thuộc tính file, phần thứ hai gồm 13 phần tử: 10 phần tử đầu chứa 10 số hiệu khối đầu tiên của file, phần tử thứ 11 chứa số hiệu khối chứa bảng single, phần tử thứ 12 chứa số .EDU.VNhiệu khối chứa bảng double, phần tử thứ 13 chứa số hiệu khối chứa bảng triple. Trong đĩ mỗi phần tử của bảng triple chứa số hiệu khối chứa bảng double, mỗi phần tử của bảng double chứa số hiệu khối chứa bảng single và mỗi phần tử của bảng single chứa số hiệu khối dữ liệu tiếp theo cấp cho file. + Để quản lý các khối trống phương pháp thường dùng là danh sách liên kết hoặc vector bit. 42
43. Danh sách liên kết: mỗi nút là một khối chứa một bảng gồm các số hiệu khối trống, phần tử cuối của bảng lưu số hiệu khối tiếp theo trong danh sách. Vector bit: Bit thứ i = 1 là khối thứ i trống, = 0 là đã sử dụng. Vector bit được lưu trên một hoặc nhiều khối đĩa, khi cần sẽ đọc vào bộ nhớ để xử lý nhanh. + Quản lý khối bị hỏng cĩ thể dùng phần mềm: dùng một file chứa các danh sách các khối hỏng. Hoặc dùng phần cứng: dùng một sector trên đĩa để lưu giữ danh sách các khối bị hỏng. CÂU HỎI VÀ BÀI TẬP 1. Nêu các loại thiết bị nhập/xuất 2. Trình bày đặc tính của thiết bị nhập/xuất 3. Bộ điều khiển thiết bị nhập/xuất (I/O controller) là gì? 4. Nêu các chương trình thực hiện nhập/xuất 5. Nêu cách tổ chức hệ thống nhập/xuất 6. Nêu cơ chế nhập/xuất 6. Trình bày cơ chế DMA 7. Nêu cơ chế truy xuất đĩa 8. Trình bày các thuật tốn lập lịch di chuyển đầu đọc 9. Trình bày hệ số đan xen 10. Nêu khái niệm Ram Disks 11. Tại sao dữ liệu khơng lưu trữ tại vị trí bất kỳ trên đĩa mà lại lưu trữ trên các rãnh (track)? 12. Nêu lý do tại sao cần phân chia đĩa cứng thành những phân vùng (partiton). Thơng tin về các phân vùng được quản lý, lưu trữ như thế nào? Trên hệ điều hành MS-DOS hoặc windows, mỗi phân vùng cĩ cần một bảng thư mục riêng khơng? tại sao? 13. Mục đích của bảng open-files, bảng open-files lưu trữ những thơng tin nào? 14. Mục đích của bảng thư mục? phân biệt bảng thư mục gốc và bảng thư mục con. 15. Tại sao hệ điều hành CP/M khơng cần bảng cấp phát file (FAT)? 16. Nêu ưu/khuyết điểm của việc cấp phát các khối nhớ liên tục cho file. 17. Nêu ưu/khuyết điểm của việc cấp phát các khối nhớ khơng liên tục cho file. 18. Nêu ưu/khuyết điểm hệ thống quản lý file dùng bảng thư mục và bảng cấp phát file. 19. Nêu ưu/khuyết điểm hệ thống quản lý file dùng cấu trúc I-nodes. 20. Tại sao trong hệ điều hành MS-DOS và hệ điều hành WINDOWS sử dụng FAT, số file hoặc thư mục con trong thư mục gốc bị hạn chế, trong khi số file hoặc thư mục trong thư mụccon lại .EDU.VNkhơng bị hạn chế? 21. Cho dãy byte của FAT12 như sau (bắt đầu từ đầu): 240 255 255 0 64 0 9 112 255 255 143 0 255 255 255 Cho biết những phần tử nào của FAT cĩ giá trị đặc biệt, ý nghĩa của phần tử đĩ. Nếu sửa lại phần tử 5 là FF0 thì dãy byte của FAT12 này cĩ nội dung như thế nào ? 43
44. 22. Biết giá trị(dưới dạng thập phân) trong một buffer (mỗi phần tử 1 byte) lưu nội dung của FAT12 như sau (bắt đầu từ phần tử 0): 240 255 255 255 79 0 5 240 255 247 255 255 Cho biết giá trị của từng phần tử trong FAT (dưới dạng số thập phân) 23. Chép 1 File kích thước là 3220 bytes lên một đĩa 1.44Mb cịn trống nhưng bị hỏng ở sector logic 33. Cho biết giá trị từng byte của Fat (thập phân) từ byte 0 đến byte 14 . 24. Giả sử một đĩa mềm cĩ 2 side, mỗi side cĩ 128 track, mỗi track cĩ 18 sector. Thư mục gốc của đĩa cĩ tối đa là 251 File (hoặc thư mục). Một cluster = 2 sector. Đĩa sử dụng Fat 12. Hỏi muốn truy xuất cluster 10 thì phải đọc những sector nào ? 25. Hiện trạng của FAT12 và RDET (mỗi entry chỉ gồm tên File và cluster đầu tiên)của một đĩa như sau : 240 255 255 247 79 0 6 0 0 255 159 0 10 240 255 255 127 255 VD TXT 3 LT DOC 7 THO DAT 8 Cho biết hiện trạng của FAT12 và RDET sau khi xố File vd.txt và chép vào File bt.cpp cĩ kích thước 1025 bytes ( giả sử 1 cluster = 1 sector) 26. Một File được lưu trên đĩa tại những khối theo thứ tự sau : 20, 32, 34, 39, 52, 63, 75, 29, 37, 38, 47, 49, 56, 68, 79, 81, 92, 106, 157, 159, 160, 162, 163, 267, 269, 271, 277, 278, 279, 380, 381, 482, 489, 490, 499. Vẽ I_node của File này, giả sử mỗi khối chỉ chứa được 3 phần tử. 27. Viết các lệnh nội trú và ngoại trú của MSDOS bằng ngơn ngữ C và chỉ được sử dụng hai hàm đọc/ghi sector sau: int absread(int drive, int nsects, long lsect, void *buffer); int abswrite(int drive, int nsects, long lsect, void *buffer); .EDU.VN TÀI LIỆU THAM KHẢO [1]. Gary J. Nutt, University of Colorado. Centralized And Distributed Operating Systems. Second Edition, 2000. [2]. Robert Switzer. Operating Systems, A Practical Approach. Prentice-Hall International, Inc. 1993. 44
45. [3]. Andrew S. Tanenbaum. Modern Operating Systems. Prentice-Hall International, Inc. Second Edition, 2001. [4]. Abraham Silberschatz & Peter Baer Galvin. Operating System concepts. John Wiley & Sons, Inc. Fifth Edition, 1999. [5]. H. M. Deitel. Operating Systems. Addison-Wesley Inc. Second Edition, 1999. [6] Cẩm nang lập trình hệ thống cho máy vi tính IBM-PC tập 1 và 2, tác giả Michael Tischer. [7]. Trần Hạnh Nhi & Lê Khắc Nhiên Ân & Hồng Kiếm. Giáo trình hệ điều hành (tập 1 & 2). ĐHKHTN 2000. .EDU.VN 45
46. CHƯƠNG 3 QUẢN LÝ TIẾN TRÌNH Chương “QUẢN LÝ TIẾN TRÌNH" sẽ giới thiệu và giải thích các vấn đề sau: 3.1 Các khái niệm vể tiến trình 3.2 Điều phối các tiến trình 3.3 Liên lạc giữa các tiến trình 3.4 Đồng bộ các tiến trình 3.5 Tính trạng tắc nghẽn (deadlock) 3.1. CÁC KHÁI NIỆM VỀ TIẾN TRÌNH 3.1.1 Tiến trình (Process) Tiến trình là một chương trình đang xử lý, mỗi tiến trình cĩ một khơng gian địa chỉ, một con trỏ lệnh, một tập các thanh ghi và stack riêng. 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. Hệ điều hành sử dụng bộ điều phối (scheduler) để quyết định thời điểm cần dừng hoạt động của tiến trình đang xử lý và lựa chọn tiến trình tiếp theo cần thực hiện. Trong hệ thống cĩ những tiến trình của hệ điều hành và tiến trình của người dùng. * Mục đích cho nhiều tiến trình hoạt động đồng thời: a/ Tăng hiệu suất sử dụng CPU (tăng mức độ đa chương): Phần lớn các tiến trình 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 : CPU IO CPU IO CPU 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 tiến trình, CPU sẽ hồn tồn nhàn rỗi. Ý tưởng tăng cường số lượng tiến trình trong hệ thống là để tận dụng CPU: nếu tiến trình 1 xử lý IO, thì hệ điều hành cĩ thể sử dụng CPU để thực hiện tiến trình 2 Tiến trình 1: CPU IO CPU IO CPU Tiến trình 2: CPU IO CPU IO .EDU.VN b/ Tăng mức độ đa nhiệm Cho mỗi tiến trình thực thi luân phiên trong một thời gian rất ngắn, tạo cảm giác là hệ thống cĩ nhiều tiến trình thực thi đồng thời. 46
47. Hình 3.1: a) A,B,C,D thực thi tuần tự chỉ cần sử dụng một con trỏ lệnh. b) A,B,C,D thực thi đồng thời bằng cách chia xẻ CPU và sử dụng bốn con trỏ lệnh. c/ Tăng tốc độ xử lý: Một số bài tốn cĩ thể xử lý song song nếu được xây dựng thành nhiều đơn thể hoạt động đồng thời thì sẽ tiết kiệm được thời gian xử lý. Ví dụ xét bài tố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ự. 3.1.2 Tiểu trình (thread) 3.1.2.1 Khái niệm tiểu trình Một tiến trình cĩ thể tạo nhiều tiểu trình, mỗi tiểu trình thực hiện một chức năng nào đĩ và thực thi đồng thời cũng bằng cách chia sẻ CPU. Các tiểu trình trong cùng một tiến trình dùng chung khơng gian địa chỉ tiến trình nhưng cĩ con trỏ lệnh, tập các thanh ghi và stack riêng. Một tiểu 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. 3.1.2.2 Liên lạc giữa các tiểu trình Các tiến trình chỉ cĩ thể liên lạc với nhau thơng qua các cơ chế do hệ điều hành cung cấp. Các tiểu trình liên lạc với nhau dễ dàng thơng qua các biến tồn cục của tiến trình. Các tiểu trình cĩ thể do hệ điều hành quản lý hoặc hệ điều hành và tiến trình cùng phối hợp quản lý. .EDU.VN Hình 3.2: a) ba tiến trình thực thi đồng thời, mỗi tiến trình chỉ cĩ một tiểu trình. b) một tiến trình cĩ ba tiểu trình, việc hoạt động đồng thời của các tiểu trình là do tiến trình quản lý. 47
48. Hình 3.3: một chương trình xử lý văn bản cĩ ba thread: một thread nhận các kí tự nhập từ bàn phím, một thread hiện văn bản, một thread ghi văn bản vào đĩa. Hình 3.4: web server cĩ hai thread: worker thread và dispatcher thread, việc hoạt động đồng thời của các tiểu trình là do tiến trình quản lý. (a) đoạn mã cho dispatcher thread (b) đoạn mã cho worker thread .EDU.VN Hình 3.5: một process cĩ ba thread, mỗi thread sẽ cĩ stack riêng. 48
49. Trong bảng dưới đây, tất cả các thread trong cùng process dùng chung các mục ở cột 1, nhưng mỗi thread sẽ cĩ riêng các mục ở cột 2 Trong cùng tiến trình Trong mỗi tiểu trình Khơng gian địa chỉ Bộ đếm chương trình Các biến tồn cục Các thanh ghi Các tập tin mở Ngăn xếp Các tiến trình con Trạng thái Các cảnh báo Các tín hiệu và các bộ xử lý tín hiệu Thơng tin tài khoản 3.1.2.3 Cài đặt tiểu trình (Threads) a/ Cài đặt trong Kernel-space : bảng quản lý thread lưu trữ ở phần kernel và việc điều phối các thread là do hệ điều hành chịu trách nhiệm. Hình 3.6: hệ điều hành chịu trách nhiệm điều phối các tiểu trình b/ Cài đặt trong User-space: bảng quản lý thread lưu trữ ở phần user-space và việc điều phối các thread là do tiến trình chịu trách nhiệm. .EDU.VN Hình 3.7: tiến trình chịu trách nhiệm điểu phối các tiểu trình thuộc tiến trình đĩ c/ Cài đặt trong Kernel-space và User-space: Một số thread mức User được cài đặt bằng một thread mức kernel. 49
50. Hình 3.8: một thread của hệ điều hành quản lý một số thread của tiến trình. Ví dụ: giả sử quantum của process=50 msec, quantum của thread=5 msec và giả sử tiến trình A cĩ ba thread, tiến trình B cĩ 4 thread. - Nếu việc điều phối thread được thực hiện mức user-space thì thứ tự điều phối cĩ thể là A1, A2, A3, A1, A2, A3 nhưng khơng thể là A1, B1, A2, B2, A3, B3; vì khi tiến trình A được cho thực thi với quantum=50 và mỗi thread được thực thi với quantum=5 thì khơng thể A1 đến B1 được do thread của tiến trình nào tiến trình đĩ quản lý và tiến trình A chưa hết quantum nên thread của tiến trình B khơng thể thực hiện. Hình 3.9: điều phối thread ở mức user, một thứ tự điểu phối cĩ thể và khơng thể - Nếu việc điều phối thread được thực hiện mức kernel-space thì thứ tự điều phối A1 đến B1 là cĩ thể vì các thread do hệ điều hành quản lý .EDU.VN Hình 3.10: điều phối thread ở mức kernel, một thứ tự điểu phối cĩ thể và khơng thể. 50
51. 3.1.3 Các trạng thái của tiến trình Việc chuyển trạng thái của tiến trình là do bộ điều phối (scheduler) thực hiện và tại một thời điểm, tiến trình cĩ thể nhận một trong các trạng thái sau đây : a/ New: tiến trình mới được tạo đang ở trong bộ nhớ tạm trên đĩa cứng. b/ Ready: tiến trình trong bộ nhớ và chờ được cấp phát CPU. c/ Running: tiến trình trong bộ nhớ đang thực thi. d/ Blocked (wait): tiến trình trong bộ nhớ chờ được cấp phát tài nguyên, hoặc chờ thao tác nhập/xuất hồn tất hoặc chờ một sự kiện nào đĩ. e/ End: tiến trình trong bộ nhớ hồn tất xử lý. 3.1.3.1 Sơ đồ chuyển trạng thái tiến trình New End 1 5 3 Ready Running 2 6 4 Blocked Hình 3.11: 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ý nào đĩ. Trong khi đĩ, cĩ thể cĩ nhiều tiến trình ở trạng thái blocked hay 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 : - Cung 1: Tiến trình mới tạo, nếu bộ nhớ cịn trống, sẽ được đưa vào bộ nhớ và sẵn sàng nhận CPU, khi đĩ tiến trình từ trạng thái New được chuyển sang trạng thái Ready. - Cung 2: Bộ điều phối cấp phát cho tiến trình một khoảng thời gian sử dụng CPU và cho tiến trình thực hiện, khi đĩ tiến trình từ trạng thái Ready được chuyển sang trạng thái Running. - Cung 3: Khi tiến trình kết thúc việc thực hiện, khi đĩ tiến trình từ trạng thái Running được chuyển sang trạng thái End. - Cung 4: Khi 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 hoặc tiến trình chờ thao tác nhập/xuất hồn tất hoặc tiến trình chờ một sự kiện nào đĩ, khi đĩ tiến trình được chuyển từ trạng thái Running sang trạng thái Blocked. - Cung 5: Khi tiến trình tạm dừng vì hết thời gian sử dụng CPU, bộ điều phối sẽ chọn một tiến .EDU.VNtrình khác để cho xử lý, khi đĩ tiến trình được chuyển từ trạng thái Running sang trạng thái Ready. - Cung 6: Khi 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 mà tiến trình đang đợi đã hồn tất, khi đĩ bộ tiến trình được chuyển từ trạng thái Blocked sang trạng thái Ready. 51
52. 3.1.3.2 Các chế độ xử lý của tiến trình + Tập lệnh của CPU được phân chia thành tập lệnh đặc quyền (các lệnh nếu sử dụng khơng chính xác, cĩ thể ảnh hưởng xấu đến hệ thống) và tập lệnh khơng đặc quyền (khơng ảnh hưởng tới hệ thống). 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 sẽ hoạt động trong chế độ khơng đặc quyền. 3.1.4 Khối quản lý tiến trình (Process Control Block: PCB) Hệ điều hành quản lý các tiến trình thơng qua bảng tiến trình (process table), mỗi mục trong bảng gọi là PCB (khối quản lý tiến trình), PCB lưu thơng tin về một tiến trình gồm cĩ các thơng tin sau: a/ Định danh tiến trình: mã số tiến trình, giúp phân biệt tiến trình này với tiên trình khác b/ Trạng thái tiến trình: xác định hoạt động hiện hành của tiến trình. c/ Ngữ cảnh tiến trình: mơ tả các tài nguyên tiến trình đang sử dụng, dùng để 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. Ngữ cảnh tiến trình bao gồm các thơng tin sau: - 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ỉ lệnh kế tiếp mà tiến trình sẽ thực hiện. 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. - Số hiệu bộ xử lý: 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 nguyê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. d/ Thơng tin giao tiếp: 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 gồm cĩ các thơng tin sau: - 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. e/ Thơng tin thống kê: đâ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 cho cơng việc đánh giá tình hình hệ thống và dự đốn các tình huống tương lai. .EDU.VN Hình 3.12: Cấu trúc của khối quản lý tiến trình (PCB) 52
53. Cĩ thể liệt kê thơng tin trong PCB theo chức năng quản lý như sau: Quản lý tiến trình Quản lý bộ nhớ Quản lý tập tin Các thanh ghi Con trỏ tới đoạn văn bản Thư mục gốc Bộ đếm chương trình Con trỏ tới đoạn dữ liệu Thư mục làm việc Trạng thái chương trình Con trỏ tới đoạn stack Các mơ tả tập tin Con trỏ Stack ID người dùng Tình trạng của tiến trình ID nhĩm Độ ưu tiên Các tham số điều phối ID của tiến trình Tiến trình cha Nhĩm tiến trình Các tín hiệu Thời điểm bắt đầu tiến trình Thời gian CPU sử dụng Thời gian CPU của tiến trình con Thời gian lần cảnh báo kế tiếp Hình 3.13: thơng tin trong khối PCB được liệt kê theo chức năng quản lý 3.1.5 Các thao tác trên tiến trình a/ Tạo lập tiến trình (create) 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 (trong Windows khơng cĩ khái niệm cây tiến trình, mọi tiến trình là ngang cấp). 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 tiến trình cha tạo tiến trình con, tiến trình cha 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, hoặc 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ý. Ví dụ: tiến trình A tạo hai tiến trình con B và C, B tạo ba tiến trình con D, E, F. .EDU.VNCá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. + Các cơng việc cần thực hiện khi tạo lập tiến trình: - Đị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 53
54. - Cấp phát các tài nguyên ban đầu cho tiến trình - Tạo PCB lưu trữ thơng tin tiến trình + Các thời điểm tiến trình được tạo ra : Tiến trình được tạo ra vào một trong các thời điểm sau: - Thời điểm khởi tạo hệ thống (System initialization) - Thời điểm thực thi lời gọi tạo tiến trình - Thời điểm người sử dụng yêu cầu tạo tiến trình mới - Thời điểm khởi đầu một cơng việc theo lơ (batch job) b/ Kết thúc tiến trình (destroy) Một tiến trình kết thúc xử lý khi nĩ hồn tất lệnh 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ĩ. 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 cần thực hiện các cơng việc sau: - Thu hồi các tài nguyên đã 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. Tiến trình cĩ thể tự kết thúc bình thường (Normal exit ) do đã thực thi xong hoặc cĩ lỗi và tự kết thúc (Error exit) hoặc cĩ lỗi nặng và bị hệ điều hành kết thúc (Fatal exit) hoặc bị kết thúc bởi tiến trình khác (Killed by another process ). c/ Tạm dừng tiến trình (suspend) d/ Tái kích hoạt tiến trình (resume) e/ Thay đổi độ ưu tiên tiến trình (change priority) 3.1.6 Khối quản lý tài nguyên ( Resource Control Block: RCB) Mỗi tài nguyên được hệ điều hành quản lý bằng một cấu trúc gọi là khối quản lý tài nguyên RCB. RCB khác nhau về chi tiết cho từng loại tài nguyên, nhưng cơ bản cĩ các thơng tin sau: a/ Định danh tài nguyên: dùng để phân biệt tài nguyên này với tài nguyên khác. b/ Trạng thái tài nguyên: 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. .EDU.VNc/ Hàng đợi trên 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. d/ Bộ cấp phát tài nguyên: là đoạn mã đảm nhiệm việc cấp phát tài nguyên. 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. 54
55. RCB Ý nghĩa Định danh tài nguyên rid Trạng thái tài nguyên Danh sách các phần của tài nguyên cĩ thể sử dụng Hàng đợi Danh sách các tiến trình đang đợi tài nguyên Bộ cấp phát Con trỏ đến bộ cấp phát tài nguyên Hình 3.14: thơng tin trong khối RCB + Mục tiêu của bộ cấp phát tài nguyên : - 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 thể 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ì hỗn cĩ thể chấp nhận được. - Tối ưu hĩa sự sử dụng tài nguyên. 3.2 ĐIỀU PHỐI TIẾN TRÌNH Hệ điều hành điều phối tiến trình thơng qua bộ điều phối (scheduler) và bộ phân phối (dispatcher). Bộ điều phối sử dụng một giải thuật thích hợp để lựa chọn tiến trình được xử lý tiếp theo. Bộ phân phối chịu trách nhiệm cập nhật ngữ cảnh của tiến trình bị tạm ngưng và trao CPU cho tiến trình được chọn bởi bộ điều phối để tiến trình thực thi. 3.2.1 Mục tiêu của bộ điều phối a/ 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. b/ Tính hiệu qủa (Efficiency): Hệ thống phải tận dụng được CPU 100% thời gian. c/ Thời gian đáp ứng hợp lý (Response time): Cực tiểu hố thời gian hồi đáp cho các tương tác của người sử dụng. d/ Thời gian lưu lại trong hệ thống (Turnaround Time): Cực tiểu hĩa thời gian hồn tất các tác vụ xử lý theo lơ. e/ 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ị .EDU.VNthời gian. Thường hệ điều hành khĩ thể thỏa mãn tất cả các mục tiêu kể trên mà chỉ cĩ thể dung hịa. Để việc điều phối cĩ hiệu qủa, hệ điều hành cần quan tâm đến đặc tính của tiến trình. 3.2.2 Các đặc tính của tiến trình a/ Tính hướng nhập/xuất( I/O-boundedness): 55
56. Tiến trình khi thực thi, chủ yếu thực hiện thao tác nhập xuất, rất ít lệnh xử lý. Tiến trình cĩ khuynh hướng khơng sử dụng CPU đến 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 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ý( CPU-boundedness): Tiến trình khi thực thi, chủ yếu thực hiện thao tác xử lý, rất ít thao tác nhập/xuất. Tiến trình 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ì hỗ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 ưu tiên theo một số tiêu chuẩn nào đĩ. Các tiến trình cĩ độ ưu tiên cao cần thực hiện trước. 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 để hồ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 để hồ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 để hồ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ý. Khi thực hiện điều phối, cần 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ể dựa vào các nguyên lý sau: 3.2.3 Các nguyên lý điều phối 3.2.3.1 Điều phối độc quyền (preemptive): Tiến trình khi nhận được CPU sẽ được độc chiếm CPU đến khi hồn tất xử lý hoặc tự nguyện giải phĩng CPU. Các giải thuật độc quyền thường đơn giản và dễ cài đặt nhưng khơng thích hợp với các hệ thống 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 ý, 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 độc quyền cũng 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 hồn tất. .EDU.VN3.2.3.2 Điều phối khơng độc quyền (nopreemptive): Khi một tiến trình nhận được CPU, nĩ vẫn được sử dụng CPU đến khi hồn tất hoặc tự nguyện giải phĩng CPU, nhưng nếu xuất hiện một tiến trình khác cĩ độ ưu tiên cao hơn thì hệ điều hành sẽ cho tiến trình cĩ độ ưu tiên cao hơn dành quyền sử dụng CPU của tiến trình ban đầu. Các thuật tốn điều phối khơng độc quyền tránh đượ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. 56
57. Đối với các hệ thống tương tác, các hệ thời gian thực (real time), cần đ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 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. Vấn đề đặt ra cho hệ điều hành là thời điểm nào cần thực hiện điều phối. + Thời điểm thực hiện điều phối Hệ điều hành thực hiện việc điều phối tiến trình khi cĩ một trong các tình huống sau: a/ Tiến trình chuyển từ trạng thái running sang trạng thái 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 b/ Tiến trình chuyển từ trạng thái running sang trạng thái ready: ví dụ xảy ra một ngắt. c/ Tiến trình chuyển từ trạng thái blocked sang trạng thái ready: ví dụ một thao tác nhập/xuất hồn tất. d/ Tiến trình kết thúc. e/ Tiến trình cĩ độ ưu tiên cao hơn xuất hiện: chỉ áp dụng đối với điều phối khơng độc quyền 3.2.4 Tổ chức điều phối 3.2.4.1 Các danh sách điều phối Để thực hiện điều phối, hệ điều hành sử dụng ba loại danh sách là: danh sách tác vụ (job list), danh sách sẵn sàng (ready list), danh sách chờ đợi (waiting list). Khi một tiến trình được tạo, PCB của tiến trình sẽ được chèn vào danh sách tác vụ (job list). Khi bộ nhớ đủ chỗ, một tiến trình trong danh sách tác vụ được chọn, nạp từ đĩa vào bộ nhớ và PCB của tiến trình đĩ được chuyển sang danh sách sẵn sàng (ready list). 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ẽ thi hành, và sẽ chuyển sang danh sách chờ đợi (waiting list) khi xảy ra các sự kiện ví dụ như đợi một thao tác nhập/xuất hồn tất hoặc yêu cầu tài nguyên mà chưa được thỏa mãn hoặc được yêu cầu tạm dừng Tiến trình đang thi hà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. Hệ điều hành chỉ sử dụng một danh sách tác vụ, một danh sách sẵn sàng nhưng mỗi một tài nguyên (thiết bị ngoại vi, file, ) 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 đĩ. .EDU.VN Hình 3.15: Mỗi tài nguyên cĩ một hàng đợi lưu danh sách các tiến trình đang đợi tài nguyên. 57
58. ds sẵn sàng CPU Yêu cầu ds đợi tài nguyên I/O tài nguyên Hết thời gian Ngắt xảy ra Đợi 1 ngắt Hình 3.16: khi cĩ yêu cầu tài nguyên mà chưa được đáp ứng, tiến trình được đưa vào hàng đợi tài nguyên. 3.2.4.2 Các loại điều phối a) Điều phối tác vụ (job scheduling) Là lựa chọn tác vụ nào được đưa 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ột tiế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 . Để 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 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 ( process scheduling) 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, bộ điều phối tiến trình cần sử dụng các thuật tốn tốt nhất. 3.2.4.3 Các thuật tốn điều phối a/ Thuật tốn FIFO CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng, tiến trình này là tiến trình được đưa vào hệ thống sớm nhất. Đây là thuật tốn điều phối theo nguyên tắc độc quyền. .EDU.VN Hình 3.17: mơ hình điều phối theo FIFO Ví dụ: Hệ thống lần lượt cĩ ba tiến trình P1, P2, P3 vào ready list. Thời điểm vào RL và thời gian xử lý của mỗi tiến trình cho trong bảng sau: 58
59. Tiến trình Thời điểm vào RL Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 Theo thuật tốn FIFO, thứ tự cấp phát CPU cho các tiến trình là : P1 P2 P3 0 24 27 30 Thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (27-2) với P3. Thời gian chờ trung bình là ( 0+23+25)/3 = 16 miliseconds. Nhận xét: - Cĩ thể một tiến trình cĩ thời gian xử lý ngắn phải chờ một tiến trình cĩ thời gian xử lý dài thực thi xong. - Thời gian chờ trung bình phụ thuộc vào thứ tự của các tiến trình trong danh sách sẵn sàng. b/ Thuật tốn phân phối xoay vịng (Round Robin) Bộ điều phối lần lượt cấp phát cho mỗi tiến trình trong danh sách RL một khoảng thời gian sử dụng CPU gọi là quantum. 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 (blocked) 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 hồ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. Đây là một giải thuật điều phối khơng độc quyền Hình 3.18: mơ hình điều phối theo round robin Ví dụ: .EDU.VNTiến trình Thời điểm vào RL Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 59
60. Nếu sử dụng quantum là 4 miliseconds, thứ tự cấp phát CPU sẽ là : P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 Thời gian chờ đợi trung bình sẽ là (6+3+5)/3 = 4.66 milisecondes. Nhận xét: - Nếu cĩ n tiến trình trong danh sách sẵn sàng và sử dụng quantum q, thì 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. - Nếu thời lượng quantum quá bé sẽ phát sinh 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 giảm khả năng tương tác của hệ thống. c/ Thuật tốn độ ưu tiên Mỗi tiến trình được gán cho một độ ưu tiên, 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 nhờ vào các yếu tố bên trong hay bên ngồi. Yếu tố bên trong như là giới hạn thời gian, nhu cầu bộ nhớ Yếu tố bên ngồi như là 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 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 mới cao hơn tiến trình hiện hành. 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 theo thứ tự độ ưu tiên, 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ụ : giả sử độ ưu tiên 1 > độ ưu tiên 2> độ ưu tiên 3 Tiến trình Thời điểm vào RL Độ ưu tiên Thời gian xử lý P1 0 3 24 P2 1 1 3 P3 2 2 3 .EDU.VNSử dụng thuật giải độ ưu tiên độc quyền, thứ tự cấp phát CPU như sau : P1 P2 P3 0 24 27 30 Thời gian chờ đợi trung bình sẽ là (0+23+25)/3 =16 milisecondes. 60