Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 3)

Chương 5: Đồng bộ - 3

01/2015

Mục tiêu

 Biết được các giải pháp đồng bộ tiến trình theo kiểu

“Sleep & Wake up” bao gồm:

 Semaphore

 Critical Region

 Monitor

 Áp dụng các giải pháp này vào các bài toán đồng bộ

kinh điển

Đồng bộ

2

Nội dung

 Các giải pháp “Sleep & Wake up”

 Semaphore

 Các bài toán đồng bộ kinh điển

 Monitor

Đồng bộ

3

Các giải pháp “Sleep & Wake up”

int busy; // =1 nếu CS đang bꢀ chiếm

int blocked; // sô

do{

́ P đang bꢀ khꢁa

if (busy){

blocked = blocked +1;

sleep();

}

else busy =1;

CS;

busy = 0;

if (blocked !=0){

wakeup (process);

blocked = blocked -1;

}

RS;

} while (1);

Đồng bộ

4

Semaphore

 Một trong những công cụ đảm bảo sự đồng bộ của các

process mà hệ điều hành cung cấp là Semaphore.

 Ý tưởng của Semaphore:

 Semaphore S là một biến sꢂ nguyên.

 Ngoài thao tác khởi động biến thꢃ Semaphore chꢄ

có thể được truy xuất qua hai hàm có tꢅnh đơn

nguyên (atomic) là wait và signal

Hàm wait() và signal() còn có tên gọi khác lần lượt là P()

và V()

Đồng bộ

5

Semaphore

 Đầu tiên, hàm wait và signal được hiện thực như sau:

Tuy nhiên, với cách hiện thực này, vòng lặp “while (S <= 0);” trong

hàm wait() sẽ dẫn tới busy waiting.

 Để không busy waiting, hàm wait() và signal() được cải tiến. Một

hàng đợi semaphore được đưa thêm vào để thay vì phải lặp vòng

trong trường hợp semaphore nhỏ hơn hoặc 0, process sẽ được

đưa vào hàng đợi này để chờ và sẽ được ra khỏi hàng đợi này khi

hàm signal()g đọ ư i .ợc

Đồng bộ

6

Semaphore

 Hàm wait và signal của Semaphore cải tiến, không busy

waiting như sau:

 Đꢀnh nghꢆa semaphore lꢇ một record

typedef struct {

int value;

struct process *L; /* process queue */

} semaphore;

 Mỗi Semaphore có một giá trꢀ nguyên của nó và một danh sách

các process.

 Khi các process chưa sẵn sàng để thực thi thì sẽ được đưa vào

danh sách này. Danh sách này còn gọi là hàng đợi semaphore.

Lưu ý: Các process khi ra khỏi hàng đợi semaphore sẽ vào hàng đợi

Ready để chờ lấy CPU thực thi.

Đồng bộ

7

Semaphore

 Hàm wait và signal của Semaphore cải tiến, không busy

waiting như sau:

 Hàm wait() và signal() được hiện thực như sau:

void wait(semaphore *S) {

Lập trình thực tế, tùy

từng ngôn ngữ, có thể

S.value--;

if (S.value < 0) {

là:

add this process to S.L;

S.value hoặc

block();

Svalue

}

void signal(semaphore *S) {

S.value++;

if (S.value <= 0) {

remove a process P from S.L;

wakeup(P);

}

Đồng bộ

8

Semaphore

 Hàm wait và signal của Semaphore cải tiến, không busy

waiting như sau:

 Khi hàm wait() được gọi, ngay lập tức giá trꢀ value của

Semaphore S bꢀ giảm đi 1. Và nếu giá trꢀ Semaphore S âm,

process này sẽ bꢀ đưa vào danh sách L (đưa vào hàng đợi

Semaphore) và bꢀ khóa (block) lại.

 Khi hàm signal() được gọi, ngay lập tức giá trꢀ value của

Semaphore S tăng lên 1. Và nếu giá trꢀ Semaphore lớn hơn

hoặc bằng 0, một process sẽ được chọn lựa trong danh sách L,

tức trong hàng đợi Semaphore và bꢀ đánh thức dậy (wakeup) để

ra hàng đợi ready và chờ CPU để thực hiện.

Lưu ý: Trong hiện thực, các PCB của các process bị block sẽ được

đưa vào danh sách L. Danh sách L có thể dùng hàng đợi FIFO

hoặc cấu trúc khác tùy thuộc vào yêu cầu hệ thống.

Đồng bộ

9

Semaphore

 Hàm wait và signal của Semaphore cải tiến, không busy

waiting như sau:

 Block() và Wakeup() là hai system calls của hệ điều hành.

 block(): Process này đang thực thi lệnh này sẽ bꢀ khóa lại.

Process chuyển từ Running sang Waiting

 wakeup(P): hồi phục quá trꢃnh thực thi của process P đang bꢀ

blocked

Process P chuyển thừ Waiting sang Ready

Đồng bộ

10

Ví dụ sử dụng semaphore (1)

 Shared data:

Ví dụ 1:

semaphore mutex;

Dùng semaphore giải quyết

n process truy xuất vào CS.

(Khởi tạo mutex.value = 1)

Có hai trường hợp:

 Process Pi:

 Chꢄ duy nhất một process

được vꢇo CS (mutual

exclusion)

do {

wait(mutex);

critical section

Khꢀi tꢁo S.value = 1

signal(mutex);

remainder section

} while (1);

 Cho phꢈp k process vꢇo CS

Khꢀi tꢁo S.value = k

Đồng bộ

11

Ví dụ sử dụng semaphore (2)

Ví dụ 2:

 Process P1:

S1;

Dùng Semaphore giải quyết

đồng bộ giữa hai process

signal(synch);

Yêu cầu:

 Process P2:

Cho hai process: P1 và P2

wait(synch);

S2;

P1 thực hiện lệnh S1 vꢇ P2 thực

hiện lệnh S2.

Lệnh S2 chꢄ được thực thi sau khi

lệnh S1 được thực thi.

Khꢀi tao semaphore tên synch

và

synch.value = 0

Đồng bộ

12

Ví dụ sử dụng semaphore (3)

Ví dụ 3:

 Process P1:

Dùng Semaphore giải quyết

đồng bộ giữa hai process

A1;

signal(s1);,

wait(s2);

A2;

Yêu cầu:

Xét 2 tiến trình xử lý đoạn

chương trình sau:

 Process P2:

B1

• Tiến trình P1 {A1, A2}

• Tiến trình P2 {B1, B2}

Đồng bộ hóa hoạt động của 2 tiến

trình sao cho cả A1 và B1 đều

hoàn tất trước khi A2 và B2 bắt

đầu.

signal(s2);

wait(s1);

B2;

Khꢀi tꢁo 2 Semaphore s1 và s2

s1.value = s2.value = 0

Đồng bộ

13

Nhận xét

 Khi S.value ≥ 0: value chính là sꢂ process cꢁ thể

thực thi wait(S) mꢇ không bꢀ blocked

 Khi S.value < 0: trꢀ tuyệt đꢂi của value chính là sꢂ

process đang đợi trên hàng đợi semaphore

Đồng bộ

14

Nhận xét (tt)

 Việc hiện thực Semaphore phải đảm bảo tính chất Atomic vꢇ

mutual exclusion: tức không được xảy ra trường hợp 2 process

cꢉng đang ở trong thân lệnh wait(S) vꢇ signal(S) (cꢉng semaphore

S) tại một thời điểm (ngay cả với hệ thꢂng multiprocessor)

⇒ do đꢁ, đoạn mꢊ đꢀnh nghꢆa các lệnh wait(S) vꢇ signal(S) cꢋng

chꢅnh lꢇ vꢉng tranh chấp

 Giải pháp cho vꢉng tranh chấp wait(S) vꢇ signal(S):

 Uniprocessor: cꢁ thể dꢉng cơ chế cấm ngắt (disable

interrupt). Nhưng phương pháp nꢇy không hiệu quả trên hệ

thꢂng multiprocessor.

 Multiprocessor: cꢁ thể dꢉng các giải pháp software (như giải

Peterson và Bakery) hoặc giải pháp hardware (TestAndSet,

Swap).

 Vꢉng tranh chấp của các tác vụ wait(S) vꢇ signal(S) thông

thường rất nhꢌ: khoảng 10 lệnh.

Vꢃ CS rất nhꢌ nên chi phꢅ cho busy waiting sẽ rất thấp.

Đồng bộ

15

Deadlock và starvation

 Deadlock: hai hay nhiều process đang chờ đợi vô hạn đꢀnh một

sự kiện không bao giờ xảy ra.

Ví dụ thường gặp nhất của deadlock là hai (hoặc nhiều) process đang

chờ đợi qua lại các sự kiện của nhau thì mới được thực thi, nhưng cả hai

process này đều đꢊ bꢀ block, nên sự kiện này không bao giờ xảy ra và hai

process sẽ bꢀ block vꢆnh viễn.

Ví dụ: Gọi S vꢇ Q lꢇ hai biến semaphore được khởi tạo = 1

P0

P1

wait(S);

wait(Q);

…

wait(Q);

wait(S);

…

signal(S);

signal(Q);

signal(S);

Ví dụ khởi tạo S.value và Q.value bằng 1. P0 đầu tiên thực thi wait(S), rồi

P1 thực thi wait(Q), rồi P0 thực thi wait(Q) và bꢀ blocked, tiếp theo P1

thực thi wait(S) bꢀ blocked.

 Tình huꢂng nà là P0 và P1 bꢀ rơi vào deadlock.

Đồng bộ

16

Deadlock và starvation

 Starvation (indefinite blocking): Trường hợp một tiến trꢃnh cꢁ

thể không bao giờ được lấy ra khꢌi hꢇng đợi mꢇ nꢁ bꢀ khóa/treo

(block) trong hꢇng đợi đꢁ.

Đồng bộ

17

Các loại semaphore

 Counting semaphore: một sꢂ nguyên cꢁ giá trꢀ

không hạn chế.

 Binary semaphore: cꢁ trꢀ lꢇ 0 hay 1. Binary

semaphore rất dễ hiện thực.

Đồng bộ

18

Các bài toán đồng bộ kinh điển

Ba bài toán đồng bộ kinh điển:

 Bounded-Buffer Problem

 Dining-Philosophers Problem

 Readers and Writers Problem

Đồng bộ

19

Bài toán Bounded-Buffer

Producer sản suất một sản phẩm và đặt vào buffers,

buffers giới hạn chꢄ chứa được n sản phẩm.

Consumer tiêu thụ mỗi lần một sản phẩm, sản phẩm được

lấy ra từ buffers.

Khi buffers đꢊ chứa n sản phẩm, Producer không thể đưa

tiếp sản phẩm vào buffers nữa mà phải chờ đến khi buffers

có chỗ trꢂng. Khi buffers rỗng, Consumer không thể lấy sản

phẩm để tiêu thụ mà phải chờ đến khi có ít nhất 1 sản

phẩm vào buffers.

Đồng bộ

20

Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 3) - Trần Thị Như Nguyệt