Thảo luận Bài 7

Nói đến đồng bộ hóa tiến trình là nói đến sự chờ đợi của tiến trình này đối với tiến trình kia để các tiến trình làm việc nhịp nhàn ăn khớp có trước có sau, nhằm đảm bảo tính nhất quán của tài nguyên dùng chung ( tính đúng đắn, tính tuần tự, nối tiếp nhau, trước sau như 1 của các tiến trình ) và tránh được hiện tượng deadlock( hiện tượng kẹt tiến trình )
VD: khi thầy viết lên bảng “ thông dịch ≠ biên dịch “ nhưng thầy chỉ mới viết đến “thông dịch ≠ biên” mà 1 bạn đã vội lấy máy ảnh ra chụp lại mà ko chờ thầy viết xong thì ảnh của bạn chụp chỉ có “thông dịch ≠ biên” thì kết quả này ko có ý nghĩa gì hết.

tranvanminh82(I22A) đã viết:Giả sử P1 có mã là S1, P2 có mã là S2, P3 có mã là S3.

Semaphore synch1 = 0;

Semaphore synch2 = 0;

Bài 3: P1 trước P2,P3

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	wait(synch1)	wait(synch2)
signal(synch1)	S2	S3
signal(synch2)

Bài 4: P1,P2 trước P3.

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	S2	wait(synch1)
signal(synch1)	signal(synch2)	wait(synch2)

Bạn có thể giải thích cụ thể được không, nhìn mấy cái table mình chưa hiểu lắm.

Mục đích của đồng bộ hóa công việc các tiến trình là:
+ Đảm bảo tính nhất quán của tải nguyên dùng chung.
+ Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).

VD1: khi thầy giáo viết lên bảng 1 câu chưa hoàn tất “Biên dịch khác với phiên”. Một bạn học sinh đã lấy máy ảnh chụp lại nội dung đó và không chờ cho đến khi thầy giáo kết thúc “Biên dịch khác với phiên dịch” => Không nhất quán về dữ liệu.

VD2: Khi máy tính vận hành nhiều tiến trình cùng một thời điểm. Nếu hệ điều hành không đứng ra đồng bộ (yêu cầu chương trình này đứng chờ cho đến khi một chương trình khác hoàn thành) mà cho tiến trình hoạt động tự do, chiếm CPU sẽ dẫn đến trình trạng treo máy.

VD3: Mỗi một xe máy trên đường là một tiến trình, cùng nhau sử dụng tài nguyên dùng chung là mặt đường. Nếu không có công an giao thông (hệ điều hành) đứng ra điều phối, hướng dẫn đường đi khi đông xe thì sẽ bị kẹt xe.

VD4: Một thợ chụp ảnh khi chụp mà không chờ tính nhất quán tức là mọi người chưa đứng đầy đủ hoàn chỉnh mà đã bấm máy thỉ kết quả là người thì nhắm mắt, số lượng người chưa đủ, người thì đứng nghiên, ...

VoMinhDien(I22B) đã viết:Ví dụ thực tế về đồng bộ hóa: Thầy chia lop thành 2 nhóm, nhóm lên bảng xếp hàng để chụp hình, nhóm còn lại làm nhiệm vụ chụp hình. Nếu nhóm bên dưới không chờ nhóm trên bảng xếp hàng ngay ngắn, chuẩn bị chụp hình thì sẽ có những bức hình lộn xộn, thậm chí có bạn nhắm mắt. Nếu nhóm chụp hình chờ 1 chút sẽ có những bức hình đẹp, việc đó gọi là đồng bộ hóa.

Ví dụ dể hiểu, cảm ơn bạn

TruongNhuNgoc (I22A) đã viết:

tranvanminh82(I22A) đã viết:Giả sử P1 có mã là S1, P2 có mã là S2, P3 có mã là S3.

Semaphore synch1 = 0;

Semaphore synch2 = 0;

Bài 3: P1 trước P2,P3

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	wait(synch1)	wait(synch2)
signal(synch1)	S2	S3
signal(synch2)

Bài 4: P1,P2 trước P3.

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	S2	wait(synch1)
signal(synch1)	signal(synch2)	wait(synch2)

Bạn có thể giải thích cụ thể được không, nhìn mấy cái table mình chưa hiểu lắm.

Có thể tạm hiểu wait=đèn đỏ,signal=đèn xanh,các xe S1,S2,S3
Theo như mình hiểu thì
B3 sẽ là:
_P1 đang thực hiện lệnh S1 lúc này synch=-1.
_P2 vs 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,lúc này P2 vs P3 mới thực hiện
=>P1 trước P2 vs P3

