Thảo luận Bài 7

Một cơ sở dữ liệu mà tiến trình muốn đọc(độc giả) hoặc ghi lên đó (nhà văn) . Hệ thống cho phép đồng thời có nhiều tiến trình đọc cơ sở dữ liệu nhưng chỉ duy nhất một tiến trình ghi lên CSDL tại một thời điểm. Khi có một tiến trình ghi lên CSDL thì không có tiến trình nào được phép truy cập đến CSDL kể cả tiến trình đọc .
Yêu cầu: Lập trình cho hai tiến trình “Độc giả “ và “nhà văn”
Seamphore Mutex =1;
Semaphore Db=1;// Truy cập vào DBF của tiến trình Writer
int rc; // Đếm số tiến trình đọc
void Reader (void )
{ while (TRUE)
{ down (Mutex);
rc= rc+1;
if ( rc==1)
down(db);
up(Mutex);
ReadDBF();
down(Mutex);
rc=rc-1;
if (rc==0)
up(db);
up(Mutex);
}
}
void Writer (void )
{ while (TRUE)
{ CreateData();
down(db);
WriteData();
up(db);
}
}
Các bạn cùng thảo luận bài toán này!

Có 5 nhà hiền triết ngồi quanh một bàn tròn trong một bữa ăn tối. Mỗi người có một dĩa mì Spaghetti. Mỗi người cần phải có 2 nĩa để có thể ăn mì. Giữa 2 dĩa có một nĩa.
Giả định rằng cuộc đời của nhà hiền triết chỉ luân phiên nhau 2 hành vi: ăn và suy nghĩ. Khi nhà hiền triết cảm thấy đói ông ta muốn lấy 2 nĩa bên trái và phải theo thứ tự nào đó. Nếu lấy được cả 2 nĩa ông ta bắt đầu ăn. Sau đó đặt nĩa xuống và tiếp tục suy nghĩ.
Yêu cầu viết chương trình cho mỗi nhà hiền triết sao cho không bị “kẹt”.
#define N 5
typedef int Semaphore;
Semaphore Mutex=1;
void HiềnTriết (int i)
{ while(TRUE)
{ SuyNghĩ();
down(&Mutex);
LấyNĩa(i);
LấyNĩa((i+1)%N); // Nhà hiền triết I lấy nĩa bên trái, phải
Ă n();
ĐặtNĩa(i);
ĐặtNĩa((i+1)%N);
up(&Mutex);
}
}

Định nghĩa: Semaphore 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 semaphore.
-Khởi đầu Semaphore 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(), semaphore sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphore 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ị Semaphore <=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 Semaphore cấp phát cho lần sử dụng khác.
Ứng dụng Semaphore:
-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ụ.

- Năm nhà hiền triết ngồi quanh một chiếc bàn tròn
- Trên bàn, giữa họ là những chiếc đũa.
- Các nhà hiền triết độc lập với nhau và suy nghĩ.
- Khi đói, mỗi người nhấc đũa 2 bên và nếu được cả đôi thì bắt đầu ăn, sau đó đặt từng chiếc đũa về vị trí cũ.
- Lập trình hành vi của mỗi hiền triết để không xảy ra hiện tượng Deadlock.
- Deadlock xảy ra khi: Các hiền triết cùng một lúc nhấc đũa bên trái hoặc đũa bên phải. Cứ thế chờ nhau mà không ai được ăn cả. Đó là hiện tượng Chờ xoay vòng (Circular Waiting).
- Thuật giải chính: Mỗi hiền triết tìm cách lấy đủ 2 đũa hai bên. Không đủ 2 đũa, không lấy.

Các ký hiệu:
‘d’ : đói.
‘a’ : đang ăn
‘-‘ : đang suy nghĩ.

Chopsticks[]: mảng đèn hiệu các cây đũa, chopstick[i]=TRUE, đũa rảnh có thể lấy.

Mảng cs[2]: trạng thái cây đũa bên trái và bên phải

WaitForMultipleObjects(2, cs, TRUE, INFINITE); chờ cho tới khi cs[0],cs[1] đều có giá trị là TRUE.

ReleaseMutex(chopsticks[LEFT]): nhả đèn hiệu của 1 cây đũa.

#define numPhilosophers 5

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

HANDLE chopsticks[numPhilosophers]; // mang(den hieu)
char chState[numPhilosophers+1]; // mang trang thai cac cay dua
char phState[numPhilosophers+1]; // mang trang thai cac nha hien triet

