Thảo luận Bài 7

-Đ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 A
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 1 tháng 1 năm 2012
Người làm đơn
....(chữ ký)....
Nguyen Van B

. 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 A thì phía dưới cũng phải là Lê 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 Lê Văn A phía trên thành Lê Văn C, trong khi P2 (nhà sản xuất khác) sửa Lê Văn A phía dưới thành Lê Vă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 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 C
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 1 tháng 1 năm 2012
Người làm đơn
....(chữ ký)....
Nguyen Van B

Định nghĩa đèn hiệu với 2 tác nguyên Wait và Signal.
- Đè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):

Code:

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

Sử dụng Đèn hiệu nhị phân Mutex để đảm bảo tính loại trừ lẫn nhau.

Code:

typedef int semaphore;
semaphore mutex = 1; // Binary Semaphore
while (1)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}

.

-Bài tóan 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.

Code:

#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

- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm cho các tiến trình có thể tự khóa mình (Block Itseft) và chuyển sang trạng thái waiting, sau đó xếp vào hàng chờ của đèn hiệu. Trình điếu phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.
- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựa chọn và đánh thức bằng lệnh WakeUp(P) để chuyển P từ trạng thái Waiting sang trạng thái Ready. Lúc này trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào thuật giải cụ thể.
.

đây là ví dụ của thầy trên lớp, mấy bạn tham khảo nhé.
ĐƠ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 13 tháng 4 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 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 B, 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 C, 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 14 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Nguyễn Văn C

Giải:
- 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).

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

Ví dụ ở một công ty có sản xuất 1 sản phẩm nào đó, có nhà sản xuất và nhà tiêu thụ.Nhà sản xuất khi sản xuất xong sản phẩm sẽ đưa vào kho chứa hàng --> Khi đó nhà tiêu thụ sẽ đưa sản phẩm trong kho hàng đi tiêu thụ. Để hoạt động sản xuất trơn tru, tiến trình trong chu trình sản xuất thì không được xếp sản phẩm khi chưa hoàn chỉnh vào kho chưa hàng và không được để xảy ra việc có 2 nhà sản xuất cùng ghi vào 1 lú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).
ví dụ:



. 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 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 B, 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 C, 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

câu 1: NHỮNG LÍ DO ĐỒNG BỘ HÓA CÔNG VIỆC TIẾN TRÌNH VÀ CHO VÍ DỤ MINH HỌA
- Đả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 lap ( tài nguyên dùng chung) lớp có giờ học trước thì được vào phòng lap 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 lap

câu 2: KHÁI NIỆM ĐOẠN TƯƠNG TRANH VÀ LOẠI TRỪ LẪN NHAU.CHO VÍ DỤ MINH HỌA
Đoạn tương tranh : xét một hệ có tiến trình P0,P1 ....pn mỗi tiến trình cs 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 thì đoạn mã đó là đoạn tương tranh
Tính loại trừ lẫn nhau hay Loại trừ tương hỗ về phương diện thời gian : khi có một 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ó một tiến trình được phép truy cập vào 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:

ĐƠN XIN VIỆC
Kính gửi: giám đốc cty long trương giang
tên tôi là nguyễn doãn linh
.................. nội dung đơn.......................
TPHCM ngày 5 tháng 5 năm 2011
người làm đơn
........... chữ ký..........
nguyễn doãn linh
nội dung đơn này phải được đảm bảo tính toàn vẹn vídụ: phía trên là nguyễn doãn linh thì dưới cũng phải là nguyễn doãn linh

Các bạn có thể giải thích và so sánh cho mình biết ưu và nhược điểm của thuật giải dùng biến đếm count và thuật giải không dùng biến đếm count để giải quyết bài toán sản xuất và tiêu thụ?
cảm ơn các bạn trước!

Đồ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 deadlock: 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.

- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi dùng xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.
Trình bày giải pháp ngăn chặn Deadlock
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy
Ví dụ đời thường trong lớp của thầy là : kẹt xe giữa đường hay cầu , chỉ cần 1 cái j đó để nhấc các thành phần gây ra kẹt xe ở chỗ bị kẹt 1 thời gian để xe lưu thông là sẽ có thể giải quyết tình trạng này.
Ngăn chặn deadlock (bằng cách phủ định 1 trong 4 điều kiện):
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
Loại bỏ điều kiện loại trừ tương hỗ (loại trừ lẫn nhau):
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
Các process gởi yêu cầu cho printer daemo

• Loại bỏ điều kiện giữ và chờ tài nguyên:

• Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới. Process khai báo tài nguyên và được cấp phát 1 lần. Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.

• Loại bỏ điều kiện không lấy lại tài nguyên (không có tiếm quyền)

• Lấy lại tài nguyên từ process.

VD: Không thể với tài nguyên như máy in.
Loại bỏ vòng chờ các process (chờ vòng xoay).
Có thể quy định số thứ tự tài nguyên. Process chỉ được yêu cầu tài nguyên theo thứ tự tăng.
Giả sử có deadlock:
P1 giữ Ri, chờ Rj -> i < j.
P2 giữ Rj, chờ Rj -> j < i.
Tránh deadlock:
• Chấp nhận các điều kiện tạo deadlock.
• Theo dõi và tránh dẫn đến deadlock.
• Hai hướng giải quyết.
• Không tạo process mới nếu có thể dẫn đến deadlock.:
Process cần khai báo số lượng tài nguyên cần sử dụng.
Không tạo process mới nếu số lượng tài nguyên hệ thống không đủ, có thể dẫn đến deadlock.
• Không cấp phát thêm tài nguyên cho process:
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process.
Định nghĩa trạng thái hệ thống với:
Vector A: tổng số các loại tài nguyên.
Vector B: số tài nguyên mỗi loại chưa dùng.
Ma trận C: số tài nguyên đã cấp phát cho các process.
Ma trận D: số lượng tài nguyên các process sẽ tiếp tục yêu cầu.
Giải pháp để ngăn chặn DeadLock là bằng cách phủ định một trong bốn điều kiện trên như sau:
+Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung.
Ngăn chặn deadlock
Để deadlock xảy ra, một trong bốn điều kiện cần phải xảy ra. Bằng cách đảm
bảo ít nhất một trong bốn điều kiện này không thể xảy ra, chúng ta có thể ngăn chặn
việc xảy ra của deadlock. Chúng ta tìm hiểu tỷ mỹ tiếp cận này bằng cách xem xét
mỗi điều kiện cần riêng rẻ nhau.

Tính nhất quán của tài nguyên dùng chung là đảm bảo được tính đúng đắn, hợp lý, toàn vẹn của tài nguyên dùng chung.

