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

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

Ôn tập chương 4

 Tại sao phải định thời? Nêu các bộ định thời và

mô tả về chúng?

 Các tiêu chuẩn định thời CPU?

 Có bao nhiêu giải thuật định thời? Kể tên?

 Mô tả và nêu ưu điểm, nhược điểm của từng

giải thuật định thời? FCFS, SJF, SRTF, RR,

Priority Scheduling, HRRN, MQ, MFQ.

Đồng bộ

2

Bài tập chương 4

 Sử dụng các giải thuật FCFS, SJF, SRTF, Priority -

Pre, RR (10) để tính các giá trị thời gian đợi, thời gian

đáp ứng và thời gian hoàn thành trung bình và vẽ giản

đồ Gantt

Đồng bộ

3

Mục tiêu

 Hiểu được vấn đề tranh chấp giữa các tiến trình

trong hệ điều hành

 Biết được các giải pháp để giải quyết tranh chấp

 Hiểu được các vấn đề trong giải quyết tranh chấp

 Biết được các yêu cầu của các giải pháp trong

việc giải quyết tranh chấp và phân nhóm các giải

pháp

Đồng bộ

4

Nội dung

 Giới thiệu về race condition

 Giới thiệu các giải pháp tổng quát để giải

quyết tranh chấp

 Phân tích các chi tiết các vấn đề trong việc

giải quyết tranh chấp

 Yêu cầu của giải pháp trong việc giải quyết

tranh chấp

 Phân nhóm các giải pháp

Đồng bộ

5

Đặt vấn đề

 Khảo sát các process/thread thꢀc thi đồng thời

và chia sꢁ dữ liệu (qua shared memory, file).

 Nếu không có sꢀ kiểm soát khi truy cập các dữ

liệu chia sꢁ thì có thể đưa đến ra trường hợp

không nhất quán dữ liệu (data inconsistency).

 Để duy trì sꢀ nhất quán dữ liệu, hệ thꢂng cần

có cơ chế bảo đảm sꢀ thꢀc thi có trật tꢀ của

các process đồng thời.

Q

L

p

R

Đồng bộ

6

Bài toán Producer - Consumer

 P không được ghi dữ liệu vào buffer đã đầy

 C không được đọc dữ liệu từ buffer đang trꢂng

 P và C không được thao tác trên buffer cùng lúc

Giới hạn, không giới hạn

???

P

Buffer (N)

C

Đồng bộ

7

Bounded buffer

Xét trường hợp Bounded buffer:

 Quá trình Producer

item nextProduce;

