Remainder section là gì

Ñoàng Boä Quaù Trình1Nội dungKhái niệm cơ bảnVùng tranh chấp [critical section]Các giải pháp dùng lệnh máy thông thường● Giải thuật Peterson, và giải thuật bakeryCác giải pháp dùng lệnh cấm ngắt hoặc lệnh máy đặcbiệtSemaphoreSemaphore và các bài toán đồng bộMonitor2Bài toán đồng bộ [1/2]•Khảo sát các process/thread thực thi đồng thời và chiasẻ dữ liệu [như ghi shared memory] trong hệ thống● uniprocessor, hoặc● shared memory multicore/multiprocessorNếu không có sự kiểm soát khi truy cập các dữ liệu chiasẻ thì chúng có thể trỡ nên không nhất quán.Để 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ời3Bài toán đồng bộ [2/2]Hai lớp bài toán đồng bộ:● Hợp tác Bài toán producer-consumer: bounded buffer● Cấp phát tài nguyên Bài toán loại trừ tương hỗ: đồâng bộ nhiều quá trình sử dụngmột tài nguyên không chia sẻ đồâng thời được [= chỉ có thểđược sử dụng lần lượt bởi các quá trình] Bài toán Dining Philosophers4“Đồng thời” bao gồm “song song”Trên uniprocessor hay trên shared memorymultiprocessor, các quá trình chạy đồng thờiTrên shared memory multiprocessor, các quá trình cóthể chạy song songquá trình 1quá trình 2Shared memoryBiến chia sẻQuá trinh 1 và 2code và private data5Baứi toaựn Producer-Consumer [1/3]Vớ duù: Bounded buffer, theõm bieỏn ủeỏm count#define BUFFER_SIZE 8/* 8 buffers */typedef struct {. . .} item;item buffer[BUFFER_SIZE];int in = 0, out = 0, count = 0;Bài toán Producer-Consumer [2/3]Quá trình Produceritem nextProduced;while[1] {while [count == BUFFER_SIZE];buffer[in] = nextProduced;count++;in = [in + 1] % BUFFER_SIZE;}Quá trình Consumeritem nextConsumed;while[1] {while [count == 0];nextConsumed = buffer[out];count--;out = [out + 1] % BUFFER_SIZE;}con trỏcon trỏbiến count được chia sẻgiữa producer và consumer7Bài toán Producer-Consumer [3/3]•Các lệnh tăng/giảm biến count tương đương trong ngônngữ máy là:Producercount++:• register1 = count• register1 = register1 + 1• count= register1•Consumercount--:• register2 = count• register2 = register2 - 1• count= register2Trong đó, registeri là thanh ghi của CPU.8Đồng bộ và lệnh đơn nguyên•Mã máy của các lệnh tăng và giảm biến count có thể thực thi xen kẽGiả sử count đang bằng 5. Chuỗi thực thi sau có thể xảy ra:1:producerregister1 := count{register1 = 5}producerregister1 := register1 + 1{register1 = 6}consumerregister2 := count{register2 = 5}consumerregister2 := register2 - 1{register2 = 4}3:producercount := register1{count = 6}4:consumercount := register2{count = 4}2:Cả hai process thao tác đồng thời lên biến chung count. Trò của biếnchung này không nhất quán dưới các thao tác của hai process.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 thực thi đan xen nhau.9Race conditionRace condition: tình huống khi nhiều process truy xuất vàthao tác đồng thời lên dữ liệu chia sẻ [như biến count];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 [máy] thao tác lên dữliệu.Để dữ liệu chia sẻ bởi quá trình Producer và Consumerđược nhất quán, cần bảo đảm sao cho các process lầnlượt 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.10Khái niệm critical sectionGiả sử có nhiều process đồng thời truy xuất dữ liệu chiasẻ.Giải quyết vấn đề race condition cho những đoạn codecó 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].Bài toán loại trừ tương hỗ: phải bảo đảm sự loại trừ tươnghỗ [mutual exclusion, mutex], tức là khi một process Pđang thực thi trong CS của P, không có process Q nàokhác đồng thời thực thi các lệnh trong CS của Q.11Cấu trúc tổng quát của quá trình trong bài toánloại trừ tương hỗCấu trúc tổng quát của mộtprocess:do {entry sectioncritical sectionexit sectionremainder section} while[1];Giả thiết Có thể có nhiều CPU Không ràng buộc về thứ tựthực thi của các process Các process có thể chia sẻmột số biến chung nhằm đồngbộ hoạt động của chúngVấn đề Thiết kế entry section và exitsection12Đònh nghóa lời giải của bài toán loại trừtương hỗLời giải phải thỏa ba tính chất1. Mutual exclusion2. Progress [Tiến triển]● [Progress cho entry section] Nếu ít nhất một process đang trongentry section và không có process nào đang trong critical section,thì một process vào critical section tại một thời điểm sau đó● [Progress cho exit section] Nếu ít nhất một process đang trongexit section, thì một process vào remainder section tại một thờiđiểm sau đó•3. Starvation freedom [Không bò “bỏ đói”]● [cho entry section] quá trình vào entry section sẽ vào CS● [cho exit section] quá trình vào exit section sẽ vào remaindersection13Phân loại giải pháp cho bài toán loại trừtương hỗCó thể giải bài toán loại trừ tương hỗ?Giải pháp dùng lệnh máy thông thườngGiải pháp dùng lệnh cấm ngắt hay lệnh máy đặc biệt● Lệnh Disable interrupt● Lệnh máy đặc biệt như TestAndSet14Giải pháp dùng lệnh máy thông thườngGiải pháp cho 2 process● Giải thuật 1 và 2● Giải thuật Peterson cho 2 processGiải pháp cho nhiều process● Giải thuật bakery15Giải thuật 1[1/2]Biến chia sẻ• int turn;/* khởi đầu turn = 0 */• nếu turn = i thì Pi được phép vào critical section, với i = 0 hay 1Process Pido {while [turn != i];critical sectionturn = j;remainder section} while [1];Giải thuật thoả mãn mutual exclusion [1], nhưng khôngthoả mãn tính chất progress [2], xem slide tới.16Giải thuật 1[2/2]Mã của mỗi quá trìnhProcess P0do {while [turn != 0];critical sectionturn := 1;remainder section} while [1];Process P1do {while [turn != 1];critical sectionturn := 0;remainder section} while [1];Giải thuật không thỏa mãn tính chất Progress cho entrysection:Nếu turn = 0, P0 được vào CS và sau đó gán turn = 1 và vào remaindersection [RS]; giả sử P0 “ở lâu” trong đó.Trong khi đó P1 vào CS và sau đó gán turn = 0, kế đó P1 vào và xongRS, vào lại entry section để đợi vào CS một lần nữa; nhưng vì turn = 0 nênP1 phải chờ P0.17Giải thuật 2Biến chia sẻboolean flag[ 2 ];/* khởi đầu flag[ 0 ] = flag[ 1 ] = false */● Nếu Pi ghi flag[ i ] = true thì nó “muốn” vào critical section flag[ i ] = false thì nó chưa muốn vào critical sectionProcess Pido {flag[ i ] = true;while [flag[ j ]];critical sectionflag[ i ] = false;remainder section} while [1];18Giải thuật 2 [tiếp]Mã của mỗi quá trìnhProcess P0Process P1do {do {flag[ 0 ] = true;while [flag[ 1 ]];critical sectionflag[ 0 ] = false;remainder section} while [1];flag[ 1 ] = true;while [flag[ 0 ]];critical sectionflag[ 1 ] = false;remainder section} while [1];- Bảo đảm được mutual exclusion. Chứng minh?- Không thỏa mãn progress cho entry section. Vì sao? Chứng minhbằng phản chứng. Nếu đồng thờiP0 gán flag[ 0 ] = true vàP1 gán flag[ 1 ] = true P0 và P1 sẽ loop mãi mãi trong vòng lặp while19Giải thuật Peterson cho 2 process [1/2]Biến chia sẻ: kết hợp từ giải thuật 1 và 2Process Pi , với i = 0 hay 1do {flag[ i ] = true; // Process i ‘muốn’ vào vùng tranh chấpturn = j;// ‘Nhường’ process jwhile [flag[ j ] and turn == j];critical sectionflag[ i ] = false;remainder section} while [1];20Giải thuật Peterson cho 2 process [2/2]Mã của mỗi quá trìnhProcess P0Process P1do {flag[0] = true;turn = 1;while [flag[1] &&turn == 1];critical sectionflag[0] = false;remainder section} while[1];do {flag[1] = true;turn = 0;while [flag[0] &&turn == 0];critical sectionflag[1] = false;remainder section} while[1];21Giải thuật Peterson cho 2 process: Tínhđúng đắnMutual exclusion được bảo đảm● Chứng minh bằng phản chứng• Nếu P0 và P1 cùng ở trong CS thì flag[0] = flag[1] = true, suy ratừ điều kiện của vòng lặp while sẽ có turn = 0 [trong P0] và turn= 1 [trong P1]. Điều không thể xảy ra.Chứng minh thỏa yêu cầu về progress và starvationfreedom● Xem textbook22Giải thuật bakery [1/3]Cho nhiều processTrước khi vào CS, process Pi nhận một con số, và sẽ đểcác process có số nhỏ hơn [nhưng  0] vào CS trước● Trường hợp Pi và Pj nhận được cùng một con số: Nếu i < j thì Pi được vào CS trướcKhi xong CS, Pi gán số của mình bằng 0● Cách cấp số cho các process thường tạo các số tăng dần, ví dụ1, 2, 3, 3, 3, 3, 4, 5,…Kí hiệu● [a,b] < [c,d] nếu a < c hoặc nếu a = c và b < d● max[a0,…,ak ]: số lớn nhất trong {a0,…,ak}23Giải thuật bakery [2/3]Process Pi, i = 0 .. n - 1/* shared variable */booleanchoosing[ n ]; /* initially, choosing[ i ] = false */intnum[ n ];/* initially, num[ i ] = 0*/do {choosing[ i ] = true;num[ i ]= max[num[0], num[1],…, num[n  1]] + 1;choosing[ i ] = false;for [ j = 0; j < n; j++] {while [choosing[ j ]];while [[num[ j ] != 0] && [num[ j ], j] < [num[ i ], i]] ;}critical sectionĐợi quá trình có sốnum[ i ] = 0;nhỏ hơn xong CS,remainder sectionnhưng vượt qua quá} while [1];trình có số lớn hơn24Giaỷi thuaọt bakery [3/3]Giaỷi thuaọt bakery baỷo ủaỷm Mutual exclusion Progress Starvation freedom[Khoõng chửựng minh]25

