Bài giảng Hệ điều hành: Chương 4

Hệ Điều Hành Chương 4. Quản Lý Tiến Trình, Đồng bộ hóa Tiến trình & Tắc nghẽn

Giảng viên

TS. Trần Công Án tcan@cit.ctu.edu.vn

Khoa Công Nghệ Thông Tin & Truyền Thông

Đại học Cần Thơ

2018

[HĐH] Ch4. Quản lý tiến trình

Mục Tiêu

Giới thiệu các khái niệm về Tiến trình và những thao tác cơ bản trong Quản lý Tiến trình như tạo, định thời và kết thúc tiến trình. Các phương thức Giao tiếp liên tiến trình và vấn đề Tắc nghẽn của tiến trình cũng sẽ được trình bày.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 2

[HĐH] Ch4. Quản lý tiến trình

Nội Dung

Tổng quan về tiến trình

Giao tiếp liên tiến trình

Định thời tiến trình

Các giải thuật định thời

Đồng bộ hóa tiến trình

Tắc nghẽn (Deadlock)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 3

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình

Tổng quan về tiến trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 4

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khái niệm Tiến trình

Khái Niệm Tiến Trình

(cid:73) Tiến trình là thể hiện (instance) của một chương trình máy tính trong

bộ nhớ, đang thực thi hoặc chờ thực thi.

(cid:73) Mỗi tiến trình thường được gán 1 số định danh tiến trình (process

identifier, pid), dùng để định danh các tiến trình.

(cid:73) Một tiến trình bao gồm:

(cid:73) Mã lệnh chương trình (program code)

(cid:73) Bộ đếm chương trình (program counter) và các thanh ghi của CPU

(cid:73) Ngăn xếp (stack)

(cid:73) Phần dữ liệu (data section)

(cid:73) Có thể gồm phần bộ nhớ cấp phát động khi tiến trình thực thi (heap)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 5

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khái niệm Tiến trình

Chương Trình & Tiến Trình

(cid:73) Chương trình là một thực thể bị động, được lưu

trữ trên đĩa.

(cid:73) Tiến trình là một thực thể chủ động, lưu trú

trên bộ nhớ chính.

(cid:73) Khi một chương trình được kích hoạt (nhấp

chuột, CLI, . . . ), một thể hiện của chương trình sẽ được nạp lên bộ nhớ, tạo ra 1 tiến trình.

(cid:73) Một chương trình có thể có vài tiến trình trong

bộ nhớ.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 6

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Trạng thái của Tiến trình (Process state)

Trạng Thái Của Tiến Trình (Process State)

(cid:73) Một tiến trình có thể có một trong các trạng thái sau:

(cid:73) new: tiến trình đang được khởi tạo.

(cid:73) running: các chỉ thị của tiến trình đang được thực thi.

I/O, tín hiệu từ tiến trình khác, . . . ).

(cid:73) waiting: tiến trình đang chờ đợi một sự kiện nào đó xảy ra (hoàn thành

(cid:73) ready: tiến trình sẵn sàng để thực thi (đang đợi để được sử dụng CPU).

(cid:73) terminated: tiến trình đã kết thúc.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 7

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Trạng thái của Tiến trình (Process state)

Sơ Đồ Chuyển Trạng Thái Của Tiến Trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 8

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Khối điều khiển Tiến trình (Process Control Block – PCB)

Khối Điều Khiển Tiến Trình (PCB)

(cid:73) Chứa thông tin của tiến trình trong Hệ điều hành:

(cid:73) Trạng thái của quá trình: ready, running, . . .

(cid:73) Bộ đếm chương trình: chỉ thị kế tiếp sẽ được thực thi

(cid:73) Các thanh ghi: phụ thuộc vào k/trúc máy tính

(cid:73) Thông tin về định thời sử dụng CPU

(cid:73) Thông tin về quản lý bộ nhớ

(cid:73) Thông tin về chi phí: t/gian sử dụng CPU, pid, . . .

được cấp phát, danh sách tập tin đang mở, . . .

(cid:73) Thông tin về trạng thái nhập/xuất: các thiết bị đang

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 9

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Chuyển CPU giữa các Tiến trình

Chuyển CPU Giữa Các Tiến Trình

(cid:73) PCB là nơi lưu giữ trạng thái của tiến trình

(cid:73) Trạng thái của tiến

trình phải được lưu trữ vào PCB khi một interrupt xuất hiện, nhằm cho phép tiến trình có thể tiếp tục chính xác về sau.

(cid:73) Tác vụ chuyển CPU

còn được gọi là chuyển ngữ cảnh (context switch).

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 10

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Các thao tác trên Tiến trình

Tạo Tiến Trình

(cid:73) Một tiến trình (cha) có thể tạo những tiến trình khác (con) . . .

(cid:73) Quan hệ “cha–con” của các tiến trình tạo nên cây tiến trình.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 11

[HĐH] Ch4. Quản lý tiến trình Tổng quan về tiến trình Các thao tác trên Tiến trình

Kết Thúc Tiến Trình

(cid:73) T/trình thực thi câu lệnh cuối cùng và yêu cầu HĐH xóa nó (exit())

(cid:73) Truyền dữ liệu từ tiến trình con lên tiến trình cha (wait()).

zombie

(cid:73) Tiến trình con kết thúc trước khi t/trình cha gọi wait()

⇒

(cid:73) Tiến trình con còn thực thi khi t/trình cha đã kết thúc

orphan

⇒

(cid:73) Tiến trình cha có thể kết thúc tiến trình con (abort()):

(cid:73) Thu hồi tài nguyên đã được cấp phát cho tiến trình.

(cid:73) Tiến trình con đã có vượt quá số tài nguyên được cấp.

(cid:73) Công việc giao cho tiến trình con làm nay không còn cần thiết nữa.

(cid:73) Tiến trình cha đang thoát: một vài HĐH không cho phép orphan.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 12

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình

Giao tiếp liên tiến trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 13

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình

Hợp Tác Tiến Trình (Cooperating Process)

(cid:73) Tiến trình độc lập: không thể ảnh hưởng hoặc không bị ảnh hưởng bởi

sự thực thi của quá trình khác.

(cid:73) Hợp tác tiến trình: có thể ảnh hưởng hoặc bị ảnh hưởng bởi sự thực

thi của quá trình khác.

(cid:73) Thuận lợi của sự hợp tác quá trình:

(cid:73) Chia sẻ thông tin

(cid:73) Gia tăng tốc độ tính toán (nếu máy có nhiều CPU)

(cid:73) Module hóa

(cid:73) Tiện dụng

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 14

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình

Giao Tiếp Liên Tiến Trình

(cid:73) Các tiến trình muốn trao đổi dữ liệu với nhau cần sử dụng cơ chế giao

tiếp liên tiến trình (interprocess communication, IPC):

bộ nhớ chia sẻ

truyền thông điệp

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 15

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory)