B4 sẽ là:
_P1 và P2 đang thực hiện lệnh S1, S2, lúc này synch=-1.
_P3 đang bị khóa tại hàm wait(synch) đợi khi synch >0.
_Khi P1 vs P2 thực hiện,S1 vs S2 dc thi hành xong hàm signal(synch) sẽ tăng synch lên 1,lúc này P3 sẽ thực hiện
=>P1 vs P2 trước P3

Theo mình hiểu là như vậy,còn sai mấy bạn sửa dùm

Bài 1: Thiết kế lại đèn hiệu ở đầu cầu để cho tối đa được 2 chiếc ô tô cùng 1 lúc trên mặt cầu?
Trả lời: theo bài học thì hàm wait có giá trị truyền vào là mutex và mutex = 1, mình sẽ đổi giá trị đó thành 2 vậy khi xe 1 lên cầu thì giá trị mutex=1 và xe thứ 2 lên thì mutex=0 khi có chiếc thứ 3 tới nó sẽ chờ vì trong hàm wait có vòng lặp while(mutex<-0);, khi 1 xe đã xuống cầu thì nhờ vào hàm signal mà mutex=1, tiếp đó thì xe 3 được lên. Vậy cùng 1 lúc chỉ có 2 chiếc xe trên mặt cầu.
Bài 2: Đồng bộ công việc sao cho P1 trước P2, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:
Bài 3: Đồng bộ P1, P2, P3 sao cho P1 trước P2 và P3
Trả lời: Ta dùng đèn hiệu sau:
Bài 4: Đồng bọ P1, P2, P3 sao cho P1, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:

Thưa thầy, em có thắc mắc là: ứng dụng thứ nhất của đèn hiệu là giải quyết vùng tương tranh


Liệu có thể xảy ra tình huống khi Pi bật signal thì Pj và Pk cùng 1 lúc nhận được signal đó và tranh giành nhau hay không?

Admin
- Giả sử Pj bắt đầu bằng lệnh wait(synch) và Pk cũng khởi đầu bằng lệnh wait(synch) như vậy.
- Khi Pi thực hiện signal(synch), chỉ một trong Pj và Pk "bắt" được tín hiệu từ Pi và đi vào vận hành mã chính của nó ! Giả sử Pk được chọn, khi đó đèn synch sẽ Đỏ và Pj sẽ phải "ngủ" mãi mãi tại wait(synch) nếu như Pi hoặc Pk sau đó không "bật" synch về Xanh !

- Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng.

- Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.

- Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.

- Thuật giải đồng bộ hoá bằng 3 đèn hiệu: semFull (quản lý số sản phẩm có trong bộ đệm, giá trị ban đầu bằng 0), semEmpty (quản lý số khoang còn trống, giá trị ban đầu bằng số khoang của bộ đệm) và Mutex (đảm bảo tính loại trừ tương hỗ, nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/cập nhật tài nguyên dùng chung, giá trị ban đầu bằng 1).

o Thuật giải cho Producer:

wait(semEmpty);

wait(Mutex);

// Đưa sản phẩm vào Buffer

..........................

signal(semFull);

signal(Mutex);


o Thuật giải cho Consumer:

wait(semFull);

wait(Mutex);

// Lấy sản phẩm từ Buffer

..........................

signal(semEmpty);
signal(Mutex);
lekhanhhoaI122B-lekhanhhoa(I22B)

Alan Mathison Turing (23 tháng 6, 1912 – 7 tháng 6, 1954) là một nhà toán học, logic học và mật mã học người Anh thường được xem là cha đẻ của ngành khoa học máy tính. Phép thử Turing (Turing test) là một trong những cống hiến của ông trong ngành trí tuệ nhân tạo: thử thách này đặt ra câu hỏi rằng máy móc có khi nào đạt được ý thức và có thể suy nghĩ được hay không. Ông đã hình thức hóa khái niệm thuật toán và tính toán với máy Turing, đồng thời đưa ra phiên bản của "Turing", mà ngày nay được đông đảo công chúng chấp nhận, về luận đề Church-Turing, một luận đề nói rằng tất cả những gì tính được bằng thuật toán đều có thể tính được bằng máy Turing.

Bắt đầu từ năm 1966, Giải thưởng Turing đã được Association for Computing Machinery (Hiệp hội Máy tính) trao cho cá nhân có đóng góp kĩ thuật cho cộng đồng máy tính. Giải này được coi như tương đương với giải Nobel trong cộng đồng này.

