Tổng Quan Về Hệ Điều Hành

Tổng Quan Về Môn Học

• Môn học bao gồm tổng quan về hệ điều hành, cấu trúc hệ điều hành, quản lý tiến trình, định thời CPU, đồng bộ hóa tiến trình, tắc nghẽn, quản lý bộ nhớ, bộ nhớ ảo, HĐH Linux và Windows.

Tổng Quan Về Hệ Điều Hành

• Hệ điều hành là chương trình trung gian giữa phần cứng và người dùng, điều khiển phần cứng, cung cấp dịch vụ cơ bản cho ứng dụng.
• Mục tiêu của hệ điều hành là giúp người dùng dễ dàng sử dụng hệ thống và quản lý tài nguyên hiệu quả.
• Phần cứng, hệ điều hành, ứng dụng và người dùng tương tác để chạy ứng dụng.

Cấu Trúc Hệ Thống Máy Tính

• Phần cứng bao gồm CPU, bộ nhớ và thiết bị I/O.
• Hệ điều hành phân phối tài nguyên và điều khiển hoạt động của các chương trình.
• Ứng dụng sử dụng tài nguyên để giải quyết bài toán của người dùng.

Hoạt Động Bên Trong Máy Tính

• Nhân (kernel) là chương trình luôn chạy khi máy tính hoạt động.
• Chương trình hệ thống được đóng gói cùng hệ điều hành, nhưng không thuộc nhân.
• Middleware cung cấp các dịch vụ bổ sung cho nhà phát triển ứng dụng.
• CPU và trình điều khiển thiết bị kết nối qua bus để truy xuất bộ nhớ chia sẻ.
• Các thiết bị nhập/xuất và CPU có thể thực thi đồng thời.
• Mỗi trình điều khiển thiết bị chịu trách nhiệm một loại thiết bị cụ thể và có bộ đệm cục bộ.

Ngắt (Interrupts)

• Ngắt chuyển điều khiển đến interrupt service routine thông qua interrupt vector.
• Kiến trúc ngắt phải lưu địa chỉ của lệnh phát sinh ngắt.
• Hệ điều hành hoạt động định hướng theo ngắt.

Cấu Trúc Lưu Trữ (Storage)

• Hệ thống lưu trữ được tổ chức phân cấp dựa trên tốc độ, chi phí và khả năng lưu trữ khi không có điện.
• Bộ nhớ chính là thiết bị lưu trữ duy nhất CPU truy xuất trực tiếp.
• Bộ nhớ thứ cấp mở rộng bộ nhớ chính, cung cấp khả năng lưu trữ không bay hơi với dung lượng lớn.

Hoạt Động Của Máy Tính Hiện Đại

• Kiến trúc Von Neuman được sử dụng.
• CPU thực thi các lệnh.
• Multicore: nhiều lõi tính toán trên một CPU.
• Multiprocessor: nhiều bộ xử lý.

Kiến Trúc Hệ Thống Máy Tính

• Hệ thống đơn bộ xử lý.
• Hệ thống đa bộ xử lý.
• Hệ thống gom cụm.

Hệ Thống Đơn Bộ Xử Lý

• Chỉ có một bộ xử lý đa dụng với một lõi duy nhất.
• Có thể có các bộ xử lý riêng biệt chỉ thực thi các tập lệnh hạn chế.

Hệ Thống Đa Bộ Xử Lý

• Ưu điểm: tăng năng suất, kinh tế, độ tin cậy cao.
• Phân loại: đa xử lý bất đối xứng và đa xử lý đối xứng.

Hệ Thống Gom Cụm

• Là một dạng hệ thống đa bộ xử lý, gồm nhiều hệ thống làm việc với nhau.
• Thường chia sẻ không gian lưu trữ qua mạng lưu trữ khu vực (SAN).
• Cung cấp các dịch vụ có độ sẵn sàng cao.

Các Thao Tác Trong Hệ Điều Hành

• Các thao tác trong hệ điều hành bao gồm: Đơn chương (uniprogramming), đa chương (multiprogramming) và đa nhiệm (multitasking)
• Các chế độ hoạt động.

Đơn Chương (Uniprogramming)

• Chỉ một công việc/chương trình được nạp vào bộ nhớ tại một thời điểm.
• Công việc/chương trình được thi hành tuần tự.

Đa Chương (Multiprogramming)

