Mục lục bài họcĐang ở d06-b1
Resources, Processes and Processor Scheduling
What counts as a resource. The resources an operating system manages are processor time, primary memory, secondary storage, network bandwidth, and the peripherals including screen, sound and input devices. Each has a finite capacity, and the key insight for this topic is that they are interdependent: a shortage of one leaves the others idle. A machine short of memory has a processor that spends its time waiting for the disk, so measuring processor utilisation alone gives a completely misleading picture of what is wrong.
The operating system as a manager. The operating system stands between hardware and applications. It schedules the processor between processes, allocates and protects memory so that one process cannot corrupt another, controls peripherals through device drivers, organises secondary storage as a file system, and presents a consistent interface so that applications do not need to know which particular hardware they are running on.
Processes and their states. A process is a program in execution together with its current state. At any moment a process is running on the processor, ready and waiting for its turn, or blocked while waiting for input, output or another event. Only one process per processor core can be running at a time; what looks like simultaneous execution is rapid switching. Each switch requires a context switch: the registers and program counter of the outgoing process are saved and those of the incoming process are restored. A context switch consumes processor time without completing any user work, so its cost is a real constraint on how finely the processor can be shared.
Scheduling algorithms. First come first served runs each process to completion in arrival order: simple and free of starvation, but a single long process makes every short process behind it wait. Shortest job first gives the lowest average waiting time of any algorithm, but it requires knowing run times in advance, which is rarely possible, and a long process can be starved indefinitely if short ones keep arriving. Round robin gives each process a fixed time slice called a quantum and cycles through them: no process is starved and response time is good, at the cost of extra context switches. Priority scheduling serves the most important process first and is used where some work is genuinely more urgent, but it too can starve low-priority work unless priority is raised as a process waits. Note that round robin does not reduce the total time to finish all work — it redistributes the waiting.
Cái gì được tính là tài nguyên. Các tài nguyên mà hệ điều hành quản lý gồm thời gian bộ xử lý, bộ nhớ chính, bộ nhớ ngoài, băng thông mạng, và các thiết bị ngoại vi gồm màn hình, âm thanh và thiết bị nhập. Mỗi loại đều có dung lượng hữu hạn, và nhận định then chốt của chuyên đề này là chúng phụ thuộc lẫn nhau: thiếu hụt ở một loại làm các loại còn lại nằm không. Một máy thiếu bộ nhớ có bộ xử lý dành phần lớn thời gian chờ ổ đĩa, nên chỉ đo mức sử dụng bộ xử lý sẽ cho một bức tranh hoàn toàn sai lệch về vấn đề thực sự.
Hệ điều hành với vai trò người quản lý. Hệ điều hành đứng giữa phần cứng và các ứng dụng. Nó lập lịch bộ xử lý giữa các tiến trình, cấp phát và bảo vệ bộ nhớ để một tiến trình không phá được vùng nhớ của tiến trình khác, điều khiển thiết bị ngoại vi qua trình điều khiển, tổ chức bộ nhớ ngoài thành hệ thống tệp, và trình bày một giao diện nhất quán để ứng dụng không cần biết nó đang chạy trên phần cứng cụ thể nào.
Tiến trình và các trạng thái của nó. Tiến trình là một chương trình đang được thực thi cùng với trạng thái hiện tại của nó. Tại mỗi thời điểm, một tiến trình hoặc đang chạy trên bộ xử lý, hoặc sẵn sàng và chờ tới lượt, hoặc bị chặn trong lúc chờ nhập, xuất hoặc chờ một sự kiện khác. Mỗi lõi xử lý chỉ chạy được một tiến trình tại một thời điểm; cái trông như thực thi đồng thời thực chất là việc chuyển đổi rất nhanh. Mỗi lần chuyển đổi đòi một lần chuyển ngữ cảnh: các thanh ghi và con trỏ lệnh của tiến trình đi ra được lưu lại, và của tiến trình đi vào được nạp lại. Chuyển ngữ cảnh tiêu tốn thời gian bộ xử lý mà không hoàn thành công việc nào của người dùng, nên chi phí của nó là một ràng buộc thật lên mức độ chia nhỏ mà bộ xử lý có thể chịu được.
Các thuật toán lập lịch. Đến trước phục vụ trước chạy trọn từng tiến trình theo thứ tự tới: đơn giản và không gây bỏ đói, nhưng một tiến trình dài duy nhất làm mọi tiến trình ngắn đứng sau phải chờ. Công việc ngắn nhất trước cho thời gian chờ trung bình thấp nhất trong mọi thuật toán, nhưng nó đòi biết trước thời gian chạy — điều hiếm khi làm được — và một tiến trình dài có thể bị bỏ đói vô hạn nếu các tiến trình ngắn liên tục tới. Xoay vòng cấp cho mỗi tiến trình một lát thời gian cố định gọi là lượng tử rồi luân phiên qua chúng: không tiến trình nào bị bỏ đói và thời gian đáp ứng tốt, với cái giá là nhiều lần chuyển ngữ cảnh hơn. Lập lịch theo ưu tiên phục vụ tiến trình quan trọng nhất trước và được dùng ở nơi có những công việc thực sự cấp bách hơn, nhưng nó cũng có thể bỏ đói công việc ưu tiên thấp trừ khi ưu tiên được nâng dần theo thời gian chờ. Lưu ý rằng xoay vòng KHÔNG làm giảm tổng thời gian hoàn thành mọi công việc — nó phân phối lại thời gian chờ.
Bốn tiến trình cùng đến lúc 0 với thời gian chạy: P1 cần 8, P2 cần 2, P3 cần 6, P4 cần 4. Tính thời gian chờ trung bình cho đến trước phục vụ trước theo thứ tự P1 tới P4, cho công việc ngắn nhất trước, và cho xoay vòng với lượng tử bằng 4. Rồi kết luận nên chọn cái nào.
Đến trước phục vụ trước, thứ tự P1, P2, P3, P4. P1 bắt đầu ở 0 và xong ở 8; P2 chờ 8 và xong ở 10; P3 chờ 10 và xong ở 16; P4 chờ 16 và xong ở 20. Thời gian chờ lần lượt là 0, 8, 10, 16, nên trung bình bằng 34 chia 4 bằng 8,5.
Công việc ngắn nhất trước, thứ tự P2, P4, P3, P1. P2 chờ 0 và xong ở 2; P4 chờ 2 và xong ở 6; P3 chờ 6 và xong ở 12; P1 chờ 12 và xong ở 20. Thời gian chờ lần lượt là 0, 2, 6, 12, nên trung bình bằng 20 chia 4 bằng 5,0. Đây là giá trị nhỏ nhất có thể đạt được, và điều đó không phải trùng hợp: có thể chứng minh rằng chạy công việc ngắn trước luôn cho thời gian chờ trung bình tối thiểu, vì mỗi đơn vị thời gian của một công việc dài làm TẤT CẢ các công việc đứng sau nó phải chờ thêm.
Xoay vòng với lượng tử 4. Lần theo dòng thời gian. Từ 0 tới 4 chạy P1, còn lại 4. Từ 4 tới 6 chạy P2, xong ở 6. Từ 6 tới 10 chạy P3, còn lại 2. Từ 10 tới 14 chạy P4, xong ở 14. Từ 14 tới 18 chạy P1, xong ở 18. Từ 18 tới 20 chạy P3, xong ở 20.
Thời gian hoàn thành: P1 ở 18, P2 ở 6, P3 ở 20, P4 ở 14. Vì mọi tiến trình đều đến lúc 0, thời gian chờ bằng thời gian hoàn thành trừ thời gian chạy: P1 chờ 10, P2 chờ 4, P3 chờ 14, P4 chờ 10. Trung bình bằng 38 chia 4 bằng 9,5.
Đọc kết quả cho đúng, vì đây mới là phần được chấm. Xoay vòng cho thời gian chờ trung bình tệ nhất trong ba thuật toán ở ví dụ này. Nếu chỉ nhìn con số đó thì kết luận sẽ sai. Điều xoay vòng thực sự cải thiện là thời gian đáp ứng — khoảng thời gian từ lúc một tiến trình tới cho tới lần đầu nó được chạy. Với xoay vòng, cả bốn tiến trình đều được chạm tới trong 14 đơn vị đầu; với đến trước phục vụ trước, P4 phải chờ tới thời điểm 16 mới được nhìn tới. Trên một hệ thống có người dùng ngồi trước màn hình, đó là khác biệt giữa cảm giác mượt và cảm giác treo máy.
Kết luận theo bối cảnh, không kết luận chung. Với một hệ thống xử lý theo lô chạy ban đêm và không ai chờ, hãy chọn công việc ngắn nhất trước nếu ước lượng được thời gian chạy, vì thông lượng và thời gian chờ trung bình là tiêu chí duy nhất. Với một hệ thống tương tác nhiều người dùng, hãy chọn xoay vòng, chấp nhận thời gian chờ trung bình cao hơn để đổi lấy thời gian đáp ứng đều và không ai bị bỏ đói. Và phải nêu cái giá: mỗi lần đổi tiến trình tốn một lần chuyển ngữ cảnh, nên lượng tử quá nhỏ sẽ khiến chi phí này nuốt mất phần lớn thời gian xử lý, còn lượng tử quá lớn thì xoay vòng thoái hoá thành đến trước phục vụ trước.
Một hệ thống dùng lập lịch theo ưu tiên. Các báo cáo cho thấy một tác vụ sao lưu ưu tiên thấp đã ở trạng thái sẵn sàng suốt sáu tiếng mà chưa được chạy lần nào. Giải thích hiện tượng và nêu cách khắc phục.
Cơ chế bỏ đói. Lập lịch theo ưu tiên luôn chọn tiến trình có ưu tiên cao nhất trong hàng sẵn sàng. Nếu hệ thống liên tục nhận các tiến trình ưu tiên cao hơn — mỗi lần bộ xử lý rảnh lại có một tiến trình như vậy chờ sẵn — thì tiến trình ưu tiên thấp không bao giờ lên tới đầu hàng. Điểm quan trọng cần nhấn: đây không phải lỗi; thuật toán đang hoạt động chính xác theo thiết kế. Vấn đề nằm ở chỗ thiết kế đó không có cơ chế bảo đảm tiến độ cho mọi tiến trình.
Vì sao bỏ đói cũng xảy ra với công việc ngắn nhất trước. Cùng một cấu trúc: nếu các công việc ngắn liên tục tới, một công việc dài luôn bị xếp sau và có thể chờ vô hạn. Hai thuật toán này chia chung một điểm yếu vì cả hai đều chọn theo một thuộc tính tĩnh của tiến trình mà không tính tới thời gian nó đã chờ.
Cách khắc phục 1 — nâng ưu tiên theo thời gian chờ. Đây là giải pháp chuẩn và nên nêu tên: hệ thống tăng dần ưu tiên của một tiến trình theo thời gian nó nằm trong hàng sẵn sàng. Một tác vụ ưu tiên thấp chờ đủ lâu cuối cùng sẽ vượt lên trên các tiến trình ưu tiên cao mới tới, nên nó chắc chắn được chạy. Cách này giữ được lợi ích của ưu tiên trong ngắn hạn đồng thời bảo đảm tiến độ trong dài hạn.
Cách khắc phục 2 — bảo đảm một phần thời gian tối thiểu. Dành sẵn một tỷ lệ nhất định thời gian bộ xử lý cho nhóm ưu tiên thấp, chẳng hạn cứ mười lượt lập lịch thì có một lượt bắt buộc phục vụ nhóm này. Cách này đơn giản hơn và cho hành vi dễ dự đoán hơn, nhưng nó làm giảm khả năng đáp ứng của các tiến trình ưu tiên cao.
Cách khắc phục 3 — hàng đợi nhiều mức có phản hồi. Duy trì nhiều hàng đợi với lượng tử khác nhau: tiến trình mới vào hàng ưu tiên cao nhất với lượng tử ngắn; tiến trình nào dùng hết lượng tử mà chưa xong bị chuyển xuống hàng thấp hơn với lượng tử dài hơn. Cơ chế này tự động nhận ra tiến trình nào là tương tác và tiến trình nào là tính toán kéo dài, mà không cần biết trước thời gian chạy — nên nó có được phần lớn lợi ích của công việc ngắn nhất trước mà không cần thông tin mà thực tế không có.
Nguyên tắc chung để viết trong bài. Mọi thuật toán lập lịch chỉ chọn theo một thuộc tính đều có nguy cơ bỏ đói ở một nhóm nào đó. Cách chữa luôn là đưa thời gian đã chờ vào quyết định lập lịch, để không tiến trình nào có thể bị hoãn vô hạn.
Bẫy 2 — quên nêu chi phí chuyển ngữ cảnh khi đề xuất lượng tử nhỏ. Mỗi lần đổi tiến trình phải lưu và nạp lại toàn bộ thanh ghi, tiêu tốn thời gian mà không hoàn thành công việc nào. Lượng tử quá nhỏ thì chi phí này nuốt mất phần lớn thời gian xử lý.
Bẫy 3 — coi bỏ đói là một lỗi lập trình. Đó là hệ quả tất yếu của việc lập lịch theo một thuộc tính tĩnh; cách chữa là đưa THỜI GIAN ĐÃ CHỜ vào quyết định, chẳng hạn bằng cách nâng dần ưu tiên.
Đọc xong rồi — làm thử ngay
Bài tập của chương Resource Management (HL) gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.