Thảo luận Bài 7

- Đoạn tương tranh là một đoạn mã của tiến trình mà khi thực hiện nó truy cập và tác động đến tài nguyên dùng chung.

Code:

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

Ví dụ: Một cây cầu 1 thời điểm chỉ có thể chịu được trọng tải của 1 xe đi qua.
Khi có 1 xe đang qua cầu thì đèn đỏ sẽ bật lên các xe còn lại phải chờ ở dưới chân cầu.
Khi chiếc xe đó đi qua được bên kia cầu sẽ chuyển đèn tín hiệu sang màu xanh, xe tiếp theo sẽ được lên cầu.

Code:

while(1)
{
Đi đến cầu  //Tài nguyên dùng chung là cây cầu
Wait(mutex);
Lên cầu, qua cầu
Signal(mutex);
Đi tiếp
Quay về theo cầu khác
}


P/s: Trên đây là những gì mình chép được ở lớp, thay vì ngồi học bài mình viết lên đây luôn vừa dễ nhớ vừa chia sẻ cho bạn nào bữa đó nghỉ học ^^

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 Operation

Đị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ụ.

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

Ta dùng 2 đèn hiệu SemFull và SemEmpty
SemFull : kiểm tra số Sản phẩm trong bộ đệm.
SemEmpty: Kiểm tra số vùng trống trong bộ đệm.
Hai tác nguyên: Wait và Signal

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

Thuật ngữ: Critical section là đoạn tương tranh, Đoạn mã găng,đoạn mã tới hạn.
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. Đoạn tương tranh thường nằm giữa Entry Section (Đoạn đăng nhập) và Exit Section (Đoạn đăng xuất).
Ví dụ minh họa : Trong slide 7.9 chương 7 ta có hai đoạn mã là đoạn tương tranh trong việc sử dụng đèn hiệu
1.wait (semaphore S) {
while ( S <= 0 ); // chờ bận nếu S<=0
S --; // Giảm S đi 1
}

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

Vùng tranh chấp: là vùng chứa các biến dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ :
bạn A lên bảng viết tên của bạn ấy lên bảng thì cái bảng là "vùng tranh chấp". Bạn B phải chờ bạn A viết tên của mình xong và nhấn đèn xanh thì bạn B mới lên bảng viết tiếp.
Trong ví dụ các chuyến xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp". Chiếc xe thứ nhất đang qua cầu thì đèn đang đỏ, các xe tiếp theo đứng chờ cho đến khi xe thứ nhất qua bên kia cầu, đèn xanh bật lên thì thứ hai tiếp tục qua cầu.

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

Admin
- Phân biệt đúng sự khác nhau giữa "Đoạn Tương tranh" và "Vùng tranh chấp" !
- Các ví dụ nêu sát !

1/ Người lái xe qua cầu:
Semaphore s=1; // 0 đèn đỏ, 1 đèn xanh
Wait (s);
Lên cầu; // đoạn tương tranh
Qua cầu // đoạn tương tranh
Signal (s);

2/ Sản xuất-Tiêu thụ:
- Các đèn hiệu chung:
Semaphore semEmpty=10, semFull=0;
Semaphore critSec=1;
- Producer:
wait (semEmpty);
wait (critSec); // đoạn đăng nhập
đưa sản phẩm vào bộ đệm // đoạn tương tranh
signal (semFull); // đoạn tương tranh
signal (critSec); // đoạn đăng xuất

- Consumer:
wait (semFull);
wait (critSec); // đoạn đăng nhập
lấy sản phẩm ra khỏi bộ đệm // đoạn tương tranh
signal (semEmpty); // đoạn tương tranh
signal (critSec); // đoạn đăng xuất
Mình lấy từ bạn huynhnguyenngochien

Admin
Lấy tốt !

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ấ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.
Code:
While(1)
{
Remainder section // chưa ảnh hưởng đến tài nguyên dùng chung
Entry section // các tiến trình(1 lệnh hoặc chuỗi lệnh) được chờ tại đây.
Critical section //vùng tương tranh
Exit section // tiến trình thực hiện xong thoát và thông báo cho tt kế tiếp thực thi.
Remainder section
}
VD
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 "Share":

ĐƠN XIN VIỆC