• Đa chương tổ chức các công việc sao cho CPU luôn có thể chọn một để thực thi.
• Nhiều công việc được nạp đồng thời vào bộ nhớ.
• Một công việc đang thực thi được gọi là một tiến trình.

Các Chế Độ Hoạt Động

• Cho phép hệ điều hành bảo vệ chính nó và các thành phần khác của hệ thống.
• Hai chế độ cơ bản: Chế độ người dùng (user mode) và chế độ hạt nhân (kernel mode).
• Bit chế độ được thêm vào phần cứng để phân biệt khi nào hệ thống thực thi mã người dùng hay mã hạt nhân.

Lịch Sử Phát Triển Hệ Điều Hành

• Thế hệ 1 (1945-1955): Thiết kế, xây dựng, lập trình, thao tác do một nhóm người, lưu trên phiếu đục lỗ.
• Thế hệ 2 (1955-1965): Phân công công việc, hệ thống xử lý theo lô ra đời, lưu trên băng từ.
• Thế hệ 3 (1965-1980): Ra đời hệ điều hành, khái niệm đa chương, HĐH chia sẻ thời gian như CTSS của MIT, MULTICS, UNIX.
• Thế hệ 4 (1980 – nay): Ra đời máy tính cá nhân, HĐH MS-DOS, MacOS, MS Windows, OS/1, Linux, QNX, HĐH mạng,…
• Thế hệ 5 (1990 – nay): Thiết bị di động ra đời và phổ biến, Symbian, BlackBerry OS, Android, iOS.

Các Thành Phần Của Hệ Điều Hành

• Quản lý tiến trình, bộ nhớ chính, file, hệ thống I/O, hệ thống lưu trữ thứ cấp, hệ thống bảo vệ và hệ thống thông dịch lệnh.

Quản Lý Tiến Trình

• Các nhiệm vụ chính: tạo và hủy tiến trình, tạm dừng/thực thi tiếp tiến trình.
• Cung cấp cơ chế đồng bộ và giao tiếp giữa các tiến trình.
• Khống chế tắc nghẽn.

Quản Lý Bộ Nhớ Chính

• Theo dõi, quản lý các vùng nhớ trống và đã cấp phát.
• Quyết định nạp chương trình nào khi có vùng nhớ trống.
• Cấp phát và thu hồi các vùng nhớ khi cần thiết.

Quản Lý File

• Các dịch vụ chính: tạo và xóa file/thư mục, các thao tác xử lý file/thư mục.
• "Ánh xạ" file/thư mục vào thiết bị thứ cấp tương ứng.
• Sao lưu và phục hồi dữ liệu.

Quản Lý Hệ Thống I/O

• Che dấu sự khác biệt của các thiết bị I/O trước người dùng.
• Cung cấp giao diện chung đến các trình điều khiển thiết bị.
• Bộ điều khiển các thiết bị phần cứng.

Quản Lý Hệ Thống Lưu Trữ Thứ Cấp

• Quản lý không gian trống trên đĩa (free space management).
• Cấp phát không gian lưu trữ (storage allocation).
• Định thời hoạt động cho đĩa (disk scheduling).

Hệ Thống Bảo Vệ

• Kiểm soát tiến trình người dùng đăng nhập/xuất và sử dụng hệ thống.
• Kiểm soát việc truy cập các tài nguyên trong hệ thống.
• Đảm bảo người dùng/tiến trình chỉ được phép sử dụng các tài nguyên dành cho nó.

Hệ Thống Thông Dịch Lệnh

• Là giao diện chủ yếu giữa người dùng và hệ điều hành.
• Các lệnh chủ yếu: Tạo, hủy và quản lý tiến trình, hệ thống; Kiểm soát I/O; Quản lý bộ lưu trữ thứ cấp; Quản lý bộ nhớ chính; Truy cập hệ thống file và cơ chế bảo mật.

Các Dịch Vụ Hệ Điều Hành Cung Cấp

• Thực thi chương trình, thực hiện các thao tác I/O, các thao tác trên hệ thống file.
• Trao đổi thông tin giữa các tiến trình qua chia sẻ bộ nhớ hoặc chuyển thông điệp.
• Phát hiện lỗi trong CPU, bộ nhớ, trên thiết bị I/O và do chương trình.
• Cấp phát tài nguyên như CPU, bộ nhớ chính, ổ đĩa.
• Kế toán nhằm lưu vết user để tính phí hoặc đơn giản để thống kê.
• Bảo vệ và an ninh để kiểm soát các truy xuất tài nguyên của hệ thống.
• Cung cấp giao diện người dùng: Command-Line (CLI), Graphics User Interface (GUI) và Touch-screen.

