1
GIỚI THIỆU KHOA HỌC MÁY TÍNH
CHƯƠNG 3 – HỆ ĐIỀU HÀNH
NGUYỄN THANH TRUNG
2
Mục tiêu
Giới thiệu tổng quan về hệ điều hành gồm: HĐH là gì, chức năng của HĐH, phân loại và những HĐH phổ biến,...
Trình bày những kiến thức cơ bản về nguyên lý hoạt động cũng cấu trúc bên trong của HĐH.
Giúp sinh viên biết được tầm quan trọng của HĐH cũng như việc lựa chọn HĐH cho phù hợp với mục tiêu sử dụng.
3
Bố cục
3.1. Lịch sử các hệ điều hành
3.2. Tổ chức và hoạt động
3.3. Cơ chế bảo vệ thông tin của HĐH
4
Tài liệu tham khảo
Chương 3, Computer Science
Chương 3, bài giảng Giới thiệu Khoa học Máy tính.
Tham khảo Bài giảng Hệ điều hành, Đại học Khoa học Tự nhiên (ebook)
5
Khái niệm
Lịch sử phát triển
Chức năng
Phân loại
3.1. Tổng quan hệ điều hành
6
Hệ điều hành là một chương trình chạy trên máy tính, dùng để điều hành, quản lý các thiết bị phần cứng và các tài nguyên phần mềm trên máy tính.
Đóng vai trò trung gian trong việc giao tiếp giữa người sử dụng và phần cứng máy tính, cung cấp một môi trường cho phép người sử dụng phát triển và thực hiện các ứng dụng của họ một cách dễ dàng.
3.1.1 Khái niệm
7
3.1.2.Lịch sử Hệ điều hành
Theo các giai đoạn phát triển
Thế hệ I: Chưa có HĐH, thao tác bằng tay trên bảng điều khiển.
Thế hệ II: Hệ thống xử lý theo lô, gồm thực hiện các yêu cầu trên băng từ 1 cách tuần tự.
Thế hệ III: Hệ điều hành đầu tiên gồm nhiều dòng lệnh hợp ngữ; HĐH đa chương (bộ nhớ chia thành nhiều phần chứa các công việc khác nhau); HĐH chia sẻ thời gian… trên máy mainframe, mini,…
Thế hệ IV: Với sự ra đời máy tính cá nhân, nhiều HĐH: HĐH đa nhiệm, HĐH Mạng, HĐH phân tán … ra đời
8
3.1.3.Chức năng
Quản lý chia sẻ tài nguyên
Tài nguyên của hệ thống (CPU, bộ nhớ, thiết bị ngoại vi, ...) … hệ điều hành cần phải có cơ chế và chiến lược thích hợp để quản lý việc phân phối tài nguyên.
Ngoài yêu cầu dùng chung tài nguyên để tiết kiệm chi phí, người sử dụng còn cần phải chia sẻ thông tin (tài nguyên phần mềm) lẫn nhau, khi đó hệ điều hành cần đảm bảo việc truy xuất đến các tài nguyên này là hợp lệ, không xảy ra tranh chấp, thiếu nhất quán ...
9
Giả lập máy tính mở rộng
Hệ điều hành làm ẩn đi các chi tiết phần cứng, người sử dụng được cung cấp 1 giao diện đơn giản, dễ hiểu và không phụ thuộc vào thiết bị cụ thể.
Thực tế, ta có thể xem Hệ điều hành như là 1 hệ thống bao gồm nhiều máy tính trừu tượng xếp thành nhiều lớp chồng lên nhau, máy tính mức dưới phục vụ cho máy tính mức trên. Lớp trên cùng là giao diện trực quan nhất để chúng ta điều khiển.
Ngoài ra có thể chia theo 4 chức năng sau : Quản lý tiến trình (process management), Quản lý bộ nhớ (memory management) Quản lý hệ thống lưu trữ (storage management) Giao tiếp với người dùng (user interaction)
10
Một số nhiệm vụ cụ thể
Điều khiển và quản lý trực tiếp các phần cứng như bo mạch chủ, bo mạch đồ họa và bo mạch âm thanh,...
Thực hiện một số thao tác cơ bản trong máy tính như các thao tác đọc, viết tập tin, quản lý hệ thống tập tin (file system) và các kho dữ liệu.
Cung ứng một hệ thống giao diện sơ khai cho các ứng dụng thường là thông qua một hệ thống thư viện các hàm chuẩn để điều hành các phần cứng mà từ đó các ứng dụng có thể gọi tới.
Cung ứng một hệ thống lệnh cơ bản để điều hành máy. Các lệnh này gọi là lệnh hệ thống (system command).
Ngoài ra cũng cung cấp các dịch vụ cơ bản cho các phần mềm ứng dụng ...
11
3.1.4.Phân loại các HĐH
Theo loại máy tính
Hệ điều hành dành cho máy MainFrame
Hệ điều hành dành cho máy Server
Hệ điều hành dành cho máy nhiều CPU
Hệ điều hành dành cho máy tính cá nhân (PC)
Hệ điều hành dành cho máy PDA (Embedded OS - hệ điều hành nhúng)
Hệ điều hành dành cho máy chuyên biệt
Hệ điều hành dành cho thẻ chíp (SmartCard)
12
Dưới góc độ số chương trình được sử dụng cùng lúc
Hệ điều hành đơn nhiệm
Hệ điều hành đa nhiệm
Dưới góc độ người dùng (truy xuất tài nguyên cùng lúc)
Một người dùng
Nhiều người dùng
13
Dưới góc độ hình thức xử lý
Hệ thống xử lý theo lô
Hệ thống chia sẻ
Hệ thống song song
Hệ thống phân tán
Hệ thống xử lý thời gian thực
14
3.2.TỔ CHỨC VÀ HOẠT ĐỘNG
Cấu trúc HĐH
Phân chia thời gian
Phân phối tài nguyên
Các kiến trúc HĐH
15
Kiến trúc phân lớp của HĐH
Phân loại phần mềm
Phần mềm hệ thống
Phần mềm ứng dụng
Hệ điều hành
Shell
Kernel
Kernel
Shell
User
16
shell
GUI (Graphical User Interface)
EX: Windows Manager
Thông dịch dòng lệnh
17
Kernel
File Manager
Device Driver
Memory Manager
Schedule
Dispatcher
18
3.2.1.Cấu trúc HĐH
Đơn vị xử lý câu lệnh (Command Processor)
Bộ lập lịch (Scheduler)
Đơn vị quản lý tập tin, ql tài nguyên
Đơn vị ql bộ nhớ
Bộ điều phối (Dispatcher)
19
Đơn vị xử lý câu lệnh
Giúp HĐH giao tiếp với người dùng
Thông qua các thiết bị nhập/xuất
Khi nhận lệnh hợp lệ và tìm thấy yêu cầu xử lý của chương trình  yêu cầu bộ lập lịch sắp xếp các câu lệnh.
20
Đơn vị quản lý tập tin và đơn vị quản lý bộ nhớ
Trước khi chương trình được bộ lập lịch chia lịch thực hiện thì bộ lập lịch cũng liên lạc với 2 dịch vụ khác đó là đơn vị quản lý tập tin và đơn vị quản lý bộ nhớ.
đơn vị quản lý tập tin: Cung cấp thông tin liên quan đến dữ liệu trong khối lưu trữ; bảo vệ tập tin trong khối lưu trữ tránh việc truy cập bất hợp pháp.
đơn vị quản lý bộ nhớ: Phân chia việc sử dụng bộ nhớ chính, cấp phát/thu hồi vùng nhớ.
21
Đơn vị quản lý tài nguyên
Quản lý, phân phối các tài nguyên.
Phối hợp với Bộ lập lịch phân chia tài nguyên cho các tiến trình để tránh việc tranh chấp tài nguyên…
VD: Nếu 1 tiến trình xử lý cần 1 tài nguyên mà không thể cung cấp được thì đơn vị quản lý tài nguyên sẽ thông báo cho Bộ lập lịch biết. Còn ngược lại thì nó sẽ cấp tài nguyên cho tiến trình này  tiến trình được lập lịch và thực hiện.
22
Bộ lập lịch
Sắp xếp việc thực hiện các chương trình (tiến trình).
Vd: đối với hệ thống xử lý theo lô thì chương trình sẽ được đưa vào hàng đợi theo độ ưu tiên của chương trình.
Đối với hệ thống đa nhiệm thì nó yêu cầu chương trình phối hợp với các họat động khác cùng phân chia thời gian.
Các họat động khác cùng phân chia thời gian này thực chất là các tiến trình.

