Bài giảng Hệ điều hành - Chương V: Đồng bộ tiến trình - Hà Duy An

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An 1. Vấn đề miền tương trục 2. Giải pháp phần mềm 3. Giải pháp phần cứng 4. Semaphores 5. Các bài toán đồng bộ hóa cổ điển 6. Monitors 10/29/2013 Chương 5: Đồng bộ hóa2 • Các tiến trình được thực thi đồng thời o Có thể bị ngắt tại bất cứ vị trí nào • Các tiến trình đồng thời truy cập lên dữ liệu chia sẻ → tình trạng không nhất quán dữ liệu (inconsistency). • Việc duy trì sự nhất quán dữ liệu yêu cầu các 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. • Xét trường hợp: Bài toán Người sản xuất – Người tiêu thụ (Producer – Consumer Problem) với vùng đệm có kích thước giới hạn (bounded-buffer). 10/29/2013 Chương 5: Đồng bộ hóa4 • Dữ liệu chia sẻ: #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; 10/29/2013 Chương 5: Đồng bộ hóa5 while (true) { /* produce an item in next produced */ while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } 10/29/2013 Chương 5: Đồng bộ hóa6 while (true) { while (counter == 0) ; /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; /* consume the item in next consumed */ } 10/29/2013 Chương 5: Đồng bộ hóa7 • counter++ có thể được cài đặt: register1 = counterregister1 = register1 + 1counter = register1 • Counter-- có thể được cài đặt: register2 = counterregister2 = register2 - 1counter = register2 • Xét sự thực thi đan xen nhau với “count = 5” là giá trị khởi tạo: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4} 10/29/2013 Chương 5: Đồng bộ hóa8 • Nếu cả hai producer và consumer cố gắng cập nhật vùng đệm đồng thời, các phát biểu assembly có thể bị phủ lấp. • Sự phủ lấp phụ thuộc vào cách producer và consumer được định thời. • Tình trạng đua tranh (Race Condition): là tình trạng mà vài 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 nào hoàn thành cuối cùng.  Để ngăn chặn tình trạng đua tranh, các tiến trình cạnh tranh phải được đồng bộ hóa. 10/29/2013 Chương 5: Đồng bộ hóa9 • Xét hệ thống có n tiến trình {p0, p1, pn-1} • Mỗi tiến trình có một đoạn mã lệnh được gọi là miền tương trục (critical section): o Tiến trình có thể cập nhật các dữ liệu dùng chung o Khi một tiến trình đang trong miền tương trục, thì không tiến trình nào khác được phép thực thi trong miền tương trục của chúng => Vấn đề miền tương trục (critical-section problem): thiết kế giao thức giải quyết vấn đề này 10/29/2013 Chương 5: Đồng bộ hóa10 • Cấu trúc tổng quát của tiến trình Pi là: 10/29/2013 Chương 5: Đồng bộ hóa11 • Mỗi tiến trình phải kiểm tra sự hợp lệ trong phần entry section để đi vào miền tương trục, tiếp theo sau khi vào miền tương trục tiến trình sẽ thực hiện thao tác thoát khỏi miền tương trục exit section, và tiếp tục thực thi phần còn lại remainder section Giải pháp cho vấn đề miền tương trục phải thỏa các yêu cầu: 1. Loại trừ hỗ tương (Mutual Exclusion). Nếu tiến trình Pi đang thực thi trong miền tương trục, thì không có tiến trình nào khác có thể thực thi trong 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 vài tiến trình muốn được thực thi trong miền tương trục của chúng, thì việc lựa chọn một tiến trình được vào miền tương trục của nó không thể bị trì hoãn mãi được. 3. Chờ đợi hữu hạn (Bounded Wait). Không có tiến trình nào phải chờ đợi vĩnh viễn để có thể đi vào miền tương trục của nó. • Hai hướng tiếp cận giải quyết vấn đề phụ thuộc vào nhân HĐH: o Non-preemptive kernel: không cho phép tiến trình bị trưng dụng khi nó đang chạy ở chế độ nhân => vấn đề được giải quyết cho các cấu trúc dữ liệu trong nhân o Preemptive kernel: cho phép các tiến trình bị trưng dụng khi đang chạy ở chế độ nhân 10/29/2013 Chương 5: Đồng bộ hóa12 • Các biến chung: o boolean lock; khởi đầu lock = false; • Tiến trình Pi: do { while (lock) ; lock = true; critical section lock = false; remainder section } while (1); => Không giải quyết được vấn đề 10/29/2013 Chương 5: Đồng bộ hóa15 • Các biến chung: o int turn; khởi đầu turn = 0 o turn = i⇒Pi có thể bước vào miền tương trục của nó • Tiến trình Pi do { while (turn != i) ; critical section turn = j; remainder section } while (1); => Không thõa điều kiện 2 10/29/2013 Chương 5: Đồng bộ hóa16 • Các biến chia sẻ: o boolean flag[2]; khởi đầu flag[0] = flag[1] = false. o flag[i] = true ⇒Pi sẵn sàng bước vào miền tương trục của nó • Tiến trình P1: do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); => Không thỏa mãn điều kiện 2 10/29/2013 Chương 5: Đồng bộ hóa17 • Giải quyết được vấn đề miền tương trục (thỏa mãn cả 3 điều kiện) cho 2 tiến trình • Giả sử các lệnh load và store là nguyên tử (không thể bị ngắt) • Hai tiến trình chia sẽ hai biến: o int turn; o Boolean flag[2] • turn – chỉ định tiến trình nào được phép vào miền tương trục • flag – cho biết tiến trình nào đã sẵn sàng vào miền tương trục o flag [i] = true⇒Pi sẵn sàng bước vào miền tương trục của nó 10/29/2013 Chương 5: Đồng bộ hóa18 do { flag[i] = true; turn = j; while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true); • Nhận xét: 1. Loại trừ hỗ tương được đảm bảo 2. Yêu cầu tiến triển được thỏa mãn 3. Yêu cầu chờ đợi hữu hạn được đáp ứng 10/29/2013 Chương 5: Đồng bộ hóa19 • Nhiều hệ thống cung cấp phần cứng hỗ trợ đồng bộ hóa • Tất cả các giải pháp này dựa trên ý tưởng bảo vệ miền tương trục bằng "khóa" • Vô hiệu hóa các ngắt: khi một tiến trình bắt đầu thực thi trong miền tương trục thì các ngắt bị vô hiệu hóa đến khi tiến trình thoát khỏi miền tương trục o Cho phép tiến trình người dùng có khả năng vô hiệu các ngắt => có thể tác động xấu đến sự vận hành hệ thống o Không giải quyết được vấn đề trên hệ thống đa xử lý • Các hệ thống máy tính hiện đại cung cấp các thao tác nguyên tử (atomic hardware instructions): o test_and_set o compare_and_swap • Nếu các lệnh có tính chất nguyên tử thực thi cùng lúc thì thứ tự thực hiện của chúng luôn được đảm bảo – một lệnh được hoàn thành trước khi lệnh khác được thực thi o Atomic = non-interruptible 10/29/2013 Chương 5: Đồng bộ hóa21 • Lệnh test_and_set đọc và sửa đổi nội dung của một word một cách nguyên tử: boolean test_and_set(boolean *target) { boolean rv = *target; *target = true; return rv; } 10/29/2013 Chương 5: Đồng bộ hóa22 • Dữ liệu chia sẻ: boolean lock = false; • Tiến trình Pi: do { while (Test_And_Set(lock)) ; /* do nothing */ /* critical section */ lock = false; /* remainder section */ } while(1); =>không thỏa mãn yêu cầu chờ đợi hữu hạn 10/29/2013 Chương 5: Đồng bộ hóa23 • Tự động hoán chuyển (swap) hai biến: int compare_and_swap(int *value,int expected,int new value){ int temp = *value; if (*value == expected) *value = new value; return temp; } 10/29/2013 Chương 5: Đồng bộ hóa24 • Dữ liệu chia sẻ (khởi tạo là false): boolean lock; • Tiến trình Pi do { while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ /* critical section */ lock = 0; /* remainder section */ } while (true); =>không thỏa mãn yêu cầu chờ đợi hữu hạn 10/29/2013 Chương 5: Đồng bộ hóa25 • Dữ liệu chia sẻ (khởi tạo false): boolean lock; boolean waiting[n]; • Tiến trình Pi: do {waiting[i] = true;key = true;while (waiting[i] && key) key = test_and_set(&lock); waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; else waiting[j] = false; /* remainder section */ } while (true); => Thỏa tất cả các yêu cầu cho vấn đề miền tương trục 10/29/2013 Chương 5: Đồng bộ hóa26 • Các giải pháp với test_and_set và compare_and_swap thì phức tạp và người lập trình ứng dụng thường không thể truy cập đến các lệnh này • Người thiết kế HĐH xây dựng các công cụ phần mềm để giải quyết vấn đề này • Công cụ đơn giản nhất làMuxtex lock • Mutex lock có một biến boolean => miền tương trục có sẵn sàng hay không? • Bảo vệ miền tương trục với 2 hàm: o Acquire(): yêu cầu khóa trước khi vào miền tương trục o Release(): giải phóng khóa trước khi rời khỏi miền tương trục • Hai hàm acquire và release phải được gọi và thực thi một cách nguyên tử o Thường được cài đặt bằng các thao tác nguyên tử được cung cấp bởi phần cứng (hardware atomic instructions) như: test_and_set hay compare_and_swap • Muxtex lock đòi hỏi tiến trình chờ đợi bận (busy waiting) khi miền tương trục không sẵn sàng • Muxtex lock còn được gọi là spinlock 10/29/2013 Chương 5: Đồng bộ hóa27 acquire() { while (!available) ; /* busy wait */ available = false;; } release() { available = true; } do { acquire lock critical section release lock remainder section } while (true); 10/29/2013 Chương 5: Đồng bộ hóa28 • Các giải pháp chờ đợi bận làm hao phí thời gian của CPU. Semaphore là công cụ đồng bộ hóa không gây ra tình trạng chờ đợi bận. • Semaphore cho phép tiến trình chờ đợi vào miền tương trục sẽ ngủ/nghẽn (sleep/blocked) và sẽ được đánh thức (wakeup) bởi một tiến trình khác. • Ít phức tạp hơn • Semaphore S: là một biến integer, chỉ có thể được truy cập thông qua hai thao tác nguyên tử: wait (S) { while (S <= 0) ; // busy wait S--; } signal (S) { S++; } 10/29/2013 Chương 5: Đồng bộ hóa30 • Semaphore đếm – giá trị của integer của biến semaphore có một miền giá trị không giới hạn • Semaphore nhị phân: chỉ có giá trị 0 hay 1 => giống như mutex lock • Semaphore đếm S có thể được dùng để cài đặt như là một semaphore nhị phân • Xét tiến trình P1 và P2 yêu cầu lệnh S1 thực thi trước S2 P1: S1; signal(synch); P2: wait(synch); S2; 10/29/2013 Chương 5: Đồng bộ hóa31 • Định nghĩa một semaphore như là một cấu trúc gồm có: o Một giá trị integer o Một danh sách các tiến trình đang đợi trên nó typedef struct { int value; struct process *L; } semaphore; • Giả sử ta đã có hai thao tác được cung cấp bởi hệ điều hành như những lời gọi hệ thống cơ bản: block() – ngưng tạm thời tiến trình gọi thao tác này. wakeup(P) khởi động lại tiến trình P đã gọi thao tác block() trước đó. 10/29/2013 Chương 5: Đồng bộ hóa32 • Yêu cầu: không có bất kỳ 2 tiến trình nào có thể thực thi cùng lúc hai thao tác wait() và signal() => critical-section problem • Cài đặt wait() và signal(): o Hệ thống đơn xử lý: vô hiệu hóa các ngắt o Hệ thống đa xử lý: • Dùng busy waiting (các lệnh nguyên tử hay spinlock) • Không hoàn toàn loại bỏ được busy waiting tuy nhiên mã lệnh của wait() và signal() là ngắn => giảm bớt thời gian tiến trình phải dùng cho busy waiting 10/29/2013 Chương 5: Đồng bộ hóa33 wait(semaphore *S) { S->value--; if (S->value list; block(); } } signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } 10/29/2013 Chương 5: Đồng bộ hóa34 • Khóa chết – hai hoặc nhiều tiến trình đang chờ đợi vô hạn một sự kiện nào đó, mà sự kiện đó chỉ có thể được tạo ra bởi một trong các tiến trình đang chờ đợi khác. • Giả sử có 2 semaphore S và Q có giá trị 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); . . signal (S); signal (Q); signal (Q); signal (S); • Sự đói CPU –bị nghẽn (block) không hạn định. Một tiến trình có thể không bao giờ được xóa khỏi hàng đợi trong semaphore. 10/29/2013 Chương 5: Đồng bộ hóa35 1. Vùng đệm có kích thước giới hạn 2. Bộ đọc – bộ ghi 3. Các triết gia ăn tối • Vùng đệm có kích thước giới hạn – Bounded-Buffer • Hai tiến trình producer và consumer chia sẻ vùng đệm có kích thước n. • Dữ liệu chia sẻ: o Semaphoremutex: dùng cho loại trừ hỗ tương, khởi tạo 1. o Các Semaphore empty và full: dùng để đếm số khe trống và đầy. Khởi tạo empty = n và full = 0. 10/29/2013 Chương 5: Đồng bộ hóa37 • Tiến trình Producer: do { ... /* produce an item in next_produced */ ... wait(empty); wait(mutex); ... /* add next produced to the buffer */ ... signal(mutex); signal(full); } while (true); 10/29/2013 Chương 5: Đồng bộ hóa38 • Tiến trình Consumer: do { wait(full); wait(mutex); ... /* remove an item from buffer to next_consumed */ ... signal(mutex); signal(empty); ... /* consume the item in next consumed */ ... } while (true); 10/29/2013 Chương 5: Đồng bộ hóa39 • Một tập dữ liệu (data set) được chia sẻ giữa nhiều tiến trình thực thi đồng thời. o Readers: tiến trình chỉ đọc, không cập nhật dữ liệu o Writers: tiến trình thực thi cả hai thao tác đọc và ghi dữ liệu • Vấn đề: o Các reader có thể đọc dữ liệu chia sẽ đồng thời o Tại một thời điểm chỉ một writer được phép truy cập dữ liệu chia sẽ • Các biến thể: o Bộ đọc trước bộ ghi: không bộ đọc nào phải chờ, trừ khi bộ ghi đang cập nhật dữ liệu => bộ ghi có thể bị đói o Bộ ghi trước bộ đọc: khi bộ đọc đã sẳn sàng, nó sẽ ghi sớm nhất có thể => bộ đọc có thể bị đói 10/29/2013 Chương 5: Đồng bộ hóa40 • Dữ liệu chia sẻ: o Biến read_count: ghi vết số tiến trình đang đọc đối tượng. Khởi tạo 0. o Semaphore mutex: dùng cho loại trừ hỗ tương khi cập nhật biến readcount. Khởi tạo 1. o Semaphore rw_mutex: dùng loại trừ hỗ tương cho các bộ ghi. Khởi tạo rw_mutex = 1. Semaphore này cũng được dùng để ngăn cấm các bộ ghi truy cập vào đối tượng chia sẻ khi nó đang được đọc. 10/29/2013 Chương 5: Đồng bộ hóa41 do { wait(rw_mutex); ... /* writing is performed */ ... signal(rw_mutex); } while (true); 10/29/2013 Chương 5: Đồng bộ hóa42 do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex); ... /* reading is performed */ ... wait(mutex); read_count--; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true); 10/29/2013 Chương 5: Đồng bộ hóa43 • Năm triết gia ngồi trên bàn tròn, giữa là bát cơm và 5 chiếc đũa như hình, vừa ăn vừa suy nghĩ. • Khi suy nghĩ, triết gia không giao tiếp với các triết gia khác. • Khi đói, ông ta cố gắng chọn 2 chiếc đũa gần nhất (giữa ông ta và 2 láng giềng). Ông ta chỉ có thể lấy được 1 chiếc đũa tại mỗi thời điểm, và không thể lấy được đũa đang được dùng bởi láng giềng. 10/29/2013 Chương 5: Đồng bộ hóa44 • Khi có 2 chiếc đũa, triết gia ăn và chỉ đặt đũa xuống khi ăn xong, sau đó suy nghĩ tiếp. • Dữ liệu chia sẻ: semaphore chopstick[5]; Khởi đầu, các giá trị là 1. • Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) // eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); // think } while (TRUE); 10/29/2013 Chương 5: Đồng bộ hóa45 • Giải thuật bảo đảm không có 2 láng giềng ăn cùng lúc, nhưng có thể gây khóa chết (tình huống 5 triết gia cùng đói và mỗi người cùng lấy đũa bên trái) và đói tài nguyên. • Các giải pháp khả dụng: o Cho phép nhiều nhất 4 triết gia cùng ngồi trên bàn. o Cho phép một triết gia lấy đũa chỉ nếu cả hai chiếc đũa đều sẵn dùng. o Dùng giải pháp bất đối xứng. Ví dụ triết gia lẻ lấy đũa trái trước, rồi đến đũa phải, trong khi triết gia chẵn thao tác ngược lại. 10/29/2013 Chương 5: Đồng bộ hóa46 • Sử dụng không đúng: o signal(mutex) . wait(mutex) o wait(mutex) wait(mutex) o Thiếu wait(mutex) hoặc signal(mutex) hay cả hai • Khóa chết và đối tài nguyên 10/29/2013 Chương 5: Đồng bộ hóa48 • Monitor là một cấu trúc của ngôn ngữ lập trình (programming language construct), cung cấp cơ chế đồng bộ hóa ở mức ngôn ngữ cấp cao (high- level language synchronization construct) giúp thuận tiện và hiệu quả để đồng bộ hóa các tiến trình 10/29/2013 Chương 5: Đồng bộ hóa49 monitor monitor‐name { // shared variable declarations procedure P1 () { . } . . . procedure Pn () {} initialization_code () {  } } • Abstract data type (ADT): kiểu dữ liệu trừu tượng: dữ liệu được bao bọc bởi các hàm bên ngoài, và chỉ các hàm này được phép truy cập đến các dữ liệu đó => monitor type là một ADT • Chỉ một tiến trình có thể thưc thi bên trong monitor tại một thời điểm => chỉ một hàm bên trong monitor được thực thi tại một thời điểm 10/29/2013 Chương 5: Đồng bộ hóa50 • Condition x, y; • Hai thao tác trên biến điều kiện: o x.wait () – ngưng tạm thời tiến trình gọi thao tác này cho đến khi x.signal () o x.signal () – phục hồi lại tiến trình đã gọi x.wait () • Nếu không có bất kỳ tiến trình nào chờ trên biến điều kiện x hàm signal() không gây bất cứ ảnh hưởng nào 10/29/2013 Chương 5: Đồng bộ hóa51 10/29/2013 Chương 5: Đồng bộ hóa52 • Giả sử tiến trình P gọi x.signal() khi tiến trình Q đang chờ trên biến điều kiện x, để tránh hai tiến trình thực thi cùng lúc trong monitor, một trong hai lựa chọn sau đây có thể được dùng: 1. Signal and wait: P chờ cho đến khi Q rời khỏi monitor hoặc chờ một điều kiện khác 2. Signal and continue: Q chờ cho đến khi P rời khỏi monitor hoặc chờ một điều kiện khác • Lựa chọn thứ 2 được sử dụng kèm theo với điều kiện P phải lập tức thoát ra khỏi monitor được sử dụng trong ngôn ngữ Concurrent Pascal • Nhiều ngôn ngữ lập trình cài đặt cơ chế đồng bộ xác với ý tưởng monitor như đã mô tả (bao gồm C# và Java) • Một số ngôn ngữ lập trình khác (như Erlang) cung cấp các cơ chế tương tự 10/29/2013 Chương 5: Đồng bộ hóa53 • Dùng ngôn ngữ Pascal được đơn giản hóa (Pidgin Pascal) minh họa sử dụng Monitor giải quyết bài toán Producer-Consumer 10/29/2013 Chương 5: Đồng bộ hóa54 monitor ProducerConsumer condition full, empty; integer count; procedure insert(item: integer); begin if count = N then wait(full); insert_item(item) ; count := count + 1 ; if count = 1 then signal( empty) end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count ‐ 1 ; if count = N‐ 1 then signal(full) end; count := 0; end monitor; procedure producer; begin while true do begin item = producer_item; ProducerConsumer.insert(item) end end; 10/29/2013 Chương 5: Đồng bộ hóa55 procedure consumer; begin while true do begin item = ProducerConsumer.remove; consume_item(item) end end;