Bài giảng Hệ điều hành (Operating System)

h
Chỉ số ơ FAT đầu tiên
của thư mục cha nếu
cha là thư mục gốc thì
bằng 0
Block
51
Ví dụ
• Giả sử thư mục L (6) trong ví dụ chứa tập tin A(1) và
B.doc(8) thì nội dung của block 6 và bảng FAT như sau:
1032doc
B
332
A
016..
816.
6FFF
FFFFFF
45
FFF9 
FFF0 (free)
52
Bài tập FAT và RD
• Dung lượng đĩa sẽ quyết định kích thước 1 ơ trên
bảng FAT.
• FAT12  212 ơ = 4096 ơ  tối đa là 4094 block. (vì
mỗi ơ quản lý 1 block) Tính tốn khoảng gần đúng.
• Ví dụ: cho đĩa cĩ dung lượng 20MB. Mỗi block là 2 
sector. Hỏi đĩa sử dụng bảng FAT nào là hợp lý?
– Số ơ = số block + 2 = (20*10242)/(2*512) 
= 5*212+2 Nên dùng FAT 16.
• Nếu dùng FAT 32 thì sao?
– Mỗi block cĩ kích thước nhỏ đi 1 block cĩ thể
chỉ là 1 sector.
53
Bài tập FAT và RD
• Cho một volume cĩ 20 block như sau
• Thư mục gốc \:
– E (0)
• M.TXT (1,19,18)
• C (2)
– U.TXT (4,5)
– V (6)
» N.TXT (7,8)
» I.TXT (9,10)
– M.TXT (3,17,16)
• Hãy vẽ FAT, RD và các block liên quan (block nội dung 
của thư mục cĩ cấu trúc tượng tự RD thêm vào . và ..) .
• Quy ước cĩ phần mở rộng là tập tin, cĩ chứa con thì sẽ
phải là thư mục.
Cho một đĩa cĩ dung lượng 40GB. Mỗi block gồm 16 sector. Hỏi ta sử
dụng bảng FAT nào là thích hợp nhất?
54
Câu Hỏi Ơn tập
1. So sánh thời gian các lệnh copy, move, 
delete trong tất cả các trường hợp cĩ thể cĩ.
2. Tại sao trong UNIX khơng cĩ system call 
detete(…) để xố file mà chỉ cĩ system call 
unlink(…) để xố một link đến file?
3. Trình bày các thao tác của DOS/Win khi tiến
hành khi delete một file?
1Hệ thống quản lý nhập/xuất
2Tổng quan
• Giới thiệu về thiết bị nhập xuất
• Các kỹ thuật quản lý thao tác nhập xuất
• Các vấn đề về thiết kế hệ thống quản lý 
nhập xuất trong HðH
• Kỹ thuật vùng đệm nhập xuất
• Quản lý hệ thống nhập xuất đĩa
3Phân loại các thiết bị nhập/xuất
• Human readable
– Dùng để giao tiếp với người dùng
– Máy in
– Thiết bị đầu cuối liên quan đến hiển thị
• Màn hình hiển thị
• Bàn phím
• Chuột
4Phân loại các thiết bị nhập/xuất 
(2)
• Machine readable
– Dùng để giao tiếp với thiết bị điện tử
– ðĩa
5Phân loại các thiết bị nhập/xuất 
(2)
• Giao tiếp
– Dùng để giao tiếp với các thiết bị ở xa 
(remote device)
– Modem
6Sự khác nhau giữa các thiết bị
I/O
• Tốc độ
• Ứng dụng
• Mức độ phức tạp để kiểm sốt
• ðơn vị truyền
• Biểu diễn dữ liệu
• Phát sinh lỗi
8Sự khác nhau giữa các thiết bị I/O 
(2)
• Ứng dụng
– ðĩa dùng để lưu trữ địi hỏi phải cĩ hệ thống 
quản lý tập tin đi kèm
– ðĩa dùng để làm bộ nhớ ảo địi hỏi phải cĩ sự
hỗ trợ phần cứng và phần mềm.
– Các thiết bị đầu cuối được sử dụng bởi quản 
trị sẽ cĩ độ ưu tiên cao hơn.
9Sự khác nhau giữa các thiết bị I/O 
(3)
• ðộ phức tạp để kiểm sốt:
– Máy in so với đĩa
• ðơn vị truyền
– Cĩ thể được truyền theo byte hoặc khối (cĩ thể là bit)
• Biểu diễn dữ liệu
– Cơ chế mã hĩa
• Phát sinh lỗi
– Thiết bị khác nhau xử lý lỗi phát sinh khác nhau
10
Kỹ thuật xử lý I/O
• Programmed I/O
– Tiến trình phải busy-waiting cho thao tác nhập 
xuất hồn thành
• Interrupt-driven I/O
– Phát sinh lệnh I/O
– Bộ xử lý tiếp tục thực thi các chỉ thị khác
– Module I/O gởi một ngắt đến bộ xử lý khi 
hồn thành thao tác I/O
11
Kỹ thuật quản lý I/O (2)
• Direct Memory Access (DMA)
– Module DMA điều khiển việc chuyển đổi dữ
liệu giữa bộ nhớ chính và thiết bị I/O
– Bộ xử lý chỉ bị ngắt khi tồn bộ khối đã được 
chuyển
12
Lịch sử phát triển của quản lý 
I/O
• Bộ xử lý trực tiếp điều khiển thiết bị ngoại 
vi
• Bộ điều khiển (Controller) hay module I/O 
module được thêm vào
– Bộ xử lý dùng programmed I/O khơng cĩ hỗ
trợ ngắt
– Bộ xử lý khơng cần phải quản lý chi tiết các 
thiết bị ngoại vi
13
Lịch sử phát triển của quản lý 
I/O
• Bộ điều khiển hoặc module I/O module cĩ
hỗ trợ ngắt
– Bộ xử lý khơng cần phải bỏ thời gian chờ thao 
tác I/O thi hành
• Direct Memory Access
– Khối dữ liệu được chuyển vào bộ nhớ mà
khơng cần xử lý của bộ xử lý
– Bộ xử lý chỉ liên quan vào lúc bắt đầu và lúc 
kết thúc chuyển khối.
14
Lịch sử phát triển của quản lý 
I/O
• Module I/O là một bộ xử lý riêng biệt
– Cĩ tập lệnh chuyên biệt
• Bộ xử lý I/O
– Module I/O cĩ bộ nhớ riêng
15
Các vấn đề thiết kế liên quan đến 
HðH
• Tính hiệu quả
– Hầu hết các thiết bị I/O đều rất chậm so với 
bộ nhớ chính
• Sử dụng cơ chế đa chương cho phép một vài tiến 
trình chờ I/O trong khi tiến trình khác thi hành
– Cơ chế swapping
• Bản chất cũng là thao tác nhập/xuất
16
Các vấn đề thiết kế liên quan đến 
HðH
• Tính tổng quát
– Mong muốn xử lý tất cả các thiết bị I/O giống 
nhau
– Che giấu hầu hết chi tiết của thiết bị nhận 
xuất để tiến trình (mức cao) xem các thiết bị ở
một vài chức năng thơng dụng như read, 
write, open, close, lock, unlock
17
Mơ hình lơgic các chức năng nhập xuất
• Giao tiếp đơn giản (thiết bị ngoại vi cục 
bộ)
– Logical I/O
– Device I/O
– Scheduling and Control
• Giao tiếp thơng quan cổng kết nối
– Communication architecture
– Device I/O
– Scheduling and Control
18
Mơ hình lơgic các chức năng nhập 
xuất
• Hệ thống tập tin
– Directory management
– File system
– Physical organization
– Device I/O
– Scheduling and Control
20
Kỹ thuật vùng đệm nhật/xuất
• Lý do
– Các tiến trình phải chờ hồn thành I/O trước 
khi xử lý tiếp
– Thao tác I/O vẫn phải tốn bộ nhớ
21
Kỹ thuật vùng đệm nhật/xuất (2)
• Các thiết bị I/O cĩ hai dạng hỗ trợ nhập/xuất cơ bản:
– Hướng khối (block – oriented)
– Hướng dịng (stream – oriented)
• Block-oriented
– Thơng tin được lưu trong những khối cĩ kích thước cho trước
– ðơn vị chuyển là một khối / một lần
– Dùng cho đĩa
• Stream-oriented
– Truyền thơng tin như là một dịng các byte
– Dùng cho các thiết bị đầu cuối, máy in, chuột, cổng giao tiếp,…
22
Single Buffer
• HðH dành riêng một vùng đệm trong bộ nhớ
chính cho thao tác I/O
• Block-oriented
– Dữ liệu vào được chuyển vào vùng đệm theo đơn vị
khối
– Khối đĩ sẽ chuyển đến cho tiến trình người dùng khi 
cần
– Khối khác được chuyển vào vùng đệm, trong khi tiến 
trình đang xử lý khối trước đĩ.
• Stream-oriented
– Như khối nhưng với đơn vị là dịng. Một dịng được 
kết thúc bởi dấu CF.
23
I/O Buffering
24
Double Buffer
• Dùng hai vùng đệm thay vì một
• Một tiến trình cĩ thể chuyển dữ liệu vào và
ra một vùng đệm trong khi hệ điều hành 
truyền thơng tin hoặc thao tác trên vùng 
đệm cịn lại
25
Circular Buffer
• Nhiều hơn hai vùng đệm
• Trong trường hợp thao tác nhập xuất gắn 
liền với tiến trình.
26
I/O Buffering
27
Nhắc lại cấu trúc đĩa
• Các thành phần của đĩa
– platters
– surfaces
– tracks
– sectors
– cylinders
– arm
– heads
platter
surface
track
sector
cylinder
arm
head
28
Các tham số liên quan đến hiệu 
năng truy xuất đĩa
• ðể đọc hay ghi, đầu đĩa phải di chuyển đến 
track và sector tương ứng
• Seek time
– Thời gian dùng để định vị đầu đĩa đến track mong 
muốn
• Rotational delay hoặc rotational latency
– Thời gian dùng để di chuyển đầu đĩa đến sector 
tương ứng (vị trí đầu tiên của sector)
• Transfer time
– Thời gian chuyển dữ liệu (từ hoặc vào bộ nhớ chính)
29
Thời gian thi hành tác vụ I/O
30
Tham số hiệu năng đĩa
• Access time = seek time + rotational delay
– Thời gian để đặt đầu đĩa và đúng vị trí để đọc 
và ghi
• Dữ liệu sẽ được chuyển khi đầu đĩa nằm 
đúng vị trí sector.
31
Chính sách lập lịch trên đĩa
• Mấu chốt là Seek time.
– Vì sao?
• Với một đĩa cĩ thể một số các yêu cầu I/O
• Cần cĩ cơ chế xử lý các yêu cầu này thích 
hợp  tăng hiệu năng xử lý I/O
32
Chính sách lập lịch trên đĩa (2)
• First-in, first-out (FIFO)
– Xử lý yêu cầu một cách tuần tự
– Cơng bằng cho tất cả tiến trình
– Nếu nhiều tiến trình thì xác suất xem như là
ngẫu nhiên
33
Chính sách lập lịch trên đĩa (3)
• Cĩ ưu tiên
– Mục tiêu khơng phải là tối ưu đĩa mà để phục 
vụ cho các mục tiêu khác
– Các cơng việc cĩ thời gian thi hành ngắn cĩ
thể cĩ độ ưu tiên cao hơn
– Khả năng tương tác cao
34
Chính sách lập lịch trên đĩa (4)
• Last-in, first-out
– Tốt cho các hệ thống xử lý giao dịch
(transaction processing system)
• Thiết bị được giao cho người dùng gần đây nhất
 đầu đọc di chuyển ít nhất