23
bộ điều phối (dispatcher)
Điều phối các tiến trình: Lựa chọn các tiến trình đang quan tâm trong số các tiến trình đã được lập lịch…
Đơn vị xử lý câu lệnh
Bộ lập lịch
Đơn vị ql tập tin, tài nguyên
Đơn vị ql bộ nhớ
Bộ điều phối
24
3.2.2. Các nguyên lý cơ bản của phân chia thời gian
Điều khiển ngắt
Cấp phát thời gian: Cho 2 tiến trình được lập lịch là A và B, giả sử A thực hiện được 1 khoảng thời gian thì bị ngắt bởi bộ điều phối  thực hiện B, sau 1 khoảng thời gian B bị ngắt  thực hiện A,….
Như vậy, bằng cách điều khiển ngắt mà bộ điều phối có thể cho phép thực hiện xoay vòng nhiều tiến trình trong 1 khoảng thời gian gọi là kỹ thuật xoay vòng.
25
VD1: trong 1 máy tính thực hiện xoay vòng khoảng 50 tiến trình, khoảng thời gian thực hiện mỗi tiến trình khoảng 10 – 100 miligiây… cảm giác nhiều tiến trình được thực hiện đồng thời.
VD2: Một máy tính đa người dùng, thì HĐH tạo ra mỗi người dùng 1 máy ảo được tạo ra theo cách phân chia thời gian như vậy.
Ngoài ra các tiến trình có thể có sự ưu tiên khác nhau.
26
3.2.3.Phân phối tài nguyên
a. Điều phối tài nguyên
Tài nguyên có 2 loại: phân chia được và không phân chia được. (VD)
Nguyên tắc:
Tạo Bộ phân phối và thu hồi các tài nguyên
Các ttiến trình trong môi trường đa xử lý không được phép liên lạc trực tiếp với các ngoại vi mà phải thông qua HĐH
Gán cờ hiệu cho tài nguyên (0/1)
27
b. Deadlock
Deadlock là gì? Đợi 1 sự kiện không bao giờ xảy ra.
Ví dụ:
Phân tích: Deadlock xuất hiện khi thoả cả 3 đk sau:
Có sự cạnh tranh ở các tài nguyên không thể chia.
Những tài nguyên bị yêu cầu trên từng phần cơ bản; để kết thúc và nhận lại 1 số tài nguyên từ 1 tiến trình thì phải cung cấp cho nó 1 số tài nguyên khác.
Một lần 1 tài nguyên bị phân chia, nó không thể yêu cầu sử dụng lại.
28
Xử lý Deadlock
Bỏ đi 1 tiến trình nào đó gây ra vấn đề trên.
Chuyển các tài nguyên không phân chia  có thể phân chia. VD: kỹ thuật Spooling khi in dữ liệu.
29
3.3. Quản lý tiến trình
Các máy tính ngày nay đều có khả năng xử lý đồng thời nhiều chương trình, nhưng thiết bị phần cứng chỉ có 1 cho nên HĐH thiết kế mô hình song song giả lập để xử lý 1 lúc nhiều chương trình  mỗi chương trình này  Tiến trình.
30
Tiến trình (Process)
Là ctrình đang xử lý
Sở hữu 1 con trỏ lệnh, tập các thanh ghi, và các biến.
Cần 1 số tài nguyên: CPU, memory, các tập tin, và thiết bị xuất/nhập.
Khác với chương trình-xem như thực thể thụ động thì tiến trình xem như thực thể tích cực, có thể tương tác, thay đổi trạng thái…
31
Các trạng thái của ttrình
Khởi tạo: ttrình được tạo lập
Ready: ttrình chờ được cấp phát tài nguyên để xử lý
Running: các lệnh của ttrình đang được xử lý.
Blocked: ttrình chờ cấp phát tài nguyên, hay chờ 1 sự kiện xảy ra.
Kết thúc: ttrình hoàn tất xử lý.
32
Chuyển trạng thái của ttrình
Khởi tạo
Kết thúc
Ready
Running
Blocked
(1)
(5)
(3)
(2)
(6)
(4)
33
Chuyển đổi trạng thái của ttrình
(1): ttrình mới tạo được đưa vào hệ thống.
(2): Bộ điều phối cấp phát cho ttrình 1 khoảng thời gian sử dụng CPU.
(3): ttrình kết thúc.
(4): ttrình yêu tài nguyên nhưng chưa được đáp ứng; hoặc phải chờ 1 sự kiện hay thao tác xuất/nhập.
(5): Bộ điều phối chọn ttrình khác để cho xử lý.
(6): tài nguyên yêu cầu đã sẵn sàng; hoặc sự kiện hay tao tác xuất/nhập đã hoàn tất.
34
Điều phối tiến trình
Chia sẻ thời gian – để chuyển đổi CPU qua lại giữa các ttrình.
Bộ phân phối (dispatcher)
Lựa chọn ttrình để xử lý tiếp theo.
Chuyển ngữ cảnh (context).
Mục tiêu điều phối (scheduling)
Sự công bằng (fairness)
Hiệu quả (efficiency)
Thời gian đáp ứng hợp lý (response time)
Thời gian lưu lại hệ thống (turnaround time)
Thông lượng tối đa (throughput)
35
Cơ chế điều phối của HĐH
Điều phối độc quyền (preemptive)
Ttrình nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU.
Quyết định điều phối xảy ra khi:
Ttrình chuyển từ tthái running sang blocked
Ttrình kết thúc
36
Cơ chế điều phối của HĐH (tt)
Điều phối không độc quyền (non-preemptive)
Ttrình nhận được CPU vẫn được sử dụng CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU.
Nhưng ttrình khác có độ ưu tiên có thể dành quyền sử dụng CPU.
Quyết định điều phối xảy ra khi:
Ttrình chuyển từ tthái running sang blocked
Ttrình chuyền từ running sang ready
Ttrình chuyền từ blocked sang ready
Ttrình kết thúc
37
Interval timer/ interrupting clock
HĐH sử dụng một bộ đếm thời gian / đồng hồ ngắt giờ
Khoảng thời gian t thích hợp ứng với 1 lượt cấp phát CPU cho 1 ttrình.
Sau khoảng thời gian t xảy ra ngắt báo hiệu hết thời gian xử lý của ttrình hiện hành. Khi đó, HĐH được kích hoạt, và bộ điều phối sẽ quyết định ttrình nào sẽ được cấp phát CPU trong lượt kế tiếp.
38
Độ ưu tiên của tiến trình
Được gán bởi hệ thống hay gán tường minh bởi user.
Độ ưu tiên tĩnh: không thay đổi bất kể sự biến động của môi trường.
Độ ưu tiên động: thay đổi theo thời gian và môi trường xử lý
39
Tổ chức điều phối
Danh sách sẵn sàng (ready list) chứa các ttrình đã được nạp vào bộ nhớ chính và ở trạng thái sẵn sàng (ready) tiếp nhận CPU.
Danh sách chờ đợi (waiting list): chứa các ttrình chờ đợi 1 thao tác xuất nhập hoàn tất, yêu cầu tài nguyên chưa được thoả mãn, yêu cầu tạm dừng
Mỗi tài nguyên (tbị ngoại vi) có danh sách chờ đợi riêng bao gồm các ttrình đang chờ được cấp tài nguyên đó.
40
Các danh sách điều phối
head
trail
Ready list
PCB2
PCB5
head
trail
Resource 1
PCB1
head
trail
Resource 2
PCB8
PCB8
41
Sơ đồ chuyển đổi giữa các danh sách điều phối
Ready list
Waiting list
Yêu cầu
hết
Đợi 1 ngắt
Ngắt
I/O
CPU
42
Các cấp độ điều phối
Điều phối theo tác vụ (job scheduling)
Quyết định lựa chọn tác vụ nào đưa vào hệ thống và nạp những ttrình của tác vụ đó vào bộ nhớ chính.
Tạo lập 1 ttrình hay có 1 ttrình kết thúc: kích hoạt chức năng điều phối tác vụ mới.
Chức năng điều phối tác vụ có tần xuất hoạt động thấp do tính đa chương tương đối ổn định.
Cần phân biệt ttrình theo hướng xuất/nhập hay hướng xử lý.
Cân bằng hoạt động CPU và tbị ngoại vi: pha trộn hợp lý giữa các ttrình hướng xuất/nhập và hướng xử lý.

