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

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 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 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 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 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 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 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 3. KỸ THUẬT BỘ NHỚ ẢO 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ý 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 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 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 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 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 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 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 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 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 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 CHƯƠNG IV:QUẢN LÝ FILE VÀ ĐĨA 1. CÁC KHÁI NIỆM CƠ BẢN 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). 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ị 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. 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 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 2. CÁC PHƯƠNG PHÁP TRUY XUẤT Truy xuất tuần tự Truy xuất trực tiếp 3. CẤU TRÚC THƯ MỤC 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. 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. 3.3 Cấu trúc thư mục dạng cây 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 3.5. Cấu trúc thư mục dạng đồ thị tổng quát 4. CÁC PHƯƠNG PHÁP CÀI ĐẶT HỆ THỐNG QUẢN LÝ TẬP TIN 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 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 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 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 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 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 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) 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ừ 210 đến 232 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. 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]