Giáo trình Hệ điều hành - Đặng Thanh Hải

73 trang phuongnguyen 3920

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ điều hành - Đặng Thanh Hải", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

giao_trinh_he_dieu_hanh_dang_thanh_hai.pdf

Nội dung text: Giáo trình Hệ điều hành - Đặng Thanh Hải

TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA CƠNG NGHỆ THƠNG TIN ThS. Đặng Thanh Hải BÀI GIẢNG TĨM TẮT HỆ ĐIỀU HÀNH Dành cho sinh viên ngành Cơng Nghệ Thơng Tin (Lưu hành nội bộ) Đà Lạt 2008
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành LỜI NĨI ĐẦU Giáo trình “ Hệ điều hành” được biên soạn theo chương trình đào tạo hệ thống tín chỉ của trường Đại Học Đà Lạt. Mục đích biên soạn giáo trình nhằm cung cấp cho sinh viên ngành Cơng Nghệ Thơng Tin những kiến thức về hệ điều hành. Tuy cĩ rất nhiều cố gắng trong cơng tác biên soạn nhưng chắc chắn rằng giáo trình này cịn nhiều thiếu sĩt. Chúng tơi xin trân trọng tiếp thu tất cả những ý kiến đĩng gĩp của các bạn sinh viên, cũng như của các đồng nghiệp trong lĩnh vực này để hồn thiện giáo trình, 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. Khoa Cơng Nghệ Thơng Tin Trường Đại Học Đà Lạt Trang 2
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành MỤC LỤC CHƯƠNG I – TỔNG QUAN HỆ ĐIỀU HÀNH 6 I. 1 Khái niệm hệ điều hành 6 I.2 Phân loại hệ điều hành 7 I.2.1 Hệ điều hành xử lý theo lơ đơn giản 7 I.2.2 Hệ điều hành xử lý theo lơ đa chương 7 I.2.3 Hệ điều hành đa nhiệm 8 I.2.4 Hệ điều hành tương tác 8 I.2.5 Hệ điều hành giao diện bàn giấy (Desktop) 8 I.2.6 Hệ thống song song 8 I.2.7 Hệ thống phân tán 9 I.2.8 Hệ thống cầm tay 10 I.3.Lịch sử phát triển hệ điều hành 11 CHƯƠNG II – CẤU TRÚC HỆ ĐIỀU HÀNH 12 II.1 Các thành phần cơ bản của hệ thống máy tính 12 II.1.1 Quản lý tiến trình 12 II.1.2 Quản lý bộ nhớ chính 12 II.1.3 Quản lý tập tin 13 II.1.4 Quản lý hệ thống nhập xuất 13 II.1.5 Quản lý hệ thống lưu trữ phụ 13 II.1.6 Hệ thống bảo vệ 13 II.1.7 Hệ thống dịng lệnh 13 II.2 Các dịch vụ hệ điều hành 13 II.3 Lời gọi hệ thống 14 II.4 Chương trình hệ thống 14 II.5 Cấu trúc hệ thống 14 II.5.1 Cấu trúc đơn giản 14 II.5.2 Cấu trúc theo lớp 16 II.6 Máy ảo 17 II.7 Qúa trình nạp hệ điều hành 18 CHƯƠNG III – GIỚI THIỆU MỘT SỐ HỆ ĐIỀU HÀNH 19 III.1 Hệ điều hành MS-DOS 19 III.1.1 Giới thiệu 19 III.1.2 Cấu trúc hệ điều hành MS-DOS 19 III.1.3 Lịch sử phát triển 20 III.1.4 Cài đặt hệ điều hành 20 III.1.5 Tập lệnh 20 Trang 3
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành III.2 Hệ điều hành Windows 22 III.2.1 Giới thiệu 22 III.2.2 Lịch sử phát triển 22 III.2.3 Các tiện ích của Windows 22 III.3 Hệ điều hành Linux 23 III.3.1 Đặc điểm 23 III.3.2 Lịch sử phát triển 23 III.3.3 Cài đặt hệ điều hành 24 III.3.4 Tập lệnh 24 CHƯƠNG IV – HỆ THỐNG QUẢN LÝ TẬP TIN Error! Bookmark not defined.27 IV.1 Khái niệm tập tin – thư mục 27 IV.2 Mơ hình quản lý và tổ chức tập tin 28 IV.3 Các chức năng hệ thống tập tin 28 IV.4 Cài đặt hệ thống tập tin 28 IV.5 Hệ thống tập tin MS-DOS 30 IV.5 Hệ thống tập tin Unix 40 CHƯƠNG V – HỆ THỐNG QUẢN LÝ NHẬP XUẤT T Error! Bookmark not defined. V.1 Các khái niệm 44 V.1.1 Thiết bị nhập xuất 44 V.1.2 Thiết bị logic 44 V.1.3 Hệ thống quản lý nhập/ xuất 44 V.2 Mơ hình tổ chức và quản lý việc nhập xuất 45 V.2.1 Mơ hình 45 V.2.1.1 các thiết bị nhập xuất 45 V.2.1.2 Điều khiển thiết bị 45 V.2.1.3 DMA 45 V.2.1 Thiết bị logic 45 V.2.1.1 Kiểm sốt ngắt 46 V.2.1.2 Device Drivers 46 V.2.1.3 Phần mềm nhập xuất độc lập thiết bị 46 V.2.1.4 Phần mềm nhập xuất phạm vi người sử dụng 46 V.2.2 Các chức năng 46 V.2.2.1 Điều khiển thiết bị nhập xuất 46 V.2.2.2 DMA 47 V.2.2.3 Thiết bị Logic 47 CHƯƠNG VI – HỆ THỐNG QUẢN LÝ TIẾN TRÌNH 50 VI.1 Khái niệm tiến trình 50 VI.2 Các trạng thái của tiến trình 50 Trang 4
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành VI.3 Cài đặt tiến trình 51 VI.4 Tiểu trình 51 VI.5 Lập lịch tiến trình 51 VI.5.1 Chiến lược lập lịch tiến trình FIFO 51 VI.5.2 Chiến lược Round Robin 52 VI.5.3 Chiến lược gán độ ưu tiên 53 VI.6.1 Các phương pháp thực hiện loại trừ nhau vào vùng găng 56 VI.6.1.1 Dùng biến khĩa 56 VI.6.1.2 Luân phiên ngặt 56 VI.6.1.3 Giải pháp Peterson 57 VI.6.1.4 Giải pháp gọi lời gọi hệ thống SLEEP vào WAKEUP 57 VI.6.1.5 Semaphore 58 VI.6.2 Áp dụng Semaphore để giải quyết bài tốn cổ điển 59 VI.6.2.1 Bài tốn” Bữa ăn tối của các nhà hiền triết” 60 VI.6.2.2 Bài tốn” Độc giả và nhà văn” 62 CHƯƠNG VII – HỆ THỐNG QUẢN LÝ BỘ NHỚ Error! Bookmark not defined.65 VII.1 Giới thiệu 65 VII.2 Quản lý bộ nhớ khơng phân trang, khơng Swapping 66 VII.3 Quản lý bộ nhớ với những phân đọan cố định 70 VII.4 Quản lý bộ nhớ với những phân đọan động 70 VII.5 Các thuật tốn thay thế trang 70 VII.5.1 Thuật tốn FIFO 71 VII.5.2 Thuật tốn tối ưu 71 VII.5.3 Thuật tốn lâu nhất chưa sử dụng (LRU) 71 VII.5.4 Thuật tốn Not Recently Used (NRU) 71 Trang 5
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CHƯƠNG I TỔNG QUAN HỆ ĐIỀU HÀNH I. 1 KHÁI NIỆM HỆ ĐIỀU HÀNH • Hệ điều hành là một chương trình được xem như trung gian giữa người sử dụng máy tính và phần cứng máy tính với mục đích thực hiện các chương trình giúp cho người dùng sử dụng máy tính dễ dàng hơn, sử dụng phần cứng một cách cĩ hiệu quả. • Hệ điều hành là một phần quan trọng của hệ thống máy tính. Một hệ thống máy tính thường bao gồm các phần: phần cứng, hệ điều hành, các chương trình ứng dụng và người sử dụng. - Phần cứng : Bao gồm tài nguyên cơ bản của máy tính (CPU, memory, I/O devices). - Hệ điều hành: Điều khiển và kết hợp sử dụng phần cứng trong các ứng dụng khác nhau của nhiều người dùng khác nhau. - Các chương trình ứng dụng : Sẽ sử dụng tài nguyên hệ thống để giải quyết vấn đề của người sử dụng (Trình biên dịch, hệ thống cơ sở dữ liệu, games, chương trình thương mại). - Người sử dụng : Người, các máy tính khác. • Mơ hình hệ thống máy tính • Hệ điều hành cũng cĩ thể được xem là bộ cấp phát tài nguyên – Quản lý và cấp phát tài nguyên. Hình 1.1 Trang 6
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Hệ điều hành Điều khiển chương trình – Điều khiển thực hiện các chương trình người sử dụng và các hoạt động của thiết bị nhập xuất. • Hệ điều hành cịn được gọi là Kernel(nhân) – Đây là các phần cốt lõi của chương trình, thường trú trong bộ nhớ, và thực hiện hầu hết các nhiệm vụ điều hành chính. I.2 PHÂN LOẠI HỆ ĐIỀU HÀNH I.2.1 Hệ điều hành xử lý theo lơ đơn giản • Khi một cơng việc chấm dứt, hệ thống sẽ thực hiện cơng việc kế tiếp mà khơng cần sự can thiệp của người lập trình, do đĩ thời gian thực hiện sẽ mau hơn. Một chương trình gọi là bộ giám sát thường trực được thiết kế để giám sát việc thực hiện dãy cơng việc một cách tự động, chương trình này luơn thường trú trong bộ nhớ chính. • Hệ điều hành theo lơ thực hiện các cơng việc lần lượt theo những chỉ thị định trước. I.2.2 Hệ điều hành xử lý theo lơ đa chương • Đa chương làm gia tăng khai thác CPU bằng cách tổ chức các cơng việc sao cho CPU luơn luơn phải trong tình trạng làm việc. • Cách thực hiện là hệ điều hành lưu trữ một phần của các cơng việc ở nơi lưu trữ trong bộ nhớ. CPU sẽ lần lượt thực hiện các phần cơng việc này. Khi đang thực hiện, nếu cĩ yêu cầu truy xuất thiết bị thì CPU khơng nghỉ mà thực hiện tiếp các cơng việc tiếp theo. • Mơ hình bộ nhớ cho hệ điều hành đa chương: Hình 1.2 • Các đặc trương của hệ điều hành đa chương: - Việc nhập xuất phải thực hiện thường xuyên bởi hệ thống. - Quản lý bộ nhớ – hệ thống phải cấp phát bộ nhớ cho các cơng việc. - Lập lịch CPU – hệ thống phải chọn giữa các cơng việc nào thật sự được chạy. - Cấp phát các thiết bị. Trang 7
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành I.2.3 Hệ điều hành đa nhiệm • Hệ điều hành đa nhiệm là một sự mở rộng logic của hệ điều hành đa chương. Nhiều cơng việc cùng được thực hiện thơng qua cơ chế chuyển đổi CPU như hệ đa chương nhưng thời gian mỗi lần chuyển đổi diễn ra rất nhanh. • Hệ điều hành đa nhiệm được phát triển để cung cấp việc sử dụng bên trong của một máy tính cĩ giá trị hơn. • Một chương trình khi thi hành được gọi là tiến trình. Trong khi thi hành một tiến trình nĩ phải thực hiện các thao tác nhập xuất và trong khoảng thời gian đĩ CPU sẽ thi hành một tiến trình khác. • Hệ điều hành đa nhiệm cho phép nhiều người sử dụng chia xẻ máy tính một cách đồng bộ do thời gian chuyển đổi nhanh nên họ cĩ cảm giác là các tiến trình đang chạy được thi hành cùng lúc. • Hệ điều hành đa nhiệm phức tạp hơn hệ điều hành đa chương và nĩ phải cĩ thêm các chức năng: quản trị và bảo vệ bộ nhớ, sử dụng bộ nhớ ảo, • Hệ điều hành đa nhiệm hiện nay rất thơng dụng. I.2.4 Hệ điều hành tương tác • Hệ điều hành cung cấp cơ chế truyền thơng trực tiếp giữa người sử dụng và hệ thống. Khi hệ điều hành kết thúc thực hiện một lệnh, nĩ sẽ tìm ra lệnh kế tiếp từ người sử dụng thơng qua bàn phím. • Hệ thống cho phép người sử dụng truy cập dữ liệu và mã chương trình một cách trực tiếp. I.2.5 Hệ điều hành giao diện bàn giấy (Desktop) • Hệ điều hành này cĩ cách giao diện với người sử dụng giống như một bàn làm việc, tức trên màn hình trình bày rất nhiểu biểu tượng chương trình, cơng cụ làm việc. Hệ điều hành cĩ đặc điểm là: - Cài đặt trên máy tính cá nhân – hệ thống máy tính được thiết kế cho một người sử dụng đơn lẻ. - Các thiết bị hỗ trợ đắc lực là thiết bị nhập xuất – bàn phím, mouse, màn hình, máy in. - Thuận tiện cho người dùng và đáp ứng nhanh. - Cĩ thể kế thừa kỹ thuật để phát triển hệ điều hành lớn hơn. • Một số hệ điều hành khác nhau sử dụng bàn giấy hiện nay (Windows, UNIX, Linux) I.2.6 Hệ thống song song • Ngồi các hệ thống tín chỉ cĩ một bộ xử lý cịn cĩ các hệ thống 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. • Thuận lợi của hệ thống xử lý song song: - Xử lý nhiều cơng việc cùng lúc thật sự - Tăng độ tin cậy Trang 8
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Trong hệ thống xử lý song song được thành hai loại: Đa xử lý đối xứng - Mỗi bộ xử lý chạy một bản sao hệ điều hành. - Nhiều tiến trình cĩ thể chạy cùng lúc mà khơng gây hỏng. - Hầu hết các thế hệ hệ điều hành đều hỗ trợ đa xử lý đối xứng Đa xử lý khơng đối xứng - Mỗi bộ xử lý được gắn vào một cơng việc cụ thể; Bộ xử lý chủ lập lịch và cấp phát cơng việc cho bộ xử lý phụ. - Phổ biến nhiều trong hệ thống cực kỳ lớn. • Kiến trúc hệ thống đa bộ xử lý đối xứng: Hình 1.3 I.2.7 Hệ thống phân tán • Hệ thống thực hiện phân tán việc tính tốn giữa các bộ xử lý . • Mỗi bộ xử lý cĩ vùng nhớ riêng; các bộ xử lý truyền thơng với nhau qua hệ thống mạng tốc độ cao. • Thuận lợi của hệ thống phân tán: - Chia xẻ tài nguyên - Tăng tốc độ tính tốn - Đáng tin cậy - Truyền thơng • Trong hệ thống yêu cầu cơ sở hạ tầng về mạng. Mạng cục bộ (LAN) hoặc mạng diện rộng (WAN), cũng cĩ thể là hệ thống client-server hoặc peer-to-peer. • Mơ hình hệ thống Client- server: Hình 1.4 Trang 9
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành I.2.8 Hệ thống cầm tay • Máy trợ lý cá nhân kỹ thuật số (PDAs) (personal digital assistant – PDA) • Vấn đề cần giải quyết : - Bộ nhớ bị giới hạn - Bộ xử lý chậm - Màn hình hiển thị nhỏ I.3.LỊCH SỬ PHÁT TRIỂN HỆ ĐIỀU HÀNH • Thế hệ 1: 1945 – 1955 - Năm 1940 Howard Aiken và John Von Neumam đã thành cơng trong việc xây dựng một máy tính dùng ống chân khơng. - Loại máy này sử dụng khoảng 1000 ống chân khơng, kích thước lớn nhưng khả năng xử lý chậm - Thời kỳ này ngơn ngữ lập trình là ngơn ngữ máy (nhị phân) - Việc điều hành máy, thiết kế chương trình đều do một nhĩm người. - Năm 1950 phiếu đục lỗ ra đời và cĩ thể viết chương trình trên phiếu đục lỗ . • Thế hệ 2: 1955 – 1965 - Thời kỳ này máy tính được chế tạo bằng thiết bị bán dẫn. - Cơng việc lập trình được thực hiện trên giấy bằng ngơn ngữ (assembler, fortran) sau đĩ được đục lỗ trên phiếu và cuối cùng đưa phiếu vào máy. - Hệ thống xử lý theo lơ ra đời. Các cơng việc lưu trữ vào băng từ, chuyển điều khiển đến các cơng việc khác nhau được thực hiện bởi một chương trình thường trú- Đây chính là tiền thân của hệ điều hành - Với hệ thống máy tính này đã cĩ sự phân biệt rõ ràng giữa người thiết kế , người xây dựng, vận hành, lập trình và bảo trì máy. • Thế hệ 3: 1965 – 1980 - Thời kỳ này máy tính được chế tạo bằng IC do đĩ: Kích thước và giá cả máy tính giảm đáng kể Máy tính trở nên phổ biến hơn Các thiết bị ngoại vi dành cho máy tính càng nhiều Các thao tác điều kiển máy tính ngày càng phức tạp - Hệ điều hành ra đời nhằm điều phối, kiểm sốt hoạt động và giải quyết các yêu cầu tranh chấp thiết bị. - Một số hệ điều hành ra đời: MULTICS, UNIX • Thế hệ 4: 1980 - - 1980 IBM cho ra đời máy tính cá nhân PC với hệ điều hành MS-DOS - Cĩ nhiều hệ điều hành đa nhiệm, giao diện ngày càng thân thiện với người sử dụng ra đời. - Hiện nay hệ điều hành mạng được phát triển mạnh mẽ. (Windows, Linux) Trang 10
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CÂU HỎI 1. Trình bày các khái niệm hệ điều hành? 2. Trình bày khái niệm hệ điều hành đa nhiệm? Sự khác nhau giữa hệ điều hành đa chương và hệ điều hành đa nhiệm? 3. Ngày nay một hệ điều hành được thiết kế phải là những loại hệ điều hành nào? Trang 11
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CHƯƠNG II CẤU TRÚC HỆ ĐIỀU HÀNH II.1 CÁC THÀNH PHẦN CỦA HỆ ĐIỀU HÀNH Hệ điều hành cung cấp một mơi trường làm việc cho các chương trình thi hành. Nĩ cung cấp các dịch vụ cho người sử dụng, giao tiếp với người sử dụng. các thành phần bên trong của hệ điều hành II.1.1 Quản lý tiến trình • Tiến trình là một chương trình đang thực hiện. Một tiến trình cần các tài nguyên bao gồm thời gian CPU , bộ nhớ , files, và thiết bị nhập xuất, để hồn tất các cơng việc của mình. • Vai trị của việc quản lý tiến trình trong hệ điều hành. Tạo, huỷ tiến trình của người sử dụng và của hệ thống Ngưng và cho phép chạy lại các tiến trình. Cung cấp cơ chế : - Đồng bộ hĩa tiến trình - Truyền thơng giữa các tiến trình - Kiểm sốt deadlock II.1.2 Quản lý bộ nhớ chính • Bộ nhớ là một dãy lớn các word hoặc byte, mỗi phần tử cĩ một địa chỉ. Nĩ là nơi lưu trữ, truy xuất dữ liệu một cách nhanh chĩng. • Bộ nhớ chính là thiết bị lưu trữ cĩ thể thay đổi. Nĩ sẽ làm mất hết dữ liệu trong trường hợp hệ thống bị hỏng. • Vai trị quản lý bộ nhớ chính trong hệ điều hành: Lưu trữ thơng tin các vùng nhớ hiện được sử dụng bởi ai. Quyết định tiến trình nào được nạp vào bộ nhớ khi bộ nhớ cĩ chỗ trống. Cấp phát và thu hồi bộ nhớ khi cần thiết. II.1.3 Quản lý tập tin • Một file là một sự thu thập các thơng tin cĩ liên quan được định nghĩa bởi người tạo ra nĩ. Thường file thể hiện cho chương trình và dữ liệu. • Vai trị quản lý file trong hệ điều hành: Tạo và xĩa file. Tạo và xố thư mục. Cung cấp các thao tác trên file và thư mục. Ánh xạ file vào hệ thống lưu trữ phụ. Backup tập tin trên các thiết bị lưu trữ II.1.4 Quản lý hệ thống nhập xuất Trang 12
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Một trong những mục tiêu của hệ điều hành là che dấu những đặc thù của thiết bị phần cứng đối với người sử dụng thay vào đĩ là một lớp thân thiện hơn, người sử dụng dễ thao tác hơn. • Một hệ thống nhập/ xuất bao gồm: Hệ thống buffer-caching Giao tiếp thiết bị Bộ điều khiển cho các thiết bị phần cứng II.1.5 Quản lý hệ thống lưu trữ phụ • Chính vì bộ nhớ chính thường thay đổi và quá nhỏ lưu trữ tất cả dữ liệu và chương trình một cách lâu dài,hệ thống máy tính cung cấp bộ nhớ phụ để back up từ bộ nhớ chính. • Hầu hết hệ thống máy tính ngày nay sử dụng đĩa như thành phần cơ bản lưu trữ cả chương trình và dữ liệu. • Vai trị quản lý đĩa trong hệ điều hành: Quản lý bộ nhớ cịn trống Cấp phát lưu trữ Lập lịch đĩa II.1.6 Hệ thống bảo vệ • Bảo vệ truy cập bởi các chương trình, các tiến trình, hoặc người sử dụng. • Cơ chế bảo vệ phải là: Phân biệt giữa cho phép hay khơng được phép. Chỉ rõ điều khiển bị lợi dụng. Cung cấp các biện pháp phải tuân thủ. II.1.7 Hệ thống dịng lệnh • Một trong những phần quan trọng của chương trình hệ thống trong một hệ điều hành là cơ chế dịng lệnh, đây là sự giao tiếp giữa người sử dụng và hệ điều hành. • Các lệnh đưa vào hệ điều hành thơng qua bộ điều khiển lệnh. Trong các hệ thống đa nhiệm một chương trình cĩ thể đọc và thơng dịch các lệnh điều khiển được thực hiện một cách tự động. • Chức năng hệ thống dịng lệnh là lấy lệnh kế tiếp và thi hành. • Các lệnh cĩ quan hệ với việc tạo và quản lý các tiến trình, kiểm sốt nhập xuất, quản lý bộ lưu trữ phụ, quản lý bộ nhớ chính, truy xuất hệ thống tập tin và cơ chế bảo vệ. II.2 CÁC DỊCH VỤ HỆ ĐIỀU HÀNH Trang 13
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Thực hiện chương trình – hệ thống cĩ khả năng nạp một chương trình vào bộ nhớ và thi hành nĩ. • Thực hiện nhập xuất – Từ chương trình người dùng khơng thể thực hiện nhập xuất trực tiếp, hệ điều hành phải cung cấp các cách thức để thực hiện nhập xuất. • Các thao tác trên hệ thống file – chương trình cĩ khả năng đọc, ghi, tạo và xố file. • Truyền thơng – Trao đổi thơng tin giữa các tiến trình đang thực hiện cùng lúc trên máy tính hay trên các hệ thống trên mạng. Thực hiện bằng cách thơng qua bộ nhớ dùng chung hay qua các thơng điệp. • Phát hiện lỗi – bảo đảm phát hiện lỗi trong CPU, bộ nhớ, thiết bị nhập xuất hoặc trong chương trình người sử dụng II.3 LỜI GỌI HỆ THỐNG • Lời gọi hệ thống là giao diện giữa chương trình đang chạy và hệ điều hành. Thơng thường là các chỉ thị bằng ngơn ngữ assembler. • Cĩ ba phương pháp được sử dụng truyền tham số giữa chương trình đang chạy và hệ điều hành. Truyền tham số qua các thanh ghi. Lưu trữ các tham số trong một bảng trong bộ nhớ và địa chỉ của bảng được truyền qua tham số vào thanh ghi. Các chương trình thực hiện Push các tham số vào stack và được pop bởi hệ điều hành. Hình 2.1 • Các loại lời gọi hệ thống: - Điều khiển tiến trình - Quản lý file - Quản lý thiết bị - Truyền thơng II.4 CHƯƠNG TRÌNH HỆ THỐNG Hệ điều hành là một tập hợp các chương trình hệ thống. Chương trình hệ thống cung cấp một mơi trường thuận tiện cho việc phát triển và thực hiện chương trình. Chúng được chia thành : Trang 14
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Thao tác trên file: các chương trình này tạo, xố, sao chép, in , liệt kê và các thao tác tổng quát trên tập tin và thư mục. Thơng tin các trạng thái : Cung cấp các thơng tin về ngày, giờ, khối lượng bộ nhớ hoặc dung lượng đĩa, số lượng người dùng, hoặc thơng tin về trạng thái. Những thơng tin này được định dạng và xuất trên các thiết bị xuất như terminal hay tập tin. Mơ tả tập tin: Một số trình soạn thảo văn bản bao gồm việc tạo và mơ tả tập tin lưu trên đĩa. Hỗ trợ ngơn ngữ lập trình : Chương trình dịch, hợp ngữ, và thơng dịch cho một số ngơn ngữ lập trình. Các chương trình này cĩ thể được cung cấp chung với hệ điều hành hay là một phần riêng. Nạp và thực hiện chương trình : Hệ thống cung cấp các bộ nạp, định vị, liên kết ngồi ra cịn cung cấp chức năng debug. Truyền thơng: Hệ thống cung cấp cơ chế tạo sự kết nối ảo giữa các tiến trình, người sử dụng, và hệ thống máy tính khác. Chương trình ứng dụng: Thơng thường hệ điều hành kèm theo một số chương trình ứng dụng như định dạng, sao chép đĩa, II.5 CẤU TRÚC HỆ THỐNG II.5.1 Cấu trúc đơn giản • Các hệ điều hành đơn giản thường khơng cĩ cấu trúc được định nghĩa tốt, thường bắt đầu từ một hệ thống nhỏ, đơn giản và cĩ giới hạn. • MS-DOS là một hệ điều hành cĩ cấu trúc đơn giản, nĩ cung cấp những chức năng cần thiết nhất trong một khơng gian nhỏ nhất do sự giới hạn của phần cứng và khơng chia thành những đơn thể rõ rệt • Các chương trình ứng dụng cĩ thể truy cập trực tiếp các thủ tục nhập xuất cơ bản và ghi trực tiếp lên màn hình hay bộ điều khiển đĩa. Trang 15
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hình 2.2 • Hệ điều hành Unix bao gồm hai phần: hạt nhân và các chương trình hệ thống. hạt nhân được chia thành một chuỗi giao tiếp và driver thiết bị . • Những gì dưới lời gọi hệ thống và bên trên phần cứng là hạt nhân (kernel) • Hạt nhân cung cấp hệ thống tập tin, lập lịch CPU, quản trị bộ nhớ và các chức năng của hệ điều hành khác thơng qua lời gọi hệ thống. Hình 2.3 II.5.2 Cấu trúc theo lớp • Các phiên bản mới của Unix được thiết kế sử dụng phần cứng phức tạp hơn, do đĩ hệ điều hành được chia thành nhiều phần nhỏ hơn Trang 16
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Việc chia hệ thống thành nhiều phần nhỏ nĩ che dấu thơng tin, khơng cho chương trình của người sử dụng cĩ thể cài đặt những hàm truy xuất cấp thấp, thay vào đĩ là các lớp giao tiếp bên trong. • Hệ điều hành chia thành nhiều lớp. Lớp dưới cùng là phần cứng, lớp trên cùng là giao tiếp với người sử dụng. • Một lớp của hệ điều hành bao gồm một số cấu trúc dữ liệu và các hàm cĩ thể được gọi bởi lớp ở phía trên và bản than nĩ gọi những chức năng của lớp bên dưới. Mỗi lớp cài đặt chỉ sử dụng những thao tác do lớp dưới cung cấp. Lớp 6: Chương trình của người sử dụng Lớp 5: Driver thiết bị và bộ lập lịch Lớp 4: Bộ nhớ ảo Lớp 3: Kênh nhập xuất Lớp 2: Lập lịch CPU Lớp 1: Thơng dịch các chỉ thị Lớp 0: Phần cứng II.6 MÁY ẢO • Một máy ảo cung cấp một giao diện giống hệt các lớp phần cứng. • Hệ điều hành tạo ra các tiến trình ảo, mỗi việc thực hiện trên bộ xử lý với bộ nhớ ảo của nĩ. • Tài nguyên của máy tính thật được chia xẻ để tạo ra máy ảo. • Lập lịch CPU cũng được tạo ra như là người sử dụng cĩ bộ xử lý riêng. • Spooling và hệ thống file được cung cấp một card reader ảo và một line máy in ảo. Hình 2.4 • Thuận tiện, Bất lợi của máy ảo: - Khái niện máy ảo đưa ra chế độ bảo vệ tài nguyên hệ thống hồn chỉnh từ các máy ảo khác. Các máy ảo là độc lập nhau khơng trực tiếp chia xẻ tài nguyên. Trang 17
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Một hệ thống máy ảo là một phương tiện hồn chỉnh để nghiên cứu hệ điều hành và phát triển nĩ. Các hệ thống được phát triển trên máy ảo thay vì trên máy thật bởi vậy hệ thống trên máy thật khơng bị phá vỡ. - Khái niệm máy ảo đơi khi cũng khĩ thực hiện các yêu cầu chính xác như trên máy thật. II.7 QUÁ TRÌNH NẠP HỆ ĐIỀU HÀNH • Khi bật máy,chương trình Bootstrap – (là đoạn mã lưu trữ trong ROM ) được thi hành để kiểm tra các thiết bị máy tính cĩ hoạt động tốt khơng. Nếu mọi thiết bị đều sẵn sàng thì chương trình này đọc bootsector(đĩa mềm ) hay masterboot(đĩa cứng) vào bộ nhớ tại địa chỉ 0:7C00h và trao quyền điều khiển tại đây. • Trong bootsector bao gồm bảng tham số đĩa để mơ tả tổ chức vật lý và tổ chức logic trên đĩa và một chương trình mồi hệ điều hành. • Từ đĩ chương trình mồi hệ điều hành trong bootsector sẽ nạp các phần cịn lại của hệ điều hành (kernel) vào bộ nhớ và hệ điều hành bắt đầu hoạt động. • Đối với đĩa cứng thì cĩ dung lượng lớn, do đĩ một hệ điều hành cĩ thể khơng sử dụng hết dung lượng trên đĩa. Một đĩa cứng cĩ thể chứa đồng thời nhiều hệ điều hành, mỗi hệ điều hành được lưu trữ mỗi phân vùng riêng biệt và mỗi phân vùng gọi là partition. • Masterboot là sector đầu tiên trên đĩa cứng vật lý và bao gồm một bảng mơ tả các partition hiện cĩ trên đĩa như là sector bắt đầu, sector kết thúc, thuộc tính của các partition tương ứng. Ngồi ra masterboot cịn chứa một đoạn chương trình thực hiện đọc bảng tham số partition để xác định partition active. Từ đĩ nạp bootsector của partition active đĩ vào bộ nhớ và chuyển quyền điều khiển cho chương trình mồi hệ điều hành trong bootsector. CÂU HỎI 1. Khi xây dựng một hệ điều hành phải bao gồm những thành phần nào? Trình bày các chức năng của các thành phần đĩ? Liệt kê các thành phần khơng thể thiết được của một hệ điều hành đa nhiệm? 2. Các chương trình ứng dụng giao tiếp với hệ điều hành thơng qua thành phần nào của hệ điều hành? 3. Lời gọi hệ thống được cài đặt trong hệ điều hành bằng kỹ thuật gì? Việc truyền tham số cho lời gọi hệ thống bằng kỹ thuật nào? Trình bày kỹ thuật đĩ cho việc truyền tham trị và tham biến ? 4. Trình bày quá trình hệ điều hành được khởi động trên một hệ thống máy tính? Nếu sector đầu tiên trên ổ đĩa bị hỏng thì việc cài đặt hệ điều hành lên ổ đĩa đĩ cĩ được thực hiện khơng? Giải thích? 5. Trên một ổ đĩa cứng cĩ thể thể cài đặt được nhiều hệ điều hành khơng ? Vì sao? 6. Vì sao cĩ loại virus được gọi là B-Virus? Các biện pháp phịng và diệt loại B- Virus? 7. Cài đặt phần mềm máy ảo VMware workstation ? Trang 18
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CHƯƠNG III GIỚI THIỆU MỘT SỐ HỆ ĐIỀU HÀNH III.1 Hệ điều hành MS-DOS III.1.1 Giới thiệu • MS-DOS là một hệ điều hành đầu tiên chạy trên máy PC và được thiết kế bởi Microsoft • MS-DOS là hệ điều hành đơn nhiệm, một người ung , và cĩ cấu trúc đơn giản nên yêu cầu cấu hình máy thấp, bộ nhớ chính 640KB, giao diện theo cơ chế dịng lệnh • MS-DOS cĩ thể được cài đặt trên đĩa mềm hoặc đĩa cứng III.1.2 Cấu trúc hệ điều hành MS-DOS • Tổ chức của MS-DOS bao gồm: - Chương trình mồi hệ điểu hành được nạp vào bootsertor - Chương trình shell: giao tiếp giữa người sử dụng và hệ điều hành. - Chương trình chứa các chức năng cơ bản của hệ điều hành - Chương trình nhập xuất - Hệ thống các chương trình tiện ích. • Cấu trúc bộ nhớ 1024KB- 4GB Extended memory area High memory area (64KB) 640-1024KB Upper memory area 0-640KB Conventional Memory Hình 3.1 • Nội dung hệ điều hành - IO.SYS : hệ thống nhập xuất - MSDOS.SYS: hệ thống tập tin, giao tiếp dịng lệnh - CONFIG.SYS: cài đặt driver thiết bị Trang 19
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - COMMAND.COM : tập lệnh nội trú(internal) - AUTOEXEC.BAT : chứa tập lệnh DOS chạy tự động khi hệ điều hành bắt đầu III.1.3 Lịch sử phát triển • Năm 1980 IBM sản xuất máy tính cá nhân đầu tiên với bộ xử lý 8088, 16 bit và yêu cầu Microsoft thiết kế một hệ điều hành. MS-DOS ra đời 1981 • Version 1.0 ra đời 8/1981 bao gồm 4000 dịng hợp ngữ. - Quản lý 12K bộ nhớ - Được tổ chức thành 3 tập tin : IBMIO.COM- chứa hệ thống nhập xuất, IBMMS-DOS chứa hệ thống tập tin trên đĩa, chương trình giao tiếp, COMMAND.COM chứa các lệnh xử lý. - Được cài đặt trên đĩa mềm hai mặt 320KB • Version 2.0 : ra đời 3/1983 cung cấp hệ thống tập tin cấp bậc - Sử dụng đĩa cứng 10MB - Cho phép cài đặt các bộ điều khiển thiết bị trong tập tin CONFIG.SYS • Version 3.0 : ra đời 8/1984 quản lý được đĩa cứng 20MB, đĩa mềm 1.2MB, sử dụng đĩa ảo – lấy RAM làm đĩa ảo • Version 4.0 : ra đời 7/1988 hỗ trợ đĩa cứng lớn hơn 32MB đến 2GB, sử dụng vùng nhớ mở rộng đĩa ảo • Version 5.0 : ra đời 4/1991 tận dụng bộ nhớ mở rộng dùng để lưu trữ các device driver. • Version 6.0: 1993 cĩ các đặc điểm: - Tăng dung lượng đĩa sử dụng DBLSPACE - Tạo bộ nhớ cho đĩa với SmartDrv - Tối ưu bộ nhớ dùng Memmaker - Cứu tập tin bằng tiện ích Undelete - Kiểm tra đĩa bằng Scandisk III.1.4 Cài đặt hệ điều hành • Khởi động hệ điều hành DOS và thực hiện lệnh Format ổ đĩa: /s • Hoặc Sys ổ đĩa: III.1.5 Tập lệnh • Lệnh thơng tin hệ thống - DATE: Thiết lập hoặc hiển thị ngày hệ thống - TIME: Thiết lập hoặc hiển thị giờ hệ thống - PROMPT: Định nghĩa dấu nhắc hệ thống - SET: Định nghĩa biến mơi trường - VER: Hiển thị phiên bản hệ điều hành • Lệnh làm việc với đĩa - DISKCOPY: Sao chép đĩa mềm Trang 20
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - FORMAT: Định dạng đĩa - LABEL: xem, đặt nhã đĩa - VOL: Hiển thị nhãn và số serial của đĩa • Lệnh làm việc với thư mục - Ổ đĩa:↵ Chuyển ổ đĩa hiện hành - CHDIR hoặc CD : chuyển thư mục hiện hành - DIR: hiển thị nội dung thư mục - MKDIR hoặc MD: tạo thư mục mới - PATH: Định nghĩa đường dẫn - RMDIR hoặc RD: xố thư mục khác rỗng - TREE: Hiển thị cấu trúc cây thư mục • Thiết lập mơi trường - BUFFERS: Mơ tả số buffer đĩa - DEVICE: Cài đặt device driver - FILES: Số tập tin tối đa được mơ tả - LASTDRIVER: Số ổ đĩa tối đa • Sử dụng tập tin Batch - CALL : Gọi tập tin batch khác với tham số - ECHO: Hiển thị thơng điệp lên màn hình - FOR: Thực hiện lệnh DOS nhiều lần - GOTO: Nhảy đến một vị trí thi hành lệnh khác trong tập tin batch - IF: Kiểm tra điều kiện thi hành lệnh batch - PAUSE: Dừng lệnh bacth - REM: Khơng thi hành lệnh batch • Ví dụ tạo ra đĩa khởi động cài đặt driver CDROM - Copy các tập tin himem.sys, oakcdrom.sys, aspi2dos.sys, mscdex.exe, guest.exe, smartdrv.exe vào đĩa mềm. - Tạo tập tin config.sys [memu] menuitem=NONE, Khoi dong khong co CDROM Menuitem=CDROM, Khoi dong co CDROM Menuitem=USB, Khoi dong co USB [common] Device =himem.sys /testm:off Lastdrive=z [CDROM] Device=oakcdrom.sys /d:mscd001 [USB] Device=aspi2dos.sys /int/all [NONE] Trang 21
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Tạo tập tin autoexec.bat @echo off Goto %config% :CDROM Mscdex.exe /d:mscd001 Goto end :USB Guest.exe Goto end :NONE :END Smartdrv.exe III.2 Hệ điều hành Windows III.2.1 Giới thiệu • Windows được thiết kế bởi Microsoft. • Windows là hệ điều hành đa nhiệm, nhiều người dùng. • Giao diện người dung thân thiện, chế độ đồ họa • Cài đặt và thay đổi cấu hình hệ thống dễ dàng, khái niệm Plug and play • Cĩ tính ổn định cao, nếu cĩ tiến trình nào bị hỏng thì hệ thống huỷ bỏ tiến trình đĩ mà khơng ảnh hưởng đến tồn bộ hệ thống. • Cĩ tính bảo mật cao. III.2.2 Lịch sử phát triển • 11/1983 Microsoft tuyên bố sự ra đời hệ điều hành Windows • 11/1987 version 2.0 ra đời cĩ sự thay đổi về giao diện, cửa sổ cĩ thể chồng lên nhau, menu, dialog box • 5/1990 version 3.0 cho phép truy cập đến bộ nhớ 16Mb bộ nhớ. Cĩ Program Manager, Task Manager, File Manager. • 4/1992 version 3.1 hỗ trợ Multimedia( sound& music). Windows trở thành HĐH chiến lược của Microsoft. • 9/1995 Windows 95. Độc lập thiết bị, hỗ trợ CD-Rom, kỹ thuật Plug and play, hỗ trợ mạng cục bộ, truy xuất từ xa. Cải tiến giao diện đồ họa. • 1998 Windows 98 ra đời với hệ thống tập tin FAT32, hỗ trợ tên tập tin dài. Tiếp theo WindowsMe được tích hợp rất nhiều driver thiết bị • 2000 Windows 2K ra đời là sự lai ghép Windows 98 và Windows NT hỗ 2 hệ thống tập tin FAT32 và NTFS. Hỗ trợ tính bảo mật trên hệ thống tập tin NTFS. Hệ điều hành mạng Client/server. Cĩ 2 phiên bản Windows 2K server và professional • 2001 : Windows Xp ra đời với cải tiến giao diện. Hỗ trợ mạng Internet. Đây là hệ điều hành thơng dụng nhất hiện nay. III.2.3 Các tiện ích của Windows • Quản lý các driver thiết bị gắn vào máy tính: Device Manager Trang 22
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Xem cấu hình máy tính: dxdiag • Xem ,cài đặt các thơng số máy tính: control panel • Khởi động các dịch vụ HĐH: Administrator tool – Service • Cài đặt thêm các thành phần HĐH, gỡ bỏ các chương trình: Administrator Tool- Add or remove programs • Quản lý đĩa: Administrator Tool – Computer Management – Disk management • Tạo tài khoản người dùng: Administrator Tool – Computer Management- Local users and Groups • Xem huỷ các tiến trình đang chạy : Task manager • Bảo mật folder trên hệ thống NTFS • Chia xẻ folder III.3 Hệ điều hành Linux III.3.1 Đặc điểm • Multi: Tasking, Threading, User • Multi-platform: Chạy trên nhiều nền tảng phần cứng (khác Intel). • Open Source: Bao gồm cả kernel, drivers, cơng cụ phát triển • Hỗ trợ nhiều hệ thống File: Minix-1, Xenix, System V , MS-DOS, VFAT, FAT-32, ISO 9660 (CD-ROMs). EXT, và EXT2 • Multiple Networking Protocols: Các giao thức nền tảng được hỗ trợ bởi Kernel như: TCP, Ipv4, Ipv6, AX.25, X.25, IPX, v.v • Multiprocessor Simultaneous Multiprocessing (SMP) • Virtual Memory PagingMemory Protection: Hệ thống và các quá trình được bảo vệ lẫn nhau do đĩ khơng quá trình nào cĩ thể làm cho tồn hệ thống sụp đổ. • TCP/IP Networking: bao gồm ftp, telnet, • Client and Server Support: Bao gồm Netware, và Windows (SMB) • Ký hiệu Linux Kernel - Các phiên bản của Linux. Các phiên bản của HDH Linux được xác định bởi hệ thống số dạng X.YY.ZZ. Nếu YY là số chẵn => phiên bản ổn định. YY là số lẻ => phiên bản thử nghiệm - Ví dụ: - Kernel 2.4.2 - 2 là Số chính - .4 là số phụ , phiên bản ổn định - .2 Patch Level, phiên bản ổn định (nếu số lẻ là phiên bản đang thử nghiệm) III.3.2 Lịch sử phát triển • 1969 Kend Thompson thiết kế mơi trường nghiên cứu và phát triển chương trình đây chính là tiền thân HĐH Unix. Unix được viết bằng hợp ngữ • 1973 Unix được viết lại bằng ngơn ngữ C, dễ hiểu hơn 1975 Mã nguồn của Unix được cung cấp cho các trường đại học. Unix được nhiều cơng ty, tổ chức phát triển Trang 23
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Năm 1991 Linus Torvalds, sinh viên của đại học tổng hợp Helsinki, Phần lan, bắt đầu xem xét Minix, một phiên bản của Unix làm ra với mục đích nghiên cứu cách tạo ra một hệ điều hành Unix chạy trên máy PC với bộ vi xử lý Intel 80386 • Ngày 25/8/1991, Linus cho ra version 0.01 và thơng báo trên comp.os.minix của Internet về dự định của mình về Linux • 1/1992, Linus cho ra version 0.12 với shell và C compiler. Linus khơng cần Minix nữa để recompile HDH của mình. Linus đặt tên HDH của mình là Linux • 1994, phiên bản chính thức 1.0 được phát hành III.3.3 Cài đặt hệ điều hành • Các thao tác chuẩn bị cài đặt - Kiểm tra phần cứng máy tính 9 CPU, RAM, HDD: Tùy thuộc vào phiên bản Linux mà ta sẽ cài đặt. 9 Ví dụ: Để cài đặt RedHat Linux 6.0 ta cần cấu hình phần cứng tối thiểu như sau: CPU Intel 133MHz, 16MB RAM, 2Gb HDD Kiểm tra phần mềm - Phiên bản Linux sẽ cài đặt. - Ví dụ: RedHat Linux 7.3 ( phiên bản này yêu cầu CPU 233MHz ↑, 64MB RAM, 4Gb HDD • Phân hoạch đĩa cứng - Đối với hệ điều hành Linux nĩ địi hỏi phải cĩ ít nhất 2 partition của đĩa cứng để cĩ thể cài đặt thành cơng. - Partition thứ nhất: Dùng để chứa hệ điều hành. Dung lượng cho partition này tuỳ theo các package mà bạn cài đặt, thơng thường khoảng 2Gb là đủ. 9 Swap Partition: Dung lượng cho parttion chỉ cần bằng dung lượng của RAM là vừa đủ 9 Đặc biệt đối với các hệ thống Linux mà sau này muốn cài đặt hệ quản trị CSDL Oracle lên thì ta phải cho swap space lớn hơn hoặc bằng 500MB • Các chế độ cài đặt - Server - Workstation - Custom - Upgrade III.3.4 Tập lệnh • Quá trình khởi động RedHat Linux Tập tin đầu tiên mà hệ điều hành xem xét đến là /etc/inittab # Default runlevel. The runlevels used by RHS are: #0 – halt (Do NOT set initdefault to this) #1 – Single user mode #2 – Multiuser, without NFS #3 – Full multiuser mode #4 – unused Trang 24
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành #5 – X11 #6 – reboot (Do NOT set initdefault to this) id:3:initdefault: • Tập lệnh cơ bản - Login : Đăng ký sử dụng - Who : cho biết thơng tin về người sử dụng - Date: thơng báo về thời gian - Exit, logout : chấm dứt phiên làm việc - Passwd: thay đổi password - Man: giúp đỡ - Ls : Liệt kê nội dung thư mục - Cp: sao chép tập tin - Mv: Đổi tên một tập tin - Rm: xĩa tập tin - Cat: Hiển thị tập tin - Pwd: Cho biết thư mục hiện hành - Cd: Thay đổi thư mục hiện hành - Rmdir: xĩa thư mục - Chmod: thay đổi quyền tập tin - Chgrp: thay đổi nhĩm - Chown: thay đổi người sở hữu - df,du: thơng hệ thống tập tin - Useradd: Tạo người dùng - Usergroup:Tạo nhĩm người dùng - Su: chuyển đổi người dùng - Biên dịch chương trình c: gcc gcc -o output input.c - chown: change owner. Thay đổi quyền sở hữu tập tin cho user khác. Chỉ được chạy bởi root chown user1 hello.txt - chgrp: change group. Thay đổi quyền sở hữu tập tin cho nhĩm khác . Chỉ được chạy bởi root chgrp users hello.txt - chmod: change mode: Thay đổi quyền của file, file của ai người đĩ mới được thay đổi ( ngoại trừ root, cĩ quyền trên tất cả các file chmod g+r hello.txt chmod o-x hello.txt chmod u+xwr hello.txt Trang 25
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CÂU HỎI VÀ BÀI TẬP 1. Trình bày các đặc điểm của hệ điều hành DOS, Windows, Linux? Sực khác nhau giữa các hệ điều hành trên. 2. Cài đặt và sử dụng tập lệnh hệ điều hành MS-DOS? 3. Tạo đĩa CDRom cĩ khả năng khởi động hệ điều hành DOS nhận diện được CDROM và USB ? 4. Cài đặt và sử dụng tập lệnh hệ điều hành Windows? 5. Cài đặt và sử dụng tập lệnh hệ điều hành Linux? 6. Cài đặt nhiều hệ điều hành trên một máy tính? Trang 26
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành CHƯƠNG IV HỆ THỐNG QUẢN LÝ TẬP TIN IV.1 Khái niệm tập tin – thư mục • Tập tin Tập tin là đơn vị lưu trữ thơng tin của bộ nhớ ngồi. Các tiến trình cĩ thể đọc hay tạo mới tập tin. Các thơng tin trong tập tin là bền vững khơng bị ảnh hưởng bởi các xử lý ngoại trừ người sử dụng muốn xĩa. Tập tin được quản lý bởi hệ điều hành. • Thư mục Thư mục lưu trữ các tập tin theo một qui định. Một số hệ thống coi thư mục cũng như là tập tin. Hệ thống quản lý tập tin Các tập tin được quản lý bởi hệ điều hành với một cơ chế riêng gọi là hệ thống quản lý tập tin. • Hệ thống quản lý tập tin bao gồm: cách hiển thị , các yếu tố cấu thành tập tin, cách truy xuất, các thao tác trên tập tin và thư mục, IV.2 Mơ hình quản lý và tổ chức tập tin • Tập tin Tên tập tin: - Mỗi tập tin được quản lý bằng một tên. - Cách đặt tên tập tin mỗi hệ diều hành là khác nhau. Cấu trúc tập tin: - Dãy các byte khơng cĩ cấu trúc. - Dãy các record cĩ chiều dài cố định Kiểu tập tin: Các hệ điều hành hỗ trợ cho nhiều loại tập tin khác nhau - Tập tin thường: là tập tin text hay nhị phân chứa các thơng tin của người sử dụng. - Thư mục: là một loại tập tin hệ thống dùng lưu trữ cấu trúc hệ thống tập tin - Tập tin cĩ ký tự đặc biệt: liên quan đến nhập xất thơng qua các thiết bị nhập xuất Thuộc tính của tập tin: Các thơng tin về tập tin gọi là thuộc tính tập tin. Thuộc tính tập tin thường là các thơng in: - Bảo vệ: bảo vệ việc truy xuất từ người sử dụng - Mật khẩu: Mật khẩu cần thiết khi truy xuất. - Người tạo: Chỉ danh người tập tin. - Người sở hữu: Chỉ danh người sở hữu hiện tại. - Chỉ đọc: 0: đọc ghi, 1: chỉ đọc - Ẩn: 0 bình thường, 1 khơng hiển thị khi liệt kế - hệ thống: 0 bình thường, 1 tập tin hệ thống . Trang 27
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Khố: 0 khơng khĩa, 1 bị khĩa - Độ dài record: số byte trong một record - Thời gian tạo: ngày , giờ tạo tập tin - Thời gian truy xuất sau cùng: ngày , giờ truy xuất gần nhất - Thời gian thay đổi cuối cùng: ngày, giờ thay đổi tập tin - Kích thước hiện thời: Số byte tập tin • Thư mục Hệ thống thư mục cấp bậc: - Một thư mục thường chứa các entry. Mỗi entry thể hiện cho một tập tin( chứa các thuộc tính tập tin) - Số lượng thư mục trên mỗi hệ điều hành là khác nhau. - Một số hệ thống chỉ cĩ một thư mục duy nhất, nhưng một số hệ thống cĩ thư mục gốc, trong thư mục gốc cĩ các thư mục con và trong các thư mục con lại cĩ các thư mục con nữa. Đường dẫn - Trong hệ thống tổ chức thư mục cấp bậc theo hình cây cĩ hai cách để xác định một tập tin: đường dẫn thuyệt đối, đường dẫn tương đối. - Trong hầu hết các hệ điều hành tổ chức thư mục “.” và “ ” để chỉ ra thư mục hiện hành và thư mục cha. IV.3 Các chức năng hệ thống tập tin Một hệ thống tập tin thơng thường bao gồm các chức năng sau: - Tạo tập tin - Xố tập tin - Mở tập tin - Đọc, ghi tập tin - Tìm kiếm tập tin - Đổi tên tập tin - Tạo thư mục - Xĩa thư mục - Đổi tên thư mục IV.4 Cài đặt hệ thống tập tin • Cấu trúc tập tin - Mỗi tập tin hay thư mục (tập tin đặc biệt) được thể hiện bằng một Entry tập tin. Cấu trúc của Entry tập tin lưu trữ thơng tin về tập tin tương ứng. - Trước khi tập tin được đọc, ghi hệ thống phải biết đường dẫn do người sử dụng cung cấp từ đĩ định vị được cấu trúc entry của tập tin - Cấu trúc một entry tập tin: Trang 28
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hình 4.1 • Cấu trúc thư mục - Thư mục chứa các tập tin do đĩ chứa các entry của tập tin, kích thước mỗi Entry tuỳ thuộc mỗi hệ thống - Trong hệ thống quản lý tập tin cần phải định vị cấu trúc thư mục gốc, và các thư mục con Hình 4.2 • Quản lý vùng nhớ cịn trống trên đĩa Hệ thống quản lý tập tin cịn phải thực hiện lưu trữ các thơng tin về các ơ nhớ đã sử dụng chưa? Các ơ nhớ đã sử dụng thuộc về tập tin, thư mục nào? Phương pháp định vị liên tiếp: lưu trữ nội dung tập tin trên một dãy các khối liên tiếp nhau. - Ưu điểm : dễ cài đặt, dễ thao tác trên các tập tin - Khuyết điểm: Xử lý phức tạp khi kích thước tập tin thay đổi, sự phân mảnh trên đĩa gây lãng phí Phuơng pháp định vị bằng danh sách liên kết: Khơng cĩ sự phân mảnh vì các ơ nhớ được cấp phát hết, truy xuất chậm vì các ơ nhớ chứa nội dung tập tin nằm rải rác. Trang 29
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hình 4.3 IV.5 Hệ thống tập tin MS-DOS Cấu trúc tổng quát hệ thống tập tin MS-DOS bao gồm các cấu trúc: - Bảng tham số đĩa: lưu trữ các thơng tin về đĩa và các thơng tin cần thiết cho hệ thống tập tin. - Cấu trúc FAT(File Allocation Table): Lưu trữ các thơng tin địa chỉ các ơ nhớ cịn trống, các ơ nhớ nào thuộc về mỗi tập tin, - Cấu trúc thư mục gốc(ROOT):Cấu trúc thư mục gốc bao gồm các Entry của tập tin, thư mục con. - Vùng lưu trữ dữ liệu(Data): Lưu trữ nội dung tập tin và các cấu trúc thư mục con. Cấu trúc thư mục con tương tự cấu trúc thư mục gốc. Hình 4.5 • Bảng tham số đĩa(BPB): nằm trong bootsec bắt đầu tại địa chỉ offset 0 và chứa các thơng tin: Offset Kích Tên, ý nghĩa thước(B) +0h 3 JMP Lệnh nhảy đến đọan mồi HĐH 0h+3 8 Version Tên Cty, Version của HĐH +0Bh 2 SecSiz Số byte trong một sector +0Dh 1 ClustSiz Số sector của cluster Trang 30
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành +0Eh 2 ResSec Số Sector trước bảng FAT +10h 1 FatCnt Số bảng FAT cài đặt +11h 2 RootSiz Số Entry tối đa của ROOT +13h 2 TotSecs Tổng số sector đĩa 32MB . +3eh Bắt đầu đoạn CTmồi HĐH • Đối với đĩa cứng sector đầu tiên là masterboot chứa bảng tham số partition. Địa chỉ offset bảng partition bắt đầu tại 01BEh . Với một đĩa cứng cĩ thể chi thành 4 partition, mỗi partition được thể hiện bằng một Entry(16byte) cĩ cấu trúc như sau: Offset Kích Tên, ý nghĩa thước(B) +0h 1 Boot =0 khơng Active, =80h Active +1h 1 HdBeg Số mặt bắt đầu +2h 2 SecCylBeg Số cylinder bắt đầu(10bit) và sector bắt đầu (6bit) +4h 1 Sys =0Unknown, =1: Dos FAT 12bit, ; =4: Dos FAT 16bit +5h 1 HdEnd Số mặt kết thúc Trang 31
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành +6h 2 SecCylEnd Số cylinder kết thúc(10bit) và sector kết thúc (6bit) +8h 4 SecLogic Sector bắt đầu tương đối +0Ch 4 TotSecs Tổng số sector của partition • Cấu trúc Fat( file allocation table) - Khái niệm Cluster: Khi đĩa được format đơn vị nhỏ nhất trên đĩa là Sector. Đối đĩa cứng lớn cĩ nhiều sector mà Dos khơng thể quản lý được. Trong trường hợp này để giảm số sector cần quản lý bằng cách định nghĩa cluster là tập hợp các sector. Lúc này Dos chỉ quản lý Cluster thay vì sector. - Số hiệu các entry trong bảng Fat thể hiện cho các cluster cĩ số hiệu tương ứng trong vùng dữ liệu. - Fat thể hiện thơng tin về các cluster cịn trống hay khơng? Và các cluster đã sử dụng thuộc về tập tin nào. - Do Trong Fat 2 phần tử đầu tiên dành riêng khơng sử dụng nên số hiệu các entry được đánh số từ 2 trở đi. Chính vì vậy số hiệu cluster cũng được đánh số từ 2 trở đi. - Fat cĩ 3 loại : fat 12bit, fat 16bit, fat 32bit. Đối với Fat 12bit thì kích thước mỗi Entry trong Fat là 12 bit và quản lý được số cluster tối đa là (212 -2). Tương tự đối với Fat 16bit và Fat 32bit. - Fat 12bit dùng cho đĩa 2GB( HĐH Windows) - Nội dung của Fat o Dos quản lý tập tin bằng cách giá trị entry của cluster này chứa giá trị là số thứ tự entry tiếp theo nĩ, cứ thế các cluster của một tập tin tạo thành một chuỗi cho đến khi gặp dấu hiệu kết thúc tập tin. o Tuỳ thuộc vào loại fat 12bit hay 16bit các entry cĩ giá trị như sau: 0(000) : Cluster tương ứng số hiệu entry cịn trống (0)002- (F)FEF : Cluster đang chứa dữ liệu của một tập tin nào đĩ, giá trị là của nĩ là số hiệu cluster kế tiếp (F)FF0 – (F)FF6 : Dành riêng khơng sử dụng (F)FF7 : Cluster hỏng (F)FF8- (F)FFF : Cluster cuối cùng của tập tin Trang 32
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Một ví dụ nội dung của Fat: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 03 04 05 Ff 00 00 09 0a 0b 15 00 00 00 00 01 00 00 00 00 00 16 17 19 f7 1a 1b Ff 00 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Hình 4.5 Tập tin myfile.txt dài 10 cluster: 8,9,0a,0b,15,16,17,19,1a,1b Cluster 18h : đánh dấu hỏng Cluster 2,3,4,5: thuộc một tập tin nào đĩ Các cluster khác cịn trống Tìm các cluster của một tập tin PointType ReadEntryFile(unsigned int ClustBegin) { PointType ListClust, last; ListClust=last=NULL; unsigned clust; clust=ClustBegin; while(1) { InsertLast(ListClust, clust); clust=NextEntry(clust) if (clust==0x0fff) break; } Trang 33
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành return ListClust; } Đọc nội dung các Entry trong Fat: - Nếu Fat 16 bit thì địa chỉ entry kế tiếp bằng địa chỉ entry hiện thời +2 - Nếu Fat 12 bit : Xét 3 byte một : số hiệu entry chẵn là 12 bit thấp và số hiệu entry lẻ là 12 bit cao - Hình 4.6 Hình 4.7 Các biến dùng chung: unsigned X, X1, Addr; Trường hợp số hiệu Entry Chẵn X = FAT[Addr]; 00000000 X1= FAT[Addr+1]; 00000000 X1= X1 <<8; 00000000 X = X + X1; X = X & 0x0FFF; 0000 Trường hợp số hiệu Entry lẻ X = FAT[Addr]; 00000000 X1= FAT[Addr+1]; 00000000 X1= X1 <<8; 00000000 X = X + X1; Trang 34
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành X = X >>4; 0000 Hàm đọc nội dung Entry Fat 12bit unsigned NextEntry ( unsigned Index) { unsigned X, X1, Addr; Addr= (Index *3 )/ 2; X = FAT[Addr]; X1= FAT[Addr+1]; X1= X1 >4; return X; } • Cấu trúc một Entry Trong thư mục gốc hay thư mục con: Mỗi Entry thể hiện cho một tập tin hay thư mục con và lưu trữ các thơng tin cần thiết. Kích thước Entry là 32 byte Offset Kích thước Nội dung +0h 8 Tên tập tin hay thư mục +8h 3 Phần mở rộng tên tập tin +0bh 1 Thuộc tính tập tin +0ch 0ah Dành riêng khơng sử dụng +16h 2 Thời gian tạo +18h 2 Ngày tạo +1ah 2 Số hiệu cluster đầu tiên +1ch 4 Kích thước tập tin (bytes) Trang 35
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Byte đầu tiên của entry thể hiệc các thơng tin sau: o 0: Entry này cịn trống o . : Thư mục cha o 0E5 : Entry của tập tin này tạm thời bị xĩa o Ký tự bất kỳ : tên của một tập tin - Diễn dải byte thuộc tính: - Diễn dải ngày tạo, giờ tạo 7bit : năm 4bit: tháng 5bit: ngày 5bit: giờ 6bit: phút 5bit: giây • Cấu trúc dữ liệu cài đặt: Hình 4.8 - Khai báo bảng tham số đĩa Typedef struct { unsigned char JMP[3]; unsigned char Ver[8]; unsigned SecSiz; unsigned char ClustSiz; unsigned ResSec; unsigned char FatCnt; unsigned RootSiz; unsigned TotSec; unsigned char Media; unsigned FatSiz; unsigned TrkSec; unsigned HeadCnt; unsigned HidSec; }EntryBPB; typedef union { unsigned char Sector[512]; Trang 36
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành EntryBPB Entry; }UnionBPB; Hình 4.9 Ví dụ #include #include Typedef struct { }EntryBPB Typedef Union { }UnionBPB Int main() { UnionBPB bpb; ReadDisk (0,1, bpb.sector); cout<<bpb.Entry.secsiz; cout <<bpb.Entry.Clustsiz; . Return 1; } - Khai báo kiểu thời gian tạo tập tin, thư mục typedef struct { unsigned S:5 ; unsigned M: 6 ; unsigned H:5; }Time; typedef union { Trang 37
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành unsigned intTime; Time T ; }UnionTime; - Khai báo kiểu ngày tháng năm tạo tập tin, thư mục typedef struct { unsigned D: 5 ; unsigned M: 6 ; unsigned Y:7; }Date; typedef union { unsigned intDate; Date Day ; }UnionDate; - Khai báo cấu trúc byte thuộc tính tập tin typedef struct { unsigned char ReadOnly : 1 ; unsigned char Hidden : 1 ; unsigned char System : 1 ; unsigned char Volume : 1 ; unsigned char SubDir : 1 ; unsigned char Archive : 1 ; unsigned char DR : 2 ; }Attrib; typedef union { unsigned char charAtt; Attrib Attr ; }UnionAttrib; - Khai báo cấu trúc một Entry tập tin typedef struct { unsigned char FileName[8] ; unsigned char Ext[3] ; UnionAttrib Attribute ; unsigned char DR[10] ; UnionTime CreateTime ; UnionDate CreateDate ; unsigned ClustBegin ; long FileSize; }EntryDir; Trang 38
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành typedef union { unsigned char Entry[32]; EntryDir EntDir ; }UnionDir; - Danh sách liên kết typedef struct Node{ void *Data; Node *Next; }NodeType; typedef NodeType *PointerType; Hình 4.10 Hàm InsertLast int InsertLast (PointerType &List, PointerType &Last, void* Item) { PointerType Temp; Temp= new NodeType; if( !Temp) return 0; Temp->Data = Item; Temp->Next = NULL; if(List==NULL) List=Temp; else Last->Next=Temp; Last = Temp; return 1; } - Hàm đọc Sector từ đĩa với số hiệu theo kiểu vật lý int ReadDiskBios(unsigned char *Buff,unsigned Side, unsigned TrackSec, unsigned Sector, unsigned SecNum) Trang 39
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành { union REGS u, v; struct SREGS s; int k, i=0; v.x.cflag=1; while(i >2; X=X & 0X00FF; X=X | Sector; Track = Track <<8; TrackSec=Track | X; //Track ( 10), Sector(6) if ( ReadDiskBios(Buff, Side, TrackSec, Sector, SecNum)) return 1; else return 0; } IV.6 Hệ thống tập tin Unix • Cấu trúc tổng quát Trang 40
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hình 4.11 - BootSector : chứa chương trình mồi hệ điều hành - Khối đặc biệt: lưu trữ các thơng tin quan trọng về tồn bộ hệ thống tập tin, (số I- node, số khối đĩa, dãy các ơ nhớ cịn trống trên đĩa, ) - Sau khối đặc biệt là bảng I-Node được đánh số từ 1 đến tối đa. - Khối dữ liệu là vùng nhớ lưu trữ nội dung tập tin, thư mục. • Cách quản lý các ơ nhớ cịn trống trong khối dữ liệu: Dùng phương pháp Bitmap: Với đĩa cĩ n ơ nhớ sẽ được ánh xạ thành n bit với giá trị 1 là cịn trống, giá trị 0 là đã chứa dữ liệu. Như vậy một đĩa 20MB cần 20000 bit để lưu trữ thơng tin. Chiếm khoảng 3 ơ nhớ. Hình 4.11 • Tổ chức lưu trữ tập tin: - Mỗi file trong unix tương ứng với một I-Node. Một I-Node cĩ kích thước 64byte bao gồm các thơng tin về file: file Node, quyền sở hữu file của người sử dụng, quyền sở hữu nhĩm, kích thước file, thời điểm tạo,thời điểm truy cập sau cùng, thời điểm thay đổi sau cùng, địa các ơ nhớ chứa nội dung, - Phần đánh địa chỉ các ơ nhớ nội dung tập tin được chia thành 2 phần: phần đầu gồm 10 pt chứa được 10 địa chỉ ơ nhớ. Phần thứ 2 gồm 3 con trỏ gián tiếp: Single indirect, double indirect, triple indirect. - Đối với tập tin cĩ kích thước nhỏ hơn 10 ơ nhớ dữ liệu thì các con trỏ gián tiếp khơng được sử dụng để ghi địa chỉ. Trang 41
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Khi một file cĩ kích thước lớn hơn 10 ơ nhớ dữ liệu thì con trỏ single indirect được sử dụng chỉ đến một ơ nhớ dành riêng, ơ nhớ này lại chứa 256 địa chỉ của ơ nhớ dữ liệu. - Tương tự con trỏ double chỉ đến một ơ nhớ chứa 256 địa chỉ ơ nhớ và mỗi ơ nhớ này lại chứa 256 địa chỉ ơ nhớ dữ liệu. - Một file lớn nhất sử dụng cả 3 con trỏ gián tiếp là 16 GB. Hình 4.13 • Cấu trúc thư mục Cấu trúc thư mục được sử dụng trong Unix vơ cùng đơn giản, mỗi entry bao gồm tên tập tin, số hiệu I-Node của file. Mỗi Entry cĩ kích thước 16 byte: I-Node Tên tập tin Hình 4.14 Khi một file được mở , hệ thống file phải xác định vị trí khối dữ liệu trên đia nhờ vào đường dẫn được cung cấp. Ví dụ: cách truy tìm file dựa vào đường dẫn được cung cấp : /usr/ast/mbox Trước hết đọc I-Node của thư mục gốc – là I-Node đầu tiên trong bảng I- Node Trang 42
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Đọc từng entry trong thư mục gốc so sánh với thư mục usr từ đĩ tìm ra I- node của thư mục usr. Từ I-node này tiếp tục xác định các entry trong thư mục và so sánh với ast khi đĩ tìm được I-node của /usr/ast. Tiếp tục tương tự sẽ tìm được I-node của /usr/ast/mbox Hình 4.15 CÂU HỎI VÀ BÀI TẬP 1. Trình bày các thành phần cấu trúc hệ thống tập tin? 2. Trình các chức năng hệ thống tập tin? 3. Trình bày cấu trúc tổ chức hệ thống tập tin MS-DOS 4. Trình bày cấu trúc tổ chức hệ thống tập tin Unix 5. Trình bày sự khác biệt giũa 2 cấu trúc tổ chức hệ thống tập tin MS-DOS và Unix? 6. Viết chương trình đọc và xuất ra màn hình bảng tham số đĩa mềm 1.44mb? 7. Viết chương trình xem nội dung thư mục gốc ? 8. Viết chương trình xem nội dung thư mục bất kỳ ? 9. Viết chương trình xem nội dung tập tin ? 10. Viết chương trình xố tập tin , phục hồi tập tin ? 11. Viết chương trình copy tập tin ? 12. Viết chương trình sắp xếp đĩa (dồn cluster) ? 13. Viết chương trình xố các cluster mồ cơi ? 14. Viết chương trình tạo thư mục? CHƯƠNG V HỆ THỐNG QUẢN LÝ NHẬP XUẤT Trang 43
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành V.1 Các khái niệm Một trong các chức năng chính của hệ điều hành là hệ thống quản lý thiết bị nhập xuất. Hệ điều hành chỉ thị cho các thiết bị, kiểm sốt các ngắt và lỗi. Ngồi ra hệ điều hành phải cung cấp cơ chế giao tiếp đơn giản và tiện dụng giữa các thiết bị và các phần cịn lại của hệ thống. Việc giao tiếp này phải độc lập với thiết bị. V.1.1 Thiết bị nhập xuất Cĩ nhiều cách nhìn khác nhau về thiết bị nhập xuất. Đối với các lập trình viên thì quan niệm các thiết bị nhập xuất là các lệnh thực thi được trên các thiết bị nhập xuất, chúng thực thi các chức năng gì và thơng báo lỗi của chúng bao gồm những gì. V.1.2 Thiết bị logic Mục tiêu chung của thiết bị logic là dễ biểu diễn. Thiết bị logic được tổ chức thành nhiều lớp. Lớp dưới cùng giao tiếp với phần cứng, lớp trên cùng giao tiếp tốt , thân thiện với người sử dụng. Thiết bị logic độc lập với thiết bị ví dụ như cĩ thể viết chương trình truy xuất file trên đĩa mềm hay đĩa cứng mà khơng cần mơ tả chương trình cho từng loại thiết bị. Ngồi ra thiết bị logic phải cĩ khả năng kiểm sốt lỗi. Thiết bị logic được tổ chức thành 4 lớp: Kiểm sốt lỗi, điều khiển thiết bị, phần mềm hệ điều hành độc lập thiết bị, phần mềm người sử dụng. V.1.3 Hệ thống quản lý nhập/ xuất Hệ thống quản lý nhập xuất được tổ chức theo từng lớp, mỗi lớp cĩ một chức năng nhất định và các lớp cĩ giao tiếp với nhau theo sơ đồ sau: Các lớp Chức năng nhập xuất Xử lý của người sử Tạo lời gọi nhập xuất, định dạng nhập xuất dụng Phần mềm độc lập Đặt tên, bảo vệ, tổ chức khối, bộ đệm, định vị thiết bị Điều khiển thiết bị Thiết lập thanh ghi thiết bị, kiểm tra trạng thái Kiểm sốt ngắt Báo cho driver khi nhập xuất hồn tất Phần cứng Thực hiện thao tác nhập xuất V.2 Mơ hình tổ chức và quản lý việc nhập xuất V.2.1 Mơ hình V.2.1.1 các thiết bị nhập xuất Trang 44
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Các thiết bị nhập xuất cĩ thể chia tương đối thành 2 loại thiết bị khối và thiết bị thuần tự: - Thiết bị khối là thiết bị mà thơng tin được lưu trữ trong các khối cĩ kích thước cố định và được lưu trữ trong những khối cĩ kích thước cố định và được định vị bởi địa chỉ. Kích thước thơng thường của một khối khoảng từ 128 byte đến 1024 byte. Đặc điểm của thiết bị khối là chúng cĩ thể được truy xuất từng khối riêng biệt và chương trình cĩ thể cĩ thể truy xuất một khối bất kỳ nào đĩ. Đĩa là một ví dụ truy xuất khối. - Một dạng thiết bị thứ hai là thiết bị tuần tự. Ở dạng thiết bị này việc gởi và nhận thơng tin là chuỗi các bits, khơng cĩ xác định địa chỉ và khơng thể tìm kiếm. Màn hình, bàn phím, máy in, card mạng, mouse là các thiết bị tuần tự. V.2.1.2 Điều khiển thiết bị Một đơn vị nhập xuất thường được chia làm hai thành phần chính là thành phần cơ và thành phần điện tử. Thành phần diện tử được gọi là bộ phận điều khiển thiết bị hay bộ tương thích, trong các máy tính thường được gọi là card. Một bộ phận điều khiển thường cĩ bộ phận kết nối trên chúng để cĩ thể gắn thiết bị lên đĩ. Một bộ phận điều khiển cĩ thể quản lý được 2 hay 4 , 8 thiết bị khác nhau. Nếu giao tiếp giữa thiết bị và bộ phận điều khiển là các chuẩn như ANSI, IEEE, hay ISO thì nhà sản xuất thiết bị và bộ điều khiển phải tuân theo chuẩn đĩ. Giao tiếp giữa bộ điều khiển và thiết bị là giao tiếp ở mức thấp. Ổ đĩa Giao tiếp thiết bị Máy in CPU Memory Bộ điều khiển đĩa Bộ điều khiển Printer Bus hệ thống Hình 5.1 V.2.1.3 DMA Đa số các loại thiết bị, đặc biệt là các thiết bị dạng khối hỗ trợ cơ chế DMA (Direct Memory Access). Để hiểu cơ chế này trước hết phải xét quá trình đọc đĩa mà khơng cĩ DMA. Trước tiên bộ điều khiền đọc tuần tự các khối trên đĩa, từng bit từng bit cho tới khi tồn bộ khối được đưa vào buffer của bộ điều khiển. sau đĩ máy tính thực hiện checksum để đảm bảo khơng cĩ lỗi xảy ra. Tiếp theo bộ điều khiển tạo ra một ngắt để báo cho CPU biết. CPU lấy dữ liệu từ buffer chuyển về bộ nhớ chính bằng cách tạo ra 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, do đĩ để tối ưu dùng cơ chế DMA. V.2.1 Thiết bị logic V.2.1.1 Kiểm sốt ngắt Trang 45
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Ngắt là một hiện tượng phức tạp. Nĩ phải cần được che dấu sâu trong hệ điều hành,và một phần ít của hệ thống biết về chúng. Cách tốt nhất để che dấu chúng là hệ điều hành cĩ mọi tiến trình thực hiện thao tác nhập xuất cho tới khi hồn tất mới tạo ra một ngắt. Tiến trình cĩ thể tự khố lại bằng cách thực hiện lệnh WAIT theo một biến điều kiện hoặc RECEIVE theo một thơng điệp. V.2.1.2 Device Drivers Tất cả các đoạn mã độc lập thiết bị đều được chuyển đến device driver. Mỗi device drivers kiểm sốt mỗi loại thiết bị, nhưng cũng cĩ khi là một tập hợp các thiết bị liên quan mật thiết với nhau. Device drivers phát ra các chỉ thị và kiểm tra xem chỉ đĩ cĩ được thực hiện chính xác khơng. Ví dụ driver của đĩa là phần duy nhất của hệ điều hành kiểm sốt bộ điều khiển đĩa. Nĩ quản lý sector, track, cylinder, head, giúp cho các thao tác đĩa được thực hiện tốt. V.2.1.3 Phần mềm nhập xuất độc lập thiết bị Mặc dù một số phần mềm nhập xuất mơ tả thiết bị nhưng phần lớn chúng là độc lập với thiết bị. Ranh giới chính xác giữa driver và phần mềm độc lập thiết bị là độc lập về mặt hệ thống, bởi vì một số hàm mà được thi hành theo kiểu độc lập thiết bị cĩ thể được thi hành trên driver vì lý do hiệu quả hay những lý do khác nào đĩ. V.2.1.4 Phần mềm nhập xuất phạm vi người sử dụng Hầu hết các phần mềm nhập xuất đều ở bên trong của hệ điều hành và một phần nhỏ của chúng chứa các thư viện liên kết với chương trình của người sử dụng ngay cả những chương trình thi hành bên ngồi hạt nhân. Lời gọi hệ thống bao gồm lời gọi hệ thống nhập xuất thường được thực hiện bởi các hàm thư viện. Khơng phải tất cả các phần mềm nhập xuất đều chứa hàm thư viện, cĩ một loại quan trọng khác gọi là hệ thống spooling dùng để khai thác tối đa thiết bị nhập xuất trong hệ thống đa chương. V.2.2 Các chức năng V.2.2.1 Điều khiển thiết bị nhập xuất Chức năng của bộ điều khiển là giao tiếp với hệ điều hành vì hệ điều hành khơng thể truy xuất trực tiếp với thiết bị. Việc thơng tin thơng qua hệ thống đường truyền gọi là bus. Cơng việc của bộ điều khiển là chuyển đổi dãy các bit tuần tự trong một khối các byte và thực hiện sửa chữa nếu cần thiết. Thơng thường khối các byte được tổ chức thành từng bit và đặt trong buffer của bộ điều khiển. Sau hiện checksum nội dung của buffer sẽ được chuyển vào bộ nhớ chính. Ví dụ bộ điều khiển cho màn hình đọc các byte của ký tự để hiển thị trong bộ nhớ và tổ chức các tín hiệu để điều khiển các tia của CRT để xuất trên màn hình bằng cách quét các tia dọc, ngang. Nếu khơng cĩ bộ điều khiển, lập trình viên hệ điều hành phải tạo thêm chương trình điều khiển tín hiệu analog cho đèn hình. Với bộ điều khiển, hệ điều hành chỉ cần khởi động chúng với một tham số như số ký tự trên một dịng, số dịng trên màn hình và bộ điều khiển sẽ thực hiện điều khiển các tia. Trang 46
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Mỗi bộ điều khiển cĩ một số thanh ghi để liên lạc với CPU. Trên một số máy tính, các thanh ghi này là một phần của bộ nhớ chính tại một địa chỉ xác định gọi là ánh xạ bộ nhớ nhập xuất. Hệ máy PC dành ra một vùng địa chỉ đặc biệt gọi là địa chỉ nhập xuất và trong đĩ được chia làm nhiều đoạn, mỗi đoạn cho một loại thiết bị. Bộ điều khiển nhập xuất Địa chỉ nhập xuất Vector ngắt Đồng hồ 040 – 043 8 Bàn phím 060 – 063 9 RS232 phụ 2F8 – 2FF 11 Đĩa cứng 320 – 32F 13 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ệ điều hành thực hiện nhập xuất bằng cách ghi lệnh lên các thanh ghi của bộ điều khiển. Ví dụ bộ điều khiển đĩa mềm của IBMPC chấp nhận 15 lệnh khác nhau như Read, Write, Seek, Format, một số lệnh cĩ tham số và các tham số cũng được nạp vào thanh ghi. Khi một lệnh đã được chấp nhận, CPU sẽ rời bộ điều khiển để thực hiện cơng việc khác. Sau khi thực hiện xong, bộ điều khiển phát sinh một ngắt để báo hiệu cho CPU biết và đến lấy kết quả được lưu giữ trong các thanh ghi. V.2.2.2 DMA Cơ chế DMA giúp cho CPU khơng bị lãng phí thời gian. Khi sử dụng, CPU gửi cho bộ điều khiển một số các thơng số như địa chỉ trên đĩa của khối, địa chỉ trong bộ nhớ nơi định vị khối, số lượng byte dữ liệu để chuyển. Sau khi bộ điều khiển đã đọc tồn bộ dữ liệu từ thiết bị vào buffer của nĩ và kiểm tra checksum. 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ố byte phải chuyển. Quá trình này lập cho tới khi số byte phải chuyển bằng 0, và bộ điều khiển tạo một ngắt. Như vậy khơng cần phải copy khối vào trong bộ nhớ, nĩ đã hiện hữu trong bộ nhớ. V.2.2.3Thiết bị Logic Kiểm sốt ngắt Khi một ngắt xảy ra, hàm xử lý ngắt khởi tạo một tiến trình mới để xử lý ngắt. Nĩ sẽ thực hiện một tín hiệu trên biến điều khiển và gửi những thơng điệp đến cho các tiến trình bị khố. Tổng quát, chức năng của ngắt là làm cho một tiến trình đang bị khố được thi hành trở lại. Device Driver Chức năng của device driver là nhận những yêu cầu trừu tượng từ phần mềm nhập xuất độc lập thiết bị ở lớp trên, và giám sát yêu cầu này thực hiện. Nếu driver đang rãnh, nĩ sẽ thực hiện ngay yêu cầu, ngược lại yêu cầu đĩ sẽ được đưa vào hàng đợi. Trang 47
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Ví dụ bước đầu tiên của yêu cầu nhập xuất đĩa là chuyển từ trừu tượng thành cụ thể. Driver của đĩa phải biết khối nào cần đọc, kiểm tra sự hoạt động của motor đĩa, xác định ví trí của đầu đọc đã đúng chưa. Nghĩa là device driver phải xác định được những thao tác nào của bộ điều khiển phải thi hành và theo trình tự nào. Một khi đã xác định được chỉ thị cho bộ điều khiển, nĩ bắt đầu thực hiện bằng cách chuyển lệnh vào thanh ghi của bộ điều khiển thiết bị. Bộ điều khiển cĩ thể nhận một hay nhiều chỉ thị liên tiếp và sau đĩ tự nĩ thực hiện khơng cần sự trợ giúp của hệ điều hành. Trong khi lệnh thực hiện. Cĩ hai trường hợp xảy ra: một là device driver phải chờ cho tới khi bộ điều khiển thực hiện xong bằng cách tự khố lại cho tới khi một ngắt phát sinh mở khố cho nĩ. Hai là hệ điều hành chấm dứt mà khơng chờ, vì vậy driver khơng cần thiết phải khố. Sau khi hệ điều hành hồn tất việc kiểm tra lỗi và nếu mọi thứ đều ổn driver sẽ chuyển dữ liệu cho phần mềm độc lập thiết bị. Cuối cùng nĩ sẽ trả về thơng tin về trạng thái hay lỗi cho nơi gọi và nếu cĩ một yêu cầu khác ở hành đợi, nĩ sẽ thực hiện tiếp, nếu khơng nĩ sẽ khố lại chờ đến yêu cầu tiếp theo. Phần mềm nhập xuất độc lập thiết bị Giao tiếp đồng nhất cho device driver Đặt tên thiết bị Bảo vệ thiết bị Cung cấp khối độc lập thiết bị Tổ chức buffer Định vị lưu trữ trên thiết bị khối Cấp phát và giải phĩng thiết bị tận hiến Báo lỗi Các chức năng của phần mềm nhập xuất độc lập thiết bị Chức năng cơ bản của phần mềm nhập xuất độc lập thiết bị là những chức năng chung cho tất cả các thiết bị và cung cấp một giao tiếp đồng nhất cho phần mềm với người sử dụng. Trước tiên phải cĩ chức năng tạo một ánh xạ giữa các thiết bị ví dụ với Unix tên /dev/tty() dành riêng để mơ tả I-node cho một file đặc biệt, và I-node này chứa sĩ thiết bị chính, được dùng để xác định driver thích hợp và số thiết bị hư, được dung để xác định các tham số cho driver để cho biết là đọc hay ghi. Thứ hai là bảo vệ thiết bị là cho phép hay khơng cho phép người sử dụng truy xuất thiết bị. Các hệ điều hành cĩ hay khơng chức năng này. Thứ ba là cung cấp khối dữ liệu độc lập thiết bị vì ví dụ những đĩa khác nhau sẽ cĩ kích thước sector khác nhau và điều này sẽ gây khĩ khăn cho các phần mềm người sử dụng ở lớp trên. Chức năng này cung cấp các khối dữ liệu logic độc lập với kích thước sector vật lý. Thứ tư là cung cấp buffer để hỗ trợ cho đồng bộ hố quá trình hoạt động của hệ thống ví dụ buffer của bàn phím. Thứ năm là định vị lưu trữ trên các thiết bị khối Trang 48
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Thứ sáu là cấp phát và giải phĩng các thiết bị tận hiến. Cuối cùng là thơng báo lỗi cho lớp bên trên từ các lỗi do device driver báo về. Phần mềm nhập xuất phạm vi người sử dụng Các hàm thư viện chuyển các tham số thích hợp cho lời gọi hệ thống và hàm thư viện thực hiện việc định dạng cho nhập và xuất như lệnh printf trong c. Thư viện nhập xuất chuẩn chứa một số hàm cĩ chức năng nhập xuất và tất cả chạy như chương trình người sử dụng. Chức năng của spooling là tránh trường hợp một tiến trình đang truy xuất thiết bị, chiếm giữ thiết bị nhưng sau đĩ khơng làm gì cả trong một khoảng thời gian và như vậy các tiến trình khác bị ảnh hưởng vì khơng thể truy xuất thiết bị đĩ. Một ví dụ của spooling device là line printer. Spooling cịn được sử dụng trong hệ thống mạng như hệ thống email chẳng hạn. CÂU HỎI VÀ BÀI TẬP 1. Trình bày các khái niệm thiết bị nhập xuất, thiết bị logic? 2. Trình bày hệ thống quản lý nhập xuất? 3. Trình bày mơ hình quản lý nhập xuất? 4. Trình bày các chức năng hệ thống nhập xuất? CHƯƠNG VI HỆ THỐNG QUẢN LÝ TIẾN TRÌNH Trang 49
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành VI.1 Khái niệm tiến trình • Trong hệ thống đa chương cĩ thể thể thực hiện nhiều tác vụ đồng thời. • Việc thực hiện đồng thời này được hiện bằng cách chuyển đổi CPU qua lại giữa các chương trình. Điều này tạo cảm giác cĩ nhiều chương trình thực hiện đồng thời. • Trong hệ thống như vậy tất cả phần mềm được tổ chức thành một số tiến trình. • Một tiến trình là một chương trình đang được xử lý, sở hữu con trỏ lệnh , tập các thanh ghi, biến và để hồn thành nhiệm vụ của mình một tiến trình phải sử dụng các tài nguyên máy tính như CPU, bộ nhớ chính, các tập tin và thiết bị nhập xuất. • Ý tưởng là cĩ thể xem như mỗi tiến trình sở hữu một CPU ảo cho riêng mình, nhưng trong thực tế chỉ cĩ một bộ xử lý thật sự được chuyển đổi qua lại giữa các tiến trình. • Hệ điều hành chịu trách nhiệm sử dụng một thuật tốn điều phối để quyết định thời điểm cần dừng một tiến trình để thực hiện một tiến trình khác VI.2 Các trạng thái của tiến trình • Trạng thái của một tiến trình tại một thời điểm được xác định bằng hoạt động hiện thời của tiến trính đĩ. • Tại một thời điểm một tiến trình cĩ thể nhận một trong các trạng thái sau đây: - Mới tạo: Tiến trình đang được tạo lập. - Running: các chỉ thị của tiến trình đang được xử lý. - Blocked: Tiến trình chờ được cấp phát một tài nguyên hay chờ một sự kiện nào đĩ xảy ra. - Ready: Tiến trình chờ cấp phát CPU để xử lý. - Kết thúc : Tiến trình hồn tất xử lý. • Mơ hình chuyển đổi giữa các trạng thái: Hình 6.1 (1) Tiến trình mới tạo được đưa vào hệ thống. (2) Bộ lập lịch cấp phát cho tiến trình một khoảng thời gian sử dụng CPU (3) Tiến trình kết thúc (4)Tiến trình yêu cầu một tài nguyên nhưng chưa được đáp ứng hoặc phải chờ thao tác nhập xuất. (5) Bộ lập lịch thu hồi CPU và cấp phát cho tiến trình khác Trang 50
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành (6) Tài nguyên mà tiến trình yêu cầu đã được cấp phát hay thao tác nhập xuất đã hồn tất. VI.3 Cài đặt tiến trình • Hệ điều hành quản lý các tiến trình trong hệ thống thơng qua khối quản lý tiến trình (Process Control Block- PCB). • PCB là một vùng nhớ lưu trữ các thơng tin mơ tả cho tiến trình như sau: - Chỉ danh của tiến trình: Để phân biệt các tiến trình - Trạng thái tiến trình: Xác định hoạt động hiện hành của tiến trình 9 Ngữ cảnh của tiến trình: quản lý các tài nguyên của tiến trình: 9 Trạng thái CPU : nội dung các thanh ghi. 9 Bộ nhớ chính: Danh sách các ơ nhớ được cấp phát cho tiến trình. 9 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. 9 Tài nguyên tạo lập: Danh sách tài nguyên do tiến trình tạo lập. - 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: 9 Tiến trình cha: Tiến trình tạo lập tiến trình này. 9 Tiến trình con: Các tiến trình do tiến trình này tạo lập. 9 Độ ưu tiên: Giúp bộ lập lịch lựa chọn tiến trình được cấp pháp CPU. - Thơng tin thống kê: thống kê về hoạt động của tiến trình: thời gian sử dụng CPU, thời gian chờ. VI.4 Tiểu trình • Trong hệ điều hành mỗi tiến trình cĩ khơng gian địa chỉ và cĩ một dịng xử lý, nhưng đơi khi người sử dụng mốn cĩ nhiều dịng xử lý cùng chia xẻ trong cùng khơng gian địa chỉ và các dịng xử lý này hoạt động song song tương tư như các tiến trình phân biệt khác. • Mỗi dịng xử lý phân biệt này gọi là một tiểu trình. • Mỗi tiểu trình xử lý tuần tự đoạn mã của minh và sở hữu con trỏ lệnh tập các thanh ghi, stack riêng. Các tiểu trình chia sẻ CPU như các tiến trình độc lập. • Một tiến trình cĩ thể sở hữu nhiều tiểu trình . • Các tiểu trình trong một tiến trình cĩ thể chia sẻ tài nguyên của tiến trình cha (các biến tồn cục) VI.5 Lập lịch tiến trình • Trong hệ thống đa nhiệm tại một thời điểm cĩ thể nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu là chuyển đổi CPU qua lại các tiến trình thường xuyên. • Để thực hiện điều này hệ điều hành phải lựa chọn tiến trình kế tiếp để xử lý. Bộ lập lịch sẽ sử dụng thuật tốn để thực hiện. • Mục tiêu của bộ lập lịch: Hệ điều hành xây dựng nhiều chiến lược khác nhau thực hiện lập lịch nhưng phải đạt các mục tiệu như sau: - Sự cơng bằng: Các tiến trình chia sẻ CPU một cách cơng bằng. Khơng tiến trình nào chờ vơ hạn mới được cấp pháp CPU Trang 51
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Tính hiệu quả: Hệ thống phải tận dụng CPU 100% thời gian - Thời gain đáp ứng hợp lý: Cực tiểu hĩa thời gian hồi đáp cho cac tương tác của người sử dụng. - Thời gian lưu lại hệ thống : Cực tiểu hĩa thời gian hồn tất các tác vụ xử lý theo lơ. - Thơng lượng tối đa: Cực đại hĩa số cơng việc được xử lý trong một đơn vị thời gian • Tất cả mục tiêu trên thường khơng thỏa hết vì chính bản thân chúng cĩ sự mâu thuẫn với nhau. • Lập lịch tiến trình: - Hệ điều hành tổ chức một danh sách chứa các tiến trình đang sẵng sàng - Hệ điều hành sẽ chọn một tiến trình trong danh sách sẵng sàng để cấp phát CPU. - Các chiến lược lập lịch tiến trình VI.5.1 Chiến lược lập lịch tiến trình FIFO CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng- là tiến trình được đưa vào hệ thống sớm nhất. Hình 6.2 Ví dụ: Tiến trình Thời điểm vào Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 Thứ tự cấp phát CPU cho các tiến trình: P1 P2 P3 0 24 27 30 - Thời gian chờ được xử lý của P1 : 0 - Thời gian chờ được xử lý của P2 : 24-1=23 - Thời gian chờ được xử lý của P3 : 24+3 -2 =25 Trang 52
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Thời gian chờ trung bình là : (0+ 23+ 25)/3 =16 milisecondes - Thời gian chờ trung bình khơng đạt cực tiểu và xảy ra hiện tượng tích luỹ thời gian tất cả tiến trình phải chờ một tiến trình cĩ yêu cầu thời gian dài kết thúc. VI.5.2 Chiến lược Round Robin • Trong chiến lược này danh sách sẵn sàng được sử dụng như danh sách vịng. Bộ điều lập lịch lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là Quantum • Khi một tiến trình sử dụng hết thời gian Quantum dành cho nĩ thì hệ điều hành thu hồi CPU cấp cho tiến trình khác trong danh sách. • Nếu tiến trình bị Blocked hoặc kết thúc trước khi hết Quantum thì hệ điều hành cũng thu hồi CPU. • Nếu một tiến trình sử dụng hết Quantum mà chưa xử lý xong sẽ được đưa vào cuối danh sách sẵng sàng để chờ cấp phát CPU lần sau. Hình 6.3 Ví dụ: Tiến trình Thời điểm vào Thời gian xử lý P1 0 24 P2 1 3 P3 4 3 Với Quantum = 4 thứ tự cấp phát CPU như sau: P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 - Thời gian chở xử lý P1: 0 - Thời gian chờ xử lý P2 : 4-1=3 - Thời gian chờ xử lý P3: 7-2 = 5 - Thời gian chờ xử lý P1 lần sau: 10-4=6 - Thời gian chờ trung bình : (0+3+5+6)/3 =4.66 Milisecondes Trang 53
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Thời gian của Q quá bé thì chuyển đổi CPU giữa các tiến trình quá nhiều khiến việc sử dụng CPU khơng hiệu quả. • Nếu Q quá lớn thì tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống VI.5.3 Chiến lược gán độ ưu tiên • Mỗi tiến trình được gán một độ ưu tiên tương ứng, tiến trình nào cĩ độ ưu tiên cao hơn sẽ được chọn cấp phát CPU đầu tiên. • Độ ưu tiên được định nghĩa trong nội tại hoặc từ bên ngồi. • Chiến lược độ ưu tiên khơng độc quyền: Khi một tiến trình được đưa vào danh sách 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 đang xử lý. Bộ lập lịch 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 nĩ cao hơn độ ưu tiên của tiến trình hiện hành • Chiến lược độ ưu tiên độc quyền: CPU vẫn được cấp phát cho tiến trình hiện hành mặc dù tiến trình mới vào cĩ độ ưu tiên cao hơn độ ưu tiên của tiến trình hiện hành. Ví dụ : Chiến lược độ ưu tiên độc quyền Tiến trình Thời điểm vào Độ ưu tiên Thời gian xử lý P1 0 3 24 P2 1 2 3 P3 2 1 4 Thứ tự cấp phát CPU như sau: P1 P3 P2 0 24 28 31 Ví dụ : Chiến lược độ ưu tiên khơng độc quyền Trang 54
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Tiến trình Thời điểm vào Độ ưu tiên Thời gian xử lý P1 0 3 24 P2 1 2 3 P3 2 3 4 Thứ tự cấp phát CPU như sau: P1 P2 P3 P2 P1 0 1 2 6 8 31 - Với chiến lược này tiến trình cĩ độ ưu tiên thấp sẽ đợi CPU vơ hạn. Để tránh trường hợp này thì bộ lập lịch phải giảm dần độ ưu tiên của các tiến trình sau một chu kỳ thời gian. VI.5.4 Chiến lược cơng việc ngắn nhất được thực hiện trước: • Đây là thuật giải dành cho hệ thống xử lý theo lơ, khi mà thời gian chạy của mỗi cơng việc được biết trước. • Giả sử a, b, c, d lần lượt là thời gian của 4 cơng việc . Nếu cho 4 cơng việc này chạy theo thứ tự đĩ thì thời gian chạy trung bình là : (4a+3b+2c+d ) /4 . • Dễ dàng thấy là nếu chọn cơng việc ngắn cho chạy trước thì giá trị thời gian chạy trung bình là nhỏ nhất. VI.6 Đồng bộ hĩa tiến trình • Sự liên lạc giữa các tiến trình - Trong mơi trường đa nhiệm các tiến trình khơng chạy độc lập mà thường xuyên cĩ nhu cầu trao đổi thơng tin với nhau. - Nguyên tắc chung trao đổi thơng tin giữa các tiến trình: Sử dụng vùng nhớ được chia sẻ, Trao đổi thơng điệp. - Vấn đề nảy sinh : xảy ra hiện tượng đua nhau sử dụng vùng nhớ chia xẻ dẫn đến kết quả khơng chính xác - Cần phải đồng bộ hĩa tiến trình. • Điều kiện đua: Nếu cĩ nhiều tiến trình đọc , ghi dữ liệu vào vùng nhớ dùng chung và kết quả cuối cùng phụ thuộc thời điểm tiến trình nào chạy thật sự gọi là điều kiện đua. • Vùng găng: - Để tránh điều kiện đua, nếu hệ điều hành khơng cho phép cĩ nhiều tiến trình đọc hoặc ghi vào vùng nhớ lưu trữ chung tại cùng một thời điểm cần phải đạt sự loại trừ lẫn nhau Trang 55
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Một phần nào đĩ của chương trình mà tại đĩ thực hiện truy cập đến vùng nhớ dùng chung gọi là vùng găng • Để tránh điều kiện đua thì hệ điều hành phải được thiết kế sao cho khơng cho phép 2 hay nhiều hơn tiến trình đồng thời trong vùng găng. • Bốn điều kiện cần đảm bảo để thiết kế hệ điều hành cho phép nhiều tiến trình sử dụng vùng nhớ dùng chung một cách đúng đắn và hiệu quả: - (1) Khơng cho phép cĩ nhiều hơn một tiến trình đồng thời trong vùng găng. - (2) Khi lập trình các tiến trình khơng được phép cĩ bất kỳ giả định nào về tốc độ CPU và số lượng CPU. - (3) Khơng cho phép một tiến trình ở ngồi vùng găng của mình làm Blocked một tiến trình khác. - (4) Khơng cho phép bất kỳ một tiến trình nào đợi thời gian quá lâu mới cĩ thể vào vùng găng của mình. VI.6.1 Các phương pháp thực hiện loại trừ nhau vào vùng găng VI.6.1.1 Dùng biến khĩa Hệ điều hành sử dụng một biến dùng chung, gọi là biến khĩa lock được khởi tạo =0. Khi một tiến trình muốn vào vùng găng, nĩ thực hiện kiểm tra biến lock int lock =0; if (lock==0) (*) { lock =1; tiến trình trong vùng găng; } else { tiến trình đợi cho đến khi lock =0 } Với phương pháp này vi phạm điều kiện (1) khi bộ lập lịch thu hồi CPU của một tiến trình tại (*), tiến trình này đã ghi nhận biến lock =0 và chuẩn bị vào găng. Lúc này bộ lập lịch cấp phát CPU cho tiến trình khác, tiến trình này kiểm tra biến lock thấy vẫn =0 và được phép vào găng. Nếu bộ lập lịch lại cấp phát CPU cho tiến trình trước thì tiến trình này tiếp tục chạy và thực hiện vào găng. Vậy tại một thời điểm cĩ 2 tiến trình vào găng. VI.6.1.2 Luân phiên ngặt Ý tưởng: Dùng một biến dùng chung turn=0; và mỗi tiến trình cĩ đoạn mã sau: Trang 56
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành whie (TRUE) while(TRUE) { { while (turn !=0); while(turn !=1); Tronggăng(); TrongGăng(); turn=1; turn =0; ngồigăng(); NgồiGăng(); } } Phương pháp này vi phạm điều kiện (4) vì theo phương pháp này hai tiến trình phải thay phiên ngặt vào ra vùng găng. Nếu một tiến trình vào ra vùng găng khơng luân phiên sẽ gây ra tiến trình cịn lại đợi quá lâu khơng vào vùng găng. VI.6.1.3 Giải pháp Peterson #define FALSE 0 #define TRUE 1 #define N 2 int turn; int interested[N]; /* khởi gán bằng FALSE*/ void Vàogăng(int Process) { int other; other = 1- Process; interested[Process]= TRUE; turn = Process; while (turn ==Process && interested[other] ==TRUE); } void RaGăng(int Process) { interested[Process]=FALSE; } Khi một tiến trình nào đĩ muốn vào vùng găng thi gọi hàm Vaogang() và truyền tham số là số hiệu tiến trình. Khi tiến trình muốn ra khỏi vùng găng nĩ gọi hàm RaGăng() Mặc dù giải pháp Peterson là chấp nhận được vì thỏa mãn 4 điều kiện nhưng bị hàn chế: 1. Khi một tiến trình đợi vào vùng găng tiến trình vẫn sử dụng thời gian CPU – Lãng phí CPU. 2. Khi đưa ra khái niệm độ ưu tiên cho các tiến trình giải pháp Peterson khơng đáp ứng được. (xét trường hợp tiến trình cĩ độ ưu tiên thấp hơn trong vùng găng và tiến trình cĩ độ ưu tiên cao đợi vào vùng găng.) Trang 57
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Giải pháp gọi VI.6.1.4 Giải pháp gọi lời gọi hệ thống SLEEP vào WAKEUP sẽ làm blocked tiến trình đợi vào vùng găng SLEEP: Chuyển tiến trình gọi nĩ về trạng thái blocked cho đến khi tiến trình khác gởi đến nĩ tín hiệu đổi trạng thái ( WAKEUP) WAKEUP(Process) : Chuyển tiến trình Process về trạng thái Ready (tiến trình đã gọi SLEEP trước đĩ) Xét bài tốn : “Sản xuất – tiêu thụ “: Cĩ hai tiến trình SảnXuất và TiêuThụ dùng chung buffer cĩ kích thước cố định. Tiến trình SảnXuất đặt sản phẩm vào buffer nếu buffer cịn trống. Tiến trình TiêuThụ lấy sản phẩm từ buffer nếu buffer khác rỗng. #define N 100 int count=0; void SảnXuất(void) { int item; while (TRUE) { SảnXuấtSảnPhẩm(&Item); if (count == N) SLEEP(); ĐặtSảnPhẩm(Item); count++; if (count == 1) WAKEUP(TieuThụ); } } void TiêuThụ(void) { int Item; while( TRUE) { if (count == 0) SLEEP(); LấySảnPhẩm(&Item); count ; if (count == N-1) WAKEUP (SảnXuất); TiêuThụsảnPhẩm(Item); } } Với giải pháp này hệ thống cĩ thể dẫn đến tình trạng Deadlock tức cả hai tiến trình đều rơi vào trạng thái Block, khơng cĩ tiến trình wakeup do sử dụng biến dùng chung Trang 58
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành count khơng được thực hiện theo thao tác nguyên tử. Kết quả là tín hiệu WAKEUP bị mất khi tiến trình được WAKEUP chưa thật sự SLEEP. • Cần duy trì một biến đếm cho mỗi tiến trình để đếm tín hiệu WAKEUP được gởi đến từ tiến trình khác . Mỗi khi gọi SLEEP tiến trình kiểm tra biến đếm , nếu biến đếm >0 thì giảm biến đếm xuống 1 và tiến trình vẫn khơng bị blocked. • Đĩ chính là ý tưởng để xây dựng khái niệm Semaphore VI.6.1.5 Semaphore Semaphore là một kiểu nguyên khơng âm. Một semaphore s =0 chỉ ra rằng khơng tín hiệu WAKEUP nào được gởi đến. Cĩ hai thao tác nguyê tử trên semaphore được định nghĩa như sau: DOWN(s) : if (s >0) s=s-1; else SLEEP(); UP(s): if ( s >0 ) s=s+1; else nếu cĩ một hoặc nhiều tiến trình đang bị Blocked trên semaphore s . Hệ điều hành chọn ngẫu nhiên một tiến trình cho phép thốt khỏi trạng thái Blocked. (Trong khi đĩ s vẫn =0.) ngược lại: khơng cĩ tiến trình nào Blocked trên s thì: s= s+1 ; • Tất cả cơng đoạn kiểm tra giá trị s, thay đổi s, gọi SLEEP được tích hợp thành một thao tác duy nhất khơng phân chia được- gọi là thao tác nguyên tử . • Một semaphore s được khởi tạo =1 và được sử dụng bởi nhiều tiến trình để đảm bảo chỉ một trong chúng là vào được vùng găng tại một thời điểm gọi là semaphore nhị phân. Vì vậy mỗi tiến trình chỉ cần gọi tốn tử DOWN(s) trước khi vào vùng găng và gọi UP(s) sau khi ra khỏi vùng găng thì cĩ thể đảm bảo được sự loại trừ lẫn nhau. • Các loại semaphore khác gọi là semaphore đồng bộ hĩa, nĩ đảm bảo một dãy các sự kiện nào đĩ là xuất hiện hoặc khơng xuất hiện. • Áp dụng Semaphore để giải quyết bài tốn Sản suất – tiêu thụ #define N 100 typedef int Semaphore; Semaphore Mutex = 1; Semaphore Empty =N; Semaphore Full = 0; void SảnXuất (void) { int Item; while(TRUE) { SảnXuấtSảnPhẩm(&Item); down(&Empty); down(&Mutex); Trang 59
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành ĐặtSảnPhẩm(Item); up(&Mutex); up(&Full); } } void TiêuThụ (void) { int Item; while(TRUE) { down(&Full); down(&Mutex); LấySảnPhẩm(&Item); up(&Mutex); up(&Empty); TiêuThụsảnPhẩm(Item); } } VI.6.2 Áp dụng Semaphore để giải quyết bài tốn cổ điển VI.6.2.1 Bài tốn” Bữa ăn tối của các nhà hiền triết” Cĩ 5 nhà hiền triết ngồi quanh một bàn trịn trong một bữa ăn tối. Mỗi người cĩ một dĩa mì Spaghetti. Mỗi người cần phải cĩ 2 nĩa để cĩ thể ăn mì. Giữa 2 dĩa cĩ một nĩa. Giả định rằng cuộc đời của nhà hiền triết chỉ luân phiên nhau 2 hành vi: ăn và suy nghĩ. Khi nhà hiền triết cảm thấy đĩi ơng ta muốn lấy 2 nĩa bên trái và phải theo thứ tự nào đĩ. Nếu lấy được cả 2 nĩa ơng ta bắt đầu ăn. Sau đĩ đặt nĩa xuống và tiếp tục suy nghĩ. Yêu cầu viết chương trình cho mỗi nhà hiền triết sao cho khơng bị “kẹt”. Hình 6.4 #define N 5 void HiềnTriết (int i) Trang 60
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành { while(TRUE) { SuyNghĩ(); LấyNĩa(i); LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải Ă n(); ĐặtNĩa(i); ĐặtNĩa((i+1)%N); } } Lời giải 1 #define N 5 typedef int Semaphore; Semaphore Mutex=1; void HiềnTriết (int i) { while(TRUE) { SuyNghĩ(); down(&Mutex); LấyNĩa(i); LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải Ă n(); ĐặtNĩa(i); ĐặtNĩa((i+1)%N); up(&Mutex); } } Lời giải trên đúng nhưng khơng tối ưu tài nguyên – tại một thời điển chỉ cĩ 1 nhà hiền triết ở trạng thái ăn trong khi đĩ cĩ thể cĩ 2 Lời giải 2 #define N 5 #define LEFT (i-1)%N #define RIGHT (i+1)%N #define THINKING 0 #define HUNGRY 1 #define EATING 2 typedef int Semaphore; int State [N]; Semaphore Mutex=1; Semaphore S[N];// Khởi gán =0 void HiềnTriết (int i) Trang 61
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành { while(TRUE) { SuyNghĩ(); LấyNĩa(i);// Lấy nĩa trái và phải Ă n(); ĐặtNĩa(i); } } void LấyNĩa (int i) { down (&Mutex); State[i]=HUNGRY; Test(i); up(&Mutex); down(&S[i]); return ; } void ĐặtNĩa (int i) { down (&Mutex); State[i]=THINKING; Test(LEFT); Test(RIGHT); up(&Mutex); return ; } void Test (int i) { if( State[i]==HUNGRY && State[LEFT]!=EATING && State[RIGHT]!=EATING) { State[i]=EATING; up(&S[i]); } } VI.6.2.2 Bài tốn” Độc giả và nhà văn” Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đĩ (nhà văn) . Hệ thống cho phép đồng thời cĩ nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi cĩ một tiến trình ghi lên CSDL thì khơng cĩ tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc . Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn” Seamphore Mutex =1; Semaphore Db=1;// Truy cập vào DBF của tiến trình Writer int rc; // Đếm số tiến trình đọc Trang 62
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành void Reader (void ) { while (TRUE) { down (Mutex); rc= rc+1; if ( rc==1) down(db); up(Mutex); ReadDBF(); down(Mutex); rc=rc-1; if (rc==0) up(db); up(Mutex); } } void Writer (void ) { while (TRUE) { CreateData(); down(db); WriteData(); up(db); } } CÂU HỎI VÀ BÀI TẬP 1. Trình bày khái niệm tiến trình và giải thích quá trình chuyển đổi giữa các trạng thái tiến trình? 2. Trình bày mục tiêu của bộ lập lịch tiến trình? 3. Hãy tính thời gian chờ được xử lý trung bình của các tiến trình theo thuật tốn Round Robin với Q=3 Tiến trình Thời điểm vào Thời gian xử lý P1 0 10 P2 1 5 P3 4 7 P4 5 8 Trang 63
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hãy tính thời gian chờ được xử lý trung bình của các tiến trình theo thuật tốn độ ưu tiên khơng độc quyền kết hợp Round Robin(Q=3) đối với các tiến trình cĩ cùng độ ưu tiên. Biết rằng: - Độ ưu tiên của P1, P2, P3, P4 lần lượt là 2, 3,1, 2. (1>2>3) - Sau mỗi lần xử lý độ ưu tiên của tiến trình giảm đi 1. 4. Hãy tính thời gian chờ được xử lý trung bình của các tiến trình theo thuật tốn độ ưu tiên khơng độc quyền , với độ ưu tiên 1>2>3 . Tiến trình Thời điểm vào Độ ưu tiên Thời gian xử lý P1 0 1 7 P2 1 3 5 P3 4 2 3 P4 5 1 8 5. Trình bày nguyên tắc trao đổi thơng giữa các tiến trình. Lý do cần đồng bộ hố các tiến trình? 6. Thảo luận sự vi phạm điều kiện (4) cần đảm bảo để thiết kế hệ điều hành cho phép nhiều tiến trình sử dụng vùng nhớ dùng chung một cách đúng đắn và hiệu quả của thuật tốn luân phiên ngặt? 7. Trình bày nhược điểm của giải pháp đồng bộ hố Peterson và giải pháp gọi lời gọi hệ thống Sleep() và wakeup() ? 8. Trình khái niệm Semaphore và định nghĩa 2 tốn tử Down() và Up() trên semaphore ? Cho một ví dụ tình huống sử dụng semaphore nhị phân? 9. Sử dụng semaphore thực hiện đồng bộ hĩa hai tiến trình SendMessage() và ReceiveMessage(). Biết rằng hai tiến trình trên sử dụng chung một hàng đợi Queue, tiến trình ReceiceMessage() nhận message từ bàn phím và ghi vào đầu hàng đợi và tiến trình SendMessage() lấy message từ hàng đợi Queue và gởi lên mạng máy tính. Kích thước của hàng đợi Queue là N, mỗi phần tử hàng đợi chứa được một message. Khi hàng đợi đầy tiến trình ReceiceMessage() phải tạm ngưng, khi hàng đợi rỗng tiến trình SendMessage() phải tạm ngưng. 10. Sử dụng semaphore tạo ra hai tiến trình sau sao cho nb<na<nb+10: Tiến trình 1: Tiến trình 2: While(TRUE) While(TRUE) { { na=na+1; nb=nb+1; } } CHƯƠNG VII Trang 64
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành HỆ THỐNG QUẢN LÝ BỘ NHỚ VII.1 Giới thiệu • Bộ nhớ chính là thiết bị lưu trữ duy nhất thơng qua đĩ CPU cĩ thể trao đổi thơng tin với mơi trường ngồi. • Nhu cầu tổ chức quản lý bộ nhớ là nhiệm vụ hàng đầu của hệ điều hành. • Bộ nhớ chính được tổ chức như một mảng một chiều các ơ nhớ. Việc trao đổi thơng tin với mơi trường ngồi được thực hiện thơng qua các thao tác đọc ghidữ liệu vào địa chỉ cụ thể của bộ nhớ. • Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu quả sử dụng CPU. VII.2 Quản lý bộ nhớ khơng phân trang, khơng Swapping • Bộ nhớ chỉ được chia sẻ cho hệ điều hành và một chương trình duy nhất của người sử dụng. Tức tại một thời điểm một phần bộ nhớ sẽ do HĐH chiếm giữ và phần cịn lại thuộc về một tiến trình người sử dụng, tiến trình này cĩ tồn quyền sử dụng vùng nhớ dành cho nĩ. • Mơ hình Hình 7.1 • Để bảo vệ vùng nhớ của HĐH khỏi sự xâm phạm của tiến trình người dùng cần phải tổ chức thanh ghi giới hạn. • Địa chỉ cao nhất của vùng nhớ được cấp phát cho HĐH sẽ được nạp vào thanh ghi giới hạn. • Tất cả các địa chỉ được tiến trình người dùng truy xuất đến sẽ được so sánh với nội dung thanh ghi giới hạn, nếu địa chỉ lớn hơn nội dung thanh ghi giới hạn thì đây là một địa chỉ hợp lệ, ngược lại một ngắt được phát sinh để thơng báo cho hệ thống về một truy xuất bất hợp lệ. • Với tổ chức như vậy thì chỉ cĩ thể xử lý một chương trình duy nhất tại một thời điểm. • Trong thực tế cĩ rất nhiều tiến trình phải trải qua phần lớn thời gian chờ thao tác nhập xuất hồn thành trong suốt thời gian này CPU nhàn rỗi ◊ để nâng cao hiệu suất sử dụng CPU cần cho phép chế độ đa chương. VII.3 Quản lý bộ nhớ với những phân đọan cố định Trang 65
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành • Hệ điều hành chia bộ nhớ thành n vùng nhớ cố định( cĩ thể khơng bằng nhau) • Việc phân chia này được thực hiện vào lúc khởi động hệ thống và khơng thay đổi suốt quá trình chạy. • Với tổ chức như vậy cần duy trì một hàng đợi duy nhất để lưu trữ những tiến trình chưa được cấp phát bộ nhớ. Hình 7.2 • Tất cả tiến trình được đặt trong một hàng đợi duy nhất. Khi cĩ một phân vùng tự do , tiến trình đầu tiên trong hàng đợi cĩ kích thước phù hợp sẽ được đặt vào phân vùng này và cho xử lý. • Nếu kích thước của tiến trình khơng vừa đúng bằng kích thước phân vùng chứa nĩ, phần bộ nhớ khơng sử dụng đến trong phân vùng sẽ bị lãng phí. - Xảy ra hiện tượng phân mảnh nội vi. - Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng • Vấn đề bảo vệ giữa các phân vùng: Để bảo vệ cần tổ chức hai thanh ghi : thanh ghi nền và thanh ghi giới hạn. - Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước của tiến trình - Sau đĩ mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình khơng truy xuất ngồi phạm vi được cấp phát cho nĩ. VII.4 Quản lý bộ nhớ với những phân đọan động • Như tổ chức quản lý bộ nhớ trên gây ra lãng phí bộ nhớ vì vậy một phương pháp mới được đề xuất là cấp pháp cho tiến trình vùng nhớ vừa đủ kích thước của tiến trình. • Khi một tiến trình kết thúc vùng nhớ đã đã cấp cho nĩ sẽ được giải phĩng và được cấp pháp cho tiến trình khác. • Với giải pháp này khơng cịn hiện tượng phân mảnh nội vi nhưng lại xuất hiện phân mảng ngoại vi. Khi các tiến trình lần lượt vào ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình cĩ thể dẫn đến tình huống tổng vùng nhớ cịn trống đủ để thỏa mãn yêu cầu nhưng các vùng nhớ này khơng liên tục. Trang 66
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - Cĩ thể áp dụng kỹ thuật dồn bộ nhớ để kết hợp các mảnh bộ nhớ rời rạc thành một vùng nhớ lớn liên tục. - Một vấn đề khác nảy sinh khi kích thước của tiến trình tăng trưởng trong quá trình xử lý mà khơng cịn vùng nhớ cịn trống gần kề để mở rộng vùng nhớ cho tiến trình. • Quản lý các ơ nhớ cịn trống: Cần phải lưu trữ thơng tin các ơ nhớ cịn trống để cấp phát cho các tiến trình, Cĩ hai phương pháp chính: Bitmap và danh sách liên kết. • Phương pháp Bitmap: Chia bộ nhớ thành từng đơn vị nhỏ (vài bytes) . Xây dựng bitmap, ứng với mỗi bit trong bitmap là một đơn vị bộ nhớ. - Bit được đánh dấu là 1 khi đơn vị bộ nhớ tương ứng đã được cấp phát - Bit được đánh dấu 0 khi đơn vị bộ nhớ tương ứng chưa được cấp phát. Thao tác cấp phát bộ nhớ là : Giả sử tiến trình cần k đơn vị bộ nhớ, HĐH duyệt bitmap và tìm ra k bit liên tiếp bằng 0 Hình 7.3 • Quản vùng nhớ cịn trống bằng danh sách liên kết Tổ chức một danh sách liên kết, mỗi phần tử tương ứng với một tiến trình hay lỗ hổng. Mỗi phần tử trong danh sách cĩ 4 trường : - Cờ biểu thị tiến trình (P) hay lỗ hổng (H) - Địa chỉ bắt đầu của vùng nhớ tương ứng - Kích thước của vùng nhớ - Con trỏ Next Hình 7.4 • Thao tác cấp phát bộ nhớ Trang 67
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành - First Fit : Xác định lỗ hổng đầu tiên trong danh sách cĩ kích thước đủ lớn để cấp phát cho tiến trình và lỗ hổng này được chia làm 2 phần : 1 phần cho tiến trình và phần kia là lỗ hổng mới. - Best Fit : xác định lỗ hổng bé nhất cĩ kích thước đủ lớn để cấp phát cho tiến trình. - Worst Fit : Cấp phát phân đoạn tự do lớn nhất đủ lớn để cấp phát cho riến trình. Cĩ thể làm tăng tốc độ bằng cách cho cả 3 thuật tốn trên bằng cách tổ chức 2 danh sách: 1 cho tiến trình và một cho lỗ hổng. Tuy nhiên lại làm chậm thao tác giải phĩng bộ nhớ. • Thao tác giải phĩng bộ nhớ - Khi thực hiện thao tác giải phĩng chú ý cần xem xét các trường hợp khác nhau của 2 phần tử kề nhau. Nhờ đĩ thực hiện thao tác kết hợp hai lỗ hổng kề nhau một cách phù hợp: Hình 7.5 • Quá trình Swapping Trong hệ thống đa nhiệm nhiều người dùng thường là bộ nhớ khơng đủ chỗ để lưu trữ tất cả các tiến trình vì thế hệ thống dùng DSLK để lưu trữ tạm thời một số tiến trình nào đĩ chưa thật sự chạy, khi được cấp phát CPU thì hệ thống phải mang nĩ vào bộ nhớ chính . Việc di chuyển tiến trình từ bộ nhớ vào đĩa và ngược lại gọi là quá trình swapping. • Bộ nhớ ảo Bộ nhớ ảo được đưa ra nhằm khắc phục tình trạng kích thước chương trình vượt quá kích thước bộ nhớ vật lý. Hệ điều hành chia chương trình thành nhiều phần và giữa lại những phần chương trình đang chạy hiện thời vừa đủ chứa trong bộ nhớ , phần cịn lại lưu trữ trên đĩa. HĐH theo dõi và quản lý tất cả cơng việc swapping giữa đĩa và bộ nhớ . Dĩ nhiên bộ nhớ ảo vẫn cĩ thể thiết kế cho hệ thống đa nhiệm. • Sự phân trang (paging) Hầu hết những hệ thống cĩ sử dụng bộ nhớ ảo đều sử dụng kỹ thuật phân trang. Địa chỉ ảo là địa chỉ tham khảo từ chương trình . Tập tất cả địa chỉ ảo gọi là vùng địa chỉ ảo, đối với những hệ thống khơng dùng bộ nhớ ảo , địa chỉ ảo cũng là địa chỉ vật lý. Trang 68
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Vùng địa chỉ ảo được chi thành nhiều trang (page) cĩ kích thước bằng nhau tướng ứng với những khung trang (Page frame) trong bộ nhớ vật lý. Trang và khung trang luơn cĩ kích thước bằng nhau. Ví dụ: cĩ 32K bộ nhớ vật lý chia thành 8 khung trang cĩ kích thước 4K và 64K bộ nhớ ảo chia thành 16 trang kích thước 4K. Trong bất kỳ thời điểm nào chỉ cĩ 8 trang từ bộ nhớ ảo ánh xạ vào bộ nhớ vật lý như sau: Hình 7.6 • Nếu lệnh nào đĩ trong chương trình tham khảo đến địa chỉ ảo khơng thuộc về bất kỳ trang nào đang được ánh xạ hiện thời gọi là lỗi trang. Trong trường hợp này HĐH tìm ra một khung trang nào ít sử dụng nhất trục xuất khỏi bộ nhớ và tìm kiếm trên đĩa trang nào chứa địa chỉ mà chương trình muốn tham khảo đến để chuyển vào bộ nhớ vật lý. Tiếp đến hệ thống cập nhật ánh xạ bộ nhớ cho trang mới. • Bảng trang Hệ thống phải duy trì một bảng trang thể hiện ánh xạ từ bộ nhớ ảo vào bộ nhớ vật lý và chứa thơng tin trang nào hiện thời đang được ánh xạ. Trang 69
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành Hình 7.7 VII.5 Các thuật tốn thay thế trang Mỗi khi gặp lỗi trang HĐH phải chọn 1 trong các trang nào đĩ trục xuất ra khỏi bộ nhớ. Nếu nội dung trang đĩ bị thay đổi thì phải ghi nội dung mới của trang lên đĩa. Vấn đề là chọn trang nào để trục xuất để giảm tổn phí. Xét ví dụ một tiến trình truy xuất đến một dãy các trang sau: 7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 giả sử cĩ 3 khung trang và ban đầu cả 3 khung trang đều rỗng. VII.5.1 Thuật tốn FIFO • Ghi nhận thời điểm 1 trang được mang vào bộ nhớ chính khi cần thay thế trang , thì trang lâu nhất sẽ được chọn để trục xuất. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 * * * * * * * * * * * * * * * Hình 7.8 • Với thuật tốn này cĩ thể cĩ trang được chọn để thay thế cĩ thể chứa nhiều dữ liệu cần thiết thường xuyên được nạp vào sớm , do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chĩng gây ra lỗi trang. Trang 70
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành VII.5.2 Thuật tốn tối ưu • Thay thế trang sẽ lâu nhất được sử dụng trong tương lai 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * Hình 7.9 • Thuật tốn này bảo đảm lỗi trang là ít nhất tuy nhiên thuật tốn này khơng khả thi vì khơng thể biết trước dãy các trang được truy xuất theo thứ tự. VII.5.3 Thuật tốn lâu nhất chưa sử dụng (LRU) • Với mỗi trang ghi nhận thời điểm cuối cùng trang được truy cập, trang được thay thế là trang lâu nhất chưa sử dụng. 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 * * * * * * * * * * * Hình 7.10 • Thuật tốn địi hỏi một cơ chế xác định thứ tự các trang theo thời điểm truy xuất cuối cùng. Dùng stack - Cần tổ chức một stack lưu trữ số hiệu các trang - Mỗi khi thực hiện một truy xuất đến 1 trang , số hiệu của trang sẽ được xĩa khỏi vị trí hiện hành trong stack và đưa lên đỉnh stack. - Trang ở đỉnh stack là trang được chọn để thay thế. VII.5.4 Thuật tốn Not Recently Used (NRU) • Thuật tốn dựa trên sự tồn tại 2 bit gắn liền với mỗi trang để chỉ ra trang đĩ cĩ vừa mới được tham khảo hay là được ghi lên hay khơng. Những bit này chứa trong bảng trang Trang 71
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành 9 Bit R =1: nếu trang đĩ truy cập ngược lại chưa được truy cập 9 Bit M =1 : Trang đĩ đã bị thay đổi ngược lại chưa bị thay đổi - Cứ mỗi lần truy cập bộ nhớ cần phải cập nhật lại các bit này - Khi một tiến trình bắt đầu cả 2 bit trong tất cả các trang được đặt bằng 0. theo một chu kỳ thời gian bit R được đặt lại bằng 0 để phân biệt những trang mới được truy cập với trang đã truy cập trước đĩ. - Khi xuất hiện một lỗi trang HĐH duyệt tồn bộ bảng trang và chia chúng thành 4 lớp dựa vào các bit R, M như sau: Class 0 : R=0, M=0 Class 1: R=0, M=1 Class 2: R=1, M=0 Class 3: R=1, M=1 Sau đĩ thuật tốn chọn ra một trang để thay thế thuộc thuộc lớp thấp nhất khác rỗng. CÂU HỎI VÀ BÀI TẬP 1. Trình bày hiện tượng phân mảnh nội vi và ngoại vi trong quá trình tổ chức quản lý bộ nhớ phân đoạn cố định và động ? 2. Trình bày thuật tốn cấp phát bộ nhớ (thuật tốn first Fit, Best Fit, Worst Fit ) trong kỹ thuật quản lý bộ nhớ động bằng danh sách liên kết và kỹ thuật bitmap? 3. Trình bày thuật tốn giải phĩng bộ nhớ trong kỹ thuật quản lý bộ nhớ động bằng danh sách liên kết ? 4. Trình bày phương pháp chuyển đổi địa chỉ ảo sang địa chỉ vật lý trong phương pháp quản lý bộ nhớ ảo? Kích thước trang và khung trang, nội dung bảng trang như mục VII.4 ? 5. Trong một thống cài đặt bộ nhớ ảo theo kỹ thuật phân trang, giả sử một chương trình truy cập đến các trang sau: 1, 0,4, 2, 1, 3, 1, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 3, 0, 1. Giả sử hệ thống cĩ 3 khung trang lúc đầu cịn trống. Cĩ bao nhiêu lỗi trang xảy ra khi hệ thống sử dụng thuật tốn thay thế trang LRU, FIFO ? HẾT Trang 72
Khoa Cơng Nghệ Thơng Tin Hệ Điều Hành TÀI LIỆU THAM KHẢO [1] Giáo trình hệ điều hành 1, Lê Khắc Nhiên Ân, Hồng Kiếm [2] Giáo trình hệ điều hành 2, Lê Khắc Nhiên Ân, Hồng Kiếm [3] Hỗ trợ kỹ thuật lập trình hệ thống, Nguyễn Tín [4] Virus tin học huyền thoại và thực tế, Ngơ Anh Vũ [5] Operating Systems, Andrew S.Tanenbaum [6] Operating System Concepts, Abraham Siberschatz, Peter B. Galvin Trang 73