Ngày 23 tháng 6 năm 2001 một bức tượng của Turing được đặt tại công viên Sackville Park của thành phố Manchester, giữa tòa nhà của Đại học Manchester trên phố Whitworth và khu gay village của phố Canal. Để kỉ niệm 50 năm ngày mất của ông, một tấm bảng kỉ niệm đã được khánh thánh tại nơi ông ở trước đây, Hollymeade, Wilslow, vào ngày 6 tháng 7 năm 2004.

Tấm bảng đánh dấu nơi ở cũ của TuringViện khoa học Alan Turing (Alan Turing Institute) được sáng lập bởi UMIST và Đại học Manchester vào mùa hè năm 2004.

Lễ kỉ niệm cuộc đời và sự nghiệp của Turing đã được tổ chức tại Đại học Manchester vào ngày 5 tháng 6 năm 2004 do British Logic Colloquium (Hội Logic Anh) và British Society for the History of Mathematics (Nhóm nghiên cứu Lịch sử Toán học Anh) tổ chức.

Vào ngày 28 tháng 10 năm 2004 a bức tượng đồng của Alan Turing, tạc bởi John W. Mills, được khánh thành tại Đại học Surrey. Bức tượng kỷ niệm 50 năm ngày Turing mất. Nó diễn tả Turing đang cầm sách đi trong viện đại học này.

Holtsoft đã sản xuất ngôn ngữ lập trình mang tên Turing. Ngôn ngữ này dành cho người mới bắt đầu lập trình và không tương tác trực tiếp với phần cứng.

TruongNhuNgoc (I22A) đã viết:Đoạn tương tranh là đoạn mã chương trình, điều khiển công việc của tiến trình có tính chất, mà khi thể hiện đoạn mã đó tác động tới tài nguyên dùng chung.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

Thuậtngữ: Critical section
Thuậtngữ tiếng Việt: Đoạn mã găng, đoạn mã tới hạn.
Xét mộthệ có n tiếntrình P0, P1, ..., Pn, mỗi tiến trình có một đoạn mã lệnh gọi là đoạn mã găng, ký hiệu là CSi , nếu như trong đoạn mã này, các tiến trình thao tác trên các biến chung, đọc ghi file... (tổng quát: thao tác trên dữ liệu chung).
- Đặc điểm quan trọng mà hệ n tiến trình này cần có là: Khi một tiến trình Pi thực hiện đoạn mã CSi thì không có tiến trình Pj nào khác được phép thực hiện CSj. Mỗi tiến trình Pi phải “xin phép”(entry section) trước khi thực hiện CSi và thông báo (exit section) cho các tiến trình khác sau khi thực hiện xong CSi
.- Cấu trúc chung của Pi để thực hiện đoạn mã găng CSi
do {
Xin phép (ENTRY i ) thực hiện CSi ; // Entry section Thự chiện CSi ;
Thông báo (EXIT i ) đã thực hiện xong CSi ; // Exit section
Phần mã lệnh khác (REMAIN i ); // Remainder section
}
while (TRUE);
- Viết lại cấu trúc chung của đoạn mã găng:
do {
ENTRYi ; // Entry section
Thựchiện CSi ; // Critical section
EXITi ; // Exit section
REMAINi ; // Remainder section
}
while (TRUE);
-------------------------------------------------

Cách thiết kế đèn có sao cho cầu có thể đi được 2 xe cùng một lúc: có 2 cách.
C1: thiết kế đèn hiệu nhị phân, có ba trạng thái (giá trị 0 đèn màu đỏ,1 đèn màu xanh lá,2 màu xanh lục)
Typedef int semaphore;
Semaphore mutex = 1;
While(1)
{
Xe P1 đi đến cầu;
Wait(mutex); //chờ đèn xanh(so sánh 2 giá trị xanh và xanh lục cho đi,đỏ thi không cho đi)
xe P1 Lên cầu; //đoạn tương tranh, đèn màu xanh lục
xe P2 Lên cầu; đoạn tương tranh, đèn màu đỏ
Qua cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển màu( 2 giá trị xanh và xanh lục)
Xe P3 tiếp tực vào nếu thấy đèn có 2 giá trị (xanh lá và xanh lục)
}