Kính gửi: Giám đốc công ty Phương Nam
Tôi tên là: Lê Văn Ba
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 12 tháng 11 năm 2010
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 Phương Nam
Tôi tên là: Lê Văn Bàng
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 12 tháng 11 năm 2010
Người làm đơn
....(chữ ký)....
Lê Văn Bá

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

.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

Đị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ụ.

- Đ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 ABC
Tôi tên là Đỗ Ngọc Thiện
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 3 tháng 5 năm 2012
Người làm đơn
....(chữ ký)....
Đỗ Ngọc Thiện

. 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 ABC
Tôi tên là Đỗ Ngọc Thiện
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 3 tháng 5 năm 2012
Người làm đơn
....(chữ ký)....
Đỗ Ngọc Thiện

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

-Đị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ụ.

Thuật ngữ: Critical section là đoạn tương tranh, Đoạn mã găng,đoạn mã tới hạn.
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. Đoạn tương tranh thường nằm giữa Entry Section (Đoạn đăng nhập) và Exit Section (Đoạn đăng xuất).
Ví dụ minh họa : Trong slide 7.9 chương 7 ta có hai đoạn mã là đoạn tương tranh trong việc sử dụng đèn hiệu
1.wait (semaphore S) {
while ( S <= 0 ); // chờ bận nếu S<0
S --; // Giảm S đi 1
}

2.signal (semaphore S) {
S ++; //Tăng S lên 1
}
Vùng tranh chấp: là vùng chứa các biến dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ :
Trong ví dụ bạn Dương Trung Tính lên bảng viết tên của bạn ấy lên bảng thì cái bảng là "vùng tranh chấp", trong ví dụ các chuyến xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp".
- Đoạn tương tranh :
typedef int semaphore;
semaphore mutex=1;
while (1) {
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
Ví dụ : bạn A lên bảng viết tên của bạn ấy lên bảng thì cái bảng là "vùng tranh chấp". Bạn B phải chờ bạn A viết tên của mình xong và nhấn đèn xanh thì bạn B mới lên bảng viết tiếp. Trong ví dụ các chuyến xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp". Chiếc xe thứ nhất đang qua cầu thì đèn đang đỏ, các xe tiếp theo đứng chờ cho đến khi xe thứ nhất qua bên kia cầu, đèn xanh bật lên thì thứ hai tiếp tục qua cầu.

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

Bài 7:
Ví dụ tính loại trừ tương hỗ: Xe qua cầu yếu
Typedef int semaphore;
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái
//0: đèn màu đỏ
//1: đèn màu xanh
While(1)
{
Đi đến cầu;
Wait(mutex); //chờ đèn xanh
Lên cầu; //đoạn tương tranh, đèn màu đỏ
Qua cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển sang màu xanh
Đi tiếp;
Quay về theo cầu khác;
}
--- --- ---- ------------------ --------------------------------------
- Đè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).
------------------------------------- --------------------------------------
• Toán tử wait và signal
wait(S) // hoặc P(S)
{
while (S<=0);
S--;
}
- Toán tử wait: Chờ khi semaphore S âm và giảm S đi 1 nếu S>0
signal(S) // hoặc V(S)
{
S++;
}
- Toán tử signal: Tăng S lên 1
* Sử dụng semaphore (1)
- Với bài toán đoạn mã găng:
do {
wait(mutex); // mutex là semaphore khởi tạo 1
CSi;
signal(mutex);
REMAINi;
} while (1);

+Đồng bộ hóa công việc các tiến trình P1, P2, P3 để sao cho P1 trước P2,P3.
Semaphore synch = 0;
P1 P2 P3
S1 wait(synch); wait(synch);
signal(synch, 2); S2 S3

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

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.
Code:
While(1)
{
Remainder section // chưa ảnh hưởng đến tài nguyên dùng chung
Entry section // các tiến trình(1 lệnh hoặc chuỗi lệnh) được chờ tại đây.
Critical section //vùng tương tranh
Exit section // tiến trình thực hiện xong thoát và thông báo cho tt kế tiếp thực thi.
Remainder section
}

ví dụ:
Vùng tương tranh là cái bảng. Ở 1 thời điểm chỉ có 1 sinh viên lên thao tác trên đó.Sau khi sinh viên đó xong thì sinh viện khác với đc lên bảng thao tác.