– Cĩ thể xảy ra tình trạng đĩi (starvation)
35
Chính sách lập lịch trên đĩa (5)
• First Come, First Service
– Phương pháp này dễ lập trình nhưng khơng
cung cấp dịch vụ tốt.
– Ví dụ: cần phải đọc các khối theo thứ tự sau
98 183 37 122 14 75 và đầu đọc đang ở vị trí
59.
– ðầu đọc sẽ lần lượt đi qua các khối 59 98 183 
37 122 12 75.
36
Chính sách lập lịch trên đĩa (6)
• Shortest Service Time First (SSTF)
– Chọn yêu cầu I/O mà địi hỏi ít di chuyển nhất
đầu đĩa từ vị trí hiện tại
– Luơn luơn cho ra seek time nhỏ nhất.
– Ví dụ: cần đọc các khối 98 183 37 122 14 124 
65 và 67. Giả sử đầu đọc đang ở vị trí 53.
– ðầu đọc sẽ lần lượt qua các khối 53 65 67 37 
4 98 122 124 183
37
Chính sách lập lịch trên đĩa (7)
• SCAN
– ðầu đọc di chuyển theo một hướng nhất định. 
Ví dụ cần đọc các khối 98 183 37 122 14 124 
65 67. Giả sử đầu đọc ở vị trí 53.
– ðầu đọc sẽ lần lượt qua các khối 53 37 14 0
65 67 98 122 124 183 (theo SCAN định
hướng về 0)
38
Chính sách lập lịch trên đĩa (7)
• C-SCAN
– Như SCAN, giới hạn chỉ di chuyển theo 1 
chiều
– Quay về vị trí bắt đầu ngay khi đụng track ở
xa nhất, khơng cần phải tiếp tục.
– Ví dụ cần đọc các khối 98 183 37 122 14 124 
65 67. Giả sử đầu đọc ở vị trí 53.
– ðầu đọc sẽ lần lượt qua các khối 53 65 67 98 
122 124 183 199 0 14 37
39
Disk Scheduling Algorithms
40
Câu hỏi ơn tập
– Ví dụ: cần đọc các khối 98 183 124 65 12 và
67. Giả sử đầu đọc đang ở vị trí 53.
– ðầu đọc sẽ lần lượt qua các khối nào và vẽ
sơ đồ theo các thuật tốn đọc đĩa FCFS, 
SSTF, SCAN và C-SCAN.
– Từ đĩ kết luận xem cách đọc nào tối ưu nhất.
41
ðịa chỉ tương đối = (head, cylinder, sector)
Head : 0  Số mặt trên đĩa – 1
Cylinder: 0  Số cylinder trên đĩa – 1
Sector : 1  Số sector trên track
ðịa chỉ tuyệt đối = head * Số sector/track + 
track * số sector/cylinder + sector - 1