Bài giảng Hệ điều hành - Chương 1: Tổng quan về hệ điều hành - Huỳnh Triệu Vỹ

Chương I:TỔNG QUAN VỀ HĐH 
ThS. Huỳnh Triệu Vỹ 
1 
NỘI DUNG : 
1.1	 Lịch sử phát triển của HĐH 
1.2	 Khái niệm về HĐH 
1.3	 Phân Loại HĐH 
1.4	 Giới thiệu về cấu trúc của HĐH 
1.5	 Giới thiệu một số HĐH phổ biến hiện nay 
2 
1.1 LỊCH SỬ PHÁT TRIỂN CỦA HĐH 
1. Thế hệ 1(1945-1955): 
Năm 46 máy tính dùng ống chân không ra đời (do Howard Aiken ở ĐH Havard và John von Neumann ở ĐH Princeton chế tạo ) 
Máy có kích thước rất lớn , nặng , tiêu thụ điện lớn . 
Vận hành máy tính cần 1 nhóm người : Thiết kế , xây dựng chương trình , thao tác , quản lý , 
Chưa có khái niệm về ngôn ngữ lập trình và HĐH 
Đầ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 
Máy ENIAC dùng các ống chân không 
3 
1.1 LỊCH SỬ PHÁT TRIỂN CỦA HĐH(tt ) 
2. Thế hệ 2(1955-1965) 
Máy tính dùng transistor ra đời 
Bộ phận sử dụng máy tính được phân chia rõ ràng : người thiết kế , người xây dựng , người lập trình , người vận hành , 
Ngôn ngữ lập trình ra đời (Assembly, Foxtran ), chương trình được viết trên phiếu đục lỗ 
Hệ thống xử lý theo lô ra đời , hoạt động dưới sự điều khiển của 1 chương trình đặc biệt 
Bardeen, Brattain và Shockley phát minh ra transistor và đoạt giải Nobel Vật lý (1956) 
4 
1.1 LỊCH SỬ PHÁT TRIỂN CỦA HĐH(tt ) 
Chip IC do Jack Kilby sáng chế năm 58 
Jack Kilby được nhận giải 
 Nobel Vật lý năm 2000 
Robert Noyce (trái) và Gordon Moore 
5 
1.1 LỊCH SỬ PHÁT TRIỂN CỦA HĐH(tt ) 
3. Thế hệ 3(1965-1980) 
Hãng IBM cho ra máy IBM 360 sử dụng mạch IC 
Máy tính được sử dụng rộng rãi 
Thiết bị ngoại vi dùng cho máy tính xuất hiện ngày càng nhiều 
Các thao tác điều khiển máy tính ngày càng phức tạp 
HĐH ra đời nhằm điều phối , kiểm soát hoạt động của hệ thống và giải quyết các yêu cầu tranh chấp thiết bị 
6 
1.1 LỊCH SỬ PHÁT TRIỂN CỦA HĐH(tt ) 
4. Thế hệ 4(1980->) 
Máy tính cá nhân ra đời ( đặc biệt , năm 80 chiếc IBM-PC đầu tiên dùng vi xử lý 8bit 8085 của Intel ra đời ) 
Sự ra đời và phát triển nhiều HĐH gắn liền với sự phát triển của phần cứng máy tính 
Cho đến nay có các dòng HĐH được sử dụng rộng rãi và luôn phát triển : 
Dòng Windows 
Dòng Linux 
7 
1.2 KHÁI NIỆM VỀ HĐH 
Hệ điều hành là một chương trình hay một hệ chương trình phần mềm máy tính , hoạt động ở lớp trung gian giữa người sử dụng và phần cứng máy tính 
Mục tiêu của HĐH là cung cấp môi trường để người sử dụng : 
Thực thi dễ dàng các chương trình 
Sử dụng máy tính trở nên dễ dàng , khai thác phần cứng máy tính một cách hiệu quả 
8 
1.2 KHÁI NIỆM VỀ HĐH(tt ) 
HĐH là một bộ phận quan trọng của hệ thống máy tính . Một hệ thống máy tính bao gồm 4 phần : 
Phần cứng : CPU; Bộ nhớ ; Các thiết bị xuất/nhập 
Các chương trình ứng dụng 
Hệ điều hành 
Đối tượng sử dụng : Người , thiết bị hoặc máy tính khác 
9 
4 Thành phần của hệ thống máy tính 
Người sử 
 dụng 1 
Người sử 
 dụng 2 
Người sử 
 dụng 3 
Người sử 
 dụng n 
Các chương trình ứng dụng 
Hệ điều hành 
Phần cứng 
Trình biên dịch 
Hợp ngữ 
Soạn thảo văn bản 
CSDL 
10 
1.3 PHÂN LOẠI HĐH 
Hệ thống xử lý theo lô đơn giản 
Hệ thống xử lý theo lô đa chương 
Hệ thống chia sẻ thời gian 
Hệ thống song song 
Hệ thống phân tán 
Hệ thống xử lý thời gian thực 
V.v. 
11 
HỆ THỐNG XỬ LÝ THEO LÔ ĐƠN GiẢN 
Các tác vụ được đưa vào hàng đợt 
Thực hiện các tác vụ lần lượt theo những chỉ thị đã được xác định trước 
Tác vụ tiếp theo tự động được thực hiện khi tác vụ trước kết thúc 1 cách tự động 
Có bộ giám sát thường trực để giám sát việc thực hiện của các tác vụ trong hệ thống 
	Processor rơi vào trạng thái chờ khi hệ thống truy xuất thiết bị vào ra 