Lập trình bài toán sản xuất tiêu thụ được đồng bộ bằng 2 đèn hiệu SemEmpty và SemFull
Producer:
Wait (SemEmpty);
Wait (Mutex);
Buffer [in] = sp mới; //xếp sản phẩm vào bộ đệm
in = (in + 1) % BUFFER_SIZE;
Signal (SemFull);
Signal(Mutex);
Consumer:
Wait (SemFull);
Wait (Mutex);
p = Buffer [out] //lấy sản phẩm ra khỏi bộ đệm
out = (out + 1) % BUFFER_SIZE;
Signal (SemEmpty);
Signal (Mutex);
Lưu ý:
Giá trị ban đầu của Mutex là 1.
Giá trị ban đầu của SemFull là 0.
Giá trị ban đầu của SemEmpty là BUFFER_SIZE
Giải bài tập đồng bộ hóa công việc của P1, P2, P3
a) P1 trước P2, P2 trước P3?
b) P1 trước P2 và P3?
c) P1 và P2 trước P3?

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

a) P1 trước P2, P2 trước P3
Semaphore synch1 = 0, synch2 = 0;
P1 P2 P3
S1 wait(synch1); wait(synch2);
signal(synch1); S2

signal(synch2); S3

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

b) P1 trước P2 và P3
Semaphore synch = 0;
P1 P2 P3
S1 wait(synch); wait(synch);
signal(synch, 2); S2 S3

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

c) P1 và P2 trước P3
Semaphore synch = -1;
P1 P2 P3
S1 S2 wait(synch);
signal(synch); signal(synch); S3

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

Sản Xuất Tiêu Thụ Original
#define BUFFER_SIZE 10 //số lượng khoang chứa
int buffer[BUFFER_SIZE]; //bộ nhớ đệm size 10 phần tử
int in=0; // biến in chứa giá trị chỉ vị trí xếp sản phẩm vào
int out=0; // biến out chứa giá trị chỉ vị trí lấy sản phẩm ra

int nextProduced=1; //tạo 1 sản phẩm được sản xuất kế tiếp

//nhà sản xuất:
void Producer()
{
while (1)
{
//Quá trình tạo ra 1 sản phẩm
// ... San xuat (nextProduced


while(((in+1)%BUFFER_SIZE)==out);// khoang chứa đầy thì quẩn tại đây đến khi nào có chỗ trống
buffer[in]=nextProduced++; // cho sản phẩm vào mảng tại vị trí in
in=(in+1)%BUFFER_SIZE; //sau khi chèn sản phẩm vào mảng, tăng in lên 1, nếu in đang nằm ở vị trí cuối mảng sẽ nhảy về đầu mảng

SuspendThread(GetCurrentThread());//getcureentthread: hàm của thư viện win32 API, trả về giá trị mục quản của luồng hiện hành, vd: 1700. SuspendThread(): ngừng luồng có mục quản là giá trị trong ngoặc, vd: SuspendThread(1700) ngừng luồng có mục quản 1700
}
}

//nhà tiêu thụ:
void Consumer()
{
int nextConsumed;
while (1)
{

while(in==out);//trong khoang chứa hết sản phẩm thì quẩn tại đây cho đến khi nào trong buffer có sản phẩm
nextConsumed=buffer[out]; //sản phẩm ở vị trí out được đưa vào biến netxconsumed
out=(out+1)%BUFFER_SIZE; ;//out tăng lên 1, nếu out đang nằm ở cuối mảng thì nhảy lên đầu mảng

// ... Tieu thu (nextConsumed)--> quá trình tiêu thụ sàn phẩm

Sleep(GetTickCount()%5000);// hàm gettickcount() sẽ trả về thời gian tính bằng ms trôi qua kể từ khi hệ thống khởi động tới thời điểm hiện tại, kết quả sẽ ra được con số rất lớn và chia lấy số dư cho 5000 sẽ ra được 1 con số từ 0-4999, cho luồng tiêu thụ này ngủ trong khoảng thời gian đó.
}
}

int main(){
HANDLE ProducerHandle1, ProducerHandle2// lưu mục quản của 2 nhà sx vào 2 biến ProducerHandle1, ProducerHandle2
HANDLE ConsumerHandle1, ConsumerHandle2;//lưu mục quản của 2 nhà tiêu thụ

DWORD ProducerID1, ProducerID2, ConsumerID1, ConsumerID2;//chứa ID nhà sản xuất và nhà tiêu thụ

// tạo 2 luồng sản xuất trong trạng thái ngủ
ProducerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0,4,&ProducerID1);// các đối số đầu ko quan tâm vì mới chạy được
// số 0 tiếp theo chỉ ra hàm Producer ko có tham biến, số 4 chỉ ra luồng vừa tạo sẽ không chạy mà ngủ luôn, &ProducerID1 chỉ ra luồng sẽ có mã số định danh là ProducerID1
ProducerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0,4,&ProducerID2);

