Thảo luận Bài 7

Đồng bộ hóa công việc của các tiến trình để các tiến trình chạy một cách có trật tự, đảm bảo tính nhất quán của tài nguyên dùng dung.

Nhất quán: Có chờ lẫn nhau. Ví dụ: nhà sản xuất chưa hoàn tất tính toán nhà tiêu thụ đã lấy sản phẩm dẫn đến kết quả sai, không đảm bảo tính toàn vẹn.

Tài nguyên dùng chung: là các mảng buffer ( bài toán sản xuất và tiêu thụ )

Nếu như các luồng làm việc không đúng trật tự, không đúng công việc sẽ dẫn đến kết quả sai. Ví dụ hàm sleep để trễ một chút, để đồng bộ ).

Đồng bộ hóa tránh được tình trạng dead clock: các tiến trình rơi vào trạng thái treo không làm việc được.

Ví dụ bài toán sản xuất tiêu thụ có biến count để đếm số sản phẩm trong bộ đệm, gán bằng 0 khi chưa có sản phẩm nào.
vòng lặp lẩn quẩn bên trong khi count =0 và chờ đến khi count !=0 tức là có sản phẩm thì nhà tiêu thụ mới lấy về.
kiểm tra chỗ trống để xếp vào bộ đệm.
Nhà sản xuất không được xếp thêm vào bộ đệm nếu như không còn chỗ trống, nhà tiêu thụ không được lấy sản phẩm khi không có sản phẩm nào trong bộ đệm. Công việc của nhà sản xuất nhà tiêu thụ được đồng bộ hóa.

Các tiến trình p0,p1,pn-1 cùng làm việc song song, đồng hành lẫn nhau ( gọi là miền găng ).
Khi chúng hoạt động, chúng tác động, thay đổi tài nguyên dùng chung,những lệnh trong đoạn tương tranh ảnh hưởng đến các biến, tài nguyên dùng chung.
Các tiến trình tương tranh có đoạn đăng nhập, đăng xuất và đoạn còn lại

Để ngăn chặn các tình huống lỗi có thể xảy ra thì:
Mutual Exclusion: tính loại trừ lẫn nhau.

A: đang làm việc.
B: không được thực hiện.
A làm B nghỉ ( bắt buộc )

Nếu không sẽ có 2 người ghi lên bảng cùng lúc, phải bảo đảm có 1 người ghi, một người chụp nếu không 2 tiến trình cùng tác động, ảnh hưởng đến tài nguyên( theo ví dụ của Thầy)
Mỗi thời điểm chỉ có một mà thôi.

Một tiến trình 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.

Không có tiến trình nào phải chờ vô hạn để được vào miền găng.

08H1010052 đã viết:

TrinhThiOanh (I11C) đã viết:

DaoQuangSieu (I11C) đã viết:

phamdieptuan (I11C) đã viết:câu 4: đồng bộ hóa công việc của P1, P2, P3. sao cho:
a) P1 trước P2, P2 trước P3?
b) P1 trước P2 và P3?
c) P1 và P2 trước P3?

Giải:
Giả sửa có 3 tiến trình P1, P2 và P3 có mã tương ứng là S1, S2 và S3

a) P1 trước P2, P2 trước P3
Semaphore synch1 = 0, synch2 = 0;

P1	P2	P3
S1	wait(synch1);	wait(synch2);
signal(synch1);	S2 signal(synch2);	S3

Khi P1 dc thực hiện, thì P2 bị khóa tại hàm wait(synch1) do synch1=0; P3 bị khóa tại hàm wait(synch2) do synch2=0. Sau khi S1 dc thi hành thì synch1 sẽ tăng lên 1 do signal(synch1).
Lúc này P2 sẽ dc thực hiện(synch1 =1), nhưng P3 vẫn bị khóa do synch2 =0, sau khi S2 thi hành xong thì synch2 =1(signal(synch2)) lúc này P3 mới dc thực hiện.
=> P1 trước P2, P2 trước P3.

b) P1 trước P2 và P3
Semaphore synch = 0;

P1	P2	P3
S1	wait(synch);	wait(synch);
signal(synch, 2);	S2	S3

Tại thời điểm ban đầu: synch=0,
Khi tiến trình P2 được thực hiện, thì P2 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi tiến trình P3 được thực hiện, thì P3 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi P1 thực hiện ,S1 được thi hành xong thì lệnh signal(synch, 2); dc thực thi, tức là tăng synch = 2.
Khi đó synch>0 ,tiến trình P2 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=1).
Đồng thời P3 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=0).
->P2 và P3 cùng thực hện.
=>P1 đi trước P2 và P3.

c) P1 và P2 trước P3
Semaphore synch = -1;

P1	P2	P3
S1	S2	wait(synch);
signal(synch);	signal(synch);	S3

Tại thời điểm ban đầu: P1 và P2 đang thực hiện lệnh S1, S2, lúc này synch=-1.
Lúc này P3 đang bị khóa tại hàm wait(synch) đợi khi synch >0.
Khi P1 thực hiện, S1 dc thi hành xong thì hàm signal(synch) sẽ tăng synch lên 1 và synch= 0. P3 lúc này vẫn bị khóa do synch=0.
Khi P2 thực hiện, S2 dc thi hành xong thì hàm signal(synch) sẽ tăng synch lên 1 và synch= 1.
Lúc này P3 mới dc thực hiện.
=>P1 và P2 trước P3.

Mong thầy và các bạn góp ý.

Đề nghị bạn giải thích rõ câu b giùm. Mình chưa hiểu rõ !!! THANKS

Mình cũng giống như bạn khi đọc giải thích câu b mình khó hiểu lắm.
Qua tìm hiểu mình xin góp ý bổ sung giải thích như sau:

Tại thời điểm ban đầu: synch=0,

Khi tiến trình P2 được thực hiện, thì P2 sẽ bị khóa tại hàm wait(synch) do synch=0 tức là bị khóa tại hàm kiểm tra điều kiện while (S<=0) Hàm này sẽ kiểm tra synch đã lớn hơn 0 chưa và chờ cho đến khi synch>0 thì hàm S2 sẽ được thực hiện.

Khi tiến trình P3 được thực hiện, thì P3 sẽ bị khóa tại hàm wait(synch) do synch=0 tức là bị khóa tại hàm kiểm tra điều kiện while (S<=0) Hàm này sẽ thường xuyên kiểm tra synch đã lớn hơn 0 chưa và chờ cho đến khi synch>0 thì hàm S3 sẽ được thực hiện.

Các bạn góp ý thêm để hoàn thiện bài này hơn nha.