12 
HỆ THỐNG XỬ LÝ THEO LÔ ĐA CHƯƠNG 
Thực hiện được nhiều tác vụ đồng thời 
HĐH nạp 1 phần code và data của tác vụ vào bộ nhớ 
Khi có tác vụ đang sử dụng Processor thực hiện truy xuất thiết bị vào ra thì Processor sẽ được chuyển thực hiện tác vụ khác 
Cần có cơ chế lập lịch cho Processor 
13 
HỆ THỐNG CHIA SẺ THỜI GIAN 
Các tác vụ, tiến trình được sử dụng Processor luân phiên nhau theo lịch phân chia thời gian sử dụng Processor đã được lập (t rất nhỏ) 
Cung cấp cho mỗi người sử dụng 1 phần nhỏ trong máy tính chia sẻ ->Người sử dụng có thể yêu cầu máy tính thực hiện đồng thời nhiều công việc 
Có cơ chế quản trị và bảo vệ bộ nhớ, sử dụng bộ nhớ ảo 
14 
HỆ THỐNG SONG SONG 
Có nhiều Processor trong cùng một hệ thống máy tính 
Các Processor cùng chia sẻ đường truyền dữ liệu, đồng hồ xung, bộ nhớ và các thiết bị ngoại vi 
Có 2 loại HĐH đa Processor: 
Đa xử lý đối xứng (Symmetric multiprocessing-SMP) 
Đa xử lý bất đối xứng (Asymmetric multiprocessing-ASMP) 
15 
HỆ THỐNG SONG SONG(tt) 
Đa xử lý đối xứng: 
 Mỗi Processor chạy độc lập trên một bản sao HĐH như nhau 
Cho phép nhiều tiến trình chạy đồng thời trên một hệ thống 
Đa xử lý bất đối xứng: 
Mỗi Processor được giao một nhiệm vụ riêng biệt 
Có một hoặc 2 Processor chủ làm nhiệm vụ lập lịch, xác định công việc cho các Processor thành viên 
16 
HỆ THỐNG PHÂN TÁN 
Phân tán sự tính toán trên các bộ xử lý vật lý 
Mỗi bộ xử lý có bộ nhớ cục bộ riêng 
Các bộ xử lý thông tin với nhau thông qua các đường truyền thông tốc độ cao 
Có 2 dạng hệ thống: Client/Server và Peer-to-Peer 
17 
HỆ THỐNG XỬ LÝ THỜI GIAN THỰC 
Có khả năng cho kết quả tức thời, chính xác sau mỗi tác vụ 
Tác vụ cần thực hiện không đưa vào hàng đợi mà sử lý tức thời và trả lại ngay kết quả chính xác trong khoảng thời gian bị thúc ép nhanh nhất 
18 
1.4 	CẤU TRÚC CỦA HĐH 
1.4.1 CÁC THÀNH PHẦN CỦA HĐH 
Quản lý tiến trình 
Quản lý bộ nhớ chính 
Quản lý bộ nhớ phụ 
Quản lý xuất/nhập 
Quản lý tập tin 
Thông dịch lệnh 
Bảo vệ hệ thống 
19 
NHIỆM VỤ CỦA THÀNH PHẦN QUẢN LÝ TIẾN TRÌNH 
Tạo lập và hủy bỏ tiến trình 
Tạm dừng và kích hoạt lại tiến trình 
Tạo cơ chế thông tin liên lạc giữa các tiến trình 
Tạo cơ chế đồng bộ hóa giữa các tiến trình 
20 
NHIỆM VỤ CỦA THÀNH PHẦN QuẢN LÝ BỘ NHỚ CHÍNH 
Cấp phát, thu hồi vùng nhớ 
Ghi nhận trạng thái bộ nhớ chính 
Bảo về bộ nhớ 
Quyết định tiến trình nào được nạp vào bộ nhớ 
21 
NHIỆM VỤ CỦA THÀNH PHẦN QUẢN LÝ XUẤT/NHẬP 
Làm cho các thao tác trao đổi thông tin trên các thiết bị nhập/xuất được trong suốt với người sử dụng 
Một hệ thống nhập/xuất bao gồm: 
Hệ thống buffer caching. 
 Bộ giao tiếp điều khiển thiết bị. 
 Bộ điều khiển cho các thiết bị đặc thù. 
