Giáo trình Hệ điều hành - Chương 1: Tổng quan về hệ điều hành

421 trang huongle 7070

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ điều hành - Chương 1: Tổng quan về hệ điều hành", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_he_dieu_hanh_chuong_1_tong_quan_ve_he_dieu_hanh.pdf

Nội dung text: Giáo trình Hệ điều hành - Chương 1: Tổng quan về hệ điều hành

Chapter 1: Tổng quan về hệ điều hành Duy Phan 01/2015
Mục tiêu  Biết được hệ điều hành là gì  Biết được các loại hệ điều hành  Biết được lịch sử phát triển hệ điều hành Phan Duy 2 Tổng quan về hệ điều hành
Chuẩn đầu ra của bài học  Hiểu và phát biểu lại được các khái niệm cơ bản về hệ điều hành, và các thành phần của hệ điều hành  Biết được sự khác biệt cơ bản giữa các loại hệ điều hành Phan Duy 3 Tổng quan về hệ điều hành
Nội dung  Tổng quan  Phân loại hệ điều hành  Lịch sử phát triển hệ điều hành Phan Duy 4 Tổng quan về hệ điều hành
Tổng quan  Định nghĩa hệ điều hành  Cấu trúc hệ thống máy tính  Các chức năng chính của hệ điều hành Phan Duy 5 Tổng quan về hệ điều hành
Định nghĩa  Hệ điều hành là gì? Người dùng  Chương trình trung gian giữa phần cứng máy tính và người sử dụng, cĩ chức năng điều khiển và phối hợp việc sử dụng phần cứng và cung cấp các Các ứng dụng Chạy ứng dụng abc trên dịch vụ cơ bản cho các ứng phần cứng XYZ dụng. Hệ Điều Hành  Mục tiêu Phần cứng  Giúp người dùng dễ dàng sử dụng hệ thống.  Quản lý và cấp phát tài nguyên hệ thống một cách hiệu quả. Phan Duy 6 Tổng quan về hệ điều hành
Định nghĩa (tt) Banking Airline Web browser Application programs system reservation Command Compilers Editors interpreter System programs Operating system Machine language Microprogramming Hardware Physical devices Hình của Dror G. Feitelson Phan Duy 7 Tổng quan về hệ điều hành
Cấu trúc hệ thống máy tính Phan Duy 8 Tổng quan về hệ điều hành
Cấu trúc hệ thống máy tính  Phần cứng (hardware)  Bao gồm các tài nguyên cơ bản của máy tính như CPU, bộ nhớ, các thiết bị I/O  Hệ điều hành (operating system)  Phân phối tài nguyên, điều khiển và phối hợp các hoạt động của các chương trình trong hệ thống.  Chương trình ứng dụng (application programs)  Sử dụng hệ thống tài nguyên để giải quyết một bài tốn tính tốn nào đĩ của người sử dụng.  Ví dụ: compilers, database systems, video games, business programs.  Users (people, machines, other computers) Phan Duy 9 Tổng quan về hệ điều hành
Các chức năng chính của hệ điều hành  Phân chia thời gian xử lý và định thời CPU  Phối hợp và đồng bộ hoạt động giữa các processes (coordination & synchronization)  Quản lý tài nguyên hệ thống (thiết bị I/O, bộ nhớ, file chứa dữ liệu, )  Thực hiện và kiểm sốt access control, protection  Duy trì sự nhất quán (integrity) của hệ thống, kiểm sốt lỗi và phục hồi hệ thống khi cĩ lỗi (error recovery)  Cung cấp giao diện làm việc cho users Phan Duy 10 Tổng quan về hệ điều hành
Nội dung  Tổng quan  Phân loại hệ điều hành  Lịch sử phát triển hệ điều hành Phan Duy 11 Tổng quan về hệ điều hành
Phân loại hệ điều hành  Dưới gĩc độ 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) Phan Duy 12 Tổng quan về hệ điều hành
Phân loại hệ điều hành (tt)  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  Mạng ngang hàng  Mạng cĩ máy chủ: LAN, WAN, Phan Duy 13 Tổng quan về hệ điều hành
Phân loại hệ điều hành (tt)  Dưới gĩc độ hình thức xử lý  Hệ thống xử lý theo lơ  Hệ thống đơn chương (uniprograming OS)  Hệ thống đa chương (multiprogramming OS)  Hệ thống chia sẻ thời gian  Hệ thống song song  Hệ thống phân tán  Hệ thống xử lý thời gian thực Phan Duy 14 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý  Hệ thống đơn chương  Tác vụ được thi hành tuần tự.  Bộ giám sát thường trực  CPU và các thao tác nhập xuất:  Xử lý offline  Đồng bộ hĩa các thao tác bên ngồi – Spooling (Simultaneous Peripheral Operation On Line) Máy tính Nhập chính Xuất Phan Duy 15 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống đa chương  Nhiều cơng việc được nạp đồng thời vào bộ nhớ chính  Khi một tiến trình thực hiện I/O, một tiến trình khác được thực thi  Tận dụng được thời gian rảnh, tăng hiệu suất sử dụng CPU (CPU utilization) Tác vụ I/O Bộ xử lý Kết thúc tác vụ Phan Duy 16 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống đa chương: yêu cầu đối với hệ điều hành  Định thời cơng việc (job scheduling): chọn job trong job pool trên đĩa và nạp nĩ vào bộ nhớ để thực thi.  Quản lý bộ nhớ (memory management)  Định thời CPU (CPU scheduling)  Cấp phát tài nguyên (đĩa, máy in, )  Bảo vệ Phan Duy 17 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt) Hệ điều hành đơn chương Hệ điều hành đa chương Phan Duy 18 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống chia sẻ thời gian  Hệ thống đa nhiệm (multitasking)  Lập lịch CPU  Thời gian chuyển đổi giữa các tác vụ rất ngắn      Bộ xử lý Phan Duy 19 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Yêu cầu đối với OS trong hệ thống time-sharing  Định thời cơng việc (job scheduling)  Quản lý bộ nhớ (memory management)  Virtual memory  Quản lý các quá trình (process management)  Định thời CPU  Đồng bộ các quá trình (synchronization)  Giao tiếp giữa các quá trình (process communication)  Tránh deadlock  Quản lý hệ thống file, hệ thống lưu trữ  Cấp phát hợp lý các tài nguyên  Bảo vệ (protection) Phan Duy 20 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống song song  Hai hoặc nhiều bộ xử lý cùng chia sẻ một bộ nhớ.  Master/Slave : một bộ xử lý chính kiểm sốt một số bộ xử lý I/O Bộ Bộ xử lý xử lý Bộ nhớ chính Phan Duy 21 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống song song (parallel, multiprocessor, hay tightly-coupled system)  Nhiều CPU  Chia sẻ computer bus, clock  Ưu điểm  Năng xuất hệ thống (System throughput): càng nhiều processor thì càng nhanh xong cơng việc  Multiprocessor system ít tốn kém hơn multiple single- processor system: vì cĩ thể dùng chung tài nguyên (đĩa, )  Độ tin cậy: khi một processor hỏng thì cơng việc của nĩ được chia sẻ giữa các processor cịn lại Phan Duy 22 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Phân loại hệ thống song song  Đa xử lý đối xứng (symmetric multiprocessor)  Mỗi processor vận hành một bản sao hệ điều hành giống nhau  Các copy dữ liệu cho nhau khi cần  (Windows NT, Solaris 5.0, Digital UNIX, OS/2, Linux)  Đa xử lý bất đối xứng (asymmetric multiprocessor)  Mỗi processor thực thi một cơng việc khác nhau  Master processor định thời và phân cơng việc cho các slave processors  (SunOS 4.0) Phan Duy 23 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống phân tán Hệ thống máy tính 1 Hệ thống máy tính 2 Giao tiếp mạng Giao tiếp mạng Mạng Bộ xử lý Bộ xử lý Bộ nhớ Bộ nhớ  Mỗi processor cĩ bộ nhớ riêng, giao tiếp với nhau qua các kênh nối như mạng, bus tốc độ cao  Người dùng chỉ thấy một hệ thống đơn nhất Phan Duy 24 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Ưu điểm hệ thống phân tán (distributed system, loosely-coupled system)  Chia sẻ tài nguyên (resource sharing)  Chia sẻ sức mạnh tính tốn (computational sharing)  Độ tin cậy cao (high reliability)  Độ sẵn sàng cao (high availability): các dịch vụ của hệ thống được cung cấp liên tục cho dù một thành phần hardware trở nên hỏng Phan Duy 25 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Các mơ hình hệ thống phân tán  Client-server Server: cung cấp dịch vụ Client: cĩ thể sử dụng dịch vụ của server  Peer-to-peer (P2P) Các peer (máy tính trong hệ thống) đều ngang hàng nhau Khơng cĩ cơ sở dữ liệu tập trung Các peer là tự trị Ví dụ: Gnutella Phan Duy 26 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống thời gian thực (real-time system)  Sử dụng trong các thiết bị chuyên dụng như điều khiển các thử nghiệm khoa học, điều khiển trong y khoa, dây chuyền cơng nghiệp, thiết bị gia dụng, quân sự  Ràng buộc về thời gian: hard và soft real-time  Hard real-time  Hạn chế (hoặc khơng cĩ) bộ nhớ phụ, tất cả dữ liệu nằm trong bộ nhớ chính (RAM hoặc ROM)  Yêu cầu về thời gian đáp ứng/xử lý rất nghiêm ngặt, thường sử dụng trong điều khiển cơng nghiệp, robotics,  Soft real-time  Thường được dùng trong lĩnh vực multimedia, virtual reality với yêu cầu mềm dẻo hơn về thời gian đáp ứng Phan Duy 27 Tổng quan về hệ điều hành
Phân loại dưới gĩc độ hình thức xử lý (tt)  Hệ thống nhúng  Điện thoại di động (smartphone)  Máy tính bảng  Đặc trưng của các thiết bị này Bộ nhớ nhỏ (512 KB - 128 MB - 4GB) Tốc độ processor thấp (để ít tốn pin) Màn hình hiển thị cĩ kích thước nhỏ Cĩ thể dùng các cơng nghệ kết nối như IrDA, Bluetooth, wireless Cĩ thể cĩ một hoặc nhiều cảm biến khác nhau Phan Duy 28 Tổng quan về hệ điều hành
Nội dung  Tổng quan  Phân loại hệ điều hành  Lịch sử phát triển hệ điều hành Phan Duy 29 Tổng quan về hệ điều hành
Lịch sử phát triển của 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 1 nhĩm người  Lưu trên phiếu đục lỗ  Thế hệ 2 (1955 - 1965)  Xuất hiện sự phân cơng cơng việc  Hệ thống sử lý theo lơ ra đời, lưu trên băng từ  Hoạt động dưới sự điều khiển đặc biệt của 1 chương trình Phan Duy 30 Tổng quan về hệ điều hành
3. Lịch sử phát triển của hệ điều hành  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)  Ra đời máy tính cá nhân, IBM PC  HĐH MS-DOS, MacOS (Apple Macintosh), MS Windows, OS/1  Linux, QNX, HĐH mạng, 31 Phan Duy 31 Tổng quan về hệ điều hành
Windows And Linux Evolution  Nhân Windows và Linux được dựa trên những nền tảng phát triển từ giữa những năm 1970s 1970 1980 1990 2000 1970 1980 1990 2000 (see for diagrams showing history of Windows & Unix) Phan Duy 32 Tổng quan về hệ điều hành
Tổng kết  Định nghĩa HĐH  Các chức năng của HĐH Phan Duy 33 Tổng quan về hệ điều hành
Tổng kết  Dưới gĩc độ loại máy tính  MainFrame  Server  CPU  Máy tính cá nhân (PC)  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) Phan Duy 34 Tổng quan về hệ điều hành
Tổng kết Dưới gĩc độ hệ thống xử lý  Hệ thống xử lý theo lơ  Hệ thống chia sẻ thời gian  Hệ thống song song  Hệ thống phân tán  Hệ thống xử lý thời gian thực Phan Duy 35 Tổng quan về hệ điều hành
Câu hỏi ơn tập  Nêu cấu trúc hệ thống máy tính?  HĐH cĩ những chức năng chính nào?  Theo gĩc độ hệ thống xử lý, HĐH được phân thành mấy loại? Kể tên?  Những yêu cầu của hệ điều hành đối với hệ thống chia sẻ thời gian? Phan Duy 36 Tổng quan về hệ điều hành
Kết thúc chương 1 Phan Duy 37 Tổng quan về hệ điều hành
Chương 2: Cấu trúc Hệ Điều Hành Duy Phan 01/2015
Ơn tập chương 1  Nêu cấu trúc hệ thống máy tính?  HĐH cĩ những chức năng chính nào?  Theo gĩc độ hệ thống xử lý, HĐH được phân thành mấy loại? Kể tên?  Những yêu cầu của hệ điều hành đối với hệ thống chia sẻ thời gian?  Định nghĩa hệ điều hành? Duy Phan 2 Cấu trúc hệ điều hành
Mục tiêu  Biết được các thành phần của hệ điều hành  Hiểu được các dịch vụ mà hệ điều hành cung cấp  Hiểu được cấu trúc của một hệ thống máy tính Duy Phan 3 Cấu trúc hệ điều hành
Nội dung  Các thành phần của hệ điều hành  Các dịch vụ hệ điều hành cung cấp  Lời gọi hệ thống (System call)  Các chương trình hệ thống (System programs)  Cấu trúc hệ thống  Máy ảo (Virtual machine) Duy Phan 4 Cấu trúc hệ điều hành
Các thành phần của hệ điều hành  Quản lý tiến trình  Quản lý bộ nhớ chính  Quản lý file  Quản lý hệ thống I/O  Quản lý hệ thống lưu trữ thứ cấp  Hệ thống bảo vệ  Hệ thống thơng dịch lệnh Duy Phan 5 Cấu trúc hệ điều hành
Quản lý tiến trình  Tiến trình (hay Quá trình) là gì?  Tiến trình khác chương trình ở điểm gì? Duy Phan 6 Cấu trúc hệ điều hành
Quản lý tiến trình  Để hồn thành cơng việc, một tiến trình cần:  CPU  Bộ nhớ  File  Thiết bị I/O,  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ác cơ chế  Đồng bộ hoạt động các tiến trình  Giao tiếp giữa các tiến trình  Khống chế tắc nghẽn Duy Phan 7 Cấu trúc hệ điều hành
Quản lý bộ nhớ chính  Bộ nhớ chính là trung tâm của các thao tác, xử lý  Để nâng cao hiệu suất sử dụng CPU, hệ điều hành cần quản lý bộ nhớ thích hợp  Các nhiệm vụ chính:  Theo dõi, quản lý các vùng nhớ trống và đã cấp phát  Quyết định sẽ 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 Duy Phan 8 Cấu trúc hệ điều hành
Quản lý bộ nhớ chính Duy Phan 9 Cấu trúc hệ điều hành
Quản lý bộ nhớ chính Duy Phan 10 Cấu trúc hệ điều hành
Quản lý file  Hệ thống file  File  Thư mục  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 Duy Phan 11 Cấu trúc hệ điều hành
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  Cĩ chức năng:  Cơ chế: buffering, caching, spooling  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 Duy Phan 12 Cấu trúc hệ điều hành
Quản lý hệ thống lưu trữ thứ cấp  Bộ nhớ chính: kích thước nhỏ, là mơi trường chứa tin khơng bền vững => cần hệ thống lưu trữ thứ cấp để lưu trữ bền vững các dữ liệu, chương trình  Phương tiện lưu trữ thơng dụng là đĩa từ, đĩa quang  Nhiệm vụ của hệ điều hành trong quản lý đĩa  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 họat động cho đĩa (disk scheduling) => Sử dụng thường xuyên => ảnh hưởng lớn đến tốc độ của cả hệ thống => cần hiệu quả Duy Phan 13 Cấu trúc hệ điều hành
Hệ thống bảo vệ  Trong hệ thống cho phép nhiều user hay nhiều process diễn ra đồng thờ  Kiểm sốt tiến trình người dùng đăng nhập/ xuất và sử dụng hệ thống  Kiểm sốt việc truy cập các tài nguyên trong hệ thống  Bảo đảm những user/process chỉ được phép sử dụng các tài nguyên dành cho nĩ  Các nhiệm vụ của hệ thống bảo vệ  Cung cấp cơ chế kiểm sốt đăng nhập/ xuất  Phân định được sự truy cập tài nguyên hợp pháp và bất hợp pháp (authorized/unauthorized)  Phương tiện thi hành các chính sách (enforcement of policies) (vídụ: cần bảo vệ dữ liệu của ai đối với ai) Duy Phan 14 Cấu trúc hệ điều hành
Hệ thống thơng dịch lệnh  Là giao diện chủ yếu giữa người dùng và OS  Ví dụ: shell, mouse-based window-and-menu  Khi user login  command line interpreter (shell) chạy, và chờ nhận lệnh từ người dùng, thực thi lệnh và trả kết quả về.  Các lệnh ->bộ điều khiển lệnh ->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 số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 Duy Phan 15 Cấu trúc hệ điều hành
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 theo yêu cầu của c.trình  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 hai cách:  Chia sẽ bộ nhớ (Shared memory)  Chuyển thơng điệp (Message passing)  Phát hiện lỗi  Trong CPU, bộ nhớ, trên thiết bị I/O (dữ liệu hư, hết giấy, )  Do chương trình: chia cho 0, truy cập đến địa chỉ bộ nhớ khơng cho phép. Duy Phan 16 Cấu trúc hệ điều hành
Các dịch vụ hệ điều hành cung cấp (tt)  Ngồi ra cịn các dịch vụ giúp tăng hiệu suất của hệ thống:  Cấp phát tài nguyên (resource allocation) Tài nguyên: CPU, bộ nhớ chính, ổ đĩa, OS cĩ các routine tương ứng  Kế tốn (accounting) Nhằm lưu vết user để tính phí hoặc đơn giản để thống kê. Duy Phan 17 Cấu trúc hệ điều hành
Các dịch vụ hệ điều hành cung cấp (tt)  Ngồi ra cịn các dịch vụ giúp tăng hiệu suất của hệ thống:  Bảo vệ (protection) Hai tiến trình khác nhau khơng được ảnh hưởng nhau Kiểm sốt được các truy xuất tài nguyên của hệ thống  An ninh (security) Chỉ các user được phép sử dụng hệ thống mới truy cập được tài nguyên của hệ thống (vd: thơng qua username và password) Duy Phan 18 Cấu trúc hệ điều hành
Lời gọi hệ thống  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  Ví dụ: open, read, write file  Thơng thường ở dạng thư viện nhị phân (binary libraries) hay giống như các lệnh hợp ngữ  Trong các ngơn ngữ lập trình cấp cao, một số thư viện lập trình được xây dựng dựa trên các thư viện hệ thống (ví dụ Windows API, thư viện GNU C/C++ như glibc, glibc++, )  Ba phương pháp truyền tham số khi sử dụng system call  Qua thanh ghi  Qua một vùng nhớ, địa chỉ của vùng nhớ được gửi đến hệ điều hành qua thanh ghi  Qua stack Duy Phan 19 Cấu trúc hệ điều hành
Lời gọi hệ thống (tt) Chuỗi các lời gọi hệ thống để copy nội dung từ file này đến file khác Duy Phan 20 Cấu trúc hệ điều hành
Lời gọi hệ thống (tt) Một số lời gọi hệ thống trong windows và unix Duy Phan 21 Cấu trúc hệ điều hành
Các chương trình hệ thống  Chương trình hệ thống (system program, phân biệt với application program) gồm  Quản lý hệ thống file: như create, delete, rename, list  Thơng tin trạng thái: như date, time, dung lượng bộ nhớ trống  Soạn thảo file: như file editor  Hỗ trợ ngơn ngữ lập trình: như compiler, assembler, interpreter  Nạp, thực thi, giúp tìm lỗi chương trình: như loader, debugger  Giao tiếp: như email, talk, web browser   Người dùng chủ yếu làm việc thơng qua các system program (khơng làm việc “trực tiếp” với các system call) Duy Phan 22 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Hệ điều hành là một chương trình lớn  Nĩ cĩ nhiều dạng cấu trúc khác nhau:  Cấu trúc đơn giản - MS-DOS  Cấu trúc phức tạp hơn – UNIX  Cấu trúc phân tầng  Cấu trúc vi nhân Duy Phan 23 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Cấu trúc đơn giản (monolithic)  MS-DOS: khi thiết kế, do giới hạn về dung lượng bộ nhớ nên khơng phân chia thành các module (modularization) và chưa phân chia rõ chức năng giữa các phần của hệ thống Cấu trúc phân tầng của MS-DOS Duy Phan 24 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Cấu trúc phức tạp hơn (more complex)  UNIX: gồm hai phần cĩ thể tách rời nhau Nhân (cung cấp file system, CPU scheduling, memory management, và một số chức năng khác) và system program Duy Phan 25 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Cấu trúc phân tầng: HĐH được chi thành nhiều lớp (layer).  Lớp dưới cùng: hardware  Lớp trên cùng là giao tiếp với user  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  Mỗi lớp tương đương một đối tượng trừu tượng: cấu trúc dữ liệu + thao tác  Phân lớp cĩ lợi ích gì?  Gỡ rối (debugger)  kiểm tra hệ thống  thay đổi chức năng Duy Phan 26 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Cấu trúc phân tầng:  Lần đầu tiên được áp dụng cho HĐH THE (Technische Hogeschool Eindhoven) Duy Phan 27 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Vi nhân: phân chia module theo microkernel (CMU Mach OS, 1980)  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 như quản lý tiến trình, bộ nhớ và cơ chế giao tiếp giữa các tiến trình  Giao tiếp giữa các module qua cơ chế truyền thơng điệp một module Application OS/2 POSIX application application File POSIX server OS/2 server server Microkernel Duy Phan 28 Cấu trúc hệ điều hành
Cấu trúc hệ thống (tt)  Vi nhân:  Lợi ích: dễ mở rộng HĐH  Một số HĐH hiện đại sử dụng vi nhân:  Tru64 UNIX (Digital UNIX trước đây): nhân Mach  Apple MacOS Server : nhân Mach  QNX – vi nhân cung cấp: truyền thơng điệp, định thời CPU, giao tiếp mạng cấp thấp và ngắt phần cứng  Windows NT: chạy các ứng dụng khác nhau win32, OS/2, POSIX (Portable OS for uniX) Duy Phan 29 Cấu trúc hệ điều hành
Máy ảo  Làm thế nào để thực thi một chương trình MS-DOS trên một hệ thống Sun với hệ điều hành Solaris ?  Tạo một máy ảo Intel bên trên hệ Intel x86 Application điều hành Solaris và hệ thống Sun Intel x86 VM  Các lệnh Intel (x86) được máy ảo VM interpretation Intel chuyển thành lệnh tương ứng Solaris kernel của hệ thống Sun Sun hardware Duy Phan 30 Cấu trúc hệ điều hành
Máy ảo  Từ OS layer đến máy ảo (virtual machine) Duy Phan 31 Cấu trúc hệ điều hành
Máy ảo  Từ OS layer đến máy ảo (virtual machine) processes processes processes processes programming kernel kernel kernel interface VM1 VM2 VM3 kernel Virtual-machine implementation hardware hardware Non-virtual machine Virtual machine system model system model Duy Phan 32 Cấu trúc hệ điều hành
Máy ảo Ảo hĩa phần mềm Ảo hĩa phần cứng Duy Phan 33 Cấu trúc hệ điều hành
Kết thúc chương 2 Duy Phan 01/2015
Chương 3: Tiến trình Duy Phan 01/2015
Ơn tập chương 2 Duy Phan 2 01/2015
Mục tiêu  Hiểu được khái niệm và các trạng thái của tiến trình  Biết được các thơng số của tiến trình  Biết được các khái niệm về định thời tiến trình  Biết được các tác vụ cơ bản của một tiến trình  Hiểu được cách giao tiếp giữa các tiến trình Duy Phan 3 01/2015
Nội dung  Khái niệm cơ bản  Trạng thái tiến trình  Khối điều khiển tiến trình  Định thời tiến trình  Các tác vụ đối với tiến trình  Sự cộng tác giữa các tiến trình  Giao tiếp giữa các tiến trình  Tiểu trình Duy Phan 4 01/2015
Khái niệm cơ bản  Các hoạt động của CPU được gọi là gì?  Hệ thống bĩ (Batch system): jobs  Time-shared systems: use program, task  Các hoạt động là tương tự → gọi là process  tiến trình (prcess) là gì?  Một chương trình đang thực thi Duy Phan 5 01/2015
Khái niệm cơ bản (tt)  Một tiến trình bao gồm:  Text section (program code)  Data section (chứa global variables)  Program counter (PC)  Process status word (PSW)  Stack pointer (SP)  Memory management registers  Duy Phan 6 01/2015
Khái niệm cơ bản (tt)  Các bước nạp chương trình vào bộ nhớ: Duy Phan 7 01/2015
Khái niệm cơ bản (tt)  Chương trình -> tiến trình:  Dùng load module để biểu diễn chương trình thực thi được  Layout luận lý của process image Executable Process image binary file (load in main module) memory program start address program code code data data stack Duy Phan 8 01/2015
Khái niệm cơ bản (tt)  Các bước khởi tạo tiến trình:  Cấp phát một định danh duy nhất cho tiến trình  Cấp phát khơng gian nhớ để nạp tiến trình  Khởi tạo khối dữ liệu Process Control Block (PCB) cho tiến trình  Thiết lập các mối liên hệ cần thiết (ví dụ: sắp PCB vào hàng đợi định thời, ) Duy Phan 9 01/2015
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 cần CPU  running: các lệnh của tiến trình đang được thực thi  waiting: hay là blocked, tiến trình đợi I/O hồn tất, tín hiệu  terminated: tiến trình đã kết thúc Duy Phan 10 01/2015
Trạng thái tiến trình (tt) terminated new admit dispatch exit ready running interrupt I/O or event I/O or completion event wait waiting Chuyển đổi giữa các trạng thái của tiến trình Duy Phan 11 01/2015
Trạng thái tiến trình (tt)  Chuỗi trạng thái của /* test.c */ tiến trình test như sau int main(int argc, char argv) (trường hợp tốt nhất): {  new printf(“Hello world\n"); exit(0);  ready }  running Biên dịch chương trình trong  waiting (do chờ I/O Linux: gcc test.c –o test khi gọi printf) Thực thi chương trình test:  ready ./test  running Trong hệ thống sẽ cĩ một tiến trình test được tạo ra, thực thi  terminated và kết thúc. Duy Phan 12 01/2015
Process control block  Mỗi tiến trình trong hệ thống đều được cấp phát một Process Control Block (PCB)  PCB là một trong các cấu trúc dữ liệu quan trọng nhất của hệ điều hành  PCB gồm:  Trạng thái tiến trình: new, ready, running,  Bộ đếm chương trình  Các thanh ghi  Thơng tin lập thời biểu CPU: độ ưu tiên,  Thơng tin quản lý bộ nhớ  Thơng tin: lượng CPU, thời gian sử dụng,  Thơng tin trạng thái I/O Duy Phan 13 01/2015
Process control block (tt)  Lưu đồ chuyển CPU từ tiến trình này đến tiến trình khác Duy Phan 14 01/2015
Yêu cầu đối với hệ điều hành về quản lý tiến trình  Hỗ trợ sự thực thi luân phiên giữa nhiều tiến trình  Hiệu suất sử dụng CPU  Thời gian đáp ứng  Phân phối tài nguyên hệ thống hợp lý  Tránh deadlock, trì hỗn vơ hạn định  Cung cấp cơ chế giao tiếp và đồng bộ hoạt động các tiến trình  Cung cấp cơ chế hỗ trợ user tạo/kết thúc tiến trình Duy Phan 15 01/2015
Quản lý các tiến trình: các hàng đợi Ví dụ các PCB running 7 process number ready 11 4 2 17 waiting 19 11 Duy Phan 16 01/2015
Định thời tiến trình  Tại sao phải định thời?  Đa chương  Cĩ vài tiến trình chạy tại các thời điểm  Mục tiêu: tận dụng tối đa CPU  Chia thời  User tương tác với mỗi chương trình đang thực thi  Mục tiêu: tối thiểu thời gian đáp ứng Duy Phan 17 01/2015
Các hàng đợi định thời  Hàng đợi cơng việc-Job queue  Hàng đợi sẵn sàng-Ready queue  Hàng đợi thiết bị-Device queues  Duy Phan 18 01/2015
Các hàng đợi định thời (tt) Lưu đồ hàng đợi của định thời tiến trình Duy Phan 19 01/2015
Bộ định thời  Bộ định thời cơng việc (Job scheduler) hay bộ định thời dài (long-term scheduler)  Bộ định thời CPU hay bộ định thời ngắn  Các tiến trình cĩ thể mơ tả như:  tiến trình hướng I/O  tiến trình hướng CPU  Thời gian thực hiện khác nhau -> kết hợp hài hịa giữa chúng Duy Phan 20 01/2015
Bộ định thời trung gian  Đơi khi hệ điều hành (như time-sharing system) cĩ thêm medium- term scheduling để điều chỉnh mức độ đa chương của hệ thống  Medium-term scheduler  chuyển tiến trình từ bộ nhớ sang đĩa (swap out)  chuyển tiến trình từ đĩa vào bộ nhớ (swap in) Duy Phan 21 01/2015
Các tác vụ đối với tiến trình  Tạo tiến trình mới:  Một tiến trình cĩ thể tạo nhiều tiến trình mới thơng qua một lời gọi hệ thống create-process (vd: hàm fork trong Unix)  Ví dụ: (Unix) Khi user đăng nhập hệ thống, một command interpreter (shell) sẽ được tạo ra cho user  tiến trình được tạo là tiến trình con của tiến trình tạo (tiến trình cha)  Quan hệ cha-con định nghĩa một cây tiến trình Duy Phan 22 01/2015
Cây tiến trình trong Linux/Unix init pid = 1 login kthreadd sshd pid = 8415 pid = 2 pid = 3028 bash khelper pdflush sshd pid = 8416 pid = 6 pid = 200 pid = 3610 tcsch ps emacs pid = 4005 pid = 9298 pid = 9204 Duy Phan 23 01/2015
Các tác vụ đối với tiến trình (tt)  Tạo tiến trình mới:  tiến trình con nhận tài nguyên: từ HĐH hoặc từ tiến trình cha  Chia sẻ tài nguyên của tiến trình cha  tiến trình cha và con chia sẻ mọi tài nguyên  tiến trình con chia sẻ một phần tài nguyên của cha  Trình tự thực thi  tiến trình cha và con thực thi đồng thời (concurrently)  tiến trình cha đợi đến khi các tiến trình con kết thúc Duy Phan 24 01/2015
Về quan hệ cha/con  Khơng gian địa chỉ:  Khơng gian địa chỉ của tiến trình con được nhân bản từ cha  Khơng gian địa chỉ của tiến trình con được khởi tạo từ tamplate  Ví dụ trong Unix/Linux  System call fork() tạo một tiến trình mới  System call exec() dùng sau fork() để nạp một chương trình mới vào khơng gian nhớ của tiến trình mới Duy Phan 25 01/2015
Ví dụ tạo process với fork() #include #include int main (int argc, char *argv[]){ int pid; /* create a new process */ pid = fork(); if (pid > 0){ printf(“This is parent process”); wait(NULL); exit(0);} else if (pid == 0) { printf(“This is child process”); execlp(“/bin/ls”, “ls”, NULL); exit(0);} else { // pid < 0 printf(“Fork error\n”); exit(-1); } } Duy Phan 26 01/2015
Các tác vụ đối với tiến trình (tt)  Kết thúc tiến trình:  tiến trình tự kết thúc  tiến trình kết thúc khi thực thi lệnh cuối và gọi system routine exit  tiến trình kết thúc do tiến trình khác (cĩ đủ quyền, vd: tiến trình cha của nĩ)  Gọi system routine abort với tham số là pid (process identifier) của tiến trình cần đượ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 (vùng nhớ, I/O buffer, ) Duy Phan 27 01/2015
Cộng tác giữa các tiến trình  Trong tiến trình thực thi, các tiến trình cĩ thể cộng tác (cooperate) để hồn thành cơng việc  Các tiến trình cộng tác để  Chia sẻ dữ liệu (information sharing)  Tăng tốc tính tốn (computational speedup)  Nếu hệ thống cĩ nhiều CPU, chia cơng việc tính tốn thành nhiều cơng việc tính tốn nhỏ chạy song song  Thực hiện một cơng việc chung  Xây dựng một phần mềm phức tạp bằng cách chia thành các module/process hợp tác nhau  Sự cộng tác giữa các tiến trình yêu cầu hệ điều hành hỗ trợ cơ chế giao tiếp và cơ chế đồng bộ hoạt động của các tiến trình Duy Phan 28 01/2015
Bài tốn người sản xuất-người tiêu thụ  Producer tạo ra các dữ liệu và consumer tiêu thụ, sử dụng các dữ liệu đĩ  Sự trao đổi thơng tin thực hiện qua buffer  unbounded buffer: kích thước buffer vơ hạn (khơng thực tế)  bounded buffer: kích thước buffer cĩ hạn  Producer và consumer phải hoạt động đồng bộ vì  Consumer khơng được tiêu thụ khi producer chưa sản xuất  Producer khơng được tạo thêm sản phẩm khi buffer đầy Duy Phan 29 01/2015
Giao tiếp liên tiến trình  IPC là cơ chế cung cấp bởi hệ điều hành nhằm giúp các tiến trình:  Giao tiếp với nhau  Đồng bộ hoạt động  mà khơng cần chia sẻ khơng gian địa chỉ  IPC cĩ thể được cung cấp bởi message passing system Duy Phan 30 01/2015
Hệ thống truyền thơng điệp Làm thế nào để các tiến trình giao tiếp nhau?  Đặt tên (Naming)  Giao tiếp trực tiếp  send(P, msg): gửi thơng điệp đến tiến trình P  receive(Q, msg): nhận thơng điệp đến từ tiến trình Q  Giao tiếp gián tiếp: thơng qua mailbox hay port  send(A, msg): gửi thơng điệp đến mailbox A  receive(Q, msg): nhận thơng điệp từ mailbox B  Đồng bộ hĩa (Synchronization): blocking send, nonblocking send, blocking receive, nonblocking receive Duy Phan 31 01/2015
Hệ thống truyền thơng điệp (tt) Làm thế nào để các tiến trình giao tiếp nhau?  Tạo vùng đệm (Buffering): dùng queue để tạm chứa các message  Khả năng chứa là 0 (Zero capacity hay no buffering)  Bounded capacity: độ dài của queue là giới hạn  Unbounded capacity: độ dài của queue là khơng giới hạn Duy Phan 32 01/2015
Tiểu trình - Thread  Tiểu trình: là một đơn vị cơ bản sử dụng CPU gồm:  Thread ID, PC, Registers, Stack và chia sẻ chung code, data, resourses (files) Duy Phan 33 01/2015
PCB và TCB trong mơ hình multithreads PCB pid Thread Control Block Threads list TCB Context tid (Mem, global State ressources ) (State, details) Relatives Context ( Dad, children) (IP, local stack ) Scheduling statistic Duy Phan 34 01/2015
Lợi ích của tiến trình đa luồng  Đáp ứng nhanh: cho phép chương trình tiếp tục thực thi khi một bộ phận bị khĩa hoặc một hoạt động dài  Chia sẻ tài nguyên: tiết kiệm khơng gian nhớ  Kinh tế: tạo và chuyển ngữ cảnh nhanh hơn tiến trình  Ví dụ: Trong Solaris 2, tạo process chậm hơn 30 lần, chuyển chậm hơn 5 lần so với thread  Trong multiprocessor: cĩ thể thực hiện song song Duy Phan 35 01/2015
Tiểu trình người dùng (User thread) T1 T2 T3 User mode LWP1 LWP2 P2 Kernel P1 mode Kernel Khái niệm tiểu trình được hỗ trợ bởi một thư viện hoạt động trong user mode Duy Phan 36 01/2015
Tiểu trình hạt nhân (Kernel thread) T1 T2 User mode System call Kernel mode HDH Khái niệm tiểu trình được xây dựng bên trong hạt nhân Duy Phan 37 01/2015
Tổng kết  Trạng thái tiến trình  Khối điều khiển tiến trình  Định thời tiến trình  Các tác vụ đối với tiến trình  Sự cộng tác giữa các tiến trình  Giao tiếp giữa các tiến trình  Tiểu trình Duy Phan 38 01/2015
Câu hỏi ơn tập Duy Phan 39 01/2015
Kết thúc chương 3 Duy Phan 01/2015
Chương 4: Định thời CPU - 1 Duy Phan 01/2015
Mục tiêu  Biết được các khái niệm cơ bản về định thời  Biết được các tiêu chuẩn định thời CPU  Hiểu được các giải thuật định thời  Vận dụng các giải thuật định thời để làm bài tập và mơ phỏng Duy Phan 2 Định thời CPU
Nội dung  Các khái niệm cơ bản về định thời  Các bộ định thời  Các tiêu chuẩn định thời CPU  Các giải thuật định thời  First-Come, First-Served (FCFS)  Shortest Job First (SJF)  Shortest Remaining Time First (SRTF)  Round-Robin (RR)  Priority Scheduling Duy Phan 3 Định thời CPU
Khái niệm cơ bản  Trong các hệ thống multitasking  Thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống  Tại mỗi thời điểm, chỉ cĩ một process được thực thi = > cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất -> chiến lược định thời CPU  Định thời CPU  Chọn một process (từ ready queue) thực thi  Với một multithreaded kernel, việc định thời CPU là do OS chọn kernel thread được chiếm CPU Duy Phan 4 Định thời CPU
Các bộ định thời new Long-term Long-term scheduling scheduling Medium-term suspended scheduling Short-term ready ready scheduling running Medium-term suspended scheduling blocked blocked terminated Duy Phan 5 Định thời CPU
Các bộ định thời (tt)  Long-term scheduling  Xác định chương trình nào được chấp nhận nạp vào hệ thống để thực thi  Điều khiển mức độ multiprogramming của hệ thống  Long term scheduler thường cố gắng duy trì xen lẫn CPU-bound và I/O-bound process  Medium-term scheduling  Process nào được đưa vào (swap in), đưa ra khỏi (swap out) bộ nhớ chính  Được thực hiện bởi phần quản lý bộ nhớ và được thảo luận ở phần quản lý bộ nhớ Duy Phan 6 Định thời CPU
Các bộ định thời (tt)  Short-term scheduling  Xác định process nào trong ready queue sẽ được chiếm CPU để thực thi kế tiếp (cịn được gọi là định thời CPU, CPU scheduling)  Short term scheduler cịn được gọi với tên khác là dispatcher  Bộ định thời short-term được gọi mỗi khi cĩ một trong các sự kiện/interrupt sau xảy ra:  Ngắt thời gian (clock interrupt)  Ngắt ngoại vi (I/O interrupt)  Lời gọi hệ thống (operating system call)  Signal Duy Phan 7 Định thời CPU
Dispatcher  Dispatcher sẽ chuyển quyền điều khiển CPU về cho process được chọn bởi bộ định thời ngắn hạn  Bao gồm:  Chuyển ngữ cảnh (sử dụng thơng tin ngữ cảnh trong PCB)  Chuyển chế độ người dùng  Nhảy đến vị trí thích hợp trong chương trình ứng dụng để khởi động lại chương trình (chính là program counter trong PCB)  Cơng việc này gây ra phí tổn  Dispatch latency: thời gian mà dispatcher dừng một process và khởi động một process khác Duy Phan 8 Định thời CPU
Các tiêu chuẩn định thời CPU  Hướng người dùng (User-oriented)  Thời gian đáp ứng (Response time): khoảng thời gian process nhận yêu cầu đến khi yêu cầu đầu tiên được đáp ứng (time-sharing, interactive system) → cực tiểu  Thời gian quay vịng (hồn thành) (Turnaround time): khoảng thời gian từ lúc một process được nạp vào hệ thống đến khi process đĩ kết thúc → cực tiểu  Thời gian chờ (Waiting time): tổng thời gian một process đợi trong ready queue → cực tiểu Duy Phan 9 Định thời CPU
Các tiêu chuẩn định thời CPU (tt)  Hướng hệ thống (System-oriented)  Sử dụng CPU (processor utilization): định thời sao cho CPU càng bận càng tốt → cực đại  Cơng bằng (fairness): tất cả process phải được đối xử như nhau  Thơng lượng (throughput): số process hồn tất cơng việc trong một đơn vị thời gian → cực đại Duy Phan 10 Định thời CPU
Hai yếu tố của giải thuật định thời  Hàm chọn lựa (selection function): dùng để chọn process nào trong ready queue được thực thi (thường dựa trên độ ưu tiên, yêu cầu về tài nguyên, đặc điểm thực thi của process, )  Ví dụ:  w = tổng thời gian đợi trong hệ thống  e = thời gian đã được phục vụ  s = tổng thời gian thực thi của process (bao gồm cả “e”) Duy Phan 11 Định thời CPU
Hai yếu tố của giải thuật định thời (tt)  Chế độ quyết định (decision mode): chọn thời điểm thực hiện hàm chọn lựa để định thời  Cĩ hai chế độ:  Khơng trưng dụng (Non-preemptive)  Khi ở trạng thái running, process sẽ thực thi cho đến khi kết thúc hoặc bị blocked do yêu cầu I/O  Trưng dụng (Preemptive)  Process đang thực thi (trạng thái running) cĩ thể bị ngắt nửa chừng và chuyển về trạng thái ready  Chi phí cao hơn non-preemptive nhưng đánh đổi lại bằng thời gian đáp ứng tốt hơn vì khơng cĩ trường hợp một process độc chiếm CPU quá lâu Duy Phan 12 Định thời CPU
Preemptive và Non-preemptive  Hàm định thời được thực hiện khi  (1)Chuyển từ trạng thái running sang waiting  (2) Chuyển từ trạng thái running sang ready  (3) Chuyển từ trạng thái waiting, new sang ready  (4) Kết thúc thực thi  (1) và (4) khơng cần lựa chọn loại định thời biểu, (2) và (3) cần  Trường hợp 1, 4 được gọi là định thời nonpreemptive  Trường hợp 2, 3 được gọi là định thời preemptive Thực hiện theo cơ chế nào khĩ hơn? Tại sao? Duy Phan 13 Định thời CPU
Các giải thuật định thời  First-Come, First-Served (FCFS)  Shortest Job First (SJF)  Shortest Remaining Time First (SRTF)  Round-Robin (RR)  Priority Scheduling  Highest Response Ratio Next (HRRN)  Multilevel Queue  Multilevel Feedback Queue Duy Phan 14 Định thời CPU
Khảo sát giải thuật định thời  Service time = thời gian process cần CPU trong một chu kỳ CPU-I/O  Process cĩ service time lớn là các CPU-bound process load store add store CPU burst một chu kỳ read from file CPU-I/O Arrival Service Process wait for I/O I/O burst Time Time inc store 1 0 3 CPU burst write to file 2 2 6 wait for I/O I/O burst 3 4 4 load store 4 6 5 CPU burst add store 5 8 2 read from file wait for I/O I/O burst Duy Phan 15 Định thời CPU
First-Come, First-Served (FCFS)  Hàm lựa chọn:  Tiến trình nào yêu cầu CPU trước sẽ được cấp phát CPU trước  Process sẽ thực thi đến khi kết thúc hoặc bị blocked do I/O  Chế độ quyết định: non-preemptive algorithm  Hiện thực: sử dụng hàng đợi FIFO (FIFO queues)  Tiến trình đi vào được thêm vào cuối hàng đợi  Tiến trình được lựa chọn để xử lý được lấy từ đầu của queues 0 5 10 15 20 P1 P2 P3 P4 P5 run add Duy Phan 16 Định thời CPU
First-Come, First-Served (FCFS) (tt)  Giả sử thứ tự vào của  Ví dụ : các tiến trình là  P1, P2, P3 Process Burst Time  Thời gian chờ P1 24  P1 = 0 P2 3  P2 = 24 P3 3  P3 = 27  Thời gian chờ trung Gantt Chart for Schedule bình? P1 P2 P3  (0+24+27)/3 = 17 0 24 27 30 Duy Phan 17 Định thời CPU
First-Come, First-Served (FCFS) (tt)  Giả sử thứ tự vào của  Ví dụ : các tiến trình là  P2, P3, P1 Process Burst Time  Thời gian chờ P1 24  P1 = 6 P2 3  P2 = 0 P3 3  P3 = 3  Thời gian chờ trung Gantt Chart for Schedule bình? P2 P3 P1  (6+0+3)/3 = 3 0 3 6 30 => tốt hơn Duy Phan 18 Định thời CPU
Shortest-Job-First (SJF)  Định thời biểu cơng việc ngắn nhất trước  Khi CPU được tự do, nĩ sẽ cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc ( tiến trình ngắn nhất)  Liên quan đến chiều dài thời gian sử dụng CPU cho lần tiếp theo của mỗi tiến trình  Sử dụng những chiều dài này để lập lịch cho tiến trình với thời gian ngắn nhất Duy Phan 19 Định thời CPU
Shortest-Job-First (SJF) (tt)  Scheme 1: Non-preemptive  Khi CPU được trao cho quá trình nĩ khơng nhường cho đến khi nĩ kết thúc chu kỳ xử lý của nĩ  Scheme 2: Preemptive  Nếu một tiến trình mới được đưa vào danh sách với chiều dài sử dụng CPU cho lần tiếp theo nhỏ hơn thời gian cịn lại của tiến trình đang xử lý, nĩ sẽ dừng hoạt động tiến trình hiện hành → Shortest- Remaining-Time-First (SRTF)  SJF là tối ưu – cho thời gian chờ đợi trung bình tối thiểu với một tập tiến trình cho trước Duy Phan 20 Định thời CPU
Non-Preemptive SJF  Ví dụ: Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 Gantt Chart for Schedule P1 P3 P2 P4 0 7 8 12 16 Average waiting time = (0+6+3+7)/4 = 4 Duy Phan 21 Định thời CPU
Preemptive SJF (SRTF)  Ví dụ 1: Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4  Ví dụ 2: Gantt Chart for Schedule Process Arrival TimeBurst Time P1 0 8 P1 P2 P3 P2 P4 P1 P2 1 4 0 2 4 5 7 11 16 P3 2 9 Average waiting time = P4 3 5 (9+1+0+2)/4 = 3 Duy Phan 22 Định thời CPU
Nhận xét về giải thuật SJF  Cĩ thể xảy ra tình trạng “đĩi” (starvation) đối với các process cĩ CPU-burst lớn khi cĩ nhiều process với CPU-burst nhỏ đến hệ thống.  Cơ chế non-preemptive khơng phù hợp cho hệ thống time sharing (interactive)  Giải thuật SJF ngầm định ra độ ưu tiên theo burst time  Các CPU-bound process cĩ độ ưu tiên thấp hơn so với I/O-bound process, nhưng khi một process khơng thực hiện I/O được thực thi thì nĩ độc chiếm CPU cho đến khi kết thúc Duy Phan 23 Định thời CPU
Nhận xét về giải thuật SJF (tt)  Tương ứng với mỗi process cần cĩ độ dài của CPU burst tiếp theo  Hàm lựa chọn: chọn process cĩ độ dài CPU burst nhỏ nhất  Chứng minh được: SJF tối ưu trong việc giảm thời gian đợi trung bình  Nhược điểm: Cần phải ước lượng thời gian cần CPU tiếp theo của process  Giải pháp cho vấn đề này? Duy Phan 24 Định thời CPU
Nhận xét về giải thuật SJF (tt)  (Thời gian sử dụng CPU chính là độ dài của CPU burst)  Trung bình tất cả các CPU burst đo được trong quá khứ  Nhưng thơng thường những CPU burst càng mới càng phản ánh đúng hành vi của process trong tương lai  Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ (exponential averaging)  τn+1 = a tn + (1 - a) τn , 0 ≤ a ≤ 1 j  τn+1 = a tn + (1- a) a tn-1 + + (1- a) aτn-j + + (1- n+1 a) aτ0  Nếu chọn a = ½ thì cĩ nghĩa là trị đo được tn và trị dự đốn τn được xem quan trọng như nhau. Duy Phan 25 Định thời CPU
Dự đốn thời gian sử dụng CPU Độ dài CPU burst đo được Độ dài CPU burst dự đốn, với a = ½ và 0 = 10 Duy Phan 26 Định thời CPU
Priority Scheduling  Mỗi process sẽ được gán một độ ưu tiên  CPU sẽ được cấp cho process cĩ độ ưu tiên cao nhất  Định thời sử dụng độ ưu tiên cĩ thể:  Preemptive hoặc  Nonpreemptive Duy Phan 27 Định thời CPU
Priority Scheduling (tt)  SJF là một giải thuật định thời sử dụng độ ưu tiên với độ ưu tiên là thời-gian-sử-dụng-CPU-dự- đốn  Gán độ ưu tiên cịn 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  Các yêu cầu bên ngồi ví dụ như: số tiền người dùng trả khi thực thi cơng việc Duy Phan 28 Định thời CPU
Priority Scheduling (tt)  Vấn đề: trì hỗn vơ hạn định – process 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 process sẽ tăng theo thời gian Duy Phan 29 Định thời CPU
Câu hỏi ơn tâp  Cĩ bao nhiêu bộ định thời? Kể tên?  Nêu các tiêu chí định thời?  Nêu ưu điểm và nhược điểm của các giải thuật định thời FCFS, SJF, SRTF, Priority? Duy Phan 30 Định thời CPU
Bài tập  Sử dụng các giải thuật FCFS, SJF, SRTF, Priority để tính các giá trị thời gian đợi, thời gian đáp ứng và thời gian hồn thành trung bình Duy Phan 31 Định thời CPU
Bài tập (tt)  Sử dụng các giải thuật FCFS, SJF, SRTF, Priority để tính các giá trị thời gian đợi, thời gian đáp ứng và thời gian hồn thành trung bình Duy Phan 32 Định thời CPU
Kết thúc chương 4-1 Duy Phan 01/2015
Chương 4: Định thời CPU - 2 Duy Phan 01/2015
Mục tiêu  Biết được các khái niệm cơ bản về định thời  Biết được các tiêu chuẩn định thời CPU  Hiểu được các giải thuật định thời  Vận dụng các giải thuật định thời để làm bài tập và mơ phỏng Duy Phan 2 Định thời CPU
Ơn tập chương 4 - 1  Các khái niệm cơ bản về định thời  Các bộ định thời  Các tiêu chuẩn định thời CPU  Các giải thuật định thời  First-Come, First-Served (FCFS)  Shortest Job First (SJF)  Shortest Remaining Time First (SRTF)  Priority Scheduling Duy Phan 3 Định thời CPU
Bài tập chương 4 - 1  Sử dụng các giải thuật FCFS, SJF, SRTF, Priority để tính các giá trị thời gian đợi, thời gian đáp ứng và thời gian hồn thành trung bình Duy Phan 4 Định thời CPU
Nội dung  Các khái niệm cơ bản về định thời  Các bộ định thời  Các tiêu chuẩn định thời CPU  Các giải thuật định thời  First-Come, First-Served (FCFS)  Shortest Job First (SJF)  Shortest Remaining Time First (SRTF)  Priority Scheduling  Round-Robin (RR)  Highest Response Ratio Next (HRRN)  Multilevel Queue  Multilevel Feedback Queue Duy Phan 5 Định thời CPU
Round Robin (RR)  Mỗi process nhận được một đơn vị nhỏ thời gian CPU (time slice, quantum time), thơng thường từ 10-100 msec để thực thi  Sau khoảng thời gian đĩ, process bị đoạt quyền và trở về cuối hàng đợi ready  Nếu cĩ n process trong hàng đợi ready và quantum time = q thì khơng cĩ process nào phải chờ đợi quá (n -1)q đơn vị thời gian Duy Phan 6 Định thời CPU
Round Robin (RR) (tt)  Hiệu suất:  Nếu q lớn: RR => FCFS  Nếu q nhỏ: q khơng được quá nhỏ bởi vì phải tốn chi phí chuyển ngữ cảnh  Thời gian chờ đợi trung bình của giải thuật RR thường khá lớn nhưng thời gian đáp ứng nhỏ Duy Phan 7 Định thời CPU
Round Robin (RR) (tt)  Ví dụ: Quantum time = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 Gantt Chart for Schedule P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 turn-around time trung bình lớn hơn SJF, nhưng đáp ứng tốt hơn Duy Phan 8 Định thời CPU
Round Robin (RR) (tt)  Quantum time = 1:  Thời gian turn-around trung bình cao hơn so với SJF nhưng cĩ thời gian đp ứng trung bình tốt hơn  Ưu tiên CPU-bound process  I/O-bound  CPU-bound Duy Phan 9 Định thời CPU
Round Robin (RR) (tt)  Quantum time và context switch: context Process time = 10 quantum switch 12 0 10 6 1 6 10 1 9 1 2 3 4 5 6 7 8 9 10 Duy Phan 10 Định thời CPU
Round Robin (RR) (tt)  Thời gian hồn thành trung bình (average turnaround time) khơng chắc sẽ được cải thiện khi quantum lớn Duy Phan 11 Định thời CPU
Round Robin (RR) (tt)  Quantum time và response time Duy Phan 12 Định thời CPU
Quantum time cho Round Robin  Khi thực hiện process switch thì OS sẽ sử dụng CPU chứ khơng phải process của người dùng (OS overhead)  Dừng thực thi, lưu tất cả thơng tin, nạp thơng tin của process sắp thực thi  Performance tùy thuộc vào kích thước của quantum time (cịn gọi là time slice), và hàm phụ thuộc này khơng đơn giản  Time slice ngắn thì đáp ứng nhanh  Vấn đề: cĩ nhiều chuyển ngữ cảnh. Phí tổn sẽ cao.  Time slice dài hơn thì throughput tốt hơn (do giảm phí tổn OS overhead) nhưng thời gian đáp ứng lớn  Nếu time slice quá lớn, RR trở thành FCFS Duy Phan 13 Định thời CPU
Quantum time cho Round Robin  Quantum time và thời gian cho process switch:  Nếu quantum time = 20 ms và thời gian cho process switch = 5 ms, như vậy phí tổn OS overhead chiếm 5/25 = 20%  Nếu quantum = 500 ms, thì phí tổn chỉ cịn 1%  Nhưng nếu cĩ nhiều người sử dụng trên hệ thống và thuộc loại interactive thì sẽ thấy đáp ứng rất chậm  Tùy thuộc vào tập cơng việc mà lựa chọn quantum time  Time slice nên lớn trong tương quan so sánh với thời gian cho process switch  Ví dụ với 4.3 BSD UNIX, time slice là 1 giây Duy Phan 14 Định thời CPU
Quantum time cho Round Robin (tt)  Nếu cĩ n process trong hàng đợi ready, và quantum time là q, như vậy mỗi process sẽ lấy 1/n thời gian CPU theo từng khối cĩ kích thước lớn nhất là q  Sẽ khơng cĩ process nào chờ lâu hơn (n - 1)q đơn vị thời gian  RR sử dụng một giả thiết ngầm là tất cả các process đều cĩ tầm quan trọng ngang nhau  Khơng thể sử dụng RR nếu muốn các process khác nhau cĩ độ ưu tiên khác nhau Duy Phan 15 Định thời CPU
Nhược điểm của Round Robin  Các process dạng CPU-bound vẫn cịn được “ưu tiên”  Ví dụ: Một I/O-bound process sử dụng CPU trong thời gian ngắn hơn quantum time và bị blocked để đợi I/O. Một CPU-bound process chạy hết time slice và lại quay trở về hàng đợi ready queue (ở phía trước các process đã bị blocked) Duy Phan 16 Định thời CPU
Highest Response Ratio Next  Chọn process kế tiếp cĩ giá trị RR (Response ratio) lớn nhất  Các process ngắn được ưu tiên hơn (vì service time nhỏ) time spent waiting expected service time RR expected service time Duy Phan 17 Định thời CPU
Multilevel Queue Scheduling  Hàng đợi ready được chia thành nhiều hàng đợi riêng biệt theo một số tiêu chuẩn như  Đặc điểm và yêu cầu định thời của process  Foreground (interactive) và background process,  Process đượ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 Duy Phan 18 Định thời CPU
Multilevel Queue Scheduling (tt)  Hệ điều hành cần phải định thời cho các hàng đợi.  Fixed priority scheduling: phục vụ từ hàng đợi cĩ độ ưu tiên cao đến thâp. Vấn đề: cĩ thể cĩ starvation.  Time slice: mỗi hàng đợi được nhận một khoảng thời gian chiếm CPU và phân phối cho các process trong hàng đợi khoảng thời gian đĩ. Ví dụ: 80% cho hàng đợi foreground định thời bằng RR và 20% cho hàng đợi background định thời bằng giải thuật FCFS Duy Phan 19 Định thời CPU
Multilevel Queue Scheduling (tt)  Ví dụ phân nhĩm các quá trình Độ ưu tiên cao nhất System Processes Interactive Processes Batch Processes Student Processes Độ ưu tiên thấp nhất Duy Phan 20 Định thời CPU
Multilevel Feedback Queue  Vấn đề của multilevel queue  process 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 process di chuyển một cách thích hợp giữa các hàng đợi khác nhau Duy Phan 21 Định thời CPU
Multilevel Feedback Queue (tt)  Multilevel Feedback Queue  Phân loại processes dựa trên các đặc tính về CPU- burst  Sử dụng decision mode preemptive  Sau một khoảng thời gian nào đĩ, các I/O-bound process và interactive process sẽ ở các hàng đợi cĩ độ ưu tiên cao hơn cịn CPU-bound process sẽ ở các queue cĩ độ ưu tiên thấp hơn  Một process đã 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ế niên hạn, aging) Duy Phan 22 Định thời CPU
Multilevel Feedback Queue (tt)  Ví dụ: Cĩ 3 hàng đợi  Q0 , dùng RR với quantum 8 ms  Q1 , dùng RR với quantum 16 ms  Q2 , dùng FCFS Duy Phan 23 Định thời CPU
Multilevel Feedback Queue (tt)  Định thời dùng multilevel feedback queue địi hỏi phải giải quyết các vấn đề sau  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 process đến hàng đợi cao hơn hoặc thấp hơn?  Khi process yêu cầu được xử lý thì đưa vào hàng đợi nào là hợp lý nhất? Duy Phan 24 Định thời CPU
So sánh các giải thuật  Giải thuật định thời nào là tốt nhất?  Câu trả lời phụ thuộc các yếu tố sau:  Tần xuất tải việc (System workload)  Sự hỗ trợ của phần cứng đối với dispatcher  Sự tương quan về trọng số của các tiêu chuẩn định thời như response time, hiệu suất CPU, throughput,  Phương pháp định lượng so sánh Duy Phan 25 Định thời CPU
Đọc thêm  Policy và Mechanism  Định thời trên hệ thống multiprocessor  Đánh giá giải thuật định thời CPU  Định thời trong một số hệ điều hành thơng dụng (Đọc trong tài liệu tham khảo sách gốc tiếng Anh) Duy Phan 26 Định thời CPU
Tổng kết  Các khái niệm cơ bản về định thời  Các bộ định thời  Các tiêu chuẩn định thời CPU  Hai yếu tố của giải thuật định thời Duy Phan 27 Định thời CPU
Tổng kết (tt)  Các giải thuật định thời  First-Come, First-Served (FCFS)  Shortest Job First (SJF)  Shortest Remaining Time First (SRTF)  Round-Robin (RR)  Priority Scheduling  Highest Response Ratio Next (HRRN)  Multilevel Queue  Multilevel Feedback Queue Duy Phan 28 Định thời CPU
Bài tập Duy Phan 29 Định thời CPU
Kết thúc chương 4 Duy Phan 01/2015
Chương 5: Đồng bộ - 1 Duy Phan 02/2015
Ơn tập chương 4 Duy Phan 2 Đồng bộ
Bài tập chương 4 Duy Phan 3 Đồng bộ
Mục tiêu  Hiểu được vấn đề tranh chấp giữa các tiến trình trong hệ điều hành  Biết được các giải pháp để giải quyết tranh chấp  Hiểu được các vấn đề trong giải quyết tranh chấp  Biết được các yêu cầu của các giải pháp trong việc giải quyết tranh chấp và phân nhĩm các giải pháp Duy Phan 4 Đồng bộ
Nội dung  Giới thiệu về race condition  Giới thiệu các giải pháp tổng quát để giải quyết tranh chấp  Phân tích các chi tiết các vấn đề trong việc giải quyết tranh chấp  Yêu cầu của giải pháp trong việc giải quyết tranh chấp  Phân nhĩm các giải pháp Duy Phan 5 Đồng bộ
Đặt vấn đề  Khảo sát các process/thread thực thi đờng thời và chia sẻ dữ liệu (qua shared memory, file).  Nếu khơng cĩ sự kiểm sốt khi truy cập các dữ liệu chia sẻ thì cĩ thể đưa đến ra trường hợp khơng nhất quán dữ liệu (data inconsistency).  Để duy trì sự nhất quán dữ liệu, hệ thớng cần cĩ cơ chế bảo đảm sự thực thi cĩ trật tự của các process đờng thời. Q p L R Duy Phan 6 Đồng bộ
Bài tốn Producer - Consumer  P khơng được ghi dữ liệu vào buffer đã đầy  C khơng được đọc dữ liệu từ buffer đang trớng  P và C khơng được thao tác trên buffer cùng lúc Giới hạn, khơng giới hạn ??? P Buffer (N) C Duy Phan 7 Đồng bộ
Bounded buffer  Quá trình Producer item nextProduce; while(1){ while(count == BUFFER_SIZE); /*ko lam gi*/ buffer[in] = nextProducer; count++; biến count được chia sẻ in = (in+1)%BUFFER_SIZE; giữa producer vàconsumer  Quá trình Consumer item nextConsumer; while(1){ while(count == 0); /*ko lam gi*/ nextConsumer = buffer[out]; count ; out = (out+1)%BUFFER_SIZE; Duy Phan 8 Đồng bộ
Bounded buffer (tt)  Các lệnh tăng, giảm biến count tương đương trong ngơn ngữ máy là:  Producer (count++)  register1 = count  register1 = register1 + 1  count = register1  Consumer (count )  register2 = count  register2 = register2 - 1  count = register2  Trong đĩ, các register là các thanh ghi của CPU Duy Phan 9 Đồng bộ
Bounded buffer (tt)  Mã máy của các lệnh tăng và giảm biến count cĩ thể bị thực thi xen kẽ  Giả sử count đang bằng 5. Chuỗi thực thi cĩ thể xảy ra  0:producer register1 := count {register1 = 5}  1:producer register1 := register1 + 1 {register1 = 6}  2:consumer register2 := count {register2 = 5}  3:consumer register2 := register2 - 1 {register2 = 4}  4:producer count := register1 {count = 6}  5:consumer count := register2 {count = 4}  Cần phải cĩ giải pháp để các lệnh count++, count phải là đơn nguyên (atomic), nghĩa là thực hiện như mợt lệnh đơn, khơng bị ngắt nửa chừng. Duy Phan 10 Đồng bộ
Bounded buffer (tt)  Race condition: nhiều process truy xuất vàthao tác đờng thời lên dữ liệu chia sẻ( như biến count)  Kết quả cuới cùng của việc truy xuất đờng thời này phụ thuợc thứ tự thực thi của các lệnh thao tác dữ liệu.  Để dữ liệu chia sẻ được nhất quán, cần bảo đảm sao cho tại mỡi thời điểm chỉ có tmợ process được thao tác lên dữ liệu chia sẻ. Do đó, cần cócơ chế đờng bợ hoạt đợng của các process này. Duy Phan 11 Đồng bộ
Vấn đề Critical Section  Giả sử cĩ n process truy xuất đờng thời dữ liệu chia sẻ  Cấu trúc của mỗi process Pi cĩ đoạn code như sau: Do { entry section /* vào critical section */ critical section /* truy xuất dữ liệu chia xẻ */ exit section /* rời critical section */ remainder section /* làm những việc khác */ } While (1)  Trong mỗi process cĩ những đoạn code cĩ chứa các thao tác lên dữ liệu chia sẻ. Đoạn code này được gọi là vùng tranh chấp (critical section, CS). Duy Phan 12 Đồng bộ
Vấn đề Critical Section (tt)  Vấn đềCritical Section: phải bảo đảm sựloạ i trừ tương hỡ(mutual exclusion, mutex), tức làkhi mợt process đang thực thi trong vùng tranh chấp, khơng có process nào khác đờng thời thực thi các lệnh trong vùng tranh chấp. Duy Phan 13 Đồng bộ
Yêu cầu của lời giải cho CS Problem  Lời giải phải thỏa ba tính chất:  (1) Loại trừ tương hỗ (Mutual exclusion): Khi mợt process P đang thực thi trong vùng tranh chấp (CS) của nĩ thì khơng cĩ process Q nào khác đang thực thi trong CS của Q.  (2) Progress: Mợt tiến trình tạm dừng bên ngồi miền găng khơng được ngăn cản các tiến trình khác vào miền găng  (3) Chờ đợi giới hạn (Bounded waiting): Mỗi process chỉ phải chờ để được vào vùng tranh chấp trong mợt khoảng thời gian cĩ hạn định nào đĩ. Khơng xảy ra tình trạng đĩi tài nguyên (starvation).Khơng cĩ giả thiết nào đặt ra cho sựliên hệ về tớc đợ của các tiến trình, cũng như về sớ lượng bợ xử lýtrong hệ thớng Duy Phan 14 Đồng bộ
Phân loại giải pháp  Nhĩm giải pháp Busy Waiting  Sử dụng các biến cờ hiệu  Sử dụng việc kiểm tra luân phiên  Giải pháp của Peterson  Cấm ngắt  Chỉ thị TSL  Nhĩm giải pháp Sleep & Wakeup  Semaphore  Monitor  Message Duy Phan 15 Đồng bộ
Các giải pháp “Busy waiting”  Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng  Khơng địi hỏi sự trợ giúp của Hệ điều hành While (chưa cĩ quyền) do_nothing() ; CS; Từ bỏ quyền sử dụng CS Duy Phan 16 Đồng bộ
Các giải pháp “Sleep & Wake up”  Từ bỏ CPU khi chưa được vào miền găng  Cần Hệ điều hành hỗ trợ if (chưa cĩ quyền) Sleep() ; CS; Wakeup (somebody); Duy Phan 17 Đồng bộ
Tổng kết  Race condition  Các giải pháp tổng quát để giải quyết tranh chấp  Các chi tiết các vấn đề trong việc giải quyết tranh chấp  Yêu cầu của giải pháp trong việc giải quyết tranh chấp  Các nhĩm các giải pháp Duy Phan 18 Đồng bộ
Câu hỏi ơn tập Duy Phan 19 Đồng bộ
Kết thúc chương 5-1 Duy Phan 02/2015
Chương 5: Đồng bộ - 2 Duy Phan 01/2015
Câu hỏi ơn tập 5 - 1 Duy Phan 2 Đồng bộ
Mục tiêu  Hiểu được nhĩm giải pháp Busy waiting bao gồm:  Các giải pháp phần mềm  Các giải pháp phần cứng Duy Phan 3 Đồng bộ
Nội dung  Các giải pháp phần mềm  Sử dụng giải thuật kiểm tra luân phiên  Sử dụng các biến cờ hiệu  Giải pháp của Peterson  Giải pháp Bakery  Các giải pháp phần cứng  Cấp ngắt  Chỉ thị TSL Duy Phan 4 Đồng bộ
Giải thuật 1  Biến chia sẻ  int turn; /* khởi đầu turn = 0 */  nếu turn = i thìPi được phép vào critical section, với i = 0 hay 1  Process Pi do { while (turn != i); critical section turn = j; remainder section } while (1);  Thoả mãn mutual exclusion (1)  Nhưng khơng thoả mãn yêu cầu về progress (2) vàbounded waiting (3) vì tính chất strict alternation của giải thuật Duy Phan 5 Đồng bộ
Giải thuật 1 (tt) Process P0: Process P1: do do while (turn != 0); while (turn != 1); critical section critical section turn := 1; turn := 0; remainder section remainder section while (1); while (1);  Ví dụ: P0 cĩ RS (remainder section) rất lớn cịn P1 cĩ RS nhỏ ??? Duy Phan 6 Đồng bộ
Giải thuật 2  Biến chia sẻ  boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */  Nếu flag[ i ] = true thì Pi “sẵn sàng” vào critical section.  Process Pi do { flag[ i ] = true; /* Pi “sẵn sàng” vào CS */ while ( flag[ j ] ); /* Pi “nhường” Pj */ critical section flag[ i ] = false; remainder section } while (1);  Bảo đảm được mutual exclusion. Chứng minh?  Khơng thỏa mãn progress. Vìsao? Duy Phan 7 Đồng bộ
Giải thuật 3 (Peterson)  Biến chia sẻ  Kết hợp cả giải thuật 1 và 2.  Process Pi, với I = 0 hay 1 do { flag[ i ] = true; /* Process i sẵn sàng */ turn = j; /* Nhường process j */ while (flag[ j ] and turn == j); critical section flag[ i ] = false; remainder section } while (1);  Thoả mãn được cả 3 yêu cầu (chứng minh?)  ⇒ giải quyết bài toán critical section cho 2 process Duy Phan 8 Đồng bộ
Giải thuật Peterson – 2 process Process P Process P0 1 do { do { /* 0 wants in */ /* 1 wants in */ flag[0] = true; flag[1] = true; /* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */ turn = 1; turn = 0; while (flag[1] &&turn == 1); while (flag[0] && turn == 0); critical section critical section /* 0 no longer wants in */ /* 1 no longer wants in */ flag[0] = false; flag[1] = false; remainder section remainder section } while(1); } while(1); Duy Phan 9 Đồng bộ
Giải thuật 3: Tính đúng đắn  Giải thuật 3 thỏa mutual exclusion, progress, và bounded waiting  Mutual exclusion được đảm bảo bởi vì  P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = I cho mỗi Pi (khơng thể xảy ra)  Chứng minh thỏa yêu cầu về progress và bounded waiting  Pi khơng thể vào CS nếu và chỉ nếu bị kẹt tại vịng lặp while() với điều kiện flag[j]=true và turn = j  Nếu Pj khơng muốn vào CS thì flag[j] = false và do đĩ Pi cĩ thể vào CS Duy Phan 10 Đồng bộ
Giải thuật 3: Tính đúng đắn (tt) Nếu Pj đã bật flag[j]=true và đang chờ tại while() thì cĩ chỉ hai trường hợp là turn = i hoặc turn = j Nếu turn = i và Pi vào CS. Nếu turn = j thì Pj vào CS nhưng sẽ bật flag[j]=false khi thốt ra -> cho phếp Pi và CS Nhưng nếu Pj cĩ đủ thời gian bật flag[j]=true thì Pj cũng phải gán turn = i Vì Pi khơng thay đởi trị của biến turn khi đang kẹt trong vòng lặp while(), Pi sẽ chờ để vào CS nhiều nhất là sau mợt lần Pj vào CS (bounded waiting) Duy Phan 11 Đồng bộ
Giải thuật bakery: n process  Trước khi vào CS, process Pi nhận mợt con sớ. Process nào giữ con sớ nhỏ nhất thì được vào CS  Trường hợp Pi và Pj cùng nhận được mợt chỉ sớ:  Nếu i < j thì Pi được vào trước. (Đới xứng)  Khi ra khỏi CS, Pi đặt lại sớ của mình bằng 0  Cơ chế cấp sớ cho các process thường tạo các sớ theo cơ chế tăng dần, ví dụ 1, 2, 3, 3, 3, 3, 4, 5,  Kí hiệu  (a,b) < (c,d) nếu a < c hoặc if a = c và b < d  max(a0, ,ak) là con sớ b sao cho b ≥ ai với mọi i = 0, , k Duy Phan 12 Đồng bộ
Giải thuật bakery: n process (tt) /* shared variable */ boolean choosing[ n ]; /* initially, choosing[ i ] = false */ int num[ n ]; /* initially, num[ i ] = 0 */ do { choosing[ i ] = true; num[ i ] = max(num[0], num[1], , num[n  1]) + 1; choosing[ i ] = false; for (j = 0; j < n; j++) { while (choosing[ j ]); while ((num[ j ] != 0) && (num[ j ], j) < (num[ i ], i)); } critical section num[ i ] = 0; remainder section } while (1); Duy Phan 13 Đồng bộ
Từ software đến hardware  Khuyết điểm của các giải pháp software:  Các process khi yêu cầu được vào vùng tranh chấp đều phải liên tục kiểm tra điều kiện (busy waiting), tớn nhiều thời gian xử lý của CPU  Nếu thời gian xử lý trong vùng tranh chấp lớn, mợt giải pháp hiệu quả nên có cơ chế block các process cần đợi.  Các giải pháp phần cứng:  Cấm ngắt (disable interrupts)  Dùng các lệnh đặc biệt Duy Phan 14 Đồng bộ
Cấm ngắt  Trong hệ thống uniprocessor: Process Pi: mutual exclusion được đảm bảo do {  Nhưng nếu system clock được disable_interrupts() cập nhật do interrupt thì ; critical section  Trong hệ thống multiprocessor: enable_interrupts(); mutual exclusion khơng được remainder section đảm bảo } while (1);  Chỉ cấm ngắt tại CPU thực thi lệnh disable_interrupts  Các CPU khác vẫn cĩ thể truy cập bộ nhớ chia sẻ Duy Phan 15 Đồng bộ
Lệnh TestAndSet  Đọc và ghi một biến trong một thao tác atomic (khơng chia cắt được) boolean TestAndSet( boolean Shared data: *target){ boolean lock = false; boolean rv = *target; Process Pi : *target = true; return rv; do { } while (TestAndSet(&lock)); critical section lock = false; remainder section } while (1); Duy Phan 16 Đồng bộ
Lệnh TestAndSet (tt)  Mutual exclusion được bảo đảm: nếu Pi vào CS, các process Pj khác đều đang busy waiting  Khi Pi ra khỏi CS, quá trình chọn lựa process Pj vào CS kế tiếp là tùy ý⇒ khơng bảo đảm điều kiện bounded waiting. Do đó có thể yxả ra starvation (bị bỏ đói)  Các processor (ví dụPentium ) thơng thường cung cấp một lệnh đơn là Swap(a, b) có tác dụng hốn chuyển nội dung của a và b.  Swap(a, b) cũng cóưu nhược điểm như TestAndSet Duy Phan 17 Đồng bộ
Swap và mutual exclusion Biến chia sẻlock được khởi Biêń chia se ̉ (khởi taọ la ̀ false) tạo giá trịfalse bool lock; bool key; Mỗi process Pi có biến cục bợ key Process Pi Process Pi nào thấy giá trị lock = false thì được vào CS. do { key = true; Process Pi sẽ loại trừ các while (key == true) process Pj khác khi thiết lập lock = true Swap(&lock, &key); critical section void Swap(boolean *a, lock = false; boolean *b) { remainder section boolean temp = *a; } while (1) *a = *b; *b = temp; Khơng thoả mañ bounded waiting } Duy Phan 18 Đồng bộ
Giải thuật dùng TestAndSet thoả mãn 3 yêu cầu  Cấu trúc dữ liệu dùng chung (khởi tạo là false) bool waiting[ n ]; bool lock;  Mutual exclusion: Pi chỉ có thể vào CS nếu và chỉ nếu hoặc waiting[ i ] = false, hoặc key = false  key = false chỉ khi TestAndSet (hay Swap) được thực thi Process đầu tiên thực thi TestAndSet mới có key == false; các process khác đều phải đợi  waiting[ i ] = false chỉ khi process khác rời khỏi CS Chỉ có mợt waiting[ i ] có giá trị false  Progress: chứng minh tương tự như mutual exclusion  Bounded waiting: waiting in the cyclic order Duy Phan 19 Đồng bộ
Giải thuật dùng TestAndSet thoả mãn 3 yêu cầu (tt) do { waiting[ i ] = true; key = true; while (waiting[ i ] && key) key = TestAndSet(lock); waiting[ i ] = false; critical section j = (i + 1) % n; while ( (j != i) && !waiting[ j ] ) j = (j + 1) % n; if (j == i) lock = false; else waiting[ j ] = false; remainder section } while (1) Duy Phan 20 Đồng bộ
Ơn tâp  Các giải pháp phần mềm  Sử dụng giải thuật kiểm tra luân phiên  Sử dụng các biến cờ hiệu  Giải pháp của Peterson  Giải pháp Bakery  Các giải pháp phần cứng  Cấp ngắt  Chỉ thị TSL Duy Phan 21 Đồng bộ
Kết thúc chương 5-2 Duy Phan 01/2015
Chương 5: Đồng bộ - 3 Duy Phan 01/2015
Câu hỏi ơn tập 5 - 2 Duy Phan 2 Đồng bộ
Mục tiêu  Biết được các giải pháp đồng bộ tiến trình theo kiểu “Sleep & Wake up” bao gồm:  Semaphore  Critical Region  Monitor  Áp dụng các giải pháp này vào các bài tốn đồng bộ kinh điển Duy Phan 3 Đồng bộ
Nội dung  Các giải pháp “Sleep & Wake up”  Semaphore  Các bài tốn đồng bộ kinh điển  Critical Region  Monitor Duy Phan 4 Đồng bộ
Các giải pháp “Sleep & Wake up” int busy; // =1 nếu CS đang bị chiếm int blocked; // sớP đang bị khóa do{ if (busy){ blocked = blocked +1; sleep(); } else busy =1; CS; busy = 0; if (blocked !=0){ wakeup (process); blocked = blocked -1; } RS; } while (1); Duy Phan 5 Đồng bộ
Semaphore  Là cơng cụ đờng bợcung cấp bởi OS mà khơng địi hỏi busy waiting  Semaphore S là mợt biến sớnguyên.  Ngồi thao tác khởi đợng biến thì chỉ cĩ thể được truy xuất qua hai tác vục ĩ́ tính đơn nguyên (atomic) và loại trừ(mutual exclusive)  wait(S) hay cịn gọi là P(S): giảm giá trịsemaphore (S=S-1) . Kế đó nếu giá trị này âm thìprocess thực hiện lệnh wait() bịblocked.  signal(S) hay cịn gọi là V(S): tăng giá trịsemaphore (S=S+1) . Kế đó nếu giá trị này khơng dương, mợt process đang blocked bởi mợt lệnh wait() sẽ được hời phục để thực thi.  Tránh busy waiting: khi phải đợi thìprocess sẽ được đặt vào mợt blocked queue, trong đó chứa các process đang chờ đợi cùng mợt sự kiện. Duy Phan 6 Đồng bộ
Semaphore (tt)  P(S) hay wait(S) sử dụng để giành tài nguyên và giảm biến đếm S=S-1  V(S) hay signal(S) sẽ giải phóng tài nguyên và tăng biến đếm S= S+1  Nếu P được thực hiện trên biến đếm <= 0 , tiến trình phải đợi V hay chờ đợi sự giải phóng tài nguyên Duy Phan 7 Đồng bộ
Semaphore (tt) Duy Phan 8 Đồng bộ
Hiện thực semaphore  Định nghĩa semaphore là mợt record typedef struct { int value; struct process *L; /* process queue */ } semaphore;  Giả sử hệ điều hành cung cấp hai tác vụ(system call):  block(): tạm treo process nào thực thi lệnh này  wakeup(P): hời phục quá trình thực thi của process P đang blocked Duy Phan 9 Đồng bộ
Hiện thực semaphore (tt)  Các tác vụ semaphore được hiện thực như sau: void wait(semaphore S) { S.value ; if (S.value < 0) { add this process to S.L; block(); } } void signal(semaphore S) { S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } } Duy Phan 10 Đồng bộ
Hiện thực semaphore (tt)  Khi mợt process phải chờtrên semaphore S, nó sẽ bịblocked và được đặt trong hàng đợi semaphore  Hàng đợi này là danh sách liên kết các PCB  Tác vụsignal () thường sử dụng cơ chếFIFO khi chọn mợt process từ hàng đợi và đưa vào hàng đợi ready  block() và wakeup() thay đởi trạng thái của process  block: chuyển từrunning sang waiting  wakeup: chuyển từwaiting sang ready Duy Phan 11 Đồng bộ
Ví dụ sử dụng semaphore 1  Dùng cho n process Shared data: semaphore mutex; /* initially mutex.value = 1 */  Khởi tạo S.value = 1 Process Pi:  Chỉ duy nhất mợt do { process được vào CS wait(mutex); (mutual exclusion) critical section signal(mutex); remainder section  Để cho phép k process } while (1); vào CS, khởi tạo S.value = k Duy Phan 12 Đồng bộ
Ví dụ sử dụng semaphore 2  Hai process: P1 và P2 Để đờng bợ hoạt đợng theo yêu cầu, P1 phải định  Yêu cầu: lệnh S1 trong nghĩa như sau: P1 cần được thực thi S1; trước lệnh S2 trong P2 signal(synch);  Định nghĩa semaphore synch để đờng bợ Và P2 định nghĩa như sau:  Khởi đợng semaphore: wait(synch); S2; synch.value = 0 Duy Phan 13 Đồng bộ
Ví dụ sử dụng semaphore 3  Xét 2 tiến trình xử lý Để đờng bợ hoạt đợng đoạn chương trình sau: theo yêu cầu, P1 phải định nghĩa như sau:  Tiến trình P1 {A1, A2} A1; Tiến trình P2 {B1, B2} signal(s1);,  Đờng bợ hĩa hoạt đợng wait(s2); của 2 tiến trình sao cho A2; cả A1 và B1 đều hồn Và P2 định nghĩa như sau: tất trước khi A2 và B2 B1 bắt đầu. signal(s2);  Khởi tạo wait(s1); B2; semaphore s1.v = s2.v = 0 Duy Phan 14 Đồng bộ
Nhận xét  Khi S.value ≥ 0: sớprocess có thể thực thi wait(S) mà khơng bị blocked = S.value  Khi S.value < 0: sớprocess đang đợi trên S là S.value  Atomic và mutual exclusion: khơng được xảy ra trường hợp 2 process cùng đang ở trong thân lệnh wait(S) và signal(S) (cùng semaphore S) tại mợt thời điểm (ngay cả với hệ thớng multiprocessor) ⇒ do đó, đoạn mã định nghĩa các lệnh wait(S) và signal(S) cũng chính là vùng tranh chấp Duy Phan 15 Đồng bộ
Nhận xét (tt)  Vùng tranh chấp của các tác vụwait (S) và signal(S) thơng thường rất nhỏ: khoảng 10 lệnh.  Giải pháp cho vùng tranh chấp wait(S) và signal(S)  Uniprocessor: có thể ngdù cơ chế cấm ngắt (disable interrupt). Nhưng phương pháp này khơng làm việc trên hệ thớng multiprocessor.  Multiprocessor: có thể ngdù các giải pháp software (như giải thuật Dekker, Peterson) hoặc giải pháp hardware (TestAndSet, Swap).  Vì CS rất nhỏ nên chi phí cho busy waiting sẽ rất thấp. Duy Phan 16 Đồng bộ
Deadlock và starvation  Deadlock: hai hay nhiều process đang chờ đợi vơ hạn định mợt sự kiện khơng bao giờ xảy ra (vd: sự kiện do mợt trong các process đang đợi tạo ra).  Gọi S và Q là hai biến semaphore được khởi tạo = 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S); signal(S); signal(Q); signal(Q); signal(S); P0 thực thi wait(S), rời P1 thực thi wait(Q), rời P0 thực thi wait(Q) bị blocked, P1 thực thi wait(S) bịblocked.  Starvation (indefinite blocking) Mợt tiến trình có thể khơng bao giờ được lấy ra khỏi hàng đợi mà nó bị treo trong hàng đợi đó. Duy Phan 17 Đồng bộ
Các loại semaphore  Counting semaphore: mợt sớ nguyên có giá trị khơng hạn chế.  Binary semaphore: có trị là0 hay 1. Binary semaphore rất dễ hiện thực.  Có thể hiện thực counting semaphore bằng binary semaphore. Duy Phan 18 Đồng bộ
Các bài tốn đồng bộ kinh điển  Bounded Buffer Problem  Readers and Writers Problem  Dining-Philosophers Problem Duy Phan 19 Đồng bộ
Bài tốn bounder buffer  Dữ liệu chia sẻ:  Semaphore full, empty, mutex;  Khởi tạo:  full = 0; /* sớ buffers đầy */  empty = n; /* sớ buffers trớng */  mutex = 1; n buffers out Duy Phan 20 Đồng bộ
Bài tốn bounder buffer producer consumer do { do { wait(full) nextp = new_item(); wait(mutex); wait(empty); nextc = get_buffer_item(out); wait(mutex); signal(mutex); insert_to_buffer(nextp); signal(empty); signal(mutex); consume_item(nextc); signal(full); } while (1); } while (1); Duy Phan 21 Đồng bộ
Bài tốn “Dining Philosophers”  5 triết gia ngời ăn và 3 2 suy nghĩ 3  Mỡi người cần 2 chiếc 4 2 đũa (chopstick) đểăn 4 0 1  Trên bàn chỉ có 5 đũa  Bài toán này minh họa 0 sự khókhăn trong việc phân phới tài nguyên  Dữ liệu chia sẻ: giữa các process sao  Semaphore chopstick[5]; cho khơng xảy ra  Khởi đầu các biến đều là1 deadlock và starvation Duy Phan 22 Đồng bộ
Bài tốn “Dining Philosophers” (tt) Triết gia thứ i: do { wait(chopstick [ i ]) wait(chopstick [ (i + 1) % 5 ]) eat signal(chopstick [ i ]); signal(chopstick [ (i + 1) % 5 ]); think } while (1); Duy Phan 23 Đồng bộ
Bài tốn “Dining Philosophers” (tt)  Giải pháp trên có thểgây ra deadlock  Khi tất cả triết gia đói bụng cùng lúc và đờng thời cầm chiếc đũa bên tay trái ⇒ deadlock  Mợt sớ giải pháp khác giải quyết được deadlock  Cho phép nhiều nhất 4 triết gia ngời vào cùng mợt lúc  Cho phép triết gia cầm các đũa chỉkhi cảhai chiếc đũa đều sẵn sàng (nghĩa là tác vụ cầm các đũa phải xảy ra trong CS)  Triết gia ngời ở vị trí lẻ cầm đũa bên trái trước, sau đó mới đến đũa bên phải, trong khi đó triết gia ở vị trí chẵn cầm đũa bên phải trước, sau đó mới đến đũa bên trái  Starvation? Duy Phan 24 Đồng bộ
Bài tốn Reader-Writers  Writer khơng được cập nhật dữ liệu khi có mợt Reader đang truy xuất CSDL  Tại mợt thời điểm, chỉ cho phép mợt Writer được sửa đởi nợi dung CSDL R2 R3 R1 W1 W2 Database Duy Phan 25 Đồng bộ
Bài tốn Reader-Writers (tt)  Bợ đọc trước bợghi (first  Reader process reader-writer) wait(mutex);  Dữ liệu chia sẻ readcount++; if (readcount == 1) semaphore mutex = 1; wait(wrt); semaphore wrt = 1; signal(mutex); int readcount = 0; reading is performed  Writer process wait(wrt); wait(mutex); readcount ; if (readcount == 0) writing is performed signal(wrt); signal(mutex); signal(wrt); Duy Phan 26 Đồng bộ
Bài tốn Reader-Writers (tt)  mutex: “bảo vệ” biến readcount  wrt  Bảo đảm mutual exclusion đới với các writer  Được sử dụng bởi reader đầu tiên hoặc cuới cùng vào hay ra khỏi vùng tranh chấp.  Nếu mợt writer đang ở trong CS và có n reader đang đợi thì mợt reader được xếp trong hàng đợi của wrt và n − 1 reader kia trong hàng đợi của mutex  Khi writer thực thi signal(wrt), hệ thớng có thể phục hời thực thi của mợt trong các reader đang đợi hoặc writer đang đợi. Duy Phan 27 Đồng bộ
Các vấn đề với semaphore  Semaphore cung cấp mợt cơng cụ mạnh mẽ để bảo đảm mutual exclusion và phới hợp đờng bợ các process  Tuy nhiên, nếu các tác vụ wait(S) và signal(S) nằm rải rác ở rất nhiều processes ⇒ khó nắm bắt được hiệu ứng của các tác vụ này. Nếu khơng sử dụng đúng ⇒ có thể yxả ra tình trạng deadlock hoặc starvation.  Mợt process bị “die” có thể kéo theo các process khác cùng sử dụng biến semaphore. signal(mutex) wait(mutex) signal(mutex) critical section critical section critical section wait(mutex) wait(mutex) signal(mutex) Duy Phan 28 Đồng bộ
Critical Region (CR)  Là mợt cấu trúc ngơn ngữ cấp cao (high-level language construct, được dịch sang mã máy bởi mợt compiler), thuận tiện hơn cho người lập trình.  Mợt biến chia sẻ v kiểu dữ liệu T, khai báo như sau v: shared T;  Biến chia sẻ v chỉ có thể được truy xuất qua phát biểu sau region v when B do S; /* B là mợt biểu thức Boolean */  Ý nghĩa: trong khi S được thực thi, khơng có quá trình khác có thể truy xuất biến v. Duy Phan 29 Đồng bộ
CR và bài tốn bounded buffer Dữ liệu chia sẻ: Producer region buffer when (count 0){ nextc = pool[out]; out = (out + 1) % n; count ; } Duy Phan 30 Đồng bộ
Monitor  Cũng là mợt cấu trúc ngơn ngữ cấp cao tương tự CR, có chức năng như semaphore nhưng dễ điều khiển hơn  Xuất hiện trong nhiều ngơn ngữ lập trình đờng thời như  Concurrent Pascal, Modula-3, Java,  Có thể hiện thực bằng semaphore Duy Phan 31 Đồng bộ
Monitor (tt)  Là mợt module phần mềm,  Đặc tính của monitor bao gờm  Local variable chỉ có  Mợt hoặc nhiều thủ tục thểtruy xuất bởi các (procedure) thủ tục của monitor  Mợt đoạn code khởi tạo  Process “vào monitor” (initialization code) bằng cách gọi mợt  Các biến dữ liệu cục bợ trong các thủ tục đó (local data variable)  Chỉ có tmợ process có thể vào monitor tại mợt shared data thời điểm ⇒ mutual entry queue exclusion được bảo operations đảm initialization Mơ hình của mợt monitor code đơn giản Duy Phan 32 Đồng bộ
Cấu trúc của monitor monitor monitor-name{ shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } procedure body Pn ( ) { . . . } { initialization code } } Duy Phan 33 Đồng bộ
Condition variable  Nhằm cho phép mợt process đợi “trong monitor”, phải khai báo biến điều kiện (condition variable) condition a, b;  Các biến điều kiện đều cục bợ và chỉ được truy cập bên trong monitor.  Chỉ có thểthao tác lên biến điều kiện bằng hai thủ tục:  a.wait: process gọi tác vụ này sẽ bị“ block trên biến điều kiện” a  process này chỉ có thể ptiế tục thực thi khi cóprocess khác thực hiện tác vụa.signal  a.signal: phục hời quá trình thực thi của process bịblock trên biến điều kiện a.  Nếu có nhiều process: chỉ chọn mợt  Nếu khơng cóprocess : khơng có tác dụng Duy Phan 34 Đồng bộ
Monitor cĩ condition variable shared data entry queue a  Các process có thể đợi ở entry b queue hoặc đợi ở các condition queue (a, b, )  Khi thực hiện lệnh a.wait, process sẽ được chuyển vào condition queue a operations  Lệnh a.signal chuyển mợt process từ condition queue a vào monitor initialization  Khi đó, để bảo đảm mutual code exclusion, process gọi a.signal sẽ bịblocked và được đưa vào urgent queue Duy Phan 35 Đồng bộ
Monitor cĩ condition variable (tt) entry queue monitor waiting area entrance MONITOR local data condition c1 condition variables c1.wait procedure 1 condition cn cn.wait procedure k urgent queue initialization code cx.signal exit Duy Phan 36 Đồng bộ
Monitor và dining philosophers 3 2 4 1 0 monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; Duy Phan 37 Đồng bộ
Dining philosophers (tt) void pickup(int i) { state[ i ] = hungry; test[ i ]; if (state[ i ] != eating) self[ i ].wait(); } void putdown(int i) { state[ i ] = thinking; // test left and right neighbors test((i + 4) % 5); // left neighbor test((i + 1) % 5); // right } Duy Phan 38 Đồng bộ
Dining philosophers (tt) void test (int i) { if ( (state[(i + 4) % 5] != eating) && (state[ i ] == hungry) && (state[(i + 1) % 5] != eating) ) { state[ i ] = eating; self[ i ].signal(); } void init() { for (int i = 0; i < 5; i++) state[ i ] = thinking; } } Duy Phan 39 Đồng bộ
Dining philosophers (tt)  Trước khi ăn, mỡi triết gia phải gọi hàm pickup(), ăn xong rời thì phải gọi hàm putdown() dp.pickup(i); ăn dp.putdown(i);  Giải thuật khơng deadlock nhưng có thể gây starvation. Duy Phan 40 Đồng bộ
Câu hỏi ơn tập  Semaphore là gì? Nêu cách hoạt đợng của semaphore và ứng dụng vào mợt bài tốn đờng bợ?  Monitor là gì? Nêu cách hoạt đợng của monitor và ứng dụng vào mợt bài tốn đờng bợ? Duy Phan 41 Đồng bộ
Bài tập  Sử dụng Duy Phan 42 Đồng bộ
Kết thúc chương 5-3 Duy Phan 01/2015
Chương 6: Deadlocks Duy Phan 04/2015
Câu hỏi ơn tập chương 5  Khi nào thì xảy ra tranh chấp race condition?  Vấn đề Critical Section là gì?  Yêu cầu của lời giải cho CS problem?  Cĩ mấy loại giải pháp? Kể tên? Duy Phan 2 Deadlocks
Mục tiêu  Hiểu được vấn đề bài tốn deadlock và các tính chất của deadlock  Hiển được các phương pháp giải quyết deadlock  Bảo vệ  Tránh  Kiểm tra  Phục hồi Duy Phan 3 Deadlocks
Nội dung  Bài tốn deadlock  Mơ hình hệ thống  Các tính chất của deadlock  Phương pháp giải quyết deadlock Duy Phan 4 Deadlocks
Vấn đề deadlock  Tình huống: Một tập các tiến trình bị block, mỗi tiến trình giữ tài nguyên và đang chờ tài nguyên mà tiến trình khác trong tập đang giữ  Ví dụ 1:  Hệ thống cĩ 2 file trên đĩa  P1 và Pa mỗi tiến trình mở một file và yêu cầu mở file kia  Ví dụ 2:  Bài tốn các triết gia ăn tối  Mỗi người cầm 1 chiếc đũa và chờ chiếc cịn lại Duy Phan 5 Deadlocks
Mơ hình hĩa hệ thống  Các loại tài nguyên, kí hiệu R1, R2, ,Rm, bao gồm:  CPU cycle, khơng gian bộ nhớ, thiết bị I/O, file, semaphore,  Mỗi loại tài nguyên Ri cĩ Wi thực thể  Giả sử tài nguyên tái sử dụng theo chu kỳ  Yêu cầu: tiến trình phải chờ nếu yêu cầu khơng được đáp ứng ngày  Sử dụng: tiến trình sử dụng tài nguyên  Hồn trả: tiến trình hồn trải tài nguyên  Các tác vụ yêu cầu và hồn trả đều là system call. Ví dụ:  Request/ release device  Open / close file  Allocate/ free memory  Wail/ signal Duy Phan 6 Deadlocks
Định nghĩa  Một tiến trình gọi là deadlock nếu nĩ đang đợi một sự kiện mà sẽ khơng bao giờ xảy ra  Thơng thường, cĩ nhiều hơn một tiến trình bị liên quan trong một deadlock  Một tiến trình gọi là trì hỗn vơ hạn định nếu nĩ bị trì hỗn một khoảng thời gian dài lặp đi lặp lại trong khi hệ thống đáp ứng cho những tiến trình khác  Ví dụ: Một tiến trình sẵn sàng để xử lý nhưng nĩ khơng bao giờ nhận được CPU Duy Phan 7 Deadlocks
Điều kiện cần để xảy ra deadlock  Loại trừ hỗ tương: ít nhất một tài nguyên được giữa theo nonsharable mode  Ví dụ: printer, read-only files  Giữ và chờ cấp thêm tài nguyên: Một tiến trình đang giữ ít nhất một tài nguyên và đợi thêm tài nguyên do quá trình khác giữ Duy Phan 8 Deadlocks
Điều kiện cần để xảy ra deadlock (tt)  Khơng trưng dụng: tài nguyên khơng thể bị lấy lại mà chỉ cĩ thể được trả lại từ tiến trình đang giữ tài nguyên đĩ khi nĩ muốn  Chu trình đợi: tồn tại một tập (P0, ,Pn} các quá trình đang đợi sao cho  P0 đợi một tài nguyên mà P1 giữ  P1 đợi một tài nguyên mà P2 giữ   Pn đợi một tài nguyên mà P0 giữ Duy Phan 9 Deadlocks
Đồ thị cấp phát tài nguyên - RAG  Là đồ thị cĩ hướng, với tập đỉnh V và tập cạnh E  Tập đỉnh V gồm 2 loại:  P = {P1, P2, ,Pn} (All process)  R = {R1, R2, ,Rn} (All resource)  Tập cạnh E gồm 2 loại:  Cạnh yêu cầu: Pi -> Rj  Cạnh cấp phát: Pi -> Rj Duy Phan 10 Deadlocks
Đồ thị cấp phát tài nguyên – RAG (tt)  Process i  Loại tài nguyên Rj với 4 thực thể  Pi yêu cầu một thực thể của Rj  Pi đang giữ một thực thể của Rj Duy Phan 11 Deadlocks
Ví dụ RAG Duy Phan 12 Deadlocks
Đồ thị cấp phát tài nguyên với một deadlock Duy Phan 13 Deadlocks
Đồ thị chứa chu trình nhưng khơng deadlock Duy Phan 14 Deadlocks
RAG và deadlock  RAG khơng chứa chu trình -> khơng cĩ deadlock  RAG chứa một (hay nhiều) chu trình  Nếu mỗi loại tài nguyên chỉ cĩ một thực thể -> deadlock  Nếu mỗi loại tài nguyên cĩ nhiều thực thể -> cĩ thể xảy ra deadlock Duy Phan 15 Deadlocks
Các phương pháp giải quyết deadlock  Bảo đảm rằng hệ thống khơng rơi vào tình trạng deadlock bằng cách ngăn hoặc tránh deadlock  Khác biệt  Ngăn deadlock: khơng cho phepr (ít nhất) một trong 4 điều kiện cần cho deadlock  Tránh deadlock: các quá trình cần cung cấp thơng tin về tài nguyên nĩ cần để hệ thống cấp phát tài nguyên một cách thích hợp Duy Phan 16 Deadlocks
Các phương pháp giải quyết deadlock (tt)  Cho phép hệ thống vào trạng thái deadlock, nhưng sau đĩ phát hiện deadlock và phục hồi hệ thống  Bỏ qua mọi vấn để, xem như deadlock khơng bao giờ xảy ra trong hệ thống  Khá nhiều hệ điều hành sử dụng phương pháp này  Deadlock khơng được phát hiện, dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống cĩ thể ngưng hoạt động và phải khởi động lại Duy Phan 17 Deadlocks
Ngăn deadlock  Ngăn deadlock bằng cách ngăn một trong 4 điều kiện cần của deadlock  Mutual exclusion  Đối với tài nguyên khơng chia sẻ (printer): khơng làm được  Đối với tài nguyên chia sẻ (read-only file): khơng cần thiết Duy Phan 18 Deadlocks
Ngăn deadlock (tt)  Hold and wait  Cách 1: Mỗi tiến trình yêu cầu tồn bộ tài nguyên cần thiết một lần. Nếu cĩ đủ tài nguyên thì hệ thống sẽ cấp phát, nếu khơng đủ tài nguyên thì tiến trình phải bị block  Cách 2: Khi yêu cầu tài nguyên, tiến trình khơng được giữ tài nguyên nào. Nếu đang cĩ thì phải trả lại trước khi yêu cầu Duy Phan 19 Deadlocks
Ngăn deadlock (tt)  No preemption: nếu tiến trình A cĩ giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa được cấp phát thì:  Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ A chỉ bắt đầu lại được khi cĩ được các tài nguyên đã bị lấy lại cùng với tài nguyên đang yêu cầu  Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu Nếu tài nguyên được giữ bởi một tiến trình khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A Nếu tài nguyên được giữ bởi tiến trình khơng đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà tiến trình khác yêu cầu Duy Phan 20 Deadlocks
Ngăn deadlock (tt)  Circular wait: gán một thứ tự cho tất cả các tài nguyên trong hệ thống  Tập hợp tài nguyên: R = {R1, R2, ,Rn} Hàm ánh xạ: F: R -> N  Ví dụ: F(tap drive) = 1, F (disk) = 5, F (printer) = 12 F là hàm định nghĩa thứ tự trên tập các loại tài nguyên Duy Phan 21 Deadlocks
Ngăn deadlock (tt)  Circular wait (tt):  Mỗi tiến trình chỉ cĩ thể yêu cầu thực thể của một loại tài nguyên theo thứ tự tăng dần (định nghĩa bởi hàm F) của loại tài nguyên  Ví dụ: Chuỗi yêu cầu thực thể hợp lệ: tap driver -> disk -> printer Duy Phan 22 Deadlocks
Ngăn deadlock (tt)  Circular wait (tt):  Khi một tiến trình yêu cầu một thực thể của loại tài nguyên Rj thì nĩ phải trả lại các tài nguyên Ri với F(Ri)>F(Rj)  Chứng minh giả sử tồn tại một chu trình deadlock F(R4) < F(R1) F(R1) < F(R2) F(R2) < F(R3) F(R3) < F(R4)  Vậy F(R4) < F(R4), mâu thuẫn Duy Phan 23 Deadlocks
Tránh deadlock  Ngăn deadlock sử dụng tài nguyên khơng hiệu quả  Tránh deadlock vẫn đảm bảo hiệu suất sử dụng tài nguyên tối đa đến mức cĩ thể  Yêu cầu mỗi tiến trình khai báo số lượng tài nguyên tối đa cần để thực hiện cơng việc  Giải thuật tránh deadlock sẽ kiểm tra trạng thái cấp phát tài nguyên để đảm bảo hệ thống khơng rơi vào deadlock  Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên cịn lại, số tài nguyên đã được cấp phát và yêu cầu tối đa của các tiến trình Duy Phan 24 Deadlocks
Trạng thái safe và unsafe  Một trạng thái của hệ thống được gọi là an tồn (safe) nếu tồn tại một chuỗi thứ tự an tồn  Một chuỗi quá trình <P1, P2, ,Pn) là một chuỗi an tồn nếu  Với mọi i = 1, ,n yêu cầu tối đa về tài nguyên của Pi cĩ thể được thỏa bởi Tài nguyên mà hệ thống đang cĩ sẵn sàng Cùng với tài nguyên mà tất cả các Pj (j<i) đang giữ  Một trạng thái của hệ thống được gọi là khơng an tồn (unsafe) nếu khơng tồn tại một chuỗi an tồn Duy Phan 25 Deadlocks
Trạng thái safe và unsafe (tt)  Ví dụ: hệ thơng cĩ 12 tap drive và 3 tiến trình P0, P1, P2  Tại thời điểm to Cần tối đa Đang giữ Cần thêm P0 10 5 5 P1 4 2 2 P2 9 2 7 Cịn 3 tap drive sẵn sàng Chuỗi là chuỗi an tồn -> hệ thống là an tồn Duy Phan 26 Deadlocks
Trạng thái safe và unsafe (tt)  Giả sử tại thời điểm t1, P2 yêu cầu và được cấp phát 1 tap drive  Cịn 2 tap drive sẵn sàng Cần tối đa Đang giữ P0 10 5 P1 4 2 P2 9 2 Hệ thống cịn an tồn khơng? Duy Phan 27 Deadlocks
Trạng thái safe/unsafe và deadlock  Nếu hệ thống đang ở trạng thái safe -> khơng deadlock  Nếu hệ thống đang ở trạng thái unsafe -> cĩ thể dẫn đến deadlock  Tránh deadlock bằng cách bảo đảm hệ thống khơng đi đến trạng thái unsafe deadlock unsafe safe Duy Phan 28 Deadlocks
Ơn tập  Khái niệm deadlock  Các tính chất của deadlock  Đồ thị cấp phát tài nguyên  Các phương pháp giải quyết deadlock  Ngăn deadlock  Tránh deadlock Duy Phan 29 Deadlocks
Kết thúc chương 6-1 Duy Phan 04/2015
Chương 6: Deadlocks - 2 Duy Phan 04/2015
Câu hỏi ơn tập chương 6 - 1  Khi nào Duy Phan 2 Deadlocks
Mục tiêu  Hiểu được thêm các phương pháp giải quyết deadlock  Phát hiện  Phục hồi  Hiểu và hiện thực được giải thuật Banker Duy Phan 3 Deadlocks
Nội dung  Giải thuật đồ thị cấp phát tài nguyên  Giải thuật banker  Phát hiện deadlock  Phục hồi deadlock Duy Phan 4 Deadlocks
Giải thuật đồ thị cấp phát tài nguyên Duy Phan 5 Deadlocks
Giải thuật Banker  Mỗi loại tài nguyên cĩ nhiều thực thể  Bắt chước nghiệp vụ ngân hàng  Mỗi tiến trình phải khai báo số lượng thực thể tối đa của mỗi loại tài nguyên mà nĩ cần  Khi tiến trình yêu cầu tài nguyên thì cĩ thể phải đợi  Khi tiến trình đã cĩ được đầy đủ tài nguyên thì phải hồn trả trong một khoảng thời gian hữu hạn nào đĩ Duy Phan 6 Deadlocks
Cấu trúc dữ liệu cho giải thuật Banker n: số tiến trình; m: số loại tài nguyên  Available: vector độ dài m  Available[j] = k  loại tài nguyên Rj cĩ k instance sẵn sàng  Max: ma trận n x m  Max[i, j] = k  tiến trình Pi yêu cầu tối đa k instance của loại tài nguyên Rj  Allocation: vector độ dài m  Allocation[i, j] = k  Pi đã được cấp phát k instance của Rj  Need: vector độ dài m  Need[i, j] = k  Pi cần thêm k instance của Rj  => Need[i, j] = Max[i, j] - Allocation[i, j] Ký hiệu Y X Y[i] X[i], ví dụ (0, 3, 2, 1) (1, 7, 3, 2) Duy Phan 7 Deadlocks
Giải thuật an tồn 1. Gọi Work và Finish là hai vector độ dài là m và n. Khởi tạo Work = Available Finish[i] = false, i = 0, 1, , n-1 2. Tìm i thỏa (a) Finish[i] = false (b) Needi Work Nếu khơng tồn tại i như vậy, đến bước 4. 3. Work = Work + Allocationi Finish[i] = true quay về bước 2 4. Nếu Finish[i] = true, i = 1, , n, thì hệ thống đang ở trạng thái safe Duy Phan 8 Deadlocks
Giải thuật yêu cầu tài nguyên cho tiến trình Pi Requesti là request vector của process Pi . Requesti [j] = k  Pi cần k instance của tài nguyên Rj . 1. Nếu Requesti ≤ Needi thì đến bước 2. Nếu khơng, báo lỗi vì tiến trình đã vượt yêu cầu tối đa. 2. Nếu Requesti ≤ Available thì qua bước 3. Nếu khơng, Pi phải chờ vì tài nguyên khơng còn đủ để cấp phát. 3. Giả định cấp phát tài nguyên đáp ứng yêu cầu của Pi bằng cách cập nhật trạng thái hệ thống như sau: Available = Available – Requesti Allocationi = Allocationi + Requesti Needi = Needi – Requesti Nếu trạng thái là safe thì tài nguyên được cấp thực sự cho Pi . Nếu trạng thái là unsafe thì Pi phải đợi, và phục hồi trạng thái. Duy Phan 9 Deadlocks
Giải thuật Banker - Ví dụ  5 tiến trình P0, ,P4  3 loại tài nguyên:  A (10 thực thể), B (5 thực thể), C (7 thực thể)  Sơ đồ cấp phát trong hệ thống tại thời điểm T0 Duy Phan 10 Deadlocks
Giải thuật Banker - Ví dụ (tt)  Chuỗi an tồn Duy Phan 11 Deadlocks
Ví dụ: P1 yêu cầu (1, 0, 2)  Kiểm tra Request 1 ≤ Available:  (1, 0, 2) ≤ (3, 3, 2) => Đúng  Trạng thái mới là safe (chuỗi an tồn là vậy cĩ thể cấp phát tài nguyên cho P1 Duy Phan 12 Deadlocks
Ví dụ: P4 yêu cầu (3, 3, 0)  Kiểm tra Request 4 ≤ Available:  (3, 3, 0) ≤ (3, 3, 2) => Đúng Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 0 0 2 P1 3 0 2 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 3 3 2 1 0 1  Trạng thái mới là unsafe vậy khơng thể cấp phát tài nguyên cho P4 Duy Phan 13 Deadlocks
Ví dụ: P0 yêu cầu (0, 2, 0)  Kiểm tra Request 4 ≤ Available:  (0, 2, 0) ≤ (3, 3, 2) => Đúng Allocation Need Available A B C A B C A B C P0 0 3 0 7 2 3 3 1 2 P1 3 0 2 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1  Trạng thái mới là safe, chuỗi an tồn vậy cĩ thể cấp phát tài nguyên cho P4 Duy Phan 14 Deadlocks
Phát hiện deadlock  Chấp nhận xảy ra deadlock trong hệ thống  Giải thuật phát hiện deadlock  Cơ chế phục hồi Duy Phan 15 Deadlocks
Mỗi loại tài nguyên chỉ cĩ một thực thể  Sử dụng wait-for graph  Các Node là các tiến trình  Pi -> Pj nếu Pi chờ tài nguyên từ Pj  Mỗi giải thuật kiểm tra cĩ tồn tại chu trình trong wait- for graph hay khơng sẽ được gọi định kỳ. Nếu cĩ chu trình thì tồn tại deadlock  Giải thuật phát hiện chu trình cĩ thời gian chạy là O(n2), với n là số đỉnh của graph Duy Phan 16 Deadlocks
Sơ đồ cấp phát tài nguyên và sơ đồ wait-for Resource-Allocation Graph Corresponding wait-for graph Duy Phan 17 Deadlocks
Mỗi loại tài nguyên cĩ nhiều thực thể  Available: vector đợ dài m chỉ số instance sẵn sàng của mỗi loại tài nguyên  Allocation: ma trận n × m định nghĩa số instance của mỗi loại tài nguyên đã cấp phát cho mỗi process  Request: ma trận n × m chỉ định yêu cầu hiện tại của mỗi tiến trình.  Request [i,j] = k ⇔ Pi đang yêu cầu thêm k instance của Rj Duy Phan 18 Deadlocks
Giải thuật phát hiện deadlock 1. Gọi Work và Finish là vector kích thước m và n. Khởi tạo: a. Work = Available b. For i = 1, 2, , n, nếu Allocationi 0 thì Finish[ i ] := false còn khơng thì Finish[ i ] := true 2. Tìm i thỏa mãn: a. Finish[ i ] = false b. Requesti Work Nếu khơng tồn tại i như vậy, đến bước 4. Duy Phan 19 Deadlocks