Mình xin giải thích theo cách hiểu của mình như sau:
Đầu tiên ta có 3 tiến trình P1,P2,P3 giả sử đã được cấp CPU và thực hiện. Đối với P2 và P3 thì khi ban đầu khởi tạo nhận được lệnh Wait với giá trị synch=0 nên 2 tiến trình này sẽ nằm chờ không thực hiện mã s2,s3.
Còn P1 thì theo cấu trúc mã sẽ không nhận lệnh Wait khi thực hiện nên sẽ lập tức thực hiện liền mã s1. Sau đó nhận lệnh Signal nhưng với tham số synch tăng lên 2 đơn vị (synch từ giá trị ban đầu là 0 -> 2) và kết thúc tiến trình P1.
* Vấn đề là tại điểm này: nếu ta hiểu theo thứ tự ban đầu P2 được khởi tạo và được xếp vào hàng chờ theo thuật toán điều phối của HĐH trước P3 thì sẽ có kết quả như trên, nghĩa là:
=> synch=2 và Wait(synch) của P2 trong hàng chờ sẽ kiểm tra điều kiện(synch lúc này sẽ được giãm 1 đơn vị synch=1) và thực hiện mã s2 và kết thúc tiến trình P2
=> Tùy theo thuật toán có tiếm quyền hay không thì lúc này synch=1 P3 được cấp CPU để running sau P2, khi đó Wait của P3 kiểm tra điều kiện và thực hiện mã s3 và kết thúc tiến trình cuối cùng P3.
* Mở rộng thêm: nếu ta hiểu cả 3 tiến trình P1,2,3 được cấp CPU cùng lúc thì trạng thái P2,3 lúc này đang chờ tại Wait => lúc này do HĐH quản lý tiến trình, tùy theo tiến trình nào mà HĐH cấp trước thì làm trước.
Nếu chúng ta muốn quản lý thứ tự thì chúng ta sẽ dùng 2 biến synch tương ứng cho P1:synch1=0 và P2:synch2=0 như cách giải của câu (a) phía trên. Tùy theo ý thích mà ta sẽ thay đổi synch tương ứng cho các tiến trình tương ứng (ví dụ: muốn chạy P3 trước thì Signal tại P1 sẽ tăng giá trị synch3=1. Ngược lại chạy P2 thì tăng synch2=1).
Trên đây là cách hiểu của mình. Mong Thầy và các bạn góp ý thêm.
Cám ơn Thầy và các bạn!

Thanks bạn, mình cảm thấy giải thích câu b vậy là ok.Cũng cảm ơn các bạn khác đã chia sẽ thông tin.

Khai báo :
Semaphore semEmpty=10, semFull=0, critsec=1;

Thuật giải dành cho nhà sản xuất :producer

Wait(semEmpty);
Wait(critsec);
Đưa sản phẩm vào bộ nhớ đệm
Signal(semFull);
Signal(critsec);


Thuật giải dành cho nhà tiêu thụ : Consumer

Wait(semFull);
Wait(critsec);
Lấy sp ra khỏi bộ nhớ đệm
Signal(semEmpty);
Signal(critsec);

semEmpty : biến dùng để chứa mục quản của đèn hiệu , quản lí số vùng trống trong vùng đệm.

semFull : biến dùng để chứa mục quản của đèn hiệu quản lí số sản phẩm trong bộ đệm.

critSec: biến kiểu đoạ. Tương tranh dùng để chứa đối tượng đèn hiệu Mutex


( vào thư mục Hedieuhanh\tuhoc\sanxuattieuthuC#.NET2005\sanxuattieuthu2005.sln để xem chương trình của thầy )

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAK_SECTION critsec; //Biến kiểu Mutex
void Producer(void* P)
{
while (1)
{
//..sản xuất(nẽtProduced)
//chờ đến khi có chổ trống.
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critsec);
//sắp sản phẩm vào buffer
//tăng (semFull) lên 1.
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critsec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumer;
while (1)
{
//cho den khi co san pham
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critsec);
nextConsumer =Buffer[out];
out =(out+1)%BUFFER_SIZE;
//tang (semEmpty )len 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critsec);
//tieu thu(nextConsumer)
SuspendThread(GetCurrentThread());


}
}