// Tạo 2 luồng tiêu thụ thi hành ngay
ConsumerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0,0,&ConsumerID1);
ConsumerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0,0,&ConsumerID2);

while(1)
{
printf("\n- Nhan phim P/p de san xuat, nhan 0 de ket thuc:");
switch (getch())
{
//nhấn phím P=Producing
case 'P':
// đánh thức Producer lúc này đang ở trạng thái ngủ
ResumeThread(ProducerHandle1);
break;
//nhấn phím p=Producing
case 'p': ResumeThread(ProducerHandle2); break;

//giải phóng Producer và Consumer khỏi bộ nhớ
case '0':
{
CloseHandle(ProducerHandle1);
CloseHandle(ProducerHandle2);
CloseHandle(ConsumerHandle1);
CloseHandle(ConsumerHandle2);
return 0;

}
}
//ngừng 1 khoảng thời gian nhất định để nhà sản xuất vừa được đánh thức kịp hoàn tất 1 chu trình công việc
Sleep(1);

//show kết quả sau khi sản xuất tiêu thụ
ShowBuffer();
}
}
////////////////////////////////////////Đọc thêm tham khảo//////////////////////////////////////////
- Hàm CreateThread() sẽ tạo thành 1 luồng và nhận giá trị Mục Quản của luồng dó, sau đó đem gán giá trị vào ProducerHandle1.
- Hàm CreateThread() có 6 tham số (parameters) theo thứ tự là :
+ lpThreadAttributes : thuộc tính của luồng.
+ dwStackSize : kích cỡ của stack .
+ lpStartAddress : địa chỉ bắt đầu.
((LPTHREAD_START_ROUTINE)Producer ở đây có nghĩa là địa chỉ của luồng bắt đầu chu trình của nhà sản xuất.)
+ lpParameter : tham số.
+ dwCreationFlags : cờ hiệu tạo thành (điều khiển sự tạo thành của luồng). dwCreationFlags đươc gán giá trị 4 nghĩa là luồng được tạo thành ở trạng thái ngủ (Suspend) chờ sự kiện nào đó đánh thức luồng. (Thực hành thứ 7 thầy có yêu cầu làm tạo 1 Array các nhà sản xuất và 1 Array nhà tiêu thụ để thực hiện tự động. Mình phải sửa tham số này về 0)=> 0: đánh thức luồng vừa tạo.
+ lpThreadId : chỉ số của luồng.

#include "stdafx.h"
#include
#include
#include

#define BUFFER_SIZE 10 // kích thước của buffer là 10

int buffer[BUFFER_SIZE];
int in=0;
int out=0;

int nextProduced=1;

HANDLE semEmpty, semFull;
//semEmpty là biến dùng để chứa mục quản của đèn hiệu , quản lý số vùng trống trong buffer
// semFull là biến dùng để chứa mục quản của đèn hiệu để quản lý số sản phẩm trong bộ đệm (buffer)

CRITICAL_SECTION critSec; // là biến kiểu đoạn tương tranh dùng để chứa đối tượng đèn hiệu mutex

void Producer(){
while (1){
// San xuat (nextProduced)
WaitForSingleObject(semEmpty, INFINITE); // chờ vô hạn cho đến khi đèn hiệu semEmpty = 1 sau đó giảm xuống 1 luôn

EnterCriticalSection(&critSec); // vào vùng tương tranh (Đoạn đăng nhập)

buffer[in]=nextProduced++; // đưa sản phẩm kế tiếp vào vị trí in trong buffer
in=(in+1)%BUFFER_SIZE; // sau khi chèn sản phẩm vào mảng , tăng in lên 1 , nếu in nằm cuối mảng
// thì sẽ xoay vòng về đầu mảng .

LeaveCriticalSection(&critSec); // (Đoạn đăng xuất) sau khi ra khỏi đoạn tương tranh


ReleaseSemaphore (semFull, 1, NULL); // tăng đèn semFull lên 1 vì mới tạo thêm 1 sản phẩm


SuspendThread(GetCurrentThread()); // chuyển trạng thái của luồng hiện tại sang ngủ

}
}

