TỔNG QUAN VỀ HỆ ĐIỀU HÀNH
Môn học Hệ điều hành
• II Các thành phần cơ bản một hệ thống máy tính
• III Tổng quan về Hệ điều hành
I.Môn học Hệ điều hành
1-Introduction + Computer System Structures (Giới thiệu + Cấu trúc hệ thống máy tính)
2-Operating System Structures (Cấu trúc hệ điều hành)
3-Processes + Processes Managements (Quy trình + Quản lý quy trình)
(Quy trình Lập lịch biểu S-Processes Đồng bộ hóa)
7-Memory + Memory Management (Bộ nhớ + Quản lý bộ nhớ)
8-I0 System + File System + Secondary Memory (Hệ thống IO+ Hệ thống tệp +
Các thành phần của một hệ thống máy tính
a Các thành phần của một hệ thống máy tính
Tổng quan về Hệ điều hành
I.Môn học Hệ điều hành
1-Introduction + Computer System Structures (Giới thiệu + Cấu trúc hệ thống máy tính)
2-Operating System Structures (Cấu trúc hệ điều hành)
3-Processes + Processes Managements (Quy trình + Quản lý quy trình)
(Quy trình Lập lịch biểu S-Processes Đồng bộ hóa)
7-Memory + Memory Management (Bộ nhớ + Quản lý bộ nhớ)
8-I0 System + File System + Secondary Memory (Hệ thống IO+ Hệ thống tệp +
II Các thành phần của một hệ thống máy tính a Các thành phần của một hệ thống máy tính b Các thành phần của một hệ thống máy tính
1.Hardware-Cung cấp tàp nguyên máy tính cơ bản (CPU, memory, I/0 devices)
2.Operating system - Đều khiến, và phối hợp giữa người dùng và phần cứng nhằm thực thi các chương trình ứng dụng cho nhiều đối tượng người dùng khác nhau
3 Applications programs - Định nghĩa cách các tài nguyên hệ thống đƣợc sử dụng cho việc giải quyết yêu cầu của người dùng (compilers, games, business programs)
4 Users (4 Người dùng máy tính) - hệ thống cơ sở dữ liệu, video (người, máy móc, khác)
III Tổng quan về Hệ điều hành
1 Khái niệm Hệ điều hành
• Là chương trình đóng vai trò trung gian giữa người sử dụng và phần cứng máy tính đó
- Thực thi chương trình người dùng và giải quyết các vấn đề của người dùng dễ dàng hơn
- Tăng cường hiệu quả sử dụng hệ thống máy tính
•Sử dụng phần cứng máy tính một cách hiệu quả và tối ƣu
2.Chức năng: Môi trường người dùng a,• Môi trường người dùng- Lớp HĐH (OS) giúp lớp trên kể thừa và sử dụng hiệu quả phần cứng máy tính
+) Môi trường thực thi - Quản lý tiến trình (process management), quản lý file, điều khiển ngắt , vận hènh xuất / nhập, chức năng ngôn ngữ
+)Bảo vệ và bảo mật
+) Kiểm soát lỗi và phục hồi sau lỗi b, Chức năng: Quản lý tài nguyên
-Quản lý thời gian: Định thời biểu sử dụng CPU và các công kết nối
- Quản lý không gian: Cấp phát bộ nhớ chính và bộ nhớ
-Đồng bộ và kiểm soát bể tắc: IPC, critical section, coordination
-Tài khoản và Thông tin và trạng thái: Theo dõi hiệu năng sử dụng tài nguyên
1 Lƣợc sử và phân loại hệ điều hành a, Hệ điều hành đơn chương trình
• Đặc điểm Hệ điều hành đơn chương trình:
- Toàn bộ hệ thống máy tính phục vụ 1 chương trình: Từ lúc bắt đậu khi chương trinh được đưa vào bộ nhớ đến khi kết thúc chương trinh
Khi một chương trình được nạp vào bộ nhớ và thực hiện, nó sẽ chiếm giữ tất cả tài nguyên hệ thống, dẫn đến việc không thể nạp chương trình khác vào bộ nhớ Hệ điều hành đa chương trình cho phép nhiều chương trình cùng tồn tại trong bộ nhớ, tối ưu hóa việc sử dụng tài nguyên và nâng cao hiệu suất hệ thống.
-Tại một thời điểm có nhiều chương trình có mặt đông thời trong bộ nhớ
- Các chương trình đều có nhu cầu được phân phối bộ nhớ và CPU b.2 •Phân loại Hệ điều hành đa chương trình
1) Hệ điều hành hoạt động theo mẻ (theo lô)
+ Hệ điều hành hoạt động theo lô: Hướng tới mục tiêu cực đại số lượng bài toán đƣợc giải quyết trong một đơn vị thời gian
Có 2 loại: MFT và MVT
+>MFT (Multiprogramming with Fixed number of Task-Đa chương trình với số lƣợng tác vụ cố định):
_Quy định sẵn số tiến trình có mặt đồng thời trong bộ nhớ
_Bộ nhớ đƣợc chia sẵn thành các phân vùng (Partition) mỗi phân vùng chỉ chứa một tiến trình
+>MVT (Multiprogramming with Variable number of Task):
_Bộ nhớ không đƣợc phân chia sẵn
_Tiến trình đƣợc nạp liên tục khi còn đù bộ nhớ
_Số lƣợng tiến trình đồng thời trong bộ nhớ luôn thay đối tùy thuộc vào dung lƣợng
2) Hệ điều hành chia sẻ thời gian
Hệ điều hành chia sẻ thời gian cho phép nhiều người dùng cùng làm việc trên máy tính thông qua các trạm đầu cuối, với CPU được phân phối lân lượt cho từng chương trình, đảm bảo mỗi chương trình chiếm giữ CPU trong một khoảng thời gian nhất định gọi là thời gian lượng tử Bộ nhớ luôn chứa chương trình của tất cả người dùng Hệ điều hành thời gian thực đảm bảo giải quyết các tiến trình đúng hạn, với mỗi tiến trình được gán một thời gian hoàn thành cụ thể, gọi là DeadTime, và việc hoàn thành muộn hơn không còn ý nghĩa, như trong các ứng dụng của lò phản ứng hạt nhân hay game thời gian thực Hệ thống song song cho phép nhiều CPU chia sẻ tài nguyên như đường truyền, bộ nhớ và thiết bị I/O, với các CPU làm việc phụ thuộc lẫn nhau do việc chia sẻ tài nguyên này.
Nhanh hơn, an toàn hơn (Một CPU hỏng không ảnh hưởng tới toàn bộ hệ thống) e, Hệ phân tán
Tập hợp các thiết bị, hệ thống độc lập, nhƣng giao tiếp đƣợc với nhau
2 Thành phần của Hệ điều hành
4.1.Thành phần Điều phối hoạt động
1) Các chương trình được chia thành nhiều tiến trình để thực thi
2) HĐH chịu trách nhiệm đoi với việc quản lý tiến trình: i Tạo và Xoá tiến trình ii Tạm ngừng và tiếp tục thực thi tiễn trình iii Cung cấp cơ chế cho: o Đồng bộ hoá tiến trình o Giao tiếp liên tiến trình
4.2 Thành phần Phân phối tài nguyên
4.2.1 Quản lý bộ nhớ chính (Main Memory Management):
- Quyết định xem những tiến trình nào đƣoc nạp khi có bộ nhớ trống
- Lưu lại dấu vết của các phần bộ nho dang được sử dụng và đuợc sử dụng bởi tiến trình nào
- Thu hồi bộ nhớ cho các tien trình khi thực thi xong
4.2.2.a Đặc điểm Hệ thống tập tin File System:
-Tập tin là tập hợp các thông tin liên quan đƣợc tổ chức một cách
- Tập tin được lưu trữ trên thiết bị nhớ phụ
-Thông thường, các tập tin đại diện cho dữ liệu và các chương trình (cả source- nguồn, data- dữ liệu và object forms- các biểu mẫu đối tƣợng)
- Tổ chức file (Tạo và xoá thƣ mục)
- Hỗ trợ từ gốc (primitive) đối với việc thao tác với các file và thƣ mục
-Ánh xạ các file vào bộ nhớ thứ cấp
-Backup file trên các phương tiện lưu trữ ốn định
4.2.3.a Đặc điểm Hệ thống xuất/nhập (vào/ra)
- Một thành phần quán lý bộ nhớ
- Một giao diện device-driver chung
- Các driver cho các thiết bị phần cứng riêng biệt
- Chi device driver biết các tính chất đặc biệt của thiết bị mà nó điều khiển 4.2.3b Quản lý xuất/nhập (vào/ra) I/O System Management:
- HĐH phải ra các chỉ chị điều khiến thiế bị, kiếm soát các
- HĐH phải cung cấp một cách giao diếp đơn giản và tiện dụng giữa các thiết bị và phần còn lại của hệ 6ugu
-Giao tiếp này phải độc lập với thiết bị
4.2.4a Đặc điểm Bộ nhớ phụ
- Dữ liệu trên bộ nhớ chính (primary storage): i.Tạm thời, dung lƣợng nhỏ ii.Để lưu trữ lâu dài, dung lượng lớn -> sử dụng bộ nhớ thứ cấp
(secondary sforage) để back up bộ nhớ chính
Hầu hết các hệ thống máy tính hiện đại sử dụng ổ đĩa như là phương tiện lưu trữ trực tuyến chính cho cả chương trình và dữ liệu.
4.2.4b Quản lý bộ nhớ phụ
- Quản lý các vùng nhớ tự do
- Lập lịch ổ đĩa (Disk scheduling)
4.3.Thành phần của Hệ điều hành
- Thành phần Hoạt động mạng (Networking)
- Hệ thống bảo vệ (Protection System)
- Hệ thống thông dịch lệnh (Command-Interpreter System)
5.1 Khái niệm Nhân Hệ điều hành
- Hệ điều hành có dung lƣợng lớn => không thể đƣa tat cả vào bộ nhớ
- Các chương trình của hệ điều hành phân thành 2 loại:
+Nhân Hệ điều hành: gồm các chương trình luôn tồn tại trong bộ nho de diều khiến máy tính làm việc
+Các chương trình chi được nạp vào bộ nhớ khi cần thiết
5.2 Chức năng Nhân Hệ điều hành
Chức năng phân theo nhóm chương trình:
- Module chương trình tải (loạder): Đưa một chương trình vào bộ nhớ và cho phép chương trình đã tải nhận điều khiển hay không
- Module chương trình điều phối chính: Đảm nhận việc lựa chọn các bước làm việc của toàn bộ hệ thống
- Modyle chương trình lập lịch: Chọn tiến trìn làm việc tiếp theo
- Các thông tin về hệ thống (các tham số hệ thống)
6 Dịch vụ của Hệ điều hành
6 1 Thực hện chương trình (Program exeaudon)
- Nạp một chương trình vào bộ nhớ
- Thực thi chương trình đã nạp
6 2 Thực hiện vào-ra (I/0 operations)
- Chương trình của người sử dụng không thế thực hiện trực tiếp các hoạt động vào/ra
- Hệ điều hành phải cung cấp một số cơ chế để thực hiện vào/ra
6.3.Thao tác với hệ thống file (File-system manipulatiom)
Khả năng của chương trình để đọc, ghl, tạo, xoá các file
- Trao đổi thông tin giữa các tiến trình đang thực hiện trên cùng 1 máy tính hoặc trên các hệ thống khác nhau đƣợc nối mạng
- Việc thực hiện thông qua:
+Bộ nhớ chia sẻ (shared memory)
+Hoặc chuyển thông điệp (message passing)
6.5 Phát hiện lỗi (Error detection)
- Bảo đảm việc tính toán đúng đẳn bằng cách phát hiện các lỗi
Trong CPU và bộ nhớ, trong các thiết bị vào-ra, hoặc trong chương trình của người sử dụng
7 Lời gọi hệ thống(System Call)
7.1 Khái niệm Lời gọi hệ thống
System calls cung cấp giao diện giữa một tiến trình và Hệ điều hành
- Mụỗ đớch là yờu cầu sử dụng cỏc
- Thường là các cậu lệnh viết bằng ngôn ngữ assembly
- Các ngôn ngữ bậc cao (VD: C aşsembly de cho phép việc lập trinh hệ thống tạo trực tiếp các system call
7.2 Vai trò Lời gọi hệ thống
7.2.1 Điều khiển tiến trình (Process control)
- Nạp, thực hiện tiến trình
- Tạm dừng / Khởi tạo lại tiến trình
- Sử dụng/ thiết lập các thuộc tính của tiến trình
7.2.2 Quản lý file (File management)
- Lấy/ thiết lập thuộc tính file
7.2.3 Quận lý thiết bị (Device management)
- Yêu cầu thiết bi, giải phóng thiết bị
- Lấy/ thiết lập các thuộc tính thiết bị
- Gần kết (attack), tháo gỡ (detach) mức logic các thiết bị
7.2.4 Duy trì thông tin (Information maintenance)
- Yêu cầu/ Lấy/ thiết lập giờ hoặc ngày
- Lấy/ thiết lập dữ liệu hệ thống Lấy/ thiết lập thuộc tính của tiến trình, file, thiết bị
- Tạo, xóa kết nối giao tiếp
- Truyền lại thông tin trạng thái
- Gắn kết, tháo gỡ logic các thiết bị ở xa (remote device)
Sự giao tiếp có thể thực hiện bằng cách sử dụng phương thức: message passing hoặc shared memory
7.3 Phương thức giao tiếp Lời gọi hệ thống
CẤU TRÚC CỦA HỆ ĐIỀU HÀNH
Bài 2:Cấu trúc của hệ điều hành
1 Operating System Structure - Cấu trúc của HĐH
Hệ điều hành đa năng là chương trình rất lớn
Nhiều cách khác nhau để cấu trúc
- Cấu trúc đơn giản - MS-DOS
- Cấu trúc Phức tạp hơn - UNIX
- Cấu trúc Lớp - Một sự trừu tƣợng
- Cấu trúc vi nhân Microkernel – Mach
2 Simple Structure MS-DOS - Cấu trúc đơn giản MS-DOS
MS-DOS - đƣợc viết để cung cấp nhiều chức năng nhất trong ít không gian nhất
- Không chia thành các mô-đun
- Mặc dù MS-DOS có một số cấu trúc, nhƣng các giao diện và mức độ chức năng của nó không đƣợc tách biệt rõ ràng
3.Traditional UNIX System Structure - Cấu trúc hệ thống UNIX truyền thống
Hệ điều hành UNIX, mặc dù bị giới hạn bởi chức năng phần cứng, ban đầu có cấu trúc hạn chế UNIX bao gồm hai phần có thể tách rời, cho phép người dùng linh hoạt trong việc quản lý và sử dụng hệ thống.
- Systems programs - Chương trình hệ bugun
- Bao gồm mọi thứ bên dưới giao diện cuộc gọi hệ thống và bên trên phần cứng vật lý
Hệ điều hành cung cấp một hệ thống tệp, lập lịch CPU, quản lý bộ nhớ và nhiều chức năng khác, bao gồm một lượng lớn các chức năng cho mỗi cấp độ.
- Vƣợt ra ngoài đơn giản nhƣng không đây đủ các lớp
4.Layered Approach – Tiếp cận theo lớp
Hệ điều hành được tổ chức thành nhiều lớp, với mỗi lớp được xây dựng dựa trên các lớp thấp hơn Lớp thấp nhất, gọi là lớp 0, đại diện cho phần cứng, trong khi lớp cao nhất, lớp N, là giao diện người dùng.
- Với tính mô đun, các lớp đƣợc chọn sao cho mỗi lớp chi sử dụng các chức năng (hoạt động) và dịch vụ của các lớp cấp thấp hơn
3 Microkernel System Structure- Cấu trúc hệ thống vi nhân
- Di chuyển càng nhiều từ hạt nhân vào không gian người dùng
- Mach là ví dụ của vi nhân – microkernel: Mac Os X kernel (Darwin) một phần dựa trên Mach
- Giao tiếp diễn ra giữa các mô-đun người dùng bằng cách truyền thông điệp
+ Dễ dàng mở rộng kênh nhó hơn
+ Dễ dàng chuyển hệ điều hành kiến trúc mới hơn
+ Đáng tin cây hơn (it mã hơn đang chạy trong chế độ hạt nhân) +An toàn hơn
- Nhược điểm: Quá tài hiệu suất của không gian người dùng đối với giao tiếp không gian nhân
4 Solaris Modular Approach - Cách tiếp cận mô-đun của Solaris
- Nhiều hệ điều hành hiện đại triển khai các mô-đun nhân có thể tải đƣợc + Sử dụng cách tiếp cận hướng đối
+ Mỗi thành phần cốt lõi là riêng biệt
+ Mỗi thành phần nói chuyện với thành phần khác qua các giao diện đã biết
+ Mỗi mô-đun đều có thể tải đƣợc khi cần trong nhân
- Nhìn chung, tương tự như các lớp nhưng lĩnh hoạt hơn: Linux, Solaris, v.v
5 Mac OS X Structure - Cấu trúc HĐH MAC X
- Hầu hết các hệ điều hành hiện đại thực sự không phải là một mô hình thuần túy
Hybrid kết hợp nhiều cách tiếp cận để giải quyết các nhu cầu về hiệu suất, bảo mật, khả năng sử dụng
Hạt nhân Linux và Solaris trong không gian địa chỉ hạt nhân, rất nguyên khối, cộng với mô-đun để tải động các chức năng
Windows chủ yếu được thiết kế theo dạng nguyên khối, kết hợp với microkernel để hỗ trợ các tính năng của hệ thống con khác nhau Trong khi đó, Apple Mac OS X sử dụng kiến trúc lai, với giao diện người dùng Aqua UI và môi trường lập trình Cocoa, tạo nên trải nghiệm đa lớp và phong phú cho người dùng.
Phía trên là nhân hệ thống, bao gồm các phần như Mach microkernel và BSD Unix, cùng với bộ I/O và các mô-đun có thể tải động, được gọi là phần mở rộng nhân.
- Hệ điều hành di động của Apple dành cho iPhone, iPad
+ Đƣợc cấu trúc trên Mac OS X, thêm chức năng
+ Không chạy các ứng dụng OS X nguyên bản: Cũng chạy trên kiến trúc CPU khác nhau (ARM so với Intel)
+ Cocoa Touch Objective-C API đề phát triển
+ Lớp dịch vụ phương tiện cho đô họa, âm thanh, video
+ Các dịch vụ cốt lõi cung cấp điện toán đám mây, cơ sở dữ liệu + Hệ điều hành cốt lõi, dựa trên nhân Mac OS X
7 Android Architecture - Kiến trúc Android
- Đƣợc phát triển bởi Open Handset Allance (chủ yếu là Google) : Open Source
- Ngăn xếp tương tự với ios
- Dựa trên nhân Linux nhƣng đã đƣợc sửa đối:
+ Cung cấp quy trình, bộ nhớ, quán lý trình điều khiến thiết bị
+ Thêm quản lý ngƣồn điện
-Môi trường thời glan chạy bao gồm bộ thư viện cốt lõi và máy ảo Dalvik Các ứng dụng đƣợc phát triển bắng Java và API Androld
+ Các tệp lớp Java đƣợc biên dịch sang mã bytecode của Java sau đó đƣợc dịch sang tệp thực thi hơn là chạy trong máy ảo Dalvik
+ Thƣ viện bao gồm các khuôn khố cho trình duyệt web (webkit), cơ sở dữ liệu (SQLite), đa phương tiện, libc nhỏ hơn
8 Operating-System Debugging - Gỡ lỗi HĐH
- Gỡ lỗi là tìm và sửa lỗi
- Hệ điều hành tạo các tệp nhật ký chứa thông tin lỗi
- Lỗi của một ứng dụng có thể tạo ra bộ nhớ lưu tệp kết xuất lõi của quá trình
- Lỗi hệ điều hành có thể tạo ra tệp kết xuất sự cố chứa bộ nhớ hạt nhân
Ngoài việc xử lý sự cố, việc điều chỉnh hiệu suất có thể giúp tối ưu hóa hiệu suất hệ thống Để đạt được điều này, việc sử dụng danh sách theo dõi các hoạt động và ghi lại chúng để phân tích là rất quan trọng.
+ Lập hồ sơ là lấy mẫu định kỳ con trò hướng dẫn để tìm kiếm các xu hướng thống kê
9 Performance Tuning - Điều chỉnh hiệu suất
- Cải thiện hiệu suất bằng cách loại bỏ cổ chai
- OS phải cung cấp các phương tiện tính toán và hiến thị các biện pháp về hoạt động của hệ thống
- Ví dụ: chương trình "hàng đâu" hoặc Trình quản lý tác vụ Windows
11 Performance Tuning - Điều chỉnh hiệu suất - DTrace Solaris
12 Operating-System Generation - Các thế hệ của Hệ điều hành
Khi hệ thống được khởi động, quá trình thực thi bắt đầu từ một vị trí bộ nhớ cố định, trong đó Firmware ROM giữ vai trò lưu trữ mã khởi động ban đầu.
- Hệ điều hành phải đƣợc cung cấp cho phần cứng để phần cứng có thể khởi động nó
+ Đoạn mã nhỏ- bootstrap loader, được lưu trữ trong ROM hoặc EEPROM định vị hạt nhân, tải nó vào bộ nhớ khởi động nó
+ Đôi khi quy trình hai bước trong đó boot block tại vị trí cố định đƣợc tải bởi mã ROM, nơi tải bộ tải boostrap từ đĩa
- Bộ tải bootstrap chung, GRUB, cho phép lựa chọn nhân từ nhiều đĩa, phiên bán, tùy chọn nhân
- Kermel – Nhân tải và hệ thống sau đó thực hiện
TIẾN TRÌNH VÀ LUỒNG
Tiến trình (Processes)
- Thực hiện công việc được mô tả thông quả các chương trình
+ Yêu cầu để tiến trình thực hiện
+ Đƣợc cụng cấp đây đủ tài nguyên cần thiết (oyu ga)
+ Đƣợc CPU tiếp nhận & thực hiện
+ Điều phối hoạt động các tiến trình
+ Phân phôi tài nguyên cần thiết cho tiến trình (Memory, Ið device )
+ Mã nguồn chương trình (code) (không thay đổi)
+ Bộ đếm Chương trình (Program Counter)
+ Giá trị ở các thanh ghi (Register values)
2.Các trạng thái tiến trình
- Tiến trình có một trong các trạng thái:
+ New (Tạo mới): Tiến trình đang đƣợc tạo
Chạy (Running) là trạng thái của tiến trình khi nó đang chiếm hữu CPU và thực hiện các lệnh Trong khi đó, Chờ (Waiting) là khi tiến trình đang chờ nhận tài nguyên hoặc chờ một sự kiện xảy ra để có thể chuyển sang trạng thái sẵn sàng.
+ Tiến trình ở trạng thái sẵn sàng
+ Đƣợc phân phổi đủ tài nguyên cần thiết
+ Đang chờ đến lƣợt đƣợc thực hiện theo cơ chế lập lịch của hệ điều hẳnh
+ Nó không biến mất cho đến khi một tiến trình khác đọc đƣợc trạng thái thoát của nó
- Trạng thái của tiến trình
+ Xác định bởi hoạt động của tiến trình tại thời điểm
+ Tiến trình có thể thay đổi trạng thái
+ Nguyên nhân: o Dừng hoạt động do hết thời gian o Đợi một thao tác I/O hoàn tất o Chờ một sự kiện xảy ra
3.Các hoạt động trên tiến trình
- Quá trình chuyển trạng thái
Chỉ có một tiến trình ở trạng thái running
Nhiều tiến trình có thế ở trạng thái walting hay ready
Đƣợc đƣa vào hệ thống
Đƣợc cung cấp đủ tài nguyên
(chờ đƣợc phân phối CPU để thực hiện )
- Khi tiến trình đang thực hiện (running)
-) Nó có thể chuyển sang trạng thái:
Kết thúc(terminate): nếu thực hiện xong
+) Tiến trình yêu câu một tài nguyên
Chƣa đƣợc đáp ứng tại thởi điểm yêu cầu
Vì tài nguyên chƣa sẵn sàng cấp phát +)Hoặc tiến trình phải chờ
- Khi tiến trình đang thực hiện (running)
Nó có thể chuyển sang trạng thái:
+ Khi xảy ra ngắt o Chuyến cho tiến trình có mức ƣu tên cao hơn o Hết thời glan chiếm hữu CPU
+ Tài nguyên mà tiến trình yêu câu trở nên sẵn sàng
+ Hay sự kiện/thao tác I/0 tiến trình đang đợi hoàn tất
+ -> Bộ điêu phối chọn một tiến trình ready để thực thi
4 Khối điều khiển tiến trình Process Control Block (PCB)
- Là vùng nhớ o Lưu trữ các thông tin o Mô tả cho tiến trình
- Mỗi tiến trình có một PCB
1.Định danh tiến trình o Pid-Process Id o Để phân biệt các processes
2 Trạng thái tiến trình Process state: Xác định trạng thái hiện thời
3 Ngữ cảnh tiến trình: Mô tả các tài nguyên liên quan đến tiến trình Hiện có hoặc đang đợi phân bổ
Trạng thái CPU: Con trỏ lệnh, CPU registers; Được lưu trữ để phục hồi sau ngắt
Thông tin lịch trình CPU: CPU scheduling information
Thông tin quản lý bộ nhớ: Danh sách khôi nhớ đang cấp cho tiến trình
Tài nguyên sử dụng: Danh sách tài nguyên tiến trình đang sử dụng
Tài nguyên tạo lập: Danh sách các tài nguyên mà tiến trình yêu cầu
-Phản ánh quan giữa tiến trình này với các tiến trình khác trong cùng hệ thống 5 Thông tin thống kê: Thông tin về hoạt động tiến trình
5 CPU chuyển giữa các tiến trình
+ Căn cứ vào nội dung của PCB: o Phân phối và phân phối lại CPU o Giải phóng CPU ảo mà không phân phối lại
-Trong chế độ đa chương trình
+ User mode: Nhiều chương trình thực hiện đông thời
CPU chi phục vụ một chương trình tại một thời điểm(CPU thực)
Các chương trình còn lại sử dụng CPU ảo o Là CPU logic đƣợc phân phối cho toàn bộ tiến trình o CPU ảo tốc độ > Tính toán o Chiếm dụng CPU ngắn o Cân chuyển ngữ cảnh thường xuyên
Tiến trình CPU-bound là loại tiến trình chủ yếu tập trung vào việc xử lý tính toán hơn là thao tác I/O, dẫn đến việc sử dụng CPU kéo dài Để đảm bảo hiệu suất tối ưu, cần thực hiện chuyển ngữ cảnh thường xuyên nhằm tránh tình trạng một tiến trình chiếm dụng CPU quá lâu, gây cản trở cho các tiến trình khác trong việc sử dụng tài nguyên CPU.
- Tiến trình tương tác hay xử lý theo lô: Các tiến trình chiếm dụng CPU trong khoảng thời gian nhƣ nhau gọi là lƣợng tử thời gian (quantum)
- Độ ƣu tiên của tiến trình: Các tiến trình đƣợc phân cấp theo một số tiêu chuẩn đánh giá
Thời gian sử dụng CPU của tiến trình là yếu tố quan trọng để xác định thời gian còn lại mà tiến trình cần CPU Thông tin này giúp trong việc tối ưu hóa quá trình điều phối CPU và lập lịch hiệu quả hơn.
Thời gian còn lại để hoàn tất tiến trình là yếu tố quyết định trong việc phân phối CPU, ưu tiên cho các tiến trình cần ít thời gian thực hiện nhất Điều này giúp giảm thiểu thời gian chờ đợi trung bình cho các tiến trình, tối ưu hóa hiệu suất xử lý.
7 Lập lịch tiến trình (Process Scheduling)
- Mục tiêu multiprogramming: o Có nhiều tiến trình cùng chạy tạl mọi thời điểm o TốI đa hóa sử dụng CPU
Mục tiêu của time-sharing là tối ưu hóa việc chuyển giao CPU giữa các tiến trình, thực hiện càng thường xuyên càng tốt Điều này cho phép người sử dụng có thể tương tác với mỗi chương trình trong khi nó đang chạy, mang lại trải nghiệm mượt mà và hiệu quả hơn.
- Nguyên tắc chung: o Chọn 1 tiến trình trong hàng đợi o Trạng thái ready o Có độ ƣu tiên cao nhất o Các yếu tố llên quan đến đo ƣu tiên:
Thời điểm tạo tiến trình
Thời gian đã dành để phục vụ
Thời gian trung bình tiến trình chƣa đƣợc phục vụ o Tiêu chuẩn lựa chọn phương pháp điều phốI CPU: Xem xét thời gian chờ đợi xử lý
- Các PCB: Thường liên kết với một số hàng đợi để điều phối CPU quyết định tiến trình nào sẽ đƣợc sử dụng CPU
Máy tính đơn CPU chỉ có khả năng chạy một tiến trình tại một thời điểm Khi có nhiều tiến trình cùng tồn tại, chúng phải chờ đến khi CPU rảnh rỗi để được phân phối lại và xử lý.
8 Danh sách lập lịch tiến trình (Scheduling Queues)
- Sử dụng 2 loại danh sách để điều phối các tiến trình:
+ Danh sách sẵn sàng (ready list)
+ Danh sách đợi (waiting list)
9 Các trình lập lịch - Schedulers
Lập lịch dài kỳ, hay còn gọi là lập lịch công việc, là một quá trình quan trọng trong hệ thống quản lý tiến trình Nhiệm vụ chính của nó là chọn lựa các tiến trình cần được đưa từ ổ đĩa vào danh sách sẵn sàng (ready list) Mặc dù không thường xuyên xảy ra, thường là trong khoảng thời gian vài giây đến vài phút, lập lịch dài kỳ có thể diễn ra chậm Quá trình này cũng đóng vai trò trong việc kiểm soát mức độ đa chương trình (degree of multiprogramming) của hệ thống.
Lập lịch ngắn kỳ, hay còn gọi là lập lịch CPU, là quá trình quan trọng trong việc điều phối CPU Nhiệm vụ chính của nó là lựa chọn tiến trình nào sẽ được thực hiện tiếp theo và phân phối CPU cho tiến trình đó Lập lịch này diễn ra rất thường xuyên, trong khoảng thời gian milliseconds, vì vậy yêu cầu về tốc độ thực hiện là rất cao.
- Medium-term scheduler (Lập lịch trung kỳ) o Có thể được thêm vào nếu mức độ nhiều chương trình cần giảm
• Xóa tiến trình khỏi bộ nhớ, lựu trữ trên đĩa, đƣa trở lại từ đĩa để tiếp tục thực hiện: swapping
10 Các hoạt động trên tiến trình
Cấp các thao tác chủ yếu sau đây trên một tiến trình
- Tạo lập tiến trình (create or new)
- Kết thúc tiến trình (destroy or terminal)
- Tạm dừng tiến trình (suspend)
- Tái kích hoạt tiến trình (resume)
- Thay đổi độ ƣu tiên tiến trình
11 Sự tạo tiến trình - Process Creation
- Tiến trình o Tạo lập ra nhiều tiến trình mới bằng cách sử dụng lời gọi hệ thống tương ứng: Tạo lập: Tiến trình cha o Đƣợc tạo: Tiến trình con
- Tiến trình con: Đƣợc tạo ra các tiến trình mới Quá trình này tạo ra cây tiến trình
- Tạo tiến trình: Là một công việc "nặng nhọc" vì phải phân phối bộ nhớ và tài nguyên
Hệ điều hành thực hiện nhiều nhiệm vụ quan trọng khi tạo lập tiến trình, bao gồm việc định danh tiến trình, đưa vào danh sách quản lý của hệ thống, xác định độ ưu tiên, tạo PCB (Process Control Block) và cấp phát các tài nguyên ban đầu cần thiết cho tiến trình hoạt động hiệu quả.
- Các lựa chọn chia sẻ tài nguyên (resource sharing)
Tiến trình cha và con có ba cách chia sẻ tài nguyên: Thứ nhất, tiến trình con có thể chia sẻ tất cả tài nguyên từ tiến trình cha Thứ hai, tiến trình con chỉ chia sẻ một tập con các tài nguyên của tiến trình cha Cuối cùng, cũng có trường hợp không có sự chia sẻ tài nguyên nào giữa tiến trình cha và con.
- Không gian địa chỉ (Address space)
Tiến trình con là bản sao của tiến trình cha, thường xuất hiện trong các trường hợp gọi đệ quy, hoặc có thể là một chương trình độc lập được tải vào bộ nhớ khi gọi hàm con Cả tiến trình cha và tiến trình con đều thực hiện đồng thời, với tiến trình con phụ thuộc vào tiến trình cha trong quá trình thực thi.
- Không gian địa chỉ o Bản sao con của cha o Con có một chương trình được tải vào nó
Lệnh gọi hệ thống fork () tạo tiến trình mới
Lệnh gọi hệ thống thực thi () đƣợc sử dụng sau một fork () để thay thế không gian bộ nhớ của tiến trình bằng một lệnh mới chương trình
B Sự kết thúc tiến trình- Process Termination
- Kết thúc tiến trình o Khi nó hoàn tất chỉ thị cuối cùng o Sử dụng một lời gọi hệ thống để yêu cầu HĐH hủy bỏ
Qua lệnh wait: o Dữ liệu ra từ tiến trình con o Đến tiến trình cha
Có thể chấm dứt việc thực hiện tiến trình con (abort):
Nếu tiến trình con o Dùng quá tài nguyên đƣợc phân o Nhiệm vụ thực hiện không còn cần thiết
-Khi tiến trình kết thúc:
Hệ điều hành thực hiện các nhiệm vụ quan trọng như thu hồi tài nguyên hệ thống đã cấp phát cho tiến trình, hủy bỏ tiến trình khỏi tất cả các danh sách quản lý của hệ thống, xóa bỏ PCB của tiến trình, và phân phối lại các tài nguyên cho các tiến trình khác.
-Hầu hết các hệ điều hành o Nếu tiến trình cha đã kết thúc o Không cho phép các tiến trình con tiếp tục tồn tại
12.Các tiến trình hợp tác (Interprocess Communication)
- Tiến trình độc lập (Independent process):
• Không chịu tác động Bởi sự thực hiện của tiến trình khác
-Tiến trình hợp tác (Cooperating process):
Chịu tác động bởi sự thực hiện của tiến trình khác
Ví dụ: Tiến trình này chia sẻ dữ liệu với tiến trình khác
Tiến trình sản xuất (producer process)
Tạo ra các thông tin
Để tiến trình tiêu thụ (consumer process) —>Sử dụng
Chia sẻ thông tin- Information sharing
Tăng tốc độ tính toán -Computation speed-up
13 Liên lạc (giao tiếp) tiến trình (Communication)
Sở hữu một không gian địa chỉ riêng biệt,
Các tiến trình, không thể liên lạc trực tiếp dể dàng
Phải nhờ vào các cơ chế do HĐH cung cấp
Cơ chế liên lạc: o Khác nhau cho các HĐH khác nhau o Mỗi cơ chế có những đặc tính riêng o Thích hợp trong một hoàn cảnh chuyên biệt
- Các cơ chế liên lạc:
Trao đổi thông điệp (Message) Sockets
Tìm giải pháp cho các vấn đề chính yếu:
+ Liên lạc tường minh hay têm ẩn o (explicit naming/implicit naming) o Tiến trình phải biết tiến trình khác liên quan với nó:
- Liên lạc theo chế độ đông bộ hay không đông bộ o (blocking / non-blocking) o Khi một tiến trình trao đổi thông tin với một tiến trình khác
• Phái đợi cho thao tác liên lạc hoàn tất
•Tiếp tục các xử lý khác=>đông bộ
- Liên lạc giữa các tiến trình: o Hệ thống tập trung o Hệ thống phân tán
+ Là một cơ chế phần mềm
+ Tương tự như các ngắt cứng
+ Tác động đến các tiến trình
- Mục đích: Thông báo cho tiến trình về một sự klện
- Phân loại: Mỗi một tín hiệu có một ý nghĩa tương ứng với một sự kiện đặc trƣng
• Ex: o End Task trong windows o Close all on the taskbar of windows
- Nhận xét: Tính chất Liên lạc bằng tín hiệu: o Không đồng bộ, o Tiến trình:
• Xác định trƣác thời điểm nhận tín hiệu
• KIểm tra được sự kiện tương ứng với tín hiệu có thật sự xây ra?
Chỉ có thể Thông báo cho nhau về một blến cổ nào đó -> Không trao đối dữ liệu theo cơ chế này đƣợc
+ Sở hữu một bảng biểu diễn các tín hiệu khác nhau
+ Tín hiệu: Tương ứng một trình xử lý tín hiệu (signal handler);Quy định các xử lý của tiến trình khi nhận được tín hiệu tương ứng
Các tín hiệu được gửi đi từ nhiều nguồn khác nhau, bao gồm phần cứng như lỗi trong các phép tính số học, hệ điều hành thông báo cho một tiến trình khi có thiết bị I/O sẵn sàng, một tiến trình gửi yêu cầu đến tiến trình khác như khi tiến trình cha yêu cầu tiến trình con kết thúc, và từ người dùng thông qua các phím tắt như Ctrl-F4 để ngừng xử lý của tiến trình.
-Cách xử lý khi tiến trình nhận một tín
• Xử lý theo kiểu mặc định;
• Tiếp nhận và xử lý theo cách đặc biệt của tiến trình
Pipe: Là một kênh liên lạc giữa hai tiến trình Trực tiếp Một chiều o Dữ liệu:
Xuất của tiến trình này -> nhập cho tiến trình kia
Dạng một dòng các byte o Thiết lập giữa hai tiến trình:
Một tiến trình sẽ ghi dữ liệu -> pipe
Tiến trình sẽ đọc dữ liệu từ pipe theo thứ tự FIFO, đảm bảo tính bảo toàn Kích thước dữ liệu truyền qua pipe thường bị giới hạn ở mức 4096 ký tự Mỗi tiến trình chỉ có thể sử dụng một pipe mà nó tạo ra hoặc kế thừa từ tiến trình cha.
Cung cấp các lời gọi hệ thống read/write cho các tiến trình, cho phép thực hiện thao tác đọc và ghi dữ liệu trong pipe Đồng thời, đảm bảo việc đồng bộ hóa khi truy xuất pipe để tránh xung đột dữ liệu.
Bị khóa nếu pipe trống Đợi đến khi pipe có dữ liệu để truy xuất
Tiến trình ghi pipe sẽ bị khóa nếu pipe đây; Đợi đến khi pipe có chỗ trống để chứa dữ liệu o Cơ chế liên lạc:
Liên lạc một chiều (unidirectional):
Một tiến trình kết nối với một pipe: Đọc hoặc ghi
Truyền dữ liệu với cách thức không cấu trúc
Chỉ cho phép kết nối hai tiến trình: Có quan hệ cha-con trên cùng một máy tính o Cơ chế liên lạc:
Một số hệ điều hành
• Cho phép thiết lập hai pipe giữa một cặp tiến trình tạo liên lạc hai chiều
• Đặc điểm: Vẫn có nguy cơ xáy ra tình trạng khóa chết
Cá hai pipe nối kết hai tiến trình đêu đây(hoặc đều trống)
Cả hai tiến trình đều muốn ghi (hay đọc) dữ liệu vào pipe (mỗi tiến trình ghi dữ liệu vào một pipe)
Chúng sẽ cùng bị khóa và chờ lẫn nhau mãi!
16 Vùng nhớ chia sẻ (Shared memory)
• Đến một vùng nhớ chung: Vùng nhớ chia sẻ (shared memory)
• Không trao đối thông tin bằng cách
• Dữ liệu đƣợc đặt vào một vùng nhớ chung: Nhiều tiến trình có thể cùng truy - Vùng nhớ chia sẻ:
• Tồn tại độc lập với các tiến trình
• Tiến trình muốn truy xuất
Phải kết gắn vùng nhớ chung đó vào không gian địa chỉ riêng của tiến trình
Thao tác trên đó nhƣ một vùng nhớ riêng của mình
• Tốc độ: Là nhanh nhất để trao đổi dữ liệu giữa các tiến trình
•Khó khăn: Trong việc bảo đảm sự toàn vẹn dữ liệu: Dữ liệu đang truy cập có mới nhất? Nhiều tiến trình cùng truy cập bộ nhớ chung?
• Bảo vệ: Vùng nhớ chia sẻ bằng những cơ chế đồng bộ hóa thích hợp ->Không thể áp dụng trong các hệ phân tán
- Ý tưởng: Trao đổi các thông điệp thông qua Kenel
- Hệ điều hành: Cung cấp các hàm IPC chuẩn (InterProcess communication),
Cơ bản là hai hàm:
+ send (message) Kích thước của message cố định hoặc biến đổi
- Nhận xét: Đơn vị thông tin; Thông điệp; Có thể có cấu trúc
- Tiến trình P và Q muốn giao tiếp
+ Yêu cầu: Thiết lập một liên kết giao tiếp giữa chúng (communication link); Trao đối các message qua các hoạt động: Send receive; Kết thúc liên kết giao tiếp
+ Quy trình thực hiện: Liên kết giữa hai tiến trình; Cài đặt các theo tác send /receive
+ Cách thức liên lạc: Trực tiếp hay gián tiếp; Đồng bộ hoặc không đồng bộ
- Định nghĩa: Là một điểm cuối giao tiếp (endpoint for communication)
- Đƣợc xác định: Địa chỉ IP; Sổ hiệu cổng
- Ví dụ: Socket 161.25.19.8:1625 Có nghĩa Port 1625 Trên host 161.25.19.8
-Sự giao tiếp diễn ra giữa một cặp socket: Server socket đƣợc chọn Client socket đƣoc gán tự động
19.Phân phối tài nguyên cho tiến trình (Resource Allowcation)
LẬP LỊCH – SCHEDULING
Tiêu chuẩn định thời
- CPU utilization (tận dụng) - giữ cho CPU càng bận càng tốt (0- 100%)
• Throughput (thông lƣợng tối đa) - số tiến trình đƣợc hoàn thành trong một đơn vị thời gian
Thời gian quay vòng (turnaround time) là tổng thời gian cần thiết để hoàn thành một tiến trình Nó bao gồm thời gian chờ để tiến trình được đưa vào bộ nhớ, thời gian chờ trong hàng đợi sẵn sàng (ready queue), thời gian thực hiện bởi CPU, và thời gian thực hiện vào-ra.
- Waiting time - thời gian mà một tiến trình chờ đợi ở trong ready queue
Thời gian phản hồi là khoảng thời gian tính từ khi một yêu cầu được gửi đi cho đến khi nhận được câu trả lời đầu tiên, không phải là thời gian để đưa ra kết quả của câu trả lời đó Đây được coi là một tiêu chuẩn tốt trong việc đánh giá hiệu quả giao tiếp.
3.Các giải thuật lập lịch
3.1 Giải thuật First-Come, First-Served (FCFS)
Tiến trình nào yêu cầu CPU trước sẽ được phân phối CPU trước Giải thuật FCFS'là không đƣợc ƣu tiên
Là giải thuật đơn giản nhất
Process Burst Time (thời gian xử lý-thời gian sử dụrg CPU, ms)
• Giả định rằng các tiến trình đến theo thứ tự: P1, P2, P3 thì biểu đô Gantt (Gantt Chart) của lịch biểu nhƣ sau:
Thời gian chờ đợi của các tiến trình: P1 = 0; P2 = 24; P3 = 27
Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17
3.1 Giải thuật First-Come, First-Served (FCFS)
-Giả sử các tiến trình đến theo thứ tự P2, P3, P1
• Biểu đồ Gantt của lịch biểu nhƣ sau:
• Thời gian chờ đợi của các tiến trình: P1 = 6; P2 = 0; P3 = 3
• Thời gian chờ đợi trung binh: (6 +0 + 3)/3 = 3
• Tốt hơn nhiều so với trường hợp trước
• Convoy effect (hiệu ứng hộ tổng): tiến trình ngắn đứng sau tiến trình đài -> tăng thời gian đợi của các tiến trình
3.2 Giải thuật Shortest-Job-First (SJF) (1)
Ví dụ: SJF không ưu tiên trước
• Thời gian chờ đợi của các tiến trình: P1 = 0; P2 = 6; P3 = 3, P4 = 7
• Thời gian chờ đợi trung bình = (0 + 6 + 3 + 7)/4 = 4
3.2 Giải thuật Shortest-Job-First (SJF) (2)
• Thời gian chờ đợi trung bình (9 + 1+ 0 +2)/4 = 3
3.2 Giải thuật Shortest-Job-First (SJF) (3)
3.3a Xác định thời gian sử dụng CPU kế tiếp(1)
Không thể xác định chính xác thời gian sử dụng CPU tiếp theo của tiến trình, nhưng có thể ước lượng giá trị xấp xỉ dựa vào thời gian sử dụng CPU trước đó Công thức đệ quy được sử dụng để tính toán là: τn+1 = αtn + (1- α) τn.
• τ n+1 = giá trị dự đoán cho thời gian sử dụng CPU tiếp sau
• t n = thời gian thực tế của sự sử dụng CPU thứ n
• Thời gian thực tế sử dụng CPU gồn đõy khụng cú tỏc dụng gi cả
•Chỉ tính đến thời gian sử dụng CPU thực tế ngay trước đó
3.3b Giải thuật Thời gian ngắn nhất còn lại-Thời gian đầu tiên(SRTF)
• Bây giờ chúng ta thêm các khái niệm về thời gian đến khác nhau và ƣu tiên vào phân tích
• SRTF = Biểu đồ Gantt Dự phòng SJF
• Thời gian chờ trung bình = [(10-1) + (1-1) + (17-2) + 5-3)] / 4 = 26/4 = 6,5 mili giây
3.4 Lập lịch có ƣu tiên - Priority Scheduling (1)
• Mỗi tiến trình đƣợc gắn một số ƣu tiên (số nguyên) VD: 0-127
• CPU đƣợc phân phối cho tiến trình có mức ƣu tiên cao nhất (có số ƣu tiên nhỏ nhất) o Preemptive o Nonpreemptive
• SJF là trường hợp riêng của lập lịch có ưu tiên: mức ưu tiên chính là thời gian sử dụng CPU tiếp sau dự đoán đƣợc
• Vấn đệ: những tiến trình có mức ƣu tiên thấp có thể không bao giờ đƣợc thực hiện (starvation)
• Giải pháp = Aging: kỹ thuật tăng mức ƣu tiên của các tiến trình chờ đợi lầu trong hệ thống
• VD: Sau 1-15 phút giảm số ƣu tiên một lần
3.4 Lập lịch có ƣu tiên - Priority Scheduling (2)
• T/gian chờ đợi trung bình = (0 +1+ 6 + 16 + 18)/5 = 8.2
3.5 Giải thuật Round-Robin (RR) (1)
• Mỗi tiến trình, sử dụng một lƣợng nhỏ thời gian của CPU (time quantum - thời gian định lượng, q), thường là 10-100 mili giây (ms)
• Sau thời gian thực hiện q, tiến trình đƣa vào cuối của ready queue
Ready queue được tổ chức theo dạng FIFO (First-Come, First-Served) Khi một tiến trình có thời gian sử dụng CPU còn lại nhỏ hơn giá trị q, nó sẽ giải phóng CPU khi hoàn thành Sau khi tiến trình kết thúc, nó sẽ được loại bỏ khỏi ready queue và trình lập lịch sẽ chọn tiến trình tiếp theo trong hàng đợi này.
Nếu tiến trình còn thời gian sử dụng CPU lớn hơn g, bộ định thời sẽ đếm ngược q Khi q bằng 0, hệ điều hành sẽ bị ngắt và trình lập lịch sẽ lựa chọn tiến trình tiếp theo từ hàng đợi sẵn sàng Tiến trình hiện tại sẽ được chuyển xuống cuối hàng đợi sẵn sàng.
3.5 Giải thuật Round-Robin (RR) (2)
• Thông thường, quay vòng trung bình cao hơn SJF, nhưng phản hồi tốt hơn nên lớn so với thời gian chuyển đổi ngữ cảnh
• q thường là 10ms đến 100ms, chuyển đổi ngữ cảnh Thực hiện việc rút tiền o Giả sử P2 đƣợc phân phối đù thời gian sử dụng CPU,
Tiến trình P1 o Quay lại thực hiện nốt công việc (vì đã kiểm tra điều kiện từ lần trước)
Cập nhật account = -300 -> Tình huống lỗi
• Giải pháp: o Áp dụng cơ chế truy xuất độc quyền
Trên tài nguyên đó (account): Khi một tiến trình đang sử dụng tài nguyên, thì các tiến trình khác không đƣợc sử dụng
Vấn đề đồng bộ (5): Đoạn gang
- Critical session • (- critical region: đoạn găng, miền găng)
- Trong ví dụ trên: Tiến trình P1, P2 đều bao gồm chuỗi các lệnh riêng và các lệnh thực hiện rút tiền:
Vấn đề đồng bộ (6): Đoạn găng
- Khái niệm: Đoạn găng (miền găng) là đoạn mã lệnh có khả năng xảy ra mâu thuẫn, khi truy xuất tài nguyên chung
Để giải quyết vấn đề độc quyền truy cập quyết định, cần thiết lập các giải pháp đồng bộ hiệu quả Điều này đảm bảo rằng tiến trình nào sẽ được phép thực hiện lệnh trong miền găng, từ đó tối ưu hóa hiệu suất và tính ổn định của hệ thống.
Khi một tiến trình đang ở miền găng thì các tiến trình khác không thể vào miền găng
Vấn đề đồng bộ (7): Đoạn găng
Minh họa dòng thời gian của đoạn găng:
• Sử dụng các biến cờ hiệu(semaphore)
• Sử dụng việc kiểm tra luân phiên
- Giải pháp có sự hỗ trợ phần cứng:
3.1 Sử dụng các biến cờ hiệu (Semaphore) (1)
Cỏc tiến trỡnh chia sẻ một biến chung: Biến đúng vai trũ ô chốt cửa ằ (lock), biến này đƣợc khởi động là 0
Để một tiến trình vào miền găng, trước hết cần kiểm tra giá trị của biến lock Nếu lock bằng 0, tiến trình sẽ đặt lock thành 1 và tiến vào miền găng Ngược lại, nếu lock bằng 1, tiến trình phải chờ cho đến khi lock trở lại giá trị 0.
lock=0 không có tiến trình nào đang ở trong miền găng
lock=1 hiện có một tiến trình đang ở trong miền găng
3.1 Sử dụng các biến cờ hiệu (Semaphore) (1)
3.1 Sử dụng các biến cờ hiệu (Semaphore) (2)
Nhận xét: Giải pháp này vẫn xảy ra trường hợp
- 2 tiến trình cùng trong đoạn gắng khi:
• Thấy lock==0, đi vào đoạn, nhƣng chƣa kịp đặt lock=1 Vì hết thời gian sử dụng CPU
• Thấy lock==0, đi vào đoạn găng,
• Đặt lock=1, đang thực hiện các lệnh trong đoạn gắng, nhƣng chƣa xong vì hết thời gian CPU
- Tiến trình P1 tiếp tục đƣợc phân phối CPU và thực hiện các lệnh trong đoạn găng
- Khi đó P1, P2 cùng trong đoạn găng
3.2 Sử dụng việc kiểm tra luân phiên (1) Ý tưởng: Giải pháp đề nghị cho hai tiến trình:
- Hai tiến trình sử dụng chung biến turn
Tiến trình P1 đƣợc vào đoạn găng, khi tiến trình P1 rời khỏi đoạn găng
Nó đặt giá trị turn=1 để cho phép tiến trình P2 đi vào đoạn găng
Tiến trình P2 đƣợc vào đoạn găng
Khi tiến trình P2 rời khỏi đoạn gắng, Nó lại đặt giá trị turn=0 để cho phép tiến trình P1 đi vào đoạn găng
- Nếu một trong hai tiến trình P1, P2 trong đoạn gắng: Tiến trình còn lại đi vào một vòng lặp chờ biến turn thay đổi
3.3 Sử dụng việc kiểm tra luân phiên (2)
3.2 Sử dụng việc kiểm tra luân phiên(3) Đặc điểm:
• Số lần vào đoạn găng của P1, P2 là cân bằng (luân phiên nhau) →Vấn đề: o P1 cần vào đoạn găng liên tục o P2 không cần thiết làm
3.2 Sử dụng việc kiểm tra luân phiên(3)
- Ngăn được trường hợp: 2 tiến trình đồng thời trong đoạn găng
Một tiến trình bị ngăn vào đoạn găng bởi một tiến trình bên ngoài đoạn găng khi:
Turn=0 o P1 vào đoạn găng xong, o Đặt lại turn=1 rồi ra o Và muốn nhanh chóng quay lại đoạn găng lần nữa
Trong tiến trình P2, hiện tại đang thực thi ngoài đoạn găng và chưa đến thời gian để vào đoạn găng Do đó, P2 không thể đặt lại turn về 0, dẫn đến việc P1 cũng chưa thể vào đoạn găng.
- Ý tưởng: kết hợp 2 giải pháp trên
• P0, P1 sử dụng 2 biến chung turn (0/1), in[2] (true/false) o Biến turn:
turn=1; đến phiên P1, o Biến int[i]: (i=0 hoặc i=1)
in[i]=true: Pi muốn vào đoạn găng
in[i]se Pi chƣa muốn vào đoạn găng
• Khởi tạo: o Biến in [i]: in[0] = in[1] = false; o Biên biến:
turn = 0: P0 đƣợc vào đoạn găng
turn = 1: P1 đƣợc vào đoạn găng
Do Peterson đề nghị ý tưởng kết hợp 2 giải pháp trên
- Tiến trình Pi đặt giá trị các biến:
• Biến in[i]: in[|]=true //Pi muốn vào miền găng
• Biến turn: o turn=j//Đề nghị thứ Pj vào miền găng o Trong đó, tiến trình Pj
Biến in[j]: in[j]se //Pj chƣa muốn vào miền găng -> Pi có thể vào miền găng in[j]=true |/ Pi phải chờ
• Khi tiến trình Pi rời khỏi miền găng, nó đặt lại giá trị biến
• Cấu trúc tiến trình Pi
Ngăn chặn đƣợc tình trạng mâu thuẫn truy xuất:
- Pi chỉ có thể vào miền găng khi: in[j]se hoặc turn =1
- Nếu cả hai tiến trình đều muốn vào miền găng:
Trong trường hợp cả hai tiến trình P0 và P1 đều có giá trị in[i] = in[j] = true, thì giá trị của biến turn chỉ có thể là một trong hai: nếu turn = 0, tiến trình P0 được phép vào miền găng; nếu turn = 1, tiến trình P1 được phép vào miền găng.
- Do vậy chỉ có một tiến trình đƣợc vào miền găng
• Cho phép tiến trình: o Cấm tất cả các ngắt trước khi vào miền găng, o Và phục hồi ngắt khi ra khỏi miền găng
Trong quá trình hoạt động của miền găng, việc ngắt đồng hồ không xảy ra, điều này có nghĩa là hệ thống không thể tạm dừng tiến trình đang xử lý để phân bổ CPU cho tiến trình khác Nhờ vậy, tiến trình hiện tại có thể yên tâm thao tác trong miền găng mà không lo bị tiến trình khác can thiệp hoặc tranh chấp tài nguyên.
•Không đƣợc ƣa chuộng vì rất thiếu thận trọng: Khi cho phép tiến trình người dùng, được phép thực hiện lệnh cấm ngắt
Hệ thống có nhiều CPU với lệnh cấm ngắt chỉ ảnh hưởng đến CPU đang xử lý tiến trình hiện tại, trong khi các tiến trình khác trên các CPU khác vẫn có khả năng truy xuất đến miền găng.
Chỉ thị Test-and-Set Lock (TSL) trong tập lệnh máy cho phép kiểm tra và cập nhật nội dung của một vùng nhớ trong một thao tác đơn vị.
- Nếu có hai chỉ thị TSL: • Xử lý đồng thời (trên hai CPU khác nhau), -> chúng sẽ đƣợc xử lý tuần tự
- Có thể cài đặt giải pháp:
•Truy xuất độc quyền với TSL bằng cách sử dụng thêm một biến chung lock, đƣợc khởi tạo là FALSE
•Tiến trình phải kiểm tra giá trị của biến lock trước khi vào miền gang Nếu lock = FALSE, -> Tiến trình có thể vào miền găng
Cấu trúc một chương trình sử dụng giải pháp TSL :
Giảm nhẹ công việc lập trình ->Nhƣng việc cài đặt TSL nhƣ một lệnh máy Không đơn giản
Khi có nhiều CPU, việc điều phối thực hiện TSL cho từng CPU gặp khó khăn
3.6 Kết luận về giải pháp Busy waiting
Tất cả các giải pháp đều yêu cầu thực hiện một vòng lặp kiểm tra để xác định xem có được phép vào đoạn găng hay không Nếu điều kiện chưa cho phép, tiến trình sẽ phải tiếp tục chờ trong vòng lặp này Các giải pháp này yêu cầu tiến trình liên tục kiểm tra điều kiện nhằm phát hiện thời điểm thích hợp để vào đoạn găng.
->Cỏc giải phỏp ô busy waiting ằ-"Chờ vỡ Bận"
3.7 Kết luận về giải pháp Busy waiting
Việc kiểm tra điều kiện trong quá trình xử lý có thể tiêu tốn nhiều thời gian sử dụng CPU, dẫn đến tình trạng tiến trình đang chờ vẫn chiếm dụng tài nguyên CPU.
->Xu hướng giải quyết vấn đề đồng bộ hoỏ nờn trỏnh cỏc giải phỏp ô busy waiting ằ
4 Cỏc giải phỏp ô SLEEP and WAKEUP ằ(1)
- Khắc phục nhƣợc điểm của các giải pháp busy waiting bằng cách:
•Cho một tiến trình chƣa đủ điều kiện vào đoạn găng chuyển sang trạng thái waiting
Tiến trình sẽ tạm thời bị khóa để không sử dụng CPU ngay lập tức Chỉ khi tiến trình ở trạng thái ready (sẵn sàng), nó mới có thể chuyển sang trạng thái running (đang chạy) để sử dụng CPU.
4 Cỏc giải phỏp ô SLEEP and WAKEUP ằ (1)
• Process chƣa đủ điều kiện vào đoạn găng đều ở trạng thái ready
• Process chƣa đủ điều kiện vào đoạn găng đều ở trạng thái waiting
4 Cỏc giải phỏp ô SLEEP and WAKEUP ằ (2)
- Hệ điều hành sử dụng 2 thủ tục: Sleep và Wakeup
SLEEP là một lệnh hệ thống giúp tạm dừng hoạt động của tiến trình, chuyển nó sang trạng thái chờ (waiting) cho đến khi được một tiến trình khác đánh thức.
WAKEUP: là một lời gọi hệ thống nhận một tham số duy nhất Tiến trình sẽ đƣợc tái kích hoạt (đặt về trạng thái ready)
Cỏc giải phỏp ô SLEEP and WAKEUP ằ (2)
Khi một tiến trình chưa đủ điều kiện để tiếp tục hoạt động, nó sẽ gọi hàm SLEEP để tự khóa lại Đến khi có một tiến trình khác sẵn sàng, hàm WAKEUP sẽ được gọi để giải phóng tiến trình đó, cho phép nó tiếp tục thực hiện.
• WAKEUP: o Khi một tiến trình ra khỏi miền găng, gọi WAKEUP để đánh thức một tiến trình đang chờ, tạo cơ hội cho tiến trình này vào miền găng
4 Cỏc giải phỏp ô SLEEP and WAKEUP ằ (3)
4 Cỏc giải phỏp ô SLEEP and WAKEUP ằ (4)
•Các giải pháp phổ biến:
• Trao đổi thông điệp (send message)
- Semaphore s Là một biến(cấu trúc) có các thuộc tính sau:
• Một giá trị nguyên e(s) Một hàng đợi f(s) lưu danh sách các tiến trình đang có trạng thái waiting( chờ) trên semaphore s
- Semaphore s Định nghĩa hai thao tác:
• Down(s): Giảm giá trị của semaphore e(s) đi 1 đơn vị o Nếu semaphore có trị e(s) > 0, và tiếp tục xử lý o Ngƣợc lại, nếu e(s) = 0, Tiến trình phải chờ đến khi e(s) >0
Khi thực hiện thao tác Up trên semaphore e(s), giá trị của nó sẽ tăng thêm 1 đơn vị Nếu có một hoặc nhiều tiến trình đang chờ trên semaphore s do thao tác Down, hệ thống sẽ chọn một trong số các tiến trình này để hoàn thành thao tác Down và tiếp tục xử lý.
Cài đặt: Tiến trình P thực hiện: down(s) và Up(s)
4.1.1 Tổ chức truy xuất độc quyền với Semaphores
- Semaphore: Bảo đảm nhiều tiến trình cùng truy xuất, mà không có sự mâu thuẫn
- Giả sử o n tiến trình cùng sử dụng một semaphore s, o e(s) đƣoc khởi gán là 1
- Để thực hiện đồng bộ hóa: Tất cả các tiến trình cần phải áp dụng cùng cấu trúc chương trình:
4.1.2 Tổ chức đồng bộ hóa với Semaphores
Semaphore Có thể đồng bộ hóa hoạt động của hai tiến trình trong tình huống:
Một tiến trình phải đợi một tiến trình khác
Hoàn tất thao tác nào đó ->Mới có thể bắt đầu hay tiếp tục xử lý
4.1.2 Tổ chức đồng bộ hóa với Semaphores
• Hai tiến trình: Chia sẻ một semaphore s, khởi gán e(s) là 0
Cấu trúc hai tiến trình nhƣ sau:
