Thảo luận Bài 7

- Đả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

#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef unsigned int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];
void Sinhvien (int i)
{
while (còn cơm)
{
think(); //công đoạn 1
take_forks(i); //công đoạn 2, có thể bị kẹt 1 thời gian
eat(); put_forks(i); //công đoạn 3
}
}
void take_forks(int i)
{
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đũa
state[i] = HUNGRY; //ghi nhận trạng thái đang cố gắng lấy đũa
test(i); //kiểm tra lấy được không ? nếu được s[i] → 1
up(&mutex); //đánh thức các SV khác để họ truy xuất đũa
down(&s[i]); //cố gắng và cơm & gắp thức ăn, có thể bị kẹt
}
void test (int i)
{
if (state[i] == HUNGRY //SV i muốn lấy đũa
&& state[LEFT] != EATING //SV bên trái chưa lấy
&& state[RIGHT] != EATING) //SV bên phải chưa lấy
{
state[i] = EATING; //ghi nhận SV i đã lấy được đũa
up(&s[i]); //tăng s[i] → 1
}
}
void put_forks (int i)
{
down(&mutex); //đảm bảo 0 tranh chấp khi lấy đũa
state[i] = THINKING; //ghi nhận trạng thái không dùng đũa
test(LEFT); //kiểm tra lấy được không ? nếu được đánh thức
//SV LEFT dậy để và cơm và gắp thức ăn
test(RIGHT); //kiểm tra lấy được không ? nếu được đánh thức
//SV RIGHT dậy để và cơm và gắp thức ăn
up(&mutex); //đánh thức các SV khác để họ truy xuất đũa
}

-Đèn hiệu có tên dùng để liên lạc giữa các tiến trình nặng truyền thống.
- Đèn hiệu không tên được dùng để liên lạc bên trong nội bộ của tiến trình truyền thống (giữa các luồng của nó).Ưu điểm của đèn hiệu không tên này là nó thực hiện công việc nhanh và tính bảo mật của nó cũng tốt hơn.
Bài toán Producer-Consumer dùng kỹ thuật Busy-Waiting trước đây có nhược điểm là làm cho máy tính bị chậm, tiêu tốn CPU.
Cải tiến bài toán này dùng kỹ thuật đèn hiệu có ưu điểm: chờ cho đến khi có chỗ trống, 1 khi chưa có chỗ trống thì phải chờ. Điều này làm cho không cần tiêu tốn CPU vô ích=> Máy tính sẽ nhanh hơn.
Đoạn code khai báo đèn hiệu
# Define BUFFER_SIZE 10 // Định nghĩa 1 biến BUFFER_SIZE với max =10
int buffer[BUFFER_SIZE];
char(BUFFER_SIZE);
int in=0;// Khai báo con trỏ in
int out=0;// Khai báo con trỏ out
int nextproduced=1;
HANDEL SemEmty,SemFull;// Khai báo hai đèn hiệu
CRITICAL_SECTION critsec;// Biến chứa đối tượng đèn hiệu nhị phân dùng để bảo vệ đoạn tương tranh trong chương trình.
item nextProduced;

while (1) { //lặp vô hạn để tạo 1 sản phẩm và đưa vào nextProduced
entry section
while (((in + 1) % BUFFER_SIZE) == out);
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
exit section
}

item nextConsumed;
while (1) {


while (in == out);
entry section
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
// Tiêu thụ sản phẩm trong nextConsumed
exit section
}

HANDLE s;
s=CreateSemaphore(0, n, max, t);
//n: tạo đèn hiệu với giá trị ban đầu là n.
//max: giá trị tối đa được phép có của đèn hiệu.
//t: là tên của đèn hiệu. Tên có thể là 1 chuỗi kí tự nằm trong ngoặc kép hoặc là số 0, nếu là số 0 thì đèn hiệu không tên hay là đèn hiệu nạt danh.
Phân biệt đèn hiệu không tên với đèn hiệu có tên:
_Đèn hiệu có tên dùng để liên lạc giữa các tiến trình nặng truyền thống.
_Đèn hiệu không tên chỉ được dùng để liên lạc bên trong lòng của tiến trình truyền thống(giữa các luồng của nó).
_Đèn hiệu có tên còn được gọi là đèn hiệu liên tiến trình.
_Đèn hiệu không tên còn được gọi là đèn hiệu nội tiến trình, nó sẽ bảo mật tốt hơn.
WaitForSingleObject(s, timeout): chờ cho đến khi đèn hiệu mà mục quản của nó lưu trong biến s có giá trị là khác 0 với thời gian không quá thời gian timeout.
Timeout: chờ đến khi đèn xanh nhưng không quá 5000ms.
Wait(s): chờ 1 đối tượng.
Signal(s): tăng giá trị của mục quản trong biến s lên 1.

ReleaseSemaphore(s, 1, NULL): nhả giá trị của đèn hiệu(tăng lên 1 nhưng không vượt quá max)

Edsger Wybe 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[2].

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ó [3], để đ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.)[4]

Ô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.

Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956 và ấn bản năm 1959[1], là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán thường được sử dụng trong định tuyến với một chương trình con trong các thuật toán đồ thị hay trong công nghệ Hệ thống định vị toàn cầu (GPS).
Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.

Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.

Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.
Giới thiệu thuật toán
Xét đồ thị G =(X,E) với các cạnh có trọng số không âm. - Dữ liệu nhập cho thuật toán là ma trận trọng số L (với qui ước Lhk = +∞ nếu không có cạnh nối từ đỉnh h đến đỉnh k)và hai đỉnh x,y cho trước. - Dữ liệu xuất là đường đi ngắn nhất từ x đến y.

Chứng minh
Ý tưởng của thuật toán được chứng minh như sau.

Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.

Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.

Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy,
Mã giả
Phân tích
Với giải thuật đã mô tả ta dễ dàng thực hiện trực tiếp trên các đồ thị kích thước nhỏ,để có thể mã hóa và cài đặt hiệu quả cần đưa thêm các cấu trúc dữ liệu để sử dụng trong giải thuật.

Dữ liệu
Hàm d(u) dùng để lưu trữ độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Rõ ràng d(s)= 0. Ký hiệu X^-(u) là tập tất cả các đỉnh có cạnh đi tới đỉnh u. Nếu với mọi v \in X^-(u) đã xác định được d(v) thì:
d(u)= min\{d(v)+w(v,u), v\in X^-(u)\}
.

Để tính được giá trị nhỏ nhất này, như thông thường khi khởi tạo ta phải gán cho d(v)=\infty, sau đó gặp giá trị nhỏ hơn thì thay thế lại.
Thời gian chạy
Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O(n^2+m). Tuy nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp sẽ là O( (m+n)\log n ), nếu dùng đống Fibonacci thì độ phức tạp giảm xuống còn O( m + n\log n ). Trong đó m là số cạnh, n là số đỉnh của đồ thị đang xét.
Những đỉnh đã tính được d(v)hữu hạn được cho vào một hàng đợi có ưu tiên. Hàng đợi này luôn được bổ sung và sắp xếp lại nên một cấu trúc hợp lý là cấu trúc đống nhị phân (heap).
Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta dùng hàm COLOR(u) xác định với mọi v\in V. Lúc đầu các đỉnh được tô màu trắng (WHITE), khi cho vào hàng đợi nó được tô màu xám (GRAY), khi đã tính xong khoảng cách nó được tô màu đen(BLACK).
Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để chỉ đỉnh đứng ngay trước đỉnh u trên đường đi ngắn nhất từ s tới u.

Một quá trình hợp tác là một quá trình có thể gây ảnh hưởng hay bị ảnh hưởng tới quá trình khác đang thực thi trong hệ thống. Các quá trình hợp tác có thể chia sẻ trực tiếp không gian địa chỉ luận lý (mã và dữ liệu), hay được phép chia sẻ dữ liệu thông qua các tập tin. Trường hợp đầu đạt được thông qua việc sử dụng các quá trình có trọng lượng nhẹ hay luồng. Truy xuất đồng hành dữ liệu được chia sẻ có thể dẫn tới việc không đồng nhất dữ liệu. Trong chương này chúng ta sẽ thảo luận các cơ chế đảm bảo việc thực thi có thứ tự của các quá trình hợp tác chia sẻ không gian địa chỉ để tính đúng đắn của dữ liệu luôn được duy trì.

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).

Tên đầy đủ là Edsger Wybe Dijkstra, sinh ngày 11 tháng 5 năm 1930 tại Rotterdam, mất ngày 6 tháng 8 năm 2002 tại Nuenen sau một thời gian dài bị ung thư, ông 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.
_ 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).
_ 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.
_ 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".
_ Một năm sau khi ông mất, 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.

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).

Mục đích của đồng bộ hóa công việc các tiến trình nhầm đảm bảo các tiến trình làm việc nhất quán, chờ lẫn nhau, sử dụng chung tài nguyên và tránh được hiện tượng kẹt tiến trình.