22 
NHIỆM VỤ CỦA THÀNH PHẦN QUẢN LÝ BỘ NHỚ PHỤ 
Quản lý không gian trống trên đĩa 
Định vị lưu trữ thông tin trên đĩa 
Lập lịch cho vấn đề ghi/đọc thông tin trên đĩa 
23 
NHIỆM VỤ CỦA THÀNH PHẦN QuẢN LÝ TẬP TIN 
Tạo/xóa tập tin, thư mục 
Bảo vệ tập tin khi có truy xuất đồng thời 
Cung cấp các thao tác xử lý và bảo vệ tập tin, thư mục 
Tạo cơ chế truy xuất tập tin thông qua tên tập tin, 
24 
NHIỆM VỤ CỦA THÀNH PHẦN THÔNG DỊCH LỆNH 
Đóng vai trò giao tiếp giữa HĐH và người sử dụng 
Một số HĐH thành phần này nằm trong nhân của nó , một số HĐH khác thiết kế dưới dạng 1 chương trình đặc biệt 
25 
NHIỆM VỤ CỦA THÀNH PHẦN BẢO VỆ HỆ THỐNG 
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 
26 
1.4.2 CẤU TRÚC CỦA HĐH 
a. HỆ THỐNG ĐƠN KHỐI: 
Là một tập hợp các thủ tục , mỗi thủ tục có thể gọi thực hiện một thủ tục khác bất kỳ lúc nào cần thiết 
MS-DOS là một hệ điều hành có cấu trúc đơn giản , nó cung cấp những chức năng lớn nhất cho hệ thống tối thiểu 
27 
1.4.2 CẤU TRÚC CỦA HĐH(tt ) 
b. HỆ THỐNG PHÂN LỚP: 
Hệ thống được chia thành một số lớp 
Mỗi lớp được xây dựng dựa trên một lớp bên dưới 
Lớp dưới cùng là phần cứng , lớp trên cùng là giao diện với người sử dụng 
28 
Hệ thống phân lớp của UNIX 
Phần cứng 
Hệ điều hành Unix 
Thư viện chuẩn 
Chương trình tiện ích chuẩn 
Người sử dụng 
29 
1.4.2 CẤU TRÚC CỦA HĐH(tt ) 
c. MÁY ẢO (Virtual Machine) 
Là bản sao chính xác các đặc tính phần cứng của máy tính thực . Được cung cấp phần cứng và kernel của HĐH như máy thật 
Tài nguyên máy tính vật lý được chia sẻ để tạo ra các máy ảo 
Mỗi tiến trình được thực hiện trên một máy ảo độc lập 
30 
31 
1.4.2 CẤU TRÚC CỦA HĐH(tt ) 
d. MÔ HÌNH Client/Server: 
Mô hình này các tiến trình được chia thành 2 loại 
Tiến trình Client: Là các tiến trình bên ngoài hay tiến trình của chương trình người sử dụng 
Tiến trình Server: Là các tiến trình của HĐH 
Khi cần thực hiện 1 chức năng của hệ thống tiến trình client gửi yêu cầu đến tiến trình server tương ứng , tiến trình server xử lý và trả về cho client 
32 
CHƯƠNG II:QUẢN LÝ TIẾN TRÌNH 
33 
1. TỔNG QUAN VỀ TiẾN TRÌNH 
34 
1.1 Tiến trình(process )? 
Tiến trình là một chương trình đang được thực thi , được sở hữu 1 con trỏ lệnh , tập các thanh ghi và các biến 
Để hoàn thành tác vụ của mình , một tiến trình có thể cần đến một số tài nguyên như CPU, bộ nhớ chính , các tập tin và thiết bị nhập/xuất . 
35 
1.1 Tiến trình(process)?(tt ) 
Tiến trình bao gồm 3 thành phần : Code, Data, Stack 
Code: Thành phần câu lệnh thực hiện 
Data: Thành phần dữ liệu 
Stack: Thành phần lưu thông tin tạm thời 
Các câu lệnh trong code chỉ dùng data và stack riêng của mình ngoại trừ các vùng dùng chung 
Tiến trình được hệ thống phân biệt bằng số hiệu pid ( proccess indentification ) 
36 
1.2 Các trạng thái của tiến trình 
Trạng thái của tiến trình tại mỗi thời điểm được xác định bởi hoạt động hiện thời của nó : 
New: tiến trình được tạo lập 
Ready: tiến trình đã sẵn sàng , đang chờ cấp CPU 
Running: tiến trình đang được xử lý 
Waiting: tiến trình tạm dừng và chờ vì thiếu tài nguyên hay chờ 1 sự kiện nào đó 
Halt: Tiến trình hoàn tất 
37 
Mô tả chuyển trạng thái của tiến trình 
New 
Ready 
Running 
Halt 
Waiting 
(1) 
(2) 
(3) 
(4) 
(5) 
(6) 
38 
1.2 Các trạng thái của tiến trình(tt ) 
Tại một thời điểm chỉ có 1 tiến trình ở trạng thái Running trên 1 bộ xử lý bất kỳ và có thể có nhiều tiến trình ở trạng thái Ready và Waiting 
39 
1.3 Chế độ xử lý của tiến trình 
Chế độ xử lý được chia thành 2 chế độ nhờ sự hỗ trợ của phần cứng : Đặc quyền và không đặc quyền 
Tiến trình của HĐH cần được bảo vệ khỏi sự xâm phạm của tiến trình khác 
Tiến trình của HĐH hoạt động trong chế độ đặc quyền và của người sử dụng hoạt động trong chế độ không đặc quyền 
40 
1.3 Chế độ xử lý của tiến trình(tt ) 
Tập lệnh của CPU được chia thành 2 tập 
OS 
Hardware 
Shell, editor 
users 
Chế độ không đặc quyền 
Chế độ đặc quyền 
41 
1.4 Các thao tác điều khển tiến trình 
a. Khởi tạo tiến trình 
HĐH gán PID và đưa vào danh sách quản lý của hệ thống 
Cấp phát không gian bộ nhớ 
Khởi tạo các thông tin cần thiết cho khối điều khiển tiến trình : Các PID của p cha ( nếu có ), thông tin trạng thái , độ ưu tiên , ngữ cảnh của processor 
Cung cấp đầy đủ các tài nguyên ( trừ processor) 
Đưa tiến trình vào danh sách P nào đó : ready list, waiting list 
42 
1.4. Các thao tác điều khển tiến trình 
b. Kết thúc tiến trình : HĐH thực hiện các thao tác : 
Thu hồi tài nguyên đã cấp phát cho p 
Loại bỏ tiến trình ra khỏi danh sách quản lý của hệ thống 
Hủy bỏ khối điều khiển p 
43 
1.4. Các thao tác điều khển tiến trình 
c. Thay đổi trạng thái của P, HĐH thực hiện : 
Lưu ngữ cảnh của Processor 
Cập nhật PCB (process control block) của tiến trình sao cho phù hợp với trạng thái của P 
Di chuyển PCB của p đến 1 hàng đợi thích hợp 
Chọn tiến trình khác để cho phép nó thực hiện 
Cập nhật PCB của p vừa thực hiện 
Cập nhật thông tin liên quan đến quản lý bộ nhớ 
Khôi phục lại ngữ cảnh của processor 
44 
1.5 Khối điều khiển tiến trình(process control block -PCB). 
Quản lý mọi hoạt động của tiến trình 
Cấu trúc dữ liệu của khối điều khiển bao gồm : 
Định danh tiến trình 
Trạng thái của tiến trình 
Ngữ cảnh của tiến trình 
Thông tin giao tiếp 
Thông tin thống kê 
45 
status 
pid 
Waiting/waiting list 
CPU-state- rec 
Processor 
Main store 
Resource 
Created recource 
Parent 
Progency 
Priority 
CPU time 
Unit 1 
Unit 2 
RCB 1 
RCB 2 
RCB 1 
RCB 2 
PCB 
PCB 1 
PCB 2 
Ngữ cảnh của ttrình 
Thông tin giao tiếp 
Thông tin thống kê 
Trạng thái ttrình 
Định danh ttrình 
46 
1.6 Tiểu trình 
Thông thường mỗi tiến trình có 1 không gian địa chỉ và 1 dòng xử lý 
Mong muốn có nhiều dòng xử lý cùng chia sẻ 1 không gian địa chỉ và các dòng xử lý hoạt động song song như các tiến trình độc lập 
Xuất hiện HĐH có cơ chế thực thi mới gọi là tiểu trình 
Như vậy , tiểu trình là : 
1 đơn vị xử lý cơ bản 
Sở hữu 1 con trỏ lệnh , tập các thanh ghi , 1 vùng nhớ stack riêng 
Có các trạng thái như tiến trình thật . 
47 
2. TÀI NGUYÊN GĂNG VÀ ĐOẠN GĂNG 
48 
2.1 Tài nguyên găng(Critical Resource) 
Tài nguyên găng ? 
Những tài nguyên được HĐH chia sẻ cho nhiều tiến trình hoạt động đồng thời dùng chung mà có nguy cơ tranh chấp giữa các tiến trình này khi sử dụng chúng 
Tài nguyên găng có thể là tài nguyên phần cứng hoặc phần mềm , có thể là tài nguyên phân chia được hoặc không phân chia được 
49 
2.1 Tài nguyên găng(Critical Resource) 
Ví dụ : bài toán rút tiền ngân hàng từ tài khoản dùng chung 
If ( tài khoản – tiền rút >=0) 
	 tài khoản := tài khoản – tiền rút 