43
Các cấp độ điều phối (tt)
Điều phối theo tiến trình (process scheduling)
Quyết định chọn 1 ttrình ở trạng thái sẵn sàng.
Có tần xuất hoạt động cao do bị ngắt (đồng hồ, tbị ngoại vi…)
Cấp độ điều phối trung gian: Kết hợp 2 cấp độ điều phối theo tác vụ và theo tiến trình
44
Các chiến lược điều phối
Chiến lược FIFO
Chiến lược phân phối xoay vòng (round robin)
Chiến lược điều phối theo độ ưu tiên
Chiến lược theo công việc ngắn nhất (shortest-Job-First) SJF
Chiến lược điều phối theo nhiều mức độ ưu tiên …
45
Khối điều khiển tiến trình
Process Control Block –PCB
HĐH quản lý tiến trình thông qua PCB
PCB là 1 cấu trúc gồm nhiều trường:
Định danh tiến trình: Pid
Trạng thái tiến trình:
Ngữ cảnh
Thông tin giao tiếp
Thông tin thống kê
46
Khối điều khiển ttrình
status
pid
Waiting/waiting list
CPU-state-res
Processor
Main store
Resource
Created resource
Parent
Progency
Priority
CPU time
Unit 1
Unit 2
RCB 1
RCB 2
RCB 1
RCB 2
PCB
PCB 1
PCB 2
…
Ngữ cảnh của ttrình
Thông tin giao tiếp
Thông tin thống kê
Trạng thái ttrình
Định danh ttrình
47
Giải thích
Định danh tiến trình giúp phân biệt các tiến trình khác nhau.
Trạng thái tiến trình là tình trạng hiện tại của tiến trình.
Ngữ cảnh tiến trình chứa các thông tin về tài nguyên của tiến trình gồm:
Trạng thái CPU: Registers, IP
CPU trong trường hợp máy có nhiều CPU
Memory
Tài nguyên sử dụng: danh sách các tài nguyên hệ thống mà tiến trình sử dụng
Tài nguyên tạo lập: danh sách các tài nguyên được tiến trình tạo lập
48
Thông tin giao tiếp: Thông tin về quan hệ giữa tiến trình này vơí các tiến trình khác
Tiến trình cha: Tạo ra tiến trình này
Tiến trình con: Do nó tạo ra
Độ ưu tiên: Để bộ điều phối xác định chế độ ưu tiên
Thông tin thống kê: Thông tin thống kê hoạt động của tiến tình (thời gian sử dụng CPU, thời gian chờ, …)
49
Tiểu trình (thread) & Tiến trình (Process)
Một tiến trình: Có Không gian địa chỉ riêng, chỉ 1 dòng xử lý
Các tiến trình độc lập liên lạc với nhau thông qua cơ chế do HĐH cung cấp.
Mong muốn nhiều dòng xử lý chia sẻ 1 không gian địa chỉ và các dòng xử lý hoạt động song song Tiểu trình:
1 đơn vị xử lý cơ bản
Sở hữu 1 con trỏ lệnh, tập các thanh ghi, 1 vùng nhớ stack riêng
Có các trạng thái như tiến trình thật.
Các tiểu trình trong cùng tiến trình chia sẻ không gian địa chỉ chung…
50
Phân bổ thông tin lưu trữ
Tiến trình
Không gian địa chỉ
Tài nguyên toàn cục
Các thông tin thống kê
Tiểu trình
Con trỏ lệnh + các thanh ghi, stack
Tài nguyên cục bộ
51
3.4. M?t s? Kiến trúc Hệ điều hành
Đơn giản (Monolithic)
Hạt nhân (Kernel)
Phân lớp (Layered)
Máy ảo (Virtual Machine)
Hướng đối tượng (OOOS)
Exokernel
52
Monolithic
OS = Thư viện tiện ích
Có thể tổ chức thành nhiều module : CPU scheduling, Mem Management, Device management .. nhưng chỉ có 1 trong những module này hoạt động tại một thời điểm
Đơn nhiệm
Quyền điều khiển được chuyển đổi thông qua lời gọi hàm
Khi tầm vóc phát triển hệ thống trở nên thiếu tin cậy.
Ví dụ : MS-DOS, Ultrix (mature Unix)
53
Monolithic
54
Kernel
OS = Kernel + System processes
Kernel được bảo vệ
Đa nhiệm
Kernel chịu trách nhiệm phân chia thời gian sử dụng CPU, Giao tiếp giữa các tiến trình
Chỉ có 2 mức kernel/non-kernel =>kernel lớn, thiếu tin cậy như trước
Định nghĩa cứng các giao tiếp với ứng dụng trong kernel
Ví dụ : Windows NT
55
Kernel
56
Layered
OS = các lớp trừu tượng hoá một tác vụ quản lý
Lớp trên được sử dụng các hàm xử lý� tài nguyên thuộc tác vụ do lớp dưới cung cấp
Khó xác định được các lớp xử lý rạch ròi, thứ tự lớp ?
Xếp lớp theo hàm xử lý , thay vì tác vụ
Ví dụ : THE , MULTICS
57
Layered
58
Virtual Machine
OS = Virtualizing kernel + virtual machines
Virtual machine = physical hardware
Virtualizing kernel tạo ra nhiều VM trên 1 máy tính.
Process interface = hardware interface
Ưu điểm :
Môi trường thuận lợi cho sự tương thích (compatibility)
Tăng tính an toàn hệ thống do cung cấp các VM độc lập.
D? phát triển các HDH đơn nhiệm cho mỗi VM
Khuyết điểm:
Phức tạp cho việc giả lặp (transput, add translation.)
Ví dụ : CMS(conversational Monitor System) trên VM/370 (hỗ trợ hardware)
59
Virtual Machine
60
Nói thêm về các chiến lược điều phối tiến trình (đọc thêm)
61
Chiến lược FIFO
CPU cấp cho tiến trình đầu tiên trong ready list.
Tiến trình Thời điểm vào Thời gian xử lý
P1 0 24
P2 1 3
P3 2 3