VD:
- có 2 bạn, bạn A đang làm bài tập, B rủ A đi chơi, để đồng bộ thì B phải chờ cho A làm bài xong rồi cùng đi chơi
- Cả lớp là tiến trình nặng, mỗi người là tiến trình nhẹ, thầy gọi 1 bạn lên bảng giải bài tập, muốn gọi bạn tiếp theo lên thì phải đợi bạn trước làm xong
VD trường hợp vi phạm nhất quán.
-Khi A đang soạn đơn xin việc và B lại sửa tên, bạn X chụp lại bảng => ghi tên và ký tên khác nhau => vi phạm nhất quán

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).

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

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.

DINING-PHILOSOPHERS (Có DEADLOCK)

#include
#include

#define numPhilosophers 5

#define LEFT id
#define RIGHT (id+1)%numPhilosophers

HANDLE chopsticks[numPhilosophers];
char chState[numPhilosophers+1];
char phState[numPhilosophers+1];

void PhilosopherThread(int id){
while (1) {
// Suy nghĩ ...
Sleep(GetTickCount()%2000);
// Đói, do vậy lấy đũa bên Trái
phState[id]='d';
WaitForSingleObject(chopsticks[LEFT], INFINITE);

chState[LEFT]='0';
printf("- Chopsticks:\t%s\n  Philosophers:\t%s\n\n",  chState, phState);
Sleep(GetTickCount()%100);

// Rồi lấy đũa bên phải
WaitForSingleObject(chopsticks[RIGHT], INFINITE);
chState[RIGHT]='0';
// Bắt đầu ăn ...
phState[id]='a';
printf("- Chopsticks:\t%s\n  Philosophers:\t%s\n\n", chState, phState);
Sleep(GetTickCount()%1000);
// Ăn xong
phState[id]='-';
// Đặt đũa trái xuống
chState[LEFT]='1';
ReleaseMutex(chopsticks[LEFT]);
// Đặt đũa phải xuống
chState[RIGHT]='1';
ReleaseMutex(chopsticks[RIGHT]);
}
}
void main(){
HANDLE handles[numPhilosophers];
DWORD threadID; int i;

chState[numPhilosophers]='\0'; phState[numPhilosophers]='\0';

for (i=0; i chState[i]='1'; phState[i]='-';
}
for (i=0; i chopsticks[i]=CreateMutex(0, FALSE, 0);

printf("- Chopsticks:\t%s\n  Philosophers:\t%s\n\n", chState, phState);

for (i=0; i  handles[i]=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)PhilosopherThread,
(void *) i, 0, &threadID);
WaitForMultipleObjects(numPhilosophers, handles, TRUE, INFINITE);
for (i=0; i}


DINING-PHILOSOPHERS (Không DEADLOCK)

#include
#include

#define numPhilosophers 5

#define LEFT id
#define RIGHT (id+1)%numPhilosophers

HANDLE chopsticks[numPhilosophers];
char chState[numPhilosophers+1];
char phState[numPhilosophers+1];

void PhilosopherThread(int id){
HANDLE cs[2];
while (1) {
// Suy nghĩ ...
Sleep(GetTickCount()%1000);
// Đói, do vấy lấy hai đũa Trái - Phải
phState[id]='d';

cs[0]=chopsticks[LEFT];
cs[1]=chopsticks[RIGHT];
WaitForMultipleObjects(2, cs, TRUE, INFINITE);
chState[LEFT]='0';
chState[RIGHT]='0';
// Bắt đầu ăn ...
phState[id]='a';
printf("- Chopsticks:\t%s\n Philosophers:\t%s\n\n",
chState, phState);
Sleep(GetTickCount()%1000);
// Ăn xong
phState[id]='-';
chState[LEFT]='1'; ReleaseMutex(chopsticks[LEFT]);
chState[RIGHT]='1'; ReleaseMutex(chopsticks[RIGHT]);
}
}

void main(){
HANDLE handles[numPhilosophers];
DWORD threadID; int i;

chState[numPhilosophers]='\0'; phState[numPhilosophers]='\0';

for (i=0; i chState[i]='1'; phState[i]='-';
}
for (i=0; i chopsticks[i]=CreateMutex(0, FALSE, 0);

printf("- Chopsticks:\t%s\n  Philosophers:\t%s\n\n", chState, phState);

for (i=0; i handles[i]=CreateThread(0,0,
(LPTHREAD_START_ROUTINE)PhilosopherThread,
(void *) i, 0, &threadID);
WaitForMultipleObjects(numPhilosophers, handles, TRUE, INFINITE);
for (i=0; i}
Vấn đề Deadlock xảy ra khi đồng thời các nhà hiền triết cùng nhau lấy đũa trái, nếu không ai chịu bỏ đũa của mình xuống thì sẽ không ai được ăn.
Cách giải quyết Deadlock được thực hiện như sau:
Một nhà hiền triết nào đó nhanh tay lấy hai đũa trái và phải, khi ăn xong thi hiền triết bỏ đũa xuống. Vậy tức là người sau sẽ được ăn.

‰ Trong hệ đa chương, thường có nhiều process chạy song hành,
nhưng mỗi process có không gian làm việc độc lập, không ai có
thể truy xuất trực tiếp không gian làm việc của process khác => rất
tốt cho việc bảo vệ chúng lẫn nhau nhất lý khi các process này là
những chương trình độc lập.
‰ Nếu 2 hay nhiều process cần giao tiếp nhau để đồng bộ hay để
trao đổi dữ liệu, ta cần cung cấp cơ chế cho chúng. Có 2 cơ chế
giao tiếp chính giữa các process : truy xuất bộ nhớ dùng chung và
gởi/nhận thông báo.
‰ Truy xuất bộ nhớ chung là 1 trong nhiều hoạt động tương tranh
giữa các process. Vấn đề tương tranh trên 1 tài nguyên dùng
chung là vấn đề lớn cần phải giải quyết triệt để vì nếu nhiều
process truy xuất đồng thời vào 1 tài nguyên dùng chung mà
không có sự kiểm soát thì dễ xảy ra lỗi làm hư hỏng tài nguyên.

Đả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.
ví dụ: có 2 nhân viên A và B muốn photo giấy tờ nhưng chỉ có 1 máy photocopy(tài nguyên dùng chung), khi nhân viên A sử dụng máy photocopy thì nhân viên B phải chờ nhân viên A photo xong mới tới lượt mình sử dụng máy, nếu không có thể sẽ xảy ra lỗi trong quá trình photo giấy tờ.

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á

Xét một giải pháp semaphore đúng cho bài toán Dining philosophers :
#define N 5
#define LEFT(i-1)%N
#define RIGHT(i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
semaphore mutex = 1;
semaphore s[N];//gan tri ban dau =0
//tiến trình mô phỏng triết gia thứ i
void philosopher( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
think(); // Suy nghĩ
take_forks(i); // yêu cầu đến khi có đủ 2 nĩa
eat(); // yum-yum, spaghetti
put_forks(i); // đặt cả 2 nĩa lên bàn lại
}
}
//kiểm tra điều kiện được ăn
void test ( int i) // i là triết gia thứ i : 0..N-1
{
if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!= EATING)
{
state[i] = EATING;
up(s[i]);
}
}
//yêu cầu lấy 2 nĩa
void take_forks ( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
down(mutex); // vào miền găng
state[i] = HUNGRY; // ghi nhận triết gia i đã đói
test(i); // cố gắng lấy 2 nĩa
up(mutex); // ra khỏi miền găng
down(s[i]); // chờ nếu không có đủ 2 nĩa
}
}
//đặt 2 nĩa xuóng
void put_forks ( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
down(mutex); // vào miền găng
state[i] = THINKING; // ghi nhận triết gia i ăn xong
test(LEFT); // kiểm tra ngườii bên trái đã có thể ăn?
test(RIGHT); // kiểm tra ngmái bên phải đã có thể ăn?
up(mutex); // ra khỏi miền găng
}
}