Else 
	 Thông báo lỗi 
endif 
50 
2.2 Đoạn găng(Critical Section) 
Các đoạn code trong các chương trình dùng để truy cập đến tài nguyên găng được gọi là đoạn găng 
Để hạn chế lỗi có thể xảy ra do sử dụng tài nguyên găng , tại 1 thời điểm HĐH chỉ cho 1 tiến trình nằm trong đoạn găng 
HĐH có cơ chế điều độ tiến trình qua đoạn găng 
51 
2.3 Yêu cầu của công tác điều độ tiến trình qua đoạn găng 
Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng , các tiến trình khác có nhu cầu vào đoạn găng phải chờ 
Tiến trình chờ ngoài đoạn găng không được ngăn cản các tiến trình khác vào đoạn găng 
Không có tiến trình nào phải chờ lâu để được vào đoạn găng 
Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nó vào đoạn găng khi tài nguyên găng được giải phóng 
52 
2.4 Điều độ tiến trình qua đoạn găng 
a. Giải pháp phần cứng 
Dùng cặp chỉ thị STI(setting interrupt) và CLI (clean interrupt) 
Ví dụ : 
Procedure P(i : integer) 
	begin 
	repeat 
	CLI; 
	; 
	STI; 
	; 
	until .F. 
	end; 
53 
Dùng chỉ thị TSL(Test and set) 
Function TestAndSetLock(Var i:integer):boolean 
Begin 
	if i=0 then 
	begin 
	i:=1; 
	 TestAndSetLock :=true 
	end; 
	else 
	 TestAndSetLock :=false 
End; 
54 
Procedure P(lock : integer); 
	begin 
	repeat 
	while 	( TestAnhSetLock(lock )) do; 
	; 
	lock:=0 
	; 
	until .F. 
	end; 
55 
b. Giải pháp dùng biến khóa 
Dùng biến khóa chung 
Procedure P(lock : integer); 
	begin 
	repeat 
	while 	lock=1 do; 
	Lock=1 
	; 
	lock:=0 
	; 
	until .F. 
	end; 
56 
Dùng biến khóa riêng 
Var lock1, lock2: byte; 
begin 
lock1:=0; lock2:=1 
	p1: repeat 
	while 	lock2=1 do; 
	Lock1:=1 
	; 
	lock1:=0 
	; 
	 until .F. 
	p2: repeat 
	while 	lock1=1 do; 
	Lock2:=1 
	; 
	lock2:=0 
	; 
	 until .F. 