Thời gian chờ để được xử lý:
P1 -> 0; P2-> 24 -1 = 23 ; P3=24 + 3 -2
Thời gian chờ trung bình: (0+23+25)/3 = 16 ms
P1
P2
P3
0
24
27
30
62
Chiến lược FIFO (tt)
Thảo luận:
Thời gian chờ trung bình không đạt cực tiểu
Có thể xảy ra hiện tượng tích luỹ thời gian chờ
Không phù hợp với HĐH phân chia theo thời gian
63
Chiến lược round robin
Bộ điều phối lần lượt cấp phát cho từng tiến trình trong ready list 1 khoảng thời gian sử dụng CPU là quantum.
Hết thời gian quantum mà ttrình chưa hoàn tất, ttrình đưa trở lại vào cuối ready list.
64
Chiến lược round robin (tt)
Tiến trình Thời điểm vào Thời gian xử lý
P1 0 24
P2 1 3
P3 2 3
Quantum= 4ms



Thời gian chời trung bình:
(0+6+3+5)/3=4,66ms
P1
P2
P3
P1
P1
P1
P1
0
4
7
10
14
18
22
P1
26
30
65
Chiến lược round robin (tt)
n ttrình trong ready list; Quantum q
Mỗi ttrình không đợi quá (n-1)q đvị thời gian để đến lượt nhận CPU.
Thao luận:
Độ dài quantum ?
bé: phát sinh nhiều chuyển đổi giữa các ttrình
Lớn: tăng thời gian phản hồi, giảm khả năng tương tác.
66
Chiến lược điều phối theo độ ưu tiên
Gán độ ưu tiên cho mỗi ttrình
Ttrình có độ ưu tiên cao nhất sẽ được chọn.
Độ ưu tiên xác định
đ/nghĩa nội tại (e.g. giới hạn thời gian, nhu cầu bộ nhớ,…)
nhờ yếu tố bên ngoài ( e.g. tầm quan trọng của ttrình, loại user sỡ hữu ttrình)
Có thể hoạt động theo nguyên tắc độc quyền hay không độc quyền.
67
Chiến lược điều phối theo độ ưu tiên (tt)
Khi ttrình được đưa vào ready list
Trong chế độ không độc quyền: so sánh độ ưu tiên với ttrình đang được xử lý hiện hành nếu độ ưu tiên cao hơn -> cấp phát CPU cho ttrình mới.
Trong chế độ độc quyền: chèn ttrình mới vào ready list.
Tiến trình độ ưu tiên Thời gian xử lý
P1 3 24
P2 1 3
P3 2 3