while(1){

while(count == BUFFER_SIZE); /*ko lam gi*/

buffer[in] = nextProducer;

biꢀn count đưꢁc chia sꢂ

giꢃa producer vꢄ consumer

count++;

in = (in+1)%BUFFER_SIZE;

 Quá trình Consumer

item nextConsumer;

while(1){

while(count == 0); /*ko lam gi*/

nextConsumer = buffer[out];

count--;

out = (out+1)%BUFFER_SIZE;

Đồng bộ

8

Bounded buffer (tt)

 Các lệnh tăng, giảm biến count tương đương trong ngôn ngữ máy là:

 Producer (count++)

 register1 = count

 register1 = register1 + 1

 count = register1

 Consumer (count--)

 register2 = count

 register2 = register2 - 1

 count = register2

(Trong đó, các register là các thanh ghi của CPU)

Đồng bộ

9

Bounded buffer (tt)

 Mã máy của các lệnh tăng và giảm biến count có thể bị thꢀc thi xen kẽ

 Giả sử count đang bằng 5. Chuỗi thꢀc thi có thể xảy ra, khi quantum time =

2 chu kỳ lệnh

T0: producer register1 := count

{register1 = 5}

{register1 = 6}

{register2 = 5}

{register2 = 4}

{count = 6}

T1: producer register1 := register1 + 1

T2: consumer register2 := count

T3: consumer register2 := register2 - 1

T4: producer count := register1

T5: consumer count := register2

{count = 4}

Đồng bộ

10

Bounded buffer (tt)

 Mã máy của các lệnh tăng và giảm biến count có thể bị thꢀc thi xen kẽ

 Giả sử count đang bằng 5. Chuỗi thꢀc thi có thể xảy ra khi quantum time =

3 chu kỳ lệnh

T0: producer

T1: producer

T2: producer

T3: consumer

T4: consumer

T5: consumer

register1 := count

{register1 = 5}

register1 := register1 + 1 {register1 = 6}

count := register1

register2 := count

{count = 6}

{register2 = 6}

register2 := register2 - 1 {register2 = 5}

count := register2 {count = 5}

 Cần phải có giải pháp để cꢀc lꢁnh count++, count-- phải lꢂ đơn nguyên

(atomic), nghꢃa lꢂ thꢄc hiꢁn như mꢅt lꢁnh đơn, không bꢆ ngꢇt nꢈa chꢉng.

Đồng bộ

11

Bounded buffer (tt)

 Race condition: nhiꢅu process truy xuꢆt vꢄ thao tꢇc đꢈng thꢉi

lên dꢃ liꢊu chia sꢂ (như biꢀn count) và kꢀt quꢋ cuꢌi cꢍng cꢎa

viꢊc truy xuꢆt đꢈng thꢉi nꢄy phꢏ thuꢐc thꢑ tꢒ thꢒc thi cꢎa cꢇc

lꢊnh thao tꢇc dꢃ liꢊu.

 Đꢓ dꢃ liꢊu chia sꢂ đưꢁc nhꢆt quꢇn, cꢔn bꢋo đꢋm sao cho tꢕi mꢖi

thꢉi điꢓm chꢗ cꢘ mꢐt process đưꢁc thao tꢇc lên dꢃ liꢊu chia sꢂ.

Do đꢀ, cꢁn cꢀ cơ chꢂ đꢃng bꢄ hoạt đꢄng cꢅa cꢆc process nꢇy.

Đồng bộ

12

Vấn đề Critical Section

 Giả sử có n process truy xuất đồng thời dữ liệu chia sꢁ

 Cấu trúc của mỗi process Pi có đoạn code như sau:

Do {

entry section

critical section /

exit section

/* vꢀo critical section */

/* truy xuꢁt dư liꢂu chia sꢃ */

/* rꢄi critical section */

̃

remainder section /* lꢀm nhꢅng viꢂc còn lại */

} While (1);

Trong mỗi process có những đoạn code có chứa các thao tác

lên dữ liệu chia sꢁ. Đoạn code này được gọi là vꢃng tranh

chấp (critical section, CS).

Đồng bộ

13

Vấn đề Critical Section (tt)

 Vꢆn đꢅ Critical Section: phꢋi bꢋo đꢋm sꢒ loꢕi trꢙ

tương hꢖ (mutual exclusion, mutex), tꢑc lꢄ khi mꢐt

process đang thꢒc thi trong vꢍng tranh chꢆp, không cꢘ

process nꢄo khꢇc đꢈng thꢉi thꢒc thi cꢇc lꢊnh trong

vꢍng tranh chꢆp.

Đồng bộ

14

Yêu cầu của lời giải cho CS Problem

 Lời giải phải thỏa ba tính chất:

 (1) Loại trừ tương hỗ (Mutual exclusion): Khi một process

P đang thꢀc thi trong vꢃng tranh chấp (CS) của nó thì

không có process Q nào khác đang thꢀc thi trong CS của

Q.

 (2) Progress: Một tiꢀn trꢁnh tꢂm dꢃng bên ngoài miền

găng không được ngăn cản cꢄc tiꢀn trꢁnh khꢄc vào

miền găng

 (3) Chờ đợi giới hạn (Bounded waiting): Mỗi process chꢄ

phải chờ để được vào vꢃng tranh chấp trong một khoảng

thời gian có hạn định nào đó. Không xảy ra tình trạng đói

tài nguyên (starvation).

Đồng bộ

15

Yêu cầu của lời giải cho CS Problem

 Tính chất (2) Progress

(2) Progress: Một tiꢀn trꢁnh tꢂm dꢃng bên ngoài miền găng

không được ngăn cản cꢄc tiꢀn trꢁnh khꢄc vào miền găng

Được sửa lꢂi như sau:

Progress. If no process is executing in its critical section and some

processes wish to enter their critical sections, then only those processes

that are not executing in their remainder sections can participate in

deciding which will enter its critical section next, and this selection cannot

be postponed indefinitely (Sách tham khảo trang 206)

 nếu không có process nào đang thꢀc thi trong vꢃng tranh chấp và

đang có một sꢂ process chờ đợi vào vꢃng tranh chấp thì:

– Chꢄ những process không đang thꢀc thi trong Remainder Section

mới có thể tham gia trong việc quyết định process nào sẽ vào vùng

tranh chấp.

– Và việc chọn lꢀa này không được trì hoãn vô hạn

Đồng bộ

16

Phân loꢂi giải phꢄp

 Nhóm giải pháp Busy Waiting

 Sử dụng các biến cờ hiệu

 Sử dụng việc kiểm tra luân phiên

 Giải pháp của Peterson

 Cấm ngắt

 Chꢄ thị TSL

 Nhóm giải pháp Sleep & Wakeup

 Semaphore

 Monitor

 Message

Đồng bộ

17

Cꢄc giải phꢄp “Busy waiting”

 Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng

 Không đòi hỏi sꢀ trợ giúp của Hệ điều hành

While (chưa có quyền) do_nothing() ;

CS;

Từ bỏ quyền sử dụng CS

Đồng bộ

18

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

 Từ bỏ CPU khi chưa được vào miền găng

 Cần Hệ điều hành hỗ trợ

if (chưa có quyền) Sleep() ;

CS;

Wakeup (somebody);

Đồng bộ

19

Tổng kꢀt

 Race condition

 Các giải pháp tổng quát để giải quyết

tranh chấp

 Các chi tiết các vấn đề trong việc giải

quyết tranh chấp

 Yêu cầu của giải pháp trong việc giải

quyết tranh chấp

 Các nhóm các giải pháp

Đồng bộ

20

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