end 
57 
C. Giải pháp được hỗ trợ bởi HĐH và ngôn ngữ lập trình 
Dùng Semaphore(đèn báo ) 
Semaphore S là 1 biến nguyên , khởi gán bằng 1 giá trị không âm , là khả năng phục vụ của tài nguyên găng tương ứng với nó 
Ứng với S có 1 hàng đợi F(s ) lưu các tiến trình đang chờ trên S 
Thao tác Down giảm S 1 đơn vị , Up tăng S 1 đơn vị 
Mỗi tiến trình trước khi vào đoạn găng cần gọi Down để giảm S và kiểm tra nếu S&g ... theo cấu trúc overlay 
Chỉ 1 phần cần thiết của chương trình mới được nạp vào bộ nhớ lúc nạp chương trình . Khi cần mudun nào đó mà không sẵn có trong bộ nhớ người sử dụng phải nạp nó vào đúng phân vùng của chương trình và sẽ ghi đè lên bất kỳ chương trình hoặc dữ liệu ở trong đó 
101 
2.1 Kỹ thuật phân vùng cố định(tt ) 
Thứ 2: Khi kích thước của chương trình nhỏ hơn kích thước của 1 phân vùng hoặc lớn hơn kích thước của phân vùng nhưng không phải là bội số của kích thước phân vùng . 
 Điều này gây ra sự phân mảnh nội vi , lãng phí bộ nhớ 
102 
2.1 Kỹ thuật phân vùng cố định(tt ) 
Để khắc phục nhược điểm này có thể sử dụng phân vùng cố định có kích thước không bằng nhau 
Có 2 lựa chọn để đưa tiến trình vào dạng phân vùng này 
103 
2.1 Kỹ thuật phân vùng cố định(tt ) 
Lựa chọn 1: 
Mỗi phân vùng có một hàng đợi tương ứng 
Khi 1 tiến trình cần được nạp vào bộ nhớ sẽ đưa vào hàng đợi của phân vùng có kích thước vừa đủ để chứa nó để được đưa vào phân vùng 
Nhược điểm : Có thể có phân vùng đang trống nhưng lại có nhiều tiến trình đang chờ để vào phân vùng khác 
OS 
Tiến trình  mới 
104 
2.1 Kỹ thuật phân vùng cố định(tt ) 
Lựa chọn 2: 
Dùng 1 hàng đời chung cho tất cả các phân vùng 
Khi có tiến trình muốn nạp vào bộ nhớ nhưng chưa được nạp sẽ được đưa vào hàng đợi 
Khi có phân vùng trống , HĐH sẽ chọn tiến trình có kích thước vừa đủ để đưa vào phân vùng 
Phương pháp này gây khó khăn trong việc lựa chọn tiến trình để nạp vào phân vùng 
OS 
Tiến trình  mới 
105 
2.2 Kỹ thuật phân vùng động 
Vùng nhớ user program không được phân chia trước 
Khi có tiến trình nạp vào bộ nhớ , HĐH cấp cho nó không gian nhớ đúng kích thước của nó 
Khi tiến trình kết thúc , vùng nhớ của nó sẽ được thu hồi để HĐH cấp cho tiến trình khác , kể cả tiến trình mới có kích thước nhỏ hơn vùng nhớ của tiến trình đã giải phóng 
106 
2.2 Kỹ thuật phân vùng động(tt ) 
OS- 128k 
Process1 
64k 
Process2 
128k 
Process3 
32k 
Process4 
128k 
Process5 
120k 
Process6 
65k 
Tiến trình 1,2,3,4 lần lượt được nạp vào bộ nhớ 
Tiến trình 2 kết thúc , vùng nhớ được giải phóng 
Tiến trình 5 được nạp vào vùng nhớ của tiến trình 
 2 vừa giải phóng 
4. Tiến trình 6 yêu cầu được nạp vào bộ nhớ nhưng 
 không thể vì không có vùng nhớ trống phù hợp 
 để nạp trong khi tổng dung lượng nhớ còn trống 
 lớn hơn kích thước mà tiến trình yêu cầu 
