Hệ Điều Hành - Slide PDF
Document Details
Vũ Đức Thịnh, Phạm Tuấn Khiêm
Tags
Summary
Đây là giáo trình về Hệ Điều Hành, bao gồm các chương như Tổng quan, Cấu trúc hệ điều hành, Quản lý tiến trình, Định thời CPU, v.v. Giáo trình cung cấp cái nhìn tổng quan về các khái niệm quan trọng trong Hệ Điều Hành.
Full Transcript
HỆ ĐIỀU HÀNH Hệ điều hành - GV.Vũ Đức Thịnh 1 Nội dung Chương 1: Tổng quan về hệ điều hành Chương 2: Cấu trúc hệ điều hành Chương 3: Quản lý tiến trình (Processes) Chương 4: Định thời CPU Chương 5: Đồng bộ hóa tiến trình Chương 6: Tắc nghẽn (Deadlocks) Chương 7: Quản lý bộ nhớ Chương 8: Bộ...
HỆ ĐIỀU HÀNH Hệ điều hành - GV.Vũ Đức Thịnh 1 Nội dung Chương 1: Tổng quan về hệ điều hành Chương 2: Cấu trúc hệ điều hành Chương 3: Quản lý tiến trình (Processes) Chương 4: Định thời CPU Chương 5: Đồng bộ hóa tiến trình Chương 6: Tắc nghẽn (Deadlocks) Chương 7: Quản lý bộ nhớ Chương 8: Bộ nhớ ảo Hệ điều hành - GV.Vũ Đức Thịnh 2 Chương 1 TỔNG QUAN Hệ điều hành - GV. Vũ Đức Thịnh 3 NỘI DUNG Vai trò của hệ điều hành Tổ chức hệ thống máy tính Kiến trúc hệ thống máy tính Cấu trúc hệ điều hành Hoạt động của hệ điều hành Quản lý tiến trình Quản lý bộ nhớ Quản lý lưu trữ Bảo vệ và bảo mật Cấu trúc dữ liệu nhân HĐH Các môi trường tính toán Các hệ điều hành mã nguồn mở Hệ điều hành - GV. Vũ Đức Thịnh 4 MỤC TIÊU Mô tả được cấu trúc cơ bản của hệ thống máy tính Cung cấp bao quát về các thành phần chính của hệ điều hành Đưa ra cái nhìn tổng quan về nhiều loại môi trường tính toán Khám phá nhiều hệ điều hành mã nguồn mở Hệ điều hành - GV. Vũ Đức Thịnh 5 Hệ điều hành là gì? Một chương trình hoạt động trung gian giữa người sử dụng và phần cứng máy tính Mục tiêu của hệ điều hành: ◦ Thực thi chương trình và giúp người dùng giải quyết vấn đề một cách dễ dàng hơn ◦ Giúp hệ thống máy tính hoạt động thuận tiện hơn ◦ Sử dụng phần cứng máy tính một cách hiệu quả Hệ điều hành - GV.Vũ Đức Thịnh 6 Cấu trúc hệ thống máy tính Hệ thống máy tính được chia làm 4 thành phần: ◦ Phần cứng – cung cấp tài nguyên tính toán CPU, bộ nhớ, các thiết bị nhập xuất ◦ Hệ điều hành Điều khiển và phối hợp việc sử dụng phần cứng giữa các chương trình khác nhau và người sử dụng ◦ Chương trình ứng dụng – xác định cách thức mà tài nguyên hệ thống được sử dụng để giải quyết các vấn đề của người dùng Chương trình xử lý văn bản, trình biên dịch, trình duyệt web, hệ cơ sở dữ liệu, trò chơi điện tử,… ◦ Người sử dụng Hệ điều hành - GV.Vũ Đức Thịnh 7 Bốn thành phần của hệ thống máy tính Hệ điều hành - GV.Vũ Đức Thịnh 8 Vai trò của hệ điều hành Phụ thuộc vào quan điểm (người dùng, hệ thống) Người dùng muốn tiện lợi, dễ sử dụng và làm việc hiệu quả ◦ Không quan tâm đến tài nguyên sử dụng Đối với các máy tính như mainframe hoặc minicomputer, phải được thiết kế sao cho thỏa mãn tất cả người dùng truy cập Với người sử dụng hệ thống workstations – servers, HĐH được thiết kế để giải quyết hợp lý việc sử dụng tài nguyên giữa máy trạm và máy chủ Đối với các máy tính xách tay, tài nguyên hệ thống ít, HĐH được thiết kế nhằm tối ưu khả năng sử dụng và thời gian hoạt động của Pin Một số máy tính có ít hoặc không có giao diện người dùng, chẳng hạn như máy tính nhúng trong các thiết bị gia dụng và xe ô tô, HĐH được thiết kế để chạy không có sự can thiệp của người sử dụng Hệ điều hành - GV.Vũ Đức Thịnh 9 Định nghĩa hệ điều hành HĐH là bộ cấp phát tài nguyên ◦ Quản lý tất cả tài nguyên ◦ Quyết định giữa các yêu cầu khác nhau về việc sử dụng tài nguyên hiệu quả và công bằng HĐH là 1 chương trình điều khiển ◦ Điều khiển việc thực thi chương trình để ngăn chặn lỗi và việc sử dụng máy tính không đúng cách Hệ điều hành - GV.Phạm Tuấn Khiêm 10 Định nghĩa hệ điều hành Không có 1 định nghĩa chung nhất về HĐH “Mọi thứ mà người bán hàng gửi tới khi bạn đặt ‘một HĐH’ ” “Một chương trình chạy mọi lúc trên máy tính” là 1 khái niệm tốt về HĐH , còn được gọi là hạt nhân (kernel). Mọi thứ bao gồm cả 2 ◦ Chương trình hệ thống ◦ Chương trình ứng dụng Hệ điều hành - GV.Phạm Tuấn Khiêm 11 Khởi động máy tính Chương trình tự khởi động (bootstrap program) được gọi khi bật máy hoặc khởi động lại ◦ Loại chương trình được lưu trữ trong ROM hoặc EPROM, được biết đến với tên phần dẻo (firmware) ◦ Khởi tạo tất cả các thành phần của hệ thống ◦ Gọi nhân hệ điều hành và bắt đầu khởi động Hệ điều hành - GV.Phạm Tuấn Khiêm 12 Tổ chức hệ thống máy tính Hoạt động của hệ thống máy tính ◦ Một hoặc nhiều CPU, các trình điều khiển thiết bị kết nối thông qua đường truyền để truy cập bộ nhớ chia sẻ ◦ Việc thực thi đồng thời của CPU và các thiết bị cạnh tranh nhau trong chu trình bộ nhớ Hệ điều hành - GV.Phạm Tuấn Khiêm 13 Hoạt động của hệ thống máy tính Thiết bị nhập/xuất và CPU có thể thực thi đồng thời Mỗi bộ điều khiển thiết bị phụ trách một loại thiết bị cụ thể Mỗi bộ điều khiển thiết bị có một bộ nhớ đệm cục bộ CPU di chuyển dữ liệu từ/đến bộ nhớ chính đến/từ bộ nhớ đệm cục bộ Nhập/xuất từ thiết bị đến bộ nhớ đệm cục bộ của bộ điều khiển Bộ điều khiển thiết bị thông báo cho CPU biết nó đã kết thúc hoạt động của mình bằng cách gây ra một ngắt (interrupt) Hệ điều hành - GV.Phạm Tuấn Khiêm 14 Chức năng của ngắt Ngắt chuyển điều khiển tới chương trình phục vụ ngắt thông qua véc tơ ngắt (interrupt vector), nơi chứa địa chỉ của tất cả chương trình phục vụ ngắt Kiến trúc ngắt phải lưu địa chỉ của lệnh gián đoạn Một bẫy lỗi (trap) hoặc một ngoại lệ (exception) là một loại ngắt mềm được tạo ra bởi một lỗi hoặc một yêu cầu của người sử dụng Hệ điều hành hoạt động như một chương trình điều khiển ngắt (interrupt driven) Hệ điều hành - GV.Phạm Tuấn Khiêm 15 Xử lý ngắt Hệ điều hành duy trì trạng thái của CPU bằng cách lưu trữ nội dung các thanh ghi và bộ đếm chương trình Xác định loại ngắt nào đã xuất hiện và có những hành động xử lý tương ứng Xác định loại ngắt đã xảy ra: ◦ Polling ◦ Vectored interrupt system Hệ điều hành - GV.Phạm Tuấn Khiêm 16 Định nghĩa và ký hiệu của hệ thống lưu trữ Đơn vị cơ bản của bộ nhớ máy tính là bit. Một bit chứa một trong hai giá trị là 0 và 1. Tất cả các lưu trữ khác trong một máy tính dựa trên tập hợp của các bit. Máy tính có thể biểu diễn: số, chữ cái, hình ảnh, phim, âm thanh, tài liệu và các chương trình. Một byte là 8 bit, và hầu hết các máy tính đó là các đơn vị nhỏ nhất của lưu trữ. Một thuật ngữ ít phổ biến hơn là word, là đơn vị của dữ liệu. Một word được tạo thành từ một hoặc nhiều byte. Các đơn vị đo khác ◦ 1KB (Kilobyte)=1024 bytes ◦ 1MB (Megabyte)=10242 bytes ◦ 1GB (Gigabyte)=10243 bytes ◦ 1TB (Terabyte)=10244 bytes ◦ 1PB (Petabyte)=10245 bytes Hệ điều hành - GV.Phạm Tuấn Khiêm 19 Cấu trúc hệ thống nhớ Bộ nhớ chính (Main memory) ◦ Truy cập ngẫu nhiên ◦ Khả biến Bộ nhớ thứ cấp (Secondary memory) – mở rộng của bộ nhớ chính với tính bất biến Đĩa cứng (Hard disks) ◦ Bề mặt đĩa được phân chia thành các track, mỗi track chứa nhiều sector ◦ Bộ điều khiển đĩa xác định sự tương tác giữa thiết bị và máy tính Đĩa Solid-state – nhanh hơn đĩa cứng, bất biến ◦ Công nghệ khác nhau ◦ Phổ biến Hệ điều hành - GV.Phạm Tuấn Khiêm 20 Phân cấp trong hệ thống nhớ Hệ thống nhớ được tổ chức theo cơ chế phân cấp theo: ◦ Tốc độ ◦ Giá thành ◦ Tính không ổn định Caching – sao chép thông tin vào hệ thống lưu trữ nhanh hơn Device Driver – trình quản lý cho mỗi thiết bị để quản lý việc Nhập/Xuất ◦ Cung cấp giao tiếp thống nhất giữa trình điều khiển và Kernel Hệ điều hành - GV.Phạm Tuấn Khiêm 21 Sơ đồ phân cấp trong hệ thống nhớ Hệ điều hành - GV.Phạm Tuấn Khiêm 22 Caching Kỹ thuật quan trọng, được sử dụng ở nhiều mức khác nhau trong máy tính (phần cứng, hệ điều hành, phần mềm) Sao chép thông tin tới thiết bị nhớ nhanh hơn để tăng tốc độ xử lý Dung lượng cache có hạn nên cần có sự quản lý cache (cache management) để tăng hiệu năng Hệ điều hành - GV.Phạm Tuấn Khiêm 23 Cấu trúc DMA (Direct Memory Access) Được sử dụng cho những thiết bị Nhập/Xuất có tốc độ truyền thông tin cao Trình điều khiển thiết bị chuyển khối dữ liệu từ bộ đệm lưu trữ trực tiếp vào bộ nhớ chính mà không cần sự can thiệp của CPU Sử dụng ngắt trên block (khối dữ liệu) thay vì trên byte Hệ điều hành - GV.Phạm Tuấn Khiêm 24 Kiến trúc hệ thống máy tính Hầu hết các hệ thống hiện nay sử dụng là hệ thống đơn xử lý ◦ Chạy một tập lệnh hạn chế Hệ thống đa xử lý đang phát triển mạnh và đóng vai trò quan trọng ◦ Còn được biết đến với các tên như parallel systems, tightly-coupled systems ◦ Bao gồm 3 lợi ích: Tăng thông lượng Lợi ích kinh tế Tăng độ tin cậy ◦ Có 2 loại: Đa xử lý không đối xứng (Asymmetric Multiprocessing) – mỗi vi xử lý thực hiện 1 tác vụ cụ thể Đa xử lý đối xứng (Symmetric Multiprocessing) – mỗi vi xử lý thực hiện tất cả các tác vụ Hệ điều hành - GV.Phạm Tuấn Khiêm 26 Kiến trúc đa xử lý đối xứng Hệ điều hành - GV.Phạm Tuấn Khiêm 27 Một thiết kế Dual-Core Multi-chip và multicore Hệ điều hành - GV.Phạm Tuấn Khiêm 28 Hệ thống gom cụm (Clustered systems) Giống như hệ thống đa xử lý nhưng nhiều hệ thống làm việc cùng với nhau ◦ Sử dụng bộ nhớ chung thông qua mạng lưu trữ (SAN - storage-area network) ◦ Cung cấp dịch vụ giúp hệ thống vượt qua lỗi Gom cụm bất đối xứng có 1 máy ở chế độ tin cậy cao Gom cụm đối xứng có nhiều máy chạy ứng dụng, theo dõi nhau ◦ Một số cụm dùng cho việc tính toán hiệu năng cao Các ứng dụng phải được viết để sử dụng song song ◦ Một số sử dụng quản lý khóa phân tán (DLM) để tránh các hoạt động trái ngược nhau Hệ điều hành - GV.Phạm Tuấn Khiêm 29 Hệ thống gom cụm Hệ điều hành - GV.Phạm Tuấn Khiêm 30 Cấu trúc hệ điều hành Đa chương (Multiprogramming) (hệ thống bó – Batch system) ◦ HĐH đa chương tổ chức công việc (mã và dữ liệu) sao cho CPU luôn luôn có 1 công việc để thực hiện ◦ Tập con của các công việc được lưu trữ trong bộ nhớ ◦ Một công việc được chọn và chạy thông qua lập lịch công việc (job scheduling) ◦ Khi một công việc phải chờ (chẳng hạn chờ Nhập/Xuất) thì HĐH sẽ chọn 1 công việc khác để thực hiện Chia sẻ thời gian (Timesharing) (Đa nhiệm – multitasking): mở rộng của đa chương, cho phép người dùng có thể tương tác với mỗi chương trình trong khi nó đang chạy ◦ Thời gian đáp ứng < 1 giây ◦ Mỗi người dùng có ít nhất một chương trình thực thi trong bộ nhớ process ◦ Nếu nhiều công việc sẵn sang chạy cùng lúc CPU scheduling ◦ Nếu nhiều tiến trình không phù hợp trong bộ nhớ, cơ chế swapping sẽ di chuyển chúng vào trong hoặc ra ngoài để chạy ◦ Virtual memory (Bộ nhớ ảo) cho phép thực thi các tiến trình không hoàn thành trong bộ nhớ Hệ điều hành - GV.Phạm Tuấn Khiêm 31 Sơ đồ bộ nhớ trong hệ thống đa chương Hệ điều hành - GV.Phạm Tuấn Khiêm 32 Hoạt động của hệ điều hành Điều khiển ngắt (Interrupt driven) (phần cứng và phần mềm) ◦ Ngắt cứng bằng 1 thiết bị cụ thể ◦ Ngắt mềm (ngoại lệ hoặc bẫy lỗi): Lỗi phần mềm (ví dụ chia cho 0) Yêu cầu dịch vụ HĐH Vấn đề khác như: vòng lặp vô hạn Hệ điều hành - GV.Phạm Tuấn Khiêm 33 Hoạt động của hệ điều hành Chế độ Dual-mode cho phép HĐH tự bảo vệ nó và các thành phần khác ◦ User mode và Kernel mode ◦ Chế độ bit được thực thi bằng phần cứng: Cung cấp khả năng phân biệt khi hệ thống đang chạy User mode hay Kernel mode Một số chương trình được thiết kế với đặc quyền chỉ thực thi trong kernel mode Lời gọi hệ thống (System call) làm thay đổi sang kernel mode và trở lại user mode khi thực hiện xong Hệ điều hành - GV.Phạm Tuấn Khiêm 34 Chuyển đổi từ User mode sang Kernel mode Hệ điều hành - GV.Phạm Tuấn Khiêm 35 Quản lý tiến trình Tiến trình là 1 chương trình đang thực thi. Chương trình là một thực thể thụ động, tiến trình là một thực thể hoạt động Tiến trình cần tài nguyên để thực hiện nhiệm vụ của nó ◦ CPU, bộ nhớ, I/O, tập tin ◦ Dữ liệu khởi tạo HĐH sẽ nhận lại tài nguyên khi tiến trình kết thúc Đơn tiểu trình có 1 bộ đếm chương trình giúp xác định vị trí của lệnh kế tiếp để thực thi ◦ Tiến trình thực hiện các lệnh tuần tự, mỗi lệnh tại một thời điểm, cho đến khi hoàn thành Đa tiểu trình có 1 bộ đếm chương trình trên mỗi tiểu trình Hệ thống có nhiều tiến trình, 1 số tiến trình người dung, 1 số tiến trình HĐH đang chạy trên 1 hoặc nhiều CPU ◦ Kết hợp bằng cách ghép các CPU của các tiến trình/các tiểu trình Hệ điều hành - GV.Phạm Tuấn Khiêm 36 Các hoạt động quản lý tiến trình Tạo và xóa tiến trình người dung và tiến trình hệ thống Tạm ngưng và khôi phục các tiến trình Cung cấp cơ chế giúp đồng bộ hóa tiến trình Cung cấp cơ chế giúp liên lạc giữa các tiến trình Cung cấp cơ chế giúp quản lý tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 37 Quản lý bộ nhớ Để thực thi một chương trình, tất cả (hoặc một phần) của chương trình phải có trong bộ nhớ Tất cả (hoặc một phần) dữ liệu cần cho chương trình phải nằm trong bộ nhớ Quản lý bộ nhớ xác định những gì nằm trong bộ nhớ và khi nào dùng ◦ Tối ưu hóa CPU và máy tính đáp ứng cho người dùng Các hoạt động quản lý bộ nhớ: ◦ Theo dõi các phần bộ nhớ đang sử dụng và bởi đối tượng nào ◦ Quyết định tiến trình nào (hoặc bộ phận của chúng) và dữ liệu di chuyển vào và ra khỏi bộ nhớ ◦ Cấp phát và thu hồi không gian bộ nhớ khi cần thiết Hệ điều hành - GV.Phạm Tuấn Khiêm 38 Quản lý lưu trữ HĐH cung cấp cái nhìn logic, nhất quán về các thông tin lưu trữ ◦ Trừu tượng hóa những thuộc tính vật lý thành đơn vị lưu trữ logic – tập tin (file) ◦ Mỗi phương tiện được điều khiển bằng thiết bị Tính chất khác nhau bao gồm tốc độ truy cập, công suất, tốc độ truyền dữ liệu, phương pháp truy cập (tuần tự hoặc ngẫu nhiên) Quản lý tập tin hệ thống ◦ Các tập tin được tổ chức vào trong thư mục ◦ Kiểm soát truy cập vào các hệ thống để xác định người nào có thể truy cập những gì ◦ Các hoạt động của HĐH bao gồm: Tạo và xóa tập tin, thư mục Thao tác tập tin và thư mục Ánh xạ tập tin vào bộ nhớ thứ cấp Sao lưu tập tin vào các phương tiện lưu trữ bất biến Hệ điều hành - GV.Phạm Tuấn Khiêm 39 Quản lý bộ nhớ phụ Hạn chế của bộ nhớ chính bộ nhớ phụ Bộ nhớ phụ: ◦ lưu trữ mọi thứ ◦ Bộ nhớ ảo Tác vụ cung cấp bởi hệ điều hành ◦ Quản lý không gian còn trống trên đĩa ◦ Phân phối không gian lưu trữ, định vị lưu trữ ◦ Định thời truy cập cho đĩa. Hệ điều hành - GV.Phạm Tuấn Khiêm 40 Bảo vệ và bảo mật Bảo vệ - Bất kỳ cơ chế điều khiển quyền truy cập của các tiến trình hoặc người sử dụng tới tài nguyên đều được xác định bởi hệ điều hành Bảo mật - Bảo vệ hệ thống chống lại các cuộc tấn công nội bộ và bên ngoài ◦ Phạm vi rộng lớn, bao gồm: tấn công từ chối dịch vụ, virus máy tính, sâu máy tính, trộm cắp thông tin, trộm cắp dịch vụ Hệ thống phải phân biệt người sử dụng để xác định ai làm việc gì ◦ danh tính người dùng (user ID, ID bảo mật) bao gồm tên và mật khẩu ◦ User ID được kết hợp với tất cả các tập tin, tiến trình được sử dụng để xác định quyền truy cập ◦ định danh nhóm (group ID) cho phép nhóm người dùng được xác định và được kiểm soát, gắn với mỗi tiến trình, tập tin ◦ Cơ chế đặc quyền cho phép người dung có thể thay đổi ID để có nhiều quyền hệ thống Hệ điều hành - GV.Phạm Tuấn Khiêm 41 Cấu trúc dữ liệu nhân hệ điều hành Nhiều cấu trúc giống với cấu trúc dữ liệu lập trình Danh sách liên kết đơn Danh sách liên kết đôi Danh sách liên kết vòng Hệ điều hành - GV.Phạm Tuấn Khiêm 42 Cấu trúc dữ liệu nhân hệ điều hành Cây nhị phân tìm kiếm ◦ Nút trái 0 : có lỗi Hệ điều hành - GV.Phạm Tuấn Khiêm 27 Chương trình hệ thống Chương trình hệ thống cung cấp một môi trường thuận lợi cho việc phát triển chương trình và thực thi. Chúng có thể được chia thành ◦ Quản lý File ◦ Chương trình quản lý trạng thái thông tin ◦ Cập nhật File ◦ Ngôn ngữ lập trình ◦ Chương trình tải và thực thi ◦ Liên lạc ◦ Dịch vụ nền ◦ Chương trình ứng dụng Hệ điều hành - GV.Phạm Tuấn Khiêm 28 Chương trình hệ thống Quản lý File – Tạo, xóa, sao chép, đổi tên, in ấn, kết xuất, liệt kê và các thao tác khác trên tập tin và thư mục Chương trình quản lý trạng thái thông tin ◦ Một số yêu cầu hệ thống về ngày, giờ, số lượng bộ nhớ có sẵn, không gian đĩa, số lượng người dùng ◦ Một số khác cung cấp hiệu suất, việc đăng nhập, và các trình gỡ rối ◦ Các chương trình này định dạng và xuất thông tin ra màn hình hoặc thiết bị xuất khác ◦ Một số hệ thống thực thi registry – đối tượng được sử dụng để lưu trữ và lấy thông tin cấu hình Hệ điều hành - GV.Phạm Tuấn Khiêm 29 Chương trình hệ thống Cập nhật File ◦ Trình soạn thảo văn bản giúp tạo và cập nhật tập tin ◦ Các lệnh đặc biệt để tìm kiếm nội dung của các tập tin hoặc thực hiện chuyển đổi văn bản Ngôn ngữ lập trình – trình biên dịch, trình gỡ rối được cung cấp Chương trình tải và thực thi – trình nạp, trình liên kết, trình gỡ rối dùng cho ngôn ngữ bậc cao và ngôn ngữ máy Liên lạc - Cung cấp cơ chế cho việc tạo ra các kết nối ảo giữa các tiến trình, người dùng, và hệ thống máy tính ◦ Cho phép người dùng gửi tin nhắn đến một màn hình của người khác, duyệt web, gửi mail, đăng nhập từ xa, chuyển các tập tin từ một máy tới máy khác Hệ điều hành - GV.Phạm Tuấn Khiêm 30 Chương trình hệ thống Dịch vụ nền Chạy lúc khởi động Một số chạy tại lúc hệ thống khởi động và lúc hệ thống kết thúc Một số chạy từ lúc khởi động đến lúc tắt máy Cung cấp các tiện ích như kiểm tra đĩa, điều phối tiến trình, báo lỗi đăng nhập, in ấn Chạy trong chế độ người dùng, không chạy trong chế độ hạt nhân Chương trình ứng dụng Không thuộc về hệ thống Chạy bởi người dùng Không được coi là một phần của hệ điều hành Được khởi động bằng lệnh, chuột, cảm ứng tay Hệ điều hành - GV.Phạm Tuấn Khiêm 31 Cấu trúc hệ điều hành Bao gồm các cấu trúc ◦ Cấu trúc đơn giản – MS-DOS ◦ Cấu trúc phức tạp – UNIX ◦ Cấu trúc phân lớp – trừu tượng hóa ◦ Cấu trúc Microkernel – Mash ◦ Cấu trúc Module ◦ Cấu trúc lai Hệ điều hành - GV.Phạm Tuấn Khiêm 35 Cấu trúc đơn giản – MS-DOS MS-DOS: được viết để cung cấp tối đa các chức năng trong 1 không gian nhớ ít nhất ◦ Không được chia thành các đơn thể ◦ Mặc dù MS-DOS có một số cấu trúc, nhưng giao diện và các cấp độ chức năng của nó không phân chia rõ ràng Hệ điều hành - GV.Phạm Tuấn Khiêm 36 Cấu trúc không đơn giản - UNIX UNIX - giới hạn bởi chức năng phần cứng, bản gốc của hệ điều hành UNIX có cấu trúc hạn chế. Các hệ điều hành UNIX bao gồm hai phần riêng biệt: ◦ Chương trình hệ thống ◦ Nhân (Kernel) Bao gồm tất cả mọi thứ bên dưới giao diện lời gọi hệ thống và bên trên phần cứng vật lý Cung cấp hệ thống file, lập lịch CPU, quản lý bộ nhớ, và các chức năng khác Hệ điều hành - GV.Phạm Tuấn Khiêm 37 Cấu trúc hệ thống UNIX truyền thống Vượt ra cấu trúc đơn giản nhưng chưa phân lớp đầy đủ Hệ điều hành - GV.Phạm Tuấn Khiêm 38 Phương pháp tiếp cận phân lớp Hệ điều hành được chia thành một số lớp (cấp độ), mỗi lớp được xây dựng dựa trên lớp thấp hơn. Lớp dưới cùng (layer 0) là phần cứng; lớp cao nhất (lớp N) là giao diện người dùng Với tính đơn thể hóa, mỗi lớp chỉ sử dụng các dịch vụ và chức năng của lớp thấp hơn Hệ điều hành - GV.Phạm Tuấn Khiêm 39 Cấu trúc Microkernel Di chuyển nhiều thành phần từ chế độ nhân sang chế độ người dùng HĐH Mash là ví dụ cho cấu trúc Microkernel Mac OS X kernel (Darwin) một phần dựa trên Mach Liên lạc giữa các module người dùng sử dụng cơ chế message passing Lợi ích: ◦ Dễ dàng mở rộng ◦ Dễ dàng chuyển HĐH sang một kiến trúc mới ◦ Đáng tin cậy hơn (ít mã lệnh chạy trong kernel mode) ◦ An toàn hơn Hạn chế ◦ Việc liên lạc từ chế độ người dùng sang chế độ nhân tốn hiệu suất cao Hệ điều hành - GV.Phạm Tuấn Khiêm 40 Cấu trúc Microkernel Application File Device user Program System Driver mode messages messages Interprocess memory CPU kernel Communication managment scheduling mode microkernel hardware Hệ điều hành - GV.Phạm Tuấn Khiêm 41 Cấu trúc Module Nhiều HĐH hiện đại được thực thi theo cấu trúc module hóa hạt nhân ◦ Sử dụng cách tiếp cận hướng đối tượng ◦ Mỗi thành phần lõi riêng biệt ◦ Mỗi thành phần lõi liên lạc với các thành phần khác qua giao diện ◦ Mỗi thành phần lõi có thể được nạp thông qua nhân chính Giống cấu trúc phân lớp nhưng linh hoạt hơn ◦ Linux, Solaris, … Hệ điều hành - GV.Phạm Tuấn Khiêm 42 Cấu trúc Module - Solaris Hệ điều hành - GV.Phạm Tuấn Khiêm 43 Các hệ thống lai Hầu hết các hệ điều hành hiện đại thực sự không sử dụng một mô hình thuần túy ◦ Mô hình lai sử dụng nhiều hướng tiếp cận để giải quyết tính hiệu quả, an ninh, tính khả dụng ◦ Nhân của Linux và Solaris được thiết kế nguyên khối, cộng với các mô đun chức năng động ◦ Windows hầu hết là nguyên khối, cộng với microkernel của các hệ thống phụ khác nhau – personalities Apple Mac OS X là hệ thống lai, phân lớp, giao diện người dung Aqua và môi trường lập trình Cocoa Hệ điều hành - GV.Phạm Tuấn Khiêm 44 Cấu trúc Mac OS X graphical user interface Aqua application environments and services Java Cocoa Quicktime BSD kernel environment BSD Mach I/O kit kernel extensions Hệ điều hành - GV.Phạm Tuấn Khiêm 45 iOS HĐH di động của Apple dùng cho iPhone, Ipad ◦ Có cấu trúc dựa trên Mac OS X, cộng với 1 số chức năng bổ sung ◦ Không chạy các ứng dụng OS X ◦ Cocoa Touch: Objective-C API dùng việc phát triển các ứng dụng ◦ Media services: đồ họa, âm thanh, video ◦ Core services: điện toán đám mây, cơ sở dữ liệu ◦ Core OS: dựa trên nhân HĐH Mac OS X Hệ điều hành - GV.Phạm Tuấn Khiêm 46 Android Được phát triển bởi Open Handset Alliance (chủ yếu là Google) ◦ Mã nguồn mở Ngăn xếp phân lớp tương tự trong iOS Dựa trên nhân Linux nhưng có cập nhật ◦ Cung cấp quản lý tiến trình, bộ nhớ, quản lý trình điều khiển thiết bị ◦ Cộng thêm quản lý điện năng Môi trường thời gian chạy bao gồm bộ thư viện lõi và máy ảo Dalvik ◦ Ứng dụng được phát triển trong Java cộng với API Android Hệ điều hành - GV.Phạm Tuấn Khiêm 47 Kiến trúc AndroidApplications Application Framework Libraries Android runtime SQLite openGL Core Libraries surface media Dalvik manager framework virtual machine webkit libc Hệ điều hành - GV.Phạm Tuấn Khiêm 48 Hết phần cấu trúc Hệ điều hành Hệ điều hành - GV.Phạm Tuấn Khiêm 49 Chương 2 TIẾN TRÌNH NỘI DUNG Khái niệm tiến trình Định thời tiến trình Các thao tác trên tiến trình Truyền thông liên tiến trình (Interprocess Communication - IPC) Hệ điều hành - GV.Phạm Tuấn Khiêm 2 MỤC TIÊU Giớithiệu các khái niệm về tiến trình Mô tả các đặc trưng khác nhau của tiến trình Khảo sát việc truyền thông liên tiến trình sử dụng cơ chế shared memory và cơ chế message passing Hệ điều hành - GV.Phạm Tuấn Khiêm 3 Khái niệm tiến trình HĐH thực thi nhiều loại chương trình khác nhau ◦ Hệ thống bó (Batch System) – công việc (jobs) ◦ Hệ thống chia sẻ thời gian (Time-shared System) –chương trình người dùng (user programs) hoặc tác vụ (tasks) Tiến trình – một chương trình đang thực thi Tiến trình gồm nhiều thành phần: ◦ Mã chương trình (program code), còn gọi là phần văn bản (text) ◦ Các hoạt động hiện hành: bộ đếm chương trình (program counter), thanh ghi (register) ◦ Ngăn xếp (Stack): chứa đựng dữ liệu tạm Các tham số, địa chỉ, biến cục bộ ◦ Thành phần dữ liệu (Data section): chứa đựng biến toàn cục ◦ Khối xếp (Heap): chứa bộ nhớ cấp phát động trong suốt thời gian chạy Hệ điều hành - GV.Phạm Tuấn Khiêm 4 Khái niệm tiến trình Chương trình là thực thể thụ động (passive) được lưu trữ trên đĩa (Executable file - tập tin thực thi), tiến trình là thực thể hoạt động (active) ◦ Chương trình trở thành tiến trình khi tập tin thực thi được đưa vào trong bộ nhớ Việc thực thi chương trình được bắt đầu bằng: đúp chuột trong giao diện đồ họa; gõ tên lệnh trong giao diện dòng lệnh Một chương trình có thể có nhiều tiến trình ◦ Nhiều người dùng cùng chạy một loại chương trình Hệ điều hành - GV.Phạm Tuấn Khiêm 5 Tiến trình trong bộ nhớ Hệ điều hành - GV.Phạm Tuấn Khiêm 6 Trạng thái tiến trình Khi một tiến trình thực thi, nó có thể thay đổi trạng thái ◦ New: tiến trình đang được tạo ◦ Running: tập lệnh đang được thực thi ◦ Waiting: tiến trình đang chờ một số sự kiện xảy ra ◦ Ready: tiến trình đang chờ nhận bộ xử lý (CPU) ◦ Terminated: tiến trình hoàn thành việc thực thi Hệ điều hành - GV.Phạm Tuấn Khiêm 7 Sơ đồ trạng thái tiến trình Hệ điều hành - GV.Phạm Tuấn Khiêm 8 Khối điều khiển tiến trình (Process Control Block - PCB) Thông tin được liên kết vào mỗi tiến trình (Còn gọi là khối điều khiển tác vụ) Trạng thái tiến trình – running, waiting,… Bộ đếm chương trình – vị trí của lệnh thực thi tiếp theo Thanh ghi – nội dung của tất cả tiến trình Thông tin định thời CPU – độ ưu tiên, con trỏ hàng đợi Thông tin quản lý bộ nhớ - bộ nhớ được cấp phát cho tiến trình Thông tin thống kê - CPU được sử dụng, đồng hồ đếm thời gian, giới hạn thời gian Thông tin trạng thái Nhập/Xuất – các thiết bị được cấp phát cho tiến trình, danh sách các tập tin Hệ điều hành - GV.Phạm Tuấn Khiêm 9 Chuyển CPU từ tiến trình tới tiến trình Hệ điều hành - GV.Phạm Tuấn Khiêm 10 Tiểu trình Đến thời điểm đang xét, tiến trình có 1 tiểu trình (Thread) duy nhất thực thi Xét trường hợp có nhiều bộ đếm chương trình trên tiến trình ◦ Nhiều vị trí lệnh có thể thực thi cùng một lúc Nhiều tiểu trình điều khiển khảo sát ở chương Tiểu trình (Threads) Phải có không gian lưu trữ chi tiết cho các tiểu trình, nhiều bộ đếm chương trình trong PCB Hệ điều hành - GV.Phạm Tuấn Khiêm 11 Sự biểu diễn tiến trình trong Linux Được biểu diễn bằng cấu trúc ngôn ngữ C stack_struck pid t_pid; long state; unsigned int time_slice struct task_struct *parent; struct list_head children; struct files_struct *files; struct mm_struct *mm; Hệ điều hành - GV.Phạm Tuấn Khiêm 12 Định thời tiến trình Đối với hệ thống chia sẻ thời gian: tối đa việc sử dụng CPU, chuyển đổi CPU giữa các tiến trình một cách nhanh chóng Bộ định thời tiến trình lựa chọn 1 trong các tiến trình có sẵn để thực thi tiếp theo với CPU Các hàng đợi định thời của các tiến trình ◦ Job queue – tập tất cả các tiến trình trong hệ thống ◦ Ready queue – tập tất cả các tiến trình đang có trong bộ nhớ chính, sẵn sang và chờ thực thi ◦ Device queue – tập các tiến trình đang chờ một thiết bị nhập/xuất ◦ Các tiến trình di chuyển giữa các hàng đợi Hệ điều hành - GV.Phạm Tuấn Khiêm 13 Ready queue và các Device queue khác nhau Hệ điều hành - GV.Phạm Tuấn Khiêm 14 Biểu diễn định thời tiến trình Hệ điều hành - GV.Phạm Tuấn Khiêm 15 Các bộ định thời Bộ định thời ngắn hạn (Short-term Scheduler hoặc CPU Scheduler) – chọn tiến trình sẽ được thực thi tiếp theo và cấp phát CPU ◦ Bộ định thời ngắn hạn được gọi thường xuyên (mili giây) phải nhanh chóng Bộ định thời dài hạn (Long-term Scheduler hoặc job Scheduler) – chọn tiến trình được đưa vào ready queue ◦ Bộ định thời dài hạn được gọi không thường xuyên (giây, phút) có thể chậm ◦ Bộ định thời dài hạn kiểm soát mức độ đa chương (số tiến trình trong bộ nhớ) Tiến trình có thể được mô tả theo 2 loại: ◦ Tiến trình thiên hướng vào ra (I/O-bound process) – tốn nhiều thời gian cho việc nhập xuất hơn việc tính toán, có nhiều phiên sử dụng CPU ngắn ◦ Tiến trình thiên hướng xử lý (CPU-bound process) – tốn nhiều thời gian cho việc tính toán, có vài phiên sử dụng CPU dài Bộ định thời dài hạn cố gắng làm cho 2 loại tiến trình kết hợp làm việc hiệu quả nhất Hệ điều hành - GV.Phạm Tuấn Khiêm 16 Các bộ định thời Bộ định thời trung hạn (Medium-term Scheduler) – được bổ sung khi mức độ đa chương cần giảm ◦ Di chuyển tiến trình từ bộ nhớ lưu trữ trên đĩa, đem lại từ đĩa để tiếp tục thực hiện: swapping Hệ điều hành - GV.Phạm Tuấn Khiêm 17 Chuyển ngữ cảnh Khi CPU chuyển sang một tiến trình khác, hệ thống phải lưu lại trạng thái của tiến trình cũ và tải trạng thái đã lưu cho tiến trình mới bằng cách chuyển ngữ cảnh (context switch) Ngữ cảnh của tiến trình được thể hiện trong PCB Thời gian chuyển ngữ cảnh là chi phí quản lý đầu tiên; hệ thống không có công việc hữu ích trong khi chuyển ◦ HĐH và PCB càng phức tạp chuyển ngữ cảnh càng lâu Thời gian phụ thuộc vào phần cứng hỗ trợ ◦ Một số phần cứng cung cấp nhiều tập thanh ghi trên CPU nhiều ngữ cảnh được tải cùng lúc Hệ điều hành - GV.Phạm Tuấn Khiêm 19 Các thao tác trên tiến trình Hệ thống phải cung cấp các cơ chế: ◦ Tạo tiến trình ◦ Kết thúc tiến trình ◦ Các thao tác cụ thể kèm theo Hệ điều hành - GV.Phạm Tuấn Khiêm 20 Tạo tiến trình Tiến trình cha tạo tiến trình con, tiến trình con lại tạo ra các tiến trình khác, hình thành cây tiến trình Tiến trình được xác định và quản lý thông qua mã định danh tiến trình (process identifier – pid) Các tùy chọn chia sẻ tài nguyên ◦ Tiến trình cha và tiến trình con chia sẻ tất cả tài nguyên ◦ Tiến trình con sử dụng chung tập tài nguyên con của tiến trình cha ◦ Tiến trình cha và tiến trình con không chia sẻ tài nguyên Các tùy chọn thực thi ◦ Tiến trình cha và tiến trình con thực thi đồng thời ◦ Tiến trình cha chờ đến khi tiến trình con kết thúc Hệ điều hành - GV.Phạm Tuấn Khiêm 21 Cây tiến trình trong Linux init pid = 1 login kthreadd sshd pid = 8415 pid = 2 pid = 3028 bash khelper pdflush sshd pid = 8416 pid = 6 pid = 200 pid = 3610 emacs tcsch ps pid = 9204 pid = 4005 pid = 9298 Hệ điều hành - GV.Phạm Tuấn Khiêm 22 Tạo tiến trình Không gian địa chỉ ◦ Tiến trình con là một bản sao của tiến trình cha (nó có cùng chương trình và dữ liệu như tiến trình cha) ◦ Tiến trình con là một chương trình mới được nạp vào Ví dụ trên UNIX ◦ Lời gọi hệ thống fork() tạo ra một tiến trình mới ◦ Lời gọi hệ thống exec() được sử dụng sau lời gọi fork() để thay thế không gian bộ nhớ của tiến trình bằng một chương trình mới Hệ điều hành - GV.Phạm Tuấn Khiêm 23 Chương trình C: tạo 1 tiến trình riêng biệt sử dụng lời gọi hệ thống fork() trong UNIX Hệ điều hành - GV.Phạm Tuấn Khiêm 24 Tạo tiến trình riêng biệt bằng Windows API Hệ điều hành - GV.Phạm Tuấn Khiêm 25 Kết thúc tiến trình Tiến trình thực thi câu lệnh cuối cùng và sau đó yêu cầu hệ điều hành xóa nó bằng cách sử dụng lời gọi hệ thống exit() ◦ Trạng thái dữ liệu từ tiến trình con được trả về cho tiến trình cha (thông qua lời gọi hệ thống wait() ) ◦ Các tài nguyên của tiến trình được giải phóng bởi HĐH Tiến trình cha kết thúc việc thực thi của tiến trình con bằng lời gọi hệ thống abort() vì một số lý do: ◦ Tiến trình con sử dụng vượt mức tài nguyên nó được cấp phát ◦ Tác vụ được gán cho tiến trình con không còn cần nữa ◦ Tiến trình cha kết thúc và HĐH không cho phép tiến trình con tiếp tục nếu tiến trình cha kết thúc Hệ điều hành - GV.Phạm Tuấn Khiêm 26 Kết thúc tiến trình Một số hệ thống không cho phép một tiến trình con tồn tại nếu tiến trình cha của nó đã chấm dứt. Nếu một tiến trình kết thúc (bình thường hoặc bất thường), thì sau đó tất cả các tiến trình con của nó cũng phải được kết thúc. ◦ Kết thúc theo tầng (cascading termination). Tất cả tiến trình con, cháu,… đều kết thúc ◦ Việc kết thúc được thực hiện bởi HĐH Các tiến trình cha có thể chờ đợi sự kết thúc của tiến trình con bằng lời gọi hệ thống wait(). Lời gọi này trả về trạng thái thông tin và mã pid của tiến trình kết thúc pid = wait(&status); Một tiến trình đã chấm dứt, nhưng tiến trình cha vẫn chưa gọi lời gọi wait(), thì được gọi là tiến trình zombie Nếu tiến trình cha kết thúc mà không gọi lời gọi wait(), thì tiến trình con được gọi là tiến trình orphan Hệ điều hành - GV.Phạm Tuấn Khiêm 27 Kiến trúc đa tiến trình – Chrome Browser Nhiều trình duyệt web chạy như một đơn tiến trình ◦ Nếu một trang web có lỗi, toàn bộ trình duyệt có thể bị treo hoặc sụp đổ Trình duyệt Google Chrome là đa tiến trình với 3 loại tiến trình khác nhau ◦ Tiến trình Browser: quản lý giao diện, đĩa và nhập/xuất ◦ Tiến trình Renderer: trình diễn các trang web, HTML, Javascript. Một tiến trình Renderer được tạo mỗi khi website được mở Chạy trong sandbox thì hạn chế truy cập đĩa và I/O, giảm thiểu tác động của các khai thác bảo mật ◦ Tiến trình plug-in đối với từng loại plug-in Hệ điều hành - GV.Phạm Tuấn Khiêm 28 Truyền thông liên tiến trình Tiến trình trong một hệ thống có thể là tiến trình độc lập hoặc tiến trình cộng tác Tiến trình cộng tác có thể ảnh hưởng hoặc bị ảnh hưởng bởi tiến trình khác, bao gồm chia sẻ dữ liệu Có nhiều lý do để các tiến trình cộng tác ◦ Chia sẻ thông tin ◦ Tăng tốc độ tính toán ◦ Đơn thể hóa ◦ Sự thuận tiện Tiến trình cộng tác cần cơ chế truyền thông liên tiến trình (interprocess communication - IPC) Hai mô hình IPC ◦ Bộ nhớ chia sẻ (Shared memory) ◦ Trao đổi thông điệp (Message passing) Hệ điều hành - GV.Phạm Tuấn Khiêm 29 Mô hình truyền thông (a) Message passing. (b) shared memory. Hệ điều hành - GV.Phạm Tuấn Khiêm 30 Tiến trình cộng tác Tiến trình độc lập không thể ảnh hưởng hoặc bị ảnh hưởng bởi việc thực thi của các tiến trình khác Tiến trình cộng tác có thể ảnh hưởng hoặc bị ảnh hưởng bởi việc thực thi của các tiến trình khác Lợi ích của việc cộng tác ◦ Chia sẻ thông tin ◦ Tăng tốc độ tính toán ◦ Đơn thể hóa ◦ Sự thuận tiện Hệ điều hành - GV.Phạm Tuấn Khiêm 31 Bài toán Producer-Consumer Mô hình tiến trình hợp tác: tiến trình Producer sản xuất thông tin được tiêu thụ bởi tiến trình Consumer ◦ Vùng đệm không giới hạn (Unbounded-buffer) – không giới hạn kích thước vùng đệm ◦ Vùng đệm giới hạn (Bounded-buffer) – kích thước vùng đệm được gán cố định Hệ điều hành - GV.Phạm Tuấn Khiêm 32 Bounded-buffer – giải pháp bộ nhớ chia sẻ Dữ liệu chia sẻ #define BUFFER_SIZE 10 typedef struct {... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; Hệ điều hành - GV.Phạm Tuấn Khiêm 33 Bounded-buffer – tiến trình Producer item next_produced; while (true) { while (((in + 1) % BUFFER_SIZE) == out) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } Hệ điều hành - GV.Phạm Tuấn Khiêm 34 Bounded-buffer – tiến trình Consumer item next_consumed; while (true) { while (in == out) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } Hệ điều hành - GV.Phạm Tuấn Khiêm 35 Truyền thông liên tiến trình – giải pháp bộ nhớ chia sẻ Một vùng của bộ nhớ được chia sẻ giữa các tiến trình có nhu cầu liên lạc Liên lạc dưới sự kiểm soát của các tiến trình người sử dụng, không phải hệ điều hành Vấn đề chính là cung cấp cơ chế cho phép các tiến trình người dung đồng bộ hóa các hoạt động của chúng khi chúng truy cập bộ nhớ chia sẻ Hệ điều hành - GV.Phạm Tuấn Khiêm 36 Truyền thông liên tiến trình – giải pháp trao đổi thông điệp Cơ chế cho tiến trình truyền thông và đồng bộ các hoạt động của chúng Thông điệp hệ thống - các tiến trình liên lạc với nhau mà không cần đến các biến chia sẻ IPC cung cấp hai hoạt động ◦ Send(message) ◦ Receive(message) Kích thước message là cố định hoặc biến đổi Hệ điều hành - GV.Phạm Tuấn Khiêm 37 Truyền thông liên tiến trình – giải pháp trao đổi thông điệp Nếu tiến trình P và Q cần liên lạc với nhau, chúng cần ◦ Thiết lập một liên kết truyền thông giữa chúng ◦ Trao đổi thông điệp qua việc gửi/nhận Vấn đề thực hiện: ◦ Thiết lập liên kết như thế nào? ◦ Một liên kết có thể được liên kết với hơn hai tiến trình? ◦ Bao nhiêu liên kết có thể có giữa mỗi cặp tiến trình? ◦ Năng suất của một liên kết? ◦ Liên kết một chiều, hai chiều? Hệ điều hành - GV.Phạm Tuấn Khiêm 38 Truyền thông liên tiến trình – giải pháp trao đổi thông điệp Thực hiện liên kết truyền thông ◦ Về mặt vật lý Bộ nhớ chia sẻ Đường truyền Mạng ◦ Về mặt logic Trực tiếp hoặc gián tiếp Đồng bộ hoặc không đồng bộ Vùng đệm tự động hoặc chi tiết Hệ điều hành - GV.Phạm Tuấn Khiêm 39 Truyền thông trực tiếp Tiến trình phải được đặt tên một cách rõ rang ◦ Send(P,message) – gởi thông điệp tới tiến trình P ◦ Receive(Q,message) – nhận thông điệp từ tiến trình Q Thuộc tính của liên kết ◦ Liên kết được thiết lập tự động ◦ Một liên kết được gắn chính xác với một cặp tiến trình ◦ Giữa mỗi cặp tồn tại đúng một liên kết ◦ Các liên kết có thể là một chiều, nhưng thường là hai chiều Hệ điều hành - GV.Phạm Tuấn Khiêm 40 Truyền thông gián tiếp Thông điệp được gởi và nhận từ hộp thư (mailboxs) ◦ Mỗi hộp thư có một mã id duy nhất ◦ Tiến trình có thể liên lạc chỉ khi nó chia sẻ hộp thư Thuộc tính của liên kết ◦ Liên kết chỉ được thiết lập nếu các tiến trình chia sẻ một hộp thư chung ◦ Một liên kết có thể được gắn với nhiều tiến trình ◦ Mỗi cặp tiến trình có thể chia sẻ một số liên kết ◦ Liên kết có thể là một chiều hoặc hai chiều Hệ điều hành - GV.Phạm Tuấn Khiêm 41 Truyền thông gián tiếp Các thao tác ◦ Tạo hộp thư mới (cổng) ◦ Gởi và nhận thông điệp thông qua hộp thư ◦ Hủy hộp thư Các hàm được định nghĩa như sau: ◦ Send(A,message) – gởi một thông điệp tới hộp thư A ◦ Receive(A,message) – nhận một thông điệp từ hộp thư A Hệ điều hành - GV.Phạm Tuấn Khiêm 42 Truyền thông gián tiếp Hộp thư chia sẻ ◦ P1,P2 và P3 chia sẻ hộp thư A ◦ P1 gởi thông điệp, P2 và P3 nhận thông điệp ◦ Tiến trình nào nhận thông điệp? Giải pháp ◦ Cho phép một liên kết được gắn với ít nhất hai tiến trình ◦ Tại một thời điểm, chỉ cho phép duy nhất một tiến trình nhận ◦ Cho phép hệ thống lựa chọn ngẫu nhiên tiến trình nhận. Tiến trình gởi thông báo tên của tiến trình nhận Hệ điều hành - GV.Phạm Tuấn Khiêm 43 Đồng bộ hóa Cơ chế trao đổi thông điệp có thể thực hiện theo 2 cách: Bloking hoặc non-blocking Blocking được xem như đồng bộ hóa ◦ Blocking send – tiến trình gởi bị khóa cho đến khi thông điệp được nhận ◦ Blocking receive – tiến trình nhận bị khóa cho đến khi thông điệp gởi tới Non-blocking được xem như không đồng bộ ◦ Non-blocking send – tiến trình gởi gởi thông điệp đi và tiếp tục ◦ Non-blocking receive – tiến trình nhận nhận thông điệp Hợp lệ Không hợp lệ (rỗng – null) Hệ điều hành - GV.Phạm Tuấn Khiêm 44 Vùng đệm Hàng đợi thông điệp được gán vào liên kết Thực thi bằng 1 trong 3 cách ◦ Zero capacity – không có thông điệp trong liên kết. Tiến trình gởi phải chờ tiến trình nhận ◦ Bounded capacity – giới hạn độ dài của n thông điệp. Tiến trình gởi phải chờ nếu liên kết đầy ◦ Unbounded capacity – không giới hạn độ dài. Tiến trình gởi không bao giờ chờ Hệ điều hành - GV.Phạm Tuấn Khiêm 45 Hết chương Hệ điều hành - GV.Phạm Tuấn Khiêm 46 Chương 3 TIỂU TRÌNH NỘI DUNG Tổng quan về tiểu trình Lập trình đa tiểu trình Mô hình đa tiểu trình Thư viện tiểu trình Tiểu trình ẩn Tiểu trình trong một số hệ điều hành Hệ điều hành - GV.Phạm Tuấn Khiêm 2 MỤC TIÊU Giớithiệu các khái niệm về tiểu trình Thảo luận các API trên Pthread, Windows và các thư viện tiểu trình Java Khám phá nhiều chiến lược cung cấp tiểu trình ẩn Khảo sát tiểu trình trong HĐH Windows và Linux Hệ điều hành - GV.Phạm Tuấn Khiêm 3 Tổng quan về tiểu trình Tiểu trình (Thread) (hay còn gọi là tiến trình nhỏ - lightweight process) là một đơn vị cơ bản sử dụng CPU Một thực thể trong tiến trình mà hệ điều hành có thể lập lịch để nó thực hiện, không có nó thì các tiến trình của nó không thể thực hiện được Bao gồm: ◦ Mã định danh ID (identifier) ◦ Bộ đếm chương trình (program counter) ◦ Tập thanh ghi (register) ◦ Ngăn xếp (stack) Hệ điều hành - GV.Phạm Tuấn Khiêm 4 Lý do xuất hiện tiểu trình Hầu hết các ứng dụng hiện đại được viết theo hướng đa tiểu trình Các tiểu trình chạy bên trong ứng dụng Nhiều tác vụ trên ứng dụng có thể được thực hiện bởi nhiều tiểu trình riêng biệt ◦ Cập nhật hiển thị ◦ Lấy dữ liệu ◦ Kiểm tra chính tả ◦ Trả lời một yêu cầu trong mạng Việc tạo tiến trình thì phức tạp trong khi việc tạo tiểu trình thì đơn giản hơn Mã đơn giản, nâng cao hiệu quả Nhân HĐH được đa tiểu trình hóa Hệ điều hành - GV.Phạm Tuấn Khiêm 5 Kiến trúc web-server đa tiểu trình Hệ điều hành - GV.Phạm Tuấn Khiêm 6 Lợi ích của tiểu trình Khả năng đáp ứng – cho phép tiến trình tiếp tục thực thi nếu một phần nó bị khóa, đặc biệt quan trọng đối với việc thiết kế giao diện người dùng Chia sẻ tài nguyên – Các tiểu trình chia sẻ tài nguyên của tiến trình, dễ dàng hơn so với 2 cơ chế bộ nhớ chia sẻ hoặc trao đổi thông điệp Tính kinh tế – ít tốn kém hơn so với việc tạo tiến trình, chi phí chuyển ngữ cảnh của tiểu trình thấp hơn so với chuyển ngữ cảnh của tiến trình Khả năng mở rộng – tiến trình có thể tận dụng lợi thế của kiến trúc đa xử lý Hệ điều hành - GV.Phạm Tuấn Khiêm 7 Lập trình đa tiểu trình Hệ thống đa lõi hoặc đa xử lý đòi hỏi cao đối với các lập trình viên, những thách thức bao gồm: ◦ Chia nhỏ hoạt động ◦ Cân bằng ◦ Tách dữ liệu ◦ Phụ thuộc dữ liệu ◦ Kiểm tra và gỡ lỗi Hệ thống xử lý song song: có thể thực hiện nhiều việc cùng một lúc Hệ thống xử lý đồng thời: hỗ trợ nhiều hơn một nhiệm vụ được thực hiện theo tiến độ Hệ điều hành - GV.Phạm Tuấn Khiêm 8 Lập trình đa tiểu trình Các loại xử lý song song ◦ Song song dữ liệu – phân tán các tập con của dữ liệu ban đầu đến nhiều lõi, các thao tác thực hiện tương tự trên mỗi lõi ◦ Song song tác vụ – phân phối các tiểu trình đến các lõi, mỗi tiểu trình thực hiện thao tác duy nhất Hệ điều hành - GV.Phạm Tuấn Khiêm 9 Xử lý đồng thời và xử lý song song Thực thi đồng thời trên hệ thống đơn lõi (single- core system) Thực thi song song trên hệ thống đa lõi (multi-core system) Hệ điều hành - GV.Phạm Tuấn Khiêm 10 Tiến trình đơn tiểu trình và tiến trình đa tiểu trình Hệ điều hành - GV.Phạm Tuấn Khiêm 11 Tiểu trình người dùng và tiểu trình nhân Tiểu trình người dùng (User threads) – quản lý công việc bằng thư viện tiểu trình ở mức người dùng Ba thư viện tiểu trình chính: ◦ POSIX Pthreads ◦ Windows threads ◦ Java threads Tiểu trình nhân (Kernel threads) – được hỗ trợ và quản lý trực tiếp bởi HĐH Hầu như tất cả các HĐH hiện đại đều hỗ trợ tiểu trình nhân, bao gồm: ◦ Windows ◦ Solaris ◦ Linux ◦ Tru64 UNIX ◦ Mac OS X Hệ điều hành - GV.Phạm Tuấn Khiêm 13 Mô hình đa tiểu trình Many-to-One One-to-One Many-to-Many Hệ điều hành - GV.Phạm Tuấn Khiêm 14 Mô hình Many-to-One Nhiều tiểu trình ở mức người dùng được ánh xạ đến tiểu trình nhân duy nhất Một tiểu trình bị khóa thì tất cả các tiểu trình cũng bị khóa Nhiều tiểu trình có thể không chạy song song trên hệ thống đa lõi bởi vì tại một thời điểm chỉ có một tiểu trình chạy trong chế độ nhân Một số hệ thống hiện hành sử dụng mô hình này ◦ Solaris Green Threads ◦ GNU Portable Threads Hệ điều hành - GV.Phạm Tuấn Khiêm 15 Mô hình One-to-One Mỗi tiểu trình mức người dùng ánh xạ đến một tiểu trình mức nhân Việc tạo 1 tiểu trình người dùng sẽ tạo một tiểu trình nhân Thực thi đồng thời nhiều hơn mô hình Many- to-One Số tiểu trình trên tiến trình đôi khi bị hạn chế vì chi phí tính toán Các ví dụ ◦ Windows ◦ Linux ◦ Solaris 9 và cao hơn Hệ điều hành - GV.Phạm Tuấn Khiêm 16 Mô hình Many-to-Many Cho phép nhiều tiểu trình mức người dùng được ánh xạ đến nhiều tiểu trình mức nhân Cho phép HĐH tạo ra một số lượng tiểu trình nhân đủ để thực hiện Solaris phiên bản trước 9 hỗ trợ mô hình này Windows với gói ThreadFiber hỗ trợ Hệ điều hành - GV.Phạm Tuấn Khiêm 17 Mô hình 2 mức Giống mô hình many- to-many nhưng cũng cho phép 1 tiểu trình nhất định ánh xạ đến 1 tiểu trình nhân Các ví dụ ◦ IRIX ◦ HP-UX ◦ Tru64 UNIX ◦ Solaris 8 và thấp hơn Hệ điều hành - GV.Phạm Tuấn Khiêm 18 Thư viện tiểu trình Thư viện tiểu trình cung cấp API cho lập trình viên để tạo và quản lý tiểu trình Hai cách chính để thực hiện ◦ Sử dụng thư viện hoàn toàn ở cấp độ người dùng ◦ Sử dụng thư viện tiểu trình ở cấp độ nhân được hỗ trợ bởi HĐH Hệ điều hành - GV.Phạm Tuấn Khiêm 19 Thư viện Ptheads Có thể được cung cấp ở cả mức người dùng hoặc mức nhân API tiêu chuẩn POSIX cho việc tạo và đồng bộ hóa tiểu trình Là một bản liệt kê các hoạt động của tiểu trình, không phải là sự thực thi Người thiết kế HĐH có thể thực thi bản liệt kê theo bất cứ cách nào họ muốn Phổ biến trong HĐH UNIX (Solaris, Linux, Mac OS X) Hệ điều hành - GV.Phạm Tuấn Khiêm 20 Ví dụ chương trình sử dụng Ptheads Hệ điều hành - GV.Phạm Tuấn Khiêm 21 Ví dụ chương trình sử dụng Ptheads Hệ điều hành - GV.Phạm Tuấn Khiêm 22 Mã Ptheads kết nối 10 tiểu trình Hệ điều hành - GV.Phạm Tuấn Khiêm 23 Chương trình C sử dụng thư viện Windows Threads Hệ điều hành - GV.Phạm Tuấn Khiêm 24 Chương trình C sử dụng thư viện Windows Threads Hệ điều hành - GV.Phạm Tuấn Khiêm 25 Thư viện Java Threads Tiểu trình Java được quản lý bởi JVM Thường được thực hiện bằng cách sử dụng mô hình tiểu trình được cung cấp bởi hệ điều hành Tiểu trình Java có thể được tạo bởi: Hệ điều hành - GV.Phạm Tuấn Khiêm 26 Chương trình đa tiểu trình Java Hệ điều hành - GV.Phạm Tuấn Khiêm 27 Chương trình đa tiểu trình Java Hệ điều hành - GV.Phạm Tuấn Khiêm 28 Tiểu trình ẩn Sự phát triển của các ứng dụng đa tiểu trình với số lượng tiểu trình trong ứng dụng ngày càng tăng, đòi hỏi chương trình chạy chính xác cao khó khăn nhiều với lập trình viên giải quyết: tiểu trình ẩn Tạo và quản lý tiểu trình được thực hiện bởi trình biên dịch và thư viện run-time (thời gian chạy), chứ không phải là lập trình viên Có 3 phương pháp ◦ Thread Pools ◦ OpenMP ◦ Grand Central Dispatch Các phương pháp khác bao gồm: Microsoft Threading Building Blocks (TBB), gói java.util.concurrent Hệ điều hành - GV.Phạm Tuấn Khiêm 29 Thread Pools Tạo một số tiểu trình trong một vùng lưu trữ, nơi mà các tiểu trình đang chờ đợi công việc Ưu điểm ◦ Nhanh hơn: đáp ứng một yêu cầu với một tiểu trình hiện có hơn là tạo ra một tiểu trình mới ◦ Cho phép số lượng tiểu trình trong ứng dụng được vượt kích thước của vùng lưu trữ ◦ Sử dụng các chiến lược khác nhau để chạy tác vụ Windows API hỗ trợ thread pools Hệ điều hành - GV.Phạm Tuấn Khiêm 30 OpenMP OpenMP là một tập các chỉ thị biên dịch như một API cho các chương trình viết bằng C, C ++, hoặc FORTRAN Hỗ trợ cho lập trình song song trong môi trường chia sẻ bộ nhớ Xác định vùng song song (parallel regions) - khối mã có thể chạy song song #pragma omp parallel Tạo nhiều tiểu trình như có nhiều lõi #pragma omp parallel for for(i=0;ivalue < 0) { add this process to S->list; block(); } } signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } Hệ điều hành - GV.Phạm Tuấn Khiêm 32 Tắc nghẽn và đói CPU Tắc nghẽn (deadlock) - hai hoặc nhiều tiến trình đang chờ đợi vô hạn cho một sự kiện mà có thể được gây ra bởi chỉ một trong các tiến trình đang chờ Gọi S và Q là hai semaphore khởi tạo 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S);...... signal(S); signal(Q); signal(Q); signal(S); Đói CPU (Starvation) - Một tiến trình có thể không bao giờ được rời khỏi hàng đợi semaphore nơi nó bị tạm dừng Hệ điều hành - GV.Phạm Tuấn Khiêm 33 Các bài toán đồng bộ hóa kinh điển Bài toán vùng đệm có giới hạn Bài toán tiến trình đọc – ghi Bài toán bữa ăn tối của các triết gia Hệ điều hành - GV.Phạm Tuấn Khiêm 34 Bài toán vùng đệm có giới hạn N ô nhớ vùng đệm, mỗi ô chứa 1 thông tin Semaphore mutex được khởi tạo giá trị là 1 Semaphore full được khởi tạo giá trị là 0 Semaphore empty được khởi tạo giá trị là N Hệ điều hành - GV.Phạm Tuấn Khiêm 35 Bài toán vùng đệm có giới hạn Cấu trúc của tiến trình Producer do {...... wait(empty); wait(mutex);...... signal(mutex); signal(full); } while (true); Hệ điều hành - GV.Phạm Tuấn Khiêm 36 Bài toán vùng đệm có giới hạn Cấu trúc của tiến trình Consumer do { wait(full); wait(mutex);...... signal(mutex); signal(empty);...... } while (true); Hệ điều hành - GV.Phạm Tuấn Khiêm 37 Bài toán tiến trình Đọc - Ghi Một tập dữ liệu được chia sẻ giữa một số tiến trình đồng thời ◦ Readers – các tiến trình chỉ đọc dữ liệu, chúng không thực hiện bất kỳ thay đổi nào ◦ Writers – các tiến trình có thể đọc và ghi Bài toán: Cho phép nhiều tiến trình Reader đọc dữ liệu chia sẻ cùng lúc ◦ Chỉ duy nhất một tiến trình Writer truy cập dữ liệu chia sẻ tại cùng thời điểm Bài toán tiến trình Đọc – Ghi có nhiều biến thể, tất cả đều liên quan đến một số hình thức ưu tiên Dữ liệu chia sẻ ◦ Tập dữ liệu ◦ Semaphore rw_mutex được khởi tạo là 1 ◦ Semaphore mutex được khởi tạo là 1 ◦ Integer Read_count được khởi tạo là 0 Hệ điều hành - GV.Phạm Tuấn Khiêm 38 Bài toán tiến trình Đọc - Ghi Cấu trúc của một tiến trình Writer do { wait(rw_mutex);...... signal(rw_mutex); } while (true); Hệ điều hành - GV.Phạm Tuấn Khiêm 39 Bài toán tiến trình Đọc - Ghi Cấu trúc của một tiến trình Reader do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex);...... wait(mutex); read count--; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true); Hệ điều hành - GV.Phạm Tuấn Khiêm 40 Các dạng của bài toán tiến trình Đọc - Ghi Dạng 1: không có tiến trình Reader phải chờ trừ khi tiến trình Writer có quyền sử dụng dữ liệu chia sẻ Dạng 2: khi tiến trình writer sẵn sàng, nó thực hiện việc ghi càng sớm càng tốt Cả 2 đều có thể xảy ra đói CPU kéo theo nhiều biến thể khác Bài toán tổng quát được giải quyết trên một số hệ thống bằng cách nhân HĐH cung cấp các khóa đọc - ghi Hệ điều hành - GV.Phạm Tuấn Khiêm 41 Bài toán bữa ăn tối của các triết gia Thuật ngữ: the dining philosophers problem Có 5 triết gia, 5 chiếc đũa, 5 bát cơm và một âu cơm bố trí như hình vẽ Đây là bài toán cổ điển và là ví dụ minh họa cho một lớp nhiều bài toán tranh đoạt điều khiển: Nhiều tiến trình khai thác nhiều tài nguyên chung Hệ điều hành - GV.Phạm Tuấn Khiêm 42 Bài toán bữa ăn tối của các triết gia Các triết gia chỉ làm 2 việc: Ăn và suy nghĩ ◦ Suy nghĩ: Không ảnh hưởng đến các triết gia khác, đũa, bát và âu cơm ◦ Để ăn: Mỗi triết gia phải có đủ 2 chiếc đũa gần nhất ở bên phải và bên trái mình; chỉ được lấy 1 chiếc đũa một lần và không được phép lấy đũa từ tay triết gia khác ◦ Khi ăn xong: Triết gia bỏ cả hai chiếc đũa xuống bàn và tiếp tục suy nghĩ Hệ điều hành - GV.Phạm Tuấn Khiêm 43 Bài toán bữa ăn tối của các triết gia Dữ liệu chia sẻ ◦ Bát cơm (tập dữ liệu) ◦ Semaphore chopstick được khởi tạo là 1 Hệ điều hành - GV.Phạm Tuấn Khiêm 44 Bài toán bữa ăn tối của các triết gia Cấu trúc giải thuật cho triết gia i do { wait (chopstick[i] ); wait (chopStick[(i + 1) % 5] ); // eat signal (chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think } while (TRUE); Hệ điều hành - GV.Phạm Tuấn Khiêm 45 Bài toán bữa ăn tối của các triết gia Xử lý tắc nghẽn ◦ Cho phép tối đa 4 triết gia được ngồi vào bàn cùng một thời điểm ◦ Cho phép 1 triết gia lấy 2 chiếc đũa chỉ khi cả 2 đều khả thi (việc lấy đũa phải thực hiện trong miền găng) ◦ Sử dụng giải pháp bất đối xứng – một triết gia có số thứ tự lẻ lấy chiếc đũa đầu tiên bên trái, sau đó chiếc bên phải. Một triết gia có số thứ tự chẵn lấy chiếc đũa đầu bên phải, sau đó chiếc bên trái. Hệ điều hành - GV.Phạm Tuấn Khiêm 46 Một số vấn đề với semaphore Sử dụng các toán tử semaphore không đúng ◦ signal(mutex) … wait(mutex) ◦ wait(mutex) … wait(mutex) ◦ Bỏ quên toán tử wait(mutex) hoặc signal(mutex) (hoặc cả hai) Có thể xảy ra tắc nghẽn và đói CPU Hệ điều hành - GV.Phạm Tuấn Khiêm 47 Monitor Giải pháp trừu tượng hóa mức cao, cung cấp một cơ chế tiện lợi và hiệu quả cho việc đồng bộ hóa tiến trình. Kiểu dữ liệu trừu tượng (abstract data type - ADT), các biến nội bộ (bên trong monitor) chỉ có thể truy cập bằng mã trong thủ tục. Chỉ có một tiến trình duy nhất có thể hoạt động bên trong monitor tại một thời điểm. Nhưng không đủ mạnh để mô hình hóa một số lược đồ đồng bộ hóa (chưa có nhiều ngôn ngữ lập trình định nghĩa monitor) Hệ điều hành - GV.Phạm Tuấn Khiêm 48 Cú pháp Monitor monitor monitor-name { // shared variable declarations procedure P1 (…) { …. } procedure Pn (…) {……} Initialization code (…) { … } } } Hệ điều hành - GV.Phạm Tuấn Khiêm 49 Sơ đồ của một Monitor Hệ điều hành - GV.Phạm Tuấn Khiêm 50 Biến điều kiện Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm theo là Wait và Signal Condition x, y; 2 thao tác cho phép trên biến điều kiện ◦ x.wait() – một tiến trình gọi thao tác này tạm ngưng đến khi x.signal() thực thi bởi một tiến trình khác ◦ x.signal() – khôi phục 1 trong các tiến trình đã được gọi bởi x.wait() Nếu không có lệnh x.wait() thì sau đó không có tác động trên biến điều kiện Hệ điều hành - GV.Phạm Tuấn Khiêm 51 Monitor và các biến điều kiện Hệ điều hành - GV.Phạm Tuấn Khiêm 52 Lựa chọn biến điều kiện Nếu tiến trình P gọi x.signal() và tiến trình Q tạm ngưng trong x.wait(), thì điều gì sẽ xảy ra tiếp theo? ◦ Cả 2 tiến trình Q và P không thể thực thi song song. Nếu Q được khôi phục thì P phải chờ Các lựa chọn: ◦ Signal và wait – P chờ đến khi: hoặc Q rời monitor hoặc nó chờ một điều kiện khác ◦ Signal và tiếp tục – Q chờ đến khi: hoặc P rời monitor hoặc nó chờ một điều kiện khác ◦ Cả 2 đều có ưu và nhược điểm – ngôn ngữ thực thi có thể quyết định ◦ Monitor được thực thi trong Concurrent Pascal theo sự thỏa hiệp P đang thực thi signal rời Monitor thì Q được khôi phục ◦ Được thực thi trong các ngôn ngữ khác như Mesa, C#, Java Hệ điều hành - GV.Phạm Tuấn Khiêm 53 Bài toán Dining Philosophers: giải pháp Monitor monitor DiningPhilosophers { enum { THINKING; HUNGRY, EATING) state ; condition self ; 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); test((i + 1) % 5); } Hệ điều hành - GV.Phạm Tuấn Khiêm 54 Bài toán Dining Philosophers: giải pháp Monitor void test (int i) { if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } } Hệ điều hành - GV.Phạm Tuấn Khiêm 55 Bài toán Dining Philosophers: giải pháp Monitor Mỗi triết gia i gọi các hàm pickup() và putdown() theo thứ tự sau: DiningPhilosophers.pickup(i); EAT DiningPhilosophers.putdown(i); Không có tắc nghẽn, nhưng đói CPU có thể có Hệ điều hành - GV.Phạm Tuấn Khiêm 56 Thực thi Monitor sử dụng Semaphore Các biến semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next_count = 0; Mỗi thủ tục F sẽ được thay thế bởi wait(mutex); … body of F; … if (next_count > 0) signal(next) else signal(mutex); Độc quyền truy xuất (Mutual Exclusion) trong Monitor được đảm bảo Hệ điều hành - GV.Phạm Tuấn Khiêm 57 Thực thi Monitor – biến điều kiện Với mỗi biến điều kiện x, ta có semaphore x_sem; // (initially = 0) int x_count = 0; Thao tác x.wait được thực thi như sau x_count++; if (next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count--; Hệ điều hành - GV.Phạm Tuấn Khiêm 58 Thực thi Monitor – biến điều kiện Thao tác x.signal được thực thi như sau if (x_count > 0) { next_count++; signal(x_sem); wait(next); next_count--; } Hệ điều hành - GV.Phạm Tuấn Khiêm 59 Khôi phục tiến trình trong Monitor Nếu một số tiến trình nằm trong hàng đợi với điều kiện x, và thực thi x.signal, thì tiến trình nào được khôi phục? FCFS không đáp ứng đầy đủ Xây dựng toán tử wait có điều kiện, dạng x.wait(c) ◦ c là số ưu tiên ◦ Tiến trình với độ ưu tiên thấp nhất (cao nhất) được định thời kế tiếp Hệ điều hành - GV.Phạm Tuấn Khiêm 60 Cấp phát tài nguyên duy nhất Cấp phát tài nguyên duy nhất giữa các tiến trình cạnh tranh sử dụng số ưu tiên, quy định thời gian tối đa cho việc sử dụng tài nguyên của tiến trình R.acquire(t);... access the resource;... R.release; Trong đó R là một thực thể của ResourceAllocator Hệ điều hành - GV.Phạm Tuấn Khiêm 61 Monitor để cấp phát tài nguyên duy nhất monitor ResourceAllocator { boolean busy; condition x; void acquire(int time) { if (busy) x.wait(time); busy = TRUE; } void release() { busy = FALSE; x.signal(); } initialization code() { busy = FALSE; } } Hệ điều hành - GV.Phạm Tuấn Khiêm 62 Đồng bộ hóa trên một số hệ điều hành Tham khảo “Operating System Concepts, ninth edition, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne” trang 232 Hệ điều hành - GV.Phạm Tuấn Khiêm 63 Phương pháp tiếp cận thay thế Tham khảo “Operating System Concepts, ninth edition, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne” trang 238 Hệ điều hành - GV.Phạm Tuấn Khiêm 64 Hết chương Hệ điều hành - GV.Phạm Tuấn Khiêm 65 Chương 6 TẮC NGHẼN NỘI DUNG Mô hình hệ thống Đặc điểm tắc nghẽn Các phương pháp xử lý tắc nghẽn Ngăn chặn tắc nghẽn Tránh tắc nghẽn Phát hiện tắc nghẽn Khôi phục từ tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 2 MỤC TIÊU Mở rộng mô tả về tắc nghẽn, đối tượng ngăn cản sự thực thi đồng thời của các tiến trình. Trình bày một số phương pháp khác nhau để ngăn chặn hoặc tránh tắc nghẽn trong một hệ thống máy tính. Hệ điều hành - GV.Phạm Tuấn Khiêm 3 Mô hình hệ thống Hệ thống bao gồm nhiều tài nguyên Ký hiệu tài nguyên: R1, R2, … , Rm ◦ Chu kỳ CPU, không gian nhớ, thiết bị nhập/xuất Mỗi tài nguyên Ri có Wi thực thể (instance) Mỗi tiến trình sử dụng tài nguyên như sau: ◦ Yêu cầu (request) ◦ Sử dụng (use) ◦ Giải phóng (release) Hệ điều hành - GV.Phạm Tuấn Khiêm 4 Khái niệm tắc nghẽn Tắc nghẽn (Deadlock): hai hoặc nhiều tiến trình đang chờ đợi vô hạn cho một sự kiện mà có thể được gây ra bởi chỉ một trong các tiến trình đang chờ Ví dụ: ◦ Cùng loại tài nguyên: Xét hệ thống với 3 ổ đĩa CD RW. Giả sử có 3 tiến trình và mỗi tiến trình giữ một ổ đĩa. Nếu mỗi tiến trình yêu cầu thêm một ỗ đĩa khác thì 3 tiến trình sẽ rơi vào trạng thái tắc nghẽn. Mỗi tiến trình đang chờ sự kiện “ổ CD RW được giải phóng” ◦ Khác loại tài nguyên: Xét hệ thống có 1 máy in và 1 ổ đĩa DVD. Giả sử tiến trình Pi đang giữ ổ DVD và tiến trình Pj đang giữ máy in. nếu Pi yêu cầu máy in và Pj yêu cầu ổ DVD thì sẽ xảy ra tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 5 Đặc điểm tắc nghẽn Tắc nghẽn xuất hiện nếu 4 điều kiện sau xảy ra đồng thời ◦ Độc quyền truy xuất (Mutual Exclusion): tại một thời điểm chỉ có duy nhất 1 tiến trình sử dụng tài nguyên ◦ Giữ và đợi (Hold and Wait): một tiến trình giữ ít nhất 1 tài nguyên đang chờ thêm tài nguyên được giữ bởi tiến trình khác ◦ Không ưu tiên (No preemption): một tài nguyên có thể chỉ được giải phóng một cách tự nguyện bởi một tiến trình đang giữ nó, sau khi tiến trình đó hoàn thành tác vụ của mình ◦ Đợi vòng quanh (Circular wait): tồn tại một tập tiến trình đang chờ {P0, P1, …, Pn}. Trong đó, P0 đang chờ tài nguyên được giữ bởi P1, P1 đang chờ tài nguyên được giữ bởi P2, … , Pn-1 đang chờ tài nguyên được giữ bởi Pn, Pn đang chờ tài nguyên được giữ bởi P0. Hệ điều hành - GV.Phạm Tuấn Khiêm 6 Đồ thị cấp phát tài nguyên (RAG: Resource-Allocation Graph) Một tập hợp các đỉnh V và tập các cạnh E V được chia thành 2 loại ◦ P = {P1, P2, …, Pn}, tập tất cả các tiến trình trong hệ thống ◦ R = {R1, R2, …, Rm}, tập tất cả các tài nguyên của hệ thống Cạnh yêu cầu (request edge): cạnh có hướng từ Pi Rj Cạnh cấp phát (assignment edge): cạnh có hướng từ Rj Pi Hệ điều hành - GV.Phạm Tuấn Khiêm 7 Đồ thị cấp phát tài nguyên Tiến trình Tài nguyên với 4 thực thể Pi yêu cầu thực thể tài nguyên Rj Pi Rj Pi đang giữ thực thể của Rj Pi Rj Hệ điều hành - GV.Phạm Tuấn Khiêm 8 Ví dụ về RAG Hệ điều hành - GV.Phạm Tuấn Khiêm 9 RAG có tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 10 RAG có vòng nhưng không có tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 11 Suy luận cơ bản Nếu đồ thị không chứa vòng không tắc nghẽn Nếu đồ thị chứa vòng ◦ Nếu tài nguyên chỉ có 1 thực thể, thì tắc nghẽn ◦ Nếu tài nguyên có nhiều thực thể, có khả năng tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 12 Các phương pháp xử lý tắc nghẽn Đảm bảo hệ thống sẽ không bao giờ rơi vào trạng thái tắc nghẽn: ◦ Ngăn chặn tắc nghẽn ◦ Tránh tắc nghẽn Cho phép hệ thống rơi vào trạng thái tắc nghẽn, sau đó khôi phục Bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn. Được sử dụng bởi hầu hết các hệ điều hành, bao gồm cả UNIX Hệ điều hành - GV.Phạm Tuấn Khiêm 13 Ngăn chặn tắc nghẽn Ngăn chặn 4 điều kiện làm xuất hiện tắc nghẽn ◦ Độc quyền truy xuất – không được yêu cầu đối với tài nguyên có thể chia sẻ (vd: các tập tin chỉ đọc), phải nắm giữ đối với tài nguyên không thể chia sẻ ◦ Giữ và đợi – phải đảm bảo rằng bất cứ khi nào tiến trình yêu cầu tài nguyên thì nó không được giữ bất kỳ tài nguyên nào khác Đòi hỏi tiến trình yêu cầu và được cấp phát tất cả tài nguyên trước khi nó bắt đầu thực thi, hoặc cho phép tiến trình yêu cầu tài nguyên chỉ khi tiến trình không có tài nguyên được cấp phát Việc sử dụng tài nguyên thấp, có thể đói tài nguyên Hệ điều hành - GV.Phạm Tuấn Khiêm 14 Ngăn chặn tắc nghẽn Không ưu tiên – ◦ Nếu một tiến trình đang giữ một số tài nguyên yêu cầu tài nguyên khác mà không được cấp phát ngay lập tức, thì tất cả tài nguyên hiện hành đang giữ được giải phóng ◦ Tài nguyên bị chiếm được thêm vào danh sách tài nguyên mà các tiến trình đang chờ ◦ Tiến trình sẽ được chạy lại chỉ khi nó chiếm lại tài nguyên cũ của nó, cũng như tài nguyên mới mà nó đang yêu cầu Hệ điều hành - GV.Phạm Tuấn Khiêm 15 Ngăn chặn tắc nghẽn Đợi vòng quanh – đặt tất cả các loại tài nguyên vào thứ tự, và đòi hỏi mỗi tiến trình yêu cầu tài nguyên theo thứ tự tăng dần Hệ điều hành - GV.Phạm Tuấn Khiêm 16 Tránh tắc nghẽn Yêu cầu hệ thống Mô hình đơn giản và hữu ích nhất là mỗi tiến trình sẽ khai báo số tài nguyên tối đa của mỗi loại mà tiến trình cần Các thuật toán tránh tắc nghẽn tự động kiểm tra trạng thái cấp phát tài nguyên để đảm bảo rằng không bao giờ xảy ra điều kiện đợi vòng quanh Trạng thái cấp phát tài nguyên được xác định bằng số tài nguyên khả dụng và được cấp phát, và nhu cầu tối đa của các tiến trình Hệ điều hành - GV.Phạm Tuấn Khiêm 19 Trạng thái an toàn Khi một tiến trình yêu cầu một tài nguyên có sẵn, hệ thống phải quyết định cấp phát ngay lập tức nếu hệ thống đang ở trạng thái an toàn Hệ thống là trạng thái an toàn nếu tồn tại một chuỗi tiến trình trong hệ thống mà mỗi Pi, tài nguyên mà Pi yêu cầu vẫn có thể được thỏa mãn bởi tài nguyên sẵn có hiện hành + tài nguyên được giữ bởi tất cả các Pj, với j Ở thời điểm T1, P2 yêu cầu thêm một ổ đĩa và được cấp phát, khi này hệ thống sẽ rơi vào trạng thái không an toàn. Lỗi là hệ thống đã cấp phát cho P2 thay vì buộc P2 phải đợi. Hệ điều hành - GV.Phạm Tuấn Khiêm 21 Suy luận cơ bản Nếu hệ thống ở trạng thái an toàn không có tắc nghẽn Nếu hệ thống ở trạng thái không an toàn có khả năng tắc nghẽn Tránh tắc nghẽn đảm bảo rằng hệ thống không bao giờ rơi vào trạng thái không an toàn Hệ điều hành - GV.Phạm Tuấn Khiêm 22 Trạng thái: an toàn, không an toàn, tắc nghẽn Hệ điều hành - GV.Phạm Tuấn Khiêm 23 Các giải thuật tránh tắc nghẽn Tài nguyên có một thực thể ◦ Sử dụng đồ thị cấp phát tài nguyên (RAG) Tài nguyên có nhiều thực thể ◦ Sử dụng giải thuật Banker Hệ điều hành - GV.Phạm Tuấn Khiêm 24 Phương án RAG Cạnh đòi hỏi (claim edge) Pi Rj là cạnh cho biết tiến trình Pi có thể yêu cầu tài nguyên Rj , nó được biểu diễn bằng 1 đường nét đứt. Cạnh đòi hỏi (claim edge) chuyển thành cạnh yêu cầu (request edge) khi một tiến trình yêu cầu tài nguyên. Cạnh yêu cầu được chuyển thành cạnh cấp phát (assignment edge) khi tài nguyên được cấp cho tiến trình. Khi tài nguyên được giải phóng bởi tiến trình, cạnh cấp phát chuyển lại thành cạnh đòi hỏi. Các tài nguyên phải được gán 1 độ ưu tiên trong hệ thống. Hệ điều hành - GV.Phạm Tuấn Khiêm 25 Phương án RAG Hệ điều hành - GV.Phạm Tuấn Khiêm 26 Trạng thái không an toàn trong RAG Hệ điều hành - GV.Phạm Tuấn Khiêm 27 Giải thuật RAG Giả sử tiến trình Pi yêu cầu tài nguyên Rj Yêu cầu được cấp phát chỉ khi việc chuyển từ cạnh yêu cầu thành cạnh cấp phát không tạo thành vòng trong đồ thị. Hệ điều hành - GV.Phạm Tuấn Khiêm 28 Giải thuật Banker Áp dụng cho tài nguyên có nhiều thực thể Mỗi tiến trình phải sử dụng độ ưu tiên cao nhất Khi một tiến trình yêu cầu tài nguyên, nó có thể phải chờ Khi một tiến trình có đầy đủ tài nguyên, nó phải trả lại chúng trong thời gian xác định Hệ điều hành - GV.Phạm Tuấn Khiêm 29 Cấu trúc dữ liệu của giải thuật Banker Gọi n là số tiến trình; m là số tài nguyên Available: vector với độ dài m, là số thực thể đang khả dụng (có sẵn). Nếu available[j]=k, có k thực thể của tài nguyên Rj là khả dụng. Max: ma trận nxm, số thực thể tối đa mà tiến trình yêu cầu. Nếu Max[i,j]=k, thì tiến trình Pi có thể yêu cầu nhiều nhất k thực thể của tài nguyên Rj Allocation: ma trận nxm, số thực thể của tài nguyên đã cấp phát cho tiến trình. Nếu Allocation[i,j]=k, thì hiện hành tiến trình Pi được cấp phát k thực thể của tài nguyên Rj Need: ma trận nxm, số thực thể tiến trình cần để hoàn thành tác vụ. Nếu Need[i,j]=k, thì tiến trình Pi cần thêm k thực thể của Rj để hoàn thành tác vụ Need[i,j]=Max[i,j]-Allocation[i,j] Hệ điều hành - GV.Phạm Tuấn Khiêm 30 Giải thuật xác định trạng thái an toàn 1. Gọi Work và Finish là 2 vector với độ dài tương ứng là m và n. Khởi tạo: Work = Available Finish [i] = false với i = 0, 1, …, n- 1 2. Tìm i thỏa 2 điều kiện: a) Finish[i]=false b) Needi Work Nếu không tồn tại i như vậy thì qua Bước 4 3. Work = Work + Allocationi Finish[i] = true Quay lại Bước 2 4. Nếu Finish [i] == true với tất cả i, thì hệ thống ở trạng thái an toàn Hệ điều hành - GV.Phạm Tuấn Khiêm 31 Giải thuật yêu cầu tài nguyên của tiến trình Pi Requesti – vector tài nguyên yêu cầu của tiến trình Pi. Nếu Requesti[j]=k thì tiến trình Pi muốn k thực thể của tài nguyên Rj 1. Nếu Requesti Needi tới Bước 2. Ngược lại, đưa ra lỗi vì tiến trình vượt quá đòi hỏi tối đa 2. Nếu Requesti Available tới Bước 3. Ngược lại, Pi phải chờ vì tài nguyên không có sẵn 3. Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật tình trạng hệ thống như sau: Available = Available – Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti; Nếu trạng thái là an toàn tài nguyên được cấp phát cho Pi Nếu trạng thái là không an toàn Pi phải chờ, và trạng thái cấp phát tài nguyên cũ được phục hồi Hệ điều hành - GV.Phạm Tuấn Khiêm 32 Ví dụ về giải thuật Banker 5 tiến trình: P0 đến P4 3 loại tài nguyên: ◦ A (10 thực thể); B (5 thực thể) và C (7 thực thể) Hiện trạng tại thời điểm T0: Allocation Max Available ABC ABC ABC P0 0 1 0 753 332 P1 2 0 0 322 P2 3 0 2 902 P3 2 1 1 222 P4 0 0 2 433 Hệ điều hành - GV.Phạm Tuấn Khiêm 33 Ví dụ về giải thuật Banker Ma trận Need được xác định bởi Max – Allocation Need ABC P0 743 P1 122 P2 600 P3 011 P4 431 Hệ thống ở trạng thái an toàn vì chuỗi thỏa mãn điều kiện an toàn Hệ điều hành - GV.Phạm Tuấn Khiêm 34 Ví dụ về giải thuật Banker: P1 yêu cầu (1,0,2) Kiểm tra Request1 Available ((1,0,2) (3,3,2) đúng) Allocation Need Available ABC
