Cấu Trúc và Chức Năng | Môn Nguyên lý hệ điều hành - Đại học Cần Thơ

lOMoAR cPSD| 58504431
- HĐH: là một chương trình quản lý tài nguyên của máy tính, đóng vai trò như một lớp trung gian giữa
người sử dụng máy tính và Phần cứng của máy tính.
- Mục tiêu của hđh + Cung cấp phương tiện giao tiếp giữa người dùng và máy tính + Nhận và thực
thi các yêu cầu của người dùng + Quản lý và sử dụng tài nguyên máy tính.
- Thành phần của một hệ thống máy tính gồm phần cứng, hđh, các chương trình hệ thống và ứng dụng, người dùng.
- Định nghĩa hđh từ góc nhìn hệ thống là bộ cấp phát tài nguyên, là một chương trình điều khiển, là
nhân của một hệ thống máy tính.
- Định nghĩa hđh từ góc nhìn người dùng Máy tính cá nhân (PC), Shared-computer (mainframe,
minicomputer), Các trạm làm việc (workstation), Thiết bị cầm tay (handheld).
- Quá trình khởi động của một máy tính Khi khởi động cần chương trình mồi (initial program/bootstrap)
định vị kernel của HĐH, nạp kernel vào bộ nhớ, khởi động kernel và sau đó nhường quyền điều khiển
cho HĐH Bootstrap được lưu trữ trong ROM (firm ware) Sau khi kernel của HĐH được thực thi,
HĐH sẽ bắt đầu cung cấp các dịch vụ thông qua các lời gọi hệ thống.
- Hệ thống máy tính chia làm 2 loại:
+ Các hệ thống đa dụng: mainframe, desktop, multi-processor, distributed, clustered.
+ Các hệ thống chuyên dụng: real-time, multimedia, handheld.
- Hệ thống bó là hđh thô sơ đầu tiên, giao tiếp thông qua người điều khiển (operator), rút ngắn thời
gian thiết lập chương trình (setup time) bằng cách bó lại (batch) các công việc tương tự nhau, tự động
phân dãy công việc, chuyến quyền điều khiển một cách tự động từ một công việc đến một công việc
khác thông qua bộ giám sát thường trú của HĐH, CPU thường xuyên rảnh
- Hệ thống đa chương (multi-programming) công nghệ đĩa, ưu điểm là tận dụng thời gian rỗi của CPU.
- Hệ thống đa chương (yêu cầu đối với hđh)
+ Định thời cho CPU: hệ thống phải chọn trong số các công việc đang sẵn sàng mộtcông việc để giao CPU cho nó sử dụng.
+ Một chương trình đang thực thi trong hệ thống chỉ nhường lại CPU cho chương trình khác khi nó hoàn
thành hoặc cần thực hiện thao tác I/O.
- Hệ thống chia thời gian (time-sharing) là sự mở rộng lý luận của hệ thống đa chương nhằm tăng
hiệu suất sử dụng cho phép người dùng chia sẻ, phân chia thời gian sử dụng các tài nguyên CPU sẽ
được điều phối cho nhiều công việc đang nằm trong bộ nhớ và trong đĩa Công việc được hoán chuyển
giữa bộ nhớ và đĩa giao tiếp trực tuyến giữa hệ thống và người dùng, khi hđh hoàn thành thực thi một
lệnh nó sẽ tìm “lệnh điều khiển” của người dùng từ bàn phím. lOMoAR cPSD| 58504431
Phức tạp hơn hệ thống đa chương: cơ chế quản lý bộ nhớ phức tạp, định thời vị cho CPU,phải cung
cấp hệ thống quản lý đĩa
Các hệ thống đa xử lý: đa xử lý với nhiều hơn 1 CPU, còn được gọi là hệ thống song song hay hệ
thống ghép đôi chặt.
Lợi ích của hệ thống song song: Tăng năng lực xử lí, kinh tế, tăng tính tin cậy
- Kiến trúc hệ thống đa xử lý đối xứng (SMP) mỗi CPU chạy một bản sao giống nhau của hđh, nhiều
quá trình có thể chạy song song mà không làm giám hiệu năng của hệ thống, hầu hết hđh hiện đại đều hỗ trợ SMP.
- Kiến trúc hệ thống đa xử lý bất đối xứng (AMP) mỗi CPU được giao công việc cụ thể, CPU chủ
(Master) sẽ lập biểu và giao việc cho các CPU phó, AMP thường phổ biến trong hệ thống cực lớn.
- Các hệ thống phân tán phân phối tính toán cho nhiều bộ xử lý vật lý, được gọi là hệ thống ghép đôi
lỏng, yêu cầu mạng LAN hoặc WAN, lợi ích: Chia sẻ tài nguyên, tăng tốc độ tính toán – cân bằng tỉa, tin cậy.
- Các hệ thống cụm + Hai hay nhiều máy tính được nhóm lại với nhau sao cho chúng họat động như
một máy tính độc nhất.
+ Mục đích: chia sẻ thiết bị lưu trữ, cân bằng tải, xử lý song song.
+ Cung cấp khả năng sẵn dùng, chịu lỗi và độ tin cậy cao.
+ Ghép cụm bất đối xứng (asymmetric clustering): các server chạy ứng dụng trong khi một server
khác ở trạng thái chờ (hot standby); Khi server hoạt động bi lỗi, server chờ sẽ hoạt động.
+ Ghép cụm đối xứng (symmetric clustering): tất cả các hosts cùng chạy ứng dụng và chúng kiểm
soát lẫn nhau để thay thế công việc cho nhau.
- Các hệ thống thời gian thực:
+Thường được sử dụng như là một thiết bị điều khiển trong mộ tứng dụng dạng chuyên biệt (special-purpose):
Điều khiển các thí nghiệm khoa học
Các hệ thống điều trị y khoa
Các hệ thống điều khiển trong công nghiệp, quân sự
Một số hệ thống hiển thị, …
+ Hệ thống có các ràng buộc về thời gian cố định được định nghĩa chính xác.
+ Hai loại hệ thống thời gian thực: cứng (hard) và mềm (soft).
Các Hệ Thống Thời Gian Thực “Cứng”:
+ Hoàn thành đúng giờ→các trì hoãn phải bị hạn chế. lOMoAR cPSD| 58504431
+ Hạn chế hoặc không dùng các thiết bị lưu trữ thứ cấp, dữ liệu được trữ trong bộ
nhớ ngắn kỳ (short-term) hoặc ROM.
Các Hệ Thống Thời Gian Thực “Mềm”:
+ Có độ ưu tiên cao hơn và được duy trì cho đến khi hoàn thành.
+ Có thể được dùng trong các hệ điều hành đa năng.
+ Không hỗ trợ tốt cho thời điểm tới hạn (deadline)→dễ rủi ro→ít được dùng
trong điều khiển công nghiệp hoặc robotics.
+ Hữu dụng trong các ứng dụng yêu cầu các tính năng cao cấp của hệ điều
hành (đa phương tiện, thực tại ảo). - Các Môi Trường Điện Toán
+ Tính toán truyền thống (traditional computing): Môi trường office, home, thông qua network
+ Tính toán kiểu web (web-based computing): Mở rộng môi trường tính toán thông qua nền
web (webbased), Hỗ trợ nhiều thiết bị: workstations, handheld PDAs, cellular phones
+ Tính toán kiểu hệ thống nhúng (embedded computing): Các máy tính chạy các embedded real-
time OS, Phục vụ các tác vụ chuyên biệt.
- Các Thành Phần Của Hệ Điều Hành (8TP): Là một hệ thống phức tạp bao gồm nhiều thành phần
với input, output và chức năng được định nghĩa rõ ràng.
- Quản Lý Tiến Trình:
+ Tiến trình (process) là một chương trình đang thực thi.
+ Tiến trình cần các tài nguyên để thực hiện tác vụ của nó: thời gian phục vụ của CPU, bộ nhớ,
tập tin, thiết bị vào ra.
+ Bộ quản lý tiến trình chịu trách nhiệm thực hiện các tác vụ sau: Tạo và hủy tiến trình
Ngừng và tiếp tục tiến trình.
Đưa ra các cơ chế để: đồng bộ hóa, giao tiếp, chống deadlock.
- Quản Lý Bộ Nhớ Chính:
+ Bộ nhớ là một mảng lớn các words hoặc bytes, với địa chỉ riêng biệt.
Là kho chứa dữ liệu truy cập nhanh, được chia sẻ bởi CPU và các thiết bị vào ra.
Là thiết bị lưu trữ bay hơi(volatile storage device), sẽ bị mất nội dung khi hệ thống gặp sự cố.
+ Bộ quản lý bộ nhớ chính chịu trách nhiệm thực hiện các tác vụ:
Theo dõi phần nào của bộ nhớ đang được sử dụng bởi tiến trình nào
Quyết định tiến trình nào sẽ được nạp vào bộ nhớ khi không gian nhớ còn chỗ
trống. Cấp phát và thu hồi không gian nhớ khi cần thiết.
- Quản Lý Tập Tin:
+ Một tập tin là một tập hợp các thông tin có liên quan với nhau, dùng để lưu các chương trình
hoặc dữ liệu trong các thiết bị lưu trữ,như đĩa, băng từ.
+ Bộ quản lý tập tin chịu trách nhiệm thực hiện các tác vụ:
Tạo và xóa tập tin, thư mục.
Hỗ trợ các cơ sở cho việc thao tác trên tập tin và thư mục lOMoAR cPSD| 58504431
Ánh xạ tập tin lên các thiết bị lưu trữ thứ cấp
Sao lưu tập tin lên các phương tiện lưu trữ không bay hơi.
- Quản Lý Hệ Thống Nhập/Xuất:
+ Hệ thống xuất/nhập bao gồm:
Hệ thống lưu trữ đệm(buffer-caching system): buffering, caching,spooling.
Giao diện điều khiển thiết bị tổng quát(general device-driver interface).
Trình điều khiển thiết bị(driver) cho các thiết bị cụ thể.
+ Thành phần quản lý hệ thống xuất/nhập giao tiếp với các thành phần khác của hệ thống để quản
lý các thiết bị, chuyển tải dữ liệu, và phát hiện các hoàn thành xuất/nhập.
- Quản Lý Hệ Thống Lưu Trữ Thứ Cấp:
+ Bộ nhớ chính bị bay hơi và quá nhỏ để chứa tất cả dữ liệu và chương trình
lâu dài ⇒ dùng thiết bị lưu trữ thứ cấp để hỗ trợ.
+ Hầu hết sử dụng đĩa từ làm thiết bị lưu trữ trực tuyến chính yếu cho cả dữ liệu và chương trình.
+ Bộ quản lý đĩa chịu trách nhiệm thực hiện các tác vụ:
Quản lý không gian còn trống
Cấp phát không gian lưu trữ
Định thời sử dụng đĩa
- Hệ Thống Nối Kết Mạng – Phân Tán:
+ Hệ thống phân tán là tập hợp các bộ xử lý không dùng chung bộ nhớ hoặc xung đồng
hồ. + Các bộ xử lý trong hệ thống được nối kết thông qua một mạng truyền
thông(communication network).
+ Giao tiếp được thực hiện thông qua các giao thức: FTP, NFS, HTTP
+ Hệ thống phân tán cho phép người dùng truy cập nhiều loại tài nguyên hệ thống khác nhau, giúp: Tăng tốc độ tính toán
Tăng mức độ sẵn dùng của dữ liệu Tăng độ
tin cậy - Hệ thống bảo vệ:
+ Khái niệm bảo vệ nhằm ám chỉ cơ chế điều khiển truy cập từ các chương trình, tiến trình hoặc
người dùng đến tài nguyên của cả hệt hống và của người dùng.
+ Cơ chế bảo vệ phải:
phân biệt được việc truy cập có thẩm quyền hay không xác
định những quyền điều khiển có nguy cơ bị chiếm bất hợp
pháp cung cấp các phương tiện để bảo vệ an ninh.
- Thông Dịch Lệnh (Command-line Interpreter):
+ Nhận và thực hiện các câu lệnh điều khiển của người dùng để thực hiện các tác vụ như:
quản lý tiến trình, quản lý vào/ra, quản lý bộ nhớ, truy cập hệ thống tập tin, . . .
+ Được cài đặt trong kernel (DOS) hoặc qua các chương trình hệ thống (Widows, Unix), còn
được gọi là shell lOMoAR cPSD| 58504431
+ Có 2 loại lệnh cơ bản: các lệnh cung cấp bởi shell (built-in) hay tên của một chương trình.
Sử dụng các lệnh cung cấp qua chương trình cho phép thêm các lệnhvào hệ thống mà
không cần phải cập nhật lại shell. Dung lượng shell nhỏ.
- Môi trường nền (Desktop Environment):
+ Giao diện người dùng theo dạng đồ họa (GUI): Windows DE, GNOMEDE, KDE.
+ Môi trường nền điển hình cung cấp các icons, windows, toolbars, folders, wallpapers và khả năng drag and drop.
+ Môi trường nền bao gồm: window manaer, file manager, tập hợp các themes, các chương trình
và các thư viện cho việc quản lý desktop.
- Các dịch vụ của hệ điều hành:
- Dịch Vụ Cho Chương Trình & Người Dùng:
+ Giao diện người dùng: command line, batch interface, GUI
+ Thực thi chương trình: nạp chương trình vào bộ nhớ và thực thi
+ Thao tác I/O: cung cấp các phương tiện để thực hiện các thao tác I/O
+ Thao tác hệ thống tập tin: cung cấp khả năng có thể lập trình để đọc,ghi, tạo và xóa tập tin
+ Giao tiếp: chuyển thông tin giữa các tiến trình đang thực thi trên cùngmột máy tính hoặc trên
nhiều hệ thống được kết nối với nhau quamạng máy tính (dùng p/p bộ nhớ chia sẻ hoặc chuyển thông điệp)
+ Phát hiện lỗi: phát hiện lỗi phát sinh tại CPU và bộ nhớ, tại thiết bịI/O hoặc tại chương trình
người dùng để bảo đảm tính toán chính xác.
- Dịch Vụ Cho Hệ Thống:
+ Một số chức năng không nhằm hỗ trợ người dùng mà dùng để đảm bảo cho hoạt động hiệu
quả của hệ thống bao gồm:
Cấp phát tài nguyên: cấp tài nguyên cho nhiều người dùng hoặc nhiều công việc đang chạy song song. lOMoAR cPSD| 58504431
Tính chi phí: theo dõi và ghi lại người dùng nào đã sử dụng tài nguyên gì của hệ
thống để làm cơ sở tính tiền sử dụng hệ thống hoặc thống kê sử dụng Bảo vệ: đảm bảo rằng tất
cả truy cập đến hệ thống đều được kiểm soát - Lời Gọi Hệ Thống:
+ Là giao diện giữa tiến trình và hệ điều hành, dùng để gọi các dịch vụ của HĐH.
+ Về cơ bản, được hỗ trợ dưới dạng các chỉ thị assembler.
+ Các lời gọi hệ thống còn được cài đặt bằng các ngôn ngữ cấp cao hơn (C, C++), gọi là các
giao diện lập trình ứng dụng (API).
+ Một số API phổ biến:
Windows API (cho HĐH Windows)
POSIX API (cho POSIX-Based systems như Linux, Unix,
MacOS) Java API (cho Java Virtual Machine) - Truyền Tham Số Cho
Lời Gọi Hệ Thống:
+ Một lời gọi hệ thống thường kèm theo các tham số.
+ Có 3 phương pháp tổng quát để truyền tham số:
Truyền qua thanh ghi: giới hạn số lượng tham số vì số thanh ghi tương đối ít
Truyền qua bộ nhớ: các tham số được lưu vào 1 bảng hay khối trong bộ nhớ và địa
chỉ của bảng/khối được chuyển vào thanh ghi như là 1 tham số
Truyền bằng stack: chương trình push tham số vào stack và hệ điều hành sẽ lấy tham
số bằng cách pop stack.
- Các Kiểu Lời Gọi Hệ Thống:
+ Điều khiển tiến trình (process control)
+ Quản lí file (file management)
+ Quản lí thiết bị (device management)
+ Duy trì thông tin trạng thái (information maintenace) + Giao tiếp (comunication)
+ Một số HĐH còn cung cấp lời gọi hệ thống để sử dụng các dịch vụ bảo vệ (protection) của HĐH.
- Thực Thi Chương Trình Trong MS-DOS:
+ MS-DOS là một chương trình đơn nhiệm: tại 1 thời điểm chỉ tối đa 1chương trình được thực thi
- Thực thi chương trình trong UNIX
+ UNIX là một chương trình đa nhiệm: tại 1 thời điểm có thể có nhiều chương trình được thực thi.
+ Cần cơ chế thực hiện giao tiếp giữa các tiến trình: chuyển thông điệp hay bộ nhớ chia sẻ.
- Các chương trình hệ thống:
+ Cung cấp môi trường thuận lợi cho việc phát triển và thực thi chương trình và đơn giản
hóa cho các lời gọi hệ thống đối với người dùng.
+ Các loại chương trình hệ thống:
Thao tác tập tin và điều chỉnh tập tin Thông tin trạng thái
Hỗ trợ ngôn ngữ lập trình
Nạp và thực thi chương trình
Giao tiếp giữa các tiến trình, người dùng, các máy tính. lOMoAR cPSD| 58504431
+ Người dùng hầu như nhìn HĐH qua các chương trình hệ thống, không qua các lời gọi hệ thống.
- Kiến trúc hệ điều hành:
+ Là cách thức tổ chức các thành phần HĐH để xác định đặc quyền mà mỗi thành phần
thực hiện + Ba loại kiến trúc:
Nguyên khối (monolithic): tất cả các thành phần chứa trong nhân(kernel).
Phân tầng (layered): phương pháp trên-xuống (top-down), tách biệt các chức năng
và các đặc điểm trong các thành phần.
Vi nhân (microkernel): chỉ những thành phần chủ yếu bao gồm trongkernel.
- Kiến Trúc Hệ Điều Hành MS-DOS:
+ Không có kiến trúc rõ ràng
+ Được viết để cung cấp nhiều chức năng nhất với dung lượng
nhỏ nhất + Không được chia thành các modules.
+ Mặc dù MS-DOS được tổ chức có cấu trúc, các lớp chức năng cũng như giao diện giữa chúng
không được phân chia tốt.
- Kiến Trúc Hệ Điều Hành UNIX Cổ Điển:
+ Hệ điều hành UNIX khởi thủy có kiến trúc giới hạn do những giới hạn về phần cứng.
+ Hệ điều hành UNIX bao gồm hai phần
tách biệt: Các chương trình hệ thống Nhân (Kernel):
Bao gồm mọi thứ phía dưới giao diện lời gọi hệ thống và phía trên phần cứng vật lý.
Cung cấp cơ chế quản lý hệ thống tập tin, định thời CPU, quản lý bộ nhớ và
các chức năng khác của hệ điều hành - Kiến Trúc Phân Tầng:
+ Hệ điều hành được chia thành một số tầng, mỗi tầng được xây dựng trên nền tảng của một tầng khác thấp hơn.
+ Tầng thấp nhất là tầng vật lý, tầng cao nhất là giao diện với người dùng.
+ Sự phân chia chức năng: mỗi một tầng sẽ sử dụng các hàm (thao tác) và dịch vụ được cung
cấp duy nhất bởi tầng phía dưới liền kề nó.
- Kiến Trúc Phân Tầng – Ưu Nhược Điểm: + Ưu điểm:
Tính module (modularity) ⇒ đơn giản hóa trong việc thiết kế, cài đặt, gỡ rối và kiểm tra hệ thống.
Đơn giản hóa được thể hiện qua việc có thể sửa đổi, cải tiến tại từng tầng, không ảnh
hưởng đến các tầng khác. + Nhược điểm:
Cần phải định nghĩa cẩn thận chức năng các tầng vì mỗi tầng chỉ có thể sử dụng các tầng dưới nó
Đôi khi khó khăn trong việc xác định một chức năng của HĐH nằm tại
tầng nào Tăng chi phí cho việc gọi các lời gọi hệ thống thông qua nhiều tầng - Kiến Trúc Vi Nhân:
+ Di chuyển nhiều chức năng từ nhân lên mức người dùng. lOMoAR cPSD| 58504431
+ Việc giao tiếp giữa các module người dùng được thực hiện bằng cách sử dụng cơ chế
chuyển thông điệp + Ưu điểm:
Dễ dàng mở rộng một microkernel
Dễ dàng chuyển đổi hệ điều hành sáng các kiến trúc mới
Tin cậy hơn và an toàn hơn (ít mã lệnh chạy ở mức nhân hơn) +
Nhược điểm: chi phí giao tiếp giữa tiến trình của người dùng và nhân.
- Khái Niệm Tiến Trình:
+ Tiến trình là thể hiện (instance) của một chương trình máy tính trong bộ nhớ, đang thực thi hoặc chờ thực thi
+ Mỗi tiến trình thường được gán 1 số định danh tiến trình (processidentifier, pid), dùng để định danh các tiến trình
+ Một tiến trình bao gồm:
Mã lệnh chương trình (program code)
Bộ đếm chương trình (program counter) và các thanh ghi của CPU Ngăn xếp (stack)
Phần dữ liệu (data section)
Có thể gồm phần bộ nhớ cấp phát động khi tiến trình thực thi
(heap) - Chương Trình & Tiến Trình:
+ Chương trình là một thực thể bị động, được lưu trữ trên đĩa.
+ Tiến trình là một thực thể chủ động, lưu trú trên bộ nhớ chính.
+ Khi một chương trình được kích hoạt (nhấpchuột, CLI, . . . ), một thể hiện của chương trình sẽ
được nạp lên bộ nhớ, tạo ra 1 tiến trình.
+ Một chương trình có thể có vài tiến trình trong bộ nhớ.
- Trạng Thái Của Tiến Trình (Process State):
+ Một tiến trình có thể có một trong các trạng thái
sau: new: tiến trình đang được khởi tạo.
running: các chỉ thị của tiến trình đang được thực thi.
waiting: tiến trình đang chờ đợi một sự kiện nào đó xảy ra (hoàn thànhI/O, tín hiệu
từ tiến trình khác, . . . )
ready: tiến trình sẵn sàng để thực thi (đang đợi để được sử
dụng CPU) terminated: tiến trình đã kết thúc. - Sơ Đồ Chuyển Trạng Thái Của Tiến Trình: lOMoAR cPSD| 58504431
- Khối Điều Khiển Tiến Trình (PCB):
+ Chứa thông tin của tiến trình trong Hệ điều hành:
Trạng thái của tiến trình: ready, running,…
Bộ đếm chương trình: chỉ thị kế tiếp sẽ được thực thi
Các thanh ghi: phụ thuộc vào k/trúc máy tính
Thông tin về định thời sử dụng CPU
Thông tin về quản lý bộ nhớ
Thông tin về chi phí: t/gian sử dụng CPU, pid, . . .
Thông tin về trạng thái nhập/xuất: các thiết bị đang được cấp phát, danh sách tập tin đang mở, . . .
- Chuyển CPU Giữa Các Tiến Trình:
+ PCB là nơi lưu giữ trạng thái của tiến trình
+ Trạng thái của tiến trình phải được lưu trữ vào PCB khi một interrupt xuất hiện, nhằm cho
phép tiến trình có thể tiếp tục chính xác về sau.
+ Tác vụ chuyển CPU còn được gọi là chuyển ngữ cảnh (context switch).
- Định Thời Tiến trình (Process Scheduling):
+ Là một tác vụ của hệ điều hành trong các hệ thống đa chương dựa trên phân chia thời gian
(timesharing) nhằm lựa chọn một tiến trình được phép sử dụng CPU và phân bổ thời gian sử
dụng CPU của tiến trình
+ Thành phần lựa chọn/định thời cho các tiến trình được gọi là bộ định thời tiến trình (process scheduler).
+ Bộ định thời tiến trình dùng 1 hệ thống các hàng đợi (queue) để sắp xếp và định thời cho các tiến trình.
- Hàng Đợi Tiến Trình (Process Queues):
+ Các hàng đợi dùng cho việc định thời tiến trình
Hàng đợi công việc (job queue): tập hợp tất cả các tiến trình trong hệ thống
Hàng đợi sẵn sàng (ready queue): tập hợp tất cả các tiến trình đang nằm trong bộ nhớ, sẵn sàng
và đang chờ để thực thi.
Hàng đợi thiết bị (device queue): tập hợp các tiến trình đang đợi sử dụng một thiết
bị vào ra. + Tiến trình có thể di chuyển giữa các hàng đợi khác nhau. - Sơ Đồ Định Thời Tiến Trình: lOMoAR cPSD| 58504431
- Các Loại Bộ Định Thời (Shcedulers):
+ Bộ định thời dài kỳ (long-term scheduler/job scheduler):
Chọn tiến trình nào sẽ được đặt vào hàng đợi sẵn sàng (nạp vào bộ nhớ)
Được gọi rất không thường xuyên (seconds, minutes) ⇒ có thể chậm
Khống chế cấp độ đa chương (degree of
multiprogramming) + Bộ định thời ngắn kỳ (short-term scheduler/CPU scheduler):
Chọn ra tiến trình sẽ được thực thi kế tiếp và cấp CPU cho nó.
Được gọi rất thường xuyên (milliseconds) ⇒ phải
nhanh - Bộ Định Thời Trung Kỳ (Medium-term):
+ là mức trung gian giữa bộ định thời ngắn và dài kỳ
+ thực hiện hoán vị (swapping) các tiến trình ra/vào bộ nhớ/đĩa do cạnh tranh CPU,
bộ nhớ + thường được sử dụng trong các hệ thống phân chia thời gian.
- Các Thao Tác Cơ Bản Trên Tiến Trình: 2 thao tác + Tạo tiến trình + Kết thúc tiến trình
- Tạo Tiến Trình:
+ Một tiến trình (cha) có thể tạo những tiến trình khác (con) . . .
+ Quan hệ “cha–con” của các tiến trình tạo nên cây tiến trình.
- Một Số Vấn Đề Giữa Tiến Trình Cha – Con: + Chia sẻ tài nguyên:
Tiến trình cha và con chia sẻ tất cả các tài nguyên lOMoAR cPSD| 58504431
Tiến trình cha chia sẻ một phần tài nguyên cho tiến trình con
Tiến trình cha và con không chia sẻ gì cả
+ Dữ liệu khởi tạo: được chuyển từ tiến trình cha sang con.
+ Thực thi: song song hoặc tuần tự theo thứ tự cha – con. + Không gian địa chỉ:
Tiến trình con sao chép từ tiến trình cha (cả code và dữ
liệu) Tiến trình con tự nạp chương trình riêng.
- Tạo Tiến Trình Trên UNIX & Windows NT: + UNIX:
fork(): lời gọi hệ thống để tạo tiến trình mới.
execlp(): thay thế không gian địa chỉ của tiến trình gọi bằng một tiến trình mới. + Windows NT:
CreateProcess(...): lời gọi hệ thống để tạo 1 tiến trình con và thay thế không gian địa
chỉ tiến trình con bằng 1 tiến trình mới.
Tiến trình mới được chỉ định trong đối số của lời gọi hệ
thống. - Kết Thúc Tiến Trình:
+ T/trình thực thi câu lệnh cuối cùng và yêu cầu HĐH xóa nó (exit())
Truyền dữ liệu từ tiến trình con lên tiến trình cha (wait()).
Thu hồi tài nguyên đã được cấp phát cho tiến trình.
+ Tiến trình con kết thúc trước khi t/trình cha gọi wait() ⇒
zombie + Tiến trình con còn thực thi khi t/trình cha đã kết
thúc ⇒ orphan + Tiến trình cha có thể kết thúc tiến trình con (abort()):
Tiến trình con đã có vượt quá số tài nguyên được cấp.
Công việc giao cho tiến trình con làm nay không còn cần thiết nữa.
Tiến trình cha đang thoát: một vài HĐH không cho phép orphan.
- Hợp Tác Tiến Trình (Cooperating Process):
+ Tiến trình độc lập: không thể ảnh hưởng hoặc không bị ảnh hưởng bởi sự thực thi của tiến trình khác.
+ Hợp tác tiến trình: có thể ảnh hưởng hoặc bị ảnh hưởng bởi sự thực thi của tiến trình khác.
+ Thuận lợi của sự hợp tác tiến trình: Chia sẻ thông tin
Gia tăng tốc độ tính toán (nếu máy có nhiều CPU) Module hóa Tiện dụng
- Giao Tiếp Liên Tiến Trình: lOMoAR cPSD| 58504431
+ Các tiến trình muốn trao đổi dữ liệu với nhau cần sử dụng cơ chế giao tiếp liên tiến trình
(interprocess communication, IPC):
- Truyền Thông Điệp (Message Passing):
+ Giao tiếp giữa các tiến trình không cần dùng bộ nhớ chia sẻ ⇒ hữu ích trong môi trường
phân tán, giao tiếp qua mạng.
+ Cần hai thao tác: send(msg) và receive(msg).
+ Tiến trình P và Q muốn giao tiếp với nhau:
Tạo một nối kết giao tiếp (communication link)
Trao đổi thông điệp thông qua send/receive
+ Phương thức cài đặt nối kết giao tiếp (mức luận lý):
Giao tiếp trực tiếp hay gián tiếp
Đồng bộ hay bất đồng bộ
Kích thước thông điệp cố định hay
biến đổi - Giao Tiếp Trực Tiếp (Direct Communication):
+ Các tiến trình phải được đặt tên rõ ràng:
Send(P, msg): gởi thông điệp tới tiến trình P.
Receive(Q, msg): nhận thông điệp từ tiến trình Q.
+ Các thuộc tính của nối kết giao tiếp:
Các nối kết được thiết lập tự động.
Một nối kết kết hợp với chính xác một cặp tiến trình.
Giữa mỗi cặp tiến trình tồn tại chính xác một nối kết.
Nối kết có thể một hướng, nhưng thường là hai hướng.
Giao tiếp bất đối xứng: Send(P, msg), Receive(id, msg).
- Giao Tiếp Gián Tiếp (Indirect Communication):
+ Các thông điệp được gửi và nhận thông qua mailbox hay port.
Mỗi mailbox có một định danh (id) duy nhất.
Các tiến trình chỉ có thể giao tiếp nếu chúng dùng chung mailbox.
Send/Receive(A, msg): gởi/nhận thông điệp tới/từ hộp thư A.
+ Các thuộc tính của nối kết gián tiếp:
Nối kết chỉ được thiết lập nếu các tiến trình chia sẻ một hộp thư chung. lOMoAR cPSD| 58504431
Một nối kết có thể kết hợp với nhiều tiến trình.
Mỗi cặp tiến trình có thể dùng chung nhiều nối kết giao tiếp.
Nối kết có thể một hướng hay hai hướng.
- Các Tác Vụ Trong Giao Tiếp Gián Tiếp:
+ Các tác vụ cơ bản: tạo mailbox mới, gửi và nhận thông điệp qua mailbox, và xóa mailbox. + Chia sẻ mailbox:
Các tiến trình có thể chia sẻ cùng 1 mailbox.
Vấn đề: nếu 1 tiến trình gửi thì tiến trình nào sẽ nhận?
+ Giải pháp cho việc chia sẻ mailbox:
Một liên kết chỉ tương ứng với 2 tiến trình.
Chỉ cho phép 1 tiến trình thực hiện thao tác nhận tại 1 thời điểm.
HĐH chỉ định tiến trình nhận (1 tiến trình), và thông báo cho tiến trình gửi biết người nhận.
- Đồng Bộ Hóa (Synchronisation):
+ Truyền thông điệp có thể chặn (blocking) hay không chặn (non-
blocking). + Blocking được xem là đồng bộ (synchronous):
Blocking send: tiến trình gửi chờ cho đến khi thông điệp được nhận.
Blocking receive : tiến trình nhận chờ cho đến khi thông điệp sẵn sàng.
+ Non-blocking được xem là bất đồng bộ (asynchronous):
Non-blocking send: gửi thông điệp và tiếp tục thực hiện công việc khác. Non-
blocking receive: nhận một thông điệp hay rỗng.
- Tạo Vùng Đệm (Buffering):
+ Vùng đệm dùng để chứa các thông điệp của 1 nối kết. + Ba cách cài đặt:
Sức chứa là 0 (zero capacity): tiến trình gửi bị chặn đến khi thông điệp được nhận (no buffering!?).
Sức chứa giới hạn (bounded capacity): kích thước vùng đệm giới hạn n thông điệp.
Tiến trình gửi bị chặn khi vùng đệm bị đầy.
Sức chứa không giới hạn (unbounded capacity): kích thước không giới hạn. Tiến
trình gửi không bao giờ bị chặn.
- Các Khái Niệm Định Thời CPU:
+ Định thời biểu CPU là một chức năng cơ bản và quan trọng của các HĐH đa nhiệm
+ Chức năng: phân bổ thời điểm/thời gian sử dụng CPU cho các tiến trình trong hệ thống, nhằm:
tăng hiệu năng (CPU utilisation) sử dụng
CPU giảm thời gian đáp ứng (response time) của hệ thống
+ Ý tưởng cơ bản: phân bố thời gian rãnh rỗi của CPU (khi chờ đợi tiến trình đang thực thi
thực hiện các thao tác nhập xuất) cho các tiến trình khác trong hệ thống.
- Chu Kỳ CPU–I/O (CPU–I/O Burst): + Chu kỳ CPU–I/O:
Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU–I/O. lOMoAR cPSD| 58504431
Một chu kỳ CPU–I/O bao gồm chu kỳ thực thi CPU (CPU burst) và chu kỳ chờ đợi vào/ra (I/O burst).
+ Sự phân bổ sử dụng CPU:
Tiến trình hướng xử lý (CPU-bound process) thường có nhiều chu kỳ CPU dài.
Tiến trình hướng nhập xuất (I/O-bound process) thường có nhiều chu kỳ CPU ngắn.
- Bộ Định Thời CPU (CPU Scheduler):
+ Còn gọi là bộ định thời ngắn kỳ, chọn một trong các tiến trình trong hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi.
+ Quyết định định thời xảy ra khi một tiến trình: 1.
chuyển từ trạng thái đang chạy sang trạng thái chờ đợi 2.
chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng 3.
chuyển từ trạng thái chờ đợi sang trạng thái sẵn sàng 4.
kết thúc (đang chạy sang kết thúc) - Định Thời Trưng Dụng
& Không Trưng Dụng:
+ Định thời không trưng dụng (nonpreemptive scheduling):
Tiến trình được phân CPU có quyền sử dụng CPU đến khi sử dụng xong (k/thúc hoặc
chuyển sang trạng thái chờ, như trường hợp 1 và 4).
+ Định thời trưng dụng (preemptive scheduling):
Bộ định thời có thể thu hồi CPU của tiến trình bất kỳ lúc nào để phân cho tiến trình
khác (trường hợp 2 và 3).
Phức tạp hơn định thời không trưng dụng vì nó phải giải quyết:
Sự cạnh tranh dữ liệu giữa các tiến trình.
Sự trưng dụng khi tiến trình đang thực thi trong chế độ
kernel. Dàn xếp giữa sự trưng dụng và xử lý các ngắt của hệ thống.
- Bộ Điều Phối (Dispatcher):
+ Có nhiệm vụ thực thi việc trao quyền sử dụng CPU cho tiến trình được cấp phát CPU bởi bộ định thời. + Bao gồm các tác vụ: Chuyển ngữ cảnh
Chuyển sang chế độ người dùng
Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại chương trình
đó. + Độ trễ điều phối (dispatcher latency): thời gian dispatcher cần để ngưng một tiến trình và khởi
động một tiến trình khác.
- Tiêu Chí Cho Việc Định Thời: 5 tiêu chí
+ Hiệu suất sử dụng CPU: tỷ lệ giữa thời gian CPU được sử dụng trên tổng thời gian hoạt động của hệ thống.
+ Thời gian đáp ứng (response time): lượng thời gian từ lúc một yêu cầu được đệ trình cho đến
khi bắt đầu được đáp ứng.
+ Thời gian chờ đợi (waiting time): tổng thời gian 1 tiến trình nằm trong hàng đợi sẵn sàng (ready queue). lOMoAR cPSD| 58504431
+ Thời gian xoay vòng (turnaround time): tổng thời gian để thực thi một t/trình, bao gồm các
khoảng t/gian: thực thi, chờ I/O, chờ trong ready queue (= t/điểm kết thúc – t/điểm bắt đầu vào
ready queue). + Thông lượng (throughput): số lượng tiến trình hoàn thành trên một đơn vị thời gian.
- Tối Ưu Hóa Các Tiêu Chí:
+ Các giải thuật định thời được đánh giá thông qua khả năng tối ưu hóa các tiêu chí định thời của nó: 1.
Hiệu suất sử dụng CPU: càng lớn càng tốt 2.
Thông lượng: càng lớn càng tốt 3.
Thời gian xoay vòng: càng nhỏ càng tốt 4.
Thời gian chờ đợi: càng nhỏ càng tốt 5.
Thời gian đáp ứng: càng nhỏ càng tốt- Các Giải Thuật Định Thời:
1. First-come, first-served (FCFS): đến trước được phục vụ trước.
2. Shortest-job-rirst (SJF): công việc ngắn nhất trước.
3. Priority: dựa trên độ ưu tiên.
4. Round-robin (RR): xoay vòng.
5. Multilevel scheduling: hàng đợi đa cấp.
6. Multilevel feedback-queue scheduling: hàng đợi phản hồi đa cấp.
- First-Come, First Served (FCFS):
+ Là giải thuật định thời đơn giản nhất, dựa trên nguyên tắc đến trước, được phục
vụ trước. + Cài đặt: phương pháp đơn giản nhất là dùng hàng đợi FIFO. I + Ưu
điểm: cài đặt dễ dàng, đơn giản và dễ hiểu. + Nhược điểm:
Thời gian chờ đợi trung bình thường là dài.
Không thích hợp cho hệ thống phân chia thời gian do đây là giải thuật định
thời không trưng dụng (nonpreemptive) - Shortest-Job-First (SJF):
+ Ý tưởng cơ bản: phân phối CPU cho tiến trình nào có thời gian thực thi CPU (CPU burst) kế
tiếp nhỏ nhất (shortest-next-CPU-burst alg.)
+ Mỗi tiến trình sẽ được gán 1 độ dài thời gian của lần sử dụng CPU kế tiếp (dự đoán). I
+ Có 2 cách tiếp cận cho việc phân bổ CPU:
Không trưng dụng: tiến trình được giao CPU sẽ chiếm giữ CPU đến khi nó thực thi xong CPU burst.
Trưng dụng: nếu 1 tiến trình mới đến có CPU burst ngắn hơn thời gian thực thi còn
lại của tiến trình đang thực thi, CPU sẽ được lấy lại để giao cho tiến trình mới (shortest- remaining- time-first algorithm, SRTF)
+ SJF cho thời gian chờ đợi trung bình tối ưu (ngắn nhất).
- Thời Gian Sử Dụng CPU Lần Kế Tiếp:
+ Chỉ có thể ước lượng, dựa vào lịch sử của những lần sử dụng CPU
trước đó. + Thời gian sử dụng CPU kế tiếp (công thức trung bình mũ): lOMoAR cPSD| 58504431
Tn+1: ước lượng thời gian sử dụng CPU lần
n + 1 tn: thời gian sử dụng CPU thực tế lần thứ n
α ∈ [0, 1]: hệ số trung bình mũ, dùng để điều chỉnh trọng số cho các giá trị lịch
sử (thông thường được gán giá trị 1/2) - Tùy Biến Hệ Số Trung Bình Mũ:
⇒ không tính đến lịch sử: tình trạng/sự thực thi “hiện thời” được coi như nhất thời, không có ý nghĩa.
⇒ chỉ tính đến thời gian sử dụng CPU thực tế gần nhất.
+ α = 1/2: các giá trị lịch sử thực tế và dự đoán có trọng số tương
đương + Nếu mở rộng công thức, ta có:
+ Vì α và (1 − α) ≤ 1, trọng số của giá trị lịch sử càng xa thì càng nhỏ.
- Giải Thuật Định Thời Có Ưu Tiên (Priority): + Ý tưởng:
Mỗi tiến trình sẽ được gán một chỉ số ưu tiên (priority number, int) .
CPU sẽ được cấp phát cho tiến trình có độ ưu tiên cao nhất, thông thường là có chỉ số ưu tiên nhỏ nhất.
+ SJF là trường hợp đặc biệt của giải thuật này, trong đó thời gian thực thi CPU kế tiếp đóng
vai trò là chỉ số ưu tiên.
+ Có thể cài đặt theo phương pháp trưng dụng hay không trưng dụng.
+ Có thể xảy ra tình trạng “chết đói” (starvation): các tiến trình độ ưu tiên thấp không bao giờ được thực thi.
⇒ Giải pháp: dùng sự “lão hóa” (aging) – các tiến trình đang chờ đợi trong hệ thống sẽ
được tăng dần độ ưu tiên theo thời gian chờ đợi. + Ví dụ: lOMoAR cPSD| 58504431
- Giải Thuật Định Thời Luân Phiên (Round-robin):
+ Bộ điều phối cấp phát xoay vòng cho mỗi tiến trình trong hàng đợi sẵn sàng một đơn vị
thời gian, gọi là định mức thời gian (time quantum, thường khoảng 10–100ms).
Sau khi sử dụng hết t/gian được cấp, CPU bị thu hồi để cấp cho tiến trình khác, tiến
trình bị thu hồi CPU sẽ chuyển vào hàng đợi sẵn sàng.
Bộ đếm thời gian (timer) sẽ phát ra các ngắt sau mỗi định mức thời gian để xoay vòng cấp phát CPU.
+ Nếu hàng đợi sẵn sàng có n tiến trình, định mức thời gian là q:
Mỗi tiến trình sẽ nhận được 1/n tổng thời gian CPU, trong đó thời gian mỗi lần sử dụng tối đa là q
Không có tiến trình nào chờ đợi quá lượng thời gian (n − 1) × q
+ Các Tùy Biến & Hiệu Năng:
q lớn: RR trở thành giải thuật FCFS (FIFO)
q nhỏ: q phải đủ lớn so với thời gian chuyển ngữ cảnh, nếu không, hao phí chuyển
ngữ cảnh sẽ rất cao. + Ví dụ: lOMoAR cPSD| 58504431
- Giải thuật hàng đợi đa cấp (Multilevel scheduling):
+ Chia hàng đợi s/sàng ra thành nhiều hàng đợi với độ ưu tiên khác nhau, ví dụ:
foreground: tương tác, cần ưu tiên cao hơn.
background: bó, cần ít ưu tiên hơn
+ Các tiến trình sẽ được phân phối vào các hàng đợi dựa trên các đặc tính như loại tiến trình
(foreground/background), độ ưu tiên, . . .
+ Mỗi hàng đợi sẽ được áp dụng một giải thuật định thời riêng, tùy vào tính chất của hàng đợi; ví dụ:
foreground (tương tác): cần thời gian đáp ứng nhanh
hơn ⇒ RR background (bó): có thể đáp ứng chậm hơn ⇒ FCFS
+ Tham Số Của Bộ Định Thời:
Bộ định thời đa cấp có thể được định nghĩa bằng những tham số sau: - Số lượng hàng đợi.
- Giải thuật định thời cho từng hàng đợi.
- Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào khi
tiến trình này cần được phục vụ.
+ Chiến Lược Định Thời Giữa Các Hàng
Đợi Định thời với độ ưu tiên cố định:
- Phục vụ tất cả các t/trình trong hàng đợi ưu tiên cao (vd: foreground) rồi
mới đến hàng đợi có độ ưu tiên thấp hơn (vd: background).
- Có khả năng dẫn đến tình trạng “chết đói” (starvation) CPU.
Định thời với phân chia thời gian (time-slice):
- Mỗi hàng đợi sẽ nhận được một khoảng thời gian nào đó của CPU để định
thời cho các tiến trình nằm trong đó.
- Ví dụ: 80% cho foreground với RR, và 20% cho background với FCFS.
- Giải Thuật Hàng Đợi Phản Hồi Đa Cấp (Multilevel feedback-queue scheduling):
+ Hàng đợi sẵn sàng cũng tổ chức giống như trong giải thuật Hàng đợi đa cấp.
+ Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau. lOMoAR cPSD| 58504431
+ Cơ chế định thời có thể được cài đặt theo cách:
Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào hàng đợi có độ ưu tiên thấp hơn.
Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó sẽ được chuyển
sang hàng đợi có độ ưu tiên cao hơn (cơ chế “sự lão hóa”).
+ Tham Số Của Bộ Định Thời
Bộ định thời đa cấp có phản hồi có thể được định nghĩa bằng những tham số sau: - Số lượng hàng đợi
- Giải thuật định thời cho từng hàng đợi.
- Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình.
- Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình .
- Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào khi
tiến trình này cần được phục vụ. + Ví dụ:
- Chính Sách, Cơ Chế & Định Thời:
+ Chính sách (policy) và cơ chế (mechanism) có liên hệ mật thiết đến sự lựa chọn giải thuật định thời.
Policy: Cần làm điều gì (what)?
Mechanism: Làm sao (how) để làm điều đó? + Ví dụ:
Policy: tất cả các người dùng cần được công bằng.
⇒ Mechanism: sử dụng Robin-round.
Policy: Các tiến trình người dùng trả tiền có độ ưu tiên cao hơn các tiến trình người dùng miễn phí.
⇒ Mechanism: sử dụng các giải thuật trưng dụng (preemptive).
- Đánh Giá Giải Thuật: 4 phương pháp+ Mô Hình Xác Định: lOMoAR cPSD| 58504431
Dựa vào tải công việc (workload) được xác định trước và tính toán hiệu năng của
mỗi giải thuật (như thời gian chờ trung bình, . . . ).
Ưu điểm: Đơn giản, nhanh.
Khó khăn: đòi hỏi tập hợp thông tin chính xác thông tin đầu vào ⇒ khó thực hiện trong thực tế. + Mô Hình Hàng Đợi:
Dựa vào sự phân bổ thời gian thực thi CPU và I/O (CPU, I/O burst) và thời gian đến (arrivaltime).
- Thường phân phối theo 1 hàm nào đó (thường là hàm mũ – exponential distribution).
- Dựa vào các phân phối trên, ta có thể tính hiệu năng của mỗi giải thuật (hiệu
năng CPU, t/gian chờ trung bình, chiều dài hàng đợi trung bình).
Chiều dài hàng đợi trung bình (công thức Little): n = λ × W
- λ: tỉ lệ đến trung bình của các tiến trình mới (tiến trình/s).
- W : thời gian chờ trung bình trong hàng đợi. + Mô Phỏng:
+ Cài Đặt Thực Nghiệm:
Cài đặt giải thuật vào hệ điều hành thật cùng với các phương tiện đo lường.
Thực thi các tiến trình và đo lường hiệu năng của giải thuật trên hệ thống thật.
Ưu điểm: Độ chính xác cao. Khó khăn: - Đòi hỏi chi phí cao
- Người dùng có thể phản ứng với sự thay đổi liên tục của hệ thống.