Bài giảng Hệ điều hành - Chương 3 Hệ thống quản lý tập tin

1Chương 3: Hệ thống quản lý tập tin „ Nội dung chương: „ Các khái niệm cơ bản về hệ thống tập tin „ Cài đặt hệ thống quản lý tập tin „ Mô hình tổ chức và quản lý tập tin của các HĐH thông dụng. „ Truy xuất hệ thống quản lý tập tin. 2Hệ thống lưu trữ trong máy tính „ Bộ nhớ trong „ RAM, ROM, Register, Cache „ Bộ nhớ ngoài „ HD (Hard Disk) „ FD (Floppy Disk) „ CD (Compact Disk) „ DVD (Digital Video Disk) „ USB disk „ cache Bộ nhớ chính Bộ nhớ phụ (đĩa) Bộ nhớ thứ cấp (băng từ) T ố c đ ộ D u n g l ư ợ n g G i á t h à n h 3Các khái niệm cơ bản „ RAM không có khả năng lưu trữ dữ liệu lâu dài. „ Máy tính phải sử dụng các thiết bị có khả năng lưu trữ lâu dài vì: „ Chứa lượng thông tin lớn. „ Thông tin được lưu trữ trước khi xử lý. „ Nhiều ứng dụng muốn truy cập cùng lúc. Æ Phải sử dụng các thiết bị lưu trữ ngoài gọi là bộ nhớ ngoài với các đơn vị lưu trữ được tổ chức thành: „ Tập tin „ Thư mục 4Tổ chức dữ liệu trên đĩa từ „ Cấu trúc vật lý của đĩa từ: „ Hình tròn, gồm nhiều mặt gọi là head. „ Mỗi mặt có nhiều đường tròn đồng tâm gọi là track hay cylinder. „ Trên các đường tròn (track) được chia thành các cung tròn gọi là sector. „ Mỗi cung tròn chứa 4096 điểm từ (~ 4096 bit = 512 bytes). „ Mỗi mặt có 1 đầu đọc để đọc ghi dữ liệu „ Mỗi lần đọc/ghi ít nhất 1 cung tròn (512B). 5Cấu trúc đĩa từ Head 0 Head 2 6Cấu trúc đĩa từ read-write head track sectors cylinder 7Cấu trúc đĩa từ 8Tổ chức dữ liệu trên đĩa từ (tt) „ Mỗi lần đọc hay ghi đĩa có thể thực hiện N sector liên tiếp (N>=1). „ Vị trí của mỗi sector trong đĩa được thể hiện bằng 3 tham số : {sector, track, head}. „ Head được đánh số từ trên xuống bắt đầu từ 0. „ Track được đánh số từ ngoài vào bắt đầu từ 0. „ Sector được đánh số bắt đầu từ 1 theo chiều ngược với chiều quay của đĩa. 9Tổ chức đĩa logic „ Thay vì phải dùng đến 3 tham số dựa trên cấu trúc đĩa vật lý nên khái niệm đĩa logic được đưa ra để dễ thao tác và tính toán hơn. „ Đĩa logic là một dãy sector được đánh số bắt đầu từ 0. „ Mỗi sector trên đĩa logic tương ứng với 1 sector duy nhất trên đĩa vật lý sao cho khi truy xuất sector K thì khi truy xuất tiếp sang sector K+1 là nhanh nhất. N-143210 10 Dung lượng đĩa „ Kích thước đĩa phụ thuộc vào các yếu tố sau: „ Số mặt từ (platter) „ Số track trên mỗi mặt từ „ Số sector trên mỗi track „ Kích thước (byte) trên mỗi track. 11 Ví dụ cách tổ chức đĩa mềm „ Các thông số trên đĩa mềm 1.44MB: „ Đĩa có 2 head, 80 track/head, 18 sector/track. „ Dung lượng đĩa = 2 head/disk *80 track/head *18 sector/track = 2880 sector/disk = 0.5 KB/sector * 2880 sector/disk = 1440 KB/disk (~ 1.4MB) „ Các sector logic có chỉ số từ 0 đến 2879 và tương ứng với các sector vật lý như sau: „ Sector 0..17 tương ứng với sector vật lý (1,0,0)..(18,0,0) „ Sector 18..35 tương ứng với sector vật lý (1,0,1)..(18,0,1) „ „ Sector 2879 tương ứng với sector vật lý (18,79,1). 12 Mặt đĩa Tay quay Đầu đọc Thời gian truy cập đĩa „ Disk access time = Seek Time + Latency Time + Transfer Time 13 Các thuật toán đọc đĩa „ First-Come-First-Serve (FCFS) „ SCAN, C-SCAN „ Shortest Seek Time First (SSTF) „ Look 14 First Come First Serve (FCFS) „ Phục vụ theo thứ tự yêu cầu „ Đơn giản nhưng không đáp ứng tốt dịch vụ t i m e cylinder number 1 5 10 15 20 25 12 Các khối cần đọc (đầu đọc hiện tại tại vị trí 11): 14 2 7 21 8 24 scheduling queue 24 8 21 7 2 14 12 15 SCAN „ Di chuyển đầu đọc về 1 phía của đĩa đến block xa nhất sau đó di chuyển về phía kia. „ Còn gọi là thuật toán thang máy. t i m e cylinder number 1 5 10 15 20 25 12 14 2 7 21 8 24 scheduling queue Các khối cần đọc (đầu đọc hiện tại tại vị trí 11): 16 SCAN vs. FCFS „ Trong trường hợp này, SCAN tốt hơn FCFS vì hạn chế sự di chuyển của đầu đọc đĩa cylinder number 1 5 10 15 20 25 t i m e t i m e 17 C-SCAN „ Nguyên tắc: „ Tương tự thuật toán SCAN. „ Chỉ khác khi di chuyển đến 1 đầu của đĩa thì trở về vị trí bắt đầu của đĩa. 18 C-SCAN 19 LOOK „ Nhận xét: „ Hai thuật toán lập lịch SCAN và C-SCAN luôn luôn di chuyển đầu đọc của đĩa từ đầu này sang đầu kia nhưng thông thường thì đầu đọc chỉ di chuyển đến khối xa nhất ở mỗi hướng chứ không đến cuối. „ Nguyên tắc: „ Giống SCAN và C-SCAN nhưng chỉ di chuyển đầu đọc đến khống xa nhất chứ không đến cuối. 20 LOOK 21 SSTF „ SSTF = Shortest Seek Time First „ Nguyên tắc: „ Di chuyển đầu đọc đến các khối cần thiết theo vị trí lần lượt gần với vị trí hiện hành của đầu đọc nhất 22 SSTF 23 Lập trình tương tác với đĩa „ Các truy xuất đĩa trực tiếp trong C: „ Đọc nội dung sector trên đĩa logic: hàm absread. „ Ghi nội dung vào sector logic: abswrite. „ Thực hiện thao tác trên đĩa vật lý: biosdisk. „ Cú pháp: „ int absread(int drive, int nsects, long lsect, void *buffer). „ int abswrite (int drive, int nsects, long lsect, void *buffer); „ int biosdisk (int cmd, int drive, int head, int track, int sector, int nsects, void *buffer); 24 Tập tin (1/4) „ Tập tin (file) là đơn vị lưu trữ thông tin trên bộ nhớ ngoài. „ Thông tin chứa trong tập tin là bền vững (không bị mất đi khi bị mất điện). „ Tên tập tin: „ Là cơ chế trừu tượng để quản lý tập tin. „ Có thể phân biệt chữ hoa và thường (tuỳ HĐH cụ thể) „ Hỗ trợ tên tập tin theo định dạng 8.3 (gồm tên và phần mở rộng) hay tên dài (Long File Name). „ Ví dụ: baitap.cpp hay “bai tap lap trinh.cpp” 25 Tập tin (2/4) Các thuộc tính của tập tin: „ Người sở hữu/nhóm sở hữu „ Chỉ đọc (Read-only) „ Ẩn (Hidden) „ Hệ thống (System) „ Lưu trữ (Archive) „ Ngày giờ tạo. „ Ngày giờ truy cập cuối cùng „ Ngày giờ thay đổi cuối cùng „ Kích thước 26 Tập tin (3/4) „ Tạo „ Xoá „ Mở „ Đóng „ Đọc „ Ghi Các thao tác trên tập tin: „ Thêm „ Tìm „ Lấy thuộc tính „ Thiết lập thuộc tính „ Đổi tên 27 Tập tin (4/4) „ Các loại tập tin: „ Tập tin văn bản (text file): chứa các dòng văn bản, cuối dùng có ký hiệu kết thúc dòng (end line) „ Tập tin nhị phân (binary file): là tập tin có cấu trúc. „ Các truy xuất trên tập tin: „ Tuần tự: Phải đọc từ đầu tập tin đến vị trí mong muốn. „ Ngẫu nhiên: Có thể di chuyển nhanh (SEEK) đến đúng vị trí cần đọc. 28 Khối điều khiển tập tin 29 Thư mục „ Giúp cho việc quản lý các tập tin dễ dàng hơn. „ Giúp định vị các tập tin 1 cách nhanh chóng. „ Gom nhóm các tập tin vào trong các thư mục theo ý nghĩa và mục đích sử dụng của người dùng. root bob sue www fun3013 30 Thư mục Ví dụ 1 cấu trúc cây thư mục phân cấp 31 Thư mục - Đường dẫn (Path) „ Dùng để xác định vị trí lưu tập tin khi hệ thống được tổ chức thành cây thư mục: „ Đường dẫn tuyệt đối: „ Ví dụ: “C:\Downloads\software\baigiang.doc” „ Đường dẫn tương đối: „ Ví dụ: “software\baigiang.doc” nếu thư mục hiện hành là “C:\Downloads\” „ Các thư mục đặc biệt: „ Thư mục hiện hành (.) „ Thư mục cha (..) 32 Thư mục „ Các thao tác trên thư mục: „ Tạo Xoá Đổi tên „ Mở Đóng „ Tìm kiếm Liệt kê „ Liên kết: Cho phép 1 tập tin có thể xuất hiện trong nhiều thư mục khác nhau. „ Bỏ liên kết: Nếu tập tin chỉ có 1 liên kết với 1 thư mục, nó sẽ bị loại bỏ hoàn toàn, ngược lại nó sẽ bị giảm chỉ số liên kết 33 Cấp phát vùng nhớ chứa tập tin „ Các khối (block) đĩa sẽ được cấp phát để lưu trữ nội dung tập tin theo các cơ chế cấp phát: „ Cấp phát liên tục „ Cấp phát bằng danh sách liên kết „ Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index). „ Cấp phát bằng I-node 34 Cấp phát liên tục „ Cấp phát 1 số block liên tục trên đĩa để lưu trữ nội dung tập tin „ Nhận xét: „ Đơn giản: chỉ cần quản lý số hiệu khối bắt đầu và tổng số block chiếm bởi tập tin. „ Truy cập nội dung tập tin nhanh chóng vì các block nằm kề nhau. „ Gây lãng phí bộ nhớ. „ Khó khăn khi tập tin mở rộng kích thước. 35 Cấp phát liên tục (tt) 36 Cấp phát bằng danh sách liên kết „ Nội dung tập tin được lưu trữ ở những block không cần liên tục. Các block này được xâu chuỗi tạo thành 1 danh sách liên kết để quản lý. „ Nhận xét: „ Đơn giản: Chỉ cần quản lý block bắt đầu. „ Tận dụng hiệu quả không gian đĩa. „ Truy cập tập tin lâu hơn vì đầu đọc phải di chuyển nhiều giữa các khối không liên tiếp. „ Khối dữ liệu bị thu hẹp lại vì mỗi khối phải dùng 1 phần để lưu phần liên kết đến khối kế tiếp. 37 Cấp phát bằng danh sách liên kết (tt) 38 Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index) „ Tương tự như phương pháp cấp phát bằng danh sách liên kết nhưng thay vì sử dụng 1 phần nhỏ của mỗi block để lưu chuỗi liên kết thì sử dụng 1 block riêng để lưu toàn bộ chuỗi liên kết. „ Æ Các block chỉ chứa dữ liệu. 39 Cấp phát bằng danh sách liên kết sử dụng chỉ mục (index) (tt) 40 Cấp phát bằng I-node „ Mỗi I-node gồm 2 phần: „ Các thuộc tính của tập tin „ Địa chỉ của các khối dữ liệu: gồm 13 phần tử „ 10 phần tử đầu tiên: Địa chỉ của các khối dữ liệu trực tiếp. „ Phần tử thứ 11: Địa chỉ của các khối dữ liệu gián tiếp đơn (single indirect): gồm 1 khối trỏ đến 210 phần tử chứa địa chỉ của các khối dữ liệu. „ Phần tử thứ 12: Địa chỉ của các khối dữ liệu gián tiếp đôi (double indirect): chứa địa chỉ của các khối single indirect. „ Phần tử thứ 13: Địa chỉ của các khối dữ liệu gián tiếp ba (triple indirect) 41 Cấp phát bằng I-node (tt) 42 Cài đặt hệ thống tập tin của các HĐH cụ thể „ MS-DOS „ Windows „ Unix 43 Tổ chức quản lý hệ thống tập tin trên đĩa từ 0 1 2 3 .. Đĩa từ bao gồm danh sách các sector có kích thước 512Bytes Kích thước đĩa (bytes) = (tổng số sector) x (512 bytes/sector) 44 Phân vùng đĩa (Disk Partition) „ Toàn bộ vùng lưu trữ của đĩa được phân thành các vùng logic không chồng lên nhau gọi là phân vùng đĩa. Partition #1 Partition #2 Partition #3 unused 45 Master Boot Record „ Một phần nhỏ đầu tiên của đĩa được dành riêng cho các thông tin quản lý đĩa. „ Sector logic thứ 0 của đĩa (CHS = 001) là Master Boot Record chứa thông tin mô tả cấu trúc vật lý của đĩa và thông tin về các phân vùng logic của đĩa. MBR 0 1 2 partition #1 46 MBR „ Thông tin chứa trong MBR bao gồm: „ Đoạn chương trình để giúp khởi động hệ thống „ Bảng mô tả thông tin các phân vùng logic „ Thông tin nhận diện MBR signature (2 bytes) Partition Table (64 bytes) Bootstrap Loader (446 bytes)512 bytes 47 Bảng mô tả các phân vùng „ MBR có thể mô tả cho tối đa 4 phân vùng logic được chia trên đĩa trong đó thường có 1 phân vùng ở trạng thái “Active” Starting sector ID-number Partition length (in sectors) S T A T U S T Y P E16 bytes Some fields contain ‘obsolete’ information 48 Primary Partition vs Extended Partition Reserved Reserved Reserved Reserved Reserved Reserved Reserved MBR Reserved Reserved Reserved Reserved Reserved Reserved Reserved Partition Table Primary Partition Extended Partition 49 „ Phân vùng “active” là phân vùng chứa HĐH sẽ được nạp mặc định khi máy tính khởi động. Bảng mô tả các phân vùng (tt) 50 Trường TYPE-ID trong bảng mô tả phân vùng „ Ý nghĩa của trường Type-ID trong mỗi phân vùng „ TYPE-ID = 0x07 : Phân vùng chứa “Windows” „ TYPE-ID = 0x83 : Phân vùng chứa “Linux” „ TYPE-ID = 0x00 : Phân vùng không sử dụng. 51 Quá trình khởi động hệ thống và nạp HĐH dựa trên thông tin các phân vùng „ B1: POST (Power-On Self-Test) „ B2: Tải MBR để đọc thông tin bảng phân vùng. „ B3: Tìm phân vùng “active”. „ B4: Chuyển quyền điều khiển về cho đoạn mã chương trình nằm trong Boot Record của phân vùng “active” „ B5: Tải HĐH tại phân vùng “active”. 52 Tổ chức tập tin trên Windows: FAT (12,16,32) 53 Tổ chức tập tin trên Windows: FAT (12,16,32) (tt) „ FAT: File Allocation Table „ Các phiên bản của FAT: FAT12, FAT16, FAT32 „ 12,16,32: Số bít dùng để đánh STT các khối (212,216,232) „ FAT12: 212 (khối) x 512 bytes/khối = 2MB „ FAT16: 216 (khối) x 512 bytes/khối = 32MB „ FAT32: 232 (khối) x 512 bytes/khối = 4GB Boot sector FAT1 FAT2 (backup) Root directory Other directories and files 0000 0003 0004 FFFF 0006 0008 FFFF FFFF 0000 empty File1 File1empty File2File1 File3File2 emptyFile2 empty empty emptyempty empty empty empty empty 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 54 Tổ chức tập tin trên Windows: NTFS „ Nhóm các sector liên tiếp nhau lại để tạo thành các Cluster. 55 Tổ chức tập tin trên Windows: NTFS „ NTFS không sử dụng khái niệm FAT và Root Dir để quản lý các tập tin lưu trên đĩa mà sử dụng khái nhiệm MFT (Master File Table). „ MFT là 1 Metadata file bao gồm 1 danh sách các trường chứa thông tin về mỗi tập tin lưu trữ trên đĩa. „ Thông tin trong MFT có thể giúp thiết lập các thuộc tính bảo vệ, phục hồi, tìm kiếm, thiết lập quota cho từng tập tin, thư mục trên đĩa. 56 Tổ chức tập tin trên Unix/Linux: I-node mode owner Direct block 0 Direct block 1 Direct block 10 Direct block 11 Single indirect Double indirect Triple indirect Data block Data block Data block Data block index Data block Data block Data block Data block index index indexindex indexindex Data block Data block Data block Data block index index Data block I-node Data block