107 
2.2 Kỹ thuật phân vùng động(tt ) 
Cơ chế quản lý phân vùng trống 
Trong kỹ thuật phân vùng động , HĐH phải đưa ra các cơ chế thích hợp để quản lý các khối nhớ đã cấp phát hay còn trống trên bộ nhớ . 
HĐH sử dụng cơ chế Bản đồ bít và Danh sách liên kết . 
Cả hai cơ chế HĐH đều chia không gian nhớ thành các đơn vị cấp phát có kích thước bằng nhau , các đơn vị cấp phát liên tiếp nhau tạo thành 1 khối nhớ , HĐH cấp phát các khối nhớ này cho các tiến trình 
108 
2.2 Kỹ thuật phân vùng động(tt ) 
Cơ chế bản đồ Bit: 
Mỗi đơn vị cấp phát được đại diện bởi một Bit trong bản đồ bit. 
Đơn vị cấp phát còn trống đại diện bằng bit 0, ngược lại đại diện bằng bit 1 
Bản đồ bit 
109 
2.2 Kỹ thuật phân vùng động(tt ) 
Cơ chế danh sách liên kết : 
Mỗi khối trên bộ nhớ được đại diện bởi một phần tử trong danh sách liên kết 
Mỗi phần tử gồm 3 trường chính : 
Trường đầu tiên : cho biết khối nhớ đã cấp phát ( kí hiệu P) hay còn trống ( kí hiệu H) 
Trường thứ 2: cho biết thư tự của đơn vị cấp phát đầu tiên trong khối 
Trường thứ 3: cho biết tổng số đơn vị cấp phát trong khối 
110 
2.2 Kỹ thuật phân vùng động(tt ) 
111 
2.2 Kỹ thuật phân vùng động(tt ) 
Qui tắc chọn phân vùng trống 
Khi có một tiến trình cần được nạp vào bộ nhớ , HĐH phải quyết định chọn một khối nhớ phù hợp để nạp tiến trình sao cho việc lựa chọn này dẫn đến việc sử dụng bộ nhớ chính là hiệu quả nhất . 
Có 3 thuật toán mà HĐH sử dụng trong trường hợp này : Best-fit, First-fit, và Next-fit 
112 
2.2 Kỹ thuật phân vùng động(tt ) 
Best-fit: chọn khối nhớ có kích thước vừa đúng bằng kích thước của tiến trình cần được nạp vào bộ nhớ . 
First-fit: HĐH sẽ bắt đầu quét qua các khối nhớ trống bắt đầu từ khối nhớ trống đầu tiên trong bộ nhớ , và sẽ chọn khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình . 
Next-fit: tương tự như First-fit nhưng ở đây HĐH bắt đầu quét từ khối nhớ trống kế sau khối nhớ vừa được cấp phát và chọn khối nhớ trống kế tiếp đủ lớn để nạp tiến trình 
113 
2.3 Kỹ thuật phân trang đơn 
Bộ nhớ chính được chia thành các phần bằng nhau và cố định , được đánh số bắt đầu từ 0 và được gọi là các khung trang 
Không gian địa chỉ của các tiến trình cũng được chia thành các phần có kích thước bằng kích thước của một khung trang được gọi là các trang 
Khi tiến trình nạp vào bộ nhớ thì các trang được nạp vào các khung trang bất kỳ còn trống có thể không liên tiếp nhau 
114 
2.3 Kỹ thuật phân trang đơn(tt ) 
HĐH sử dụng các bảng trang(PCT ) để theo dõi vị trí các trang của tiến trình trên bộ nhớ . Mỗi tiến trình có bảng trang riêng 
115 
2.3 Kỹ thuật phân trang đơn(tt ) 
Sự phân mảnh trong cơ chế này ? 
Sự phân mảnh sẽ xảy ra trong kỹ thuật này khi : 
Kích thước của tiến trình nhỏ hơn kích thước của 1 khung trang 
Kích thước của tiến trình lớn hơn kích thước khung trang nhưng không phải là bội số của 1 khung trang 
116 
2.4 Kỹ thuật phân đoạn đơn 
Bộ nhớ chính được chia thành các phần cố định có kích thước không bằng nhau , được đánh số bắt đầu từ 0 được gọi là các phân đoạn 
Mỗi phân đoạn bao gồm số hiệu phân đoạn và kích thước của nó 
Không gian địa chỉ của các tiến trình kể cả các dữ liệu liên quan cũng được chia thành các đoạn có kích thước không nhất thiết phải bằng nhau 
117 
2.4 Kỹ thuật phân đoạn đơn(tt ) 
Khi tiến trình được nạp vào bộ nhớ , các đoạn được nạp vào các phân đoạn còn trống trên bộ nhớ , các phân đoạn này có thể không liên tục nhau 
Để theo dõi các đoạn của các tiến trình khác nhau trên bộ nhớ HĐH sử dụng các bảng phân đoạn (SCT), thông thường mỗi tiến trình có 1 bảng phân đoạn riêng 
118 
2.4 Kỹ thuật phân đoạn đơn(tt ) 
Mỗi phần tử trong bảng phân đoạn tối thiểu gồm 2 trường 
Trường thứ nhất : cho biết địa chỉ cơ sở của phân đoạn mà đoạn chương trình tương ứng được nạp 
Trường thứ 2: cho biết độ dài của phân đoạn 
119 
2.4 Kỹ thuật phân đoạn đơn(tt ) 
Code 
100k 
Data 
64k 
Stack 
150 
base 
limit 
64 
0 
64 
164 
228 
356 
478 
100 
164 
64 
356 
150 
120 
3. KỸ THUẬT BỘ NHỚ ẢO 
121 
3.1 Khái niệm nhớ ảo 
Để thực thi chương trình có kích thước lớn hơn bộ nhớ vật lý cấp phát cho nó 
cần xây dựng chương trình theo cấu trúc Overlay 
gây khó khăn cho người lập trình 
Để khắc phục khó khăn cho người lập trình , ý tưởng sử dụng bộ nhớ ảo ra đời 
Kỹ thuật bộ nhớ ảo cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý 
122 
3.1 Khái niệm nhớ ảo(tt ) 
Bộ nhớ ảo mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất , tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý 
Người sử dụng chỉ nhìn thấy và làm việc trong không gian địa chỉ ảo , chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng 
123 
3.2 Cài đặt bộ nhớ ảo 
Có thể cài đặt bộ nhớ ảo theo 2 kỹ thuật 
Phân trang theo yêu cầu : Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swap 
Phân đoạn theo yêu cầu : sử dụng kỹ thuật phân đoạn kết hợp với kỹ thuật swap 
124 
3.2.1 Phân trang theo yêu cầu 
Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swap 
Một chương trình được xem như 1 tập hợp các trang thường trú trên bộ nhớ ngoài 
Khi thực thi hệ thống không nạp toàn bộ chương trình vào bộ nhớ trong mà chỉ nạp những trang cần thiết trong thời điểm hiện tại 
Một trang chỉ được nạp vào bộ nhớ trong khi cần thiết 
125 
3.2.1 Phân trang theo yêu cầu(tt ) 
Cần có cơ chế phần cứng để phân biệt các trang đang ở bộ nhớ trong và các trang đang ở bộ nhớ ngoài 
Tổ chức bảng trang như kỹ thuật phân trang đơn nhưng 1 phần tử trong bảng trang chứa nhiều thông tin phức tạp hơn 
Cần có 1 bit cho biết trang tương ứng của tiến trình có hay không trong bộ nhớ chinh và 1 bit cho biết trang có bị sửa đổi hay không so với lần nạp gần nhất 
126 
Hiện tượng lỗi trang 
Khi hệ thống truy xuất tới 1 trang được đánh dấu là bất hợp lệ sẽ làm phát sinh lỗi trang , HĐH xử lý lỗi trang như sau : 
Bước 1 : Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ 
 	- Nếu truy xuất bất hợp lệ  : kết thúc tiến trình 
 	- Ngược lại  : đến bước 2 