C1: thiết kế cầu có 2 đèn hiệu(có 2 trang thái xanh và đỏ) 1 đèn đặt ở đầu cầu 1 đèn đạt ở giữa cầu.
Typedef int semaphore;
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái(xanh và đỏ)
While(1)
{
xe P2 Đi đến cầu;
Wait(mutex);
Xe P2 Lên cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển sang màu xanh
xe P1 Đi đến cầu;
Wait(mutex); //chờ đèn xanh
Xe P1 Lên cầu; //đoạn tương tranh,
Qua cầu;
Signal(mutex); //đèn chuyển sang màu xanh
}
Các bạn còn nghĩ ra được thêm cách nào hay hơn nữa xin bổ sung thêm và đóng góp ý kiến.thanks

Trình bày những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa.
- Mục đích của đồng bộ hóa công việc các tiến trình là
+đảm bảo Tính nhất quán của tài nguyên chung
+Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )

VD1:
Trong trung tâm dạy tin hoc học chỉ có 1 máy tính (tài nguyên dùng chung) , học viên A vào sử dụng máy tính để nghiên cứu tư liệu .học viên B vào sau muốn sừ dụng máy tính thì phài đợi HV A sử dụng xong mới dùng được .

VD2 :
Tong công ty , có 1 chiếc thang máy ( tài nguyên dùng chung ) , nhân viên A vào thang máy trước nên lên trước . Nhân viên B tới sau thì đợi lên sau .

Đoạn tương tranh là doạn mã cho tiến trình mà khi thực hiện nó truy cập, tác động và thay đổi được tài nguyên dùng chung.
Còn đoạn mã ko truy cập, tác động và thay đổi được tài nguyên dùng chung là đoạn còn lại
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.

- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

Khái niệm đèn hiệu
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

-Việc kiểm tra S <= 0 và giảm S (trong 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 Operations).

Phát biểu bài toán Sản xuất-Tiêu thụ với thuật giải đồng bộ hoá bằng 2 đèn hiệu semFull và semEmpty.
Giải:
Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0.
– Dữ liệu chia sẻ:
SEMAPHORE full, empty, mutex;
– Khởi tạo:
full = 0;

VanNhatDongGiang(I22A) đã viết:- Đảm bảo tính nhất quán của tài nguyên dùng chung.
- Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab

Ngoài ra, để công việc đồng bộ hóa diễn ra suông sẻ, mình cũng có một ví dụ về đồng bộ hóa tiến trình.

VD: Để đảm bảo tính nhất quán của tài nguyên dùng chung và hiện tượng kẹt tiến trình, cụ thể như:
Khi chúng ta lập trình, khai báo một thư việc hệ thống dùng chung trong việc nhập xuất dữ liệu (như trong ngôn ngữ Java), việc khai báo nhập/xuất trong thư viện: import java.io.* . Và để nhập dữ liệu ta tạo một luồng nhập bằng cách tạo tập tin nhập luồng (FileInputStream) và luồng xuất dữ liệu (FileOutputStream).
=> Hai luồng nhập/ xuất tiên biệt nên tránh được tình trạng tranh chấp ứng dụng tài nguyên.

Như các bạn đã được nghe thầy giảng trên lớp, vậy mình xin giải thích thêm vấn đề giải quyết đoạn tương tranh bằng cách sử dụng đèn báo hiệu. Nếu được chúng ta sẽ thảo luận ngay tại mục này

Theo như giả thuyết, chúng ta có một chiếc cầu với tải trọng hạn chế và chỉ lưu thông được một chiều, nhưng vấn đề về giao thông lại là một bài toán nan giải. Hiện tại thì có rất nhiều xe muốn lưu thông qua chiếc cầu này. Để giải quyết được bài toán này, trước tiên ta dùng đèn báo hiệu (hay đèn lưu thông) với hai trạng thái:
0 - Đèn đỏ (xe ngừng trong khoảng thời gian s giây)
1- Đèn xanh lá (xe được lưu thông tiếp khi đến phiên của mình)

Với hai trạng thái đèn này, tương ứng với hiệu lệnh xe được phép/không được phép qua chiếc cầu tương ứng với khoảng thời gian được thiết lập sẵn, tỉ lệ thuận với chiều dài của chiếc cầu!

Câu 1: Thiết kế lại đèn hiệu ở đầu cầu để cho tối đa được 2 chiếc ô tô cùng 1 lúc trên mặt cầu?

Gán giá trị mutex = 2 (đèn màu xanh da trời) xe 1 lên cầu, sau đó mutex chuyển sang giá trị 1 (đèn màu xanh lá cây), xe 2 tiếp tục lên cầu thì mutex = 0 (đèn màu đỏ), khi đó xe 3 phải dừng lại chờ while(mutex<=0) cho đến khi xe 1 vừa xuống cầu thì hàm signal sẽ chuyển giá trị mutex=1 (đèn màu xanh da trời), vậy xe 3 được phép lên cầu. Vậy sẽ đảm bảo cho tối đa 2 xe cùng trên cầu.