/*- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm
*- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm
*- critset là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo
* tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

1. Giới thiệu Trong cơ sở dữ liệu (CSDL) thời gian thực, điều khiển tương tranh không chỉ duy trì các ràng buộc nhất quán của CSDL mà còn thoả mãn các yêu cầu về thời gian của các giao tác truy nhập CSDL. Các thuật toán điều khiển tương tranh [6] và lập lịch [8] đã được nhiều người nghiên cứu ([6], [8]). Sự phát triển của giao thức khoá thời gian thực thường bao gồm lập lịch ưu tiên kết hợp giao thức khoá. Ví dụ, chúng ta có thể sử dụng khoá hai pha để điều khiển tương tranh và sử dụng thuật toán hạn sớm nhất (earliest deadline) để thiết kế các mức ưu tiên cho các giao tác. Rất tiếc, việc thực hiện này có thể dẫn đến không kiểm soát được sự đảo ngược mức ưu tiên, nghĩa là một giao tác có mức ưu tiên cao có thể sẽ phải đợi một giao tác có mức ưu tiên thấp hơn thời gian xác định.Ví dụ 1: Giả sử T1, T2, T3 là ba giao tác được sắp xếp theo thứ tự giảm dần của mức ưu tiên với T1 có mức ưu tiên cao nhất. Giả sử rằng T1 và T3 truy nhập cùng một dữ liệu X. Giả sử tại thời điểm t1 giao tác T3 nhận một khoá ghi trên X. Trong khi T3 đang thực hiện thì giao tác T1 có mức ưu tiên cao nhất đến và cố gắng nhận khoá đọc trên dữ liệu X. Giao tác T1 sẽ bị trì hoãn, vì dữ liệu X đang được ghi bởi T3. Chúng ta có thể cho rằng T1 là giao tác có mức ưu tiên cao nhất sẽ bị trì hoãn đến tận khi T3 hoàn thành và giải phóng khoá trên X. Tuy nhiên, khoảng trì hoãn có thể không tồn tại mãi, bởi vì giao tác T3 có thể nhận được ưu tiên cao của mức ưu tiên giao tác T2 khi T2 không cần truy nhập vào dữ liệu X. Sự ưu tiên cao của giao tác T3 làm cho T1 sẽ tiếp tục trì hoãn đến tận khi T2 và ngăn cản thực hiện của các giao tác khác. Khoảng trì hoãn trong ví dụ 1 có thể kéo dài tuỳ ý. Tình trạng này có thể khắc phục một phần nếu các giao tác không cho phép thay đổi được ưu tiên cao. Tuy nhiên giải pháp này chỉ thích hợp cho các giao tác thực hiện rất ngắn, bởi vì nó tạo ra sự không cần thiết phải trì hoãn. Ví dụ, một giao tác với mức ưu tiên thấp mà thực hiện lâu khi đó, một giao tác khác đòi hỏi truy nhập tới cùng tập dữ liệu có thể sẽ bị trì hoãn và như thế hệ thống sẽ không hiệu quả. Mục đích của bài báo này là xây dựng giao thức R/WPCP (Read/Write Priority Ceiling Protocol) quản lý mức ưu tiên để điều khiển tương tranh tránh được sự chết nghẽn (deadlock) và giảm sự trì hoãn làm cho hệ thống thực hiện hiệu quả hơn.2. Giao thức R/WPCP Trước tiên chúng tôi xin giới thiệu tóm lược một số khái niệm cơ sở liên quan đến giao thức R/WPCP (Read/Write Priority Ceiling Protocol).2.1. Khái niệm cơ bản CSDL gồm tập q các đối tượng dữ liệu (x, y, z) và tập T =(Ti, iÊ n) các giao tác. Mỗi giao tác có thể thực hiện trong CSDL ở thời điểm li không xác định trước. Khi thực hiện giao tác đó có thể đọc một số đối tượng dữ liệu, thực hoặc một số tính toán riêng và sau có thể thực hiện một số thao tác ghi trên cùng các đối tượng dữ liệu đó. Mỗi giao tác có thể đọc và ghi dữ liệu trong quá trình thực hiện . Mỗi giao tác sử dụng khóa hai pha phải yêu cầu các giao tác tham gia nhận tất cả các khoá trước khi giải phóng khoá. Một giao tác khi chưa giải phóng khoá đã chiếm giữ, nó không thể nhận một khoá mới. Hơn nữa chúng ta giả thiết rằng các giao tác sẽ thiết lập một mức ưu tiên theo thuật toán lập lịch. Với giao thức khoá hai pha và xác định mức ưu tiên chúng ta có thể gặp phải vấn đề không kiểm soát được việc đảo ngược mức ưu tiên như đã được trình ở trên. Tuy nhiên vấn đề này có thể được giải quyết bởi R/WPCP. Từ đó chúng ta có những nhận xét sau:Nhận xét 1: Luật thừa kế ưu tiên [7] trong ngữ cảnh của lịch ưu tiên cho phép một giao tác T có mức ưu tiên cao có thể ưu tiên cho giao tác có mức ưu tiên thấp thực hiện khi T bị trì hoãn bởi một giao tác khác. Luật kế thừa ưu tiên khảng định khi một giao tác T làm trì hoãn thực hiện giao tác có mức ưu tiên cao hơn, T sẽ thực hiện kế thừa tại mức ưu tiên cao nhất của tất cả các giao tác bị trì hoãn. Để làm rõ nhận xét này chúng ta xét các trường hợp ở ví dụ 1. Giả sử giao tác T1 bị trì hoãn bởi T3. Giao thức kế thừa mức ưu tiên yêu cầu giao tác T3 thực hiện giao tác tại mức ưu tiên của T1 đến tận khi nó giải phóng khoá trên được dữ liệu X. Như vậy, giao tác T2 sẽ không được ưu tiên hơn T3 một khi giao tác T3 giải phóng khoá trên dữ liệu X. T3 trở về xác định mức của nó và ngay lập tức được ưu tiên bởi T1. Như vậy kế thừa ưu tiên sẽ giảm thời gian trì hoãn của các giao tác có mức ưu tiên cao nhất.Nhận xét 2: Để kiểm soát được thứ tự ưu tiên của các giao tác, chúng ta sử dụng ba tham biến cho mỗi dữ liệu trong CSDL để quản lý: - mức ưu tiên ghi cao nhất WCeil(X) là mức ưu tiên của giao tác ưu tiên cao nhất có thể ghi X. - mức ưu tiên tuyệt đối cao nhất ACeil (X) là mức ưu tiên của giao tác ưu tiên cao nhất có thể đọc hoặc ghi X. - mức ưu tiên R/W cao nhất RWCeil (X) là ưu tiên Read Write cao nhất đối với dữ liệu X được xác định tại thời điểm chạy. Giao tác T không thể có khoá đọc (ghi) đối với dữ liệu và thực hiện các thao tác của nó nếu mức ưu tiên của giao tác T không cao hơn mức ưu tiên cao nhất RWCeil (X). Chúng ta gọi đây là luật cao nhất (Ceil Rule). Để hiểu rõ luật này chúng ta ký hiệu như sau: Sysceili chỉ ra mức ưu tiên cao nhất(RWCeil(X)) trong số tất cả các giao tác Ti khoá X. Sysceili cũng được xác định động trong mỗi lần chạy khi Ti yêu cầu khoá một dữ liệu. Pi là mức ưu tiên của giao tác Ti. Trong thuật toán, điều kiện để điều khiển giao tác truy nhập dữ liệu là giao tác Ti không thể có khoá đọc (ghi) một dữ liệu X trừ khi mức ưu tiên của nó cao hơn Sysceili, nghĩa là Pi > Sysceili. Theo luật cao nhất, nếu một giao tác có Write-Lock trên dữ liệu X, khi đó X không thể được đọc/ghi bởi các giao tác khác. Để đảm bảo điều kiện này, chúng ta đặt RWCeil(X) = ACeil(X). Vì ACeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể đọc (ghi) dữ liệu X, nó ngăn cản các giao tác khác từ việc đọc (ghi) trên dữ liệu X đến tận khi khoá trên X được giải phóng. Khi một giao tác có khoá đọc dữ liệu X, chúng ta đặt RWCeil (X) bằng WCeil (X) vì WCeil (X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi X, nó ngăn cản những giao tác khác từ việc ghi dữ liệu X theo luật cao nhất. Tuy nhiên các giao tác đọc với mức ưu tiên cao hơn WCeil (X) có thể chia sẻ khoá đọc trên X. Tính chất quan trọng của giao thức này là ngăn cấm các giao tác đọc với mức ưu tiên thấp hơn hoặc bằng mức ưu tiên Wceil (X) để chia sẻ khoá đọc trên X. Trong trường hợp khác, các giao tác đọc với mức ưu tiên thấp hơn hoặc bằng mức ưu tiên ghi cao nhất thì không thể chia sẻ khoá đọc trên dữ liệu. Nếu chúng ta cho phép các giao tác đọc với mức ưu tiên thấp chia sẻ khoá đọc dữ liệu, khi đó một giao tác ghi có mức ưu tiên cao cần ghi đối với dữ liệu X thì giao tác đó phải đợi các giao tác đọc khác đang thực hiện. Nghĩa là một giao tác có thể bị trì hoãn bởi nhiều giao tác có mức ưu tiên thấp hơn. Việc quản lý mức ưu tiên mục đích của RWCeil (X) đảm bảo mỗi giao tác thực hiện tại mức ưu tiên cao hơn mức ưu tiên mà có thể được kế thừa bởi các giao tác ưu tiên. Khi một giao tác T có khoá ghi một dữ liệu X, RWCeil (X) thể hiện mức ưu tiên cao nhất mà T có thể kế thừa qua X. Ví dụ khi T có khoá ghi trên X, nó có thể làm trì hoãn giao tác có mức ưu tiên cao nhất mà giao tác đó có thể đọc (ghi) X và vì thế T sẽ kế thừa mức ưu tiên của TH. Do đó, RWCeil (X) khi ghi được định nghĩa bằng ACeil (X). Ngoài ra, khi T là một giao tác với mức ưu tiên thấp giữ một khoá đọc trên đối tượng dữ liệu X và giao tác T có mức ưu tiên cao nhất có thể yêu cầu một khoá ghi trên X. Giao tác T có thể trì hoãn Tw và kế thừa mức ưu tiên của Tw. Từ đó, RWCeil (X) khi đọc sẽ được xác định là WCeil (X). Với R/WPCP, một giao tác T không thể nhận một khoá và thực hiện trừ khi mức ưu tiên của giao tác cao hơn tất cả RWCeil (X). Vì mức ưu tiên cao nhất RWCeil(X) là mức ưu tiên cao nhất tại thời điểm hiện tại giao tác có thể thực hiện. Sự điều phối thứ tự ưu tiên của các giao tác đưa đến một số tính chất thú vị: giao thức R/WPCP có thể giúp tránh được deadlock và có thể trì hoãn duy nhất một lần. Ví dụ 2: Giả sử rằng chúng ta có 3 giao tác T0ư, T1, T2 sắp xếp theo thứ tự ưu tiên giảm dần. Cũng giả thiết rằng chúng truy nhập dữ liệu (X1, X2, X3) như sau: T0 = {.., Write lock (X0), Unlock (X0),..} T1 = {.., Read lock (X1), Write lock (X2),.., Unlock (X2), Unlock (X1),..} T2 = {.., Read lock (X2), Write lock (X1),.., Unlock (X1), Unlock (X2),..} Đầu tiên chúng ta thiết lập mức ưu tiên cho mỗi dữ liệu như sau: WCeil (X1) và ACeil(X1) là mức ưu tiên của T2 và T1 tương ứng là P2 và P1. WCeil (X2) và ACeil (X2) bằng P1. WCleil (X0) và ACeil (X0) bằng P0. Tại thời điểm to, T2 bắt đầu thực hiện. Tại thời điểm t1, T2 thực hiện Readlock (X2) và RWCeil (X2) đặt bằng WCeil (X2) và bằng P1. Khi nhận được khoá dữ liệu X2, thì T2 bắt đầu thực hiện. Tại thời điểm này giao tác T1 khởi tạo và có mức ưu tiên cao hơn. Khi T1 thực hiện Read lock (X1) tại thời điểm t2 nhưng hệ thống không thể chia sẻ. Theo lịch chúng ta thấy rằng T1 có mức ưu tiên là P1 không cao hơn RWCeil (X2) (đã được ký hiệu cũng bằng P1). Do đó, bộ lập lịch này sẽ làm trì hoãn giao tác T1 và bỏ qua sự đòi hỏi lock (X1) như vậy T1 bị trì hoãn bởi T2. Giao tác T2 bây giờ kế thừa mức ưu tiên của T1 và lại tiếp tục thực hiện. Vì T1 bị từ chối khi nhận khoá trên dữ liệu X1 và bị trì hoãn dẫn đến xảy ra deadlock. Nhưng khả năng deadlock giữa T1 và T2 được ngăn cản nếu T1 đã được nhận khoá trên dữ liệu X1 thì T1 có thể đợi cho tới tận khi T2 giải phóng khoá trên dữ liệu X2, ngoài ra T2 cũng có thể đợi T1 giải phóng khoá trên X1. Một trường hợp khác, giả sử rằng tại thời điểm t3, trong khi T2 vẫn đang trong việc thực hiện các thao tác của chúng thì giao tác To có mức ưu tiên cao nhất đến và cố gắng nhận một khoá ghi dữ liệu Xo. Vì mức ưu tiên của To cao hơn RWCeil (X2) nên giao tác To sẽ tiếp tục thực hiện các công việc của nó và vì thế T2 bị trì hoãn. Tại thời điểm t4, To hoàn thành việc thực hiện và T2 tiếp tục được thực hiện (vì T1 đã bị trì hoãn bởi T2). Giao tác T2 tiếp tục thực hiện đọc trên dữ liệu X2 và nhận khoá ghi trên dữ liệu X1. Tại thời điểm t5, T2 giải phóng X1. Tại thời điểm t6 khi T2 giải phóng X2. T1 có mức ưu tiên cao hơn T2 vì thế nó nhận được khoá và thực hiện hoàn thành. Cuối cùng T2 tiếp tục thực hiện cho đến khi hoàn thành. Chú ý: To không bao giờ bị trì hoãn. Giao tác T1 đã bị trì hoãn bởi giao tác T2 có mức ưu tiên thấp hơn trong khoảng [t2, t3] và [t4, t6]. Tuy nhiên, hai khoảng đó tương đương với khoảng mà T2 cần khoá trên hai dữ liệu X2 và X1. Vì vậy khoảng trì hoãn của T1 bằng khoảng thực hiện giao tác của giao tác T2 có mức ưu tiên thấp hơn. Như vậy tính chất của giao tác này là mỗi giao tác T có thể bị trì hoãn tại duy nhất một giao tác có mức ưu tiên thấp hơn đến tận khi giao tác làm cho trì hoãn tạm ngưng chính nó hoặc hoàn thành.2.2. Định nghĩa và các tính chất của giao thức R/WPCP Giả thiết rằng chúng ta đưa ra trong mô hình CSDL tập trung, tập các giao tác truy nhập theo thứ tự FCFS, và một giao tác không thể nhận khoá trên một dữ liệu khi nó đã có khoá và không xảy ra deadlock với chính khoá đó, và cũng không có các khóa đọc ( ghi) có thể được thực hiện trên một dữ liệu. Ký hiệu: các giao tác có thứ tự {T1..Tn} theo mức ưu tiên giảm dần, với T1 có mức ưu tiên cao nhất. Ti là giao tác thứ i, Pi chỉ mức ưu tiên của giao tác Ti. Định nghĩa 4: Chúng ta sử dụng ký hiệu dữ liệu trong cơ sở dữ liệu như là một bộ của CSDL quan hệ. Một khoá có thể là khoá đọc (ghi). Một giao tác T giữ khoá đọc (ghi) trên dữ liệu X ta nói rằng có khoá đọc (ghi) trên dữ liệu X. Mức ưu tiên cao nhất của dữ liệu, Write Priority Ceiling (WCeil(X)) được định nghĩa là mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi dữ liệu X. ACeil (X) là mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể đọc(ghi) dữ liệu X. Khi một dữ liệu X có khoá ghi, RWCeil(X) được định nghĩa bằng ACeil(X). Khi một đơn vị dữ liệu X có khoá đọc, RWCeil(X) được định nghĩa bằng WCeil(X). Chúng ta định nghĩa R/WPCP như sau: 1. Giao tác T là một giao tác có mức ưu tiên cao nhất đang thực hiện trên bộ vi xử lý được xác định. Trước khi giao tác T có thể đọc (ghi) dữ liệu X khi đó T phải nhận khoá đọc (ghi) trên dữ liệu X, các giao tác phải thoả mãn giao thức khoá hai pha và tất cả các khoá sẽ đựơc giải phóng tại thời điểm kết thúc của các giao tác. 2. Ký hiệu X* là dữ liệu với mức ưu tiên cao nhất của tất cả các dữ liệu có khoá được giữ bởi các giao tác khác giao tác T (RWCeil(X*)). Khi giao tác T nhận khoá trên dữ liệu X. T sẽ bị trì hoãn và khoá trên dữ liệu X sẽ bị từ chối, nếu mức ưu tiên của giao tác T không cao hơn mức ưu tiên RWCeil(X*). Trong trường hợp này, giao tác T sẽ bị trì hoãn bởi giao tác đang giữ khoá trên X*. Nếu giao tác T có mức ưu tiên cao hơn RWCeil(X*) thì T nhận khoá trên X. Dưới điều kiện này sẽ không có xung đột đọc ghi trên dữ liệu X, và chúng ta không cần kiểm tra nếu X đã có khoá. 3. Nếu giao tác T làm trì hoãn các giao tác có mức ưu tiên cao hơn khi đó T sẽ kế thừa mức ưu tiên PH là mức ưu tiên cao nhất của giao tác bị trì hoãn bởi T. Ví dụ nếu một giao tác T3 có mức ưu tiên thấp làm trì hoãn một giao tác T2 có mức ưu tiên trung bình và T2 làm trì hoãn giao tác T1 có mức ưu tiên cao nhất thì giao tác T2 đầu tiên sẽ kế thừa mức ưu tiên của T1. Tiếp theo T3 sẽ kế thừa mức ưu tiên của T1 từ T2. 4. Khi giao tác T không thực hiện thì có thể luôn ưu tiên các giao tác khác thực hiện tại mức ưu tiên thấp. Nhận xét: Dưới giao thức này, chúng ta không cần kiểm tra xung đột đọc ghi, ví dụ khi một dữ liệu X được nhận khoá ghi của giao tác T, RWCeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể truy nhập X. Vì vậy giao tác này sẽ bị trì hoãn bởi một giao tác có mức ưu tiên cao có thể ghi (đọc) dữ liệu X. Trường hợp khác, giả sử rằng, dữ liệu X nhận khoá đọc của giao tác T chiếm giữ thì RWCeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi dữ liệu X. Vì vậy, giao tác ghi dữ liệu X sẽ có mức ưu tiên không lớn hơn mức ưu tiên RWCeil sẽ bị trì hoãn. Chỉ những giao tác đọc X và có mức ưu tiên cao hơn giao tác RWCeil sẽ được phép đọc khoá trên X. Dưới R/WPCP Dead lock không thể xảy ra và mỗi giao tác có thể bị trì hoãn duy nhất một lần. Sau đây chúng ta sẽ chứng minh các tính chất của R/WPCP.2.3. Chứng minh các tính chất Bổ đề 1: Dưới R/WPCP, mỗi giao tác sẽ thực hiện tại một mức ưu tiên cao hơn mức ưu tiên mà các giao tác được ưu tiên có thể kế thừa. Chứng minh: Từ định nghĩa của R/WPCP khi một giao tác T giữ khoá của một dữ liệu, mức ưu tiên cao nhất T có thể kế thừa bằng mức ưu tiên cao nhất RWCeil của giao tác khoá dữ liệu. Vì vậy khi một giao tác TH có mức ưu tiên cao hơn mức ưu tiên cao nhất RWCeil của dữ liệu được khoá bởi giao tác T, giao tác Th sẽ thực hiện tại mức ưu tiên cao hơn mức ưu tiên mà các giao tác được ưu tiên có thể kế thừa.Định lý 1: Giao thức R/WPCP tránh được chết nghẽn (Deadlock). Chứng minh: Giả sử Deadlock xảy ra . Ký hiệu: P là mức ưu tiên cao nhất của tất cả các giao tác được liên quan trong Deadlock. Sự chuyển mức ưu tiên kế thừa do đó tất cả các giao tác liên quan trong Deadlock cuối cùng sẽ thừa kế cùng mức ưu tiên cao nhất P. Điều này trái với bổ đề 1. Chúng ta giả sử rằng một thao tác chính nó sẽ không bị trì hoãn trong khi thực hiện. Nghĩa là nếu một thao tác T chỉ là một giao tác trong một bộ xử lý và nếu T đã thực hiện khi đó T sẽ chạy đến tận khi hoàn thành. Dưới giả thiết này, chúng ta thấy rằng một giao tác T có thể bị trì hoãn một lần bởi giao tác TL có mức ưu tiên thấp hơn. Tiếp theo, chúng ta chứng minh rằng giao tác có thể bị trì hoãn ít nhất một lần nếu có nhiều giao tác với mức ưu tiên thấp.Bổ đề 2: Giao thức R/WPCP, trong suốt quá trình thực hiện của giao tác T hoặc chính nó bị trì hoãn hoặc T có thể bị trì hoãn duy nhất một lần bởi một hoặc nhiều giao tác có mức ưu tiên thấp hơn. Chứng minh: Giả sử rằng giao tác T bị trì hoãn bởi giao tác TL có mức ưu tiên thấp. Theo định lý 1, sẽ không có Deadlock và vì thế giao tác TL sẽ tồn tại ở một số thời điểm ví dụ t1. Tại thời điểm t1, TL được kế thừa mức ưu tiên của T. Vì TL không thể đợi lâu nó có thể kế thừa một mức ưu tiên cao hơn mức ưu tiên của chính nó. Tuy nhiên TL không thể thực hiện chạy đến tận khi T hoàn thành hoặc chính nó bị trì hoãn.Định lý 2: Dưới R/WPCP một giao tác T có thể bị trì hoãn duy nhất một lần bởi các giao tác có mức ưu tiên thấp hơn đến tận khi T thực hiện xong hoặc chính nó bị trì hoãn. Chứng minh: Giả sử rằng T bị trì hoãn bởi n giao tác có mức ưu tiên thấp hơn. Do bổ đề 2, T bị trì hoãn bởi n giao tác có mức ưu tiên thấp hơn T1, T2,.., Tn. ở đây mức ưu tiên của Ti được giả thiết cao hơn hoặc bằng Ti+1. Dưới giao thức này, một giao tác có thể luôn luôn được ưu tiên bởi một giao tác có mức ưu tiên cao hơn. Vì thế, giao tác có mức ưu tiên thấp không thể làm trì hoãn giao tác có mức ưu tiên cao hơn. Do đó các giao tác và T1..Tn phải được thực hiện. Giả thiết T bị trì hoãn bởi Tn và Tn kế thừa mức ưu tiên của T. Vì T có thể bị trì hoãn bởi Tn, mức ưu tiên của giao tác T không thể cao hơn mức ưu tiên cao nhất P mà có thể được kế thừa từ Tn. Một trường hợp khác, theo bổ đề 1, mức ưu tiên của Tn -1 cao hơn P. Suy ra mức ưu tiên của Tn-1 cao hơn mức ưu tiên của giao tác T. Điều này trái với giả thiết mức ưu tiên của T cao hơn mức ưu tiên T1, T2,.., Tn. Định lý được chứng minh.3. Kết luận Trong bài báo chúng tôi đã giới thiệu các tính chất của giao thức R/WPCP. Đây là giao thức kết hợp giữa 2PL với lịch điều khiển mức ưu tiên thời gian thực. Sau đó chúng tôi đã chứng minh giao thức này giúp giải quyết được vấn đề chết nghẽn (Deadlock) của hệ thống và có thể bị trì hoãn duy nhất một lần bởi các giao tác có mức ưu tiên thấp hơn. Bài báo này đóng góp một phần trong việc phát triển các giao thức điều khiển tương tranh mới trong CSDL thời gian thực.Tài liệu tham khảo[1] A Bestavros, J.lin and Sany Hyuk Son, Real Time Database Systems: Issuse and Application, Kluwer Academic publishers, 1997. Đoàn Văn Ban, Hồ Văn Hương, Đặc tả hình thức điều khiển tương tranh trong cơ sở dữ liệu thời gian thực. Hội thảo Quốc gia công nghệ thông tin, Huế, 6 - 2000. Đoàn Văn Ban, Hồ Văn Hương, A Formal Verification of the Concurrency Control in Duration Calculus. Conference at Institute of Mathematics, 8 - 2000. Đoàn Văn Ban, Hồ Văn Hương, Tính nhất quán lâm thời trong cơ sở dữ liệu thời gian thực, xemina tháng 10-2000, Khoa Toán Cơ Tin, Đại học khoa học tự nhiên. Đoàn Văn Ban, Hồ Văn Hương, Lịch giao tác với các ràng buộc thời gian, Conference at Hue University, 4-2001. J. R. Haritsa, M. J. Carey, and M. Livny, “Data Access Scheduling in Firm Real Time Database Systems``, The Journal of Real Time Systems, 4, pp. 203 241, 1992. Lui Sha at all, ” Priority Inheritance Protocol: An Approach to Real Time Synchronization”, IEEE, 1990. R. Abbott and H. Garcia Molina, Scheduling Real Time Transactions: A Performance Evaluation``, ACM Transaction on Database System, Vol 17, N3, 1992.

nguyenthaihiep (I11C) đã viết:

chipphonui đã viết:câu 4: bộ hóa công việc của p1,p2,p3. sao cho:
a, p1 trước p2, p2 trước p3?
b, p1 trước p2 và p3?
c, p1 và p2 trước p3?
đã ai giải bài tập này chưa? ai giúp mình với. mình có đi học nhưng không hiểu cách làm bt này. help me! help me! thanks thanks...

Bài mới học hôm qua mà, bạn nên suy nghĩ tìm cách giải đi, nếu suy nghĩ mãi mà vẫn ko tìm ra lời giải thì hãy tham khảo người khác, vừa rèn luyện cho mình tính kiên nhẫn vừa giúp mình ngày một giỏi hơn đó.

oh thanks bạn nha, tại mình có đi học nhưng không hiểu lắm nên mới lên diễn đàn hỏi chứ.

Đầu cầu có một cây đèn, có hai trạng thái đỏ và xanh. Có hai ô tô đi tới cầu và cầu chỉ có trọng tải 1 ô tô đi qua. Do vậy 1 thời điểm chỉ có duy nhất chiếc ô tô mà thôi.
minh họa code bằng khái niệm:
Semaphore có 2 trạng thái: //0 là đỏ, 1 là xanh
Wait(s);
lên cầu; //tương tranh
qua cầu;//tương tranh
Signal(s);
khi ô tô qua cầu làm cầu chĩu xuống, cầu chính là tài nguyên dùng chung

TranQuyThanh (I11C) đã viết:Ta dùng 2 đèn hiệu SemFull và SemEmpty

SemFull : kiểm tra số Sản phẩm trong bộ đệm.

SemEmpty: Kiểm tra số vùng trống trong bộ đệm.

Hai tác nguyên: Wait và Signal

Producer()

{ // Chờ khi bộ đệm đầy

WaitforSignal(SemFull,INITE)

//Sản xuất sản phẩm

Releave(SemEmpty)

//Bộ đệm đã có Sản phẩm

}

Consumer()

{ // Chờ đến khi có sản phẩm

WaitforSignal(SemEmpty ,INITE)

//tiêu thụ sản phẩm

Releave(SemFull)

//Bộ đệm đã có chổ trống

}

Mình xin phép bổ sung thêm cho đầy đủ:
Giả sử có Bộ nhớ đệm (Buffer) bao gồm nhiều khoang (Items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2,... vào.
Tiến trình Consumer lần lượt lấy sản phẩm ra theo đúng thứ tự.
Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, Không được lấy ra khi chưa có.
PRODUCER
item nextProduced;
while (1)
{
while(((in+1)%BUFFER_SIZE)==out); //quẩn tại đây khi buffer đầy.
buffer[in] = nextProduced;
in = (in+1)%BUFFER_SIZE;
}

CONSUMER
item nextConsumed;
while (1)
{
while(in==out); //quẩn khi buffer rỗng
nextConsumed = buffer[out];
out = (out+1)%BUFFER_SIZE;
}

Các trạng thái của một tiến trình.
- Trạng thái của tiến trình tại mỗi thời điểm được xác định bởi hoạt động hiện thời của tiến trình tại thời điểm đó. Trong suốt khoảng thời gian tồn tại trong hệ thống, một tiến trình có thể thay đổi trạng thái do rất nhiều nguyên nhân như: chờ đợi sự kiện nào đó xảy ra, đợi một thao tác vào/ra hoàn tất, hết thời gian xử lý...
Tại mỗi thời điểm, tiến trình có thể nhận một trong các trạng thái sau:
+ Khởi tạo (new): tiến trình đang được tạo lập.
+ Sẵn sàng (ready): tiến trình chờ được cấp phát CPU để xử lý.
+ Thực hiện (waiting): tiến trình phải dừng vì thiếu tài nguyên hoặc chờ một sự kiện nào đó.
+ Kết thúc (halt): tiến trình đã hoàn tất công việc xử lý.
Các trạng thái của tiến trình có thể đc biểu diễn qua sơ đồ sau:


Hệ điều hành quản lý hoạt động của các tiến trình trong hệ thống thông qua khối mô tả tiến trình (Process Control Block - PCB). Khối mô tả tiến trình bao gồm các thành phần:
- Số thứ tự của tiến trình
- Con trỏ trạng thái của tiến trình (cho biết trạng thái của tiến trình)
- Thông tin về tài nguyên của tiến trình đang sử dụng hoặc được phép sử dụng.

Giả sử có hai tiến trình P1 và P2 thực hiện công việc của 1 kế toán, và cùng chia sẻ 1 vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút 1 khoản tiền tienrut từ tài khoản:
if (taikhoan - tienrut >= 0)
taikhoan = taikhoan - tienrut;
else
error( " không thể rút tiền !");

Giả sử trong tài khoản còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau:
-Sau khi đã kiểm tra điều kiện ( taikhoan - tienrut >=0 ) và nhận được kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.
-P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 ( do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.
-Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện ( taikhoan - tienrut >= 0) vì đã được kiểm tra trong đợt xử lý trước, mà nó sẽ thực hiện rút tiền. Giá trị của taikhoan sẽ được cập nhật lại thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng 1 vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống, được gọi là các tình huống tranh đoạt điều khiển.

nguyenthaihiep (I11C) đã viết:

chipphonui đã viết:câu 4: bộ hóa công việc của p1,p2,p3. sao cho:
a, p1 trước p2, p2 trước p3?
b, p1 trước p2 và p3?
c, p1 và p2 trước p3?
đã ai giải bài tập này chưa? ai giúp mình với. mình có đi học nhưng không hiểu cách làm bt này. help me! help me! thanks thanks...

Bài mới học hôm qua mà, bạn nên suy nghĩ tìm cách giải đi, nếu suy nghĩ mãi mà vẫn ko tìm ra lời giải thì hãy tham khảo người khác, vừa rèn luyện cho mình tính kiên nhẫn vừa giúp mình ngày một giỏi hơn đó.

Lời khuyên của bạn Thái Hiệp rất đúng, học môn HĐH này bạn phải tự học là chính - nếu cảm thấy bí quá thì bạn hãy cố gắng tranh thủ thời gian đến lớp chịu lắng nghe thầy giảng bài rồi về nhà xem lại bài thì sẽ ko có gì là khó khăn cả bạn ah. Chúc bạn thành công!

code dành cho tiến trình người lái xe (đoạn tương tranh);

*Khai báo :
----------------------------------------------------
Semaphore SemEmpty =10 ; semfull =0;
semaphore crictsec =1 ;
----------------------------------------------------------
* semafore s // 0 :đèn đỏ
// 1 :đèn xanh

wait (s)
lên cầu ;
qua cầu ;
=> đoạn tương tranh là lên cầu và qua cầu
signal (s);

* proceducer (nhà sản xuất )
wait (sem Empty)
wait (Critsec)
signal (Semfull) // đưa sản phẩm vào bô đệm ( đoạn tương tranh)
signal (Critsec); // đoạn đăng xuất ra đoạn tương tranh.

Consumer (luồng tiêu thụ)
wait (semfull);
wait (Critsec);
signal (semEmpty) // lấy sản phẩm ra bộ đệm (đoạn tương tranh)
signal (Critsec) //đoạn đăng xuất ra đoạn tương tranh.

----
các bạn xem qua và góp ý thêm nhé !!!!

Vấn đề và cấu trúc mã của Đoạn Tương Tranh.
Xét một hệ thống gồm n tiến trình ( P0 , P1 , ... , Pn-1 ) . Mỗi tiến trình gồm có một đoạn mã, được gọi là đoạn tương tranh (Creatical Section Problem), trong đó tiến trình này có thể thay đổi những biến dùng chung, cập nhật một bảng, viết đến tập tin,.. Đặc điểm quan trọng của hệ thống là ở chỗ khi tiến trình đang thực thi trong đoạn tương tranh thì không có tiến trình nào khác được phép thực thi trong đoạn tương tranh của nó. Do đó việc thực thi của đoạn tương tranh bởi các tiến trình là sự loại trừ hỗ tương. Vấn đề đoạn tương trang là thiết kế một giao thức mà các tiến trình có thể dùng để công tác
Mỗi tiến trình phải yêu cầu quyền để đi vào vùng tương tranh của nó.
Đoạn tương tranh là một đoạn mã chương trình trong chương trình của HĐH. Là đoạn mã có tính chất khi thực hiện các lệnh trong chương trình đoạn tương tranh thì các lệnh đó có thể tác động đến tài nguyên dùng chung, biến dùng chung (ví dụ như Count ++,Count - -) và có thể sửa kết quả trong biến tài nguyên
Cấu trúc mã đoạn tương tranh
while (1) {
remainder section // Đoạn còn lại
entry section // Đoạn đăng nhập
critical section // Đoạn Tương Tranh
exit section // Đoạn Đăng Xuất.
remainder section // Đoạn còn lại.

Trình bày khái niệm đèn hiệu như một phương tiện đồng bộ hóa công việc các tiến trình. Trình bày 2 ứng dụng của đèn hiệu.

Phương pháp đồng bộ hóa đèn hiệu được E.W.Dijstra đề xuất năm 1965 và được trao tặng danh hiệu Turing do hiệp hội các nhà tin học Mỹ lập ra và trao tặng . Một Semaphone S là một biến kiểu nguyên (integer) được truy suất với hai thao tác nguyên là
+ Hàm Wait ( ) : là một hàm không chia được, có một biến truyền vào là biến S kiểu đèn hiệu
+ Hàm Signal (báo hiệu) có tham số truyền vào là đèn hiệu hàm này không chờ, chỉ tăng đèn hiệu lên.
Việc kiễm tra S<= 0 và giảm S ( tring Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn( không xảy ra ngắt trong thời gian thi hành) do đó Wait và Signal được gọi là các tác nguyên (atomic Operationns)
Những sửa đổi đối với giá trị Integer của semaphore trong các thao tác Wait ( ) và Signal ( ) phải được thực thi không bị phân chia. Nghĩa là khi một tiến trình sửa đổi giá trị semaphore , không có tiến trình nào cùng một lúc có thể sửa đổi cùng biến semaphore đó. Ngoài ra , trong trường hợp của biến wait (s), kiểm tra giá trị integer của S (Sδ0) và sửa đổi có thể của nó (S--) cũng phải được thực thi mà không bị ngắt.
Trình bày 2 ứng dụng của đèn hiệu
+ Ứng dụng 1: Giải quyết vấn đề vùng tương tranh.
Mã của tiến trình Pi bây giờ có cấu trúc:
Đoạn tương tranh là mã khi thực hiện đoạn mã thì ảnh hưởng đến vùng tranh chấp, các code trong mã khi sử dụng chugn ảnh hưởng đến miền, vùng tranh chấp.
Ví dụ : giả sử có một cây cầu ở đấu cầu có 1 đèn mutex ( có 2 trạng thái xanh và đỏ) 2 ô tô tìm cách lên cầu nhưng trọng tải của cầu chỉ chịu được 1 ô tô khi lên cầu và ô tô khác phải chờ, đoạn qua cầu thuộc đoạn tương tranh, cầu chính là tài nguyên dùng chung, và lệnh qua cầu thuộc đoạn tương tranh.
Chúng ta có thể sử dụng semaphores để giải quyết vấn đề vùng tranh chấp với n tiến trình. N tiến trình chia sẻ 1 biến semaphore, mutex được khởi tạo.
Ứng dụng 2 : Đảm bảo công việc trật tự của các tiến trình.
Chúng ta cũng có thể sử dụng Semaphores để giải quyết vấn đề đồng bộ khác nhau
Thí dụ ,để xem xét hai tiến trình đang thực thi đồng hành : P1 với câu lệnh S1 và P2 với câu lệnh S2. Chúng ta tổ chức sao cho S2 được thực thi chỉ sau khi S1 đã hoàn thành , thực hiện bằng cách P1 và P2 chia sẻ một semaphore chugn Synch được khời tạo 0 và bằng cách chèn các câu lệnh Semaphore synch = 0;

TangHuynhThanhThanh I11C đã viết:

thanhnam06511c đã viết:...

Mình bổ sung ví dụ về bài toán Đồng bộ hóa :
Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản:

if (taikhoan - tienrut >=0)

taikhoan = taikhoan - tienrut;

else

error(� khong the rut tien ! �);

Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau :

Sau khi đã kiểm tra điều kiện (taikhoan - tienrut >=0) và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.

P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 (do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.

Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0)-vì đã kiểm tra trong lượt xử lý trước- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống.

Admin
Một ví dụ thiết thực !

Thưa thầy và các bạn !
Về ví dụ rút tiền ở tài khoản ATM này em thấy có một số vấn đề đáng lưu ý sau nữa về vấn đề đồng bộ hóa tiến trình.
Về ví dụ sử dụng tài khoản ATM của bạn thì đúng là đã giải quyết vấn đề tương hỗ ( mỗi thời điểm thì có một tiến trình vào và sử dụng vùng nhớ chung - tài khoản ) nhưng là bằng chia sẻ thời gian "time out" nên vẫn xảy ra lỗi. Bởi vì kiểm tra điều kiện rồi nhưng không thực hiện luôn mà lại thực hiện sau để cho bộ nhớ chung vậy là rất dễ sai hay xảy ra lỗi. Kiểm tra điều kiện nằm ngoài vùng tương tranh.
Theo em vấn đề rút tiền này thì mỗi lần có lệnh gì liên quan tới vùng nhớ chung ( tài khoản ) thì phải kiểm tra xong rồi thực hiện lệnh cùng 1 lúc luôn. Trước khi vào kiểm tra tài khoản thì phải dùng đèn hiệu để tại mỗi thời điểm chỉ cho một người dùng vào kiểm tra duy nhất. Việc kiểm tra tài khoản và thực hiện lệnh (rút tiền) đều cùng nằm trong đoạn tương tranh thì sẽ không xảy ra lỗi trên.

Ví dụ của bạn hay nhưng mà cũng như về ví dụ qua cầu thì khi 1 xe đến, kiểm tra thấy đèn xanh và được quyền qua cầu nhưng lại không qua liền mà ngồi chơi ở bên góc cầu 10 phút (chưa vào đoạn tương tranh nên đèn vẫn còn màu xanh nên xe khác vẫn được kiểm tra và qua cầu ). Rồi lát nữa chẳng cần kiểm tra nữa mà cứ thế qua cầu khi đèn hiệu đã có thể thay đổi bởi xe khác ->Sai.
=> Kiểm tra xong là phải qua cầu liền, nếu chưa qua thì lần qua sau thì phải kiểm tra lại, quyền được phép qua cầu chỉ có hiệu lực khi kiểm tra.

Admin
- Em hiểu bài tốt, nhất là nêu được: "Trước khi vào kiểm tra tài khoản thì phải dùng đèn hiệu để tại mỗi thời điểm chỉ cho một người dùng vào kiểm tra duy nhất. Việc kiểm tra tài khoản và thực hiện lệnh (rút tiền) đều cùng nằm trong đoạn tương tranh thì sẽ không xảy ra lỗi trên".
- Tất nhiên, cần thực hiện lệnh signal(s) sau khi trừ Tài khoản, để đèn s chuyển sang xanh và cho phép tiến trình khác thao tác với Tài khoản vừa giảm.
- Với Bài toán "Xe qua cầu yếu", trong đoạn tương tranh đâu có lệnh "Ngồi chờ 10 phút" (chỉ có 2 lệnh là Lên cầu và Qua cầu), tất cả do Lập trình cụ thể cả. Mặt khác, giả sử có "Ngồi 10 phút", thì chỉ xe này mới có quyền chuyển đèn từ Đỏ sang Xanh vì theo code của nó lệnh Qua cầu thực hiện xong mới đến lệnh signal(s). Những xe khác khi đến đầu cầu, đang "Ngủ" tại lệnh wait(s) mà (vì đèn s đang Đỏ) !

Thưa thầy và các bạn.
Qua bài 5 đã học công nghệ đa luồng và bài 7 điều phối tiến trình. Em cứ suy nghĩ mãi và thắc mắc về vấn đề nhiều tiến trình cùng kiểm tra điều kiện cùng lúc -> sẽ có trường hợp cùng vào vùng tương tranh thì sao mà giải quyết nhỉ :
Ví dụ như bài toán Sản Xuất - Tiêu Thụ như sau :
Giờ không phải là 1 Producer và 1 Consumer nữa mà là 10 Producer và 10 Consumer cùng sản xuất và tiêu thụ cùng lúc. Tuy là đã giải quyết vấn đề đồng bộ hóa như ở bài 7 nhưng có khi nào sẽ xảy ra những trường hợp sau không nhỉ:
-Có từ 2 Producer kiểm tra điều kiện - (sem_wait(&semEmpty) và pthread_mutex_lock(&critSec) cùng một lúc thì có thể sẽ vào vùng tương tranh để lưu item cùng lúc. -> cho item vào cùng 1 BUFFER hoặc lưu vào BUFFER đã có item mà Consumer chưa dùng
-Có từ 2 Consumer kiểm tra điều kiện - sem_wait(&semFull) và pthread_mutex_lock(&critSec) cùng một lúc thì cũng có thể vào vùng tương tranh đề lấy item cùng lúc -> cùng nhau lấy item từ 1 khoang của BUFFER hoặc sẽ lấy item từ khoang chưa có item

Admin
- Thắc mắc của em rất hợp lý.
- Tuy nhiên, các lệnh đưa sản phẩm vào Buffer (của Producer) và lấy sản phẩm từ Buffer (của Consumer) phải được coi là thuộc Đoạn Tương tranh !
- Thật vậy, các nhà sản xuất có thể qua được wait(semEmpty) và các nhà tiều thụ cũng có thể qua được wait(semFull) của chúng, nhưng chúng không thể cùng một lúc vào Đoạn tương tranh được vì còn có thêm đèn hiệu mutex hay critSec:
Producer:
wait(semEmpty);
wait(mutex);
// Đưa sản phẩm vào Buffer (đây thuộc Đoạn Tương tranh)
signal(semFull); // lệnh này cũng thuộc Đoạn Tương tranh
signal(mutex);

Consumer:
wait(semFull);
wait(mutex);
// Lấy sản phẩm từ Buffer (đây thuộc Đoạn Tương tranh)
signal(semEmpty); // lệnh này cũng thuộc Đoạn Tương tranh
signal(mutex);

tranphanhieu36_i11c đã viết:Thưa thầy và các bạn.
Qua bài 5 đã học công nghệ đa luồng và bài 7 điều phối tiến trình. Em cứ suy nghĩ mãi và thắc mắc về vấn đề nhiều tiến trình cùng kiểm tra điều kiện cùng lúc -> sẽ có trường hợp cùng vào vùng tương tranh thì sao mà giải quyết nhỉ :
Ví dụ như bài toán Sản Xuất - Tiêu Thụ như sau :
Giờ không phải là 1 Producer và 1 Consumer nữa mà là 10 Producer và 10 Consumer cùng sản xuất và tiêu thụ cùng lúc. Tuy là đã giải quyết vấn đề đồng bộ hóa như ở bài 7 nhưng có khi nào sẽ xảy ra những trường hợp sau không nhỉ:
-Có từ 2 Producer kiểm tra điều kiện - (sem_wait(&semEmpty) và pthread_mutex_lock(&critSec) cùng một lúc thì có thể sẽ vào vùng tương tranh để lưu item cùng lúc. -> cho item vào cùng 1 BUFFER hoặc lưu vào BUFFER đã có item mà Consumer chưa dùng
-Có từ 2 Consumer kiểm tra điều kiện - sem_wait(&semFull) và pthread_mutex_lock(&critSec) cùng một lúc thì cũng có thể vào vùng tương tranh đề lấy item cùng lúc -> cùng nhau lấy item từ 1 khoang của BUFFER hoặc sẽ lấy item từ khoang chưa có item

Admin
- Thắc mắc của em rất hợp lý.
- Tuy nhiên, các lệnh đưa sản phẩm vào Buffer (của Producer) và lấy sản phẩm từ Buffer (của Consumer) phải được coi là thuộc Đoạn Tương tranh !
- Thật vậy, các nhà sản xuất có thể qua được wait(semEmpty) và các nhà tiều thụ cũng có thể qua được wait(semFull) của chúng, nhưng chúng không thể cùng một lúc vào Đoạn tương tranh được vì còn có thêm đèn hiệu mutex hay critSec:
Producer:
wait(semEmpty);
wait(mutex);
// Đưa sản phẩm vào Buffer (đây thuộc Đoạn Tương tranh)
signal(semFull); // lệnh này cũng thuộc Đoạn Tương tranh
signal(mutex);

Consumer:
wait(semFull);
wait(mutex);
// Lấy sản phẩm từ Buffer (đây thuộc Đoạn Tương tranh)
signal(semEmpty); // lệnh này cũng thuộc Đoạn Tương tranh
signal(mutex);

Em cảm ơn thầy đã giải thích cho em hiểu rõ hơn về vấn đề này.
Còn vấn đề các nhà sản xuất có thể qua được wait(semEmpty) và các nhà tiều thụ cũng có thể qua được wait(semFull) của chúng, "nhưng chúng vẫn có thể cùng một lúc vào Đoạn tương tranh được vì cùng kiểm tra đèn hiệu mutex hay critSec một lúc". Nên cùng lúc đó đều thấy đèn hiệu mutex hay critSec thỏa điều kiện rồi cùng vào vùng tương tranh một lúc luôn không thầy.
Em nghĩ cũng có thể lắm !
Nếu có vấn đề này thì có nên giải quyết bằng cách dùng hàng đợi First-Come, First-Served Scheduling (FCFS queue) cho các nhà sản xuất đã qua được wait(semEmpty) và nhà tiêu thụ đã qua được wait(semFull). Để mỗi thời điểm chỉ có một nhà sản xuất hay một nhà tiêu thụ đầu hàng đợi vào kiểm tra đèn hiệu mutex hay critSec. Nếu đèn hiệu cho qua thì sẽ qua, còn đèn hiệu chưa cho qua thì trở về cuối hàng đợi chờ tới lượt kiểm tra tiếp theo.
Em nghĩ mãi rồi nghĩ ra được cách này. Làm như vậy có được không thầy ?

Admin
- Không việc gì phải băn khoăn cả ! Để Hệ Điều hành lo cho !
- Khi các nhà sản xuất và các nhà tiêu thụ cùng gặp đèn mutex (hay critSec), nghĩa là cùng thực hiện wait(mutex) (hay wait(critSec)), Hệ Điều hành sẽ chỉ cho 1 tiến trình (luồng) sản xuất hay tiêu thụ được vào Đoạn tương tranh mà thôi. Các tiến trình còn lại phải chờ.

while (1){
Remainder section
Entry section
Critical section
Exit section
Remainder section
}

Producer:
Wait (SemEmpty);

Wait (Mutex);

Buffer [in] = sp mới; //xếp sản phẩm vào bộ đệm

in = (in + 1) % BUFFER-SIZE;

Signal (SemFull);

Signal(Mutex);

Consumer:

Wait (SemFull);

Wait (Mutex);

p = Buffer [out] //lấy sản phẩm ra khỏi bộ đệm

out = (out + 1) % BUFFER-SIZE;

Signal (SemEmpty);

Signal (Mutex);
----------------------------------------
Giá trị ban đầu của Mutex là 1.

Giá trị ban đầu của SemFull là 0.

Giá trị ban đầu của SemEmpty là BUFFER-SIZE.