Lời Gọi Hệ Thống (System Calls)

• Dùng để giao tiếp giữa tiến trình và hệ điều hành.
• Cung cấp giao diện giữa tiến trình và hệ điều hành bằng cách gọi đến các dịch vụ hệ điều hành cung cấp.
• Ví dụ: open, read, write file.
• Thông thường được viết bằng ngôn ngữ cấp cao (C hoặc C++) và hầu hết được truy cập thông qua các Application Programming Interface (API).
• APIs thông dụng: Win32 API cho Windows, POSIX API cho POSIX-based systems, Java API cho các máy ảo Java (JVM).
• Ba phương pháp truyền tham số khi sử dụng system call: qua thanh ghi, qua một vùng nhớ, qua stack.

Các Chương Trình Hệ Thống

• Chương trình hệ thống gồm: quản lý hệ thống file, thông tin trạng thái, soạn thảo file.
• Hỗ trợ ngôn ngữ lập trình: compiler, assembler, interpreter.
• Nạp, thực thi, giúp tìm lỗi chương trình: loader, debugger; Giao tiếp: email, talk, web browser.

Cấu Trúc Hệ Thống

• Hệ điều hành là một chương trình lớn có nhiều dạng cấu trúc khác nhau.
• Các cấu trúc: Monolithic, Layered Approach, Microkernels, Modules, Hybrid Systems.

Cấu Trúc Monolithic - Original UNIX

• UNIX gồm hai phần tách rời nhau: Nhân (cung cấp file system, CPU scheduling, memory management) và System program.

Cấu Trúc Layered Approach

• Hệ điều hành được chia thành nhiều lớp (layer), lớp trên chỉ phụ thuộc lớp dưới.
• Một lớp chỉ có thể gọi các hàm của lớp dưới và các hàm của nó được gọi bởi lớp trên.

Cấu Trúc Microkernels

• Chuyển một số chức năng của OS từ kernel space sang user space.
• Thu gọn kernel => microkernel, microkernel chỉ bao gồm các chức năng tối thiểu.
• Giao tiếp giữa các user module qua cơ chế truyền thông điệp.

Cấu Trúc Modules

• Nhiều hệ điều hành hiện đại triển khai các loadable kernel modules (LKMs).
• Mỗi core thành phần là tách biệt nhau, trao đổi thông qua các interfaces.
• Mỗi module như là một phần của nhân.
• Linux dựa theo cấu trúc monolithic được thiết kế theo dạng module.

Cấu Trúc Hybrid Systems

• Hầu hết các hệ điều hành hiện đại không theo một cấu trúc thuần túy nào mà lai giữa các cấu trúc với nhau.
• Cấu trúc lai là sự kết hợp nhiều cách tiếp cận để giải quyết các nhu cầu về hiệu suất, bảo mật, nhu cầu sử dụng.
• Nhân Linux và Solaris theo cấu trúc kết hợp không gian địa chỉ kernel, cấu trúc monolithic và modules.

Cấu Trúc Của Một Số Hệ Điều Hành

• Kiến trúc Android được phát triển bởi Open Handset Alliance (Google) và dựa trên nhân Linux.
• Môi trường chạy bao gồm tập các thư viện API và máy ảo ART VM.
• Thư viện bao gồm các frameworks cho web browser, database, multimedia.

Khái Niệm Cơ Bản Về Tiến Trình

• Hệ điều hành thực thi chương trình như một tiến trình.
• Tiến trình là một chương trình đang thực thi.
• Chương trình là thực thể bị động, tiến trình là thực thể chủ động.
• Chương trình trở thành tiến trình khi được nạp vào bộ nhớ.
• Tiến trình bao gồm text section (program code), data section (global variables), program counter, processor registers, heap section (bộ nhớ cấp phát động), stack section (dữ liệu tạm thời).
• Stack section chứa function parameters, return address, local variables.
• Các bước nạp chương trình vào bộ nhớ.
• Các bước khởi tạo tiến trình: cấp phát định danh duy nhất, cấp phát không gian nhớ, khởi tạo Process Control Block (PCB), thiết lập các mối liên hệ cần thiết.