Câu 2: Đồng bộ công việc sao cho P1 trước P2, P2 trước P3

semaphore synch1 = 0;
semaphore synch2 = 0;

Cấu trúc P1:
S1
signal(synch1);

Cấu trúc P2:
wait(synch1)
S2
signal(synch2);

Cấu trúc P3:
wait(synch2)
S3

Câu 3: Đồng bộ P1, P2, P3 sao cho P1 trước P2 và P3

semaphore synch1 = 0;
semaphore synch2 = 0;

Cấu trúc P1:
S1
signal(synch1);
signal(synch2);

Cấu trúc P2:
wait(synch1)
S2

Cấu trúc P3:
wait(synch2)
S3

Câu 4: Đồng bộ P1, P2, P3 sao cho P1, P2 trước P3

semaphore synch1 = 0;
semaphore synch2 = 0;

Cấu trúc P1:
S1
signal(synch1);

Cấu trúc P2:
S2
signal(synch2);

Cấu trúc P3:
wait(synch1);
wait(synch2)
S3

NguyenThiMai(I22A) đã viết:Mục đích của đồng bộ hóa công việc các tiến trình
- Đồng bộ hóa công việc của tiến trình cũng như đồng bộ hóa công việc của luồng.
- Đồng bộ làm cho các tiến trình làm việc có trật tự không hổn loạn.
- Đảm bảo các tiến trình làm việc có chờ đợ nhau 1 cách logic.
* Vd về tính nhất quán của tài nguyên dùng chung: các sv là các luồng, cái bảng là tài nguyên dùng chung, các sv viết thông tin lên bảng, thì thông tin đó được chia sẽ cho tất cả các sv.
* Vd về vi phạm tính đúng đắn và nhất quán: là 2 sv cùng sửa nội dung cái bảng cùng 1 lúc, 2 sv đó làm việc cùng 1 lúc thì nội dung sẽ k nhất quán -> không đồng bộ.
* vd về tính đồng bộ: các bạn được thầy gọi lên nộp bài theo mục quản, thầy gọi 1 lượt 5 bạn và làn lượt nộp bài, ai đến trc thì nộp trc 1 cách có thứ tự.

Các bạn góp ý vài dòng nào

Thêm 01 ví dụ

Bạn A đang giải bài tập. Bạn B đển rủ bạn A đi chơi. B chờ A giải bài tập xong thì cả hai bạn A & B cùng đi chơi. (Đồng bộ nghĩa là có chờ)

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ:
ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Ba
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011
Người làm đơn
....(chữ ký)....
Lê Văn Ba


. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Bàng
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 5 tháng 5 năm 2011
Người làm đơn
....(chữ ký)....
Lê Văn Bá

Khái niệm đèn hiệu
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S)
{
S ++; // Tăng S lên 1
}

-Việc kiểm tra S <= 0 và giảm S (trong 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 Operations).

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// 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 nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
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.
- CritSec 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.

Edsger Wybe Dijkstra (11 tháng 5, 1930 tại Rotterdam – 6 tháng 8, 2002 tại Nuenen), là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Tự ổn định
Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.



Tiểu sử
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.
Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization – một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.
Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 “A Case against the GO TO Statement” (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.
Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để “phát triển chứng minh và chương trình một cách đồng thời”. Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là “đúng đắn theo cách xây dựng” (correct by construction).
Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas.
Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo “Self-stabilizing Systems in Spite of Distributed Control” của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó , để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như “Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn” (Computer Science is no more about computers than astronomy is about telescopes.)
Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

Semaphores
-Định nghĩa: Semaphores là một cờ hiệu trong thực thi đa tuyến, nếu một tuyến cần sử dụng tài nguyên nó sẽ thông báo với semaphores.
-Khởi đầu Semaphores mang giá trị dương. Tuyến yêu cầu sử dụng tài nguyên bằng cách gọi hàm sem_wait(), semaphores sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphores vẫn còn >0, nó sẽ tự động làm giảm giá trị đi 1 và cho phép tuyến sử dụng tài nguyên.
-Nếu giá trị Semaphores <=0 hệ thống sẽ tạm thời dừng tuyến.
-Khi một tuyến sử dụng xong tài nguyên nó gọi hàm sem_post() để trả quyền sử dụng tài nguyên lại cho Semaphores cấp phát cho lần sử dụng khác.
Ứng dụng Semaphores:
-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.