void Consumer(void * c){
int nextConsumed;
while (1){
WaitForSingleObject(semFull, INFINITE); // chờ vô hạn cho đến khi nào đèn hiệu semfull = 1 rồi giảm đi 1 luôn

EnterCriticalSection(&critSec); // vào vùng tương tranh (Đoạn đăng nhập)

nextConsumed=buffer[out]; // lấy sản phẩm ra ở vị trí out trong buffer
out=(out+1)%BUFFER_SIZE; // tăng out lên 1 , nếu out đang nằm ở cuối mảng
// thì xoay vòng lên đầu mảng .

LeaveCriticalSection(&critSec); // Đoạn đăng xuất (ra khỏi đoạn tương tranh)

ReleaseSemaphore (semEmpty, 1, NULL); // tăng đèn hiệu semEmpty lên 1 vì khi tiêu thụ xong sẽ có 1 chỗ trống

if ((int)c == 3) // Luong so 3
SuspendThread(GetCurrentThread());
else
//Sleep(GetTickCount()%5000);
Sleep(10000);
//SuspendThread(GetCurrentThread());
}
}

void ShowBuffer(){
const char * LeftMargin="\n\t";
int i;
printf(LeftMargin);
for(i=0;i<(in*5);i++) putchar(' '); printf("!in");
printf(LeftMargin);
for (i=0;i printf("S%2d",buffer[BUFFER_SIZE-1]);
printf(LeftMargin);
for(i=0; i<(out*5);i++) putchar(' '); printf("^out");
printf("\n");
}

int main(){
HANDLE ProducerHandle1, ProducerHandle2;
HANDLE ConsumerHandle1, ConsumerHandle2, ConsumerHandle3;

DWORD ProducerID1, ProducerID2;
DWORD ConsumerID1, ConsumerID2, ConsumerID3;

semEmpty=CreateSemaphore(0, BUFFER_SIZE, BUFFER_SIZE, 0); // tạo đèn hiệu semEmpty có giá trị ban đầu là BUFFER_SIZE và lớn nhất là BUFFER_SIZE
// đây là đèn hiệu nội tiến trình vì có tham số cuối cùng là tên đèn hiệu là 0 .
semFull=CreateSemaphore(0, 0, BUFFER_SIZE, 0); // tạo đèn hiệu semFull có giá trị ban đầu là 0 và lớn nhất là BUFFER_SIZE
// đây là đèn hiệu nội tiến trình vì có tham số cuối cùng là tên đèn hiệu là 0 .

InitializeCriticalSection(&critSec);

ProducerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0,4,&ProducerID1);//
//số 0 tiếp theo chỉ ra hàm Producer ko có tham biến, số 4 chỉ ra luồng vừa tạo sẽ không chạy mà ngủ luôn, &ProducerID1 chỉ ra luồng sẽ có mã số định danh là ProducerID1
ProducerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Producer,0,4,&ProducerID2);

//ConsumerHandle1=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0,0,&ConsumerID1);
//ConsumerHandle2=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,0,0,&ConsumerID2);
ConsumerHandle3=CreateThread(0,0,(LPTHREAD_START_ROUTINE)Consumer,(void *)3,4,&ConsumerID3);

while(1) // lặp vô tận
{
printf("\n- Nhan P/p de san xuat, C/c de tieu thu, nhan 0 de ket thuc:");
switch (getch()){
case 'P': // nếu nhấn P thì
ResumeThread(ProducerHandle1); // đánh thức luồng nhà sản xuất ProducerHandle1
break;
case 'p': // nếu nhấn p thì
ResumeThread(ProducerHandle2); // đánh thức luồng nhà sản xuất ProducerHandle2
break;
case 'C':
case 'c'://nếu nhấn c thì
ResumeThread(ConsumerHandle3); // đánh thức luồng nhà tiêu thụ ConsumerHandle3
break;
case '0':
printf("\n");
CloseHandle(semEmpty);
CloseHandle(semFull);
DeleteCriticalSection(&critSec);
return 0;
}
EnterCriticalSection(&critSec);
ShowBuffer();
LeaveCriticalSection(&critSec);
}
}

Giải thưởng Turing (A. M. Turing Award) 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