Trạng Thái Tiến Trình

• New: Tiến trình vừa được tạo.
• Ready: Tiến trình đã có đủ tài nguyên, chỉ cần CPU.
• Running: Các lệnh của tiến trình đang được thực thi.
• Waiting: Tiến trình đợi I/O hoàn tất hoặc tín hiệu.
• Terminated: Tiến trình đã kết thúc.

Process Control Block (PCB)

• Mỗi tiến trình được cấp phát một PCB.
• PCB là cấu trúc dữ liệu quan trọng của hệ điều hành.
• PCB gồm: trạng thái tiến trình, bộ đếm chương trình, các thanh ghi, thông tin lập thời biểu CPU, thông tin quản lý bộ nhớ, thông tin trạng thái I/O.

Định Thời Tiến Trình (Process Scheduling)

• Hỗ trợ thực thi luân phiên giữa nhiều tiến trình, tăng hiệu suất CPU, giảm thời gian đáp ứng, phân phối tài nguyên hợp lý, tránh deadlock, cung cấp cơ chế giao tiếp và đồng bộ.
• Yêu cầu đối với hệ điều hành về quản lý tiến trình.
• Mục tiêu của định thời là tận dụng tối đa CPU (đa chương) và tối thiểu thời gian đáp ứng (chia thời).
• Quản lý các tiến trình bằng các hàng đợi (ready, running, waiting).

Định Thời Tiến Trình - Các Hàng Đợi Định Thời

• Các loại hàng đợi định thời: Job queue, Ready queue, Device queues.
• Lưu đồ hàng đợi của định thời tiến trình.

Định Thời Tiến Trình - Bộ Định Thời

• Bộ định thời dài hạn (Job scheduler) hoặc bộ định thời ngắn hạn.
• Phân loại tiến trình dựa trên thời gian thực hiện.
• Bộ định thời trung gian (Medium-term scheduler) để điều chỉnh mức độ đa chương của hệ thống bằng cách chuyển tiến trình giữa bộ nhớ và đĩa.
• Chuyển ngữ cảnh (context switch) là quá trình CPU chuyển từ tiến trình này sang tiến trình khác.

Các Tác Vụ Đối Với Tiến Trình

• Tạo tiến trình mới thông qua lời gọi hệ thống create-process.
• Tiến trình được tạo là tiến trình con của tiến trình tạo, định nghĩa một cây tiến trình.
• Tiến trình con nhận tài nguyên từ OS hoặc tiến trình cha.

Hàm fork()

• Tiến trình con sao chép toàn bộ source code và giá trị biến của tiến trình cha.
• Bắt đầu thực thi từ vị trí tạo của hàm fork.
• Giá trị trả về của hàm fork() cho biết tiến trình cha, con hoặc thất bại.

Họ Hàm exec()

• Nạp một tác vụ mới vào không gian địa chỉ của tiến trình gọi hàm.
• Tác vụ mới ghi đè vào không gian địa chỉ của tiến trình.
• Tiến trình thực thi tác vụ mới thay vì source code ban đầu.

Về Quan Hệ Cha/Con

• Không gian địa chỉ của tiến trình con được nhân bản từ cha hoặc khởi tạo từ template.
• System call tạo tiến trình mới và nạp chương trình mới vào không gian nhớ của tiến trình mới.

Các Tác Vụ Đối Với Tiến Trình - Kết Thúc Tiến Trình

• Tiến trình tự kết thúc hoặc do tiến trình khác kết thúc.
• Hệ điều hành thu hồi tất cả các tài nguyên của tiến trình kết thúc.

Cộng Tác Giữa Các Tiến Trình

• Các tiến trình có thể cộng tác để hoàn thành công việc.
• Yêu cầu hệ điều hành hỗ trợ cơ chế giao tiếp và đồng bộ hoạt động.
• Mục đích cộng tác: chia sẻ dữ liệu, tăng tốc tính toán, thực hiện công việc chung.

Giao Tiếp Liên Tiến Trình (IPC)

• IPC là cơ chế cung cấp bởi hệ điều hành để các tiến trình giao tiếp và đồng bộ hoạt động.
• Hai mô hình IPC: Shared memory và Message passing.
• Shared memory: bộ nhớ được chia sẻ giữa các tiến trình.

Bộ Nhớ Được Chia Sẻ - Shared Memory

• Vùng nhớ dùng chung giữa các tiến trình cần giao tiếp.
• Quá trình giao tiếp được thực hiện dưới sự điều khiển của các tiến trình.
• Cần cơ chế đồng bộ hoạt động của các tiến trình khi truy xuất bộ nhớ dùng chung.

Hệ Thống Truyền Thông Điệp - Message Passing

• Đặt tên: giao tiếp trực tiếp (send/receive đến tiến trình) hoặc gián tiếp (thông qua mailbox/port).
• Đồng bộ hóa: blocking send, nonblocking send, blocking receive, nonblocking receive.
• Sử dụng queue để tạm chứa các message, với các khả năng chứa khác nhau.

Tiểu Trình (Threads) - Tổng Quan

• Tiểu trình là một đơn vị cơ bản sử dụng CPU, chia sẻ code, data, resources.
• PCB (Process Control Block) và TCB (Thread Control Block) trong mô hình multithreads.
• Lợi ích của tiến trình đa luồng: tiếp tục thực thi khi bị khóa, dễ dàng chia sẻ không gian nhớ, tạo và chuyển ngữ cảnh nhanh.

Phân Loại Tiểu Trình

• Tiểu trình người dùng: thực thi các đoạn mã trong chương trình người dùng, quản lý không cần hỗ trợ từ hạt nhân.
• Tiểu trình hạt nhân: thực thi các thao tác hệ thống, được hỗ trợ và quản lý trực tiếp bởi hệ điều hành.

Các Mô Hình Đa Tiểu Trình

• Nhiều – Một (Many-to-One).
• Một – Một (One-to-One).
• Nhiều – Nhiều (Many-to-Many).

Mô Hình Nhiều - Một (Many-to-One)

• Nhiều tiểu trình người dùng được ánh xạ đến một tiểu trình hạt nhân.
• Một tiểu trình bị block dẫn đến tất cả tiểu trình bị block.
• Không thể chạy song song trên hệ thống đa lõi.

Mô Hình Một - Một (One-to-One)

• Mỗi tiểu trình người dùng ứng với một tiểu trình hạt nhân.
• Tính đồng thời tốt hơn mô hình nhiều – một.
• Số lượng tiểu trình có thể bị hạn chế.

Mô Hình Nhiều - Nhiều (Many-to-Many)

• Các tiểu trình người dùng được ánh xạ với nhiều tiểu trình hạt nhân.
• Giải quyết được hạn chế của 2 mô hình trên.
• Khó cài đặt nên ít phổ biến.

Các Khái Niệm Cơ Bản Về Định Thời CPU

• Trong hệ thống đa nhiệm, định thời là chiến lược lựa chọn tiến trình để thực thi hiệu quả nhất.
• Service time là thời gian tiến trình cần CPU trong chu kỳ CPU-I/O.
• Tiến trình hướng CPU yêu cầu thời gian thực thi trên CPU nhiều, trong khi tiến trình hướng I/O yêu cầu thời gian thực thi trên ngoại vi nhiều hơn.

Định Thời Dài (Long-term scheduling)

• Xác định chương trình nào được nạp vào hệ thống để thực thi, điều khiển mức độ đa chương.
• Cố gắng duy trì sự xen lẫn giữa tiến trình hướng CPU và tiến trình hướng I/O.

Định Thời Vừa (Medium-term scheduling)

• Quyết định tiến trình nào được đưa vào và đưa ra khỏi bộ nhớ chính (swap in/out).
• Được thực hiện bởi thành phần quản lý bộ nhớ.

Định Thời Ngắn (Short-term scheduling)

• Xác định tiến trình nào trong hàng đợi sẵn sàng sẽ được chiếm CPU để thực thi kế tiếp.
• Đối với hệ thống đa luồng, OS chọn kernel thread để chiếm CPU.
• Bộ định thời ngắn được gọi khi có ngắt thời gian, ngắt ngoại vi, lời gọi hệ thống hoặc tín hiệu đồng bộ hóa.
• Quá trình chuyển đổi quyền điều khiển CPU bao gồm chuyển ngữ cảnh, chuyển chế độ người dùng và nhảy đến vị trí thích hợp trong chương trình ứng dụng.

Các Tiêu Chuẩn Định Thời CPU