Bộ Nhớ Chia Sẻ (Shared-Memory)

(cid:73) Một vùng đệm (buffer) được dùng để chia sẻ dữ liệu giữa các t/trình:

chờ, tiến trình ghi không bao giờ chờ.

(cid:73) kích thước không giới hạn (unbounded buffer): tiến trình đọc có thể

chờ.

(cid:73) Ví dụ kinh điển “Nhà sản xuất – Người tiêu thụ”: tiến trình Nhà sản

xuất sinh dữ liệu, được sử dụng bởi tiến trình Người tiêu thụ.

(cid:73) kích thước có giới hạn (bounded buffer): cả tiến trình đọc và ghi có thể

(cid:73) Tạo 1 vùng nhớ đệm (buffer) chung.

(cid:73) Tiến trình Nhà sản xuất ghi dữ liệu lên buffer.

(cid:73) Tiến trình Người tiêu thụ lấy dữ liệu từ buffer.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 16

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory)

Tạo Vùng Đệm (Buffering)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 17

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory)

Nhà Sản Xuất (Producer)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 18

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Bộ nhớ chia sẻ (Shared-memory)

Người Tiêu Dùng (Consumer)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 19

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Truyền Thông Điệp (Message Passing)

(cid:73) Giao tiếp giữa các tiến trình không cần dùng bộ nhớ chia sẻ hữu ích trong môi trường phân tán, giao tiếp qua mạng.

⇒

(cid:73) Cần hai thao tác: send(msg) và receive(msg).

(cid:73) Tiến trình P và Q muốn giao tiếp với nhau:

(cid:73) Tạo một nối kết giao tiếp (communication link)

(cid:73) Phương thức cài đặt nối kết giao tiếp (mức luận lý):

(cid:73) Trao đổi thông điệp thông qua send/receive

(cid:73) Giao tiếp trực tiếp hay gián tiếp

(cid:73) Đồng bộ hay bất đồng bộ

(cid:73) Kích thước thông điệp cố định hay biến đổi

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 20

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Giao Tiếp Trực Tiếp (Direct Communication)

(cid:73) Các quá trình phải được đặt tên rõ ràng:

(cid:73) Send(P, msg): gởi thông điệp tới quá trình P.

(cid:73) Các thuộc tính của nối kết giao tiếp:

(cid:73) Receive(Q, msg): nhận thông điệp từ quá trình Q.

(cid:73) Các nối kết được thiết lập tự động.

(cid:73) Một nối kết kết hợp với chính xác một cặp quá trình.

(cid:73) Giữa mỗi cặp quá trình tồn tại chính xác một nối kết.

(cid:73) Nối kết có thể một hướng, nhưng thường là hai hướng.

(cid:73) Giao tiếp bất đối xứng: Send(P, msg), Receive(id, msg).

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 21

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Giao Tiếp Gián Tiếp (Indirect Communication)

(cid:73) Các thông điệp được gửi và nhận thông qua mailbox hay port.

(cid:73) Mỗi mailbox có một định danh (id) duy nhất.

(cid:73) Các quá trình chỉ có thể giao tiếp nếu chúng dùng chung mailbox.

(cid:73) Các thuộc tính của nối kết gián tiếp:

(cid:73) Send/Receive(A, msg): gởi/nhận thông điệp tới/từ hộp thư A.

(cid:73) Nối kết chỉ được thiết lập nếu các quá trình chia sẻ một hộp thư chung.

(cid:73) Một nối kết có thể kết hợp với nhiều quá trình.

(cid:73) Mỗi cặp quá trình có thể dùng chung nhiều nối kết giao tiếp.

(cid:73) Nối kết có thể một hướng hay hai hướng.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 22

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Các Tác Vụ Trong Giao Tiếp Gián Tiếp

(cid:73) Các tác vụ cơ bản: tạo mailbox mới, gửi và nhận thông điệp qua

mailbox, và xóa mailbox.

(cid:73) Chia sẻ mailbox:

(cid:73) Các tiến trình có thể chia sẻ cùng 1 mailbox.

(cid:73) Giải pháp cho việc chia sẻ mailbox:

(cid:73) Vấn đề: nếu 1 tiến trình gửi thì tiến trình nào sẽ nhận?

(cid:73) Một liên kết chỉ tương ứng với 2 tiến trình.

(cid:73) Chỉ cho phép 1 tiến trình thực hiện thao tác nhận tại 1 thời điểm.

gửi biết người nhận.

(cid:73) HĐH chỉ định tiến trình nhận (1 tiến trình), và thông báo cho tiến trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 23

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Đồng Bộ Hóa (Synchronisation)

(cid:73) Truyền thông điệp có thể chặn (blocking) hay không chặn

(non-blocking).

(cid:73) Blocking được xem là đồng bộ (synchronous):

(cid:73) Blocking send: tiến trình gửi chờ cho đến khi thông điệp được nhận.

(cid:73) Non-blocking được xem là bất đồng bộ (asynchronous):

(cid:73) Blocking receive : tiến trình nhận chờ cho đến khi thông điệp sẵn sàng .