a)Tại sao phải đặt state[i] = HUNGRY trong take_forks ?
b)Giả sử trong put_forks, lËnh gán state[i] = THINKING đmợc thực hiện sau hai lệnh test(LEFT),
test(RIGHT). Điều này ảnh hưởng thế nào đến giải pháp cho 3 triết gia? Cho 100 triết gia?

Bài toán này được đề nghị bởi Dijkstra (1965) để giải quyết vấn đề đồng bộ hóa được gọi là “các triết gia ăn tối”.
Bài toán được mô tả như sau:
Năm triết gia cùng ăn tối quanh một bàn tròn. Trước mặt mỗi ông là một đĩa thức ăn. Để ăn, mỗi người cần phải có 2 chiếc nĩa. Các chiếc nĩa được đặt giữa 2 người. Hoạt động của các triết gia gồm: ăn và suy nghĩ. Khi một triết gia đói, ông ta yêu cầu hai chiếc nĩa (trái và phải). Nếu cả hai chiếc là rỗi, ông ta lấy nĩa để ăn, ngược lại ông ta phải chờ. Sau khi ăn xong, ông ta đặt nĩa ở vị trí cũ và tiếp tục suy nghĩ. Bài toán này được xem như bài toán kinh điển bao gồm nhiều vấn đề như: đồng bộ hóa, cấp phát tài nguyên để tránh khóa chết. Bài toán có thể được giải bằng cách dùng một semaphore mutex. Khi một triết gia cần dùng nĩa, ông phải thực hiện phép down trên mutex. Sau khi
dùng nĩa xong, ông ta lại phải gọi up trên mutex. Từ quan điểm thực tế, ta thấy với 5 chiếc nĩa, ta có thể cho phép hai ông cùng ăn ở một thời điểm. Một cải tiến của giải pháp trên nhằm đảm bảo không xuất hiện khóa chết
và tối đa số triêt gia họat động đồng thời.
Giải pháp sử dụng một mảng của các biến trạng thái, state. Mỗi biến trạng thái lưu giữ trạng thái của một triết gia: ăn (eating), nghĩ (thinking) hay đói – hungry (tức là, yêu cầu dùng nĩa). Một triết gia chỉ có thể chuyển sang trạng thái ăn nếu không có láng giềng nào đang ăn. Triết gia láng giềng được định nghĩa bởi các giá trị LEFT, RIGHT. Ví dụ, triết gia
đang xét là 2, thì các láng giềng là 2, 3.
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N]; /* one semaphore per philosopher */ void philosopher(int i)
{
while (TRUE){
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i)
{
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_forks(i)
{
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}
Chương trình dùng một mảng các semaphore với mỗi semaphore cho một triết gia. Vì vậy, một triết gia yêu cầu nĩa nhưng các nĩa đang bận thì phải chờ. Chú ý rằng mỗi quá trình chạy thủ tục philosopher như hàm main. Nhưng các thủ tục take_forks và put_forks không thể tách rời trên các quá trình khác nhau.

Edsger Wybe Dijkstra (sinh ngày 11 tháng 5, 1930 tại Rotterdam –mất ngày 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.
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.

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.

Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây:

Yêu cầu độc quyền truy xuất (Mutual exclusion)
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một (hay một số lượng hạn chế) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:

• Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
  

• Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
  

Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.

Yêu cầu phối hợp (Synchronization)
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó…

Đoạn tương tranh là một đoạn mã lệnh trong chương trình, mỗi tiến trình có một đoạn mã lệnh dùng để điều khiển công việc các tiến trình, khi mà các đoạn mã này được thực thi (sửa, sử dụng) sẽ tác động đến các tài nguyên hay dữ liệu chung.

- Vùng tranh chấp là vùng xảy ra tranh chấp khi thực hiện đoạn tương tranh. Ví dụ: 2 nhà có chung một mảnh đất, 2 con chó tranh nhau 1 khúc xương,...

- 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 vận hành ở trong đoạn tương tranh, thì không có tiến trình nào khác trong nhóm cùng tồn tại chung đ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, nếu như có một tiến trình khác cũng muốn thực hiện cùng đoạn tương tranh đó thì phải đợi cho đến khi tiến trình đó kết thúc và ra khỏi đoạn tương tranh, lúc đó tiến trình khác mới có thể tiếp tục thực hiện công việc trên đoạn tương tranh đó.

- Các tiến trình tương tranh có cấu trúc mã bao gồm:

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
}

Chú thích:
- Đoạn còn lại: (nằm ngoài đoạn tương tranh) không gây ảnh hưởng gì đến tài nguyên dùng chung.
- Đoạn đăng nhập: báo cho các tiến trình khác biết rằng đang có 1 tiến trình đang vận hành đoạn mã tương tranh.
- Đoạn tương tranh: đoạn mã khi thực thi sẽ gây ảnh hưởng đến tài nguyên dùng chung.
- Đoạn đăng xuất: báo cho các tiến trình khác biết rằng hiện chưa có tiến trình vận hành đoạn mã tương tranh.

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() lol! lol!
{
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());
}
}

Chú thích:
- 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à đèn hiệu nhị phân dùng để bảo vệ đoạn tương tranh bằng cách đảm bảo tính loại trừ tương hỗ giữa các luồng của tiến trình với tài nguyên dùng chung.

• Nhu cầu đồng bộ hóa tiến trình

Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây: cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm.

1. Yêu cầu độc quyền truy xuất

Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lượng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:

• • Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.

• • Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.

Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.

[list=2][*]Yêu cầu phối hợp[/list]
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó …