Bài giảng Kiến trúc Máy tính và hệ điều hành - Chương 6: Các thành phần của hệ điều hành - Nguyễn Thị Ngọc Vinh

Nội dung text: Bài giảng Kiến trúc Máy tính và hệ điều hành - Chương 6: Các thành phần của hệ điều hành - Nguyễn Thị Ngọc Vinh

1. 6/25/2014 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG BÀI GIẢNG MÔN KIẾN TRÚC MÁY TÍNH VÀ HỆ ĐIỀU HÀNH Giảng viên: ThS. Nguyễn Thị Ngọc Vinh Bộ môn: Khoa học máy tính- Khoa CNTT1 Email: ntngocvinh@yahoo.com CHƯƠNG 6: CÁC THÀNH PHẦN CỦA HỆ ĐIỀU HÀNH www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 2 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 1
2. 6/25/2014 NỘI DUNG . Quản lý hệ thống file . Các khái niệm liên quan tới file . Thư mục . Cấp phát không gian cho file . Độ tin cậy và bảo mật cho hệ thống file www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 3 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 NỘI DUNG . Quản lý bộ nhớ . Khái niệm phân chương bộ nhớ . Khái niệm phân trang bộ nhớ . Khái niệm phân đoạn bộ nhớ . Bộ nhớ ảo . Quản lý tiến trình . Các khái niệm . Điều độ tiến trình www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 4 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 2
3. 6/25/2014 QUẢN LÝ HỆ THỐNG FILE www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 5 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CÁC KHÁI NIỆM . File được định nghĩa như tập hợp các thông tin liên quan đến nhau được đặt tên và được lưu trữ trên bộ nhớ ngoài . Thuộc tính của file: . Tên file . Kiểu file . Kích thước file . Người tạo file, người sở hữu . Quyền truy cập file . Thời gian tạo file, sửa file, truy cập lần cuối . Vị trí file www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 6 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 3
4. 6/25/2014 CÁC KHÁI NIỆM . Đặt tên cho file: . Cho phép xác định file . Là thông tin người dùng thường sử dụng nhất khi làm việc với file . Quy tắc đặt tên cho file của một số HDH: Hệ điều hành Độ dài tối đa Phân biệt chữ Cho phép sử dụng Các ký tự cấm hoa, chữ thường dấu cách MS-DOS 8 cho tên file không không Bắt đầu bằng chữ cái hoặc số 3 cho mở rộng Không được chứa các ký tự / \ [ ] : ; | = , ^ ? @ Windows NT 255 ký tự cho cả tên không có Bắt đầu bằng chữ cái hoặc số FAT file và đường dẫn Không được chứa các ký tự / \ [] : ; | = , ^ ? @ Windows NT 255 không có Không được chứa các ký tự / \ * | : NTFS Linux (EXT3) 256 Có có (nếu tên file Không được chứa các ký tự ! @ # $ % chứa trong ngoặc ^ & * ( ) [ ] { } ‘ “ / \ : ; ` kép) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 7 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CÁC KHÁI NIỆM . Cấu trúc file: . Các thông tin trong file có thể rất khác nhau . => Cấu trúc của file cũng rất khác nhau và phụ thuộc vào thông tin chứa trong file . HDH có cần biết và hỗ trợ các kiểu cấu trúc file? . Hỗ trợ cấu trúc file ở mức HDH: . Ưu điểm: . Các thao tác với file sẽ dễ dàng hơn đối với người lập trình ứng dụng . HDH có thể kiểm soát được các thao tác với file . Nhược điểm: . Tăng kích thước hệ thống . Tính mềm dẻo của HDH bị giảm . Thực tế các HDH chỉ coi file là tập hợp các byte không cấu trúc www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 8 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 4
5. 6/25/2014 THƯ MỤC 1. Khái niệm . Số lượng file lưu trữ trên đĩa rất lớn => phải tổ chức để dễ dàng quản lý, truy cập files . Không gian trên đĩa được chia thành các phần (partition/ volume) gọi là đĩa logic . Để quản lý file trên các đĩa logic, thông tin về file được lưu trong thư mục của đĩa . Thư mục = ∑ các khoản mục ~ files . Khoản mục chứa các thông tin về file: tên, kích thước, vị trí, kiểu file, hoặc con trỏ tới nơi lưu trữ thông tin này . Coi thư mục như 1 bảng, mỗi dòng là khoản mục ứng với 1 file www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 9 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 THƯ MỤC 1. Khái niệm . Các cách lưu thông tin về file trong thư mục: . Toàn bộ thuộc tính của file được lưu trong thư mục, file chỉ chứa data => kích thước khoản mục, thư mục lớn . Thư mục chỉ lưu thông tin tối thiểu cần thiết cho việc tìm kiếm vị trí file trên đĩa => kích thước giảm thuộc tính file1.txt Thuộc tính file1.txt thuộc Thuộc tính file2.c file2.c tính file3.pas Thuộc tính file3.pas thuộc tính file4.doc Thuộc tính file4.doc thuộc tính (a) (b) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 10 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 5
6. 6/25/2014 THƯ MỤC 1. Khái niệm . Mở file: . HDH tìm trong thư mục khoản mục ứng với tên file cần mở . Đọc các thuộc tính và vị trí dữ liệu của file vào bảng chứa thông tin về các file đang mở . Nếu khoản mục trỏ tới CTDL khác chứa thuộc tính file, cấu trúc này sẽ được đọc vào bảng www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 11 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 THƯ MỤC 2. Các thao tác với thư mục . Tìm kiếm file: cấu trúc thư mục phải cho phép tìm kiếm file theo tên file . Tạo file: tạo khoản mục mới và thêm vào thư mục . Xóa file: thông tin về file và khoản mục tương ứng bị xóa khỏi thư mục . Duyệt thư mục: liệt kê các file trong thư mục và thông tin chứa trong khoản mục của file . Đổi tên file: chỉ cần thực hiện với thư mục chứ không liên quan đến dữ liệu của file www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 12 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 6
7. 6/25/2014 THƯ MỤC 3. Cấu trúc hệ thống thư mục . Thư mục 1 mức: . Đơn giản nhất . Chỉ có 1 thư mục duy nhất và tất cả các file được giữ trong thư mục này . Khó chọn tên cho file . Tìm kiếm file khó www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 13 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 THƯ MỤC 3. Cấu trúc hệ thống thư mục . Thư mục 2 mức: . Phân cho mỗi người dùng 1 thư mục riêng (UFD: User File Directory), chứa các file của mình . Khi người dùng truy cập file, file sẽ được tìm kiếm trong thư mục ứng với tên người đó . => các người dùng khác nhau có thể đặt tên file trùng nhau . Cô lập người dùng . Các file mà nhiều người dùng truy cập tới => chép vào từng thư mục của từng người dùng => lãng phí www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 14 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 7
8. 6/25/2014 THƯ MỤC 3. Cấu trúc hệ thống thư mục . Thư mục cấu trúc cây: . Thư mục con có thể chứa các thư mục con khác và các files . Hệ thống thư mục được biểu diễn phân cấp như 1 cây: cành là thư mục, lá là file Thư mục gốc = Thư mục = File www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 15 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 THƯ MỤC 3. Cấu trúc hệ thống thư mục . Thư mục cấu trúc cây (tt): . Phân biệt khoản mục file và khoản mục của thư mục con: thêm bit đặc biệt trong khoản mục . 1: khoản mục của thư mục mức dưới . 0: khoản mục của file . Tại mỗi thời điểm, người dùng làm việc với thư mục hiện thời (current directory) . Tổ chức cây thư mục cho từng đĩa: . Trong hệ thống file như FAT của DOS, cây thư mục được xây cho từng đĩa. Hệ thống thư mục được coi là rừng, mỗi cây trên 1 đĩa . Linux: toàn hệ thống chỉ gồm 1 cây thư mục www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 16 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 8
9. 6/25/2014 THƯ MỤC 4. Đường dẫn . Mô tả vị trí của file trong thư mục . Đường dẫn tuyệt đối: . Đường dẫn từ gốc của cây thư mục, đi qua các thư mục trung gian, dẫn tới file . C:\bc\bin\bc.exe . Đường dẫn tương đối: . Tính từ thư mục hiện thời . Thêm 2 khoản mục đặc biệt trong thư mục: “.”, “ ” www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 17 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE . Phép ánh xạ file: từ tên file có thể chỉ ra vị trí file trên đĩa . Sơ bộ về tổ chức đĩa: . Thông tin được đọc/ghi theo từng khối sector . Nhóm các sector thành block hay cluster (khối) . Trên đĩa: 1 file gồm 1 tập các khối. HDH chịu trách nhiệm cấp phát các khối cho file: . Không gian trên đĩa phải được cấp phát cho file . Cần theo dõi không gian trống sẵn sàng cho việc cấp phát www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 18 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 9
10. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 1. Cấp phát các khối liên tiếp . Được cấp phát 1 khoảng không gian gồm các khối liên tiếp trên đĩa . Vị trí file trên đĩa được xác định bởi vị trí khối đầu tiên và độ dài (số khối) mà file đó chiếm . Khi có yêu cầu cấp phát, HDH sẽ chọn 1 vùng trống có số lượng khối đủ cấp cho file đó . Bảng cấp phát file chỉ cần 1 khoản mục cho 1 file, chỉ ra khối bắt đầu, và độ dài của file tính = khối . Là cấp phát trước, sử dụng kích thước phần thay đổi www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 19 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 1. Cấp phát các khối liên tiếp (tt) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 20 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 10
11. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 1. Cấp phát các khối liên tiếp (tt) . Ưu điểm: . Cho phép truy cập trực tiếp và tuần tự . Đơn giản, tốc độ cao . Nhược điểm: . Phải biết trước kích thước file khi tạo . Khó tìm chỗ cho file . Gây phân mảnh ngoài: www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 21 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 2. Sử dụng danh sách kết nối . Các khối được kết nối với nhau thành danh sách kết nối; phần đầu mỗi khối chứa con trỏ trỏ tới khối tiếp theo . Các khối thuộc về 1 file có thể nằm ở vị trí bất kì trên đĩa . Khoản mục của thư mục chứa con trỏ tới khối đầu tiên của file . Khi file được cấp thêm khối mới, khối đó được thêm vào cuối danh sách . HDH đọc lần lượt từng khối và sử dụng con trỏ để xác định khối tiếp theo www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 22 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 11
12. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 2. Sử dụng danh sách kết nối (tt) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 23 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 2. Sử dụng danh sách kết nối (tt) . Ưu điểm: . Không bị phân mảnh ngoài . Không yêu cầu biết trước kích thước file lúc tạo . Dễ tìm vị trí cho file, khoản mục đơn giản . Nhược điểm: . Không hỗ trợ truy cập trực tiếp . Tốc độ truy cập không cao . Giảm độ tin cậy và tính toàn vẹn của hệ thống file www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 24 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 12
13. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 3. Sử dụng danh sách kết nối trên bảng chỉ số . Bảng chỉ số: mỗi ô của bảng ứng với 1 khối của đĩa . Con trỏ tới khối tiếp theo của file được chứa trong ô tương ứng của bảng . Mỗi đĩa logic có 1 bảng chỉ số được lưu ở vị trí xác định . Kích thước mỗi ô trên bảng phụ thuộc vào số lượng khối trên đĩa www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 25 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 3. Sử dụng danh sách kết nối trên bảng chỉ số (tt) . Cho phép tiến hành truy cập file trực tiếp: đi theo chuỗi con trỏ chứa trong bảng chỉ mục . Bảng FAT (File Allocation Table): được lưu ở đầu mỗi đĩa logic sau sector khởi động . FAT12, FAT16, FAT32: mỗi ô của bảng có kích thước 12, 16, 32 bit www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 26 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 13
14. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 4. Sử dụng khối chỉ mục (index block/ node) . Tất cả con trỏ tới các khối thuộc về 1 file được tập trung 1 chỗ . Mỗi file có một mảng riêng của mình chứa trong một khối gọi là khối chỉ mục (I-node) . Mảng chứa thuộc tính của file và vị trí các khối của file trên đĩa . Ô thứ i của mảng chứa con trỏ tới khối thứ i của file . Khoản mục của file trong thư mục chứa con trỏ tới khối chỉ mục này www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 27 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 4. Sử dụng khối chỉ mục (index block/ node) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 28 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 14
15. 6/25/2014 CẤP PHÁT KHÔNG GIAN CHO FILE 4. Sử dụng khối chỉ mục (index block/ node) . Chọn kích thước I-node: . Nhỏ: tiết kiệm không gian nhưng không đủ con trỏ tới các khối nếu file lớn . Lớn: với file nhỏ chỉ chiếm 1 vài ô thì lãng phí . Giải pháp: . Thay đổi kích thước i-node = sử dụng danh sách kết nối . Sử dụng I-node có cấu trúc nhiều mức www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 29 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CẤP PHÁT KHÔNG GIAN CHO FILE 4. Sử dụng khối chỉ mục (index block/ node) . Ưu điểm: . Cho phép truy cập trực tiếp . Các khối thuộc 1 file không cần nằm liên tiếp nhau . Nhược điểm: . Tốc độ truy cập file chậm www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 30 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 15
16. 6/25/2014 ĐỘ TIN CẬY CỦA HỆ THỐNG FILE Sao dự phòng . Tạo ra một bản sao của đĩa trên một vật mang khác . Sao lưu toàn bộ (full backup): . Ghi toàn bộ thông tin trên đĩa ra vật mang tin khác . Chắc chắn nhưng tốn nhiều thời gian . Sao lưu tăng dần (incremental backup): . Được sử dụng sau khi đã tiến hành full backup ít nhất 1 lần . Chỉ ghi lại các file đã bị thay đổi sau lần sao lưu cuối cùng . Hệ thống lưu trữ thông tin về các lần lưu trữ file . DOS: file thay đổi, archive bit =1 . Kết hợp: . Full backup: hàng tuần/ tháng . Incremental backup: hàng ngày www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 31 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BẢO MẬT CHO HỆ THỐNG FILE . Ngăn cản việc truy cập trái phép các thông tin lưu trữ trong file và thư mục . Hạn chế các thao tác truy cập tới file hoặc thư mục . Dùng mật khẩu: . Người dùng phải nhớ nhiều mật khẩu . Mỗi khi thao tác với tài nguyên lại gõ mật khẩu www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 32 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 16
17. 6/25/2014 BẢO MẬT CHO HỆ THỐNG FILE . Sử dụng danh sách quản lý truy cập ACL (Access Control List) . Mỗi file được gán danh sách đi kèm, chứa thông tin định danh người dùng và các quyền người đó được thực hiện với file . ACL thường được lưu trữ như thuộc tính của file/ thư mục . Thường được sử dụng cùng với cơ chế đăng nhập . Các quyền truy cập cơ bản: . Quyền đọc (r) . Quyền ghi, thay đổi (w) . Quyền xóa . Quyền thay đổi chủ file (change owner) www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 33 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 QUẢN LÝ BỘ NHỚ www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 34 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 17
18. 6/25/2014 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 1. Phân chương cố định . Chia MEM thành các chương với số lượng nhất định, không thay đổi, gán cho tiến trình 1 chương chứa data, lệnh . Kích thước các chương bằng nhau: . Đơn giản . Kích thước chương trình > kích thước chương => không thể cấp phát . Gây phân mảnh trong www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 35 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 1. Phân chương cố định . Kích thước các chương khác nhau: . Chọn chương có kích thước nhỏ nhất: cần có hàng đợi lệnh cho mỗi chương: . Giảm phân mảnh trong, tối ưu cho từng chương . Hệ thống không tối ưu www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 36 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 18
19. 6/25/2014 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 1. Phân chương cố định . Kích thước các chương khác nhau: . Dùng hàng đợi chung cho mọi chương: . Chương sẵn có nhỏ nhất sẽ được cấp phát . Khi 1 chương được giải phóng: chọn tiến trình gần đầu hàng độ nhất và có kích thước phù hợp nhất www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 37 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 1. Phân chương cố định . Ưu điểm: đơn giản, ít xử lý . Nhược điểm: . Số lượng chương xác định tại thời điểm tạo hệ thống hạn chế số lượng tiến trình hoạt động . Kích thước chương thiết lập trước: không hiệu quả www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 38 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 19
20. 6/25/2014 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 2. Phân chương động . Kích thước, số lượng và vị trí chương đều có thể thay đổi . Khi có yêu cầu, HDH cấp cho tiến trình 1 chương có kích thước đúng bằng tiến trình đó . Khi tiến trình kết thúc sẽ tạo vùng trống trong MEM . Các vùng trống nằm cạnh nhau được nhập lại thành vùng lớn hơn www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 39 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 KỸ THUẬT PHÂN CHƯƠNG BỘ NHỚ 2. Phân chương động . Tránh phân mảnh trong . Gây phân mảnh ngoài: dồn những vùng trống nhỏ thành lớn (nén) . Sử dụng các chiến lược cấp chương . Chọn vùng thích hợp đầu tiên . Vùng thích hợp nhất . Vùng không thích hợp nhất www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 40 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 20
21. 6/25/2014 PHÂN TRANG BỘ NHỚ 1. Khái niệm phân trang . Bộ nhớ vật lý được chia thành các khối nhỏ, kích thước cố định và bằng nhau gọi là khung trang (page frame) . Không gian địa chỉ logic của tiến trình được chia thành những khối gọi là trang (page), có kích thước bằng khung www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 41 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 PHÂN TRANG BỘ NHỚ 1. Khái niệm phân trang . Tiến trình được cấp các khung để chứa các trang của mình. . Các trang có thể chứa trong các khung nằm rải rác trong bộ nhớ www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 42 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 21
22. 6/25/2014 PHÂN TRANG BỘ NHỚ 1. Khái niệm phân trang . HDH quản lý việc cấp phát khung cho mỗi tiến trình bằng bảng trang (bảng phân trang): mỗi ô tương ứng với 1 trang và chứa số khung cấp cho trang đó . Mỗi tiến trình có bảng trang riêng . Duy trì danh sách các khung trống trong MEM www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 43 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 PHÂN TRANG BỘ NHỚ 1. Khái niệm phân trang . Tương tự như phân chương cố định: khung tương tự chương, kích thước và vị trí không thay đổi . Tuy nhiên kích thước các phần tương đối nhỏ và các phần cho 1 tiến trình không cần liên tục nhau . Không có phân mảnh ngoài . Có phân mảnh trong www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 44 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 22
23. 6/25/2014 PHÂN ĐOẠN BỘ NHỚ 1. Khái niệm . Chương trình thường được chia thành nhiều phần: dữ liệu, lệnh, ngăn xếp . Chia chương trình thành các đoạn theo cấu trúc logic . Mỗi đoạn được phân vào 1 vùng nhớ, có kích thước không bằng nhau . Mỗi đoạn tương ứng với không gian địa chỉ riêng, được phân biệt bởi tên (STT) và độ dài của mình . Các vùng nhớ thuộc các đoạn khác nhau có thể nằm ở vị trí khác nhau www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 45 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 PHÂN ĐOẠN BỘ NHỚ 1. Khái niệm . Giống phân chương động: bộ nhớ được cấp phát theo từng vùng kích thước thay đổi . Khác phân chương động: chương trình có thể chiếm nhiều hơn 1 đoạn và không cần liên tiếp nhau trong MEM . Tránh hiện tượng phân mảnh trong . Có phân mảnh ngoài . Dễ sắp xếp bộ nhớ . Dễ chia sẻ các đoạn giữa các tiến trình khác nhau . Kích thước mỗi đoạn có thể thay đổi mà không ảnh hưởng tới các đoạn khác www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 46 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 23
24. 6/25/2014 PHÂN ĐOẠN BỘ NHỚ 2. Kết hợp phân trang và Phân đoạn . Phân đoạn chương trình, mỗi đoạn sẽ tiến hành phân trang . Địa chỉ gồm: số thứ tự đoạn, số thự tự trang, độ dịch trong trang . Tiến trình có 1 bảng phân đoạn, mỗi đoạn có 1 bảng phân trang www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 47 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BỘ NHỚ ẢO 1. Khái niệm . Tiến trình có thể chia thành các phần nhỏ nằm rải rác trong bộ nhớ . Tất cả các phép biến đổi là trong suốt với người dùng và người lập trình chỉ làm việc với không gian nhớ logic . Không phải tiến trình nào khi chạy cũng sử dụng tất cả các lệnh và dữ liệu của mình với tần số như nhau . => không nhất thiết toàn bộ các trang/ đoạn của một tiến trình phải có mặt đồng thời trong bộ nhớ khi tiến trình chạy . => Các trang hoặc đoạn có thể được trao đổi từ đĩa vào bộ nhớ khi có nhu cầu truy cập tới www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 48 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 24
25. 6/25/2014 BỘ NHỚ ẢO 1. Khái niệm . Việc thực hiện các tiến trình chỉ nằm một phần trong bộ nhớ có một số ưu điểm: . Có thể viết chương trình có kích thước lớn hơn kích thước thực của MEM . Cùng 1 lúc nhiều tiến trình cùng được tải vào MEM hơn . => Bộ nhớ ảo là bộ nhớ lôgic theo cách nhìn của người lập trình và tiến trình và không bị hạn chế bởi bộ nhớ thực. . Bộ nhớ ảo có thể lớn hơn bộ nhớ thực rất nhiều và bao gồm cả không gian trên đĩa . Bộ nhớ ảo thường được xây dựng dựa trên phương pháp phân trang trong đó các trang là đơn vị để nạp từ đĩa vào khi cần www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 49 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BỘ NHỚ ẢO 2. Nạp trang theo nhu cầu . Tiến trình được phân trang và chứa trên đĩa . Khi cần thực hiện, nạp tiến trình vào MEM: chỉ nạp những trang cần dùng . Tiến trình gồm các trang trên đĩa và trong MEM: thêm bit P trong khoản mục bảng trang để phân biệt (P=1: đã nạp vào MEM) 0 1 0 A Bit P 2 1 B Khung 3 2 C 4 A 0 4 1 3 D 1 0 5 A B 2 6 1 4 E 6 C C D E 3 0 F G H 5 F 4 0 7 5 9 1 6 G 8 6 0 7 H 7 0 9 F Bộ nhớ logic Bảng trang 10 Đĩa 11 12 Bộ nhớ vật lý www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 50 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 25
26. 6/25/2014 BỘ NHỚ ẢO 2. Nạp trang theo nhu cầu . Quá trình kiểm tra và nạp trang: . Tiến trình truy cập tới 1 trang, kiểm tra bit P. Nếu P=1, truy cập diễn ra bình thường. Nếu P=0, xảy ra sự kiện thiếu trang 3 • Ngắt xử lý thiếu trang: Hệ điều hành • HDH tìm 1 khung trống 0 1 trong MEM 2 0 A 2 . 1 Đọc trang bị thiếu vào 1 B 3 0 4 1 khung trang vừa tìm được 2 C 0 4 A 2 6 1 3 D 5 . Sửa lại khoản mục tương 3 0 A B ứng trong bảng trang: đổi 4 E 4 0 6 C C D E 5 9 1 F G H 5 F 7 bit P=1 và số khung đã cấp 6 0 6 G 7 0 8 4 cho trang Bảng trang 7 H 9 F . Khôi phục lại trạng thái Bộ nhớ logic 10 Đĩa 5 tiến trình và thực hiện tiếp 11 lệnh bị ngắt 12 Bộ nhớ vật lý www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 51 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BỘ NHỚ ẢO 3. Đổi trang . Bộ nhớ ảo > bộ nhớ thực và chế độ đa chương trình -> có lúc không còn khung nào trống để nạp trang mới . Giải pháp: . Kết thúc tiến trình . Trao đổi tiến trình ra đĩa và chờ thời điểm thuận lợi hơn . Đổi trang www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 52 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 26
27. 6/25/2014 BỘ NHỚ ẢO 3.1. Thao tác đổi trang . Nếu không còn khung nào trống, HDH chọn 1 khung đã cấp phát nhưng hiện không dùng tới và giải phóng nó . Quá trình đổi trang: . B1: Xác định trang cần nạp vào trên đĩa . B2: Nếu có khung trống thì chuyển sang B4 . B3: . Lựa chọn 1 khung để giải phóng, theo 1 thuật toán nào đó . Ghi nội dung khung bị đổi ra đĩa (nếu cần), cập nhật bảng trang và bảng khung . B4: Đọc trang cần nạp vào khung vừa giải phóng; cập nhật bảng trang và bảng khung . B5: Thực hiện tiếp tiến trình từ điểm bị dừng trước khi đổi trang www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 53 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BỘ NHỚ ẢO 3.2 Các chiến lược đổi trang . Đổi trang tối ưu (OPT): . Chọn trang sẽ không được dùng tới trong khoảng thời gian lâu nhất để đổi . Cho phép giảm tối thiểu sự kiện thiếu trang và do đó là tối ưu theo tiêu chuẩn này . HDH không đoán trước được nhu cầu sử dụng các trang trong tương lai . => không áp dụng trong thực tế mà chỉ để so sánh với các chiến lược khác 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2 2 4 4 4 2 2 2 OPT 3 3 3 3 3 3 3 3 3 3 3 1 5 5 5 5 5 5 5 5 F F F www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 54 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 27
28. 6/25/2014 BỘ NHỚ ẢO 3.2 Các chiến lược đổi trang . Vào trước ra trước (FIFO): . Trang nào được nạp vào trước thì bị đổi ra trước . Đơn giản nhất . Trang bị trao đổi là trang nằm lâu nhất trong bộ nhớ 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 5 5 5 5 3 3 3 3 FIFO 3 3 3 3 2 2 2 2 2 5 5 1 1 1 4 4 4 4 4 2 F F F F F F www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 55 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 BỘ NHỚ ẢO 3.2 Các chiến lược đổi trang . Đổi trang ít sử dụng nhất trong thời gian cuối (LRU): . Trang bị đổi là trang mà thời gian từ lần truy cập cuối cùng đến thời điểm hiện tại là lâu nhất . Theo nguyên tắc cục bộ về thời gian, đó chính là trang ít có khả năng sử dụng tới nhất trong tương lai . Thực tế LRU cho kết quả tốt gần như phương pháp đổi trang tối ưu 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2 2 2 2 3 3 3 3 LRU 3 3 3 5 5 5 5 5 5 5 5 1 1 1 4 4 4 2 2 2 F F F F www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 56 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 28
29. 6/25/2014 QUẢN LÝ TIẾN TRÌNH www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 57 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CÁC KHÁI NIỆM LIÊN QUAN ĐẾN TIẾN TRÌNH 1. Tiến trình là gì? . Tiến trình là một chương trình đang trong quá trình thực hiện Chương trình Tiến trình Thực thể tĩnh Thực thể động Không sở hữu tài nguyên cụ Được cấp một số tài nguyên thể để chứa tiến trình và thực hiện lệnh . Tiến trình được sinh ra khi chương trình được tải vào bộ nhớ để thực hiện . Tiến trình người dùng . Tiến trình hệ thống www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 58 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 29
30. 6/25/2014 CÁC KHÁI NIỆM LIÊN QUAN ĐẾN TIẾN TRÌNH 2. Trạng thái của tiến trình . Phân biệt theo 2 trạng thái: chạy và không chạy . => Không phản ánh đầy đủ thông tin về trạng thái tiến trình . => Mô hình 5 trạng thái: mới khởi tạo, sẵn sàng, chạy, chờ đợi, kết thúc . Mới khởi tạo: tiến trình đang được Điều độ tạo ra CPU Mới Sẵn Chạy Kết . Sẵn sàng: tiến trình chờ được cấp khởi sàng thúc tạo CPU để thực hiện lệnh của mình Ngắt . Kết thúc Vào/ra hoặc Chạy: lệnh của tiến trình được CPU vào/ra chờ sự kiện thực hiện Chờ đợi . Chờ đợi: tiến trình chờ đợi một sự kiện gì đó xảy ra (blocked) . Kết thúc: tiến trình đã kết thúc việc thực hiện nhưng vẫn chưa bị xóa www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 59 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CÁC KHÁI NIỆM LIÊN QUAN ĐẾN TIẾN TRÌNH 3. Thông tin mô tả tiến trình . Được lưu trong một cấu trúc dữ liệu gọi là khối quản lý tiến trình - PCB (Process Control Block) . Các thông tin chính trong PCB: . Số định danh của tiến trình (PID) . Trạng thái tiến trình . Nội dung một số thanh ghi CPU: . Thanh ghi con trỏ lệnh: trỏ tới lệnh tiếp theo . Thanh ghi con trỏ ngăn xếp . Các thanh ghi điều kiện và trạng thái . Các thanh ghi đa năng www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 60 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 30
31. 6/25/2014 CÁC KHÁI NIỆM LIÊN QUAN ĐẾN TIẾN TRÌNH 3. Thông tin mô tả tiến trình . PCB: . Thông tin phục vụ điều độ tiến trình: mức độ ưu tiên của tiến trình, vị trí trong hàng đợi, . Thông tin về bộ nhớ của tiến trình . Danh sách các tài nguyên khác: các file đang mở, thiết bị vào ra mà tiến trình sử dụng . Thông tin thống kê phục vụ quản lý: thời gian sử dụng CPU, giới hạn thời gian www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 61 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 CÁC KHÁI NIỆM LIÊN QUAN ĐẾN TIẾN TRÌNH 4. Bảng và danh sách tiến trình . Sử dụng bảng tiến trình chứa con trỏ tới PCB của toàn bộ tiến trình có trong hệ thống . PCB của các tiến trình cùng trạng thái hoặc cùng chờ 1 tài nguyên nào đó được liên kết thành 1 danh sách Đang chạy PCB Bảng tiến trình Con trỏ tới PCB 1 bảng tiến trình Tiến trình 1 Tiến trình 2 Sẵn sàng PCB PCB PCB Tiến trình 3 . Tiến trình n PCB n PCB PCB Chờ đợi đọc đĩa www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 62 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 31
32. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 1. Khái niệm điều độ . Điều độ (scheduling) hay lập lịch là quyết định tiến trình nào được sử dụng tài nguyên phần cứng khi nào, trong thời gian bao lâu . Tập trung vào vấn đề điều độ đối với CPU . => Quyết định thứ tự và thời gian sử dụng CPU . Điều độ tiến trình và điều độ dòng: . Hệ thống trước kia: tiến trình là đơn vị thực hiện chính => điều độ thực hiện với tiến trình . Hệ thống hỗ trợ dòng: dòng mức nhân là đơn vị HDH cấp CPU . => Sử dụng thuật ngữ điều độ tiến trình rộng rãi  điều độ dòng www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 63 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 2. Các dạng điều độ 1. Điều độ dài hạn và ngắn hạn . Điều độ dài hạn: . Thực hiện khi mới tạo ra tiến trình . HDH quyết định tiến trình có được thêm vào danh sách đang hoạt động? . Ảnh hưởng tới mức độ đa chương trình . Điều độ trung hạn: Điều độ dài hạn . Quyết định tiến trình có được Điều độ ngắn hạn cấp MEM để thực hiện? Mới Sẵn Chạy Kết khởi sàng thúc . Điều độ ngắn hạn: tạo Điều độ trung hạn . Quyết định tiến trình nào được cấp CPU để thực hiện Chờ . Thực hiện với tiến trình ở đợi trạng thái sẵn sàng www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 64 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 32
33. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 2. Các dạng điều độ (tt) 2. Điều độ có phân phối lại và không phân phối lại: . Điều độ có phân phối lại (preemptive): . HDH có thể sử dụng cơ chế ngắt để thu hồi CPU của một tiến trình đang trong trạng thái chạy . Điều độ không phân phối lại (nonpreemptive): . Tiến trình đang ở trạng thái chạy sẽ được sử dụng CPU cho đến khi xảy ra một trong các tình huống sau: . Tiến trình kết thúc . Tiến trình phải chuyển sang trạng thái chờ đợi do thực hiện I/O . => Điều độ hợp tác: chỉ thực hiện được khi tiến trình hợp tác và nhường CPU . Nếu tiến trình không hợp tác, dùng CPU vô hạn => các tiến trình khác không được cấp CPU www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 65 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 2. Các dạng điều độ (tt) 2. Điều độ có phân phối lại: . HDH chủ động hơn, không phụ thuộc vào hoạt động của tiến trình . Đảm bảo chia sẻ thời gian thực sự . Đòi hỏi phần cứng có bộ định thời gian và một số hỗ trợ khác . Vấn đề quản lý tiến trình phức tạp hơn www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 66 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 33
34. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 3. Các tiêu chí điều độ 1. Lượng tiến trình được thực hiện xong: . Số lượng tiến trình thực hiện xong trong 1 đơn vị thời gian . Đo tính hiệu quả của hệ thống 2. Hiệu suất sử dụng CPU 3. Thời gian vòng đời trung bình của tiến trình: . Từ lúc có yêu cầu tạo tiến trình đến khi kết thúc 4. Thời gian chờ đợi: . Tổng thời gian tiến trình nằm trong trạng thái sẵn sàng và chờ cấp CPU . Ảnh hưởng trực tiếp của thuật toán điều độ tiến trình www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 67 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 3. Các tiêu chí điều độ (tt) 5. Thời gian đáp ứng 6. Tính dự đoán được: . Vòng đời, thời gian chờ đợi, thời gian đáp ứng phải ổn định, không phụ thuộc vào tải của hệ thống 7. Tính công bằng . Các tiến trình cùng độ ưu tiên phải được đối xử như nhau www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 68 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 34
35. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ 1. Thuật toán đến trước phục vụ trước (FCFS): . Tiến trình yêu cầu CPU trước sẽ được cấp trước . HDH xếp các tiến trình sẵn sàng vào hàng đợi FIFO . Tiến trình mới được xếp vào cuối hàng đợi . Đơn giản, đảm bảo tính công bằng . Thời gian chờ đợi trung bình lớn . => Ảnh hưởng lớn tới hiệu suất chung của toàn hệ thống . Thường là thuật toán điều độ không phân phối lại www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 69 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ (tt) 2. Điều độ quay vòng (RR: round robin): . Sửa đổi FCFS dùng cho các hệ chia sẻ thời gian . Có thêm cơ chế phân phối lại bằng cách sử dụng ngắt của đồng hồ . Hệ thống xác định những khoảng thời gian nhỏ gọi là lượng tử/ lát cắt thời gian t . Khi CPU được giải phóng, HDH đặt thời gian của đồng hồ bằng độ dài lượng tử, lấy tiến trình ở đầu hàng đợi và cấp CPU cho nó . Tiến trình kết thúc trước khi hết thời gian t: trả quyền điều khiển cho HDH www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 70 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 35
36. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ (tt) 2. Điều độ quay vòng (tt) . Hết lượng tử thời gian mà tiến trình chưa kết thúc: . Đồng hồ sinh ngắt . Tiến trình đang thực hiện bị dừng lại . Quyền điều khiển chuyển cho hàm xử lý ngắt của HDH . HDH chuyển tiến trình về cuối hàng đợi, lấy tiến trình ở đầu và tiếp tục . Cải thiện thời gian đáp ứng so với FCFS . Thời gian chờ đợi trung bình vẫn dài . Lựa chọn độ dài lượng tử thời gian? www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 71 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ (TT) 3. Điều độ ưu tiên tiến trình ngắn nhất (SPF) . Chọn trong hàng đợi tiến trình có chu kỳ sử dụng CPU tiếp theo ngắn nhất để phân phối CPU . Nếu có nhiều tiến trình với chu kỳ CPU tiếp theo bằng nhau, chọn tiến trình đứng trước . Thời gian chờ đợi trung bình nhỏ hơn nhiều so với FCFS . Khó thực hiện vì phải biết độ dài chu kỳ CPU tiếp: . Trong các hệ thống xử lý theo mẻ: dựa vào thời gian đăng kí tối đa do lập trình viên cung cấp . Dự đoán độ dài chu kỳ CPU tiếp theo: dựa trên độ dài TB các chu kỳ CPU trước đó . Không có phân phối lại www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 72 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 36
37. 6/25/2014 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ (tt) 4. Điều độ ưu tiên thời gian còn lại ngắn nhất . SFP có thêm cơ chế phân phối lại (SRTF) . Khi 1 tiến trình mới xuất hiện trong hàng đợi, HDH so sánh thời gian còn lại của tiến trình đang chạy với thời gian còn lại của tiến trình mới xuất hiện . Nếu tiến trình mới xuất hiện có thời gian còn lại ngắn hơn, HDH thu hồi CPU của tiến trình đang chạy, phân phối cho tiến trình mới . Thời gian chờ đợi trung bình nhỏ . HDH phải dự đoán độ dài chu kỳ CPU của tiến trình . Việc chuyển đổi tiến trình ít hơn so với RR www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 73 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 ĐIỀU ĐỘ TIẾN TRÌNH 4. Các thuật toán điều độ (tt) 5. Điều độ có mức ưu tiên . Mỗi tiến trình có 1 mức ưu tiên . Tiến trình có mức ưu tiên cao hơn sẽ được cấp CPU trước . Các tiến trình có mức ưu tiên bằng nhau được điều độ theo FCFS . Mức ưu tiên được xác định theo nhiều tiêu chí khác nhau www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH Trang 74 BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1 37