(cid:73) Non-blocking send: gửi thông điệp và tiếp tục thực hiện công việc khác.

(cid:73) Non-blocking receive: nhận một thông điệp hay rỗng.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 24

[HĐH] Ch4. Quản lý tiến trình Giao tiếp liên tiến trình Truyền thông điệp (Message passing)

Tạo Vùng Đệm (Buffering)

(cid:73) Vùng đệm dùng để chứa các thông điệp của 1 nối kết.

(cid:73) Ba cách cài đặt:

được nhận (no buffering!?).

(cid:73) Sức chứa là 0 (zero capacity): tiến trình gửi bị chặn đến khi thông điệp

thông điệp. Tiến trình gửi bị chặn khi vùng đệm bị đầy.

(cid:73) Sức chứa giới hạn (bounded capacity): kích thước vùng đệm giới hạn n

hạn. Tiến trình gửi không bao giờ bị chặn.

(cid:73) Sức chứa không giới hạn (unbounded capacity): kích thước không giới

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 25

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Định thời tiến trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 26

(cid:73) Định thời biểu CPU là một chức năng cơ bản và quan trọng của các

HĐH đa chương.

(cid:73) Chức năng: phân bổ thời gian/thời điểm sử dụng CPU cho các tiến

trình trong hệ thống, nhằm:

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

(cid:73) tăng hiệu năng (CPU utilisation) sử dụng CPU

(cid:73) Ý tưởng cơ bản: phân bố thời gian rãnh rỗi của CPU (khi chờ đợi tiến trình đang thực thi thực hiện các thao tác nhập xuất) cho các tiến trình khác trong hệ thống.

(cid:73) giảm thời gian đáp ứng (response time) của hệ thống

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 27

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Chu Kỳ CPU–I/O (CPU–I/O Burst)

(cid:73) Chu kỳ CPU–I/O:

(cid:73) Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU–I/O.

chu kỳ chờ đợi vào/ra (I/O burst).

(cid:73) Sự phân bổ sử dụng CPU:

(cid:73) Một chu kỳ CPU–I/O bao gồm chu kỳ thực thi CPU (CPU burst) và

CPU ngắn.

(cid:73) Chương trình hướng nhập xuất (I/O-bound) thường có nhiều chu kỳ

dài.

(cid:73) Chương trình hướng xử lý (CPU-bound) thường có nhiều chu kỳ CPU

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 28

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Ví Dụ Về Chu Kỳ CPU–I/O

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 29

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Bộ Định Thời CPU (CPU Scheduler)

(cid:73) Còn gọi là bộ định thời ngắn kỳ, chọn một trong các tiến trình trong

hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi.

(cid:73) Quyết định định thời xảy ra khi một tiến trình:

1. chuyển từ trạng thái đang chạy sang trạng thái chờ đợi

2. chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng

3. chuyển từ trạng thái chờ đợi sang trạng thái sẵn sàng

4. kết thúc

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 30

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Định Thời Trưng Dụng & Không Trưng Dụng

(cid:73) Định thời không trưng dụng (nonpreemptive scheduling):

xong (k/thúc hoặc chuyển sang trạng thái chờ, như trường hợp 1 và 4).

(cid:73) Định thời trưng dụng (preemptive scheduling):

(cid:73) Tiến trình được phân CPU có quyền sử dụng CPU đến khi sử dụng

cho tiến trình khác (trường hợp 2 và 3).

(cid:73) Bộ định thời có thể thu hồi CPU của tiến trình bất kỳ lúc nào để phân

(cid:73) Phức tạp hơn định thời không trưng dụng vì nó phải giải quyết:

(cid:73) sự cạnh tranh dữ liệu giữa các tiến trình.

(cid:73) sự trưng dụng khi tiến trình đang thực thi trong chế độ kernel.

(cid:73) dàn xếp giữa sự trưng dụng và xử lý các ngắt của hệ thống.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 31

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình

Bộ Điều Phối (Dispatcher)

(cid:73) Có nhiệm vụ thực thi việc trao quyền sử dụng CPU cho tiến trình

được cấp phát CPU bởi bộ định thời.

(cid:73) Bao gồm các tác vụ:

(cid:73) Chuyển ngữ cảnh

(cid:73) Chuyển sang chế độ người dùng

chương trình đó.

(cid:73) Độ trễ điều phối (dispatcher latency): thời gian dispatcher cần để

ngưng một tiến trình và khởi động một tiến trình khác.

(cid:73) Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 32

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Tiêu chí cho việc định thời

Tiêu Chí Cho Việc Định Thời

1. Hiệu suất sử dụng CPU: tỷ lệ giữa thời gian CPU được sử dụng trên

tổng thời gian hoạt động của hệ thống.

2. Thời gian đáp ứng (response time): lượng thời gian từ lúc một yêu

cầu được đệ trình cho đến khi bắt đầu được đáp ứng.

3. Thời gian chờ đợi (waiting time): tổng thời gian 1 tiến trình nằm

trong hàng đợi sẵn sàng (ready queue).

4. Thời gian xoay vòng (turnaround time): tổng thời gian để thực thi

một t/trình, bao gồm các khoảng t/gian: thực thi, chờ I/O, chờ trong ready queue (= t/điểm kết thúc – t/điểm bắt đầu vào ready queue).

5. Thông lượng (throughput): số lượng tiến trình hoàn thành trên một

đơn vị thời gian.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 33

[HĐH] Ch4. Quản lý tiến trình Định thời tiến trình Tiêu chí cho việc định thời

Tối Ưu Hóa Các Tiêu Chí

Các giải thuật định thời được đánh giá thông qua khả năng tối ưu hóa các tiêu chí định thời của nó:

1. Hiệu suất sử dụng CPU: càng lớn càng tốt

2. Thông lượng: càng lớn càng tốt

3. Thời gian xoay vòng: càng nhỏ càng tốt

4. Thời gian chờ đợi: càng nhỏ càng tốt

5. Thời gian đáp ứng: càng nhỏ càng tốt

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 34

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời

Các Giải Thuật Định Thời

1. First-come, first-served (FCFS): đến trước được phục vụ trước.

2. Shortest-job-rirst (SJF): công việc ngắn nhất trước.

3. Priority: dựa trên độ ưu tiên.

4. Round-robin (RR): xoay vòng.

5. Multilevel scheduling: hàng đợi đa cấp.

6. Multilevel feedback-queue scheduling: hàng đợi phản hồi đa cấp.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 35

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served

First-Come, First Served (FCFS)

(cid:73) Là giải thuật định thời đơn giản nhất, dựa trên nguyên tắc đến trước,

được phục vụ trước.

(cid:73) Cài đặt: phương pháp đơn giản nhất là dùng hàng đợi FIFO.

(cid:73) Ưu điểm: cài đặt dễ dàng, đơn giản và dễ hiểu.

(cid:73) Nhược điểm:

(cid:73) Thời gian chờ đợi trung bình thường là dài.

định thời không trưng dụng (nonpreemptive).

(cid:73) Không thích hợp cho hệ thống phân chia thời gian do đây là giải thuật

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 36

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served

FCFS – Ví Dụ 1

(cid:73) Cho các tiến trình với thời gian thực thi và thứ tự xuất hiện như sau:

(g/s tgian xuất hiện là t = 0)

(cid:73) Biểu đồ Gantt cho lịch biểu:

(cid:73) Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27

(cid:73) Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 37

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời First-come, first-served

FCFS – Ví Dụ 2

(cid:73) Giả sử các tiến trình trong ví dụ 1 xuất hiện theo thứ tự P2, P3, P1;

biểu đồ Gantt của lịch biểu là:

(cid:73) Thời gian chờ đợi: P1 = 6, P2 = 0, P3 = 3

(cid:73) Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3

tốt hơn nhiều so với ví dụ 1 (17)

⇒

(cid:73) Tình trạng thời gian chờ đợi dài do tiến trình ngắn nằm sau tiến trình

dài được gọi là “hiệu ứng nối đuôi” (convoy effect).

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 38

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

Shortest-Job-First (SJF)

(cid:73) Ý tưởng cơ bản: phân phối CPU cho tiến trình nào có thời gian thực thi CPU (CPU burst) kế tiếp nhỏ nhất (shortest-next-CPU-burst alg.)

(cid:73) Mỗi tiến trình sẽ được gán 1 độ dài thời gian của lần sử dụng CPU kế

tiếp (dự đoán).

(cid:73) Có 2 cách tiếp cận cho việc phân bổ CPU:

nó thực thi xong CPU burst.

(cid:73) Không trưng dụng: tiến trình được giao CPU sẽ chiếm giữ CPU đến khi

(cid:73) SJF cho thời gian chờ đợi trung bình tối ưu (ngắn nhất).

(cid:73) Trưng dụng: nếu 1 tiến trình mới đến có CPU burst ngắn hơn thời gian thực thi còn lại của tiến trình đang thực thi, CPU sẽ được lấy lại để giao cho tiến trình mới (shortest-remaining-time-first algorithm, SRTF)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 39

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

SJF Không Trưng Dụng – Ví Dụ

(cid:73) Biểu đồ Gantt cho lịch biểu:

(cid:73) Thời gian chờ đợi trung bình: (0 + 6 + 3 + 7)/4 = 4

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 40

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

SJF Trưng Dụng – Ví Dụ

(cid:73) Biểu đồ Gantt cho lịch biểu:

(cid:73) Thời gian chờ đợi trung bình: (9 + 1 + 0 + 2)/4 = 3

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 41

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

Thời Gian Sử Dụng CPU Lần Kế Tiếp

(cid:73) Chỉ có thể ước lượng, dựa vào lịch sử của những lần sử dụng CPU

trước đó.

(cid:73) Thời gian sử dụng CPU kế tiếp (công thức trung bình mũ):

Tn+1 = αtn + (1

α)Tn

−

(cid:73) Tn+1: ước lượng thời gian sử dụng CPU lần n + 1

(cid:73) tn: thời gian sử dụng CPU thực tế lần thứ n

[0, 1]: hệ số trung bình mũ, dùng để điều chỉnh trọng số cho các giá

∈

trị lịch sử (thông thường được gán giá trị 1/2)

(cid:73) α

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 42

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

Thời Gian Sử Dụng CPU Lần Kế Tiếp

(cid:73) Ví dụ: ước lượng thời gian sử dụng CPU lần kế tiếp, với α = 1/2, T0 = 10

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 43

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Shortest-job-first

Tùy Biến Hệ Số Trung Bình Mũ

(cid:73) α = 0

Tn+1 = Tn = . . . = T0

⇒

không tính đến lịch sử: tình trạng/sự thực thi “hiện thời” được coi như

⇒ nhất thời, không có ý nghĩa.

(cid:73) α = 1

Tn+1 = tn

⇒

chỉ tính đến thời gian sử dụng CPU thực tế gần nhất.

⇒

(cid:73) α = 1/2: các giá trị lịch sử thực tế và dự đoán có trọng số tương đương.

(cid:73) Nếu mở rộng công thức, ta có:

α)j αtn−j + . . . (1

α)n+1T0