Định nghĩa	Thực thi trong Visual C
typedef int semaphore; semaphore s = n;	HANDLE s; s=CreateSemaphore (0, n, max, t); // t - tên đèn hiệu hoặc 0 //n: giá trị ban đầu của đèn hiệu //max: giá trị tối đa của đèn hiệu
wait (s);	WaitForSingleObject (s, timeout); /* timeout = INFINITE hoặc số ms chờ
signal (s);	ReleaseSemaphore (s, 1, NULL);

Admin
Cần thêm giải thích bằng lời !

Đồng bộ hóa các tiến trình là đồng bộ hóa các công việc của các luồng bên trong tiến trình đó một cách có logic, đúng trật tự, ăn khớp với nhau, tránh tình trạng có quá nhiều tiến trình cùng nhau sữ dụng, tranh chấp CPU, hay dữ liệu dùng chung là xảy ra tình trạng Deadlock, mất mát dữ liệu tất cả nhằm đãm bảo tính nhất hoán của tài nguyên dùng chung,
Tính nhất hoán của tài nguyên dùng chung là đãm bảo tính đúng đắng, hợp lý, tính toàn vẹn của tài nguyên dùng chung.

Ví dụ: Khi một công ty sản xuất ra được một sản phẩm A nào đó, và thực hiện chiến lược PR cho sản phẩm đó thì khi giới thiệu trước công chúng phải nói về các thông tin có liên quan đến sản phẩm A, nói đúng các chỉ tiêu của nó và người tiêu dùng sẽ trực tiếp tiếp thu các thông tin đó từ nhà cung cấp và đưa ra tiêu chí đánh giá, và khi bán A ra thị trường cho người tiêu dùng phải đúng y như những gì mà họ đã giới thiệu ở phần PR nếu ko đúng sẽ vi phạm tính nhất hóa, đồng bộ hóa thông tin của sản phẩm, làm ảnh hường đến sản phẩm và uy tính của công ty.

Admin
Ví dụ mnh hoạ này không nêu được bản chất của vấn đề cần quan tâm !

Đoạn tương tranh là một đoạn mã của tiến trình mà khi thực hiện thì nó truy cập và thay đổi nội dung của tài nguyên dùng chung.
Tính loại trừ tương hỗ: khi có 1 tiến trình đang trong đoạn tương tranh của nó thì chỉ có duy nhất một mình nó tại đó và ko tồn tại bất kỳ một tiến trình nào khác tại đây. Hay nói cách khác là tại một thời điểm thì chỉ có duy nhất 1 tiến trình được phép truy cập và thay đổi nội dung dùng chung.

Ứng dụng 1: Khi có một cây cầu rất yếu chỉ chịu được trọng lượng của một xe đi qua cầu mà cây cầu này nằm trên đoạn đường có rất nhiều xe đi qua lại. vậy phải design đèn tính hiệu như thế nào để xe có thể đi qua cầu mà ko bị xảy ra sự cố?
Giải: chúng ta phải thiết kế đèn hiệu như sau: đèn có 2 chế độ: 0: đỏ(xe ko được qua cầu), 1: xanh(xe được qua cầu), khi có một xe đang đi qua cầu, thì lúc đo cầu đang chịu một trọng lượng nhất định thì đèn sẽ chuyển sang màu đỏ để cho tất cả các xe hai bên cầu ko được đi qua. Sau một thời điểm nhất định thì đèn sẽ chuyển sang màu xanh để cho xe khác tiếp tục qua cầu, cứ thế mà tiếp tục

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.

- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm cho các tiến trình có thể tự khóa mình (Block Itseft) và chuyển sang trạng thái waiting, sau đó xếp vào hàng chờ của đèn hiệu. Trình điếu phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.
- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựa chọn và đánh thức bằng lệnh WakeUp(P) để chuyển P từ trạng thái Waiting sang trạng thái Ready. Lúc này trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào thuật giải cụ thể.

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

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.
Alan Mathison Turing là một trong những nhà khoa học lớn bị lãng quên của thế kỷ XX, cho dù ông là cha đẻ của các máy tính, hay ít nhất cũng là một phần lý thuyết của nó. Sự đóng góp to lớn của ông quyết định cho sự chiến thắng của phe Đồng Minh trong Thế chiến thứ hai. Nhưng có thể nhà cầm quyền nước Anh khuyến khích ông tự vận, vì những lý do tối mật, đã giấu tên ông?
Alan M. Turing sinh ngày 23 tháng 6 năm 1912 tại London. Cha làm trong ngành thu thuế tại Ấn độ và mẹ đi theo cha năm 1913, để lại bé Alan từ người giám hộ này tới người giám hộ khác trong các nội trú. Alan không phải là một học trò giỏi. Các giáo sư phê bình ông là học trò lơ đễnh. Năm 15 tuổi, ông gặp Christopher Morton, và hai người bạn này đã cùng nhau trao đổi đam mê khoa học. Sự liên hệ này hơi mập mờ giữa tình bạn và tình yêu. Nhưng Christopher mất vào tháng hai năm 1930 đã làm Turing bối rối.
Tuy vậy, ông cũng thi đậu vô trường King's College tại Cambridge. Tại đây ông phát triển tài năng vì nhờ nơi này không ai chế nhạo sự đồng tính luyến ái và bề ngoài khác biệt của ông. Tại trường, mỗi người giữ cá tính của riêng mình, ai sao mặc ai. Alan tóc tai quần áo bê bối và thường không cạo râu, thích đạp xe đạp và đeo cái đồng hồ nơi thắt lưng để coi thời gian đạp xe và với một mặt nạ phòng khí độc đeo trên mặt để phòng dị ứng phấn hoa (hay fever). Ngoài việc chơi thể thao cấp cao (chạy bộ), Alan còn thích những công trình về cơ học lượng tử của John Von Neumann.
Cho dù ông lập dị, nhưng khả năng toán học rực rỡ và những việc làm của ông thật đặc sắc. Năm 1924 Turing in một bài báo chứng tỏ rằng toán luôn chứa những trạng thái mà không thể chứng minh hay bị bắt bẻ. Ngoài lý luận trên, ông dự tính một cái máy có thể tính bất cứ con số nào. Cái máy đó bao gồm một bộ phận điều khiển (control unit) và một bộ nhớ, có thể hoàn thiện nhiều thao tác cơ bản: đọc, viết hay xóa những ký hiệu trên băng (tape), và cho băng chạy tới hay chạy lui. "Máy Turing" đơn giản này dùng làm mẫu cho các máy tính số sau này.
Ông cũng thích môn sinh học, đặc biệt là mạng nối giữa các dây thần kinh. Ông tự hỏi: "Tại sao các máy quá tài tình trong việc tính toán mà lại hạn chế sự mô phỏng những hành động tự nhiên giản dị nhất của người như đi, cầm cái ly...)?"
Trước tuổi 30, ông đã tưởng tượng những căn bản cho một máy tính số (digital computer) tân kỳ và dẫn đầu về lý thuyết cơ bản cho thông minh nhân tạo (artificial intelligence).
Là người phát minh tư tưởng một cái máy vạn năng (universal machine) , tìm ra lý do quan trọng tại sao một máy tính có thể làm rất nhiều chuyện. Tiếc thay Turing không còn sống để thấy sự tiến triển khổng lồ của ngành thông tin, máy tính. Nhà toán học người Anh này sống trong hai thế giới khác nhau.

Trước công chúng, ông là một nhà toán học tài ba, đã giúp Thế giới đại chiến lần II thắng nhờ giải được các mã số của phe Đức. Còn bên trong, Turing là một người nhát gan, hay mắc cỡ, lập dị và bị đối xử tàn bạo do cách sống riêng biệt của ông đã đưa ông đến cái chết đau thương lúc 41 tuổi.
Năm 1935, ông hiệu chính khái niệm một máy vạn năng để hình thức hóa khái niệm toán giải bằng algorithme. Máy của Turing có khả năng cả một quá trình algorithme. Những máy tính hiện đại là những thực hiện cụ thể máy của Turing.
Năm 1936, Turing đến Princeton University, nơi này ông lấy bằng PhD Toán học và làm việc với nhà toán học người Mỹ gốc Hongrie là John von Neumann (1903-1957), nổi tiếng nhờ Cơ học Lượng tử. Nhờ đó Turing học thêm về xác suất và logique.

Turing trở về Anh quốc năm 1938. Liền sau đó ông vào quân đội Anh cho cuộc chiến tranh sắp đến. Đầu Thế chiến thứ hai, quân đội Đức thắng nhiều trận vinh quang trên biển. Một trong những chìa khóa của các chiến thắng đó là máy viết mật mã Enigma, một máy mã hóa điện từ, để giúp bộ tham mưu Đức truyền những thông điệp cho các tàu ngầm, những thông điệp mà phe các nước Đồng Minh không thể giải được . Do đó quân đội Anh nhóm họp trong một nơi tối mật: cơ quan "bẻ mật mã" chuyên giải mật mã của máy Enigme của Đức. Họ gồm 10.000 người thư ký, các nhà nghiên cứu và ngay cả những người chơi đánh bài, nghĩa là làm tất cả mọi việc để hiểu cơ chế của máy Egnima. Khối Đồng Minh có được những sơ đồ của máy này từ đầu chiến tranh và muốn hiểu tin mật mã của Đức, nhưng họ không thành công.
Turing đến gặp của quân đội Anh tại Bletchley Park và đã giúp họ thiết kế máy tính Bombe, một máy tính rất nhanh có thể giải mã nhanh chóng bằng cách thử hàng ngàn code khác nhau. Turing làm việc với một nhà toán học khác, Gordon Welchman. Trước khi chiến tranh chấm dứt, ông đã cho ra đời một máy điện tử, máy Kolossus, dùng để giải mã tất cả những thông điệp Đức.
Sau chiến tranh, ông trở về làm việc tại Automatic Digital Machine, một computer lớn tại University of Manchester và tin rằng giữa người và máy chỉ khác tí xíu về xử lý tín hiệu. Ông sáng chế ra máy Turing Test để đo khả năng nhận thức cảm nghĩ. Turing đề nghị rằng một cái máy có thể xem như nhận thức đuợc nếu như nó lừa được những người hỏi nó nếu như nó ở một phòng và nói chuyện với một người đó ở phòng khác.
Thiên tài của Turing được Churchill công nhận. Churchill đã giao cho Turing nhiệm vụ làm một hệ thống thông tin tối mật để ông liên lạc với tổng thống Roosevelt. Nhân cơ hội đó, Turing qua Hoa kỳ và gặp Claude Shannon, người sáng lập ra thuyết Tin học và là người phát minh ra bit, 0-1.
Cũng trong thời kỳ chiến tranh mà ông hỏi cưới duy nhất một người: cô Joan Clarke. Cô Joan dạy Turing đan áo. Turing tặng cô quyển Tess of Uberville, tác giả Thomas Hardy và thú thật rằng ông có biệt nhãn với người cùng phái. Họ trở thành bạn của nhau từ đó. Turing không muốn những người láng giềng thấy mặt và sợ dị ứng với phấn hoa nên thường đi xe đạp và mang mặt nạ chống khí độc của chiến tranh. Có khi ông từ chối không ký tên lên thẻ kiểm tra chỉ vì trong hồ sơ có ghi câu "Tất cả mọi hình thức viết tay đều bị cấm". Ông viết: "Cái mà tôi thích không phải tạo ra bộ óc tài ba, mà chỉ cần một bộ óc ngu ngốc cỡ bộ óc của ông chủ tịch hãng điện thoại American Telephone và hãng điện báo Telegraph Company"
Vì thất vọng, ông đã ăn một trái táo có tẩm cyanur và mất đúng ngày lễ Pentecôte 7 tháng 6 năm 1954 tại Wilmslow, England.
Hội Alan Turing Memorial Fund (Tưởng niệm Alan Turing), thành lập từ năm 1996 thành lập một quỹ, quyên tiền để xây dựng một tượng kỷ niệm bằng đồng cho Turing. Đến cuối năm 2000 mới quyên được £15,000.
Tượng của Alan Mathison Turing tay cầm trái táo, để tưởng niệm cái chết đau đớn của ông.
Hãng Apple có cái logo trái táo cắn nửa chừng, cũng có ý như vậy? Đây chỉ là giai đoạn khai sinh của ngành này

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

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ường hợp deadlock có thể phát sinh nếu có 1 trong bốn điều kiện sau xảy ra:
1) Loại trừ hỗ tương: ít nhất một tài nguyên phải được giữ trong chế độ không chia sẻ; nghĩa là, chỉ một quá trình tại cùng một thời điểm có thể sử dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình yêu cầu phải tạm dừng cho đến khi tài nguyên được giải phóng.
2) Giữ và chờ cấp thêm tài nguyên: quá trình phải đang giữ ít nhất một tài nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi quá trình khác.
3) Không đòi lại tài nguyên từ quá trình đang giữ chúng: Các tài nguyên không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bởi quá trình đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá trình {P0, P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1, P1 đang chờ tài nguyên đang giữ bởi P2,,Pn-1 đang chờtài nguyên đang được giữ bởi quá trình P0