Hệ điều hành - Chương 1: Giới thiệu hệ điều hành

HỆ ðIỀU HÀNH Chương 1 GIỚI THIỆU HỆ ðIỀU HÀNH 2Nội dung chương 1 I. ðịnh nghĩa hệ điều hành II. Phân loại hệ điều hành III. Các khái niệm cơ bản IV. Cấu trúc hệ điều hành V. Nhắc lại về kiến trúc máy tính 3I. ðịnh nghĩa hệ điều hành
Với người sử dụng (users): • HDH là chương trình nạp vào máy đầu tiên • HDH quản lý tương tác người máy
Với người lập trình (programmers): • HDH là máy tính mở rộng • HDH quản lý tài nguyên, quản lý hoạt động của các chương trình ứng dụng Mục tiêu: • Tiện lợi, hiệu quả • Dễ phát triển 4Các lớp hoạt động của máy tính 5II. Phân loại hệ điều hành
Phân loại theo thứ tự xuất hiện  Lịch sử hệ điều hành
Phân loại theo hoạt động 6Phân loại theo thứ tự xuất hiện
Thế hệ 1 1945 - 1955 • ðèn điện tử chân khơng – tuần tự
Thế hệ 2 1955 - 1965 • Transistors – batch systems
Thế hệ 3 1965 - 1980 • Mạch tích hợp (ICs) – đa chương
Thế hệ 4 1980 - nay • Máy vi tính – đa chương hiện đại 7Ví dụ: batch system 8Các loại hệ điều hành hiện đại
Hệ điều hành máy tính lớn (mainframe)
Hệ điều hành server
Hệ điều hành đa xử lý (multiprocessor)
Hệ điều hành máy vi tính
Hệ điều hành thời gian thực (real-time)
Hệ điều hành nhúng (embeded) 9Hệ thống máy tính lớn 10 PDA (Personal Digital Assistant) 11 III. Các khái niệm cơ bản 1. Process (tiến trình) và Thread (luồng) 2. File 3. System Calls – Lệnh gọi hệ thống 4. Shell – Giao diện với người sử dụng 12 1. Process và thread
Process: chương trình được cho thực thi ðược nạp vào bộ nhớ Cĩ các thơng tin trạng thái
Hệ thống đa chương: tập hợp các process tồn tại đồng thời Các process của hệ điều hành Kernel mode Các process ứng dụng User mode 13 Thread
Process cĩ 2 đặc trưng: • ðơn vị được cấp phát tài nguyên • ðơn vị được thực thi
Thread là sự trừu tượng hố đặc trưng thực thi của process • Control path • Lightweight process • Context of execution 14 Mơ hình thread a. Dạng 1-1 b. Dạng n-1 15 Ví dụ ứng dụng thread Một word processor với 3 thread 16 2. File
File: đơn vị lưu trữ trên thiết bị nhớ ngồi
Là sự trừu tượng hố dữ liệu (che dấu phần cứng)
Các thiết bị xuất nhập cĩ thể trừu tượng hố như file
Hệ điều hành tổ chức và quản lý theo hệ thống file (file system), ví dụ: FAT, NTFS, 17 3. Lệnh gọi hệ thống
Chương trình ứng dụng (user program) truyền thơng và yêu cầu dịch vụ của hệ điều hành thơng qua lệnh gọi hệ thống (system calls)
System call: Hàm thư viện của hệ điều hành Phụ thuộc từng loại hệ điều hành 18 Ví dụ: UNIX/Win32 API (Application Programming Interface) 19 Ví dụ: các bước gọi read(fd, buffer, nbytes) 20 4. Giao diện với người sử dụng
Các dạng cơ bản: • Dịng lệnh (command line) • ðồ hoạ (Graphical User Interface, GUI) 21 IV. Cấu trúc hệ điều hành 1. Các thành phần 2. Cấu trúc hệ điều hành 3. ðặc điểm của hệ điều hành hiện đại 4. Hệ thống phân bố 22 1. Các thành phần
Quản lý process • ðiều phối • Xử lý đồng thời
Quản lý bộ nhớ
Quản lý xuất nhập
Quản lý file
Hỗ trợ mạng
Bảo mật 23 Các thành phần của hệ điều hành 24 2. Cấu trúc hệ điều hành
Cấu trúc thơng dụng: Microkernel
Gồm các phần: Kernel
Luơn cĩ trên bộ nhớ
Thực hiện các chức năng cơ bản
Hoạt động trên kernel-mode Services
Hoạt động trên user-mode
Linh hoạt
Phù hợp cho mơi trường phân bố 25 Cấu trúc Windows 2000 26 3. ðặc điểm của hệ điều hành hiện đại
Kiến trúc microkernel (Microkernel architecture)
ða luồng (Multithreading)
ða xử lý đối xứng (Symmytric MultiProcessing)
Hệ điều hành phân bố (Distributed operating systems)
Thiết kế hướng tối tượng (Object-oriented design) 27 4. Hệ thống phân bố
Hệ thống phân bố (distributed systems): • Gồm các máy tính độc lập • Kết nối mạng • Dùng phần mềm hệ thống phân bố Người sử dụng cĩ một hệ thống máy tính luận lý đơn 28 Hệ thống phân bố với middleware 29 Hệ thống phân bố với HðH mạng 30 Hệ thống phân bố với HðH mạng và middleware 31 V. Nhắc lại về tổ chức máy tính 1. Cấu trúc máy vi tính 2. Hoạt động máy vi tính 3. Giới thiệu bộ nhớ cache 32 1. Cấu trúc máy vi tính
Bộ xử lý: 1 hay nhiều
Bộ nhớ
Bus  ISA – 16 bit PCI – 32 bit PCI Express
Thiết bị xuất nhập Mạch điều khiển (controller) Thiết bị (device) 33 Cấu trúc tiêu biểu máy vi tính 34 2. Hoạt động máy vi tính
ðơn vị hoạt động: chu kỳ lệnh
Các thao tác cơ sở: Tính tốn bên trong CPU ðọc ghi bộ nhớ:
Lệnh đọc ghi bộ nhớ
ðịa chỉ bộ nhớ ðọc ghi thiết bị xuất nhập:
Lệnh xuất nhập
Các phương pháp xuất nhập 35 Chu kỳ lệnh cơ bản Lấy lệnh tiếp theo – Fetch next instruction Thực hiện lệnh – Execute instruction 36 Ví dụ: Xuất nhập dùng chương trình 37 Ví dụ: Xuất nhập dùng kỹ thuật ngắt 38 Ví dụ: Xuất nhập dùng kỹ thuật DMA 39 3. Cache a. Khái niệm b. Hoạt động c. Phân loại 40 a. Khái niệm cache
Bộ nhớ dung lượng nhỏ, tốc độ cao
Giúp CPU truy xuất bộ nhớ nhanh hơn 41 b. Hoạt động cache Giả sử CPU đọc 1 khối nhớ k lần
Nếu khơng cĩ cache: CPU đọc khối trên bộ nhớ k lần
Nếu cĩ cache: Lần 1: CPU đọc khối trên bộ nhớ và ghi khối vào cache k-1lần cịn lại: CPU đọc khối trên cache 42 Tỷ số thành cơng (hit ratio, h)
Xét k: k >> 1: h  1, chỉ truy xuất trên cache k = 1: cache là cĩ hại
Truy xuất trên cache: cache hit Khơng truy xuất được trên cache: cache miss Số lần truy xuất thành cơng trên cache k -1 Tổng số lần truy xuất k h = 43 Hoạt động khi cĩ cache Khi CPU cần truy xuất 1 khối nhớ, CPU tìm khối trên cache.
Nếu khối cĩ trên cache: CPU truy xuất khối trên cache
Nếu khối chưa cĩ trên cache: CPU truy xuất khối trên bộ nhớ CPU ghi khối vào cache 44 c. Phân loại cache
Cache cấp 1 – First level cache (L1) Ở trong CPU Kích thước nhỏ (vài chục KB)
Cache cấp 2 – Second level cache (L2) Ở ngồi CPU Kích thước lớn (vài trăm KB) 45 Các loại cache 46 Disk cache
Mở rộng khái niệm cache: giúp CPU truy xuất các loại đĩa nhanh hơn
Dùng phần cứng: linh kiện nhớ trên các ổ đĩa cứng, CD
Dùng phần mềm: dùng một phần bộ nhớ trong làm disk cache 47 Tài liệu tham khảo
Modern Operating Systems – Second Edition A.S.Tanenbaum – Prentice Hall
Operating System Concepts – Sixth Edition A. Silberschatz, P.B. Galvin, G. Gagne John Wiley & Sons, Inc
Help and Support (Windows)
HỆ ðIỀU HÀNH Chương 2 CÁC VẤN ðỀ VỀ PROCESS VÀ THREAD 2Nội dung chương 2 I. Process II. Thread III. Truyền thơng giữa các process IV. ðiều phối 3I. Process 1. Mơ hình process 2. Hiện thực process 41. Mơ hình process a. Khái niệm process b. Tổ chức thứ bậc các process c. Các trạng thái của process 5a. Khái niệm process
Process là chương trình được thực thi: • ðược nạp vào bộ nhớ • Cĩ các thơng tin trạng thái: thanh ghi PC, các thanh ghi,
Mỗi process thực thi trên một CPU ảo
Hệ thống cĩ nhiều process đồng thời: • ða chương – 1 CPU • ða xử lý – nhiều CPU trên 1 máy • Phân bố – nhiều CPU trên nhiều máy 6Process trên bộ nhớ 7Ví dụ: hệ thống đa chương với 4 process a. ða chương với 4 chương trình b. Mơ hình 4 chương trình độc lập c. Chỉ cĩ 1 chương trình được thực thi tại 1 thời điểm 8b. Tổ chức thứ bậc các process
Tạo process mới: • Hệ điều hành tạo process mới • User yêu cầu tạo process mới • Process tạo process mới
Kết thúc process: • Bình thường • Lỗi • Do process khác kết thúc 9Tổ chức thứ bậc các process (tt)
Process tạo process mới: • Parent process • Child process
Hệ thống thứ bậc các process • UNIX: process group
Windows khơng cĩ tổ chức thứ bậc • Các process được tạo tương đương 10 c. Các trạng thái của process
Mơ hình 3 trạng thái
Chuyển trạng thái 11 Các trạng thái của process Mơ hình 5 trạng thái 12 Mơ hình 3 trạng thái 13 Các trạng thái
Thực thi – Running: • ðang thực thi (đang sử dụng CPU) • Chỉ cĩ 1 running process tại 1 thời điểm trên hệ thống đa chương
Sẵn sàng – Ready: • Sẵn sàng thực thi, tạm dừng chờ CPU • Cĩ nhiều ready process • ðược quản lý bằng ready queue
Bị chặn – Blocked: • Khơng thể thực thi cho đến khi cĩ biến cố xảy ra • Cĩ nhiều ready process • ðược quản lý bằng blocked queue 14 Chuyển trạng thái
Running  Blocked (1): chờ biến cố
Running  Ready (2): hết thời gian
Ready  Running (3): được thực thi
Blocked  Ready (4): biến cố xảy ra
Scheduler – Bộ điều phối của hệ điều hành thực hiện 15 Thời điểm chuyển trạng thái
Ngắt quãng thời gian – Clock Interrupt • Dùng để kiểm sốt thời gian
Ngắt quãng thiết bị – I/O Interrupt • Liên quan đến thiết bị I/O
Lệnh gọi hệ thống, lỗi – System call, trap • Khi gọi system calls, hay khi cĩ lỗi 16 Bộ điều phối (scheduler) 17 Ví dụ: chuyển trạng thái giữa P0 và P1 18 2. Hiện thực process
Hệ điều hành tổ chức và quản lý các bảng: • Bảng process – Process Table • Bảng bộ nhớ – Memory tables • Bảng File – File Tables • Bảng xuất nhập – I/O Tables
Cấu trúc các bảng phụ thuộc hệ điều hành
Process trên bộ nhớ ảnh process (process image) 19 Process và các loại tài nguyên 20 Cấu trúc tổng quát các bảng 21 Các thơng tin cơ bản quản lý process
Danh hiệu (ID)
Trạng thái bộ xử lý (processor state) • Thanh ghi PC, thanh ghi Flag • Các thanh ghi
Thơng tin điều khiển: • Trạng thái • Sử dụng tài nguyên (bộ nhớ, file, I/O) • Quyền truy xuất • 22 Ví dụ: Windows process 23 Ví dụ: Windows process và tài nguyên 24 II. Thread 1. Khái niệm thread 2. Hiện thực thread 25 1. Khái niệm thread
Process cĩ 2 đặc trưng: • ðơn vị sử dụng tài nguyên • ðơn vị được thực thi (theo một dịng điều khiển, cĩ thể xen kẽ giữa các process)
ðặc trưng thực thi của process được trừu tượng hố thành thread 26 Các mơ hình thread cơ bản
Một thread trong một process • ðơn luồng (single thread)
Nhiều thread trong một process • ða luồng (multithreaded) 27 ðơn luồng và đa luồng 28 Các đặc điểm của thread
Mỗi thread cĩ stack, cĩ trạng thái riêng
Việc chuyển trạng thái giữa các thread nhanh hơn giữa các process
Các thread trong process dùng chung tài nguyên
Các thread thực thi đồng thời trên các hệ thống SMP, siêu phân luồng, đa lõi
Giữa các thread khơng cĩ sự bảo vệ 29 Ví dụ: các trạng thái của Windows thread 30 Ví dụ: các trạng thái của Java thread 31 Các ứng dụng thread
Cơng việc dạng background, foreground
Các xử lý bất đồng bộ
Tăng tốc độ xử lý
Tạo tính cấu trúc cho chương trình 32 2. Hiện thực thread Các dạng hiện thực
Cấp user • Do các thư viện thread quản lý • Ví dụ: win32, java thread
Cấp kernel • Do kernel quản lý • Ví dụ: Windows 2K/XP, Linux
Tổ hợp user-kernel • Ví dụ: Solaris 33 Hiện thực thread cấp user 34 Hiện thực thread cấp kernel 35 III. Truyền thơng giữa các process 1. Các điều kiện dẫn đến tranh chấp 2. Loại trừ tương hỗ 3. Giải quyết loại trừ tương hỗ dùng vịng lặp 4. Semaphores 5. Vấn đề đồng bộ giữa các process 36 1. Các điều kiện dẫn đến tranh chấp
Các dạng tương tác giữa các process tồn tại đồng thời • Các process độc lập • Các process biết nhau gián tiếp (thơng qua tài nguyên dùng chung) • Các process biết nhau trực tiếp (các process thuộc về một phần mềm) 37 Xét ví dụ: 38 Xét ví dụ (tt)
Cĩ 2 process P0, P1
Mục đích: • P0: nhập X, xuất X • P1: nhập Y, xuất Y
Kết quả: • P0: nhập X, xuất Y • P1: nhập Y, xuất Y 39 ðiều kiện dẫn đến tranh chấp ðiều kiện:
Các process dùng chung tài nguyên
Thứ tự truy xuất ảnh hưởng kết quả ðịnh nghĩa:
Tài nguyên tranh chấp Critical resource
Vùng tranh chấp Critical region/Critical section 40 2. Loại trừ tương hỗ (mutual exclusion) a. Khái niệm b. Các yêu cầu c. Các phương pháp giải quyết 41 a. Khái niệm
Loại trừ tương hỗ: nguyên tắc giải quyết triệt để vấn đề tranh chấp tài nguyên giữa các process
Khi cĩ một process vào vùng tranh chấp thì tất cả các process khác phải ở ngồi vùng tranh chấp
Cĩ thể dẫn đến trạng thái deadlock hay trạng thái starvation 42 Cấu trúc một process while (TRUE) { enter_region(); // kiểm tra điều kiện critical_region(); // vùng tranh chấp leave_region(); // thơng báo trạng thái noncritcal_region();// vùng khơng tranh chấp } 43 Loại trừ tương hỗ giữa 2 process A, B 44 Trạng thái deadlock a. Process A giữ tài nguyên R b. Process B yêu cầu tài nguyên R c. Process C và D bị deadlock vì tài nguyên T và U 45 Trạng thái starvation
Trạng thái chờ mãi mãi của process
Ví dụ: • 3 process A, B, C dùng chung tài nguyên R • Tài nguyên R được cấp luân phiên cho process A và process B • Process C sẽ chờ mãi mãi 46 b. Các yêu cầu (1) Khơng cĩ 2 process đồng thời vào vùng tranh chấp (2) Khơng cĩ giả sử gì về tốc độ và số lượng process (3) Khơng cĩ process nào ở ngồi vùng tranh chấp cĩ thể ảnh hưởng đến process khác (4) Khơng cĩ process nào chờ mãi mãi 47 c. Các phương pháp giải quyết
Các process phải kiểm ra điều kiện trước khi vào vùng tranh chấp và thơng báo khi rời vùng tranh chấp
Nếu điều kiện khơng thoả thì chờ
Cĩ hai dạng chờ: • Chờ bằng vịng lặp (busy-waiting) Dùng phần mềm Phần cứng hỗ trợ • Chờ bằng trạng thái blocked Hệ điều hành hỗ trợ 48 3. Giải quyết loại trừ tương hỗ dùng vịng lặp a. Phần mềm giải quyết loại trừ tương hỗ b. Phần cứng hỗ trợ giải quyết loại trừ tương hỗ 49 a. Phần mềm giải quyết loại trừ tương hỗ
Giải thuật luân phiên nghiêm ngặt (Strict Alternation)
Giải thuật Peterson 50 Giải thuật luân phiên nghiêm ngặt
Giải quyết trường hợp 2 process (P0 và P1) và một tài nguyên
Hai process dùng một biến turn để xác định đến phiên process nào vào vùng tranh chấp
Khởi động turn = 0 51 Giải thuật luân phiên nghiêm ngặt (tt) P0 P1 while (TRUE) { while (TRUE) { while (turn != 0) ; while (turn != 1) ; critical_region(); critical_region(); turn = 1; turn = 0; noncritcal_region(); noncritical_region(); } } 52 Xét hoạt động P0 (tương tự cho P1)
Hoạt động P0 • P0 kiểm tra biến turn P0 vào vùng tranh chấp nếu turn = 0 P0 chờ khi turn = 1 • P0 gán turn = 1 khi rời vùng tranh chấp 53 Xét hoạt động P0 (tt)
Hoạt động P0 với P1 Giả sử P0 đến vịng while: • P1 ở ngồi vùng tranh chấp turn = 0: P0 vào vùng tranh chấp • P1 ở trong vùng tranh chấp turn = 1: P0 chờ • P1 cũng đến vịng while: Do biến turn dùng chung nên chỉ cĩ 1 process được vào vùng tranh chấp, process kia chờ tại vịng while 54 ðánh giá giải thuật luân phiên nghiêm ngặt
ðạt yêu cầu (1) và yêu cầu (4)
Giả sử P0 vào vùng tranh chấp 100 lần/đơn_vị thời_gian, P1 vào vùng tranh chấp 1 lần/đơn_ vị thời_gian: • Do luân phiên nghiêm ngặt nên P0 chỉ được vào vùng tranh chấp 1 lần/đơn vị thời gian • Khơng thoả yêu cầu (2)
Giả sử P1 cĩ lỗi ngồi vùng tranh chấp: • P0 dừng mãi mãi tại vịng while • Khơng thoả yêu cầu (3) 55 Giải thuật Peterson
Xét trường hợp 2 process (P0 và P1) và một tài nguyên
Hai process dùng chung: • biến turn: xác định đến phiên process nào vào vùng tranh chấp • Mảng boolean interested[2]: thể hiện process sẵn sàng vào vùng tranh chấp, interested[0]: P0 sẵn sàng vào vùng tranh chấp • Khởi động interested[0] = interested[1] = FALSE 56 Giải thuật Peterson (tt) #define FALSE 0 #define TRUE 1 #define N 2 // s process int turn; // đ n phiên process nào int interested[N]; // process sn sàng void enter_region(int process) { int other; // process cịn li other = 1 – process; interested[process] = TRUE;//th hin process sn sàng turn = process; // đt phiên while(turn == process && interested[other] == TRUE); } 57 Giải thuật Peterson (tt) void leave_region(int process) { interested[process] = FALSE; // rời vùng tranh chấp } P0 P1 while (TRUE) { while (TRUE) { enter_region(0) ; enter_region(1); critical_region(); critical_region(); leave_region(0); leave_region(1); noncritcal_region(); noncritical_region(); } } 58 b. Phần cứng hỗ trợ giải quyết loại trừ tương hỗ
Tập lệnh CPU cĩ các lệnh đặc biệt hỗ trợ
Ví dụ: • TEST SET LOCK (TSL) Kiểm tra và đặt giá trị cho một từ nhớ • SWAP ðổi giá trị hai từ nhớ • 59 Lệnh TSL
ðọc giá trị một từ nhớ vào một thanh ghi, sau đĩ ghi giá trị khác 0 (thường là 1) vào từ nhớ
Thao tác đọc và ghi nêu trên là trong cùng một lệnh • Thao tác đơn vị (atomic, primitive) 60 Ứng dụng lệnh TSL trong loại trừ tương hỗ
Giải quyết trường hợp n process
n process dùng chung một biến flag, khởi động flag = 0
Cấu trúc process Pi: while (TRUE) { enter_region(); // kiểm tra điều kiện critical_region(); // vùng tranh chấp leave_region(); // thơng báo trạng thái noncritcal_region();// vùng khơng tranh chấp } 61 Ứng dụng lệnh TSL (tt) enter_region: TSL register, FLAG; FLAG  register, FLAG = 1 CMP register,0; so sánh FLAG với 0 JNZ enter_region; FLAG=0, lặp RET; FLAG!=0, trở về leave_region: MOV FLAG, 0; Gán FLAG=0 RET; Trở về 62 Ví dụ: lệnh CPMXCHG (IA32)
Cú pháp: CMPXCHG DEST, SRC
Hoạt động: (accumulator: AL/AX/EAX) IF accumulator = DEST THEN ZF ← 1 DEST ← SRC ELSE ZF ← 0 accumulator ← DEST FI 63 4. Semaphores a. Khái niệm semaphore b. Ứng dụng semaphore xử lý loại trừ tương hỗ c. Ứng dụng semaphore trong đồng bộ giữa các process d. Khái niệm mutex 64 a. Khái niệm semaphore
Semaphore là kỹ thuật do hệ điều hành hỗ trợ: • Xử lý loại trừ tương hỗ • ðồng bộ giữa các process
Dùng để báo hiệu (signaling)
Khi process chờ báo hiệu thì vào trạng thái blocked, khơng chờ bằng vịng lặp 65 Semaphore
Semaphore là cấu trúc dữ liệu gồm: • Giá trị integer • Hàng đợi các process
Cĩ thể xem semaphore là giá trị integer với ba thao tác dạng primitive: • Khởi động giá trị - init( ); • Giảm giá trị - down( ) / wait( ) / P( ); • Tăng giá trị - up( ) / signal( ) / V( ); 66 Semaphore (tt)
Khởi động – init( ): • Semaphore nhận giá trị khơng âm
Giảm – down( ): • Giảm giá trị semaphore 1 đơn vị • Nếu semaphore âm thì process gọi thao tác down() sẽ bị blocked, và vào hàng đợi semaphore
Tăng – up( ): • Tăng giá trị semaphore 1 đơn vị • Nếu semaphore khơng dương thì cĩ 1 process trong hàng đợi semaphore được chuyển sang trạng thái ready 67 Semaphore (tt) struct semaphore { int count; queueType queue; } void down(semaphore s) { s.count--; if (s.count < 0) { đưa process vào s.queue; block process; } } void up(semaphore s) { s.count++; if (s.count <= 0) { lấy 1 process P ra khỏi s.queue; đưa process P vào read queue; } } 68 b.Ứng dụng semaphore xử lý loại trừ tương hỗ
Giải quyết trường hợp n process
n process dùng chung một semaphore s, khởi động s = 0
Cấu trúc process Pi: while (TRUE) { down(s); // kiểm tra điều kiện critical_region(); // vùng tranh chấp up(s); // thơng báo trạng thái noncritcal_region(); // vùng khơng tranh chấp } 69 c. Ứng dụng semaphore trong đồng bộ giữa các process
Bài tốn producer/consumer: • Hai process dùng chung một buffer kích thước hữu hạn • Một process ghi dữ liệu vào buffer: producer • Một process đọc dữ liệu từ buffer: consumer
Nhận xét: • Buffer cĩ dạng xoay vịng (circular buffer) • Nếu producer nhanh hơn: mất dữ liệu • Nếu consumer nhanh hơn: trùng dữ liệu 70 Buffer kích thước hữu hạn, xoay vịng 71 Giải bài tốn producer/consumer dùng semaphore #define N 100 // kích thước buffer typedef int semaphore // kiểu semaphore semaphore mutex = 1; // loại trừ tương hỗ semaphore empty = N; // số phần tử trống semaphore full = 0; // số phần tử cĩ dữ liệu 72 Giải bài tốn producer/consumer (tt) void producer(void) { int item; // phần tử dữ liệu while (TRUE) { produce_item(&item); // tạo dữ liệu down(&empty); // giảm số phần tử trống down(&mutex); // vào vùng tranh chấp enter_item(item); // ghi dữ liệu up(&mutex); // rời vùng tranh chấp up(&full); // tăng số phần tử cĩ dữ liệu } } 73 Giải bài tốn producer/consumer (tt) void consumer(void) { int item; // phần tử dữ liệu while (TRUE) { down(&full); // giảm số phần tử cĩ dữ liệu down(&mutex);// vào vùng tranh chấp remove_item(&item); // đọc dữ liệu up(&mutex); // rời vùng tranh chấp up(&empty); // tăng số phần tử trống consume_item(item); // xử lý dữ liệu } } 74 d. Khái niệm mutex
Giá trị semaphore cĩ thể: • Số nguyên  counting semaphore • 0, 1  binary semaphore
Binary semaphore được hiện thực đơn giản hơn, cịn gọi là biến mutex
Các thao tác trên mutex • mutex_lock( ), tương đương down ( ) • mutex_unlock( ), tương đương up ( ) 75 Mutex struct mutex { enum {zero, one} value; queueType queue; } void mutex_lock(mutex m) { if (m.value == 1) m.value = 0 else { đưa process vào s.queue; block process; } } void mutex_unlock(mutex m) { if (m.queue.is_empty()) m.value = 1; else { lấy 1 process P ra khỏi s.queue; đưa process P vào read queue; } } 76 Loại trừ tương hỗ dùng mutex while (TRUE) { mutex_lock(m); // kiểm tra điều kiện critical_region(); // vùng tranh chấp mutex_unlock(m); // thơng báo trạng thái noncritcal_region();// vùng khơng tranh chấp } 77 5. Vấn đề đồng bộ giữa các process Bài tốn Dining Philosophers
Cĩ 5 triết gia ngồi quanh 1 bàn trịn
Mỗi triết gia cĩ 1 đĩa thức ăn, khi ăn cần 2 nĩa 78 Bài tốn Dining Philosophers (tt)
Hoạt động của triết gia: luân phiên giữa suy nghĩ và ăn • Khi triết gia đĩi: cần nĩa trái và nĩa phải đồng thời, nếu cĩ 2 nĩa thì ăn • Sau khi ăn thì trả 2 nĩa, tiếp tục suy nghĩ
Nếu 5 triết gia đồng thời cầm nĩa trái, chờ nĩa phải: deadlock
Nếu 5 triết gia đồng thời trả nĩa trái, suy nghĩ, đồng thời cầm nĩa phải: starvation 79 IV. ðiều phối 1. Khái niệm 2. Các phương pháp điều phối 3. Ví dụ 4. ðiều phối thread 80 1. Khái niệm
ðiều phối (scheduling): • Xác định thời điểm và • Chọn process được thực thi
Do bộ điều phối (scheduler) thực hiện
Các dạng điều phối trên hệ thống đa chương: • Thời gian dài: liên quan việc tạo process mới • Thời gian trung bình: liên quan việc đưa process và, ra bộ nhớ • Thời gian ngắn: chọn ready process để cho thực thi 81 Các chiến lược điều phối
Khơng dừng process đang thực thi • Nonpremptive scheduling • Khơng thích hợp với hệ thống cĩ tương tác (interactive system)
Dừng process đang thực thi • Premptive scheduling 82 Các dạng hàng đợi và điều phối process 83 Các dạng process khi điều phối a. Chủ yếu sử dụng CPU – Processor-bound process b. Chủ yếu thực hiện I/O – I/O-bound process 84 2. Các phương pháp điều phối thời gian ngắn a. ðộ ưu tiên (Priorities) b. First-In-First-Out (FIFO) c. Round Robin (RR) d. Shortest Job First (SJF) e. Shortest Remaining Time (SRT) f. Multi-level Feedback Queues (MFQ) 85 a. ðộ ưu tiên
Mỗi process cĩ độ ưu tiên
Process cĩ độ ưu tiên cao nhất được cho thực thi: • Khơng kể process mới  nonpreemptive • Kể cả process mới  preemptive
Process cĩ độ ưu tiên thấp cĩ thể chờ mãi mãi (starvation): • Tăng độ ưu tiên của process chờ theo thời gian (aging) 86 b. First-In-First-Out (FIFO)
Dạng nonpreemptive • Cịn gọi là First-Come-First-Serve (FCFS)
Các process được thực thi theo thứ tự xuất hiện tại hàng đợi ready RQ CPU 87 c. Round Robin (RR)
Dạng preemptive
Mỗi process được thực thi trong một đơn vị thời gian q (quantum)
Nếu process chưa kết thúc trong thời gian q thì bị dừng, đưa về cuối hàng đợi ready
Process đang ở đầu của hàng đợi được chọn để thực thi (theo FIFO) CPURQ 88 Round Robin (tt)
Nếu q đủ lớn: trở thành FIFO
Nếu q nhỏ: chi phí chuyển trạng thái là đáng kể 89 d. Shortest Job First (SJF)
Dạng nonpreemptive
Cần biết trước thời gian thực thi của các process
Process cĩ thời gian thực thi ngắn nhất được cho thực thi
Giảm thời gian chờ trung bình của các process vì process ngắn chờ ít 90 e. Shortest Remaining Time (SRT)
Dạng preemptive
Process cĩ thời gian thực thi đến kết thúc (remaining time) nhỏ nhất được cho thực thi, kể cả process mới
Cần nhiều chi phí chuyển trạng thái Process cĩ thời gian thực thi lớn phải chờ lâu 91 f. Multi-level Feedback Queues (MFQ)
Dạng preemptive
Cĩ n hàng đợi RQ0..RQn-1 • RQ0..RQn-1 : theo FIFO • RQn-1: theo Round Robin
Về độ ưu tiên RQi > Rqi+1
Về thời gian tqi < tqi+1 92 MFQ (tt) RQ0 RQ1 RQn-1 tq0 tq1 tqn-1 Round Robin FIFO FIFO 93 Xét hoạt động của process P
Vào hệ thống tại cuối RQ0
P được thực thi khi tiến đến đầu RQ0
Nếu P chưa kết thúc trong tq0, P bị dừng và vào cuối tq1
P sẽ được thực thi nếu: • P tiến đến đầu tq1 • tq0 rỗng
Cứ tiếp tục như vậy cho đến khi P vào RQn-1, hoạt động theo round robin 94 Nhận xét
Tự động phát hiện bản chất process: • Ưu tiên cho process cĩ thời gian ngắn
Giả sử P cĩ yêu cầu I/O, P rời hệ thống tại RQi. Khi P trở lại hệ thống: • Nếu vào cuối RQ0  Ưu tiên cho process dạng I/O-bound • Nếu vào cuối RQi  Ưu tiên cho process dạng processor-bound 95 3. Ví dụ 28P5 56P4 44P3 62P2 30P1 Thời gian thực thi Thời điểm xuất hiện Process 96 Qui ước
Cách biểu diễn hàng đợi
Trong phương pháp round robin: • Nếu cĩ process mới đưa vào cuối hàng đợi đồng thời với process hết thời gian thì ưu tiên cho process mới P5 P4 P3 5,4,3 RQ 97 FIFO 0 5 10 15 20 P1 P2 P3 P4 P5 2 3 4,3 5,4,3 5,4 5 P1 P2 P3 P4 P5 98 Round Robin q=4 0 5 10 15 20 P1 P2 P3 P4 P5 2 3 4,3 2,4 5,2,4 5,2 4,5 4 P1 P2 P2P3 P4 P4P5 99 SJF 0 5 10 15 20 P1 P2 P3 P4 P5 2 3 4,3 5,4,3 4,3 4 P1 P2 P5 P3 P4 100 SRT 0 5 10 15 20 P1 P2 P3 P4 P5 P1 cịn 1 P2 cịn 6 P2 cịn 5 P3 cịn 4 P2 cịn 5 P3 cịn 2 P4 cịn 5 P2 cịn 5 P4 cịn 5 P5 cịn 2 P1 P2P2 P3 P4P5 101 4. ðiều phối thread
Khi các process cĩ nhiều thread  cần hai cấp điều phối: process, thread
Phụ thuộc dạng hiện thực thread: • Cấp user (user-level) • Cấp kernel (kernel-level) • Dạng tổ hợp 102 Ví dụ: điều phối thread dạng user-level Mỗi process được thực thi trong 50 milisec Mỗi thread được thực thi trong 5 milisec 103 Ví dụ: điều phối thread dạng kernel-level Mỗi process được thực thi trong 50 milisec Mỗi thread được thực thi trong 5 milisec HỆ ðIỀU HÀNH Chương 3 DEADLOCK 2Nội dung chương 3 I. Các khái niệm II. Phát hiện và phục hồi từ deadlock III. Ngăn chặn deadlock IV. Tránh deadlock 3I. Các khái niệm
Deadlock là trạng thái hệ thống: • Tập hợp các process bị chờ mãi mãi • Mỗi process chờ biến cố chỉ cĩ được từ một process khác trong tập hợp
Nguyên nhân tạo deadlock: • Các process cĩ dùng chung tài nguyên • Các process cĩ truyền thơng 4Ví dụ
Hệ thống cĩ 2 ổ đĩa: • Mỗi process P0, P1 giữa một ổ đĩa và chờ ổ đĩa kia
Semaphore A và semaphore B khởi động là 1: P0 P1 down(A); down(B); down(B); down(A); 5Các dạng tài nguyên
Cĩ thể lấy lại từ process • Preemptable resources, ví dụ: CPU, bộ nhớ
Khơng lấy lại từ process • Nonpreemptable resources, ví dụ: máy in
Các bước sử dụng tài nguyên • Process yêu cầu tài nguyên • Nếu được cấp phát thì sử dụng (process giữ tài nguyên), nếu khơng thì chờ • Process trả lại tài nguyên 6Các điều kiện dẫn đến deadlock
Loại trừ tương hỗ (mutual exclusion) • Chỉ 1 process được sử dụng tài nguyên chung tại một thời điểm • Tài nguyên hoặc được dùng bởi 1 process hoặc chưa cấp phát
Giữ và chờ tài nguyên (hold and wait) • Process đang giữ tài nguyên được quyền yêu cầu thêm tài nguyên khác
Khơng lấy lại tài nguyên (no preemption) • Khơng lấy lại tài nguyên đã cấp cho process
Tồn tại vịng chờ các process (circular wait) • Các process tạo thành một vịng chờ 7Các chiến lược giải quyết deadlock
Khơng giải quyết • Giải thuật đà điểu (ostrich algorithm)
Phát hiện, phục hồi (detection, recovery)
Ngăn chặn (prevention) • Loại bỏ các điều kiện tạo deadlock
Tránh (avoidance) • Chấp nhận các điều kiện tạo deadlock, theo dõi và kiểm sốt 8Giải thuật đà điểu
Coi như khơng cĩ vấn đề deadlock
Dựa trên cơ sở: • Deadlock rất ít xảy ra • Chi phí giải quyết rất cao
ðược dùng trên các hệ điều hành: • UNIX • Windows 9II. Phát hiện và phục hồi từ deadlock
Phát hiện deadlock: • Dùng các giải thuật phát hiện vịng chờ các process • Do người quản trị hệ thống
Phục hồi từ deadlock: • Kết thúc các process bị deadlock • Lấy lại tài nguyên từ process • Phục hồi các điểm kiểm tra 10 Kết thúc các process bị deadlock
Kết thúc tất cả các process bị deadlock
Lần lượt kết thúc các process bị deadlock cho đến khi hết deadlock
Thơng số chọn process để kết thúc: • ðộ ưu tiên • Thời gian đã thực thi • Thời gian cịn lại • Số tài nguyên đã cấp phát • Số tài nguyên đang chờ 11 Lấy lại tài nguyên từ process
Lần lượt lấy lại tài nguyên đã cấp phát cho các process cho đến khi hết deadlock • Phụ thuộc bản chất của tài nguyên • Sử dụng cơng cụ của hệ điều hành 12 Phục hồi các điểm kiểm tra
ðịnh kỳ tạo các điểm kiểm tra (checkpoint) • Lưu trạng thái hệ thống tại điểm kiểm tra
Thực hiện lại (rollback) các process bị deadlock tại các điểm kiểm tra
Lần lượt thực hiện lại các process bị deadlock tại các điểm kiểm tra cho đến khi hết deadlock 13 III. Ngăn chặn deadlock
Loại bỏ các điều kiện dẫn đến deadlock
Các điều kiện xem như khơng thể loại bỏ: • Loại trừ tương hỗ • Khơng lấy lại tài nguyên từ process 14 Loại bỏ điều kiện loại trừ tương hỗ
Giảm số tài nguyên tranh chấp • Tăng số lượng tài nguyên
Cấp phát tài nguyên dạng spool • Ví dụ: chỉ 1 printer daemon dùng máy in • Các process gởi yêu cầu cho printer daemon 15 Loại bỏ điều kiện giữ và chờ tài nguyên
Nguyên tắc: process khơng được giữ tài nguyên khi yêu cầu tài nguyên mới • Process khai báo tài nguyên và được cấp phát 1 lần • Nếu process yêu cầu tài nguyên và khơng dược cấp phát thì phải trả các tài nguyên đang giữ 16 Loại bỏ điều kiện khơng lấy lại tài nguyên
Lấy lại tài nguyên từ process
Khơng thể với tài nguyên như máy in 17 Loại bỏ vịng chờ các process
Cĩ thể quy định số thứ tự tài nguyên • Process chỉ được yêu cầu tài nguyên theo thứ tự tăng
Giả sử cĩ deadlock: • P1 giữ Ri, chờ Rj  i < j • P2 giữ Rj, chờ Ri  j < i 18 IV. Tránh deadlock
Chấp nhận các điều kiện tạo deadlock
Theo dõi và tránh dẫn đến deadlock
Hai hướng giải quyết: • Khơng tạo process mới nếu cĩ thể dẫn đến deadlock • Khơng cấp phát thêm tài nguyên cho process nếu cĩ thể dẫn đến deadlock 19 a. Khơng tạo process mới
Process cần khai báo số lượng tài nguyên cần sử dụng
Khơng tạo process mới nếu số lượng tài nguyên hệ thống khơng đủ, cĩ thể dẫn đến deadlock 20 b. Khơng cấp phát thêm tài nguyên cho process
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process
ðịnh nghĩa trạng thái hệ thống với: • Vector E: tổng số các loại tài nguyên • Vector A: số tài nguyên mỗi loại chưa dùng • Ma trận C: số tài nguyên đã cấp phát cho các process • Ma trận R: số lượng tài nguyên các process sẽ tiếp tục yêu cầu 21 Hệ thống với n process và m loại tài nguyên 22 Ví dụ 23 Các điều kiện về định lượng
Tài nguyên hoặc đã cấp phát hoặc chưa sử dụng
Khơng cĩ process nào yêu cầu nhiều hơn số tài nguyên hệ thống
Khơng cĩ process nào được cấp phát nhiều hơn số lượng yêu cầu 24 Giải thuật ngân hàng / nhà băng
Trạng thái hệ thống (state): • Giá trị vector E, A và ma trận C, E
Trạng thái an tồn (safe state): • Tồn tại một thứ tự thực thi đến kết thúc tất cả các process
Trạng thái khơng an tồn (unsafe state): • Khơng phải là trạng thái an tồn 25 Giải thuật ngân hàng (tt)
Khi cĩ process yêu cầu thêm tài nguyên thì chỉ cấp phát nếu trạng thái hệ thống sau cấp phát là an tồn 1) Tìm một dịng trên ma trận R nhỏ hơn hay bằng A. Nếu khơng cĩ dịng nào như vậy thì hệ thống sẽ dẫn đến deadlock 2) Giả sử process tương ứng với dịng đã chọn kết thúc, thêm các tài nguyên của process này đang giữ vào A 3) Lập lại bước 1 và 2 cho đến khi mọi process kết thúc, trạng thái là an tồn. Nếu khơng thì trạng thái khơng an tồn 26 Nhận xét về giải thuật ngân hàng
Tốt về lý thuyết
Khĩ cài đặt thực tế: • Khĩ xác định yêu cầu về tài nguyên của process • Số lượng process thay đổi • Số lượng tài nguyên thay đổi • Chi phí lớn HỆ ðIỀU HÀNH Chương 4 QUẢN LÝ BỘ NHỚ 2Nội dung chương 4 I. Các khái niệm II. Quản lý bộ nhớ thực III. Quản lý bộ nhớ ảo 3I. Các khái niệm 1. Tổ chức thứ bậc của bộ nhớ 2. ðịa chỉ ơ nhớ 3. Quản lý bộ nhớ 4. Liên kết động 41. Tổ chức thứ bậc của bộ nhớ
Chương trình phải được nạp vào bộ nhớ để thực thi
Tổ chức bộ nhớ: • Các thanh ghi (registers) • Thời gian truy xuất theo chu kỳ (CPU clock) • Cache • Giúp CPU truy xuất bộ nhớ nhanh hơn • Bộ nhớ trong • Thời gian truy xuất nhiều chu kỳ • Bộ nhớ ngồi • ðĩa từ, CD, • Băng từ, 52. ðịa chỉ ơ nhớ
Process cần địa chỉ của lệnh và dữ liệu trên bộ nhớ
Thời điểm tạo địa chỉ: • Khi dịch chương trình • Khi nạp chương trình • Khi thực thi chương trình 6ðịa chỉ lệnh và dữ liệu 7Các bước xử lý chương trình ứng dụng 8ðịa chỉ luận lý, địa chỉ vật lý
ðịa chỉ luận lý (logical address): • Liên kết với một khơng gian địa chỉ vật lý riêng biệt • Do CPU tạo ra
ðịa chỉ vật lý (physical address): • Liên kết với bộ nhớ vật lý • ðược đơn vị quản lý bộ nhớ sử dụng
Chương trình của user chỉ dùng địa chỉ luận lý 93. Quản lý bộ nhớ
Khối quản lý bộ nhớ của hệ điều hành: • Cấp phát/thu hồi bộ nhớ đối với process • Quản lý việc sử dụng bộ nhớ
ðơn vị quản lý bộ nhớ (MMU, Memory Management Unit) của CPU: • Các mơ hình bộ nhớ • Hỗ trợ chuyển đổi địa chỉ 10 Các mơ hình bộ nhớ
Bộ nhớ thực • Khơng sử dụng bộ nhớ ngồi • Cĩ sử dụng bộ nhớ ngồi
Bộ nhớ ảo (virtual memory) 11 4. Liên kết động
Dynamic loading • Chỉ nạp thủ tục.hàm khi được gọi • Phù hợp với các chương trình lớn • Khơng cần hỗ trợ của hệ điều hành
Dynamic linking – Liên kết động • Chỉ liên kết trong thời gian thực thi • Hệ điều hành cần quản lý hàm/thủ tục trong khơng gian địa chỉ của process • Phù hợp với thư viện  shared libraries 12 II. Quản lý bộ nhớ thực 1. Dạng đơn chương 2. Dạng đa chương kích thước đoạn cố định 3. Dạng đa chương kích thước đoạn khơng cố định 13 1. Dạng đơn chương
Cĩ 1 chương trình ứng dụng trên bộ nhớ
Hệ điều hành nạp chương trình vào vùng nhớ xác định
Khi chương trình kết thúc, hệ điều hành nạp chương trình khác thay thế
Ví dụ: DOS 14 Hệ điều hành và một chương trình ứng dụng 15 16 2. Dạng đa chương kích thước đoạn cố định
Bộ nhớ được chia thành các vùng (partition) kích thước cố định, khơng cần bằng nhau
Cĩ nhiều process trên bộ nhớ đồng thời • Cĩ thể đưa process ra bộ nhớ ngồi (swapping)
Kích thước các vùng nhớ cố định  cĩ sự phân mảnh bên trong (internal fragmentation) 17 Ví dụ: a. Dùng nhiều hàng đợi b. Dùng 1 hàng đợi 18 Swapping 19 ðịnh vị lại (relocation), bảo vệ (protection)
Process cĩ thể nạp vào vùng nhớ kích thước phù hợp
Cĩ thể dùng địa chỉ dạng base+offset • Cần định vị lại khi nạp process vào vùng nhớ khác
Bảo vệ bộ nhớ bằng cách dùng giới hạn kích thước vùng nhớ (limit) • Nếu process cĩ quyền dùng địa chỉ tuyệt đối thì khơng thể bảo vệ bộ nhớ 20 Base và limit 21 3. Dạng đa chương kích thước đoạn khơng cố định
Các process được cấp phát vùng nhớ bằng với kích thước process • Cĩ nhiều process đồng thời trên bộ nhớ • Cĩ thể đưa process ra bộ nhớ ngồi
Khơng cịn phân mảnh bên trong
Sau một thời gian hoạt động sẽ cĩ phân mảnh bên ngồi (external fragmentation) do kích thước process khác nhau 22 Ví dụ Các process được nạp và bị xĩa trên bộ nhớ 23 Giải quyết phân mảnh bên ngồi
ðịnh kỳ dùng chương trình thu gom các khoảng trống (hole) đưa về một phía của bộ nhớ • Memory compaction, garbage collection 24 Quản lý tình trạng bộ nhớ
Quản lý vùng nhớ đã cấp phát (partition), vùng nhớ trống (hole)
Hai kỹ thuật: • Dùng bit-map • Dùng danh sách liên kết 25 Ví dụ a. 5 process và 3 khoảng trống b. Bit-map c. Danh sách liên kết 26 Nạp process vào bộ nhớ
Hệ điều hành chọn khoảng trống phù hợp để nạp process vào bộ nhớ • Các phương pháp chính: First-Fit, Next-Fit, Best-Fit
First-Fit • Tìm từ vị trí đầu bộ nhớ • Chọn khoảng trống đầu tiên đạt yêu cầu • Nhanh nhất 27 Nạp process vào bộ nhớ (tt)
Next-Fit • Tìm từ vị trí lần cấp phát trước • Chọn khoảng trống tiếp theo đạt yêu cầu • Cần lưu vị trí cấp phát
Best-Fit • Tìm trên tồn bộ nhớ • Chọn khoảng trống nhỏ nhất đạt yêu cầu • Chậm nhất 28 Ví dụ: process mới kích thước 16M 29 III. Quản lý bộ nhớ ảo 1. Khái niệm bộ nhớ ảo 2. Bộ nhớ ảo dạng phân trang 3. Bộ nhớ ảo dạng phân đoạn 4. Bộ nhớ ảo dạng phân đoạn cĩ phân trang 30 1. Khái niệm bộ nhớ ảo
Bộ nhớ ảo (virtual memory) là kỹ thuật do hệ điều hành thực hiện với hỗ trợ của phần cứng • Phân biệt địa chỉ luận lý (địa chỉ ảo) và địa chỉ vật lý
Chương trình được viết trên khơng gian địa chỉ ảo, là thơng số của CPU và hệ điều hành • CPU IA32: 246 bytes, Windows: 232 bytes
Khi thực thi: hệ điều hành nạp chương trình vào bộ nhớ, chuyển đổi địa chỉ ảo thành địa chỉ vật lý, thực thi trên bộ nhớ vật lý 31 Các đặc điểm của bộ nhớ ảo
Khơng gian địa chỉ ảo >> khơng gian địa chỉ vật lý • Chương trình cĩ thể lớn hơn bộ nhớ • Phù hợp với hệ thống đa chương
Chỉ cần phần đang thực thi của process nạp vào bộ nhớ • Phần cịn lại đặt trên đĩa
Cho phép dùng chung khơng gian địa chỉ giữa các process • Hỗ trợ liên kết động 32 Thư viện dùng chung sử dụng bộ nhớ ảo 33 Các dạng bộ nhớ ảo
Bộ nhớ ảo dạng phân trang (paging)
Bộ nhớ ảo dạng phân đoạn (segmentation)
Bộ nhớ ảo dạng phân đoạn cĩ phân trang (paged segmentation / segmentation with paging) 34 2. Bộ nhớ ảo dạng phân trang a. Tổ chức phân trang b. Bảng trang c. Chuyển đổi địa chỉ d. Nạp trang e. Thay thế trang 35 a. Tổ chức phân trang
Khơng gian địa chỉ ảo chia thành các trang (page) • Kích thước vài KB, vài MB
Khơng gian địa chỉ vật lý bao gồm các khung trang (page frame/ frame) • Kích thước khung trang = kích thước trang • Các trang của một process khơng cần ở trên các khung trang liên tục
Cĩ bảng trang (page table) quản lý các trang • Mỗi process cĩ một bảng trang 36 Bảng trang
Cĩ N dịng, với N là số trang  mỗi dịng tương ứng với 1 trang
Cấu trúc 1 dịng: • Control bits: các bit điều khiển • Valid bit/Present bit
Valid = 0 nếu trang chưa cĩ trên bộ nhớ
Valid = 1 nếu trang đang cĩ trên bộ nhớ • Frame Number (Frame #)
Số thứ tự khung trang đang chứa trang 37 Ví dụ Bộ nhớ ảo cĩ 8 trang, bộ nhớ vật lý cĩ 4 khung Bảng trang cĩ 8 phần tử 38 Các bit điều khiển
Bit R (referenced) • R=1 nếu trang cĩ được truy xuất trên bộ nhớ
Bit M (modified) • M=1 nếu trang cĩ được ghi trên bộ nhớ
39 b. Bảng trang
Bảng trang cĩ kích thước lớn • Mỗi phần tử tương ứng một trang • Mỗi process cần 1 bảng trang
Giải quyết: • Bảng trang nhiều cấp, ví dụ: IA32 • Bảng trang nghịch đảo (Inverted Page Table), ví dụ: PowerPC, IA64
Bảng trang luơn được truy xuất • Cache các phần tử trong CPU Ví dụ bảng trang 2 cấp Khơng gian địa chỉ ảo 32 bit Dùng 1 bảng trang cấp 1 và 210 bảng trang cấp 2 Process 12M chỉ cần 1 bảng trang cấp 1 và 3 bảng trang cấp 2 41 Ví dụ bảng trang 2 cấp (tt) 42 Bảng trang nghịch đảo
Số phần tử bằng số khung trang • Chỉ cần 1 bảng trên hệ thống • Vị trí trong bảng là frame number
Mỗi phần tử bao gồm: • Số thứ tự trang tương ứng • Thơng tin về process sở hữu trang (pid)
Truy xuất theo cơ chế hash • Cĩ chuỗi liên kết (chain) giải quyết trường hợp cĩ nhiều trang cùng số thứ tự trên bộ nhớ 43 Bảng trang nghịch đảo (tt) 44 c. Chuyển đổi địa chỉ
ðịa chỉ ảo theo phân trang • Page Number: số thứ tự trang • Offset/Displacement: địa chỉ trong trang
ðịa chỉ vật lý • Page Number: số thứ tự khung trang • Offset/Displacement: địa chỉ trong khung trang OffsetPage Number OffsetFrame Number 45 Sơ đồ chuyển đổi địa chỉ 46 Truy xuất theo địa chỉ ảo
Tách page # và offset từ địa chỉ ảo
Chuyển page # thành frame # bằng cách truy xuất bảng trang A. Tìm phần tử quản lý trang B. Kiểm tra valid bit 1. Valid = 1 a. Thay page # bằng frame # b. Truy xuất dữ liệu trên khung với vị trí offset 47 Truy xuất theo địa chỉ ảo (tt) 2. Valid = 0  lỗi trang a. Tìm trang trên đĩa b. Tìm một khung trống (cĩ thể phải thay thế trang nếu các khung đầy) c. Sao chép trang vào khung trống d. Cập nhật bảng trang (valid = 1, frame # mới) e. Thực hiện truy xuất như bước 1 48 Phần cứng hỗ trợ chuyển đổi địa chỉ ảo
TLB (Translation Look-aside Buffer) • Ở trong CPU • Cache các phần tử trên bảng trang
Khi chuyển đổi địa chỉ, tìm phần tử quản lý trang trên TLB trước, nếu khơng cĩ thì tìm trên bảng trang 49 Sơ đồ chuyển đổi địa chỉ với TLB 50 Xử lý lỗi trang 51 d. Nạp trang
Nạp theo yêu cầu (demand paging) • Nạp trang khi cĩ lỗi trang
Nạp trước(prepaging) • Nạp trước các trang của process theo một điều kiện xác định 52 Nạp trang trên Windows XP
Nạp trang theo yêu cầu với clustering • Nạp các trang xung quanh trang cĩ lỗi
Các process cĩ thơng số • Working set minimum: số trang tối thiểu được cĩ trên bộ nhớ • Working set maximum: số trang tối đa được cĩ trên bộ nhớ
Khi bộ nhớ khơng đủ thì đưa các trang của các process ra đĩa theo cơ chế automatic working set trimming 53 e. 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ì phải đưa ra đĩa
Cĩ các phương pháp chọn phần tử thay thế: Optimal, FIFO, LRU (thơng dụng), Second Chance, Clock 54 Các phương pháp thay thế trang
Optimal • Chọn trang sẽ khơng được truy xuất khoảng thời gian xa nhất • Khơng hiện thực được • Dùng để đánh giá các phương pháp khác
FIFO • Chọn trang nạp vào bộ nhớ đầu tiên • Dùng hàng đợi quản lý số thứ tự trang: • Khi nạp trang: đưa vào cuối hàng đợi • Khi thay thế: chọn trang tại đầu hàng đợi 55 Các phương pháp thay thế trang (tt)
LRU (Least Recently Used) • Chọn trang đã khơng được truy xuất trong khoảng thời gian lớn nhất • Hiện thực: • Dùng hàng đợi: khi cĩ truy xuất trang thì đưa trang về cuối hàng đợi (tương đương trang mới) • Dùng thêm một biến counter, lưu thời điểm truy xuất. Khi thay thế chọn trang cĩ counter nhỏ nhất 56 Các phương pháp thay thế trang (tt)
Second Chance • Cải tiến FIFO • Khi cần thay thế, xét trang tại vị trí đầu hàng đợi: • Nếu bit R = 0 thì thay thế trang • Nếu bit R = 1 thì đưa trang về cuối hàng đợi, xét trang tiếp theo cho đến trang cho R=0 57 Các phương pháp thay thế trang (tt)
Clock • Tương tự Second Chance • Các trang được quản lý theo danh sách liên kết xoay vịng • Cĩ 1 con trỏ chỉ đến trang đầu tiên • Khi cần thay thế thì xét trang tại vị trí con trỏ: • Nếu bit R = 0 thì đưa thay thế trang, xoay con trỏ 1 đơn vị • Nếu bit R = 1 thì xĩa R = 0, xoay con trỏ 1 đơn vị, xét trang tiếp theo cho đến trang cho R=0 58 Ví dụ các phương pháp thay thế trang
Bộ nhớ cĩ 3 khung trang rỗng
Các trang được truy xuất theo thứ tự: 2 3 2 1 5 2 4 5 3 2 5 2 59 Sơ đồ các trang trên các khung trang 333344111 5*5*555*555333 2*2*2*22*2*2*22*2*22CLOCK 2*22444111 55*555*555333 3333222*222*22LRU 244444111 552*22223333 33335*55522*22FIFO 55*555*5551 3333*3333333 2*224442*222*22OPT 252354251232 60 3. Bộ nhớ ảo dạng phân đoạn Tổ chức phân đoạn
Bộ nhớ ảo bao gồm các đoạn (segment) cĩ kích thướ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 61 Nhận xét về phân trang, phân đoạn
Trang trong suốt đối với người lập trình
Phân trang tránh được phân mảnh bên ngồi
Người lập trình sử dụng được đoạn
Phân đoạn phù hợp với lập trình theo khối, cấu trúc dữ liệu thay đổi, dùng chung và bảo vệ bộ nhớ 62 4. Bộ nhớ ảo dạng phân đoạn cĩ phân trang Kết hợp các ưu điểm của phân đoạn và phân trang Tổ chức:
Bộ nhớ ảo bao gồm các đoạn
Trong mỗi đoạn thực hiện phân trang 63 Ví dụ: bộ nhớ ảo trên Pentium
ðơn vị quản lý bộ nhớ (Memory Management Unit, MMU) • ðơn vị phân đoạn, (đoạn đến 232 bytes) • ðơn vị phân trang
Các mơ hình bộ nhớ • Khơng phân đoạn, khơng phân trang • Khơng phân đoạn, cĩ phân trang • Cĩ phân đoạn, khơng phân trang • Cĩ phân đoạn, cĩ phân trang 64 Chuyển đổi địa chỉ
ðịa chỉ ảo dạng phân đoạn: • Selector – 16 bit • Offset – 32 bit ðịa chỉ tuyến tính (linear address) ðịa chỉ vật lý 65 Cấu trúc selector GDT (Global Descriptor Table): dùng cho HDH LDT (Local Descriptor Table): dùng cho các chương trình Privilege level: mức đặc quyền 66 Chuyển đổi địa chỉ đoạn địa chỉ tuyến tính 67 Chuyển đổi địa chỉ tuyến tính địa chỉ vật lý 68 Ứng dụng mức đặc quyền HỆ ðIỀU HÀNH Chương 5 QUẢN LÝ XUẤT NHẬP 2Nội dung chương 5 I. Nguyên lý phần cứng xuất nhập II. Tổ chức phần mềm xuất nhập III. ðĩa từ IV. Clock 3I. Nguyên lý phần cứng xuất nhập 1. Thiết bị xuất nhập (I/O devices) 2. Mạch điều khiển (controller) 3. ðịa chỉ thiết bị I/O 4. Interrupt 5. DMA (Direct Memory Access) 41. Thiết bị xuất nhập • Block devices – Thiết bị dạng khối • Thơng tin lưu theo khối, khối cĩ địa chỉ • ðọc ghi theo từng khối độc lập • Ví dụ: đĩa từ • Character devices – Thiết bị dạng ký tự • Thơng tin truyền theo chuỗi ký tự • Khơng cĩ địa chỉ • Ví dụ: bàn phím, card mạng, chuột, • Abstract devices - Các thiết bị trừu tượng • Khơng là hai dạng trên • Ví dụ: file system, clock 5Tốc độ tiêu biểu của các thiết bị I/O 62. Mạch điều khiển (controller)
Thiết bị I/O gồm cĩ: • Thành phần cơ khí • Thành phần điện
Thành phần điện  mạch điều khiển • Cĩ thể điều khiển nhiều thiết bị
Nhiệm vụ mạch điều khiển: • Chuyển đổi dữ liệu (bits, streams, blocks) • Kiểm sốt lỗi (nếu cần thiết) • Tồn tại trong kiến trúc hệ thống 7Mạch điều khiển (tt)
Mạch điều khiển kết nối với I/O bus
Thiết bị nối với mạch điều khiển
Thơng số: • ðịa chỉ (theo phương pháp xuất nhập) • Tập lệnh điều khiển
Phần mềm điều khiển thiết bị thơng qua mạch điều khiển với tập lệnh • Ví dụ: FDC Floppy Disk Controller cĩ các lệnh SEEK, READ, WRITE, FORMAT, 83. ðịa chỉ thiết bị I/O
Memory mapped I/O • Thiết bị và bộ nhớ dùng chung một khơng gian địa chỉ • Xuất nhập tương đương đọc ghi bộ nhớ • Khơng cần lệnh I/O
Isolated I/O • Dùng khơng gian địa chỉ riêng • Cần tín hiệu điều khiển I/O riêng • Cần các lệnh I/O 9ðịa chỉ I/O (tt) a. ðịa chỉ bộ nhớ và địa chỉ I/O phân biệt b. Memory-mapped I/O c. Dạng tổ hợp (hybrid) 10 4. Interrupt
Cần interrupt controller và interrupt handler
CPU yêu cầu xuất nhập
Thiết bị yêu cầu ngắt quãng (interrupt) khi sẵn sàng
Thực thi chương trình xử lý ngắt
Thơng số thiết bị: • ðịa chỉ I/O • Yêu cầu ngắt (IRQ i) 11 Ví dụ 12 5. DMA
Cần cĩ DMA controller
CPU gởi yêu cầu xuất nhập cho DMAC
DMAC thực hiện trao đổi dữ liệu giữa bộ nhớ và thiết bị
Khi kết thúc, DMAC gởi tín hiệu ngắt quãng cho CPU
Thơng số thiết bị: • ðịa chỉ I/O • Yêu cầu ngắt (IRQ i) • Kênh DMA (DMA channel) 13 Ví dụ 14 II. Tổ chức phần mềm xuất nhập PHẦN CỨNG XỬ LÝ NGẮT QUÃNG CHƯƠNG TRÌNH ðiỀU KHIỂN THIẾT BỊ (Device Driver) PHẦN MỀM I/O CẤP HỆ ðIỀU HÀNH PHẦN MỀM I/O CẤP USER 15 Xử lý ngắt quãng
Process yêu cầu I/O bị blocked cho đến khi cĩ ngắt quãng
Chương trình xử lý ngắt quãng thực thi, chuyển blocked process sang trạng thái ready 16 Chương trình điều khiển thiết bị
Device driver chứa đoạn mã phụ thuộc từng loại thiết bị
Device driver trao đổi dữ liệu với các thanh ghi trên mạch điều khiển, kiểm tra trạng thái thiết bị
Ví dụ: Windows driver • Universal driver • Minidriver 17 Phần mềm I/O cấp hệ điều hành
Các hàm I/O chung cho các thiết bị, tạo giao diện thống nhất cho phần mềm cấp user
Giải quyết các vấn đề: • ðặt tên • Bảo vệ • Tổ chức buffer • Báo lỗi 18 Phần mềm I/O cấp user
Các yêu cầu I/O được gọi thơng qua các hàm thư viện 19 Các lớp phần mềm I/O 20 III. ðĩa từ 1. Phần cứng đĩa từ 2. Các phương pháp điều phối đĩa từ 21 1. Phần cứng đĩa từ
ðĩa từ • Hard drive
Mạch điều khiển đĩa • Disk controller 22 ðĩa từ ðĩa cứng với 4 đĩa 23 Cấu trúc một mặt đĩa 24 Partitions 25 ðĩa từ (tt)
Track, Sector, Cylinder
ðơn vị truy xuất: sector
Các bước truy xuất sector: • Di chuyển hệ thống đầu từ đến cylinder chứa sector – Seek time (mili sec) • Chờ sector xoay đến vị trí đầu từ - Rotational latency (rpm) • Truy xuất sector
Thơng số tổng quát: tốc độ truy xuất (Data Transfer Rate) theo MB/sec 26 Mạch điều khiển đĩa
Các chuẩn: • SCSI • IDE 27 SCSI (Small Computer System Interface)
Dạng I/O bus, điều khiển nhiều loại thiết bị: đĩa cứng, CDROM, scanner, máy in ..
Cĩ thể đến 15 thiết bị/cáp 28 IDE (Integrated Drive Electronics)
Cịn gọi là ATA (AT Attachment)
EIDE (Extended IDE)  ATA-2 • 4 thiết bị • ðiều khiển CDROM • Hỗ trợ LBA (Logical Block Addressing)
ATA-4  Ultra ATA • ATA-33/66/100 ..: tốc độ DMA là 33MHz/.. 29 Serial ATA (SATA)
Tốc độ cao, từ 150 MB/sec
Chỉ điều khiển đĩa
Dễ cài đặt 30 Serial ATA (tt) 31 2. Các phương pháp điều phối đĩa từ
Cĩ thể cĩ nhiều yêu cầu truy xuất đĩa đồng thời • Cần chọn xử lý một yêu cầu tiếp theo
Xử lý yêu cầu: di chuyển hệ thống đầu từ  ðiều phối đĩa từ
Các phương pháp điều phối đĩa từ: • Random, Priority, FIFO • SSF, SCAN. C-SCAN 32 Các phương pháp điều phối đĩa từ (tt)
Random: chọn yêu cầu ngẫu nhiên
Priority: chọn yêu cầu theo độ ưu tiên của process cĩ yêu cầu
FIFO: chọn yêu cầu theo thứ tự xuất hiện các yêu cầu
SSF (Shortest Seek First) • Chọn yêu cầu tiếp theo sao cho thời gian seek là ít nhất 33 Các phương pháp điều phối đĩa từ (tt)
SCAN – cịn gọi là elevator algorithm • Hệ thống đầu từ di chuyển theo 1 hướng • Xử lý các yêu cầu theo hướng này • Nếu hết yêu cầu hay đến cylinder cuối thì di chuyển theo hướng ngược lại
C-SCAN • Hệ thống đầu từ chỉ di chuyển theo 1 hướng • Xử lý các yêu cầu theo hướng này • Nếu hết yêu cầu hay đến cylinder cuối thì di chuyển nhanh về cylinder đầu tiên 34 Các phương pháp điều phối đĩa từ (tt)
Thực tế: • Nếu số yêu cầu ít: dùng SSF • Nếu số yêu cầu nhiều: dùng C-SCAN 35 Ví dụ các phương pháp điều phối đĩa từ
Cĩ các yêu cầu (theo vị trí cylinder) xuất hiện theo thứ tự: 55 58 39 18 90 160 150 34 184
Vị trí hiện tại của hệ thống đầu từ là cylinder 100 36 Kết quả điều phối 9018184184 583416034 5539150150 395518160 34583490 18903918 1841845539 1601605858 1501509055 C-SCANSCANSSFFIFO 37 IV. Clock 1. Khái niệm 2. Phần cứng clock 3. Ứng dụng clock 38 1. Khái niệm
Clock cịn gọi là timer • Là cơ sở cho các thao tác trên hệ thống chia sẻ thởi gian (time sharing)
Clock dùng để tính thời gian, ngăn chặn việc chỉ một process sử dụng CPU
Về hình thức clock là device driver • Khơng là dạng character, khơng là dạng block 39 2. Phần cứng clock
Gồm các thành phần: • Bộ tạo dao động – Crystal oscillator • Bộ đếm – Counter • Thanh ghi – Holding register
Cĩ hai chế độ hoạt động: • ðếm 1 lần – One-shot mode • ðếm liên tục – Square -ware mode 40 Phần cứng tạo clock - programmable clock 41 Chế độ đếm 1 lần
Bộ đếm được đặt giá trị ban đầu
Bộ đếm thực hiện đếm xuống
Khi bộ đếm đạt 0 thì tạo ra một tín hiệu ngắt quãng 42 Chế độ đếm liên tục
Bộ đếm và thanh ghi được đặt giá trị ban đầu
Bộ đếm thực hiện đếm xuống
Khi bộ đếm đạt 0 thì: • Tạo ra một tín hiệu ngắt quãng • Sao chép giá trị thanh ghi sang bộ đếm • Lập lại việc đếm xuống 43 3. Ứng dụng clock
Phần cứng clock tạo ra các ngắt quãng theo thời gian xác định
Clock driver thực hiện các xử lý
Các hệ điều hành cung cấp các thao tác về thời gian khác nhau 44 Các ứng dụng cơ bản của clock
Duy trì thời gian • Khuơn dạng về thời gian phụ thuộc hệ điều hành
ðiều phối process/thread • Clock tạo ra các ngắt quãng định kỳ  tương ứng với các đơn vị thời gian q
Tạo các timer cho phần mềm ứng dụng
Thực hiện các thao tác thống kê, giám sát hệ thống 45 Ví dụ: các dạng duy trì thời gian hệ thống 46 Ví dụ: tạo nhiều timer từ một clock 47 Ví dụ: Windows Task Manager 48 Ví dụ: Linux System Monitor HỆ ðIỀU HÀNH Chương 6 HỆ THỐNG FILE 2Nội dung chương 6 I. Khái niệm II. File III. Thư mục IV. Hiện thực hệ thống file V. Một số vấn đề về hệ thống file 3I. Khái niệm
File là đơn vị lưu trữ trên thiết bị nhớ ngồi: • Kích thước lớn • File tồn tại sau khi process tạo file kết thúc • File cĩ thể được truy xuất đồng thời từ nhiều process
File là sự trừu tượng hố dữ liệu khi ghi đọc đĩa • Che dấu chi tiết hoạt động trên đĩa 4Hệ thống file
Hệ điều hành tổ chức và quản lý file theo hệ thống file (file system)
Thực hiện trên file: • Tạo cấu trúc • ðặt tên • Truy xuất • Bảo vệ 5Hệ thống file (tt)
Một hệ điều hành thường hỗ trợ nhiều loại hệ thống file • Windows XP: FAT, NTFS, CDFS, UDF (Universal Disk Format),
User quan tâm về file: • ðặt tên • Truy xuất • Bảo vệ 6II. File 1. Tên file 2. Cấu trúc file 3. Loại file 4. Thuộc tính file 5. Các thao tác trên file 71. Tên file
Mỗi file cĩ tên (filename) theo quy định của hệ điều hành, ví dụ: • DOS  8.3 • Windows  long filename (<=255)
Tên file cĩ phần mở rộng (extensions) xác định loại file • Cĩ thể cĩ nhiều phần mở rộng 82. Cấu trúc file
Các dạng chính (cấp thấp): • Chuỗi byte (byte sequence) • Chuỗi record (record sequence) • Cây record (record tree)
Cấu trúc luận lý (cấp cao) do chương trình ứng dụng qui định • Ví dụ: field, record, file, database, 9Cấu trúc file (tt) a. Chuỗi byte b. Chuỗi record c. Cây record 10 3. Loại file
File thường (regular files) • Dạng nhị phân (binary) • Dạng văn bản (text)
Thư mục (folder, directory): file hệ thống
File đặc biệt (special files): trừu tượng hố thiết bị I/O • Dạng ký tự card mạng • Dạng khối  đĩa 11 Ví dụ: các dạng file nhị phân trên UNIX a. File thực thi b. File thư viện 12 4. Thuộc tính file
File cĩ tên, dữ liệu khi được tạo ra
Hệ điều hành thêm các thuộc tính (attributes) cần thiết như date, time, • Các thuộc tính phụ thuộc hệ thống file 13 Các thuộc tính thơng dụng
Name – Tên file
Identifier – Danh hiệu (Id)
Type – loại file
Location – Vị trí
Size – Kích thước
Protection – Dùng trong bảo vệ
Date, Time – Các thơng tin về thời gian
14 5. Các thao tác trên file
Các hệ điều hành cung cấp các thao tác trên file khác nhau • Dùng cho user  các thao tác trên File Manager • Dùng cho programmer  các lệnh gọi hệ thống (system calls) 15 Một số thao tác cơ bản trên file Ghi dữ liệu vào file tại vị trí hiện hànhWrite ðọc file tại vị trí hiện hànhRead Cần đĩng file sau khi sử dụngClose Cần mở file trước khi truy xuấtOpen Xố file. Cĩ thể xố tự động, phục hồiDelete Tạo file rỗng và đặt 1 số thuộc tínhCreate Ý nghĩaThao tác 16 Một số thao tác cơ bản trên file (tt) ðổi tên fileRename ðặt các thuộc tính của fileSet Attributes Lấy thuộc tính của fileGet Attributes Xác định nơi truy xuất fileSeek Ghi vào cuối fileAppend Ý nghĩaThao tác 17 III. Thư mục 1. Tổ chức thứ bậc của thư mục 2. Tên đường dẫn 3. Các thao tác trên thư mục 18 1. Tổ chức thứ bậc của thư mục
Thư mục (directory, folder) là file hệ thống dùng để quản lý hệ thống file
Thư mục bao gồm các phần tử (entry), tương ứng với các file trong thư mục, lưu các thơng tin: • Tên file • Các thuộc tính • 19 Tổ chức thứ bậc của thư mục (tt)
Tổ chức thơng dụng của thư mục: dạng hình cây, với thư mục gốc (root)
Ví dụ • Windows: cây thư mục cho từng đĩa luận lý, hệ thống file trên mạng, • Linux chỉ cĩ 1 cây thư mục trên hệ thống • Cần phải mount các đĩa luận lý, hệ thống file trên mạng vào cây thư mục 20 Ví dụ: cây thư mục 21 Ví dụ: cây thư mục 22 Ví dụ: đồ thị thư mục 23 2. Tên đường dẫn
Khi cĩ tổ chức thư mục thì cần thơng tin về vị trí file trên cây thư mục  tên đường dẫn (pathname) • Pathname = path + filename
Ví dụ: • c:\windows\explorer.exe • /etc/samba/samba.conf 24 3. Các thao tác trên thư mục
Tương tự thao tác trên file, các thao tác trên thư mục khác nhau trên các hệ thống file 25 Một số thao tác cơ bản trên thư mục Cho phép file xuất hiện trong nhiều thư mục Link Trả lại phần tử tiếp theo trong thư mụcReaddir Cần đĩng thư mục sau khi sử dụngClosedir Cần mở thư mục trước khi truy xuất, tương đương liệt kê file trong thư mục Opendir Xố thư mục rỗngDelete Tạo thư mục rỗng với . và ..Create Ý nghĩaThao tác 26 IV. Hiện thực hệ thống file 1. Khái niệm 2. Hiện thực hệ thống file 27 1. Khái niệm
Mỗi partition bao gồm các khối (block/cluster) gồm các sector liên tục: đơn vị cấp phát cho file • Mỗi khối cĩ địa chỉ
Hiện thực hệ thống file: • Quản lý các khối thuộc về file • Quản lý khối chưa sử dụng (free blocks) • Quản lý khối khơng sử dụng được (bad blocks) 28 Ví dụ 29 Các dạng partition, logical drives 30 Các hệ thống file thơng dụng
FAT • Windows 9x, Windows 2K/XP/2K3
NTFS • Windows 2K/XP/2K3
I-node • UNIX • Linux  i-node extensions (Ext2, Ext3) 31 2. Hiện thực hệ thống file a. Dạng danh sách liên kết cĩ chỉ số (FAT) b. Dạng NTFS c. Dạng i-node 32 a. Dạng danh sách liên kết cĩ chỉ số
Mỗi file gồm nhiều khối
Phần tử quản lý file trong thư mục cĩ địa chỉ khối đầu tiên của file
Danh sách liên kết địa chỉ các khối của file được lưu trong 1 bảng, FAT (File Allocation Table) 33 FAT
Mỗi partition theo dạng danh sách liên kết cĩ chỉ số cĩ 1 FAT: • Số phần tử bằng với số khối • Chứa danh sách liên kết các khối của tất cả các file • Quản lý các khối chưa sử dụng • Quản lý các khối khơng sử dụng được 34 Cấu trúc FAT partition
Boot sector: mẩu tin khởi động • Các thơng số của partition • ðoạn chương trình khởi động
FAT
FAT2: bản sao của FAT
Root folder: thư mục gốc
Data • Dữ liệu các file • Các thư mục con (subfolders) 35 Cấu trúc partition theo FAT16 36 Cấu trúc partition theo FAT32 37 Ví dụ: bảng FAT File A
Cluster đầu tiên: 3
Các cluster của file A: 3  9  4  2 File B
Cluster đầu tiên: 5
Các cluster của file B: 5  7  8 38 Các thơng số
Kích thước phần tử trên FAT • 16 bit: FAT16 • 32 bit: FAT32
Kích thước cluster • 512 bytes  64KB 39 Kích thước cluster mặc định FAT16 trên Windows 2000 40 Kích thước tối đa volume FAT32 trên Windows 2000 41 Các vấn đề trên FAT
Phân mảnh bên trong • Do kích thước đơn vị cấp phát cố định • Giải quyết: nén đĩa (disk compresstion)
Phân mảnh bên ngồi • Do thay thế file • Giải quyết: các chương trình cơng cụ dạng defragmentation/speeddisk 42 Thư mục trên FAT
Mỗi file được quản lý bằng một phần tử trong thư mục (directory entry): • Tên, các thuộc tính • ðịa chỉ cluster đầu tiên của file 43 Phần tử trên thư mục – MSDOS
Filename, Extension: tên file và phần mở rộng
Attributes: các thuộc tính (readonly, hidden, system, archive, subdirectory)
Date, Time: ngày giờ tạo file
First block number: địa chỉ cluster đầu tiên của file
Size: kích thước file 44 Phần tử trên thư mục – Windows 98 Mở rộng phần tử trên thư mục MSDOS
NT: tương thích windows NT
ðịa chỉ cluster đầu tiên kích thước 32 bit
Sec: cĩ nhiều loại date/time
45 Ví dụ: phần tử trên thư mục với tên file dài Tên file: The quick brown fox jumps over the lazy dog 46 b. NTFS
Là hệ thống file chuẩn trên Windows NT/2K/XP/2K3
Cĩ nhiều ưu điểm: • Kích thước file, volume lớn • Cĩ khả năng phục hồi, nén, mã hố tốt • Bảo mật tốt • Truy xuất nhanh 47 Kích thước cluster mặc định NTFS trên Windows 2000 48 Cấu trúc NTFS partition
Boot sector: • Thơng tin về hệ thống file • Chương trình nạp file khởi động HDH (ntldr)
MFT: file quản lý hệ thống file
System files: các file hệ thống (metadata) 49 Các file hệ thống
ðược tạo ra khi định dạng partition
Gồm các file: • MFT, MFT mirror • Log file • Cluster Bitmap file (quản lý free blocks) • Boot file • Bad cluster file • 50 MFT (Master File Table)
Quản lý hệ thống file trên NTFS partition
Bao gồm các records (1KB)
Mỗi file hay folder được quản lý bằng 1 hay nhiều MFT record • File, folder kích thước nhỏ (normal): 1 record • File, folder kích thước lớn (large): cĩ thêm các phần mở rộng 51 Cấu trúc MFT 52 Ví dụ: MFT record với file thường 9 blocks 53 Ví dụ: File kích thước lớn với 3 MFT records 54 Ví dụ: MFT record với thư mục thường 55 Tìm file trên MFT Tên file: C:\maria\web.htm 56 c. Dạng i-node
Dùng trên hệ điều hành UNIX
Mỗi file được quản lý bằng một bảng, gọi là i-node, lưu các thơng tin: • Loại file • Các thơng số về thời gian • Bảo vệ file • ðịa chỉ các khối của file 57 I-node (tt)
File kích thước nhỏ chỉ cần các địa chỉ khối trên i-node
File kích thước lớn cần thêm các khối gián tiếp (indirect block), chứa địa chỉ các khối của file 58 I-node (tt) 59 Kích thước UNIX file theo i-node 60 Directory và i-node 61 Cấu trúc partition theo i-node
Boot block: khối khởi động
Super block: thơng tin về hệ thống file
I-nodes: bảng các i-node
Data blocks: các khối dữ liệu 62 Ví dụ: các bước truy xuất /usr/ast/mbox 63 Hệ thống file trên Linux
Xuất phát từ Minix file system
Phát triển với cấu trúc VFS trên kernel • Virtual File System
Hiện thực thêm các hệ thống file theo dạng i-node: • Extended File System (Ext) • Second Extended File System (Ext2) 64 Cấu trúc VFS 65 Cấu trúc partition theo Ext2 Super block, Group descriptor: thơng tin hệ thống file Block bitmap: quản lý các khối i-node bitmap: quản lý bảng i-node I-nodes: bảng i-node Data blocks: các khối dữ liệu 66 Cấu trúc phần tử trên thư mục và ví dụ 67 V. Một số vấn đề về hệ thống file 1. Bảo vệ file 2. ðĩa luận lý 68 1. Bảo vệ file
Nguyên tắc cơ bản: dùng access control list (ACL): • Liệt kê quyền truy xuất được phép của user, nhĩm user • Do người sở hữu file (owner) qui định • ACL thường được lưu trữ theo file như thuộc tính của file 69 Ví dụ: NTFS folder permissions 70 2. ðĩa luận lý
Hệ thống file được hiện thực và tạo nên đĩa luận lý (logical drive)
Khái niệm đĩa luận lý đa dạng theo các loại hệ điều hành 71 Một số dạng đĩa luận lý trên Windows
Basic disk/volume: • 1 partition trên đĩa vật lý
Dynamic disk/volume: cĩ thể tạo volume gồm nhiều đĩa vật lý • Spanned • Stripped (cịn gọl là RAID-0) • Mirrored (cịn gọl là RAID-1) • RAID-5 (Redundant Arrays of Inexpensive Disks -5) 72 Volume trên 2 đĩa – Volume set LCN: Logical Cluster Number 73 Strip Set trên 2 đĩa 74 Mirror set trên 2 đĩa 75 Strip Set with parity (RAID-5) trên 3 đĩa