• Hướng người dùng: Thời gian đáp ứng, thời gian hoàn thành, thời gian đợi → cực tiểu.
• Hướng hệ thống: Hiệu năng sử dụng CPU → cực đại, tính công bằng, thông lượng → cực đại.

Các Giải Thuật Định Thời

• Giải thuật định thời bao gồm hàm chọn lựa và chế độ quyết định.
• Chế độ quyết định có thể là không trưng dụng hoặc trưng dụng.
• Hàm chọn lựa được thực thi khi có chuyển đổi trạng thái tiến trình.
• Các giải thuật định thời bao gồm FCFS, SJF, SRTF, RR, Priority Scheduling, HRRN, Multilevel Queue, Multilevel Feedback Queue.

Nhận Xét Về Giải Thuật SJF

• Có thể xảy ra tình trạng "đói" tài nguyên đối với các tiến trình có CPU-burst lớn nếu có nhiều tiến trình với CPU-burst nhỏ liên tục xuất hiện trong hệ thống.
• Cơ chế không trưng dụng không phù hợp cho hệ thống time sharing (interactive).
• Giải thuật SJF ngầm định rằng độ ưu tiên được xác định dựa theo độ dài CPU-burst.

Ưu Điểm Và Hạn Chế Của SJF

• Ưu điểm: SJF tối ưu trong việc giảm thời gian đợi trung bình.
• Hạn chế: Cần phải ước lượng thời gian cần CPU tiếp theo của tiến trình.

Ước Lượng Thời Gian CPU Burst

• Thời gian sử dụng CPU chính là độ dài của CPU burst.
• Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ (exponential averaging) để dự đoán thời gian sử dụng CPU.

Cách Gán Độ Ưu Tiên

• SJF là một giải thuật định thời sử dụng độ ưu tiên được xác định dựa vào thời gian sử dụng CPU (giá trị được ước lượng).
• Việc gán độ ưu tiên còn có thể dựa vào yêu cầu về bộ nhớ, số lượng file được mở, tỉ lệ thời gian dùng cho I/O trên thời gian sử dụng CPU, hoặc các yêu cầu bên ngoài.

Hạn Chế Của Định Thời Theo Độ Ưu Tiên

• Vấn đề trì hoãn vô hạn định: tiến trình có độ ưu tiên thấp có thể không bao giờ được thực thi.
• Giải pháp: làm mới (aging) – độ ưu tiên của tiến trình sẽ tăng theo thời gian.

Nhận Xét Về Giải Thuật Round Robin

• Nếu q lớn: RR trở thành FCFS.
• Nếu q nhỏ: phải tốn chi phí chuyển ngữ cảnh giữa các tiến trình => q không nên quá nhỏ.
• Ưu điểm: Thời gian đáp ứng nhỏ.
• Hạn chế: Thời gian chờ đợi trung bình và thời gian hoàn thành trung bình của giải thuật RR thường khá lớn.

Quantum Time Và Hiệu Suất Hệ Thống

• Khi thực hiện chuyển ngữ cảnh, sẽ sử dụng CPU, không phải hữu ích.
• Nếu quantum time ngắn: thời gian đáp ứng nhanh, nhưng phí tổn hệ thống lớn do số lần chuyển ngữ cảnh tăng.
• Nếu quantum time dài: hiệu quả sử dụng CPU tốt hơn, nhưng thời gian đáp ứng cũng lớn.

Cách Chọn Quantum Time

• Quantum time nên lớn trong tương quan so sánh với thời gian cho chuyển ngữ cảnh.
• Tùy thuộc vào tập công việc mà lựa chọn quantum time.

Giải Thuật Highest Response Ratio Next (HRRN)

• Chọn tiến trình kế tiếp có giá trị Response Ratio lớn nhất.
• Các tiến trình ngắn được ưu tiên hơn (vì nhỏ).

Giải Thuật Multilevel Queue

• Ready queue được chia thành nhiều hàng đợi riêng biệt theo một số tiêu chuẩn (ví dụ: đặc điểm và yêu cầu định thời của tiến trình, phân loại tiến trình).
• Tiến trình được gán cố định vào một hàng đợi, mỗi hàng đợi sử dụng giải thuật định thời riêng.

Định Thời Giữa Các Hàng Đợi