Bước 2 : Tìm vị trí chứa trang muốn truy xuất trên đĩa . 
Bước 3 : Tìm một khung trang trống trong bộ nhớ chính 
	- Nếu tìm thấy : đến bước 4 
	- Ngược lại , thực hiện cơ chế swap out 1 trang thích 	 hợp trên bộ nhớ chính sau đó cập nhật bảng trang 	 tương ứng rồi đến bước 4 
127 
Hiện tượng lỗi trang(tt ) 
Bước 4: 
- Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính tại khung trang đã xác định được 
- Cập nhật nội dung bảng trang tương ứng . 
- Tái kích hoạt tiến trình người sử dụng 
128 
Thay thế trang 
Khi các khung đã đầy mà cần nạp thêm trang thì phải thay thế một trang đang có trên khung 
Nếu trang bị thay thế có thay đổi nội dung thì cần phải đưa ra đĩa 
Có các phương pháp chọn phần tử thay thế : 
Optimal: Thay thế trang sẽ lâu được sử dụng nhất trong tương lai 
FIFO: trang ở trong bộ nhớ lâu nhất sẽ được chọn thay thế 
LRU (Least Recently Used ): trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất 
129 
3.2.2 Phân đoạn đoạn theo yêu cầu 
Bộ nhớ ảo bao gồm các đoạn (segment) có kích thuớc không cố định 
Khi nạp đoạn vào bộ nhớ thì hệ điều hành tìm khoảng trống đủ để nạp đoạn 
Có bảng đoạn quản lý các đoạn 
130 
3.2.3 Phân đoạn kết hợp phân trang 
Kết hợp các ưu điểm của phân đoạn và phân trang 
Bộ nhớ ảo bao gồm các đoạn 
Trong mỗi đoạn thực hiện phân trang 
131 
Tài liệu tham khảo 
Trần Hạnh Nhi , Giáo trình HĐH nâng cao , ĐH Khoa học Tự nhiên Tp.HCM , 1998 
Nguyễn Gia Định-Nguyễn Kim Tuấn , Nguyên Lý HĐH, NXB Khoa học kỹ thuật , 2005 
William Stallting , Operating Systems, Prentice Hall, 1995 
132 
CHƯƠNG IV:QUẢN LÝ FILE VÀ ĐĨA 
133 
1. CÁC KHÁI NIỆM CƠ BẢN 
134 
File? 
File hay còn gọi là tập tin, là tập hợp thông tin/dữ liệu được tổ chức theo một cấu trúc nào đó. 
Nội dung của tập tin có thể là chương trình, dữ liệu, văn bản,... 
Mỗi tập tin được lưu trên thiết bị lưu trữ đều được đặt tên. 
Mỗi hệ điều hành có qui ước đặt tên khác nhau, tên tập tin thường có 2 phần: phần tên (name) và phần mở rộng (extension). 
135 
Các thuộc tính trên file 
Tên (name) 
Định danh (identifier) 
Kiểu (type) 
Vị trí (location) 
Kích thước (size) 
Giờ (time), ngày (date) và định danh người dùng (user identification) 
Các thông tin tập tin được lưu trữ trên cấu trúc thư mục và được duy trì trên thiết bị 
136 
Các thao tác trên file 
Tạo 
Mở 
Đóng 
Ghi 
Đọc 
Di chuyển 
Xóa 
Tìm 
Lấy thuộc tính 
Đổi tên 
.V.v. 
137 
Các kiểu file 
File thường : là file văn bản hay file nhị phân chứa thông tin của người sử dụng 
Thư mục : là những file hệ thống dùng để lưu giữ cấu trúc của hệ thống file 
File có ký tự đặc biệt : liên quan đến nhập/xuất thông qua các thiết bị nhập/xuất tuần tự như màn hình, máy in,.. 
File khối : dùng để truy xuất trên thiết bị đĩa 
138 
Cấu trúc file 
Các hệ điều hành thường hỗ trợ ba cấu trúc file thông dụng là: 
Không có cấu trúc : file là một dãy tuần tự các byte 
Có cấu trúc : File là một dãy các mẫu tin có kích thước cố định 
Cấu trúc cây : File gồm một cây của những mẫu tin không cần thiết có cùng chiều dài, mỗi mẫu tin có một trường khoá giúp việc tìm kiếm nhanh hơn 
139 
2. CÁC PHƯƠNG PHÁP TRUY XUẤT 
Truy xuất tuần tự 
Truy xuất trực tiếp 
140 
3. CẤU TRÚC THƯ MỤC 
141 
3.1 Cấu trúc thư mục dạng đơn cấp 
Một thư mục cho tất cả các tập tin 
Thư mục đơn cấp có nhiều hạn chế khi số lượng tập tin tăng. Vì tất cả tập tin được chứa trong cùng thư mục, chúng phải có tên khác nhau. 
142 
3.2 Cấu trúc thư mục dạng hai cấp 
Mỗi người dùng có 1 thư mục riêng 
các người dùng khác nhau có thể có các tập tin với cùng một tên 
Cấu trúc này cô lập một người dùng từ người dùng khác. 
143 
3.3 Cấu trúc thư mục dạng cây 
144 
3.4 Cấu trúc thư mục dạng đồ thị không chứa chu trình 
Có chung nhau thư mục con và các file 
145 
3.5. Cấu trúc thư mục dạng đồ thị tổng quát 
146 
4. CÁC PHƯƠNG PHÁP CÀI ĐẶT HỆ THỐNG QUẢN LÝ TẬP TIN 
147 
4.1 BẢNG DANH MỤC QUẢN LÝ THƯ MỤC, TẬP TIN 
Lưu trữ các thông tin liên quan đến các tập tin và các thư mục đang tồn tại trên đĩa(hoặc thiết bị lưu trữ khác) 
Bảng danh mục gồm nhiều entry, mỗi entry sẽ lưu thông tin về tên, thuộc tính, vị trí lưu trữ,... của một tập tin hay thư mục. 
Khi có tập tin/thư mục được tạo ra, HĐH sẽ dùng một entry trong bảng danh mục để chứa các thông tin của nó 
Khi một tập tin/thư mục xóa khỏi đĩa thì HĐH sẽ giải phóng entry của nó trong bảng danh mục 
148 
4.1 BẢNG DANH MỤC QUẢN LÝ THƯ MỤC, TẬP TIN(tt) 
Số lượng entry trong bảng dnah mục có thể cố định hoặc không cố định 
Bảng danh mục thường được lưu trữ tại một không gian đặc biệt nào đó trên đĩa 
Trong quá trình hoạt động bảng danh mục thường được HĐH nạp từ đĩa vào bộ nhớ để sẵn sàng cho việc truy xuất file của HĐH sau này 
149 
4.2 Bảng phân phối vùng nhớ 
HĐH chia không gian đĩa thành các khối (block) có kích thước bằng nhau 
Nội dung file được chia thành các block bằng nhau và bằng kích thước block trên đĩa trừ block cuối cùng 
Khi lưu tập tin trên đĩa HĐH cấp vừa đủ số block để lưu trữ tập tin 
HĐH tổ chức bảng phân phối vùng nhớ để lưu giữ dãy các khối trên đĩa đã cấp phát cho tập tin hay thư mục 
150 
4.3 Các phương pháp cấp phát vùng nhớ 
Cấp phát liên tục: lưu trữ tập tin trên dãy các block liên tiếp 
151 
4.3 Các phương pháp cấp phát vùng nhớ(tt) 
Cấp phát theo danh sách liên kết: 
sử dụng danh sách liên kết các block để quản lý các block chứa file 
Word đầu tiên của mỗi block đĩa được sử dụng như 1 con trỏ trỏ đến block kế tiếp 
Kích thước của block đĩa lớn hơn kích thước block file 1 word 
152 
4.3 Các phương pháp cấp phát vùng nhớ(tt) 
Cấp phát theo danh sách liên kết sử dung Index: 
Tất cả các con trỏ liên kết các block được lưu vào 1 vị trí gọi là khối chỉ mục 
Mỗi tập tin có khối chỉ mục của chính nó, là 1 mảng địa chỉ block đĩa lưu tập tin 
153 
I-NODES 
HĐH thiết kế 1 bảng nhỏ để theo dõi các block của 1 file được gọi là I-nodes 
Một I-nodes gồm 2 phần: 
Phần 1 chứa các thuộc tính tập tin 
Phần 2 được chia ra làm 2 phần nhỏ 
Phần nhỏ thứ nhất gồm 10 phần tử, mỗi phần tử chứa địa chỉ khối dữ liệu của tập tin 
Phần tử thứ 11 chứa địa chỉ gián tiếp cấp 1 (single indirect) 
Phần tử thứ 12 chứa địa chỉ gián tiếp cấp 2 (double indirect) 
Phần tử thứ 13 chứa địa chỉ gián tiếp cấp 3 (double indirect) 
154 
I-NODES(tt) 
Địa chỉ gián tiếp cấp 1: Chứa địa chỉ của một khối, trong khối đó chứa một bảng có thể từ 2 10 đến 2 32 phần tử mà mỗi phần tử mới chứa địa chỉ của khối dữ liệu của tập tin 
Địa chỉ gián tiếp cấp 2: chứa địa chỉ của bảng các khối địa chỉ gián tiếp cấp 1 
Địa chỉ gián tiếp cấp 3: chứa địa chỉ của bảng các khối địa chỉ gián tiếp cấp 2. 
155 
TÀI LiỆU 
[1] Nguyễn Gia Định-Nguyễn Kim Tuấn , Nguyên Lý HĐH, NXB Giáo dục , 2005 
[2] Operating Systems , H. M. Deitel , P. J. Deitel and D. R. Choffnes , Pearson Education International, 2004 
[3] 
156