Giáo trình Nguyên lý hệ điều hành - Trình độ: Cao đẳng

Nội dung text: Giáo trình Nguyên lý hệ điều hành - Trình độ: Cao đẳng

1. BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TRƯỜNG CAO ĐẲNG NGHỀ KỸ THUẬT CÔNG NGHỆ š› & š› GIÁO TRÌNH MÔN HỌC : NGUYÊN LÝ HỆ ĐIỀU HÀNH NGHỀ: KỸ THUẬT SỬA CHỮA LẮP RÁP MÁY TÍNH TRÌNH ĐỘ: CAO ĐẲNG Ban hành kèm theo Quyết định số: 248b/QĐ-CĐNKTCN ngày 17 tháng 9 năm 2019 của Hiệu trưởng Trường Cao đẳng nghề Kỹ thuật Công nghệ Hà Nội, năm 2021 (Lưu hành nội bộ)
2. TUYÊN BỐ BẢN QUYỀN: Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo. Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. MÃ TÀI LIỆU: MHSCMT 16 2
3. LỜI GIỚI THIỆU Trong hệ thống kiến thức chuyên ngành trang bị cho sinh viên nghề Quản trị mạng máy tính, môn học Nguyên lý hệ điều hành góp phần cung cấp những nội dung liên quan đến việc mô tả các phương pháp giải quyết các bài toán điều khiển hoạt động của hệ thống máy tính Các nội dung chính được trình bày trong tài liệu này gồm các chương: - Giới thiệu chung về hệ điều hành - Điều khiển dữ liệu - Điều khiển bộ nhớ - Điều khiển CPU và Tiến trình - Hệ điều hành đa xử lý Mặc dầu có rất nhiều cố gắng, nhưng không tránh khỏi những khiếm khuyết, rất mong nhận được sự đóng góp ý kiến của độc giả để giáo trình được hoàn thiện hơn. Hà Nội, ngày 23 tháng 04 năm 2021 Tham gia biên soạn 1. Chủ biên Cù Ngọc Quỳnh giảng viên khoa CNTT 2. Tập thể Giảng viên Khoa CNTT Mọi thông tin đóng góp chia sẻ xin gửi về hòm thư tienphungktcn@gmail.com, hoặc liên hệ số điện thoại 0913393834-0983393834 3
4. MỤC LỤC LỜI GIỚI THIỆU 3 CHƯƠNG 1: TỔNG QUAN VỀ HỆ ĐIỀU HÀNH 8 1. Khái niệm về hệ điều hành 8 1.1. Tài nguyên hệ thống 8 1.2. Khái niệm hệ điều hành 10 2. Phân loại hệ điều hành 11 2.1. Các thành phần của hệ điều hành 11 2.2. Phân loại hệ điều hành 12 2.3. Tính chất cơ bản của hệ điều hành 14 2.4. Phân lớp các chương trình trong thành phần điều khiển 15 2.5. Chức năng cơ bản của hệ điều hành 16 2.6. Nhân của hệ điều hành, tải hệ điều hành 19 3. Sơ lược lịch sử phát triển của HĐH 20 CÂU HỎI VÀ BÀI TẬP 22 CHƯƠNG 2: ĐIỀU KHIỂN DỮ LIỆU 23 1. Các phương pháp tổ chức và truy nhập dữ liệu 23 1.1. Các phương pháp tổ chức dữ liệu 23 1.2. Các phương pháp truy nhập dữ liệu 25 1.3 Chức năng của hệ thống điều khiển dữ liệu 26 2. Bản ghi và khối 27 2.1. Bản ghi lôgic và bản ghi vật lý 27 2.2. Kết khối và tách khối 28 3. Quy trình điều khiển chung vào ra 30 3.1 Các khối điều khiển dữ liệu 30 3.2 Ví dụ về sơ đồ chung điều khiển vào ra trong hệ điều hành 30 4. Tổ chức lưu trữ dữ liệu trên bộ nhớ ngoài 31 4.1.Các khái niệm cơ bản 31 4.2.Các phương pháp quản lý không gian tự do 32 4.3.Các phương pháp cấp phát không gian tự do 34 4.4.Lập lịch cho đĩa 37 4.5.Hệ file 37 CÂU HỎI VÀ BÀI TẬP 38 CHƯƠNG 3: ĐIỀU KHIỂN BỘ NHỚ 39 1. Quản lý và bảo vệ bộ nhớ 39 1.1. Một số khái niệm liên quan đến bộ nhớ 39 1.2. Quản lý phân phối bộ nhớ. Vấn đề bảo vệ bộ nhớ 40 2. Điều khiển bộ nhớ liên tục theo đa bài toán 41 2.1. Chiến lược giới hạn tĩnh (cận cố định) 41 2.2 Chiến lược giới hạn động (cận thay đổi) 43 2.3. Cách thức Overlay và swapping 44 2.4. Các phương thức phân phối vùng nhớ (first fit, best fit, worst fit) 47 3. Điều khiển bộ nhớ gián đoạn 47 3.1. Tổ chức gián đoạn 47 3.2. Phân đoạn 49 4
5. 3.3. Phân trang 53 3.4. Kết hợp phân đoạn và phân trang 56 CÂU HỎI VÀ BÀI TẬP 58 CHƯƠNG 4: ĐIỀU KHIỂN CPU, ĐIỀU KHIỂN QUÁ TRÌNH 59 1. Các khái niệm cơ bản 59 1.1.Khái niệm quá trình 59 1.2. Quan hệ giữa các quá trình 60 2. Trạng thái của quá trình 60 2.1.Sơ đồ không gian trạng thái (SNAIL) 60 2.2. Một số khối điều khiển quá trình 61 3. Điều phối quá trình 63 3.1. Nguyên tắc chung 63 3.2. Các trình lập lịch (long term, short term) 63 4. Các thuật toán lập lịch 63 4.1. First Come First Served (FCFS) 63 4.2. Shortest Job First (SJF) 64 4.3. Shortest Remain Time (SRT) 65 4.4. Round Robin (RR) 66 4.5. Multi Level Queue (MLQ) 67 4.6. Multi Level Feedback Queues (MLFQ) 67 CÂU HỎI VÀ BÀI TẬP 69 CHƯƠNG 5: HỆ ĐIỀU HÀNH ĐA XỬ LÝ 70 1. Hệ điều hành đa xử lý tập trung 70 1.1 Hệ thống đa xử lý 70 1.2. Hệ điều hành đa xử lý tập trung 72 2. Hệ điều hành đa xử lý phân tán 72 2.1. Giới thiệu hệ phân tán 72 2.2. Đặc điểm hệ phân tán 73 CÂU HỎI VÀ BÀI TẬP 73 TÀI LIỆU THAM KHẢO 75 5
6. GIÁO TRÌNH MÔN HỌC Tên môn học: Nguyên lý hệ điều hành Mã môn học: MHSCMT 16 Vị trí, tính chất, ý nghĩa và vai trò môn học: - Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học chung, trước các môn học, mô đun đào tạo chuyên môn nghề. - Tính chất: Là môn học cơ sở. - Ý nghĩa và vai trò: Đây là môn học cơ sở ngành của các ngành liên quan đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về hệ điều hành để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiết, tối ưu hóa hệ thống máy tính. Mục tiêu của môn học: - Về kiến thức: + Hiểu vai trò và chức năng của hệ điều hành trong hệ thống máy tính; + Biết các giai đoạn phát triển của hệ điều hành; + Hiểu các nguyên lý thiết kế, thực hiện của hệ điều hành; - Về kỹ năng: + giải quyết được các vấn đề phát sinh trong hệ điều hành. - Về năng lực tự chủ và trách nhiệm: + Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học tập. Nội dung môn học: Thời gian Số Kiểm Tên chương, mục Tổng Lý TT Thực hành tra* (LT số thuyết hoặc TH) I Tổng quan về hệ điều hành 2 2 1.Khái niệm về hệ điều hành 2.Phân loại hệ điều hành 3.Sơ lược lịch sử phát triển của HĐH II Điều khiển dữ liệu 10 7 3 1.Các phương pháp tổ chức và truy nhập dữ liệu 2.Bản ghi và khối 3.Quy trình chung điều khiển vào – ra 6
7. 4.Tổ chức lưu trữ dữ liệu trên bộ nhớ ngoài III Điều khiển bộ nhớ 13 8 4 1 1.Quản lý và bảo vệ bộ nhớ 2.Điều khiển bộ nhớ liên tục theo đa bài toán 3.Điều khiển bộ nhớ gián đoạn IV Điều khiển CPU, Điều khiển 13 9 3 1 quá trình 1.Các khái niệm cơ bản 2.Trạng thái của quá trình 3.Điều phối quá trình 4.Các thuật toán lập lịch V Hệ điều hành đa xử lý 7 4 3 1.Hệ điều hành đa xử lý tập trung 2.Hệ điều hành đa xử lý phân tán Cộng 45 30 13 2 7
8. CHƯƠNG 1: TỔNG QUAN VỀ HỆ ĐIỀU HÀNH Mã chương: MHSCMT 16.01 Mục tiêu: - Nắm được yêu cầu cần có hệ điều hành; - Nắm được khái niệm hệ điều hành, chức năng, phân loại và các thành phần cơ bản trong hệ điều hành; - Thực hiện các thao tác an toàn với máy tính. Nội dung chính: 1. Khái niệm về hệ điều hành Mục tiêu: Nắm được yêu cầu cần có hệ điều hành; Nắm được khái niệm hệ điều hành. 1.1. Tài nguyên hệ thống Tài nguyên của một trung tâm máy tính được tổng hợp từ ba thành tố, đó là tài nguyên về phần cứng, tài nguyên về phần mềm và tài nguyên về nguồn nhân lực của trung tâm máy tính đó. Trong các tài liệu giới thiệu về một trung tâm máy tính bất kỳ, các số liệu thống kê về phần cứng (số lượng và chủng loại máy tính, hệ thống thiết bị ngoại vi, khả năng liên kết với môi trường ngoài v.v ) luôn là những yếu tố được quan tâm sớm nhất và là thành tố dễ nhận biết nhất về sức mạnh của trung tâm máy tính đó. Tài nguyên về phần mềm cũng được chú ý thông qua các thông tin về hệ điều hành được sử dụng, về các phần mềm ứng dụng đã có tại cơ sở tính toán đó. Hiện nay, tại những trung tâm tính toán mạnh, giá trị (tính theo tiền) thực sự của tài nguyên phần mềm lại cao hơn và vượt trội nhiều so với giá trị của tài nguyên phần cứng. Tài nguyên về nguồn nhân lực cũng được chú ý, tuy rằng trong một số trường hợp, thành tố này lại khó nhận biết và khó đánh giá hơn so hai loại tài nguyên đã nói ở trên. Năng lực về nguồn nhân lực trong hệ thống nhằm đảm bảo việc thực hiện chức năng bảo trì, phục vụ và phát triển hệ thống (kỹ sư hệ thống, kỹ thuật viên, thao tác viên v.v ) thực sự lại đánh giá hơn rất nhiều so với phần cứng và phần mềm. Tuy nhiên, trong giáo trình này, chúng ta hạn chế trong một phạm vi tiếp cận là mọi công việc của hệ điều hành bắt đầu từ hệ thống phần cứng có sẵn và hệ điều hành cần phải hoạt động nhằm phát huy cao nhất năng lực của hệ thống phần cứng đó và vì vậy chúng ta chỉ đề cập đến tài nguyên về phần cứng (có thể kể tới một phần về tài nguyên phần mềm) và định hướng tới vấn đề phát huy hiệu quả khai thác các tài nguyên đó. Để định hướng tới mục tiêu phát huy hiệu quả các thành phần trong tài nguyên phần cứng, cần xem xét một số đặc trưng cơ bản và đánh giá giá trị của mỗi thành phần trong hệ thống phần cứng, hướng tới mục đích đưa ra được các chiến lược ưu tiên thích đáng (hoặc khả dụng) đối với mỗi thành phần khi xây dựng hệ thống các chương trình điều khiển sự hoạt động của máy tính. 8
9. Theo cách tiếp cận của hệ điều hành, các tài nguyên điển hình thuộc phần cứng bao gồm: thiết bị xử lý trung tâm (CPU), bộ nhớ trong, và hệ thống vào – ra (kênh, thiết bị điều khiển thiết bị vào ra và thiết bị vào ra, bộ nhớ ngoài v.v ). CPU và bộ nhớ trong thuộc và khu vực trung tâm còn hệ thống vào – ra thường được xếp vào khu vực ngoại vi của hệ thống máy tính. Trong các thiết bị nói trên, đáng chú ý nhất phải kể đến là CPU và bộ nhớ trong. 〈 Bộ xử lý trung tâm (Central Processing Unit-CPU) Trước hết chúng ta xem xét về các đặc trưng liên quan đến CPU. Việc đánh giá tài nguyên CPU về cơ bản cũng dựa trên các đặc trưng này: tốc độ xử lý, độ dài từ máy, phương pháp thiết kế hệ lệnh máy trong CPU. Tốc độ xử lý là thông số thể hiện mức độ làm việc nhanh chậm của CPU dựa trên các đơn vị biểu diễn tốc độ. Tốc độ xử lý của CPU thường được tính theo tần số đồng hồ nhịp (với đơn vị là MHz-triệu nhịp trong 1 giây) khi xem xét tần số đồng hồ nhịp hoặc số lượng phép tính cơ bản được thực hiện trong một giây (với đơn vị là MIPS – Million Instruction Per Second – triệu phép tính cơ bản trong một giây) khi xem xét theo tốc độ thực hiện phép tính (phép cộng tĩnh – không dấu của một CPU thường được coi là phép tính cơ bản của CPU đó). Thông thường, đơn vị đo MHz được dùng cho một CPU cụ thể hoặc một máy vi tính còn đơn vị đo MIPS được dùng cho một hệ thống CPU của một máy tính lớn. Độ dài từ máy: Từ máy là lượng thông tin đồng thời mà CPU xử lý trong một nhịp làm việc. Độ dài từ máy chính là số lượng bit nhị phân của toán hạng đối số trong phép tính cơ bản của CPU. Trong thời gian gần đây, chúng ta đã quen thuộc với các CPU 8 bit, 16 bit, 32 bit, 64 bit, và số lượng bit nói trên chính là độ dài từ máy. Độ dài của từ máy có quan hệ với tốc độ xử lý. Khi nói đến năng lực hoạt động (tốc độ xử lý thông tin) thực sự của một CPU mà chỉ nói đến tốc độ xử lý mà không nói kèm theo độ dài từ máy là chưa hoàn toàn đầy đủ. Điều đó có thể được diễn giải theo phát biểu như sau “năng lực hoạt động thực sự củaCPU được đánh giá thông qua tốc độ xử lý và độ dài từ máy”. 〈 Bộ nhớ trong (Operative Memory-OM) có một số đặc trưng tiêu biểu như sau: Dung lượng bộ nhớ: Khả năng đồng thời lưu trữ thông tin của bộ nhớ trong. Hiện tại dung lượng của bộ nhớ trong từ vài MB đến vài GB. Đặc trưng tiếp theo của bộ nhớ trong phù hợp với nguyên lý thứ hai theo Von Neumann là: Bộ nhớ được địa chỉ hóa để truy nhập. Đa số các máy tính được địa chỉ hóa theo byte và trong một số trường hợp lại được địa chỉ hóa theo từ máy. Địa chỉ đầu tiên trong bộ nhớ là địa chỉ 0. Lý do của việc chọn địa chỉ đầu tiên là 0 liên quan đến tính chia hết, bởi số 0 chia hết cho mọi số. Khi phân phối bộ nhớ trong cho một đối tượng, trong nhiều trường hợp, địa chỉ vùng bộ nhớ trong của đối tượng phải chia hết cho độ dài vùng bộ nhớ dành cho đối tượng đó hoặc 9
10. chia hết cho số nào đó (ví dụ, phân phối cho một chương trình trong MS-DOS được bắt đầu bởi địa chỉ đoạn là địa chỉ chia hết cho 16). Một đặc trưng (hay cũng vậy là một yêu cầu) mang tính bản chất đối với bộ nhớ trong là: Thời gian truy cập bộ nhớ trong tới mọi địa chỉ nhớ phải đồng nhất; không thể có sự khác biệt giữa thời gian truy cập tới địa chỉ cao với thời gian truy cập tới địa chỉ thấp. Từ đặc trưng này dẫn đến việc đặt ra một yêu cầu là phải tổ chức bộ nhớ trong theo các khối phân cấp để cục bộ dần và việc cục bộ dần như vậy sẽ làm cho việc truy nhập được cân bằng. Nguồn gốc của yêu cầu này liên quan đến tính xác định của thuật toán, hay nói cách khác đi, yêu cầu này nhằm mục tiêu đảm bảo độ tin cậy của hệ thống máy tính. Chúng ta thường thấy bộ nhớ được cấu trúc từ các “ thanh bộ nhớ”, mỗi thanh bộ nhớ lại có thể được phân nhỏ hơn và việc truy nhập bộ nhớ theo cách phân cấp dần theo từng thanh, trong mỗi thanh lại theo từng bộ phận nhỏ hơn có trong thanh đó v.v cho đến khi truy nhập tuần tự trong phần nhỏ nhất chỉ có sai khác thời gian không đáng kể. Để tăng tốc độ truy nhập của CPU đối với bộ nhớ trong, người ta thường gắn CPU với bộ nhớ tạm thời của CPU (được gọi là bộ nhớ cache của CPU). Bộ nhớ cache là thiết bị nhớ đặc biệt với tốc độ truy cập của CPU tới cache của nó cao hơn rất nhiều so với tốc độ truy cập vào bộ nhớ trong. Trong cache chứa một phần nội dung của bộ nhớ trong thường là phần bộ nhớ hiện thời (chương trình và dữ liệu) được CPU đang hướng tới. Quá trình hướng truy nhập bộ nhớ (theo địa chỉ) của CPU được bắt đầu từ việc hướng tới cache, nếu cache chứa phần bộ nhớ đó thì việc hướng địa chỉ kết thúc và thực hiện công việc, ngược lại thực hiện việc hướng tới bộ nhớ trong theo quy tắc thông thường. Chương trình chỉ chạy được khi chương trình và dữ liệu tương ứng của chương trình đó phải có mặt tại bộ nhớ trong (chính xác hơn là chỉ cần bộ phận hiện thời của chương trình và dữ liệu liên quan đến bộ phận đó nằm trong bộ nhớ trong). Cách thức sử dụng bộ nhớ trong đóng vai trò quan trọng nhằm đảm bảo chất lượng hoạt động của hệ thống và vì vậy, bài toán điều khiển bộ nhớ trong có độ ưu tiên cao chỉ sau bài toán điều khiển CPU. 〈 Hệ thống ngoại vi Hệ thống ngoại vi đảm bảo việc chuyển đổi thông tin giữa môi trường ngoài và khu vực trung tâm. Có sự phân cấp trong hệ thống ngoại vi: gần khu vực trung tâm nhất là kênh, sau đó là thiết bị điều khiển thiết bị ngoại vi và ngoài cùng là thiết bị ngoại vi. 1.2. Khái niệm hệ điều hành Hệ thống máy tính là hệ thống kết hợp giữa thiết bị phần cứng và vấn đề điều khiển phân phối công việc trong toàn hệ thống. Để giải quyết bài toán này, không thể dùng phương pháp thủ công mà cần có cơ chế tự động hóa, tức cần có một chương trình điều khiển hoạt động của hệ thống máy tính. Chương trình đó gọi là hệ điều hành, đây là thành phần quan trọng của hệ thống máy tính. -Xét về phía người sử dụng thì hệ điều hành cần phải tạo được môi trường giao diện giữa người sử dụng và máy tính.Thông qua môi trường này cho phép người sử dụng đưa ra các lệnh, chỉ thị điều khiển hoạt động của máy tính. 10
11. -Về phía các chương trình ứng dụng thì hệ điều hành phải tạo môi trường để các chương trình hoạt động, cung cấp các cơ chế cho phép kích hoạt hoặc loại bỏ các chương trình ứng dụng. -Về phía phần cứng thì hệ điều hành phải quản lý các thiết bị một cách có hiệu quả, khai thác được hết các khả năng của thiết bị, cung cấp cho các chương trình và người sử dụng các tài nguyên phần cứng khi có yêu cầu, thu hồi khi cần thiết. Hình 1.1 Mô hình trừu tượng của hệ thống máy tính Vì vậy, hệ điều hành là một tập hợp các chương trình hệ thống có chức năng tạo môi trường giao diện cho người dùng, tạo môi trường hoạt động cho các chương trình ứng dụng, quản lý và khai thác hiệu quả các thiết bị phần cứng. 2. Phân loại hệ điều hành Mục tiêu:Nắm được chức năng, phân loại và các thành phần cơ bản trong hệ điều hành. Nắm được cách thức tải hệ điều hành. 2.1. Các thành phần của hệ điều hành Theo định nghĩa trên đây, hệ điều hành là một tập hợp các chương trình đã được cài đặt sẵn, mỗi chương trình đảm nhận một chức năng nào đó trong hệ thống chức năng của hệ điều hành. Một trong những nguyên tắc phổ biến nhất để nhận biết các thành phần của hệ điều hành là dựa theo chức năng của các chương trình có trong thành phần đó. Theo nguyên tắc này thì các thành phần cơ bản của hệ điều hành là thành phần điều khiển (control programs), thành phần ứng dụng (application programs, còn gọi thành phần xử lý) và các chương trình tiện ích (utilities). 〈 Thành phần điều khiển Thành ph ần điều khiển liên quan đến chức năng điều khiển, phân phối công việc của hệ điều hành. Khi một chương trình điều khiển hoạt động, nó không cho ra một sản phẩm mới (sản phẩm ở đây là các File trên đĩa từ, một kết quả được in ra) 11
12. mà cho tác động đối với sự điều khiển hoạt động của máy tính. Dưới đây liệt kê một số môdun chương trình điển hình thuộc vào thành phần điều khiển: -Chương trình dẫn dắt (điều phối chính, monitor, chương trình giải thích lệnh): Tiếp nhận các nhiệm vụ ( yêu cầu của người dùng) từ dòng vào các nhiệm vụ, sắp xếp phân phối lịch thực hiện v.v đối với từng nhiệm vụ, sau đó trả lại kết quả cho người dùng. -Điều khiển quá trình (bài toán): Thực hiện luân phiên các quá trình (process; bài toán –task) đang tồn tại trong bộ nhớ, mỗi bài toán có các khối chứa thông tin liên quan để chuyển việc thực hiện từ quá trình này sang quá trình khác sao cho việc sử dụng CPU đạt hiệu quả. -Điều khiển dữ liệu: Tổ chức lưu trữ dữ liệu trên vật dẫn ngoài và đảm bảo truy nhập dữ liệu theo yêu cầu của chương trình người dùng. Công việc vào – ra giữa bộ nhớ ngoài và bộ nhớ trong cũng như do liên quan đến một hệ thống thiết bị ngoại vi đa dạng và phong phú nên điều khiển dữ liệu cũng rất đa dạng. -Môdun chương trình tải (loader): Đảm bảo việc đưa các môdun chương trình từ bộ nhớ ngoài vào bộ nhớ trong tại một địa chỉ trong bộ nhớ trong. Trong nhiều trường hợp, môdun chương trình tải còn đảm bảo việc chuyển điều khiển để thực hiện (execute) chương trình được tải vào; -và nhiều thành phần khác 〈 Thành phần ứng dụng Thành phần ứng dụng có trong hệ điều hành bao gồm những chương trình mà khi được thực hiện sẽ tạo ra một sản phẩm mới. Các bộ dịch ngôn ngữ lập trình (compiler), các chương trình tính toán, các chương trình soạn thảo v.v được các hệ điều hành cung cấp nhằm giúp cho người sử dụng có thể chọn lựa phần mềm thích hợp trong lĩnh vực khai thác máy tính của mình. Thành phần ứng dụng rất đa dạng do tính chất đa dạng của yêu cầu người dùng. Thành phần điều khiển hướng đích là sự hiệu quả khai thác máy tính; còn thành phần ứng dụng hướng đích là việc thỏa mãn nhu cầu của người dùng, tăng hiệu suất sử dụng máy tính đối với từng lớp người dùng. 〈 Các chương trình tiện ích Các chương trình tiện ích cung cấp thêm cho người dùng các phương tiện phần mềm làm việc với hệ thống máy tính thuận tiện hơn. Các chương trình liên quan đến cách thức thâm nhập hệ thống, các chương trình sao chép, in ấn nội dung của File, các chương trình làm việc với đĩa v.v được xếp vào thành phần tiện ích. 2.2. Phân loại hệ điều hành Một trong những nguyên tắc phổ biến nhất để phân loại các hệ điều hành (truyền thống) là dựa theo tính chất hoạt động của thành phần điều khiển và việc phân loại hệ điều hành ở đây được thực hiện theo nguyên tắc đó. Tính chất hoạt động của chương trình điều khiển liên quan đến cách thức đưa chương trình vào bộ nhớ trong, chọn chương trình đã có ở bộ nhớ trong ra thực hiện v.v Theo cách thức phân loại này, có thể kể đến hệ điều hành đơn chương trình, hệ điều hành đa chương trình và hệ điều hành thời gian thực. 12
13. a. Hệ điều hành đơn chương trình Trong hệ điều hành đơn chương trình, toàn bộ hệ thống máy tính phục vụ một chương trình từ lúc bắt đầu khi chương trình đó được đưa vào bộ nhớ trong cho đến thời điểm kết thúc chương trình đó. Khi một chương trình người dùng đã được đưa vào bộ nhớ thì nó chiếm giữ mọi tài nguyên của hệ thống và vì vậy chương trình của người dùng khác không thể được đưa vào bộ nhớ trong. Do các thiết bị vào ra có tốc độ làm việc chậm, nên người ta đã cải tiến chế độ đơn chương trình theo hướng sử dụng cách thức đặc biệt (có tên gọi là SPOOLING: Simultaneous Peripheral Operation OnLine; đôi lúc dùng thuật ngữ chế độ SPOOLING cũng với nghĩa là cách thức này), mà theo cách thức này, mọi vấn đề vào ra liên quan đến chương trình được thực hiện thông qua đĩa từ. Chương trình người dùng, thông qua hệ điều hành, chỉ thực hiện vào ra với đĩa từ, còn việc vào ra giữa đĩa từ với các thiết bị khác lại do cơ chế khác đảm nhận và do vậy, thời gian giải bài toán (thời gian chương trình thực hiện) giảm đi. b. Hệ điều hành đa chương trình Đối với hệ điều hành đa chương trình thì trong máy tính, tại mỗi thời điểm có nhiều chương trình đồng thời có mặt ở bộ nhớ trong. Các chương trình này đều có nhu cầu được phân phối bộ nhớ và CPU để thực hiện. Như vậy, bộ nhớ, CPU, các thiết bị ngoại vi là các tài nguyên của hệ thống được chia sẽ cho các chương trình đó. Đặc điểm quan trọng cần lưu ý là các chương trình này phải được “bình đẳng” khi giải quyết các đòi hỏi về tài nguyên. Khái niệm chương trình nói trong chế độ đa chương trình được dùng để chỉ cả chương trình người dùng lẫn chương trình của hệ điều hành. Khi so sánh với hệ điều hành đơn chương trình, có thể nhận thấy ngay một điều là đối với một chương trình cụ thể thì trong chế độ đơn chương trình, chương trình đó sẽ kết thúc nhanh hơn (thời gian chạy ngắn hơn) so với khi nó chạy trong chế độ đa chương trình, nhưng bù lại, trong một khoảng thời gian xác định thì theo chế độ đa chương trình sẽ hoàn thiện được nhiều chương trình (giải được nhiều bài toán) hơn, do đó hiệu quả sử dụng máy tính cao hơn. Như đã đánh giá ở phần trên, một trong những tài nguyên quan trọng nhất của hệ thống máy tính là CPU và việc chia sẽ CPU là một trong những dạng điển hình của việc chia sẽ tài nguyên. 〈 Hệ điều hành hoạt động theo chế độ mẻ Đây là loại hệ điều hành định hướng tới mục tiêu làm cực đại số lượng các bài toán được giải quyết trong một khoảng đơn vị thời gian (có nghĩa là trong một khoảng thời gian thì hướng mục tiêu hoàn thiện được càng nhiều chương trình càng tốt). Ở nước ta những năm trước đây, các máy tính dùng hệ điều hành OS, DOS phổ biến hoạt động theo chế độ mẻ (batch). Các hệ điều hành theo chế độ mẻ lại có thể phân biệt thành hai loại điển hình là MFT và MVT. MFT: Multiprogramming with Fixed number of Tasks 13
14. Khi hệ thống làm việc, đã quy định sẵn một số lượng cố định các bài toán đồng thời ở bộ nhớ trong: bộ nhớ trong được chia thành một số vùng nhớ cố định, các vùng này có biên cố định mà mỗi vùng được dùng để chứa một chương trình. Mỗi chương trình người dùng chỉ được đưa vào một vùng nhớ xác định tương ứng với chương trình đó. Một chương trình chỉ có thể làm việc trong giới hạn của vùng bộ nhớ trong đang chứa nó. MVT: Multiprogramming with Variable number of Tasks Khác với chế độ MFT, trong chế độ MVT, bộ nhớ trong không bị chia sẵn thành các vùng, việc nạp chương trình mới vào bộ nhớ trong còn được tiếp diễn khi mà bộ nhớ trong còn đủ để chứa nó. 〈 Chế độ phân chia thời gian (Time Shared System:TSS) Chế độ phân chia thời gian là chế độ hoạt động điển hình của các hệ điều hành đa người dùng (multi-users). Hệ điều hành hoạt động theo chế độ này định hướng phục vụ trực tiếp người dùng khi chương trình của người dùng đó đang thực hiện, làm cho giao tiếp của người dùng với máy tính là hết sức thân thiện. Liên quan đến hệ điều hành hoạt động theo chế độ này là các khái niệm lượng tử thời gian, bộ nhớ ảo v.v Trong hệ TSS, tại cùng thời điểm có nhiều người dùng đồng thời làm việc với máy tính: mỗi người làm việc với máy thông qua trạm cuối (terminal) và vì vậy, hệ thống đã cho phép máy tính thân thiện với người dùng. Hệ điều hành phân phối CPU lần lượt cho từng chương trình người dùng, mỗi chương trình được chiếm giữ CPU trong một khoảng thời gian như nhau (khoảng thời gian đó được gọi là lượng tử thời gian): có thể thấy phổ biến về lượng tử thời gian điển hình là khoảng 0,05s. Máy tính làm việc với tốc độ cao, chu kỳ quay lại phục vụ cho từng chương trình người dùng là rất nhanh, mỗi người đều có cảm giác rằng mình chiếm toàn bộ tài nguyên hệ thống. Bộ nhớ luôn chứa chương trình của mọi người dùng, vì vậy xảy ra tình huống toàn bộ bộ nhớ trong không đủ để chứa tất cả chương trình người dùng hiện đang thực hiện, vì thế đối với hệ điều hành TSS nảy sinh giải pháp sử dụng bộ nhớ ảo: sử dụng đĩa từ như vùng mở rộng không gian nhớ của bộ nhớ trong. c. Hệ điều hành thời gian thực Nhiều tài nguyên trong lĩnh vực điều khiển cần được giải quyết không muộn hơn một thời điểm nhất định, và vì vậy, đối với các máy tính trong lĩnh vực đó cần hệ điều hành thời gian thực (RT: Real Time). Trong hệ thời gian thực, mỗi bài toán được gắn với một thời điểm thời gian (deadtime) và bài toán phải được giải quyết không muộn hơn thời điểm đã cho đó: Nếu bài toán hoàn thiện muộn hơn thời điểm đó thì việc giải quyết nó trở nên không còn có ý nghĩa nữa. Hệ thời gian thực có thể được coi như một trường hợp của hệ đa chương trình hoạt động theo chế độ mẻ có gắn thêm thời điểm kết thúc cho mỗi bài toán. 2.3. Tính chất cơ bản của hệ điều hành a)Tin cậy 14
15. Mọi hoạt động, mọi thông báo của HĐH đều phải chuẩn xác, tuyệt đối. chỉ khi nào biết chắc chắn là đúng thì HĐH mới cung cấp thông tin cho người sử dụng. Để đảm bảo được yêu cầu này, phần thiết bị kỹ thuật phải có những phương tiện hỗ trợ kiểm tra tính đúng đắn của dữ liệu trong các phép lưu trữ và xử lý. Trong các trường hợp còn lại HĐH thông báo lỗi và ngừng xử lý trao quyền quyết định cho người vận hành hoặc người sử dụng. b) An toàn Hệ thống phải tổ chức sao cho chương trình và dữ liệu không bị xoá hoặc bị thay đổi ngoài ý muốn trong mọi trường hợp và mọi chế độ hoạt động. Điều này đặc biệt quan trọng khi hệ thống là đa nhiệm. Các tài nguyên khác nhau đòi hỏi những yêu cầu khác nhau trong việc đảm bảo an toàn. c) Hiệu quả Các tài nguyên của hệ thống phải đợc khai thác triệt để sao chon gay cả điều kiện tài nguyên hạn chế vẫn có thể giải quyết những yêu cầu phức tạp. Một khía cạnh quan trọng của đảm bảo hiệu quả là duy trì đồng bộ trong toàn bộ hệ thống, không để các thiết bị tốc độ chậm trì hoãn hoạt động của toàn bộ hệ thống. d) Tổng quát theo thời gian HĐH phải có tính kế thừa, đồng thời có khả năng thích nghi với những thay đổi cso thể cso trong tương lai. Tính thừa kế là rất quan trọng ngay cả với các hệ điều hành thế hệ mới. Đối với việc nâng cấp, tính kế thừa là bắt buộc. Các thao tác, thông báo là không được thay đổi, hoặc nếu có thì không đáng kể và phải được hướng dẫn cụ thể khi chuyển từ phiên bản này sang phiên bản khác, bằng các phương tiện nhận biết của hệ thống. Đảm bảo tính kế thừa sẽ duy trì và phát triển đội ngũ người sử dụng-một nhân tố quan trọng để HĐH có thể tồn tại. Ngoài ra người sử dụng cũng rất quan tâm, liệu những kinh nghiệm và kiến thức của mình về HĐH hiện tại còn được sử dụng bao lâu nữa. Khả năng thích nghi với những thay đổi đòi hỏi HĐH phải được thiết kế theo một số nguyên tắc nhất định. e) Thuận tiện Hệ thống phải dễ dàng sử dụng, có nhiều mức hiệu quả khác nhau tuỳ theo kiến thức và kinh nghiệm người dùng. Hệ thống trợ giúp phong phú để người sử dụng có thể tự đào tạo ngay trong quá trình khai thác. Trong một chừng mực nào đó, các tính chất trên mâu thuẫn lẫn nhau. Mỗi HĐH có một giải pháp trung hoà, ưu tiên hợp lý ở tính chất này hay tính chất khác. 2.4. Phân lớp các chương trình trong thành phần điều khiển Một trong những cách phân lớp các chương trình thuộc thành phần điều khiển là dựa theo bài toán mà lớp chương trình đó giải quyết. Các bài toán cơ bản nhất nảy sinh trong quá trình điều khiển hệ thống máy tính được liệt kê như dưới đây. 〈 Điều khiển dữ liệu Điều khiển dữ liệu (điều khiển file, điều khiển vào ra) bao gồm các môdun chương trình của hệ điều hành liên quan đến việc tổ chức lưu trữ và quản lý dữ liệu trên vật dẫn ngoài, chuyển dữ liệu từ bộ nhớ ngoài vào bộ nhớ trong và ngược lại. Quá trình chuyển dữ liệu thường được thực hiện qua hai giai đoạn: chuyển đổi dữ 15
16. liệu thực sự giữa khu vực ngoại vi với bộ nhớ trong và chuyển đổi dữ liệu nội bộ bộ nhớ trong. Tính đa dạng của thiết bị ngoài dẫn tới việc có nhiều cách tổ chức, lưu trữ, cập nhật dữ liệu v.v 〈 Điều khiển CPU, điều khiển quá trình Để tối ưu hóa sự làm việc của CPU thì hoạt động của CPU được đảm bảo từ hệ thống điều khiển CPU: làm như thế nào để thời gian hoạt động có ích của CPU là cao nhất. Có thể tiếp cận theo khía cạnh điều khiển quá trình (chương trình, bài toán) với việc phân chia tài nguyên dùng chung, đồng bộ hóa, xử lý song song khi quan tâm đến mối quan hệ giữa các quá trình đang đồng thời tồn tại. 〈 Điều khiển bộ nhớ Việc quản lý bộ nhớ trong để nắm vững vùng nhớ nào rỗi, vùng nhớ nào bận và việc phân phối bộ nhớ cho một chương trình và giải phóng bộ nhớ khi nó thực hiện xong là chức năng chính của điều khiển bộ nhớ. Điều khiển bộ nhớ làm sao đạt mục tiêu sử dụng bộ nhớ càng tối ưu càng tốt. 2.5. Chức năng cơ bản của hệ điều hành a) Quản lý tiến trình Một tiến trình là một chương trình đang được thi hành. Một tiến trình phải sử dụng tài nguyên như thời gian sử dụng CPU, bộ nhớ, tập tin, các thiết bị nhập xuất để hoàn tất công việc của nó. Các tài nguyên này được cung cấp khi tiến trình được tạo hay trong quá trình thi hành. Một tiến trình là hoạt động (active) hoàn toàn-ngược lại với một tập tin trên đĩa là thụ động (passive)-với một bộ đếm chương trình cho biết lệnh kế tiếp được thi hành.Việc thi hành được thực hiện theo cơ chế tuần tự , CPU sẽ thi hành từ lệnh đầu đến lệnh cuối. Một tiến trình được coi là một đơn vị làm việc của hệ thống. Một hệ thống có thể có nhiều tiến trình cùng lúc , trong đó một số tiến trình là của hệ điều hành, một số tiến trình là của người sử dụng. các tiến trình này có thể diễn ra đồng thời. Vai trò của hệ điều hành trong việc quản lý tiến trình là : - Tạo và hủy các tiến trình của người sử dụng và của hệ thống. - Tạm dừng và thực hiện tiếp một tiến trình. - Cung cấp các cơ chế đồng bộ tiến trình. - Cung cấp các cơ chế giao tiếp giữa các tiến trình. - Cung cấp cơ chế kiểm soát deadlock b) Quản lý bộ nhớ chính : Trong hệ thống máy tính hiện đại, bộ nhớ chính là trung tâm của các thao tác, xử lý. Bộnhớ chính có thể xem như một mảng kiểu byte hay kiểu word. Mỗi phần tử đều có địa chỉ. Đó là nơi lưu dữ liệu được CPU truy xuất một cách nhanh chóng so với các thiết bị nhập/xuất. CPU đọc những chỉ thị từ bộ nhớ chính. Các thiết bị nhập/xuất cài đặt cơ chế DMA cũng đọc và ghi dữ liệu trong bộ nhớ chính. Thông thường bộ nhớ chính chứa các thiết bị mà CPU có thể định vị trực tiếp. Ví dụ 16
17. CPU truy xuất dữ liệu từ đĩa, những dữ liệu này được chuyển vào bộ nhớ qua lời gọi hệ thống nhập/xuất. Một chương trình muốn thi hành trước hết phải được ánh xạ thành địa chỉ tuyệt đối và nạp vào bộ nhớ chính.Khi chương trình thi hành, hệ thống truy xuất các chỉ thị và dữ liệu của chương trình trong bộ nhớ chính. Ngay cả khi tiến trình kết thúc, dữ liệu vẫn còn trong bộ nhớ cho đến khi một tiến trình khác được ghi chồng lên. Hệ điều hành có những vai trò như sau trong việc quản lý bộ nhớ chính : - Lưu giữ thông tin về các vị trí trong bộ nhớ đã được sử dụng và tiến trình nào đang sử dụng. - Quyết định tiến trình nào được nạp vào bộ nhớ chính, khi bộ nhớ đã có thể dùng được. - Cấp phát và thu hồi bộ nhớ khi cần thiết. c) Quản lý bộ nhớ phụ : Bộ nhớ chính quá nhỏ để có thể lưu giữ mọi dữ liệu và chương trình, ngoài ra dữ liệu sẽ mất khi không còn được cung cấp năng lượng. Hệ thống máy tính ngày nay cung cấp hệ thống lưu trữ phụ. Đa số các máy tính đều dùng đĩa để lưu trữ cả chương trình và dữ liệu. Hầu như tất cả chương trình : chương trình dịch, hợp ngữ, thủ tục, trình soạn thảo, định dạng đều được lưu trữ trên đĩa cho tới khi nó được thực hiện, nạp vào trong bộ nhớ chính và cũng sử dụng đĩa để chứa dữ liệu và kết quả xử lý. Vai trò của hệ điều hành trong việc quản lý đĩa : - Quản lý vùng trống trên đĩa. - Định vị lưu trữ. - Lập lịch cho đĩa. d) Quản lý hệ thống vào/ ra : Một trong những mục tiêu của hệ điều hành là che dấu những đặc thù của các thiết bị phần cứng đối với người sử dụng thay vào đó là một lớp thân thiện hơn, người sử dụng dễ thao tác hơn. Một hệ thống vào/ra bao gồm : - Thành phần quản lý bộ nhớ chứa vùng đệm (buffering), lưu trữ (caching) và spooling (vùng chứa). - Giao tiếp điều khiển thiết bị (device drivers) tổng quát. - Bộ điều khiển cho các thiết bị xác định. Chỉ có bộ điều khiển cho các thiết bị xác định mới hiểu đến cấu trúc đặc thù của thiết bị mà nó mô tả. e) Quản lý hệ thống tập tin : Máy tính có thể lưu trữ thông tin trong nhiều dạng thiết bị vật lý khác nhau : băng từ, đĩa từ, đĩa quang, Mỗi dạng có những đặc thù riêng về mặt tổ chức vật lý. Mỗi thiết bị có một bộ kiểm soát như bộ điều khiển đĩa (disk driver) và có những tính chất riêng. Những tính chất này là tốc độ, khả năng lưu trữ, tốc độ truyền dữ liệu và cách truy xuất. 17
18. Để cho việc sử dụng hệ thống máy tính thuận tiện, hệ điều hành cung cấp một cái nhìn logic đồng nhất về hệ thống lưu trữ thông tin. Hệ điều hành định nghĩa một đơn vị lưu trữ logic là tập tin. Hệ điều hành tạo một ánh xạ từ tập tin đến vùng thông tin trên đĩa và truy xuất những tập tin này thông qua thiết bị lưu trữ. Một tập tin là một tập hợp những thông tin do người tạo ra nó xác định. Thông thường một tập tin đại diện cho một chương trình và dữ liệu. Dữ liệu của tập tin có thể là số, là ký tự, hay ký số. Vai trò của hệ điều hành trong việc quản lý tập tin : - Tạo và xoá một tập tin. - Tạo và xoá một thư mục. - Hỗ trợ các thao tác trên tập tin và thư mục. - Ánh xạ tập tin trên hệ thống lưu trữ phụ. - Sao lưu dự phòng các tập tin trên các thiết bị lưu trữ. f) Hệ thống bảo vệ : Trong một hệ thống nhiều người sử dụng và cho phép nhiều tiến trình diễn ra đồng thời, các tiến trình phải được bảo vệ đối với những hoạt động khác. Do đó, hệ thống cung cấp cơ chế để đảm bảo rằng tập tin, bộ nhớ, CPU, và những tài nguyên khác chỉ được truy xuất bởi những tiến trình có quyền. Ví dụ, bộ nhớ đảm bảo rằng tiến trình chỉ được thi hành trong phạm vi địa chỉ của nó. Bộ thời gian đảm bảo rằng không có tiến trình nào độc chiếm CPU. Cuối cùng các thiết bị ngoại vi cũng được bảo vệ. Hệ thống bảo vệ là một cơ chế kiểm soát quá trình truy xuất của chương trình, tiến trình, hoặc người sử dụng với tài nguyên của hệ thống. Cơ chế này cũng cung cấp cách thức để mô tả lại mức độ kiểm soát. Hệ thống bảo vệ cũng làm tăng độ an toàn khi kiểm tra lỗi trong giao tiếp giữa những hệ thống nhỏ bên trong. g) Hệ thống thông dịch 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à hệ thống thông dịch lệnh, đó là giao tiếp giữa người sử dụng và hệ điều hành. Một số hệ điều hành đặt cơ chế dòng lệnh bên trong hạt nhân, số khác như MS-DOS và UNIX thì xem hệ điều hành như là một chương trình đặt biệt, được thi hành khi các công việc bắt đầu hoặc khi người sử dụng login lần đầu tiên. Các lệnh đưa vào hệ điều hành thông qua bộ điều khiển lệnh. Trong các hệ thống chia xẻ thời gian một chương trình có thể đọc và thông dịch các lệnh điều khiển được thực hiện một cách tự động. Chương trình này thường được gọi là bộ thông dịch điều khiển card, cơ chế dòng lệnh hoặc Shell. Chức năng của nó rất đơn giản đó là lấy lệnh kế tiếp và thi hành. Mỗi hệ điều hành sẽ có những giao tiếp khác nhau, dạng đơn giản theo cơ chế dòng lệnh, dạng thân thiện với người sử dụng như giao diện của Macintosh có các biểu tượng, cửa sổ thao tác dùng chuột. 18
19. Các lệnh có quan hệ với việc tạo và quản lý các tiến trình, kiểm soát nhập xuất, quản lý bộ lưu trữ phụ, quản lý bộ nhớ chính, truy xuất hệ thống tập tin và cơ chế bảo vệ. 2.6. Nhân của hệ điều hành, tải hệ điều hành 〈 Nhân của hệ điều hành (Kernel) Hệ điều hành là bộ bao gồm một số lượng lớn các chương trình, trong nhiều trường hợp đó là một bộ chương trình đồ sộ và vì vậy không thể đưa tất cả các chương trình của hệ điều hành vào bộ nhớ trong được. Nhân của hệ điều hành thông thường bao gồm: -Môdun chương trình tải (Loader). Chức năng chủ yếu của môdun chương trình tải là đưa một chương trình vào bộ nhớ trong bắt đầu từ địa chỉ nào đó để sau đó cho phép chương trình đã được tải nhận điều khiển để chạy hoặc không. -Môdun chương trình dẫn dắt (monitor). Việc chọn lựa các bước làm việc của toàn bộ hệ thống do môdun này đảm nhiệm. -Môdun chương trình lập lịch (scheduler): chọn chương trình tiếp theo để chạy. -Một số môdun chương trình khác -Cùng một số thông tin hệ thống là các tham số hệ thống. Nảy sinh một số vấn đề liên quan đến nhân hệ điều hành: Vấn đề (bài toán) đầu tiên liên quan nhân là: chọn những môdun hệ thống nào để đưa vào nhân? Nhân quá lớn (nhân chứa nhiều môdun chương trình) thì đỡ tốn thời gian tải các môdun trong hệ điều hành vào bộ nhớ trong song do chiếm nhiều bộ nhớ trong nên lại giảm dung lượng bộ nhớ trong có thể sử dụng được cho chương trình của người sử dụng. Nhân quá bé, thì công việc tải sẽ thường xuyên hơn, thời gian dành cho việc nạp môdun của hệ điều hành vào bộ nhớ trong sẽ tăng lên và như thế thời gian CPU dành cho chương trình người dùng giảm đi, hiệu suất sử dụng CPU thấp. Vấn đề thứ hai đối với nhân là: Phân phối bộ nhớ trong cho nhân như thế nào? Phân phối liên tục hay rời rạc? Một trong những nguyên lý cơ bản của việc nạp nhân là phân phối bộ nhớ cho nhân phải đảm bảo vùng bộ nhớ liên tục còn lại đạt lớn nhất có thể có và không gây cản trở cho việc nâng cấp hệ điều hành. 〈 Các mức giao tiếp trong hệ thống máy tính 19
20. Người dùng Chương trình ứng dụng Dịch vụ hệ thống Nhân Phần cứng máy tính Hình 1.2. Cấu trúc mức của hệ thống máy tính 〈 Tải hệ điều hành Hệ điều hành không thể tự đặt ngay trong máy tính được. Do hệ điều hành là tập hợp các chương trình được cài đặt sẵn nhưng ở trên vật dẫn ngoài (các file từ đĩa cứng) và muốn máy tính hoạt động được phải qua một giai đoạn đưa hệ điều hành vào máy để làm việc. Giai đoạn tải hệ điều hành (còn gọi là tải hệ thống) có thể được phân ra các bước sau đây: Khởi động chương trình tải nguyên thủy. Trong máy tính thường có đoạn chương trình nguyên thủy với tên IPL (Initial Program Loader) đã được cứng hóa (thường đặt trong EPROM) sẽ tự bị kích hoạt để thực hiện mỗi khi bật máy gây xung điện. IPL bắt đầu làm việc. IPL kiểm tra tính sẵn sàng của hệ thống thiết bị. Tương ứng với mỗi thiết bị, IPL lập ra khối điều khiển thiết bị UCB (Unit Control Block) chứa các thông số về thiết bị đó. IPL tải đoạn chương trình “mồi”, thường đặt ở sector đầu tiên ở đĩa chứa hệ điều hành, vào bộ nhớ trong tại những địa chỉ định sẵn và truyền điều khiển cho đoạn chương trình mồi. Trong một số hệ điều hành người ta gọi đoạn chương trình mồi là chương trình khởi động nhân. Đoạn chương trình thực hiện chức năng tải nhân của hệ điều hành vào. Sau khi tải nhân xong, chương trình mồi sẽ trao điều khiển cho chương trình dẫn dắt để hệ thống bắt đầu làm việc. 3. Sơ lược lịch sử phát triển của HĐH Mục tiêu: Nắm được lịch sử phát triển hệ điều hành. *Thế hệ 1 (1945 – 1955) Vào khoảng giữa thập niên 1940, Howard Aiken ở Havard và John von Neumann ở Princeton, đã thành công trong việc xây dựng máy tính dùng ống chân không. Những máy này rất lớn với hơn 10000 ống chân không nhưng chậm hơn nhiều so với máy rẻ nhất ngày nay. Mỗi máy được một nhóm thực hiện tất cả từ thiết kế, xây dựng lập trình, thao tác đến quản lý. Lập trình bằng ngôn ngữ máy tuyệt đối, thường là bằng cách dùng 20
21. bảng điều khiển để thực hiện các chức năng cơ bản. Ngôn ngữ lập trình chưa được biết đến và hệ điều hành cũng chưa nghe đến. Vào đầu thập niên 1950, phiếu đục lỗ ra đời và có thể viết chương trình trên phiếu thay cho dùng bảng điều khiển. *Thế hệ 2 (1955 – 1965) Sự ra đời của thiết bị bán dẫn vào giữa thập niên 1950 làm thay đổi bức tranh tổng thể. Máy tính trở nên đủ tin cậy hơn. Nó được sản xuất và cung cấp cho các khách hàng. Lần đầu tiên có sự phân chia rõ ràng giữa người thiết kế, người xây dựng, người vận hành, người lập trình, và người bảo trì. Để thực hiện một công việc (một chương trình hay một tập hợp các chương trình), lập trình viên trước hết viết chương trình trên giấy (bằng hợp ngữ hay FORTRAN) sau đó đục lỗ trên phiếu và cuối cùng đưa phiếu vào máy. Sau khi thực hiện xong nó sẽ xuất kết quả ra máy in. Hệ thống xử lý theo lô ra đời, nó lưu các yêu cầu cần thực hiện lên băng từ, và hệ thống sẽ đọc và thi hành lần lượt. Sau đó, nó sẽ ghi kết quả lên băng từ xuất và cuối cùng người sử dụng sẽ đem băng từ xuất đi in. Hệ thống xử lý theo lô hoạt động dưới sự điều khiển của một chương trình đặc biệt là tiền thân của hệ điều hành sau này. Ngôn ngữ lập trình sử dụng trong giai đoạn này chủ yếu là FORTRAN và hợp ngữ. *Thế hệ 3 (1965 – 1980) Trong giai đoạn này, máy tính được sử dụng rộng rãi trong khoa học cũng như trong thương mại. Máy IBM 360 là máy tính đầu tiên sử dụng mạch tích hợp (IC). Từ đó kích thước và giá cả của các hệ thống máy giảm đáng kể và máy tính càng phỗ biến hơn. Các thiết bị ngoại vi dành cho máy xuất hiện ngày càng nhiều và thao tác điều khiển bắt đầu phức tạp. Hệ điều hành ra đời nhằm điều phối, kiểm soát hoạt động và giải quyết các yêu cầu tranh chấp thiết bị. Chương trình hệ điều hành dài cả triệu dòng hợp ngữ và do hàng ngàn lập trình viên thực hiện. Sau đó, hệ điều hành ra đời khái niệm đa chương. CPU không phải chờ thực hiện các thao tác nhập xuất. Bộ nhớ được chia làm nhiều phần, mỗi phần có một công việc (job) khác nhau, khi một công việc chờ thực hiện nhập xuất CPU sẽ xử lý các công việc còn lại. Tuy nhiên khi có nhiều công việc cùng xuất hiện trong bộ nhớ, vấn đề là phải có một cơ chế bảo vệ tránh các công việc ảnh hưởng đến nhau. Hệ điều hành cũng cài đặt thuộc tính spool. Giai đoạn này cũng đánh dấu sự ra đời của hệ điều hành chia xẻ thời gian như CTSS của MIT. Đồng thời các hệ điều hành lớn ra đời như MULTICS, UNIX và hệ thống các máy mini cũng xuất hiện như DEC PDP-1. *Thế hệ 4 (1980 - nay) Giai đoạn này đánh dấu sự ra đời của máy tính cá nhân, đặc biệt là hệ thống IBM PC với hệ điều hành MS-DOS và Windows sau này. Bên cạnh đó là sự phát triển mạnh của các hệ điều hành tựa Unix trên nhiều hệ máy khác nhau như Linux. 21
22. Ngoài ra, từ đầu thập niên 90 cũng đánh dấu sự phát triển mạnh mẽ của hệ điều hành mạng và hệ điều hành phân tán. Thế hệ 1 Thế hệ 3 Thế hệ 4 Thế hệ 2 Hệ điều Hệ điều Hệ điều Hệ điều hành hành phân hành tự trị hành mạng tập tán phối hợp Hình 1.3. Phân bố các hệ điều hành CÂU HỎI VÀ BÀI TẬP 1. Trình bày khái niệm về tài nguyên hệ thống.Cho ví dụ. 2. Nêu khái niệm hệ điều hành. 3. Nêu các chức năng cơ bản hệ điều hành. 4. Các hệ điều hành MSDos, Window XP, Window 7, Linux thuộc loại hệ điều hành nào. 5. Nêu các thành phần của hệ điều hành. HƯỚNG DẪN TRẢ LỜI 1. Có ba tài nguyên hệ thống: tài nguyên về phần cứng, tài nguyên về phần mềm và tài nguyên về nguồn nhân lực (ví dụ về phần cứng có CPU,Ram,máy in; về phần mềm:hệ điều hành Window server 2008, chương trình quản lý bán hàng, ) 2. Hệ điều hành là một tập hợp các chương trình hệ thống có chức năng tạo môi trường giao diện cho người dùng, tạo môi trường hoạt động cho các chương trình ứng dụng, quản lý và khai thác hiệu quả các thiết bị phần cứng. 3. Chức năng hệ điều hành: quản lý tiến trình, quản lý bộ nhớ, quản lý hệ thống vào-ra, quản lý hệ thống tập tin, hệ thông dịch lệnh. 4. MSDos là hệ điều hành đơn chương trình; Window XP, Window 7,Linux là hệ điều hành đa chương trình. 5. Các thành phần hệ điều hành: thành phần điều khiển, thành phần ứng dụng, các chương trình tiện ích. 22
23. CHƯƠNG 2: ĐIỀU KHIỂN DỮ LIỆU Mã chương: MHSCMT 16.02 Mục tiêu: Sau khi học xong bài học này, sinh viên có khả năng: - Nắm được cách thức hệ điều hành (HĐH) tổ chức lưu trữ và tìm kiếm dữ liệu dữ liệu trên hệ thống máy tính - Nắm được các giai đoạn HĐH thực hiện điều khiển dữ liệu và sự phân công công việc giữa chương trình hệ thống (thuộc HĐH) và chương trình người dùng trong quá trình vào – ra dữ liệu - Nắm được cách thức tổ chức lưu trữ dữ liệu, các phương pháp quản lý trên bộ nhớ ngoài. Nội dung chính: 1. Các phương pháp tổ chức và truy nhập dữ liệu Mục tiêu: Nắm được cách thức HĐH tổ chức lưu trữ và tìm kiếm dữ liệu dữ liệu trên hệ thống máy tính 1.1. Các phương pháp tổ chức dữ liệu 〈 Khái niệm file (bộ dữ liệu) Dữ liệu được xử lý trong máy tính được bảo quản lâu dài trên băng từ, đĩa từ, đĩa quang v.v và dữ liệu được tập hợp lại một cách có tổ chức thành các file dữ liệu theo mục đích sử dụng. File có thể là chương trình của người dùng, một chương trình của hệ điều hành, một văn bản, một tập hợp dữ liệu. Trong một số hệ điều hành, một số thiết bị ngoại vi cũng được quan niệm như file dữ liệu. Theo góc độ quan sát của người dùng, dữ liệu trong một file lại được tổ chức thành các bản ghi lôgic (gọi tắt bản ghi), mà mỗi bản ghi lôgic có thể là một byte hoặc một cấu trúc dữ liệu nào đó. Bản ghi chính là đơn vị dữ liệu mà chương trình người dùng quan tâm đến và xử lý theo mỗi nhịp làm việc: file là tập hợp (được người dùng quan niệm là một dãy) các bản ghi có tổ chức. Thông thường, trong file tồn tại một thứ tự giữa các bản ghi, thứ tự đó thể hiện vị trí logic giữa các bản ghi với nhau (chẳng hạn như thứ tự đưa bản ghi vào file). Phụ thuộc vào mục đích sử dụng (sắp xếp, tìm kiếm bản ghi trong file), người ta đưa ra bốn kiểu tổ chức phổ biến với file. Đó là tổ chức kế tiếp, tổ chức chỉ số kế tiếp, tổ chức thư viện và tổ chức trực tiếp. Ngoài ra có thể kể đến việc tổ chức file trong chế độ bộ nhớ ảo trên đĩa từ. 〈 Tổ chức kế tiếp Bản ghi lôgic sắp xếp đúng theo trình tự làm việc đối với chúng: thứ tự trình bày trên vật dẫn ngoài trùng với thứ tự đưa bản ghi vào trong file. Tổ chức kế tiếp chính là kiểu tổ chức duy nhất đối với các file đặt trên bìa đục lỗ, băng từ v.v Rõ ràng là đối với file gồm các bản ghi trên chồng bìa hay băng từ, việc đi đến một bản 23
24. ghi nào đó phải vượt qua các bản ghi được xếp trước nó. Tuy nhiên, trên các thiết bị trực truy như đĩa từ, đĩa quang cũng cho phép file được tổ chức kế tiếp. 〈 Tổ chức chỉ số kế tiếp Trong nhiều trường hợp, việc sắp xếp và tìm kiếm các bản ghi không theo thứ tự phát sinh ra chúng, mà theo một thứ tự nào đó gắn với bản ghi: mỗi bản ghi được tương ứng với một chỉ số và việc sắp xếp, tìm kiếm bản ghi theo chỉ số. Liên quan đến file được tổ chức theo chỉ số kế tiếp có một hệ thống chỉ số bao gồm chỉ số chính, chỉ số trụ, chỉ số rãnh. Hệ thống chỉ số: để làm việc với file tổ chức chỉ số kế tiếp cần có hệ thống chỉ số gắn với file đó. Một file có thể được lưu trữ trên nhiều đĩa từ, và vì vậy, chỉ số chính cho biết trên mỗi đĩa từ chứa dữ liệu của file bao gồm các bản ghi có các chỉ số thuộc khoảng nào. Bảng dưới đây biểu diễn một bảng chỉ số chính đối với một file được tổ chức theo dạng chỉ số kế tiếp. Tên đĩa Chỉ số max VOL1 1000 VOL2 2000 VOL3 4000 . . Theo bảng này, các bản ghi có chỉ số không vượt quá 1000 nằm trong đĩa có tên là VOL1, các bản ghi có chỉ số từ 1001 tới 2000 nằm trên đĩa có tên VOL2, Việc tìm kiếm bản ghi không tiến hành lần lượt qua từng bản ghi mà được hạn chế theo không gian chỉ số: bước đầu tiên xác định đĩa từ chứa bản ghi đó và đi tới tìm kiếm trên đĩa từ đó. Với cấu trúc tương tự nhằm mục đích định vị dần được bản ghi theo chỉ số, trên mỗi đĩa chứa file lại có một bảng chỉ số trụ, cho biết mỗi trụ chứa các bản ghi thuộc khoảng chỉ số nào. Thấp hơn nữa, trên mỗi trụ lại có một bảng chỉ số rãnh cho biết cụ thể các chỉ số trên mỗi rãnh thuộc trụ nói trên. 〈 Tổ chức truy nhập trực tiếp (trực truy) Trong file được tổ chức trực truy, tồn tại sự tương ứng giữa định vị bản ghi của file với địa chỉ thực sự trên đĩa từ mà không phải qua một hệ thống chỉ số nào cả. Trong quá trình làm việc với file dữ liệu, người dùng chủ động làm việc theo sự tương ứng nói trên và tổ chức trực truy đảm bảo cho người dùng khả năng linh hoạt trong xử lý bản ghi. 〈 Tổ chức thư viện File tổ chức thư viện bao gồm một thư mục và một tập hợp file thành phần mà mỗi file thành phần lại được tổ chức kế tiếp. Mỗi file thành phần được gọi là một chương và mỗi chương có tên để truy nhập đến. 24
25. Ví dụ về file được tổ chức thư viện có thể kể đến như các file thư viện (đuôi .LIB) trong các ngôn ngữ lập trình, mỗi một môdun chương trình mẫu như một chương của file thư viện. 〈 Tổ chức theo bộ nhớ ảo Trong chế độ phân chia thời gian phải sử dụng bộ nhớ ảo. Các file có liên quan đến bộ nhớ ảo được tổ chức theo những quy cách riêng, tiện lợi cho việc luân chuyển, trao đổi giữa bộ nhớ thực và bộ nhớ ảo. 〈 Chú ý rằng, khi thiết kế hệ điều hành, với mỗi phương pháp tổ chức file, các chuyên gia tạo ra hệ điều hành phải xây dựng được các môdun chương trình tương ứng. Nếu một hệ điều hành cho phép có nhiều phương pháp tổ chức file có thể làm cho việc tạo lập và thi hành hệ điều hành trở nên quá phức tạp. Vì vậy, một hệ điều hành không cần thiết phải có tất cả các cách chức tổ chức file nêu trên. 1.2. Các phương pháp truy nhập dữ liệu Tồn tại hai cách thức truy nhập dữ liệu phổ biến nhất: truy nhập tuần tự và truy nhập cơ sở. 〈 Cách thức truy cập tuần tự Lần lượt các bản ghi theo đúng trình tự trong file (từ bản ghi đầu tiên đến bản ghi cuối cùng) được “xem xét” và “xử lý”. Theo cách thức truy nhập tuần tự thì hoàn toàn biết trước được bản ghi lôgic tiếp theo được xem xét xử lý là bản ghi nào, và vì vậy, hệ điều hành biết được vị trí trên vật dẫn ngoài của bản ghi cần xử lý tiếp theo. Khi đã biết được vị trí, để có sẵn bản ghi tiếp theo cho chương trình xử lý, cách tốt nhất là đọc trước bản ghi cần xử lý vào bộ nhớ trong. Cách thức truy nhập tuần tự cho mức độ tự động hóa cao, tuy nhiên chỉ áp dụng được với các file được tổ chức kế tiếp hoặc chỉ số kế tiếp. Để đảm bảo được tính tự động hóa cao như thế, chương trình hệ thống phải đảm bảo thực hiện mọi công việc chuẩn bị liên quan đến bản ghi cho chương trình người dùng xử lý. 〈 Cách thức truy nhập cơ sở Theo cách thức truy nhập cơ sở, hệ thống hoàn toàn không có trước thông tin về bản ghi nào là bản ghi tiếp theo để xử lý nên mức độ tự động hóa thấp: Người lập trình tự mình phải xác định bản ghi cần xử lý, và để tìm được nó, mọi vấn đề về đồng bộ hóa phải được đặt ra. Tuy mức độ tự động hóa thấp, nhưng bù lại, cách thức truy nhập cơ sở cho chương trình người sử dụng làm việc với file dữ liệu hết sức mềm dẻo và linh hoạt, đạt được mức độ chủ động cao của chương trình người dùng đối với file. 〈 Các phương pháp tổ chức và truy nhập dữ liệu phổ biến Trong hệ điều hành cần có các chương trình làm việc với các kiểu tổ chức file và cách thức truy nhập dữ liệu. Giải pháp tạo ra một chương trình của hệ điều hành làm việc phù hợp đối với tất cả các kiểu tổ chức và truy nhập file là không thực tiễn (vì làm như vậy quá trình vào ra dữ liệu trở nên rất phức tạp, không linh hoạt) vì vậy phương án thích hợp hơn là chia ra một số phương pháp tổ chức và truy nhập dữ liệu cụ thể, đối với mỗi phương pháp này có chương trình riêng phục vụ nó. Có sáu phương pháp tổ chức truy nhập dữ liệu cụ thể phổ biến, đó là: 25
26. Phương pháp truy nhập tuần tự cho file tổ chức kế tiếp (QSAM: Queue Sequel Access Method) Phương pháp truy nhập cơ sở cho File tổ chức kế tiếp (BSAM) Phương pháp truy nhập tuần tự cho file tổ chức chỉ số kế tiếp (QISAM:Queue Index Sequel Access Method) Phương pháp truy nhập cơ sở cho file tổ chức chỉ số kế tiếp (BISAM) Phương pháp truy nhập cơ sở cho file tổ chức trực tiếp (BDAM: Basic Direct Access Method); Phương pháp truy nhập cơ sở cho file tổ chức thư viện (BPAM: Basic Partition Access Method). 1.3 Chức năng của hệ thống điều khiển dữ liệu Các chức năng cơ bản của hệ thống điều khiển dữ liệu bao gồm các chức năng liên quan đến việc tổ chức bảo quản dữ liệu trên vật dẫn ngoài và truy nhập chúng để chương trình người dùng thao tác. Dưới đây sẽ trình bày chi tiết hơn về các chức năng của hệ thống điều khiển dữ liệu. 〈 Bảo quản dữ liệu trên vật dẫn ngoài Trên vật dẫn ngoài, mà phổ dụng nhất là trên băng từ và đĩa từ, các file dữ liệu (và chương trình) được lưu trữ để sau này có thể dễ dàng làm việc với chúng. Việc lưu trữ các file theo những quy định chặt chẽ của hệ điều khiển dữ liệu để không ảnh hưởng lẫn nhau, không chồng chéo. Như vậy, trên vật dẫn ngoài, việc tổ chức thông tin phải theo những quy định của hệ điều hành. Tồn tại một số phương pháp quản lý vùng nhớ trên vật dẫn ngoài để phân phối cho các file (sử dụng bảng FAT, sử dụng Bitmap, ). Thực tế là không gian trên vật dẫn ngoài không dành cho việc lưu trữ nội dung của các file mà còn phải có các vùng không gian để chứa thông tin liên quan đến đặc trưng của vật mang tin và tình trạng phân phối không gian cho các file trên vật mang tin đó. Trên đĩa từ, các hệ điều hành thường cung cấp cho người dùng một hệ thống phân cấp dạng cấu trúc cây tổ chức các file có trong đĩa đó. Ngoài khái niệm file, hệ thống còn sử dụng các thư mục cho việc quản lý lưu trữ file. 〈 Đảm bảo cách thức tổ chức khác nhau đối với dữ liệu và định vị chúng Như đã nói, mỗi cách tổ chức dữ liệu kèm theo những mặt mạnh và mặt yếu riêng và phù hợp với mục tiêu sử dụng nhất định. Người dùng mong muốn file dữ liệu mà mình làm việc được tổ chức theo cách thức mà người đó mong muốn. Hệ điều hành cần đảm bảo việc lưu trữ file trên vật dẫn ngoài phù hợp với cách tổ chức nội tại (các bản ghi lôgic có trong file) nhằm thỏa mãn yêu cầu phong phú của người dùng. 〈 Thực hiện các phương pháp truy nhập khác nhau tới dữ liệu phụ thuộc vào phương pháp tổ chức chúng Mỗi phương pháp truy nhập bao gồm các môdun chương trình liên quan đến việc tổ chức nội tại của file và cách thức truy nhập của chúng. Khi cho phép các cách tổ chức khác nhau đối với file trên vật dẫn ngoài đồng thời cần cho phép chúng được truy nhập theo các phương pháp phong phú. Ngay cả đối với một file trên vật 26
27. dẫn ngoài, tại thời điểm này người dùng có thể sử dụng cách thức QSAM song một lúc khác, người dùng có thể sử dụng cách thức BDAM (nếu điều đó có thể được). Chức năng này đòi hỏi hệ điều hành xử lý mềm dẻo theo yêu cầu người dùng. 〈 Catalog dữ liệu và thực hiện việc tìm kiếm tự động hóa dữ liệu đã được catalog theo tên ký hiệu mà không cần theo địa chỉ Trong nhiều hệ điều hành, các file có thể được catalog hóa. Những file thường xuyên được sử dụng (các chương trình ứng dụng, các file dữ liệu người dùng v.v ) nếu được catalog hóa thì việc tìm kiếm chúng khá dễ dàng. Trong một đĩa từ đặc biệt, được gọi là đĩa thường trực, có bảng catalog: bảng này cho thấy sự tương ứng giữa tên một file đã catalog hóa với địa chỉ tìm kiếm trực tiếp nó (tên đĩa từ chứa file đó, vị trí cụ thể đặt file nói trên trên đĩa từ). Mỗi khi làm việc với một file đã catalog, hệ thống yêu cầu đặt đĩa từ có tên xác định vào và tự động tìm ngay được file cho người dùng. 〈 Cho phép sự độc lập cao nhất của chương trình đối với dữ liệu của chương trình đó Việc lưu trữ các file trên vật dẫn ngoài do hệ thống tự động đặt, không phụ thuộc vào chương trình người dùng. Điều đó cho phép sự độc lập cao nhất có thể có giữa chương trình và dữ liệu. Con người không quan tâm đến việc hệ điều hành đã đặt file ở đâu trên vật dẫn ngoài, chỉ quan tâm đến tên của nó. Sự độc lập nói trên còn cho phép nhiều người dùng có thể sử dụng chung tài nguyên dữ liệu và như vậy, giá trị của dữ liệu vì thế càng được nâng cao. 2. Bản ghi và khối Mục tiêu: Nắm được khái niệm bản ghi logic và bản ghi vật lý; Nắm được khái niệm kết khối và tách khối. Vận dụng được để đưa ra ví dụ cụ thể của quá trình kết khối và tách khối trong hệ điều hành. 2.1. Bản ghi lôgic và bản ghi vật lý a.Bản ghi lôgic và bản ghi vật lý Một mặt, file được tổ chức thành các đơn vị dữ liệu để chương trình ứng dụng xử lý: đó là các bản ghi lôgic. Quy cách và nội dung của bản ghi lôgic được xác định theo chương trình ứng dụng. Mặt khác, việc lưu trữ file trên vật dẫn ngoài tuân theo các quy tắc làm việc của hệ điều hành đối với vật dẫn ngoài đó: file được xếp trên bộ nhớ ngoài thành các bản ghi vật lý (phổ biến hơn được gọi là Khối). Thông thường, khối đơn vị bộ nhớ ngoài mà hệ điều hành thực hiện việc đọc/ghi đối với file. Chẳng hạn, trong MS DOS, một cluster chính là một khối trên đĩa từ và file được lưu trữ trên một tập hợp các cluster của đĩa từ. Một bài toán điển hình liên quan đến các khối trên đĩa từ là bài toán quản lý không gian đĩa để nắm bắt được trạng thái rỗi/bận của các khối trên đĩa để biết được khối nào rỗi (để phân phối cho nhu cầu mới), khối nào bận là khối đã chứa nội dung của một file (để tránh ghi đè lên nó). Việc đọc/ghi đối với một file cũng cần có được các thông tin trạng thái như vậy. Tồn tại một số phương pháp giải quyết bài toán đó. 27
28. Một phương pháp đơn giản là sử dụng bảng định vị file (File Allocation Table: FAT) mà MS DOS sử dụng. Phương pháp phổ dụng hơn là phương pháp Bit map, trong đó người ta dùng một vùng, được gọi là Bit map, để trình bày tình trạng rỗi/ bận của tất cả các khối trên đĩa. Theo phương pháp này, mỗi khối trên đĩa được tương ứng với một bit trong vùng bit map và tình trạng rỗi/bận của khối đó được xác định bằng giá trị 0/1 của bit tương ứng. b. Bản ghi theo tổ chức của File: có ba dạng tổ chức bản ghi lôgic Thông thường có ba dạng phổ biến là dạng cố định, dạng động và dạng không xác định. Dạng bản ghi của file dữ liệu sẽ quy định tới cách thức xử lý của hệ điều hành đối với file. Dạng cố định (F): Mọi bản ghi trong file có độ dài cố định và như nhau (mỗi bản ghi có thể có dấu hiệu điều khiển). Làm việc với các file gồm các bản ghi dạng F rất tiện lợi, từ vị trí của bản ghi đầu tiên và số thứ tự của một bản ghi có thể nhận được vị trí của bản ghi đó. Việc định vị bản ghi theo số liệu là hoàn toàn xác định. Mặt khác, các công việc chuẩn bị để xử lý các bản ghi dạng F là đơn giản. Ví dụ: các bản ghi trong một file có kiểu trong ngôn ngữ lập trình PASCAL thuộc dạng F Dạng động (V): độ dài của bản ghi thay đổi từ bản ghi này cho tới bản ghi khác, song ngay khi xử lý bản ghi thì hệ điều hành đã biết độ dài của bản ghi đó: Trong một phần nội dung của bản ghi đã ghi nhận độ dài của bản ghi. Tùy thuộc vào độ dài mỗi bản ghi có thể chuẩn bị các công việc liên quan để xử lý chúng, chẳng hạn việc tách các bản ghi từ một khối sau khi đọc từ vật dẫn ngoài vào bộ nhớ trong. Dạng không xác định (U): độ dài bản ghi không thể xác định, cuối mỗi bản ghi mới có dấu hiệu kết thúc bản ghi. Việc xử lý các file mà bản ghi thuộc dạng U nói chung có tính tự động hóa thấp hơn so với file gồm các bản ghi dạng F và V. 2.2. Kết khối và tách khối Một khối có thể chứa một hoặc một vài bản ghi và ngược lại, một bản ghi có thể được xếp trên một hoặc một số khối. Như vậy, tồn tại mối quan hệ giữa khối với bản ghi và điều đó liên quan đến vấn đề xác định bản ghi theo khối. Việc tổ chức file trên vật dẫn ngoài theo các khối là công việc của hệ điều hành (do các chương trình của phương pháp truy nhập đảm nhận) và như đã nói là cần đảm bảo tính độc lập với chương trình người dùng cho nên việc đưa một khối vào bộ nhớ trong hoặc đưa dữ liệu lên một khối là do hệ điều hành đảm nhận. Ta có thể gọi quá trình đó là vào ra vậy lý. Sau khi hệ điều hành đã đưa một khối vào bộ nhớ trong, cần phải xác định bản ghi hiện thời để chương trình người dùng xử lý. Đó là quá trình tách khối. Tách khối là quá trình từ các khối đưa ra được các bản ghi cần tìm có liên quan đến khối đó. Quá trình này diễn ra sau khi hệ điều hành đã đọc một khối từ vật dẫn ngoài vào bộ nhớ trong và trước khi chương trình người dùng xử lý bản ghi. Tùy thuộc vào phương pháp truy nhập dữ liệu mà tách khối hoặc do hệ điều hành hoặc do chính chương trình người dùng đảm nhận. 28
29. Sau khi chương trình người dùng chuẩn bị xong nội dung bản ghi, thông tin trên bản ghi đó đã đúng như yêu cầu của người dùng, cần đưa nó lên vật dẫn ngoài để lưu trữ lâu dài. Như đã biết, hệ điều hành ghi thông tin lên thiết bị nhớ ngoài theo đơn vị là khối, vì vậy bản ghi nói trên phải được xếp vào một khối tương ứng (quá trình đó gọi là kết khối). Khi khối đã đầy đủ thông tin được xử lý thì hệ điều hành cần đặt đúng khối đã có vào vị trí đã dành cho nó trên vật dẫn ngoài. Về hình thức, kết khối là quá trình ngược lại với quá trình tách khối. Kết khối diễn ra sau khi chương trình người dùng chuẩn bị xong nội dung bản ghi và đưa bản ghi đó vào khối để đưa ra thiết bị nhớ ngoài. Chương trình người dùng xử lý dữ liệu tại những vùng bộ nhớ theo quy định của chương trình, được gọi là vùng làm việc. Hệ điều hành đọc khối vào các vùng nhớ trung gian được gọi là vùng đệm (buffer vào) trước khi dữ liệu được chương trình xử lý. Sau khi chương trình xử lý dữ liệu xong, bản ghi đã hoàn thiện được kết khối vào các vùng nhớ đệm ra (buffer ra) trước khi được hệ điều hành đưa ra vật dẫn ngoài. Khối ngoài Khối ngoài Do hệ điều hành Buffer vào Vùng Buffer ra làm Bộ nhớ trong việc Hình 2.1 Sơ đồ tách khối / kết khối Sơ đồ trong hình 2.1 diễn tả sơ lược về hai quá trình trên. Trong sơ đồ này, giai đoạn đọc vật lý (khi vào) và ghi vật lý (khi ra) do chương trình của phương pháp truy nhập phải đảm nhận hoặc do chương trình người dùng đảm nhận tùy thuộc vào file dữ liệu nói trên được mở làm việc theo phương pháp truy nhập vào. Theo sơ đồ trên đây, ta có thể nhận thấy rằng mỗi phương pháp tổ chức và truy nhập dữ liệu bao gồm một số thành phần cơ bản như sau (môdun chương trình có thể được phát triển thành nhóm môdun chương trình): -Môdun chương trình đảm bảo chức năng tổ chức lưu trữ và định vị trên vật dẫn ngoài; -Môdun chương trình đảm bảo vào/ra mỗi khối (bản ghi vật lý) đối với mỗi khối xác định; -Môdun chương trình đảm bảo việc tách/kết khối theo bản ghi đối với file xác định. 29
30. 3. Quy trình điều khiển chung vào ra Mục tiêu: Nắm được quy trình điều khiển vào ra. 3.1 Các khối điều khiển dữ liệu Các chương trình hệ thống phải quản lý được các thông tin về các File đang làm việc trong hệ thống, cách thức truy nhập chúng, thông tin về vật dẫn ngoài chứa nội dung các File đó. Để có thể thực hiện được các chức năng của mình, hệ thống xây dựng (hoặc đòi hỏi) một số khối điều khiển dữ liệu. Các khối điều khiển dữ liệu điển hình được giới thiệu ở dưới đây. Khối FCB (File Control Block): chứa thông tin quản lý làm việc đối với File. Trong một số hệ điều hành thuật ngữ “thẻ File” có ý nghĩa thay thế tương đương. Trong khối này có những thông tin cụ thể về File tương ứng: số lượng bản ghi, bản ghi hiện thời, địa chỉ các khối liên kết v.v Khối DCB (Data Control Block): chương trình người dùng được viết theo ngôn ngữ bậc cao thì chương tình dịch tạo DCB, còn nếu được viết theo hợp ngữ thì chương trình người dùng tạo DCB. Khối DCB chứa mọi thông tin liên quan đến điều khiển vào ra: tổ chức File, phương pháp truy nhập, địa chỉ các khối điều khiển liên quan v.v Khối UCB (Unit Control Block): chứa thông tin về thiết bị vào ra, vật dẫn ngoài tương ứng, giúp cho quá trình điều khiển thiết bị. Ngoài ra còn có một số khối mở rộng khác cho điều khiển dữ liệu. 3.2 Ví dụ về sơ đồ chung điều khiển vào ra trong hệ điều hành Qua xem xét sơ đồ ở hình 2.3 chúng ta thấy: Chương trình người dùng và chương trình của phương pháp truy nhập ở vùng bộ nhở RAM (địa chỉ của chúng tùy theo trạng thái máy trước khi chúng được nạp vào). Các chương trình gọi ngắt vào ra, thân ngắt và kết thúc ngắt được đặt trên những địa chỉ xác định. Trong thân ngắt có chứa lệnh bắt đầu vào/ra(SIO: start Input/Output). Như đã biết điều khiển vào ra do kênh đảm nhận và kênh hoạt động theo hệ thống lệnh riêng (lệnh kênh). Gọi ngắt READ EXCP hướng SIO Hoàn thiện hướng tới Chương Chương trình supervisor trình của hệ điều 30
31. (Trong sơ đồ trên, vùng nằm trong đường rời nét là thuộc các vùng nhớ cố định của bộ nhớ trong) Hình 2.3. Một ví dụ về điều khiển vào – ra trong hệ điều hành OS Chi tiết quá trình được tóm tắt như sau (xét các máy theo hệ OS): -Chuẩn bị một chương trình kênh (dãy các lệnh kênh) -Xây dựng từ địa chỉ kênh (CAW: channel address Word) -Gửi từ địa chỉ kênh nói trên vào một địa chỉ quy định sẵn -Đưa ra lệnh SIO và tải chương trình kênh (theo kênh và thiết bị tương ứng) -Phân tích kết quả việc tải chương trình kênh -Sau khi tải thành công chương trình kênh, CPU và kênh làm việc song song -Sau khi kết thúc (tốt hay không tốt) công việc vào ra, kênh đưa ra tín hiệu cho ngắt vào/ra. Chương trình xử lý ngắt sẽ phân tích tín hiệu trên để biết thành công hay không và dấu hiệu sai sót. Chương trình người dùng, dựa vào kiểm tra kết quả vào/ra để xử lý: nếu hoàn thiện thì công việc tiếp tục; nếu có sai sót sẽ tùy từng ngữ cảnh để xử lý. Nếu chỉ ra rằng, thao tác vào ra không thể kết thúc ngay được thì chương trình sẽ chuyển sang trạng thái chờ đợi. 4. Tổ chức lưu trữ dữ liệu trên bộ nhớ ngoài Mục tiêu: Nắm được cách thức tổ chức lưu trữ dữ liệu, các phương pháp quản lý trên bộ nhớ ngoài. 4.1.Các khái niệm cơ bản Yêu cầu quản lý bộ nhớ ngoài Khi cần lưu trữ các chương trình hoặc dữ liệu, các hệ thống máy tính bắt buộc phải sử dụng bộ nhớ ngoài (đĩa từ, băng từ, ). Nhiệm vụ chính hệ điều hình phải đảm bảo các chức năng sau: Quản lý không gian nhớ tự do trên bộ nhớ ngoài (free space manage) Cấp phát không gian nhớ tự do (allocation methods) Cung cấp các khả năng định vị bộ nhớ ngoài Lập lịch cho bộ nhớ ngoài Cấu trúc vật lý đĩa từ Đĩa từ bao gồm một hoặc nhiều lá đĩa đặt đồng trục. Mỗi mặt đĩa chia thành các rãnh tròn đồng tâm gọi là track, mỗi track được chia thành các cung gọi là sector. Trên mỗi mặt đĩa có đầu đọc ghi dữ liệu. Hệ điều hành xem đĩa như mảng một chiều mà thành phần là các khối đĩa (disk block). Mỗi khối đĩa ghi các thông tin về mặt đĩa, track, sector mà hệ điều hành có thể định vị trên đó. 31
32. 4.2.Các phương pháp quản lý không gian tự do Vì không gian trống là giới hạn nên chúng ta cần dùng lại không gian từ các tập tin bị xoá cho các tập tin mới nếu có thể. Để giữ vết của không gian đĩa trống, hệ thống duy trì một danh sách không gian trống. Danh sách không gian trống ghi lại tất cả khối đĩa trống. Để tạo tập tin, chúng ta tìm trong danh sách không gian trống lượng không gian được yêu cầu và cấp phát không gian đó tới tập tin mới. Sau đó, không gian này được xoá từ danh sách không gian trống. Khi một tập tin bị xoá, không gian đĩa của nó được thêm vào danh sách không gian trống. Mặc dù tên của nó là danh sách nhưng danh sách không gian trống có thể không được cài như một danh sách. a) Bit vector Thường thì danh sách không gian trống được cài đặt như một bản đồ bit (bit map) hay một vector bit (bit vector). Mỗi khối được biểu diễn bởi 1 bit. Nếu khối là trống, bit của nó được đặt là 1, nếu khối được cấp phát bit của nó được đặt là 0. Thí dụ, xét một đĩa khi các khối 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, và 27 là trống và các khối còn lại được cấp phát. Bản đồ bit không gian trống sẽ là: 001111001111110001100000011100000 Lợi điểm chính của tiếp cận này là tính tương đối đơn giản và hiệu quả của nó trong việc tìm khối trống đầu tiên, hay n khối trống tiếp theo trên đĩa. Một lần nữa, chúng ta thấy các đặc điểm phần cứng định hướng chức năng phần mềm. Tuy nhiên, các vector bit là không đủ trừ khi toàn bộ vector được giữ trong bộ nhớ chính. Giữ nó trong bộ nhớ chính là có thể cho các đĩa nhỏ hơn, như trên các máy vi tính nhưng không thể cho các máy lớn hơn. Một đĩa 1.3 GB với khối 51 bytes sẽ cần một bản đồ bit 332 KB để ghi lại các khối trống. Gom bốn khối vào một nhóm có thể giảm số này xuống còn 83 KB trên đĩa. 32
33. b) Danh sách liên kết Hình 2.4 danh sách không gian trống được liên kết trên đĩa Một tiếp cận khác để quản lý bộ nhớ trống là liên kết tất cả khối trống, giữ một con trỏ tới khối trống đầu tiên trong một vị trí đặc biệt trên đĩa và lưu nó trong bộ nhớ. Khối đầu tiên này chứa con trỏ chỉ t ới khối đĩa trống tiếp theo, Trong thí dụ trên, chúng ta có thể giữ một con trỏ chỉ tới khối 2 như là khối trống đầu tiên. Khối 2 sẽ chứa một con trỏ chỉ tới khối 3, khối này sẽ chỉ tới khối 4, (như hình X-10). Tuy nhiên, cơ chế này không hiệu quả để duyệt danh sách, chúng ta phải đọc mỗi khối, yêu cầu thời gian nhập/xuất đáng kể. Tuy nhiên, duyệt danh sách trống không là hoạt động thường xuyên. Thường thì, hệ điều hành cần một khối trống để mà nó có thể cấp phát khối đó tới một tập tin, vì thế khối đầu tiên trong danh sách trống được dùng. Phương pháp FAT kết hợp với đếm khối trống thành cấu trúc dữ liệu cấp phát. c) Nhóm Thay đổi tiếp cận danh sách trống để lưu địa chỉ của n khối trống trong khối trống đầu tiên. n-1 khối đầu tiên này thật sự là khối trống. Khối cuối cùng chứa địa chỉ của n khối trống khác, Sự quan trọng của việc cài đặt này là địa chỉ của một số lượng lớn khối trống có thể được tìm thấy nhanh chóng, không giống như trong tiếp cận danh sách liên kết chuẩn. d) Bộ đếm Một tiếp cận khác đạt được lợi điểm trong thực tế là nhiều khối kề có thể được cấp phát và giải phóng cùng lúc, đặc biệt khi không gian được cấp phát với giải thuật cấp phát kề hay thông qua nhóm. Do đó, thay vì giữ một danh sách n địa chỉ đĩa trống, chúng ta có thể giữ địa chỉ của khối trống đầu tiên và số n khối kề trống theo sau khối đầu tiên. Mỗi mục từ trong danh sách không gian trống sau đó chứa một địa chỉ đĩa và bộ đếm. Mặc dù mỗi mục từ yêu cầu nhiều không gian hơn một địa chỉ đĩa đơn, nhưng toàn bộ danh sách sẽ ngắn hơn với điều kiện là bộ đếm lớn hơn 1. 33
34. 4.3.Các phương pháp cấp phát không gian tự do Tính tự nhiên của truy xuất trực tiếp đĩa cho phép chúng ta khả năng linh hoạt trong việc cài đặt tập tin. Trong hầu hết mọi trường hợp, nhiều tập tin sẽ được lưu trên cùng đĩa. Vấn đề chính là không gian cấp phát tới các tập tin này như thế nào để mà không gian đĩa được sử dụng hiệu quả và các tập tin có thể được truy xuất nhanh chóng. Ba phương pháp quan trọng cho việc cấp phát không gian đĩa được sử dụng rộng rãi: cấp phát kề, liên kết và chỉ mục. Mỗi phương pháp có ưu và nhược điểm. Một số hệ thống hỗ trợ cả ba. Thông dụng hơn, một hệ thống sẽ dùng một phương pháp cụ thể cho tất cả tập tin. a) Cấp phát kề Phương pháp cấp phát kề yêu cầu mỗi tập tin chiếm một tập hợp các khối kề nhau trên đĩa. Các địa chỉ đĩa định nghĩa một thứ tự tuyến tính trên đĩa. Với thứ tự này, giả sử rằng chỉ một công việc đang truy xuất đĩa, truy xuất khối b+1 sau khi khối b không yêu cầu di chuyển trước. Khi di chuyển đầu đọc được yêu cầu (từ cung từ cuối cùng của cylinder tới cung từ đầu tiên của cylinder tiếp theo), nó chỉ di chuyển một rãnh (track). Do đó, số lượng tìm kiếm đĩa được yêu cầu cho truy xuất kề tới các tập tin được cấp phát là nhỏ nhất. Cấp phát kề của một tập tin được định nghĩa bởi địa chỉ đĩa và chiều dài (tính bằng đơn vị khối) của khối đầu tiên. Nếu tập tin có n khối và bắt đầu tại khối b thì nó chiếm các khối b, b+1, b+2, ,b+n-1. Mục từ thư mục cho mỗi tập tin hiển thị địa chỉ của khối bắt đầu và chiều dài của vùng được cấp phát cho tập tin này 34
35. Hình 2.5 danh sách không gian trống được cấp phát kề b) Cấp phát liên kết Cấp phát liên kết giải quyết vấn đề của cấp phát kề. Với cấp phát liên kết, mỗi tập tin là một danh sách các khối đĩa được liên kết; các khối đĩa có thể được phân tán khắp nơi trên đĩa. Thư mục chứa một con trỏ chỉ tới khối đầu tiên và các khối cuối cùng của tập tin. Thí dụ, một tập tin có 5 khối có thể bắt đầu tại khối số 9, tiếp tục là khối 16, sau đó khối 1, khối 10 và cuối cùng khối 25 . Mỗi khối chứa một con trỏ chỉ tới khối kế tiếp. Các con trỏ này không được làm sẳn dùng cho người dùng. Hình 2.6 danh sách không gian trống được cấp phát liên kết Một thay đổi quan trọng trên phương pháp cấp phát liên kết là dùng bảng cấp phát tập tin (file allocation table-FAT). Điều này đơn giản nhưng là phương pháp cấp phát không gian đĩa hiệu quả được dùng bởi hệ điều hành MS-DOS và OS/2. Một phần đĩa tại phần bắt đầu của mỗi phân khu được thiết lập để chứa bảng này. Bảng này có một mục từ cho mỗi khối đĩa và được lập chỉ mục bởi khối đĩa. FAT được dùng nhiều như là một danh sách liên kết. Mục từ thư mục 35
36. chứa số khối của khối đầu tiên trong tập tin. Mục từ bảng được lập chỉ mục bởi số khối đó sau đó chứa số khối của khối tiếp theo trong tập tin. Chuỗi này tiếp tục cho đến khi khối cuối cùng, có giá trị cuối tập tin đặc biệt như mục từ bảng. Các khối không được dùng được hiển thị bởi giá trị bảng 0. Cấp phát một khối mới tới một tập tin là một vấn đề đơn giản cho việc tìm mục từ bảng có giá trị 0 đầu tiên và thay thế giá trị kết thúc tập tin trước đó với địa chỉ của khối mới. Sau đó, số 0 được thay thế với giá trị kết thúc tập tin. Một thí dụ minh hoạ là cấu trúc FAT của hình X-7 cho một tập tin chứa các khối đĩa 217, 618 và 339. Hình 2.7 Bảng cấp phát tập tin Cơ chế cấp phát FAT có thể dẫn tới số lượng lớn tìm kiếm đầu đọc đĩa nếu FAT không được lưu trữ(cache). Đầu đọc đĩa phải di chuyển tới điểm bắt đầu của phân khu để đọc FAT và tìm vị trí khối sau đó di chuyển tới vị trí của chính khối đĩa đó. Trong trường hợp xấu nhất, cả hai di chuyển xảy ra cho mỗi khối đĩa. Lợi điểm là thời gian truy xuất ngẫu nhiên được cải tiến vì đầu đọc đĩa có thể tìm vị trí của bất cứ khối nào bằng cách đọc thông tin trong FAT. c) Cấp phát được lập chỉ mục Cấp phát liên kết giải quyết việc phân mãnh ngoài và vấn đề khai báo kích thước của cấp phát kề. Tuy nhiên, cấp phát liên kết không hỗ trợ truy xuất trực tiếp hiệu quả vì các con trỏ chỉ tới các khối được phân tán với chính các khối đó qua đĩa và cần được lấy lại trong thứ tự. Cấp phát được lập chỉ mục giải quyết vấn đề này bằng cách mang tất cả con trỏ vào một vị trí: khối chỉ mục (index block). Mỗi tập tin có khối chỉ mục của chính nó, khối này là một mảng các địa chỉ khối đĩa. Mục từ thứ i trong khối chỉ mục chỉ tới khối i của tập tin. Thư mục chứa địa chỉ của khối chỉ mục (như hình 2.8). Để đọc khối i, chúng ta dùng con trỏ trong m ục từ kh ối chỉ m ục để tìm và đọc khối mong muốn. Cơ ch ế này tương tự như cơ chế phân trang. 36
37. Hình 2 . 8 Cấp phát không gian đĩa được lập chỉ mục 4.4.Lập lịch cho đĩa Khái niệm về lập lịch cho đĩa Lập lịch cho đĩa là xây dựng các thuật toán dịch chuyển đầu từ đọc ghi sao cho thời gian truy nhập đĩa là tối ưu nhất. Một số phương pháp lập lịch -FCFS -SSTF -Scan -C-Scan -Look -C-Look 4.5.Hệ file Dữ liệu được xử lý trong máy tính được bảo quản lâu dài trên băng từ, đĩa từ, đĩa quang v.v và dữ liệu được tập hợp lại một cách có tổ chức thành các file dữ liệu theo mục đích sử dụng. File có thể là chương trình của người dùng, một chương trình của hệ điều hành, một văn bản, một tập hợp dữ liệu. Trong một số hệ điều hành, một số thiết bị ngoại vi cũng được quan niệm như file dữ liệu. Theo góc độ quan sát của người dùng, dữ liệu trong một file lại được tổ chức thành các bản ghi lôgic (gọi tắt bản ghi), mà mỗi bản ghi lôgic có thể là một byte hoặc một cấu trúc dữ liệu nào đó. Bản ghi chính là đơn vị dữ liệu mà chương trình người dùng quan tâm đến và xử lý theo m ỗi nhịp làm việc: file là tập hợp 37
38. (được người dùng quan niệm là một dãy) các bản ghi có tổ chức. Thông thường, trong file tồn tại một thứ tự giữa các bản ghi, thứ tự đó thể hiện vị trí logic giữa các bản ghi với nhau (chẳng hạn như thứ tự đưa bản ghi vào file). CÂU HỎI VÀ BÀI TẬP 1. Nêu các phương pháp tổ chức và truy nhập dữ liệu. 2. Nêu chức năng của hệ thống điều khiển dữ liệu. 3. Khái niệm về kết khối và tách khối. 4. Nêu vai trò buffer. 5. Trình bày các khối điều khiển dữ liệu 6. Trình bày các phương pháp của quản lý và cấp phát không gian nhớ trên bộ nhớ ngoài của hệ điều hành. 7. Khái niệm file. HƯỚNG DẪN TRẢ LỜI 1. Các phương pháp tổ chức : tổ chứ kế tiếp, tổ chức chỉ số kế tiếp, tổ chức truy nhập trực tiếp, tổ thư viện, tổ chức theo bộ nhớ ảo. Các phương pháp truy nhập dữ liệu: cách thức truy nhập tuần tự, cách thức truy nhập cơ sở. 2. Chức năng của hệ thống điều khiển dữ liệu: Bảo quản dữ liệu trên thiết bị ngoài, đảm bảo cách thức tổ chức khác nhau đối với dữ liệu, thực hiện các phương pháp truy nhập khác nhau tới dữ liệu, catalog dữ liệu và thực hiện việc tìm kiếm tự động hóa dữ liệu theo tên kí hiệu mà không cần theo địa chỉ. 3. Kết khối diễn ra sau khi chương trình người dùng chuẩn bị xong nội dung bản ghi và đưa bản ghi đó vào khối để đưa ra thiết bị nhớ ngoài. Tách khối là quá trình từ các khối đưa ra được các bản ghi cần tìm có liên quan đến khối đó. Quá trình này diễn ra sau khi hệ điều hành đã đọc một khối từ vật dẫn ngoài vào bộ nhớ trong và trước khi chương trình người dùng xử lý bản ghi. 4. Buffer là vùng nhớ đệm trung gian lưu trữ tạm thời, thuận tiện cho việc vào –ra. 5. Có các khối điều khiển: Khối FCB (File Control Block), Khối DCB (Data Control Block), Khối UCB (Unit Control Block). 6. Các phương pháp quản lý không gian nhớ : quản lý bằng bit vectơ (bitmap), quản lý bằng danh sách móc nối. Các phương pháp cấp phát không gian nhớ: cấp phát kề (liên tục), cấp phát liên kết, cấp phát chỉ số. 7. Xem phần khái niệm file. 38
39. CHƯƠNG 3: ĐIỀU KHIỂN BỘ NHỚ Mã chương: MHSCMT 16.03 Mục tiêu: Sau khi học xong bài học này, sinh viên có khả năng: - Nắm được nguyên lý điều khiển bộ nhớ của HĐH, phương thức tối ưu hóa việc phân phối bộ nhớ, tránh lãng phí và chia sẻ tài nguyên bộ nhớ. Nội dung chính: 1. Quản lý và bảo vệ bộ nhớ Mục tiêu : Nắm được các khái niệm về bộ nhớ, quản lý phân phối bộ nhớ và vấn đề bảo vệ bộ nhớ. 1.1. Một số khái niệm liên quan đến bộ nhớ Đơn vị lưu trữ và địa chỉ hóa bộ nhớ trong được chọn là byte hoặc từ máy song phổ biến nhất là byte. Địa chỉ được bắt đầu từ 0. Trong các lệnh, địa chỉ (của chương trình, tạo ra không gian địa chỉ) được cho theo một dạng sau đây : Địa chỉ tuyệt đối: địa chỉ thực sự trong bộ nhớ. Ví dụ về việc truy nhập địa chỉ tuyệt đối xảy ra trong chương trình là khi cần chuyển điều khiển từ đơn vị chương trình này sang đơn vị chương trình khác. Địa chỉ tuyệt đối thường được cho theo độ dài từ máy, chẳng hạn, với từ máy 32 bit không gian địa chỉ lên đến 4 GB. Trường hợp ngoại lệ như trong máy vi tính 16 bit, nếu dùng một từ máy địa chỉ hóa chỉ tới 64KB, thì địa chỉ tuyệt đối được cho bằng hai từ máy : một từ máy được dùng để chỉ segment, một từ dùng để chỉ offset. Các toán hạng trong một lệnh có thể là địa chỉ của một vùng nhớ nào đó (một, hai và thậm chí ba địa chỉ vùng nhớ) nếu chỉ dùng địa chỉ tuyệt đối thì độ dài của lệnh máy sẽ dài và kéo theo sự tăng đáng kể độ dài của toàn bộ chương trình. Đó là một trong những lý do chính dẫn tới cần dùng giải pháp sử dụng địa chỉ tương đối. Địa chỉ tương đối : Có nhiều cách thức để biểu thị địa chỉ tương đối. Một trong những cách điển hình là đối với địa chỉ liên tiếp nhau sẽ sử dụng chung một thanh ghi (được gọi là thanh ghi cơ sở) chứa địa chỉ đầu tiên trong dãy đó, các địa chỉ còn lại được quy chiếu bằng một gia số so với địa chỉ đầu (nội dung của thanh ghi cơ sở). Gia số chính là khoảng cách của địa chỉ đang tính với địa chỉ đầu. Khi quy định một thanh ghi xác định nào đó là thanh ghi cơ sở thì trong lệnh không cần thiết nêu thanh ghi cơ sở nữa mà chỉ cần chỉ ra gia số địa chỉ, mà gia số thường nhỏ nên số bit dành cho nó trong lệnh là rất ít (việc dùng các thanh ghi CS, DS, SS, ES trong máy vi tính là ví dụ đáp ứng mục đích này). Một phương pháp dùng địa chỉ tương đối thường hay gặp là ngoài thanh ghi cơ sở, thì địa chỉ các thành phần trong một cấu trúc dữ liệu còn được tương ứng với một thanh ghi chỉ số : địa chỉ các thành phần trong cấu trúc dữ liệu đó được biểu diễn bằng gia số đối với địa chỉ ở thanh ghi chỉ số. Như vậy, trong lệnh có thể có thêm số hiệu của thanh ghi chỉ số song mỗi máy tính lại chỉ có rất ít thanh ghi nên 39
40. số bit dành cho địa chỉ cũng giảm đi. Chẳng hạn, câu lệnh WITH trong PASCAL đã sử dụng cơ chế nói trên hoặc mode địa chỉ [BX + SI +4] trong ngôn ngữ assembler trên PC. Hệ thống cần phân phối hay giải phóng bộ nhớ đối với chương trình người sử dụng : đơn vị cung cấp hay giải phóng bộ nhớ thường là trang (page) hoặc một đơn vị bộ nhớ nào đó được hệ thống quy định (ví dụ, trong MS-DOS đơn vị đó là 1 đoạn –paragraph). Trang đó có độ dài 2 KB, 4 KB v.v song phổ biến nhất là 4KB. Địa chỉ của trang phù hợp với độ dài của trang theo nghĩa địa chỉ chia hết cho độ dài. Phân phối bộ nhớ cho chương trình còn được phân biệt là phân phối tĩnh hay phân phối động : liên quan đến thời điểm phân phối bộ nhớ là trước (khi tải) hay trong thời gian thực hiện chương trình. Việc phân phối tĩnh hay động được thực hiện đối với cả chương trình lẫn dữ liệu. Truy nhập tới bộ nhớ cũng phân biệt là truy nhập tuần tự hay truy nhập trực tiếp. Truy nhập tuần tự theo các địa chỉ kế tiếp nhau tương ứng với địa chỉ tương đối (ví dụ, truy nhập tới các phần tử của mảng là tuần tự bắt đầu từ phần tử đầu tiên), còn truy nhập trực tiếp tương ứng với địa chỉ tuyệt đối. 1.2. Quản lý phân phối bộ nhớ. Vấn đề bảo vệ bộ nhớ Bài toán cơ bản của điều phối bộ nhớ là : -Phân phối các vùng nhớ cho chương trình và dữ liệu để có thể thực hiện được một cách chính quy, không ảnh hưởng đến các chương trình khác đang tồn tại trong bộ nhớ ; -Bảo vệ chương trình và dữ liệu không bị xóa hoặc chồng chéo bởi những chương trình khác ; -Sử dụng bộ nhớ hiệu quả nhất có thể được. Như vậy, khi điều phối bộ nhớ, đòi hỏi thỏa mãn hai yêu cầu : phân rã được không gian địa chỉ và chia xẻ bộ nhớ. Để đảm bảo được các chức năng cơ bản trên, chương trình điều khiển bộ nhớ phải giải quyết một số nội dung sau đây : Phân rã không gian địa chỉ để tránh chồng chéo, xâm phạm lẫn nhau giữa các chương trình. Cũng giống như trong chương trình PASCAL, các biến local (cục bộ) và global (toàn bộ) dù giống nhau về tên nhưng lại được phân phối các vùng địa chỉ hoàn toàn khác nhau, khi xem xét tình trạng bộ nhớ đang có một số chương trình người dùng, cần phân rã các địa chỉ để không chồng chéo. Để làm được điều đó có thể đưa ra một số chiến lược. Một chiến lược điển hình dùng trong một số hệ điều hành là phân lớp cho các vùng bộ nhớ và gắn lớp bộ nhớ cho mỗi chương trình. Một miền bộ nhớ chỉ có thể phân phối cho một số lớp chương trình, cũng như vậy, một chương trình có thể được phân phối vào một số lớp bộ nhớ nào đó. Đối với mỗi trang, có hai trạng thái áp dụng : đã được phân phối hay còn rỗi. Ví dụ, với các hệ đơn chương trình, như MS-DOS trên máy tính PC, quản lý bộ nhớ đơn giản: sử dụng con trỏ để xác định cận của các vùng bộ nhớ còn rỗi. Tuy nhiên, cũng với máy tính PC với các bộ vi xử lý từ 386 trở đi, cho phép chạy được trong chế độ đa chương trình. Người ta đã phân chia các mức bộ nhớ và các mức chương trình và đã tính đến quyền thâm nhập địa chỉ và cung cấp bộ nhớ : Chỉ khi mức của chương 40
41. trình cho phép thâm nhập đến một vùng bộ nhớ theo quyền hạn thì mới cập nhật được. Chia xẻ bộ nhớ liên quan đến việc dùng chung các phần bộ nhớ mà không ảnh hưởng đến nhau. Trong chế độ đa chương trình, một số chương trình người dùng, có thể cùng hướng đến một chương trình hay dữ liệu chung nào đó. Để dùng chung được, các môdun chương trình có thể có chế độ chạy nhiều lần và các chương trình người dùng có thể gọi chương trình nói trên theo yêu cầu của mình độc lập với các chương trình của người sử dụng khác thâm nhập vào chương trình nói trên. Chú ý rằng, để một môdun chương trình được nhiều người dùng chung thì một điều kiện dễ nhận biết là trong khi môdun đó chạy, không gây ra sự biến đổi nội dung các lệnh thuộc môdun đó. Trong phân phối bộ nhớ cho chương trình, cần chú ý tới hai cách thức là : phân phối liên tục và phân phối rời rạc. Tùy thuộc vào hệ điều hành và chế độ hoạt động của nó mà phân phối bộ nhớ có thể tiến hành theo một trong hai yêu cầu : phân phối liên tục và phân phối rời rạc. Phân phối liên tục là một chương trình sẽ chiếm một vùng nhớ liên tục ; nội dung từ đầu chương trình đến cuối chương trình nằm trọn trong vùng nhớ đó và không cho phép chương trình khác sử dụng vùng nhớ chèn giữa vùng nhớ dành cho chương trình. Phân phối liên tục làm đơn giản việc cung cấp bộ nhớ cho chương trình cũng như việc quản lý bộ nhớ. Phân phối rời rạc là một chương trình có thể được phân chia thành một số đoạn, các đoạn này nằm ở các vùng nhớ rời rạc nhau, giữa các vùng nhớ này có thể có các vùng nhớ được phân phối cho các chương trình khác. Phân phối rời rạc sẽ làm cho bài toán quản lý và phân phối bộ nhớ phức tạp hơn. Phân phối một vùng nhớ cho chương trình được thực hiện theo một trong hai cách thức : chọn cái đầu tiên và chọn cái tốt nhất. Sự khác nhau của hai cách thức đó được giải thích như sau. Thông thường, tại một thời điểm bất kỳ bộ nhớ trong có một số vùng bộ nhớ rỗi rời rạc nhau do việc giải phóng các chương trình nào đó trong bộ nhớ. Các vùng nhớ này có kích thước khác nhau được quản lý trong một danh sách có thứ tự nào đó. Giả sử nảy sinh nhu cầu cần phân phối một dung lượng n đơn vị bộ nhớ (trang, paragraph ) cho việc thực hiện một chương trình nào đó. Theo cách thức « chọn cái đầu tiên » thì vùng nhớ rỗi đầu tiên trong danh sách có dung lượng lớn hơn hoặc bằng n đơn vị nhớ sẽ được sử dụng để phân phối. Theo cách thức « chọn cái tốt nhất » thì vùng nhớ rỗi có dung lượng lớn hơn hay bằng n đơn vị nhớ mà độ dư thừa ít nhất sẽ được sử dụng để phân phối cho nhu cầu nói trên. 2. Điều khiển bộ nhớ liên tục theo đa bài toán Mục tiêu: Nắm được các phương pháp điều khiển bộ nhớ liên tục. 2.1. Chiến lược giới hạn tĩnh (cận cố định) Một trong những phương pháp điển hình phân phối bộ nhớ liên tục là chiến lược giới hạn tĩnh còn gọi là chiến lược phân chương (tương ứng với chế độ MFT của hệ điều hành). Bộ nhớ được chia thành các chương: gán tên chương, 41
42. địa chỉ, dung lượng trong quá trình khởi tạo hệ điều hành. Hình 3.4 cho một hình ảnh phân chương bộ nhớ và việc phân phối bộ nhớ cho một số chương trình. 184K P4(72K) 112K P3(72K) 72K P2(40K) 32K P1(40K) 0K P0(32K) Địa chỉ Chương bộ nhớ Hình 3.1 Bộ nhớ được phân chương Đối với ví dụ theo hình vẽ 3.1, bộ nhớ được phân ra thành 5 chương: P0 (32K), P1 (40K), P2 (40K), P3 (72K), P4 (72K). Chương P0 được dành cho nhân, mỗi chương còn lại đã có một chương trình được tải (load). Kích cỡ (dung lượng) trung bình của mỗi chương phụ thuộc vào dung lượng của bộ nhớ và số lượng chương. Các chương trình được gán số hiệu để chỉ có thể tải vào những chương trình nhất định. Nảy sinh trường hợp có thể có những chương rỗi mà không tải được chương trình: lớp gắn với nó bị bận hoặc độ rộng của chương không đủ để tải. Lúc đó hoặc hệ thống hoặc thao tác viên thực hiện việc thay đổi lớp gắn cho chương trình hoặc thay đổi số lượng chương, kích cỡ chương song phổ biến là thao tác viên dùng lệnh để thực hiện công việc đó. Tuy điều đó xem ra có vẻ thủ công song tránh được sự phức tạp cho chương trình điều khiển. Để quản lý bộ nhớ trong trường hợp này, sử dụng bảng mô tả chương (partition description table: PDT), có dạng: Số hiệu chương Địa chỉ Độ dài Tình trạng 0 0K 32K Đã load 1 32K 40K Đã load 2 72K 40K Đã load 3 112K 72K Đã load 4 184K 72K Đã load Đối với một bài toán, nó được gắn với một vài chương bộ nhớ, chiến lược phân phối bộ nhớ cho nó có thể được kể làm hai hướng: phân phối nhanh nhất (gặp chương được gắn, đủ độ rộng đầu tiên), phân phối tối ưu (chọn chương với vùng nhớ dư thừa là ít nhất). Trở lại vấn đề vướng mắc khi phân phối bộ nhớ: -Không có chương nào đủ để phân phối cho chương trình; 42
43. -Mọi chương đã được tải; -Một số chương rỗi, mỗi chương rỗi không đủ chứa bài toán song nối vài chương rỗi tạo ra một vùng nhớ đủ để tải bài toán. Việc phân phối bộ nhớ cho bài toán (quá trình) được coi như gắn với mỗi chương có 1 dòng xếp hàng các bài toán cần được phân phối bộ nhớ đối với nó. Mỗi bài toán lại có thể gắn với một vài chương, có sự chung nhau giữa một số dòng xếp hàng. Việc phân phối bộ nhớ cho một bài toán liên quan tới việc thao tác đối với các dòng xếp hàng nói trên. Mối liên kết giữa chương và lớp bài toán không phải là luôn chặt chẽ. Như trên đã thấy, tồn tại một số cách thức thay đổi mối liên kết nói trên (hoặc do chương trình hệ thống hoặc do thao tác viên v.v ). 2.2 Chiến lược giới hạn động (cận thay đổi) Như trên đã thấy, chế độ phân phối cận cố định (phân phối tĩnh) nảy sinh một số vấn đề trong việc sử dụng tối ưu bộ nhớ, với phương án khắc phục đưa vào lệnh của thao tác viên. Trong cách thức phân phối liên tục bộ nhớ, chế độ giới hạn thay đổi được áp dụng. Trong chế độ này (tương ứng với chế độ MVT của hệ điều hành), bộ nhớ không chia thành các chương giống như ở chế độ giới hạn cố định. Các chương trình nạp liên tục vào bộ nhớ cho đến khi còn nạp được. Một ví dụ về hình ảnh của bộ nhớ trong được cho trong hình 3.2. Trong quá trình làm việc, các chương trình được thực hiện và giải phóng, các vùng bộ nhớ giải phóng đó có thể liên tục hoặc rời rạc. Sử dụng vùng bộ nhớ đó ra làm sao. Một số tình huống nảy sinh (hình 3.2). Trên hình vẽ thứ 6, chương trình 4 (Prg 4) được giải phóng đầu tiên. Ngay trước chương trình 4, một vùng nhớ rỗi với dung lượng 20K. Khi giải phóng chương trình 4, có một vùng rỗi liên tục với dung lượng 102K. Chương trình 8 với độ dài 52K được tải vào trong bộ nhớ trong và sau đó chương trình 6 được giải phóng. Hiện tại, trên dòng đợi, đến lượt chương trình Pr9 có độ dài 80K. Mỗi vùng rỗi riêng rẽ trong bộ nhớ không thể chứa nối chương trình 9, trong khi đó dung tích rỗi tổng cộng là 88K. Hệ thống cần nhập hai vùng nhớ rỗi trên để nạp được chương trình Pr9. 24K Prg.2 Prg.2 Prg.2 82K Prg.4 Prg.4 Prg.4 42K Rỗi 30K Rỗi Rỗi 50K Prg.3 92K 62K Prg.5 26K Prg.1 Prg.1 32K Nhân Nhân 24K Prg.2 Prg.2 Prg.2 82K Prg.4 Prg.4 82K Prg.4 43
44. 30K Rỗi 20K Rỗi 62K Prg.5 118K Rỗi 60K Prg.7 26K Rỗi 38K Prg.6 32K Nhân Nhân Nhân Hình 3.2. Các hình trạng bộ nhớ với cận thay đổi Điều khiển bộ nhớ theo cận thay đổi sử dụng linh hoạt tối ưu bộ nhớ, tránh được một số hạn chế so với cận cố định (cho phép độ dài của môdun chương trình lớn) và miền nhớ rỗi được sử dụng linh hoạt. Tuy vậy, công việc phân phối bộ nhớ là phức tạp. -Quản lý bộ nhớ luôn thay đổi -Định vị lại bộ nhớ cho các chương trình. Khi chương trình đang hoạt động, nó đang ở trạng thái trung gian, nếu không có những cơ chế thích hợp thì việc định vị lại sẽ ảnh hưởng đến sự thực hiện chương trình. Điều này cũng liên quan đến vấn đề địa chỉ hóa trong chương trình: sử dụng địa chỉ cở sở không tường minh. Chỉ khi có thể quy chiếu trên địa chỉ không tường minh mới có thể giải quyết được bài toán định vị lại như trên. Mặc khác, không phải thời điểm nào cũng cho phép định vị lại. Chương trình đang đợi kết quả của công việc vào/ra thì việc định vị lại gặp trở ngại lớn trong vấn đề liên kết kết quả công việc vào/ra với chương trình. Vấn đề định vị lại có ý nghĩa không chỉ trong phân phối bộ nhớ liên tục mà cả trong phân phối bộ nhớ gián đoạn. Việc sử dụng địa chỉ tương đối là một hình thức phù hợp với việc định vị lại. Có một số cách thức liên quan đến định vị lại: định vị tĩnh và định vị động. 2.3. Cách thức Overlay và swapping a) Cách thức OVERLAY Trong các trường hợp điều khiển bộ nhớ nói trên, để khắc phục hiện tượng thiếu bộ nhớ khi phân phối liên tục, một số hệ thống cho phép chương trình hoạt động theo chế độ OVERLAY. Chế độ OVERLAY cho phép tổ chức chương trình thành các đơn vị chương trình và đảm bảo các điều kiện sau: Phân phối bộ nhớ cho chương trình trong một miền liên tục, Môdun tải bao gồm một số đơn vị chương trình (segment chương trình) mà các segment chương trình được tải đồng thời (phân phối liên tục). Một số môdun tải có thể được tải vào cùng 1 vùng bộ nhớ. Các môdun tải như vậy được tập hợp trong các File trên đĩa. Trong tập hợp các môdun chương trình sẽ nảy sinh quan hệ độc lập/phụ thuộc: sự có mặt của một nhóm môdun trong bộ nhớ không đòi hỏi/có đòi hỏi sự có mặt của một nhóm môdun khác. 44
45. A 30K 12 B 24K C 12 D 12 E 12 G 12 H I J 6 6 Hình 3.3 Cấu trúc chương trình OVERLAY Trong các môdun nói trên, có một môdun luôn tồn tại trong quá trình chương trình thực hiện: đó là chương trình chính, mọi môdun chương trình đều phụ thuộc vào nó sẽ được tổ chức dưới dạng hình cây. Hình trên đây (hình 3.3) cho một ví dụ cấu trúc một chương trình: bộ nhớ đòi hỏi của môdun A:30KB; B:24KB, C:12KB, D, E, G, H: 12KB; I, J: 6KB. Theo cấu trúc đó: A (môdun chính) sử dụng hai môdun B và C. B và C độc lập nhau: chúng có thể được lưu trữ trên cùng một vùng nhớ. B sử dụng hai môdun độc lập là D và E; C sử dụng hai môdun độc lập là G và H. H sử dụng hai môdun độc lập là I và J. Như vậy, cây chương trình có gốc B cần 36KB; cây chương trình có gốc C cần 30KB. Vậy chương trình cần vùng nhớ liên tục là 30KB +36KB = 66KB. Trong khi đó nếu không sử dụng chế độ overlay, chương trình nói trên cần vùng nhớ liên tục là 30KB +24KB+5*12KB+2*6KB=126KB. Ví dụ, trong các ngôn ngữ lập trình nói chung cho phép chế độ này. Chẳng hạn, khai báo OVERLAY trong PASCAL, FORTRAN v.v Cụ thể, trong TP3.0, các môdun overlay được cho vào File cùng phần tên với file chương trình nhưng phần mở rộng là 001, 002 v.v ;Một số phần mềm, có file đi kèm có phần mở rộng OVL, chứa các môdun cùng mức khi tải vào bộ nhớ trong. b) Cách thức swapping Swapping là cách thức hệ thống thực hiện việc chuyển giao nội dung một số phần bộ nhớ ra đĩa từ để giải phóng bộ nhớ cho một yêu cầu phân phối hiện tại. Phần nội dung bộ nhớ được chuyển ra ngoài chứa cả nội dung các chương trình đang tồn tại trong bộ nhớ; sau đó khi chương trình nói trên được chọn thực hiện, thì phần bộ nhớ được đưa từ đĩa từ vào bộ nhớ trong. Swapping áp dụng chủ yếu cho điều phối bộ nhớ liên tục song trong một số trường hợp cũng được các hệ điều hành hoạt động điều phối bộ nhớ gián đoạn sử dụng. Về hình thức, có thể coi swapping là một biến thể của overlay: Trong overlay, môdun chương trình chính thuộc chương trình người dùng còn trong swapping, môdun chương trình chính thuộc về hệ điều hành, còn môdun overlay là các chương trình người dùng, trong một số trường hợp thì thậm chí đấy là các bộ phận các chương trình người dùng. Trong các hệ điều hành dùng cách thức swapping, tồn tại một môdun hệ thống tên là swapper có chức năng như sau: 45
46. Chọn quá trình (chương trình người dùng) để đưa ra đĩa từ (swap out) Chọn quá trình để đưa trở lại từ đĩa vào bộ nhớ trong (swap in) Định vị và quản lý không gian swap (trong bộ nhớ trong cũng như trên đĩa từ). Swap out Swapper định hướng chọn quá trình được đưa ra đĩa từ (quá trình bị swap out) là quá trình đang bị đình chỉ mà đang chiếm một vùng nhớ đủ lớn để có thể phân phối bộ nhớ cho quá trình đang được nạp vào bộ nhớ trong. Trong những quá trình thóa mãn điều kiện trên, swapper sẽ chọn lựa quá trình có độ ưu tiên thấp nhất, chờ đợi một sự kiện xảy ra chậm và quá trình này thường xuyên bị đình chỉ khi thống kê trong một khoảng thời gian dài. Một số điều cần chú ý khi chọn quá trình bị swap out là tính đến là thời gian quá trình đó đã tải (hoặc nhận) vào bộ nhớ trong, tính chất thực hiện trong bộ nhớ trong của quá trình đó v.v Cần tránh trường hợp một quá trình vừa bị swap out xong thì lại cần gửi nó vào lại bộ nhớ trong (swap in). Swap in Swapper chọn quá trình đang ở bộ nhớ ngoài (do swap out) nhận lại vào bộ nhớ trong phụ thuộc vào một số thông số: thời gian quá trình đã ở bộ nhớ ngoài, độ ưu tiên của quá trình v.v Mục tiêu của công việc chọn lựa này là đảm bảo sao cho thời gian dành cho swap out và swap in là ít nhất có thể được. Định vị và quản lý không gian swap Các quá trình trong trạng thái swap out được hệ điều hành lưu trữ dưới dạng thực hiện được cùng với dữ liệu có liên quan lên một File trên đĩa được gọi là File swap. Không những thế, File này còn chứa các thuộc tính của quá trình bị swap, chẳng hạn như độ ưu tiên của quá trình và yêu cầu bộ nhớ đối với quá trình đó. Trong một số trường hợp File như trên còn được gọi là ảnh của quá trình. Do quá trình khi thực hiện làm thay đổi stack và dữ liệu cho nên ảnh- dạng đang thực hiện của quá trình khác với ảnh lưu trữ thông thường khi chưa được tải. Nói chung, cũng giống như việc bảo vệ trạng thái quá trình khi chuyển điều khiển, khi swap out, vùng bảo vệ tương ứng với quá trình đó cũng được lưu trên ảnh của nó. Tồn tại hai lựa chọn cơ sở đối với việc định vị File swap: - 1 file swap cho toàn bộ hệ thống - 1 số file swap chuyên dụng theo quá trình. Lựa chọn chỉ 1 file swap cho toàn bộ hệ thống: Một file rất lớn được khởi tạo, thường xảy ra tại thời điểm khởi tạo hệ thống, chứa mọi ảnh swap out của mọi quá trình. Nói chung, File swap chung đó đặt trên “bộ nhớ ngoài” tốc độ cao; File đó thường có địa chỉ và độ rộng tĩnh. Một điều quan trọng đối với sự lựa chọn này là kích cỡ của file swap chung đó. Nếu kích cỡ của nó quá lớn thì vùng trên “bộ nhớ ngoài” dành cho các mục đích khác sẽ bé, ảnh hưởng đến tốc độ hoạt động chung của hệ thống. Ngược lại, nếu kích cỡ của file nhỏ thì có thể xảy ra tình huống sai sót khi swap out. Lựa chọn một số file swap chuyên dụng: mỗi một quá trình bị swap out sẽ tương ứng với một file trên bộ nhớ ngoài (nhiều file ảnh). File swap (ảnh của quá 46
47. trình) được khởi tạo hoặc dạng tĩnh (ngay khi quá trình được nạp vào bộ nhớ trong) hoặc động (khi cần swap out mới tạo file). Việc swap out và swap in đối với quá trình ảnh hưởng đến thời gian thực hiện quá trình và liên quan đến tốc độ vào ra với bộ nhớ ngoài. 2.4. Các phương thức phân phối vùng nhớ (first fit, best fit, worst fit) Tập hợp các lỗ trống được tìm thấy để xác định lỗ nào là tốt nhất để cấp phát. Các chiến lược first-fit, best-fit, worst-fit là những chiến lược phổ biến nhất được dùng để chọn một lỗ trống từ tập hợp các lỗ trống. •First-fit: cấp phát lỗ trống đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu tập hợp các lỗ trống hay tại điểm kết thúc của tìm kiếm first-fit trước đó. Chúng ta dừng tìm kiếm ngay khi chúng ta tìm thấy một lỗ trống đủ lớn. •Best-fit: cấp phát lỗ trống nhỏ nhất đủ lớn. Chúng ta phải tìm toàn bộ danh sách, trừ khi danh sách được xếp thứ tự theo kích thước. Chiến lược này tạo ra lỗ trống nhỏ nhất còn thừa lại. •Worst-fit: cấp phát lỗ trống lớn nhất. Chúng ta phải tìm toàn danh sách trừ khi nó được xếp theo thứ tự kích thước. Chiến lược này tạo ra lỗ trống còn lại lớn nhất mà có thể có ích hơn lỗ trống nhỏ từ tiếp cận best-fit. Các mô phỏng hiển thị rằng cả first-fit và best-fit là tốt hơn worst-fit về việc giảm thời gian và sử dụng lưu trữ. Giữa first-fit và best-fit không thể xác định rõ chiến lược nào tốt hơn về sử dụng lưu trữ, nhưng first-fit có tốc độ nhanh hơn. Tuy nhiên, các giải thuật này gặp phải vấn đề phân mãnh ngoài (external fragmentation). Khi các quá trình được nạp và được xoá khỏi bộ nhớ, không gian bộ nhớ trống bị phân rã thành những mãnh nhỏ. Phân mãnh ngoài tồn tại khi tổng không gian bộ nhớ đủ để thoả mãn một yêu cầu, nhưng nó không liên tục; vùng lưu trữ bị phân mãnh thành một số lượng lớn các lỗ nhỏ. Vấn đề phân mãnh này có thể rất lớn. Trong trường hợp xấu nhất, chúng có thể có một khối bộ nhớ trống nằm giữa mỗi hai quá trình. Nếu tất cả bộ nhớ này nằm trong một khối trống lớn, chúng ta có thể chạy nhiều quá trình hơn. 3. Điều khiển bộ nhớ gián đoạn Mục tiêu: nắm được phương thức tối ưu hóa việc phân phối bộ nhớ, tránh lãng phí và chia sẻ tài nguyên bộ nhớ 3.1. Tổ chức gián đoạn Như đã biết, với hệ điều hành hoạt động theo chế độ đa người dùng, tại cùng một thời điểm có nhiều người cùng làm việc với máy: tồn tại nhiều chương trình đang có mặt trong bộ nhớ trong để làm việc và nói chung thì số chương trình này không giảm đi như đã xét theo chế độ mẻ. Vì bộ nhớ trong là rất hạn chế, có nhiều người dùng (do vậy có nhiều chương trình người dùng đang ở trong bộ nhớ trong) và chương trình người dùng có độ dài không thể giới hạn trước và vì vậy, không phải toàn bộ chương trình người dùng nào cũng phải trong bộ nhớ trong: một bộ phận nằm ở bộ nhớ trong và bộ phận còn lại nằm ở bộ nhớ ngoài. Để liên kết các bộ phận nói trên, không thể sử dụng địa chỉ tương đối như chế độ overlay trong phân phối liên tục mà các bộ phận này phải thống nhất với nhau về hệ thống địa chỉ, các lệnh quy chiếu đến các địa chỉ thống nhất đó. Như vậy, với một chương 47
48. trình người dùng, các địa chỉ thuộc vào không gian địa chỉ thực và không gian địa chỉ ảo. Bộ nhớ trong được địa chỉ hóa (bằng số, bắt đầu là địa chỉ 0) và CPU trực tiếp thao tác lấy và ghi bộ nhớ đối với những địa chỉ thuộc bộ nhớ trong một tập hợp nào đó; tập hợp các địa chỉ nói trên được gọi là không gian địa chỉ thực. Lực lượng của không gian địa chỉ thực luôn được xác định trước và gắn với máy. Trong chương trình (không phải viết trên ngôn ngữ máy), người lập trình hướng đến bộ nhớ qua tập hợp các tên logic, cho phép các tên logic là kí hiệu chứ không hoàn toàn là số địa chỉ thực. Một cách tổng quát, địa chỉ được biểu thị bằng tên, các tên nói trên tạo ra một không gian tên. Một chương trình được viết như một thể thống nhất có mối liên hệ giữa các tên nói trên. Tập hợp các tên sử dụng chưa được xác định trước. Tập hợp các tên-địa chỉ có lực lượng vượt quá địa chỉ có thực trong bộ nhớ. Với nhiều người dùng, một “tên” không phải gắn với một “định vị cố định” nào cả. Mặt khác, việc dùng tên của các người lập trình khác nhau là độc lập nhau, vì thế hệ thống cho phép không gian tên được phép dùng là “vô hạn”. Hệ thống chương trình cần phải định vị được “bộ nhớ” đối với mỗi tên trong chương trình: cần ánh xạ không gian tên vào địa chỉ vật lý và trong ánh xạ đó nảy sinh khái niệm không gian địa chỉ ảo. Ánh xạ từ không gian tên tới bộ nhớ vật lý được chia làm hai bước (hình3.9). Bước 1: do chương trình dịch đảm nhận. Việc xác định địa chỉ ảo không phải do chương trình người dùng hoặc hệ thống phần cứng mà do chương trình dịch trong hệ thống: địa chỉ ảo có thể là ký hiệu, số hoặc chỉ dẫn số. Tập hợp các địa chỉ ảo (do chương trình dịch trong hệ thống thiết lập) được gọi là không gian địa chỉ ảo (ngắn gọn là không gian địa chỉ). Bước 2: do hệ điều hành (cụ thể là điều khiển bộ nhớ) ánh xạ địa chỉ ảo vào bộ nhớ vật lý. Tại giai đoạn này xảy ra quá trình tải bộ phận của chương trình vào bộ nhớ trong tại một vùng nhớ còn rỗi. Chương trình được tải trong bộ nhớ trong theo tập hợp các vùng nhớ rời rạc nhau đang dành cho nó. Trong việc kiến thiết tên nảy sinh các trường hợp: Đồng nhất không gian địa chỉ với bộ nhớ vật lý: ánh xạ chỉ cần chương trình hệ thống khi sinh mã máy chương trình, hệ điều hành chỉ đảm bảo phân phối liên tục cố định bộ nhớ. Assembler với tải và sử dụng trực tiếp là ví dụ cho trường hợp này. Tên Không gian tên logic Do chương trình dịch Địa chỉ ảo Không gian địa chỉ ảo 48