• Hệ điều hành cần phải định thời cho các hàng đợi.
• Ví dụ, định thời theo độ ưu tiên từ hàng đợi có độ ưu tiên cao đến thấp (có thể gây đói tài nguyên) hoặc mỗi hàng đợi được nhận một khoảng thời gian chiếm CPU.

Ví Dụ Phân Chia Hàng Đợi Và Tiến Trình

• Các hàng đợi có thể được phân chia thành System Processes, Interactive Processes, Batch Processes, Student Processes với độ ưu tiên khác nhau.

Hạn Chế Của Multilevel Queue

• Tiến trình không thể chuyển từ hàng đợi này sang hàng đợi khác.
• Khắc phục bằng cơ chế feedback: cho phép tiến trình di chuyển một cách thích hợp giữa các hàng đợi khác nhau.

Giải Thuật Multilevel Feedback Queue

• Phân loại tiến trình dựa trên các đặc tính về thời gian sử dụng CPU.
• Sử dụng chế độ trưng dụng (preemptive).
• Một tiến trình đã chờ quá lâu ở một hàng đợi có độ ưu tiên thấp có thể được chuyển đến hàng đợi có độ ưu tiên cao hơn (cơ chế aging).

Các Vấn Đề Với Multilevel Feedback Queue

• Số lượng hàng đợi bao nhiêu là thích hợp?
• Dùng giải thuật định thời nào ở mỗi hàng đợi?
• Làm sao để xác định thời điểm cần chuyển một tiến trình đến hàng đợi cao hơn hoặc thấp hơn?
• Khi tiến trình yêu cầu được xử lý thì đưa vào hàng đợi nào là hợp lý nhất?

Định Thời Tiểu Trình (Thread Scheduling)

• Trên các hệ điều hành hiện đại, tiểu trình được định thời, không phải tiến trình.
• Có sự phân biệt giữa tiểu trình người dùng và tiểu trình hạt nhân khi định thời.
• Tiểu trình người dùng được định thời thông qua các thư viện quản lý tiểu trình, còn tiểu trình hạt nhân được định thời trên tất cả các CPU khả dụng.

Định Thời Đa Bộ Xử Lý (Multi-Processor Scheduling)

• Định thời CPU trở nên phức tạp hơn khi hệ thống có nhiều bộ xử lý.
• Có hai cách tiếp cận phổ biến: đa xử lý bất đối xứng và đa xử lý đối xứng.
• Đa xử lý bất đối xứng có ưu điểm là đơn giản nhưng có thể bị nghẽn cổ chai, còn đa xử lý đối xứng có hai hướng tiếp cận là dùng chung hàng đợi hoặc mỗi bộ xử lý tự tổ chức hàng đợi.

Định Thời Đa Bộ Xử Lý Bất Đối Xứng

• Trong đa xử lý bất đối xứng, một bộ xử lý (master server) thực hiện tất cả các thao tác lập lịch và xử lý I/O, trong khi các bộ xử lý còn lại chỉ thực thi user code.
• Ưu điểm của phương pháp này là đơn giản, nhưng nhược điểm là master server có thể trở thành điểm nghẽn.
• Nhược điểm: master server có thể bị nghẽn cổ chai (bottleneck), làm giảm hiệu năng của hệ thống.

Định Thời Đa Bộ Xử Lý Đối Xứng

• Mỗi bộ xử lý tự định thời cho chính nó trong đa xử lý đối xứng.
• Có hai hướng tiếp cận: tất cả tiểu trình nằm trong cùng một ready queue hoặc mỗi bộ xử lý tự tổ chức hàng đợi riêng.
• Sử dụng hàng đợi riêng cho mỗi bộ xử lý giúp tránh các vấn đề về hiệu năng do tranh chấp khi dùng chung hàng đợi.

Cân Bằng Tải

• Cần đảm bảo các bộ xử lý đều được sử dụng hiệu quả bằng cách phân phối khối lượng công việc đều nhau.
• Có hai cách cân bằng tải: Push migration (đẩy tác vụ từ CPU quá tải) và Pull migration (CPU rỗi kéo tác vụ từ CPU bận).

Processor Affinity

• Tác vụ có tính liên kết với bộ xử lý (processor affinity) do bộ nhớ đệm của bộ xử lý lưu trữ dữ liệu được truy xuất bởi tác vụ.
• Cân bằng tải có thể ảnh hưởng đến processor affinity, gây tốn kém do phải nạp lại cache.
• Có hai dạng liên kết: liên kết mềm và liên kết cứng.

