Thủ Thuật Hướng dẫn Remainder section là gì Mới Nhất
Bann đang tìm kiếm từ khóa Remainder section là gì 2022-04-11 17:32:08 san sẻ Thủ Thuật Hướng dẫn trong nội dung bài viết một cách 2022.
Ñoàng Boä Quaù Trình1Nội dungKhá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ì● Giải thuật Peterson, và giải thuật bakeryCác giải pháp dùng lệnh cấm ngắt hoặc lệnh máy đặcbiệtSemaphoreSemaphore và những bài toán đồng bộMonitor2Bài toán đồng điệu (1/2)•Khảo sát những process/thread thực thi đồng thời và chiasẻ tài liệu (như ghi shared memory) trong khối mạng lưới hệ thống● uniprocessor, hoặc● shared memory multicore/multiprocessorNếu không tồn tại sự trấn áp khi truy vấn những tài liệu chiasẻ thì chúng trọn vẹn có thể trỡ nên không nhất quán.Để duy trì sự nhất quán tài liệu, khối mạng lưới hệ thống nên phải có cơ chếbảo đảm sự thực thi có trật tự của những process đồng thời3Bài toán đồng điệu (2/2)Hai lớp bài toán đồng điệu:● 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 quy trình sử dụngmột tài nguyên không san sẻ đồâng thời được (= chỉ có thểđược sử dụng lần lượt bởi những quy trình) Bài toán Dining Philosophers4“Đồng thời” gồm có “tuy nhiên tuy nhiên”Trên uniprocessor hay trên shared memorymultiprocessor, những quy trình chạy đồng thờiTrên shared memory multiprocessor, những quy trình cóthể chạy tuy nhiên 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 tự 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 những lệnh tăng và giảm biến count trọn vẹn có thể thực thi xen kẽGiả sử count đang bằng 5. Chuỗi thực thi sau trọn vẹn có thể xẩy ra:1:producerregister1 := countregister1 = 5producerregister1 := register1 + 1register1 = 6consumerregister2 := countregister2 = 5consumerregister2 := register2 – 1register2 = 43:producercount := register1count = 64:consumercount := register2count = 42:Cả hai process thao tác đồng thời lên biến chung count. Trò của biếnchung này sẽ không nhất quán dưới những thao tác của hai process.Giải pháp: những lệnh count++, count– phải là đơn nguyên (atomic),nghóa là tiến hành như một lệnh đơn, không thực thi xen kẽ nhau.9Race conditionRace condition: trường hợp khi nhiều process truy xuất vàthao tác đồng thời lên tài liệu san sẻ (như biến count);kết quả ở đầu cuối của việc truy xuất đồng thời này phụthuộc thứ tự thực thi của những lệnh (máy) thao tác lên dữliệu.Để tài liệu san sẻ bởi quy trình Producer và Consumerđược nhất quán, cần bảo vệ bảo vệ an toàn sao cho những process lầnlượt thao tác lên tài liệu san sẻ. Do đó, nên phải có cơ chếđồng bộ hoạt động giải trí và sinh hoạt của những process này.10Khái niệm critical sectionGiả sử có nhiều process đồng thời truy xuất tài liệu chiasẻ.Giải quyết yếu tố race condition cho những đoạn codecó chứa những thao tác lên tài liệu san 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 vệ bảo vệ an toàn sự loại trừ tươnghỗ (mutual exclusion, mutex), tức là lúc một process Pđang thực thi trong CS của P, không tồn tại process Q. nàokhác đồng thời thực thi những lệnh trong CS của Q..11Cấu trúc tổng quát của quy 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 những process Các process trọn vẹn có thể chia sẻmột số biến chung nhằm mục tiêu đồngbộ hoạt động giải trí và sinh hoạt 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ối thiểu một process đang trongentry section và không tồn tại process nào đang trong critical section,thì một process vào critical section tại thuở nào gian tiếp sau đó● (Progress cho exit section) Nếu tối thiểu một process đang trongexit section, thì một process vào remainder section tại một thờiđiểm tiếp sau đó•3. Starvation freedom (Không bò “bỏ đói”)● (cho entry section) quy trình vào entry section sẽ vào CS● (cho exit section) quy 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 quan trọng● Lệnh Disable interrupt● Lệnh máy đặc biệt quan trọng như TestAndSet14Giải pháp dùng lệnh máy thường thìGiải pháp cho 2 process● Giải thuật 1 và 2● Giải thuật Peterson cho 2 processGiải pháp cho nhiều process● Giải thuật bakery15Giải thuật 1(1/2)Biến san 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 là một trong nhữngProcess 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 thị hiếu tính chất Progress cho entrysection:Nếu turn = 0, P0 được vào CS và tiếp sau đó gán turn = 1 và vào remaindersection (RS); giả sử P0 “ở lâu” trong số đó.Trong khi đó P1 vào CS và tiếp 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 2Biế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ó đang chưa muốn vào critical sectionProcess 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 quy trìnhProcess P0Process 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 thị hiếu 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 san sẻ: phối 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 đắnMutual exclusion được bảo vệ bảo vệ an toàn● 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ừ Đk của vòng lặp while sẽ đã có đượ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 số lượng, 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 số lượng: Nếu i < j thì Pi được vào CS trướcKhi xong CS, Pi gán số của tớ bằng 0● Cách cấp số cho những process thường tạo những 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 số 1 trong a0,…,ak23Giả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 quy 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 dungKhái niệm cơ bảnCritical section Các giải pháp ứng dụng–Giải thuật Peterson, và giải thuật bakeryĐồng bộ bằng hardwareSemaphoreCác bài toán đồng điệuCritical regionMonitor 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 những process/thread thực thi đồng thời và san sẻ tài liệu (qua shared memory, file).Nếu không tồn tại sự trấn áp khi truy vấn những tài liệu san sẻ thì trọn vẹn có thể đưa tới ra trường hợp không nhất quán tài liệu (data inconsistency).Để duy trì sự nhất quán tài liệu, khối mạng lưới hệ thống nên phải có cơ chế bảo vệ bảo vệ an toàn sự thực thi có trật tự của những 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 tự trong ngôn từ máy là:•(Producer) count++:•register1 = count•register1 = register1 + 1•count = register1•(Consumer) count :•register2 = count•register2 = register2 – 1•count = register2Trong số đó, những registeri là những 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 những lệnh tăng và giảm biến count trọn vẹn có thể bò thực thi xen kẽGiả sử count đang bằng 5. Chuỗi thực thi sau trọn vẹn có thể xẩy ra:•0: producer register1 := count register1 = 51: producer register1 := register1 + 1 register1 = 62: consumer register2 := count register2 = 53: consumer register2 := register2 – 1 register2 = 44: producer count := register1 count = 65: consumer count := register2 count = 4Cả hai process thao tác đồng thời lên biến chung count. Trò của biến chung này sẽ không nhất quán dưới những thao tác của hai process. Giải pháp: những lệnh count++, count phải là đơn nguyên (atomic), nghóa là tiến hành 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 tài liệu san sẻ (như biến count)–Kết quả ở đầu cuối của việc truy xuất đồng thời này phụ thuộc thứ tự thực thi của những lệnh thao tác tài liệu.Để tài liệu san sẻ được nhất quán, cần bảo vệ bảo vệ an toàn sao cho tại mỗi thời gian chỉ có một process được thao tác lên tài liệu san sẻ. Do đó, nên phải có cơ chế đồng điệu hoạt động giải trí và sinh hoạt của những process này. Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM8Khái niệm Critical SectionGiả sử có n process cùng truy xuất đồng thời tài liệu san sẻKhông phải toàn bộ những đoạn code đều nên phải xử lý và xử lý yếu tố race condition mà chỉ những đoạn code có chứa những thao tác lên tài liệu san sẻ. Đoạn code này được gọi là vùng tranh chấp (critical section, CS).Vấn đề: phải bảo vệ bảo vệ an toàn sự loại trừ tương hỗ (mutual exclusion, mutex), tức là lúc một process đang thực thi trong vùng tranh chấp, không tồn tại process nào khác đồng thời thực thi những 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átGiả sử mỗi process thực thi thường thì (i.e., nonzero speed) và không tồn tại sự tương quan giữa vận tốc thực thi của những processCấu trúc tổng quát của một process:Một số giả đònhCó thể có nhiều CPU nhưng không được cho phép có nhiều tác vụ truy vấn 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 những processCác process trọn vẹn có thể san sẻ một số trong những biến chung nhằm mục tiêu mục tiêu đồng điệu hoạt động giải trí và sinh hoạt của chúngGiải pháp của toàn bộ chúng ta nên phải đặc tả được những 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 tồn tại process Q. nào khác đang thực thi trong CS của Q..(2) Progress: nếu không tồn tại process nào đang thực thi trong vùng tranh chấp và đang sẵn có một số trong những process chờ đón 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 viên cho việc được chọn vào vùng tranh chấp. –Quá trình lựa chọn này sẽ 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 chừng thời hạn hạn chế đò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ápGiải pháp ứng dụng (software solutions)–user/programmer tự tiến hành (thường thì sẽ đã có được sự tương hỗ của những thư viện lập trình)–OS phục vụ nhu yếu một số trong những công cụ (những hàm và cấu trúc tài liệu) tương hỗ cho programmer qua system calls.Giải pháp phần cứng (hardware solutions)–Dựa trên một số trong những lệnh máy đặc biệt quan trọng• Disable interrupt•TestAndSet Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM12Giải pháp ứng dụngTrườ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 1Biến san 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 là một trong nhữngProcess 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 rộng còn P1 có RS nhỏ. Nếu turn = 0, P0 được vào CS và tiếp sau đó thực thi turn = 1 và vào vùng RS.Lúc đó P1 vào CS và tiếp 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 2Biến san 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 thị hiếu progress. Vì sao? Trường hợp sau trọn vẹn 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 san sẻ: phối hợp cả giải thuật 1 và 2Process 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 tỏ?) ⇒ xử lý và xử lý 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 waitingMutual exclusion được bảo vệ bảo vệ an toàn chính vì •P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = i cho từng 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 Đk flag[ j ] = true và turn = j .–Nếu Pj không thích vào CS thì flag[ j ] = false và do đó Pi trọn vẹn 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 ⇒ được cho phép Pi vào CS–Nhưng nếu Pj có đủ thời hạn 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 processTrước khi vào CS, process Pi nhận một số lượng. Process nào giữ số lượng nhỏ nhất thì được vào CSTrườ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 thoát khỏi CS, Pi đặt lại số của tớ bằng 0Cơ chế cấp số cho những process thường tạo những 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à số lượng 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 hardwareKhuyết điểm của những 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 Đk (busy waiting), tốn nhiều thời hạn xử lý của CPU–Nếu thời hạn xử lý trong vùng tranh chấp lớn, một giải pháp hiệu suất cao nên có cơ chế block những process cần đợi.Các giải pháp phần cứng (hardware)–Cấm ngắt (disable interrupts)–Dùng những lệnh đặc biệt quan trọng Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa TP HCM23Cấm ngắtTrong khối mạng lưới hệ thống uniprocessor: mutual exclusion được bảo vệ bảo vệ an toàn.–Nhưng nếu system clock được update do interrupt thì …Trên khối mạng lưới 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 trọn vẹn có thể truy vấn 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 những lệnh đặc biệt quan trọngÝ tưởng cơ sở –Việc truy xuất vào vào một trong những đòa chỉ của cục nhớ vốn đã có tính loại trừ tương hỗ (chỉ có một thao tác truy xuất tại thuở nào gian)Mở rộng–thiết kế một lệnh máy trọn vẹn có thể tiến hành hai thao tác chập (atomic, indivisible) trên cùng một ô nhớ (vd: read và write)–Việc thực thi những lệnh máy như trên luôn bảo vệ bảo vệ an toàn mutual exclusive (trong cả với khối mạng lưới hệ thống multiprocessor) Các lệnh máy đặc biệt quan trọng trọn vẹn có thể đảm bảo mutual exclusion tuy nhiên cũng cần được kết thích phù hợp với một số trong những cơ chế khác để thoả mãn hai yêu cầu còn sót 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); Video tương quan |
Chia sẻ
đoạn Clip Remainder section là gì ?
Một số hướng dẫn một cách rõ ràng hơn về đoạn Clip Remainder section là gì tiên tiến và phát triển nhất .
Chia SẻLink Tải Remainder section là gì miễn phí
Người Hùng đang tìm một số trong những ShareLink Download Remainder section là gì Free.
#Remainder #section #là #gì