void PhilosopherThread(int id){
HANDLE cs[2];
while (1) {
// Suy nghi ...
Sleep(GetTickCount()%1000);
// Doi, do vay tim cach lay du 2 dua Trai-Phai
phState[id]='d';
cs[0]=chopsticks[LEFT];
cs[1]=chopsticks[RIGHT];
// Cho den khi co du 2 dua Trai-Phai
WaitForMultipleObjects(2, cs, TRUE, INFINITE); // chờ cho toi khi cs[0],cs[1] cung co gia tri la TRUE.
chState[LEFT]='0'; // Khi cho xong xét trang thái dua bận
chState[RIGHT]='0';
// Bat dau an ...
phState[id]='a';
printf("- Chopsticks:\\t%s\\n Philosophers:\\t%s\\n\\n", chState, phState);
Sleep(GetTickCount()%1000);

// An xong trở lại trạng thái suy nghĩ

phState[id]='-';
chState[LEFT]='1'; ReleaseMutex(chopsticks[LEFT]); // Dat dua Trai xuong
chState[RIGHT]='1'; ReleaseMutex(chopsticks[RIGHT]);// Dat dua Phai xuong
}
}

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

// khởi tạo trạng thái ban đầu, tất cả hền triết đều đang suy nghĩ.

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

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

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