Tn+1 = αtn + (1

α)αtn−1 + . . . + (1

−

(cid:73) Vì α và (1

α)

1, trọng số của giá trị lịch sử càng xa thì càng nhỏ.

−

≤

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 44

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời có ưu tiên

Giải Thuật Định Thời Có Ưu Tiên (Priority)

(cid:73) Ý tưởng:

(cid:73) Mỗi tiến trình sẽ được gán một chỉ số ưu tiên (priority number, int) .

thường là nhỏ nhất.

(cid:73) SJF là trường hợp đặc biệt của giải thuật này, trong đó thời gian thực

thi CPU kế tiếp đóng vai trò là chỉ số ưu tiên.

(cid:73) Có thể cài đặt theo phương pháp trưng dụng hay không trưng dụng.

(cid:73) Có thể xảy ra tình trạng “chết đói” (starvation): các tiến trình độ ưu

tiên thấp không bao giờ được thực thi.

Giải pháp: dùng sự “lão hóa” (aging) – các tiến trình đang chờ đợi

⇒ trong hệ thống sẽ được tăng dần độ ưu tiên theo thời gian chờ đợi.

(cid:73) CPU sẽ được cấp phát cho tiến trình có chỉ số ưu tiên cao nhất, thông

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 45

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời có ưu tiên

Ví Dụ

(cid:73) Không trưng dụng: T/gian chờ đợi trung bình = (0 + 23 + 25)/3 = 16

Biểu đồ Gantt:

(cid:73) Trưng dụng: T/gian chờ đợi trung bình = (6 + 0 + 2)/3 = 2.7

Biểu đồ Gantt:

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 46

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR)

Giải Thuật Định Thời Luân Phiên

(cid:73) Bộ điều phối cấp phát xoay vòng cho mỗi tiến trình trong hàng đợi sẵn sàng một đơn vị thời gian, gọi là định mức thời gian (time quantum, thường khoảng 10–100ms).

(cid:73) Sau khi sử dụng hết t/gian được cấp, CPU bị thu hồi để cấp cho tiến trình khác, tiến trình bị thu hồi CPU sẽ chuyển vào hàng đợi sẵn sàng.

gian để xoay vòng cấp phát CPU.

(cid:73) Nếu hàng đợi sẵn sàng có n tiến trình, định mức thời gian là q:

(cid:73) Bộ đếm thời gian (timer) sẽ phát ra các ngắt sau mỗi định mức thời

mỗi lần sử dụng tối đa là q

(cid:73) mỗi tiến trình sẽ nhận được 1/n tổng thời gian CPU, trong đó thời gian

−

(cid:73) không có tiến trình nào chờ đợi quá lượng thời gian (n

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 47

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR)

Các Tùy Biến & Hiệu Năng

(cid:73) q lớn: RR trở thành giải thuật FCFS (FIFO)

(cid:73) q nhỏ: q phải đủ lớn so với thời gian chuyển ngữ cảnh, nếu không, hao

phí chuyển ngữ cảnh sẽ rất cao.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 48

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR)

Các Tùy Biến & Hiệu Năng

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 49

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR)

Ví Dụ

(cid:73) Với time quantum = 20

(cid:73) Biểu đồ Gantt:

(cid:73) Thông thường, RR có thời gian chờ đợi trung bình lớn hơn SJF,

nhưng đảm bảo thời gian đáp ứng tốt hơn.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 50

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue)

Giải Thuật Hàng Đợi Đa Cấp

(cid:73) Chia hàng đợi s/sàng ra thành nhiều hàng đợi với độ ưu tiên khác

nhau, ví dụ:

(cid:73) foreground: tương tác, cần ưu tiên cao hơn.

(cid:73) Các tiến trình sẽ được phân phối vào các hàng đợi dựa trên các đặc tính như loại tiến trình (foreground/background), độ ưu tiên, . . .

(cid:73) Mỗi hàng đợi sẽ được áp dụng một giải thuật định thời riêng, tùy vào

tính chất của hàng đợi; ví dụ:

(cid:73) background: bó, cần ít ưu tiên hơn.

⇒

(cid:73) foreground (tương tác): cần thời gian đáp ứng nhanh hơn

FCFS

⇒

(cid:73) background (bó): có thể đáp ứng chậm hơn

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 51

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue)

Chiến Lược Định Thời Giữa Các Hàng Đợi

(cid:73) Định thời với độ ưu tiên cố định:

rồi mới đến hàng đợi có độ ưu tiên thấp hơn (vd: background).

(cid:73) Phục vụ tất cả các t/trình trong hàng đợi ưu tiên cao (vd: foreground)

(cid:73) Định thời với phân chia thời gian (time-slice):

(cid:73) Có khả năng dẫn đến tình trạng “chết đói” (starvation) CPU.

định thời cho các tiến trình nằm trong đó.

(cid:73) Mỗi hàng đợi sẽ nhận được một khoảng thời gian nào đó của CPU để

(cid:73) Ví dụ: 80% cho foreground với RR, và 20% cho background với FCFS.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 52

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue)

Ví Dụ Hàng Đợi Đa Cấp

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 53

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue)

Giải Thuật Hàng Đợi Phản Hồi Đa Cấp

(cid:73) Hàng đợi sẵn sàng cũng tổ chức giống như trong giải thuật Hàng đợi

đa cấp.

(cid:73) Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau.

(cid:73) Cơ chế định thời có thể được cài đặt theo cách:

hàng đợi có độ ưu tiên thấp hơn.

(cid:73) Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào

(cid:73) Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó sẽ được chuyển sang hàng đợi có độ ưu tiên cao hơn (cơ chế “sự lão hóa”).

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 54

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue)

Tham Số Của Bộ Định Thời

(cid:73) Bộ định thời đa cấp có phản hồi có thể được định nghĩa bằng những

tham số sau:

(cid:73) Số lượng hàng đợi

(cid:73) Giải thuật định thời cho từng hàng đợi

(cid:73) Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình.

(cid:73) Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình

khi tiến trình này cần được phục vụ.

(cid:73) Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 55

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue)

Ví Dụ Về Hàng Đợi Phản Hồi Đa Cấp

(cid:73) Các hàng đợi:

(cid:73) Định thời:

(cid:73) Q0: FCFS + quantum-time 8ms (cid:73) Q1: FCFS + quantum-time 16ms (cid:73) Q2: original FCFS

tiến trình khác và P sẽ được chuyển sang Q1.

(cid:73) Một tiến trình mới P sẽ được phân vào Q0 với giải thuật định thời FCFS. Khi có được CPU, nó sẽ được sử dụng tối đa 8ms. (cid:73) Nếu sau 8ms, P chưa hoàn thành thì CPU sẽ bị thu hồi để phân phối cho

(cid:73) Tại Q1, việc định thời diễn ra tương tự, với quantum-time là 16ms. Nếu P vẫn chưa hoàn thành thì nó sẽ được chuyển sang Q2 với giải thuật FCFS.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 56

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows

Định Thời Trong Windows

(cid:73) Đơn vị cấp phát CPU trong các HĐH hiện nay là luồng (thread) thay

vì tiến trình.

(cid:73) HĐH Windows dùng giải thuật định thời dựa trên độ ưu tiên (32 mức)

và định mức thời gian (RR), sử dụng chiến lược trưng dụng.

(cid:73) Mỗi độ ưu tiên sẽ có 1 hàng đợi riêng.

(cid:73) Một luồng được chọn thực thi bởi bộ điều phối sẽ t/thi cho đến khi:

(cid:73) bị trưng dụng bởi luồng có mức ưu tiên cao hơn, hoặc

(cid:73) kết thúc (terminate), hoặc

(cid:73) hết định mức thời gian (time quantum), hoặc

(cid:73) thực hiện lời gọi I/O.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 57

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows

Định Thời Trong Windows

(cid:73) Độ và nhóm ưu tiên của các luồng được chia như sau:

(cid:73) Ngoài ra, một số cơ chế để nâng/hạ độ ưu tiên cho cá luồng cũng được sử dụng (tương tự ý tưởng của g/thuật hàng đợi phản hồi đa cấp)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 58

[HĐH] Ch4. Quản lý tiến trình Các giải thuật định thời Định thời trong Windows

Chọn Lựa Tiến Trình Trong Windows

(cid:73) Bộ định thời duyệt qua các hàng đợi theo độ ưu tiên từ cao đến thấp.

(cid:73) Nếu không có tiến trình nào sẵn sàng, bộ định thời khởi động 1 tiến

trình đặc biệt gọi là idle process.

(cid:73) Độ ưu tiên của t/trình bị trưng dụng có thể bị thay đổi.

mức “normal”.

(cid:73) Nếu sử dụng hết time quantum: độ ưu tiên giảm, nhưng không dưới

(cid:73) Chuyển từ trạng thái chờ (waiting): độ ưu tiên tăng, mức độ tăng phụ thuộc vào t/trình đã chờ cái gì: đĩa – tăng nhiều, I/O – tăng ít hơn.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 59

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình

Đồng bộ hóa tiến trình

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 60

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu

Cạnh Tranh Và Sự Nhất Quan Dữ Liệu

(cid:73) Các tiến trình thực thi đồng thời, chia sẻ dữ liệu dùng chung có thể dẫn đến tình trạng không nhất quán (inconsistency) của dữ liệu.

(cid:73) Nhất quán = đúng đắn và chính xác; tùy thuộc vào ngữ cảnh, giao

dịch.

(cid:73) Có 2 lý do chính để thực hiện đồng thời (cạnh tranh) các tiến trình:

(cid:73) Tăng hiệu suất sử dụng tài nguyên hệ thống.

(cid:73) Việc duy trì sự nhất quán của dữ liệu yêu cầu một cơ chế để đảm bảo sự thực thi một cách có thứ tự của các tiến trình có hợp tác với nhau.

(cid:73) Giảm thời gian đáp ứng trung bình của hệ thống.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 61

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu

Ví Dụ 1 – Giao Dịch Cạnh Tranh

(cid:73) Cho hai giao dịch:

(50$: A

→

(cid:73) T1: A mua hàng trị giá 50$ của P

(100$: B

→

(cid:73) Khởi tạo ban đầu: A=500; B=500; P=1000

(cid:73) Yêu cầu về tính nhất quán: (A + B + P) không đổi; cụ thể hơn:

(cid:73) T2: B mua hàng trị giá 100$ của P

(cid:73) Nhận xét:

(cid:73) giá trị A, B, P sau khi thực hiện T1, T2 là: A=450; B=400; P=1150

T2 hoặc T2

T1, dữ liệu sẽ nhất quán.

→

(cid:73) Nếu thực hiện tuần tự T1

(cid:73) Nếu thực hiện cạnh tranh (đồng thời), dữ liệu sẽ nhất quán???

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 62

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Cạnh tranh và sự nhất quán dữ liệu

Ví Dụ 1 – Giao Dịch Cạnh Tranh

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 63

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Tình trạng tranh đua (Race condition)

Tình Trạng “Tranh Đua” (Race Condition)

(cid:73) Là tình trạng mà nhiều tiến trình cùng truy cập và thay đổi lên dữ liệu được chia sẻ, và giá trị cuối cùng của dữ liệu chia sẻ phụ thuộc vào tiến trình hoàn thành sau cùng.

(cid:73) giá trị của P trong ví dụ 1

(cid:73) Tình trạng tranh đua có thể dẫn đến tình trạng không nhất quán.

(cid:73) Để ngăn chặn tình trạng tranh đua, các tiến trình cạnh tranh cần phải

được đồng bộ hóa (synchronize).

(cid:73) hoặc giá trị biến counter trong ví dụ 2

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 64

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Vấn đề miền tương trục (Critical-section problem)

Vấn Đề Miền Tương Trục (CSP)

(cid:73) Xét 1 hệ thống có n tiến trình đang cạnh tranh

P0, P1, . . . , Pn−1

{

} (cid:73) Miền tương trục (critical section): là một đoạn mã lệnh của các tiến trình có chứa các hành động truy cập dữ liệu được chia sẻ như: thay đổi các biến dùng chung, cập nhật CSDL, ghi tập tin, . . .

Để tránh tình trạng tranh đua, các hệ thống phải đảm bảo khi một

⇒ tiến trình đang trong miền tương trục, không có một tiến trình nào khác được phép chạy trong miền tương trục của nó.

(cid:73) Vấn đề miền tương trục (critical-section problem): Thiết kế các giao thức để các tiến trình có thể sử dụng để hợp tác/cạnh tranh với nhau.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 65

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Vấn đề miền tương trục (Critical-section problem)

Vấn Đề Miền Tương Trục (CSP)

(cid:73) Cần phải xác định được phần entry section

và exit section.

(cid:73) Mỗi tiến trình phải xin phép để được vào

miền tương trục (đi qua vùng entry section), và sau đó thoát khỏi miền tương trục (đi qua vùng exit section) và thực hiện phần còn lại (remainder section).

(cid:73) Giải pháp cho vấn đề miền tương trục

tương đối phức tạp với với các hệ thống định thời trưng dụng.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 66

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Các giải pháp cho vấn đề miền tương trục

Yêu Cầu Đối Với Các Giải Pháp Cho CSP

(cid:73) Một giải pháp cho vấn đề miền tương trục phải thỏa 3 yêu cầu:

1. Loại trừ hỗ tương (mutual exclusion): Nếu 1 t/trình đang thực thi

trong miền tương trục, không một tiến trình nào khác được đi vào miền tương trục của chúng.

2. Tiến triển (progress): Nếu không có tiến trình nào đang thực thi trong miền tương trục và tồn tại tiến trình đang chờ được thực thi trong miền tương trục của chúng, thì việc lựa chọn cho một tiến trình bước vào miền tương trục không thể bị trì hoãn vô hạn.

3. Chờ đợi hữu hạn (bounded wait): Mỗi t/trình chỉ phải chờ để được

vào miền tương trục trong một khoảng t/gian có hạn định (không xảy ra tình trạng “chết đói” – starvation).

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 67

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Các giải pháp cho vấn đề miền tương trục

Phân Loại Các Giải Pháp

(cid:73) Các giải pháp phần mềm: dựa trên các giải thuật phần mềm, như:

(cid:73) Cho trường hợp chỉ có 2 tiến trình cạnh tranh:

(cid:73) Giải thuật Peterson (Peterson’s algorithm)

2 tiến trình cạnh tranh:

≥

(cid:73) Cho trường hợp có n

(cid:73) Các giải pháp phần cứng:

(cid:73) Giải thuật Bakery

(cid:73) Lệnh vô hiệu hóa ngắt (disable interrupt)

(cid:73) Lệnh máy đặc biệt: TestAndSet

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 68

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật chờ bận Peterson - 2 tiến trình

Giải Thuật Peterson

(cid:73) Kết hợp cả biến khóa chia sẻ (GT1) và biến khóa riêng (GT2):

(cid:73) int turn ; //turn = i: Pi được phép vào miền tương trục.

(cid:73) Tổ chức đoạn mã của 1 tiến trình Pi :

do {

:= t r u e

(cid:73) boolean flag [2]; //flag[i] = true: Pi sẵn sàng vào miền tương trục.

f l a g [ i ] t u r n := j ; w h i l e ( f l a g [ j ] && t u r n=j )

;

(cid:73) Nhận xét:

(cid:73) Loại trừ hỗ tương:

critical section f l a g [ i ] = f a l s e ;

remainder section

} w h i l e ( t r u e ) ;

(cid:73) Tiến triển: (cid:73) Chờ đợi hữu hạn:

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 69

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật Bakery - n tiến trình

Giải Thuật Bakery

(cid:73) Miền tương trục cho n tiến trình:

(cid:73) Mỗi t/trình sẽ nhận được 1 số trước khi vào miền tương trục.

(cid:73) Tiến trình có số nhỏ nhất sẽ có quyền ưu tiên cao nhất.

được phục vụ trước.

(cid:73) Nếu hai tiến trình Pi và Pj nhận được cùng một số, nếu i < j thì Pi

(cid:73) Dữ liệu chia sẻ:

boolean choosing[n]

int number[n]

(cid:73) Bộ sinh số luôn sinh các số theo thứ tự tăng, ví dụ: 1, 2, 3, 3, 3, 4, . . .

(cid:73) Khởi tạo: tất cả các phần tử của choosing = false và number = 0.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 70

[HĐH] Ch4. Quản lý tiến trình Đồng bộ hóa tiến trình Giải thuật Bakery - n tiến trình

Giải Thuật Bakery Cho Tiến Trình Pi

do {

. . . , number [ n

1]) + 1 ;

−

c h o o s i n g [ i ] = t r u e ; number [ i ] = max ( number [ 0 ] , number [ 1 ] , c h o o s i n g [ i ] = f a l s e ; f o r

( j = 0 ;

j < n ;

j ++) { ;

w h i l e ( c h o o s i n g [ j ] ) w h i l e ( ( number [ j ]

!= 0 ) && ( ( number [ j ] , j ) < ( number [ i ] , i ) )

;

} // f o r

$\ f r a m e b o x { c r i t i c a l

s e c t i o n }$

number [ i ] = 0 ;

$\ f r a m e b o x { r e m a i n d e r

s e c t i o n }$

} w h i l e ( t r u e ) ;

(cid:62) (number #1, i) < (number #2, j) nếu (number #1 < number #2)

hoặc (number #1 = number #2) AND (i < j) [HĐH] Ch4. Quản lý tiến trình TS. Trần Công Án

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock)

Tắc nghẽn (Deadlock)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 72

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Deadlock là gì?

Deadlock Là Gì?

(cid:73) Deadlock là một trạng thái của hệ thống trong đó:

(cid:73) một tập hợp các tiến trình đang bị nghẽn

nguyên đang bị giữ bởi một tiến trình khác trong tập các tiến trình đang bị nghẽn.

(cid:73) Ví dụ 1:

(cid:73) mỗi tiến trình đang giữ một tài nguyên và cũng đang chờ một tài

(cid:73) Giả sử 1 hệ thống có 2 tiến trình P và Q và F1, F2 là 2 tập tin.

(cid:73) Tiến trình P đang giữ F1 và cần truy xuất thêm F2.

(cid:73) Tiến trình Q đang giữ F2 và cần truy xuất thêm F1.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 73

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Deadlock là gì?

Ví Dụ 2 – Traffic Deadlock

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 74

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Điều kiện phát sinh deadlock

Điều Kiện Phát Sinh Deadlock

1. Loại trừ hỗ tương: ít nhất một tài nguyên được giữ ở chế độ không

chia sẻ (nonsharable mode).

2. Giữ và chờ: một tiến trình đang giữ ít nhất một tài nguyên và đợi

thêm tài nguyên đang bị giữ bởi tiến trình khác.

3. Không trưng dụng tài nguyên: không trưng dụng tài nguyên cấp

phát tiến trình, trừ khi tiến trình tự hoàn trả.

4. Chờ đợi vòng tròn: tồn tại một tập các tiến trình

P0, P1, . . . , Pn {

}

đang chờ đợi như sau: P0 đợi một tài nguyên P1 đang giữ, P1 đợi một tài nguyên P2 đang giữ, . . . , Pn đang đợi một tài nguyên P0 đang giữ.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 75

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Mô hình hóa hệ thống

Mô Hình Hóa Hệ Thống

(cid:73) Hệ thống gồm một tập các loại tài nguyên, kí hiệu R1, R2, . . . , Rm

(cid:73) Mỗi loại tài nguyên Ri có một tập các thể hiện (instances) Wi

(cid:73) Tiến trình sử dụng tài nguyên theo các bước:

1. Yêu cầu (request) – phải chờ nếu không được đáp ứng ngay.

2. Sử dụng (use)

3. Giải phóng (release)

(cid:73) Các tác vụ yêu cầu và hoàn trả được thực hiện bằng các lời gọi hệ

thống.

(cid:73) Ví dụ: CPU cycles, memory space, I/O devices, . . .

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 76

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Đồ Thị Cấp Phát Tài Nguyên – RAG

(cid:73) Là đồ thị có hướng, với tập đỉnh V và tập cạnh E

(cid:73) Tập đỉnh V gồm 2 loại:

P1, P2, . . . , Pn

{

(cid:73) Tập P =

: tập các tiến trình trong hệ thống } R1, R2, . . . , Rm {

: tập các tài nguyên của hệ thống }

(cid:73) Tập cạnh cũng gồm 2 loại:

(cid:73) Tập R =

(cid:73) Cạnh yêu cầu (request edge): có hướng từ Pi đến Rj

(cid:73) Cạnh cấp phát (assignment edge): có hướng từ RJ đến Pi

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 77

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Ký Hiệu

(cid:73) Tiến trình:

(cid:73) Loại tài nguyên (với 4 thể hiện):

(cid:73) Pi yêu cầu 1 thể hiện của Rj :

(cid:73) Pi đang giữ 1 thể hiện của Rj :

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 78

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 1

(cid:73) Đồ thị cấp phát tài nguyên (không có chu trình và không deadlock):

(cid:73) P =

P1, P2, P3 {

}

(cid:73) R =

}

R1, P2

P2,

(cid:73) E = R2

→ P1, R3

R3, R1 P3

R1, R2, R3, R4 { P1 { → P2, R2 →

→

→ }

→ (cid:73) Thể hiện của các loại tài nguyên:

R1 : 1; R2 : 2; R3 : 1; R4 : 3.

(cid:73) Trạng thái của các tiến trình:

(cid:73) P1: giữ (R2, 1); chờ (R1, 1) (cid:73) P2: giữ (R1, 1), (R2, 1); chờ (R3, 1) (cid:73) P3: giữ (R3, 1)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 79

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 2

(cid:73) Đồ thị cấp phát tài nguyên với chu trình và deadlock:

(cid:73) Trạng thái của các tiến trình:

(cid:73) P1: giữ (R2, 1); chờ (R1, 1)

(cid:73) P2: giữ (R1, 1), (R2, 1); chờ (R3, 1)

(cid:73) 2 chu trình nhỏ nhất (minimal cycles):

→

P1 P2

R1 R3

P2 P3

R3 R2

P3 P2

→ →

→ → (cid:73) Deadlock: cả 3 tiến trình P1, P2, P3

(cid:73) P3: giữ (R3, 1); chờ (R2, 1)

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 80

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 3

(cid:73) Đồ thị cấp phát tài nguyên có chu trình nhưng không deadlock:

(cid:73) Chu trình:

→

→ → (cid:73) Tại sao không deadlock?

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 81

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Đồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)

Đồ Thị Cấp Phát Tài Nguyên & Deadlock

(cid:73) Nếu đồ thị không có chu trình: chắc chắn không có deadlock

(cid:73) Nếu đồ thị có chu trình:

(cid:73) Nếu mỗi loại tài nguyên chỉ có một thể hiện: chắc chắn có deadlock.

(cid:73) Nếu mỗi loại tài nguyên có nhiều thể hiện: có thể có deadlock.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 82

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock

Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock

1. Đề ra các giao thức để đảm bảo cho hệ thống không bao giờ rơi vào

trạng thái deadlock.

2. Cho phép hệ thống rơi vào trạng thái deadlock, sau đó sử dụng các

giải thuật để phát hiện deadlock và phục hồi.

3. Không quan tâm và không xử lý vấn đề deadlock trong hệ thống

(cid:73) Khá nhiều hệ điều hành sử dụng phương pháp này.

(cid:73) Tuy nhiên, nếu deadlock không được phát hiện và xử lý sẽ dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải khởi động lại.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 83

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock

Ngăn chặn và tránh deadlock

(cid:73) Có hai biện pháp để đảm bảo hệ thống không rơi vào trạng thái

deadlock:

1. Ngăn chặn deadlock (deadlock prevention): không cho phép (ít nhất)

một trong bốn điều kiện cần cho deadlock xảy ra.

2. Tránh deadlock (deadlock avoidance): các tiến trình cần cung cấp thông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên một cách thích hợp.

TS. Trần Công Án [HĐH] Ch4. Quản lý tiến trình 84

[HĐH] Ch4. Quản lý tiến trình Tắc nghẽn (Deadlock) Các Cách Tiếp Cận Đối Với Vấn Đề Deadlock