P2
P3
P1
0
4
7
30
Giải thuật độ quyền
68
Chiến lược điều phối theo độ ưu tiên (tt)
Thảo luận:
Trình trạng đói CPU (starvation): ttrình có độ ưu tiên thấp chờ đợi vô thời hạn.
Khắc phục giảm độ ưu tiên của các ttrình có độ ưu tiên cao sau mỗi ngắt đồng hồ.
độ ưu tiên của ttrình giảm xuống thấp hơn ttrình có độ ưu tiên cao thứ nhì -> chuyển đổi quyền sử dụng CPU ( “lão hoá” (aging) ttrình).
69
Chiến lược theo công việc ngắn nhất (shortest-Job-First) SJF
Giải thuật đặc biệt của giải thuật điều phối theo độ ưu tiên
Độ ưu tiên p =1/t; t: thời gian xử lý yêu cầu
Giải thuật này có thể độc quyền hay không độc quyền.
Không độc quyền: dừng ttrình hiện hành, khi có 1 ttrình mới có độ ưu tiên cao hơn vào ready list.
Độc quyền: ttrình hiện hành tiếp tục xử lý.
70
Chiến lược theo công việc ngắn nhất (shortest-Job-First) SJF (tt)
Tiến trình Thời gian xử lý
P1 6
P2 8
P3 7
P4 3
SJF độc quyền: P4 ->P1->P3->P2
Thời gian chờ tbình: (3+16+9+0)/3 =7ms
Thảo luận
Thời gian chờ trung bình đạt cực tiểu
Làm sao biết thời gian yêu cầu còn lại xử lý ?
71
Chiến lược theo công việc ngắn nhất (shortest-Job-First) SJF (tt)
Dự đoán thời gian xử lý còn lại:



01
72
Chiến lược điều phối theo nhiều mức độ ưu tiên
Phân lớp các ttrình tuỳ theo độ ưu tiên của chúng. -> cách thức điều phối thích hợp cho từng nhóm.
Ready list được phân thành các list riêng biệt theo cấp độ ưu tiên.
Ttrình trong list ở cấp độ ưu tiên i chỉ được cấp phát CPU khi các list ở cấp ưu tiên lớn hơn i đã trống.
73
Chiến lược điều phối theo nhiều mức độ ưu tiên (tt)
1 ttrình gán vĩnh viễn cho 1 list ở cấp ưu tiên i; ttrình không chuyển giữa các lists
=> Giảm chi điều phối, thiếu linh động và có thể dẫn đến “đói CPU”.
Xây dựng giải thuật điều phối nhiều cấp ưu tiên và xoay vòng.
1 ttrình từ list có độ ưu tiên cao xuống list có độ ưu tiên thấp hơn sau mỗi lần sử dụng CPU. 1 ttrình từ list có độ ưu tiên thấp -> cao hơn.
Các tham số liên quan.
74
Tóm tắt chương & câu hỏi
Chức năng ?
(Cấu trúc) Các thành phần chính ?
Việc điều phối tiến trình ? Các chiến lược ?


75
Các chủ đề thảo luận thêm
- Cơ chế quản lý bộ nhớ của Hệ điều hành.
- Cơ chế quản lý nhập xuất của HĐH.