for (i=0; i// tạo tiến trình các nhà hiền triết. chạy hàm PhilosopherThread.
handles[i]=CreateThread(0,0,(LPTHREAD_START_ROUTINE)PhilosopherThread,(void *)i,0,&threadID);
WaitForMultipleObjects(numPhilosophers, handles, TRUE, INFINITE);
for (i=0; i}

ai có code demo SX-TT vs2005.mà thầy trình chiếu.cho em xin với.em kiếm trong mục học liệu mà ko có.thanks trước nha

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

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 thư viện của trường học chỉ có 1 máy tính (tài nguyên dùng chung) , Sinh viên A vào sử dụng máy tính để nghiên cứu tư liệu .Sinh viên B vào sau muốn sừ dụng máy tính thì phài đợi SV 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 .

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty X
Tôi tên là: Nguyễn Văn A
.........(nội dung đơn).........
TP.HCM, ngày 20 tháng 10 năm 2011
Người làm đơn
............(chữ ký).............
Nguyễn Văn A

Nội dung đơn này phải đảm bảo tính toàn vẹn( Integrity), ví dụ: Phía trên là Nguyễn Văn A thì phía dưới cũng phải là Nguyễn Văn A.
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 Nguyễn Văn A phía trên thành Nguyễn Văn An, trong khi P2(nhà sản xuất khác) sửa Nguyễn Văn A phía dưới thành Nguyễn Văn Ân, 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.

Thế nào là loại trừ lẫn nhau? Cho ví dụ minh họa.
- Giả sử có n tiến trình { P0, P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên 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).
Ví Dụ Minh họa:
trong giờ kiểm tra môn hệ điều hành khi làm bài xong thầy gọi từng bạn lên nộp bài trong cùng lúc đó thì cũng có nhiều bạn lên nộp bài vì vậy các bạn đó phải chờ khi nào thầy gọi đến lượt thỉ mới được nộp bài.

Giả sử có 1 đơn dạng như sau trong vùng nhớ chung (ví dụ, trong Buffer) được các tiến trình cùng sử dụng:

ĐƠN XIN VIỆC

Kính gửi: Giám đốc công ty X
Tôi tên là: Nguyễn Văn A
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày ... tháng ... năm 2012
Người làm đơn
....(chữ ký)....
Nguyễn Văn A

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à Nguyễn Văn A thì phía dưới cũng phải là Nguyễn Văn A. Nếu có nhiều tiến trình cùng sửa đơn trên cùng 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 Nguyễn Văn A phía trên thành Phan Văn B, trong khi P2 (nhà sản xuất khác) sửa Nguyễn Văn A phía dưới thành Phan Văn Ba, 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à: Nguyễn Văn A
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày ... tháng ... năm 2012
Người làm đơn
....(chữ ký)....
Nguyễn Văn A

Vấn đề về đoạn tương tranh:
Các tiến trình tác động liên quan đến thao tác tài nguyên dùng chung, sử dụng các mã lệnh trong quá trình thực hiện thì xảy ra tranh chấp gọi là đoạn tương tranh.

Tính loại trừ lẫn nhau: tại một thời điểm chỉ có thể chấp nhận cho một tiến trình đăng nhập(được chờ ở vùng đang nhập) và vùng tương tranh để thực thi. Khi thực thi xong sẽ thông báo cho các tiến trình đang chờ ở vùng đăng nhập tiếp tục thực hiện.

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.

Câu 1: trình bày mục đích của đồng bộ hóa công việc của các tiến trình. Cho ví dụ.
Câu 2: Trình bày khái niệm “đoạn tương tranh” và tính loại trừ tương hỗ trong công việc của các tiến trình đồng hành song song cùng tranh chấp tài nguyên chung.
Câu 3: trình bày khái niệm “đèn hiệu” và hai ứng dụng của đèn hiệu.
Thảo luận 1: Tại sao chúng ta cần phải biết nhiều thuật giải, nhiều công nghệ cả hiện đại lẫn lạc hậu.
Thảo luận 2: Tìm hiểu các giải thưởng Turing, Fields, Nobel.

Chúng ta cần phải biết cả cái cũ lẫn cái mới (cái lạc hậu và cái hiện đại) là bắt nguồn từ yêu cầu của thực tế. Nhiều lúc, nhiều trường hợp trong thực tế không cần đến cái quá tân tiến, hiện đại, tốn kém. Chỉ cần cái thích hợp nhất, cho hiệu quả nhất, trong trường hợp đó thì mình chỉ cần áp dụng cái lạc hậu, cái cũ, cái rẻ tiền là được rồi.

Giải thưởng Turing (A. M. Turing Award) là giải thưởng thường niên của Hiệp hội Khoa học Máy tính Association for Computing Machinery cho các cá nhân hoặc một tập thể với những đóng góp quan trọng cho cộng đồng khoa học máy tính.
Giải thưởng thường được coi như là giải Nobel cho lĩnh vực khoa học máy tính.
Giải thưởng được đặt theo tên của nhà bác học Alan Mathison Turing, nhà toán học người Anh, người được coi là cha đẻ của lý thuyết khoa học máy tính và trí tuệ nhân tạo.
Từ năm 2007, giải thưởng có giá trị $250.000, được đồng tài trợ bởi Intel và Google.
Người nhận giải thưởng đầu tiên năm 1966, là Alan Perlis của viện Carnegie Institute of Technology.
Năm 2006, Frances E. Allen của IBM là người phụ nữ đầu tiên và duy nhất cho đến nay được nhận giải thưởng.

Huy chương Fields là một giải thưởng được trao cho tối đa bốn nhà toán học không quá 40 tuổi tại mỗi kì Đại hội quốc tế (ICM) của Hiệp hội Toán học quốc tế (IMU), được tổ chức 4 năm một lần. Giải thưởng được sáng lập bởi nhà toán học Canada John Charles Fields lần đầu được trao vào năm 1936, đã bị gián đoạn trong suốt qua thời kỳ Chiến tranh thế giới thứ hai và từ năm 1950 được trao đều đặn.
Mục đích của giải thưởng là sự công nhận và hỗ trợ cho các nhà toán học trẻ tuổi đã có những đóng góp quan trọng có tính cách đột phá cho ngành toán học. Huy chương được đi kèm với số tiền thưởng cổ vũ tượng trưng là 15.000 đôla Gia Nã Đại.
Huy chương Fields thường được coi là "Giải Nobel dành cho Toán học". Sự so sánh này là không thật sự chính xác, bởi vì giới hạn tuổi của giải Fields được áp dụng nghiêm ngặt. Hơn nữa, giải Fields Medals thường được trao cho các nhà toán học có nhiều công trình nghiên cứu hơn là chỉ có một nghiên cứu quan trọng.

Giải thưởng Nobel là một tập các giải thưởng quốc tế được tổ chức trao thưởng hằng năm kể từ năm 1901 cho những cá nhân đạt thành tựu trong lĩnh vực vật lý, hoá học, y học, văn học và hoà bình; đặc biệt là giải hoà bình có thể được trao cho tổ chức hay cho cá nhân.
Vào năm 1968, Ngân hàng Thụy Điển đưa thêm vào một giải về lĩnh vực khoa học kinh tế để tưởng nhớ nhà khoa học Alfred Nobel, người đã sáng lập ra giải Nobel.
Kết quả đoạt giải được công bố hằng năm vào tháng 10 và được trao (bao gồm tiền thưởng, một huy chương vàng và một giấy chứng nhận) vào ngày 10 tháng 12, ngày kỷ niệm ngày mất của Nobel. Giải Nobel được thừa nhận rộng rãi như là giải thưởng danh giá nhất một người có thể nhận được trong lĩnh vực được trao.

Hàm Wait: chờ cho đến khi giá trị của đèn hiệu S >= 1 sau đó qua được lệnh chờ này và giá trị của đèn tự đông giảm đi 1.
Hàm signal: Giá trị của đèn S được tăng thêm 1.

nguyendangnguyen43(i13a) đã viết: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).

vi dụ của bạn giúp mình hiểu rồi.cám ơn you nhiều nha.

nguyendangnguyen43(i13a) đã viết: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).

Thanks

Đả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: Trường học chỉ có 1 phòng thí nghiệm (tài nguyên dùng chung), lớp nào có giờ học trước thì được vào thí nghiệm trước, các lớp còn lại phải đợi đến khi lớp nào lớp trước học xong thì mới được vào phòng thí nghiệm

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
WaitForSingleObject(semEmpty, INFINITE); // Chờ đến khi có chỗ trống
EnterCriticalSection(&critSec);// Vào đoạn tương tranh
ReleaseSemaphore(semFull, 1, NULL);// Tăng (semFull) lên 1
LeaveCriticalSection(&critSec);// Rời khỏi đoạn tương tranh
SuspendThread(GetCurrentThread());// luồn hiện hành ngủ tại đây
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
WaitForSingleObject(semFull, INFINITE);// Chờ đến khi có sản phẩm
EnterCriticalSection(&critSec);// Vào đoạn tương tranh
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
ReleaseSemaphore (semEmpty, 1, NULL);// Tăng (semEmpty) lên 1
LeaveCriticalSection(&critSec);//Rời khỏi đoạn tương tranh
SuspendThread(GetCurrentThread());//luồng hiện hành ngủ tại đây
}
}
- 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 nhằm đả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.

Có bạn nào giải được bài toán sản xuất và tiêu thụ đc đồng bộ với 3 đèn hiệu trở lên? Monhf tìm mà không thấy có.

- Mục đích của đồng bộ hóa công việc của các tiến trình nhằm đảm bảo tính nhất quán tính toàn vẹn của tài nguyên dùng chung và tránh được hiện tượng ket(dealdock)
ví dụ:
-Ban lớp trưởng lên bảng(Tài nguyên dùng chung) viết tên email số điện thoại của mình cho lớp, nếu bạn chưa viết xong mà bạn khác chụp ảnh trên bảng để đưa về xử lý sẽ dẫn đến thông tin bị sai, do vậy việc đồng bộ có tác dụng rất lớn nghĩa là chờ bạn lớp trưởng viết xong(nghĩa là có chờ) sau đó mới chụp ảnh lấy về thì đảm bảo thông tin chính xác.

- Giả sử có n tiến trình { P0, P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên 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).
- Xác định đoạn tương tranh là 1 đoạn mã của tiến trình mà khi thực hiện nó truy cập, tác động và thay đổi tài nguyên dùng chung.
- vd:
+ thầy kêu 5 bạn lên nộp bài thì sẽ chỉ có 1 bạn được kêu đầu tiên nộp bài trước và 4 bạn kia phải chờ,không thể 2 bạn cùng nhau lên nộp bài cùng lúc được nếu không thì sẽ không đảm bảo được tín loại trừ lẫn nhâu và đảm bảo được tín đồng bộ.
+ 2 bạn lên bảng sữa bài tập thì chỉ có 1 bạn được lên sữa trước và bạn kia phải chờ cho đến khi nào bạn này sữa xong thì mới được lê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).

Hai ứng dụng đèn hiệu:

1. Giải quyết vấn đề VTT.
Mã của tiến trình Pi bây giờ có cấu trúc:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) { // (Đèn hiệu Nhị phân)
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}


2. Giả sử P1 có mã S1 , P2 có mã S2 , cần tổ chức sao cho S2 chỉ thi hành sau S1 .
Ta dùng đèn hiệu sau:
semaphore synch = 0;
Cấu trúc P1 : Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2

Giống nhau:
cả mutex và semaphore đều được sử dụng để quản lý việc truy xuất của những process tới 1 tài nguyên (thường là vùng nhớ) được shared bởi các process này.
khác nhau:
- semaphore:
+ tại một thời điểm có nhiều hơn 1 process được truy cập vào tài nguyên dùng chung được semaphore quản lý. (số lượng process này được giới hạn ở một số lượng nhất định-một số hữu hạn process được truy cập vào vùng tài nguyên dùng chung này).
- mutex:
+ tại một thời điểm chỉ có được 1 process được truy cập vào tài nguyên này, nếu tài nguyên này đã được chiếm giữ thì process khác phải chờ để tới lượt.
+ khi tài nguyên này được "chiếm giữ" bởi 1 process thì mutex này sẽ được thiết lập trạng thái là false để các process khác không được action vào.

Trình bày những lý do đồng bộ hóa công việc tiến trình..
- 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 )