Định Thời Theo Thời Gian Thực

• Có nhiều thách thức do yêu cầu về tính chất thời gian thực.
• Có 2 dạng hệ thống thời gian thực: Soft real-time systems và Hard real-time systems.
• Hệ thống thời gian thực phải hỗ trợ định thời theo độ ưu tiên với chế độ trưng dụng.
• Có ba mô hình tác vụ trong thời gian thực: Periodic tasks, Aperiodic tasks và Sporadic tasks.

Các Giải Thuật Định Thời Theo Thời Gian Thực

• Đối với tác vụ chu kỳ, có các giải thuật Rate Monotonic (RM) và Earliest Deadline First (EDF).
• Đối với tác vụ phi chu kỳ, có các giải thuật Total Bandwidth Server (TBS), Enhanced Virtual Release Advancing TBS và Constant Bandwidth Server.

Định Thời Rate Monotonic

• Độ ưu tiên được gán dựa trên nghịch đảo của chu kỳ, chu kỳ ngắn thì độ ưu tiên cao và ngược lại.

Định Thời Trên Linux

• Nhân Linux 2.5 trở về trước sử dụng các phiên bản định thời UNIX tiêu chuẩn, không hỗ trợ tốt các hệ thống nhiều bộ xử lý.
• Nhân Linux 2.5 sử dụng bộ định thời O(1), chạy với thời gian hằng số và định thời theo độ ưu tiên với chế độ trưng dụng.
• Nhân Linux từ 2.6.23 sử dụng bộ định thời CFS (Completely Fair Scheduler), định thời theo lớp và thời gian sử dụng CPU của mỗi tác vụ dựa trên tỷ lệ giờ CPU.

Bộ Định Thời CFS Trên Linux

• Mỗi lớp được gán một độ ưu tiên cụ thể, và bộ định thời chọn tác vụ có độ ưu tiên cao nhất trong lớp có độ ưu tiên cao nhất.
• Thời gian sử dụng CPU được tính dựa trên giá trị nice được gán cho mỗi tác vụ.
• CFS xác định tác vụ được thực thi kế tiếp qua virtual run time, chọn tiến trình có virtual run time nhỏ nhất để thực thi tiếp.

Bộ Định Thời Real-time Trên Linux

• Định thời real-time dựa trên tiêu chuẩn POSIX.
• Các tác vụ real-time có độ ưu tiên tĩnh.
• Độ ưu tiên được chia thành 2 phần: real-time và normal.

Định Thời Trên Android

• Sử dụng bộ định thời của Linux.
• Độ ưu tiên được phân chia theo nhóm của các tiến trình.
• Android có thể hủy (kill) các tiến trình dựa trên độ ưu tiên của chúng để thu hồi tài nguyên.

Định Thời Trên Windows

• Định thời theo độ ưu tiên với chế độ trưng dụng.
• Sử dụng 32 độ ưu tiên, được chia thành 2 lớp: variable và real-time.
• Mỗi độ ưu tiên có hàng đợi riêng.
• Các hàm thư viện Windows API cung cấp cho tiến trình các lớp ưu tiên và độ ưu tiên tương đối khác nhau.
• Lớp ưu tiên và độ ưu tiên tương đối có thể kết hợp để xác định giá trị ưu tiên.
• Khi hết quantum, độ ưu tiên có thể giảm nhưng không nhỏ hơn độ ưu tiên cơ sở.
• Windows 7 có thêm user-mode scheduling (UMS), cho phép ứng dụng tạo và quản lý tiểu trình độc lập với nhân.
• Định thời UMS được thực hiện với sự hỗ trợ của các thư viện như C++ Concurrent Runtime (ConcRT).

Định Thời Trên Solaris

• Định thời theo độ ưu tiên.
• Có 6 lớp, mỗi lớp có độ ưu tiên khác nhau và giải thuật định thời khác nhau.
• Lớp TS sử dụng giải thuật định thời MFQ.
• Bộ định thời chuyển đổi độ ưu tiên theo lớp thành độ ưu tiên toàn cục.
• Tác vụ có độ ưu tiên cao nhất được chọn chạy tiếp.
• Nếu có nhiều tiến trình có cùng độ ưu tiên, bộ định thời sẽ sử dụng hàng đợi round-robin.