-1-Chương 7 Đồng Bộ vàGiải Quyết Tranh Chấp[Process Synchronization] Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM2Nội dungKhái niệm cơ bảnCritical section Các giải pháp phần mềm–Giải thuật Peterson, và giải thuật bakeryĐồng bộ bằng hardwareSemaphoreCác bài toán đồng bộCritical regionMonitor Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM3Khái niệm cơ bả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.Ví dụ: bounded buffer [ch. 4], thêm biến đếm count#define BUFFER_SIZE 10 /* 10 buffers */typedef struct {. . . } item;item buffer[BUFFER_SIZE];int in = 0, out = 0, count = 0; Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM4Bounded buffer [tt] Quá trình Produceritem nextProduced;while[1] {while [count == BUFFER_SIZE]; /* do nothing */buffer[in] = nextProduced;count++;in = [in + 1] % BUFFER_SIZE;}Quá trình Consumeritem nextConsumed;while[1] {while [count == 0]; /* do nothing */nextConsumed = buffer[out] ; count ;out = [out + 1] % BUFFER_SIZE;}biến count được chia sẻgiữa producer và consumer Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM5Bounded 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 registeri là các thanh ghi của CPU. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM6Bounded 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 sau có thể xảy ra:•0: producer register1 := count {register1 = 5}1: producer register1 := register1 + 1 {register1 = 6}2: consumer register2 := count {register2 = 5}3: consumer register2 := register2 - 1 {register2 = 4}4: producer count := register1 {count = 6}5: consumer count := register2 {count = 4}Cả hai process thao tác đồng thời lên biến chung count. Trò của biến chung này không nhất quán dưới các thao tác của hai process. 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. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM7Bounded 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]–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. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM8Khái niệm Critical SectionGiả sử có n process cùng truy xuất đồng thời dữ liệu chia sẻKhông phải tất cả các đoạn code đều cần được giải quyết vấn đề race condition mà chỉ 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].Vấn đề: 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. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM9Cấu trúc tổng quátGiả sử mỗi process thực thi bình thường [i.e., nonzero speed] và không có sự tương quan giữa tốc độ thực thi của các processCấu trúc tổng quát của một process:Một số giả đònhCó thể có nhiều CPU nhưng không cho phép có nhiều tác vụ truy cập một vò trí trong bộ nhớ cùng lúc [simultaneous]Không ràng buộc về thứ tự thực thi của các processCác process có thể chia sẻ một số biến chung nhằm mục đích đồng bộ hoạt động của chúngGiải pháp của chúng ta cần phải đặc tả được các phần entry section và exit sectiondo { critical section remainder section} while[1];entry sectionexit section Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM10Lời giải của bài toán tranh chấp •Lời giải phải thỏa ba tính chất[1] 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: 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 là ứng cử viên cho việc được chọn vào vùng tranh chấp. –Quá trình chọn lựa này không được trì hoãn vô hạn [postponed indefinitely].•[3] 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]. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM11Phân loại giải phápGiải pháp phần mềm [software solutions]–user/programmer tự thực hiện [thông thường sẽ có sự hỗ trợ của các thư viện lập trình]–OS cung cấp một số công cụ [các hàm và cấu trúc dữ liệu] hỗ trợ cho programmer qua system calls.Giải pháp phần cứng [hardware solutions]–Dựa trên một số lệnh máy đặc biệt• Disable interrupt•TestAndSet Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM12Giải pháp phần mềmTrường hợp 2 process đồng thời: P0 và P1–Giải thuật 1 và 2–Giải thuật 3 [Peterson’s algorithm]Giải thuật cho n process–Bakery algorithm Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM13Giải thuật 1Biến chia sẻ•int turn; /* khởi đầu turn = 0 */•nếu turn = i thì Pi được phép vào critical section, với i = 0 hay 1Process Pi do {while [turn != i];critical sectionturn = j;remainder section } while [1];Thoả mãn mutual exclusion [1]Nhưng không thoả mãn yêu cầu về progress [2] và bounded waiting [3] vì tính chất strict alternation của giải thuật Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM14Process P0:do while [turn != 0];critical section turn := 1;remainder sectionwhile [1];Process P1:do while [turn != 1];critical section turn := 0;remainder sectionwhile [1];Ví dụ: P0 có RS [remainder section] rất lớn còn P1 có RS nhỏ. Nếu turn = 0, P0 được vào CS và sau đó thực thi turn = 1 và vào vùng RS.Lúc đó P1 vào CS và sau đó thực thi turn = 0, kế đó P1 vào và xong RS, và đợi vào CS một lần nữa, nhưng vì turn = 0 nên P1 phải chờ P0.Giải thuật 1 [tt] Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM15Giải thuật 2Biến chia sẻ•boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */•Nếu flag[ i ] = true thì Pi “sẵn sàng” vào critical section.Process Pi do {flag[ i ] = true; /* Pi “sẵn sàng” vào CS */while [ flag[ j ] ]; /* Pi “nhường” Pj */critical sectionflag[ i ] = false;remainder section } while [1];Bảo đảm được mutual exclusion. Chứng minh?Không thỏa mãn progress. Vì sao? Trường hợp sau có thể xảy ra:•P0 gán flag[ 0 ] = true•P1 gán flag[ 1 ] = true•P0 và P1 loop mãi mãi trong vòng lặp while Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM16Giải thuật 3 [Peterson]Biến chia sẻ: kết hợp cả giải thuật 1 và 2Process Pi , với i = 0 hay 1do {flag[ i ] = true; /* Process i sẵn sàng */turn = j; /* Nhường process j */while [flag[ j ] and turn == j];critical sectionflag[ i ] = false;remainder section} while [1];Thoả mãn được cả 3 yêu cầu [chứng minh?] ⇒ giải quyết bài toán critical section cho 2 process. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM17Process P0do { /* 0 wants in */ flag[0] = true; /* 0 gives a chance to 1 */ turn = 1; while [flag[1] && turn == 1]; critical section /* 0 no longer wants in */ flag[0] = false; remainder section} while[1];Process P1do { /* 1 wants in */ flag[1] = true; /* 1 gives a chance to 0 */ turn = 0; while [flag[0] && turn == 0]; critical section /* 1 no longer wants in */ flag[1] = false; remainder section} while[1];Giải thuật Peterson-2 process Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM18Giải thuật 3: Tính đúng đắn•Giải thuật 3 thỏa mutual exclusion, progress, và bounded waitingMutual exclusion được bảo đảm bởi vì •P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = i cho mỗi Pi [không thể xảy ra]Chứng minh thỏa yêu cầu về progress và bounded waiting–Pi không thể vào CS nếu và chỉ nếu bò kẹt tại vòng lặp while[] với điều kiện flag[ j ] = true và turn = j .–Nếu Pj không muốn vào CS thì flag[ j ] = false và do đó Pi có thể vào CS. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM19Giải thuật 3: Tính đúng đắn [tt]–Nếu Pj đã bật flag[ j ] = true và đang chờ tại while[] thì có chỉ hai trường hợp là turn = i hoặc turn = j–Nếu turn = i thì Pi vào CS. Nếu turn = j thì Pj vào CS nhưng sẽ bật flag[ j ] = false khi thoát ra ⇒ cho phép Pi vào CS–Nhưng nếu Pj có đủ thời gian bật flag[ j ] = true thì Pj cũng phải gán turn = i–Vì Pi không thay đổi trò của biến turn khi đang kẹt trong vòng lặp while[], Pi sẽ chờ để vào CS nhiều nhất là sau một lần Pj vào CS [bounded waiting] Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM20Giải thuật bakery: n processTrước khi vào CS, process Pi nhận một con số. Process nào giữ con số nhỏ nhất thì được vào CSTrường hợp Pi và Pj cùng nhận được một chỉ số: –Nếu i < j thì Pi được vào trước. [Đối xứng]Khi ra khỏi CS, Pi đặt lại số của mình bằng 0Cơ chế cấp số cho các process thường tạo các số theo cơ chế tăng dần, ví dụ 1, 2, 3, 3, 3, 3, 4, 5,…Kí hiệu•[a,b] < [c,d] nếu a < c hoặc if a = c và b < d•max[a0,…,ak] là con số b sao cho b ≥ ai với mọi i = 0,…, k Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM21Giải thuật bakery: n process [tt]/* shared variable */boolean choosing[ n ]; /* initially, choosing[ i ] = false */int num[ n ]; /* initially, num[ i ] = 0 */do {choosing[ i ] = true;num[ i ] = max[num[0], num[1],…, num[n − 1]] + 1;choosing[ i ] = false;for [j = 0; j < n; j++] { while [choosing[ j ]]; while [[num[ j ] != 0] && [num[ j ], j] < [num[ i ], i]];} critical sectionnum[ i ] = 0; remainder section} while [1]; Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM22Từ software đến hardwareKhuyết điểm của các giải pháp software–Các process khi yêu cầu được vào vùng tranh chấp đều phải liên tục kiểm tra điều kiện [busy waiting], tốn nhiều thời gian xử lý của CPU–Nếu thời gian xử lý trong vùng tranh chấp lớn, một giải pháp hiệu quả nên có cơ chế block các process cần đợi.Các giải pháp phần cứng [hardware]–Cấm ngắt [disable interrupts]–Dùng các lệnh đặc biệt Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM23Cấm ngắtTrong hệ thống uniprocessor: mutual exclusion được bảo đảm.–Nhưng nếu system clock được cập nhật do interrupt thì …Trên hệ thống multiprocessor: mutual exclusion không được đảm bảo–Chỉ cấm ngắt tại CPU thực thi lệnh disable_interrupts–Các CPU khác vẫn có thể truy cập bộ nhớ chia sẻProcess Pi:do { disable_interrupts[]; critical section enable_interrupts[]; remainder section} while [1]; Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM24Dùng các lệnh đặc biệtÝ tưởng cơ sở –Việc truy xuất vào vào một đòa chỉ của bộ nhớ vốn đã có tính loại trừ tương hỗ [chỉ có một thao tác truy xuất tại một thời điểm]Mở rộng–thiết kế một lệnh máy có thể thực hiện hai thao tác chập [atomic, indivisible] trên cùng một ô nhớ [vd: read và write]–Việc thực thi các lệnh máy như trên luôn bảo đảm mutual exclusive [ngay cả với hệ thống multiprocessor] Các lệnh máy đặc biệt có thể đảm bảo mutual exclusion tuy nhiên cũng cần kết hợp với một số cơ chế khác để thoả mãn hai yêu cầu còn lại là progress và bounded waiting cũng như tránh tình trạng starvation và deadlock. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM25Lệnh TestAndSetĐọc và ghi một biến trong một thao tác atomic [không chia cắt được].boolean TestAndSet[boolean &target] { boolean rv = target; target = true; return rv;} Shared data: boolean lock = false; Process Pi : do { while [TestAndSet[lock]]; critical section lock = false; remainder section } while [1];