Mục lục bài họcĐang ở d08-b1
Operating systems: scheduling, memory and interrupts
What the operating system actually manages
Processes, memory, files, devices, security and the interface. All of it exists to share limited hardware between competing demands while hiding the detail from applications.
Process states
A process is running (using the processor), ready (able to run, waiting its turn) or blocked (waiting for input, output or a resource). A blocked process cannot go straight to running — it must return to ready first, and that transition is a standard exam point.
Scheduling algorithms
Round robin gives each process a fixed time slice in turn: fair, and prevents any process monopolising the CPU, but ignores urgency. First come first served is simple but a long job blocks everything behind it. Shortest job first minimises average waiting time but can starve long jobs indefinitely. Priority scheduling serves important work first, and needs ageing — gradually raising the priority of waiting processes — to stop low-priority work being starved.
Memory management
Paging divides memory into fixed-size pages; segmentation divides it into variable-size logical units. Virtual memory uses disk as an extension of RAM, swapping out pages that are not currently needed. It allows programs larger than physical memory to run, at the cost of disk access time — and if too much swapping occurs the system thrashes: the processor spends more time moving pages than executing instructions.
Interrupts and the OS
Interrupt handling is what makes a single processor appear to do many things at once. The processor checks for interrupts at the end of each cycle, saves the process state on the stack, runs the service routine, then restores and resumes — the same mechanism that underlies multitasking.
Hệ điều hành thật sự quản lý những gì
Tiến trình, bộ nhớ, tệp, thiết bị, bảo mật và giao diện. Tất cả tồn tại để chia sẻ phần cứng có hạn giữa những nhu cầu cạnh tranh nhau, đồng thời giấu chi tiết đó khỏi các ứng dụng.
Các trạng thái của tiến trình
Một tiến trình đang ở trạng thái chạy (đang dùng bộ xử lý), sẵn sàng (đủ điều kiện chạy, đang chờ tới lượt) hoặc bị chặn (đang chờ dữ liệu vào ra hoặc chờ một tài nguyên). Một tiến trình bị chặn KHÔNG đi thẳng sang trạng thái chạy — nó phải quay về sẵn sàng trước, và bước chuyển đó là một ý quen thuộc của đề thi.
Các thuật toán điều độ
Xoay vòng cho mỗi tiến trình một lát thời gian cố định lần lượt: công bằng, và ngăn được việc một tiến trình chiếm dụng CPU, nhưng bỏ qua mức độ khẩn cấp. Đến trước phục vụ trước đơn giản nhưng một tác vụ dài chặn mọi thứ phía sau. Tác vụ ngắn nhất trước làm nhỏ nhất thời gian chờ trung bình nhưng có thể bỏ đói các tác vụ dài vô hạn. Điều độ theo độ ưu tiên phục vụ việc quan trọng trước, và cần cơ chế lão hoá — dần nâng độ ưu tiên của tiến trình chờ lâu — để ngăn việc ưu tiên thấp bị bỏ đói.
Quản lý bộ nhớ
Phân trang chia bộ nhớ thành các trang kích thước cố định; phân đoạn chia thành các đơn vị logic kích thước thay đổi. Bộ nhớ ảo dùng đĩa như phần mở rộng của RAM, đẩy ra những trang hiện chưa cần. Nhờ đó chương trình lớn hơn bộ nhớ vật lý vẫn chạy được, đổi lại là thời gian truy cập đĩa — và nếu việc đổi trang xảy ra quá nhiều thì hệ thống rơi vào thrashing: bộ xử lý dành nhiều thời gian chuyển trang hơn là thực hiện lệnh.
Ngắt và hệ điều hành
Cơ chế xử lý ngắt chính là thứ làm một bộ xử lý duy nhất trông như đang làm nhiều việc cùng lúc. Bộ xử lý kiểm tra ngắt vào cuối mỗi chu trình, lưu trạng thái tiến trình vào ngăn xếp, chạy trình phục vụ, rồi khôi phục và tiếp tục — đúng cơ chế nằm dưới khả năng đa nhiệm.
Bốn tiến trình cùng đến tại thời điểm $0$ với thời gian chạy: $P1=8$, $P2=3$, $P3=5$, $P4=2$ (đơn vị mili giây).
Tính thời gian chờ trung bình theo (a) đến trước phục vụ trước, và (b) tác vụ ngắn nhất trước. Nhận xét.
(a) Đến trước phục vụ trước — thứ tự $P1, P2, P3, P4$.
$P1$ chờ $0$
$P2$ chờ $8$
$P3$ chờ $8+3=11$
$P4$ chờ $8+3+5=16$
Thời gian chờ trung bình $=\dfrac{0+8+11+16}{4}=\dfrac{35}{4}=\mathbf{8{,}75}$ ms.
(b) Tác vụ ngắn nhất trước — thứ tự $P4, P2, P3, P1$.
$P4$ chờ $0$
$P2$ chờ $2$
$P3$ chờ $2+3=5$
$P1$ chờ $2+3+5=10$
Thời gian chờ trung bình $=\dfrac{0+2+5+10}{4}=\dfrac{17}{4}=\mathbf{4{,}25}$ ms.
Nhận xét. Tác vụ ngắn nhất trước giảm thời gian chờ trung bình xuống một nửa. Lý do trực quan: chạy các tác vụ ngắn trước nghĩa là ít tiến trình phải chờ đằng sau một tác vụ dài.
Nhưng cái giá phải nêu. $P1$ — tiến trình dài nhất — phải chờ lâu nhất. Trong hệ thống thật, tiến trình mới liên tục đến, nên nếu luôn có tác vụ ngắn xuất hiện thì $P1$ có thể chờ vô thời hạn. Hiện tượng đó gọi là bỏ đói, và nó là lý do hệ điều hành thực tế hiếm khi dùng tác vụ ngắn nhất trước một cách thuần tuý.
Thêm một vấn đề thực tế: thuật toán này đòi biết trước thời gian chạy của mỗi tiến trình, mà hệ điều hành thường chỉ ước lượng được từ lịch sử. Vì vậy hệ thống thật hay dùng xoay vòng có nhiều mức độ ưu tiên kèm lão hoá — vừa công bằng vừa không bỏ đói ai.
Đọc xong rồi — làm thử ngay
Bài tập của chương Operating Systems, Networks and AI gồm 14 câu trắc nghiệm và 3 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.