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

Thay đèn hiệu critSec bằng đèn hiệu thuộc lớp HANDLE,khi đó phải tạo critSec bằng hàm CreateSemaphone,thay thế lời gọi EnterCriticalSection và LeaveCriticalSection bằng lệnh khác.

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

semaphore synch1 = 0;
semaphore synch2 = 0;

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

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

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

Bài 3: Đồng bộ P1, P2, P3 sao cho P1 trước P2 và P3
Trả lời: Ta dùng đèn hiệu sau:

semaphore synch1 = 0;
semaphore synch2 = 0;

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

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

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

Bài 4: Đồng bọ P1, P2, P3 sao cho P1, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:

semaphore synch1 = 0;
semaphore synch2 = 0;

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

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

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

P\S: đây là cách giải của mình ai có cách giải khác thì post lên cho mọi người tham khảo .
Lưu ý: các bài giải trên không bít là đúng hay sai đây chỉ là ý kiến riêng của mình nên mong mọi người chỉ bảo thêm.[code]

Admin
- Cả 4 câu giải tốt với cách làm "Mộc mạc" !
- Với Câu 1: Cần chỉ rõ là giá trị Ban đầu của Mutex được thiết lập bằng 2 (màu xanh da trời) !

cam on ban,bai lam rat thiet thuc

- Chỉ có một chiếc ôtô trên mặt cầu :

Code:

While(1)
{
    Đi đến cầu;
    wait(s);
        Lên cầu; //đoạn tương tranh
        Qua cầu; //đoạn tương tranh
    signal(s);
    Đi tiếp;
    Vòng lại theo đường khác;
}

- Sản xuất-Tiêu thụ:
Khai báo đèn hiệu

Code:

Semaphore semEmpty=10, semFull=0;
Semaphore critSec=1;

+ Producer:

Code:

wait (semEmpty);
wait (critSec); // đoạn đăng nhập
    Đưa sản phẩm vào buffer // đoạn tương tranh
    signal (semFull);    // đoạn tương tranh   
signal (critSec); // đoạn đăng xuất

+ Consumer:

Code:

wait (semFull);
wait (critSec); // đoạn đăng nhập
    Lấy sản phẩm ra khỏi buffer // đoạn tương tranh
    signal (semEmpty);    // đoạn tương tranh   
signal (critSec); // đoạn đăng xuất

- Đồng bộ hóa công việc các tiến trình là việc làm quan trọng trong việc điều phối hoạt động các tiến trình.
- Đảm bảo cho các tiến trình hoạt động theo một thể thống nhất, phối hợp nhịp nhàng với nhau một cách có thứ tự, giữ cho tài nguyên ít bị lạm dụng .
- Ngăn không cho các tiến trình hoạt động chồng chéo lên nhau gây mất kiểm soát.
- Ví dụ: Trong một dây chuyền sản xuất sữa hộp (Hệ thống được đồng bộ hóa), đầu tiên lon sữa(chưa chứa sữa) được đưa vào đúng vị trí, sau đó sữa sẽ được hệ thống cho sữa vào lon theo đúng định lượng, tiếp đến là khâu đóng nấp và cuối cùng là dán tem (Mỗi khâu sản xuất tương đương với một tiến trình).
Nếu như trong quá trình sản xuất trên có một khâu sản xuất hoạt động không đứng thứ tự (Tiến trình mất kiểm soát): sau khi đã kiểm tra đúng định lượng sữa cho một lon nhưng hệ thống lại đổ sữa trong khi hệ thống khác chưa đưa được lon đến (Tiến trình mất đồng bộ hóa), sữa bị đổ ra bên ngoài (Thất thoát tài nguyên).

Đèn hiệu không tên : chỉ được dùng để liên lạc trong nội bộ of tiến trình truyền thống (giữa các luồng của nó) .Ưu điểm là bảo mật tốt hơn .
Đèn hiệu có tên : chỉ được dùng để liên lạc giữa các tiến trình nặng (tiến trình truyền thống)

Nhưng quy trình gửi xe bằng thẻ tự động,các xe lần lượt xếp hàng chờ đến được có thẻ. Từng chiếc sẽ được vào đúng vị trí quy định để máy nhận bản số ,sau khi chiếc trước đó chạy đi thì xe kế tiếp mới được vào đúng vị trí quy định...

NguyenMinhTam(I22B) đã viết:Đèn hiệu không tên : chỉ được dùng để liên lạc trong nội bộ of tiến trình truyền thống (giữa các luồng của nó) .Ưu điểm là bảo mật tốt hơn .
Đèn hiệu có tên : chỉ được dùng để liên lạc giữa các tiến trình nặng (tiến trình truyền thống)

Mình thêm 1 ý của đèn hiệu không tên là ngoài bảo mật tốt cái quan trọng của nó là tốc độ xử lý nhanh

TranVuSang (I22B) đã viết:

Hai đoạn Code SX - TT dùng đèn hiệu thật đẹp, đẹp vì tính đối xứng. Code không những đẹp mà còn đúng nữa.

NguyenMinhTam(I22B) đã viết:Đèn hiệu không tên : chỉ được dùng để liên lạc trong nội bộ of tiến trình truyền thống (giữa các luồng của nó) .Ưu điểm là bảo mật tốt hơn .
Đèn hiệu có tên : chỉ được dùng để liên lạc giữa các tiến trình nặng (tiến trình truyền thống)

Mình xin bổ xung thêm ý của bạn là
Đèn hiệu có tên còn được gọi là đèn hiệu liên tiến trình, độ bảo mật kém.
Đèn hiệu không tên còn được gọi là đèn hiệu nội tiến trình.

VD về tính đồng bộ hóa giữa các tiến trình:
Trong một phòng mạch, người nhà bệnh nhân phải lấy số thứ tự trước rồi sau đó đợi các nhân viên gọi đến số thẻ của mình thì mới được phép vào khám bệnh, để tránh tình trạng mất trật tự do người tới sau lại chen vào khám trước. Lúc này, phòng mạch như là nguồn tài nguyên chung, được quản lý qua các số thẻ khám bệnh. Khi người nào đọc tới số thẻ của mình thì sẽ được sử dụng tài nguyên dùng chung đó. Và người kế tiếp phải đợi đến khi người trước mình hoàn thành xong việc khám bệnh mới được tiếp tục vào phòng khám.

p/s: nếu có sai sót mọi người góp ý thêm
Thanks!

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

Ví dụ:
-Chương trình dowload phim được cài đặt download 3 tập cùng 1 lúc theo thứ tự thì muốn download tập 4 phải chờ download xong 3 tập trước mới được down.

Mô hình hợp tác giữa các quá trình dựa trên giả định là
các quá trình thực hiện bất đồng bộ. Do vậy chúng có thể chia sẻ dữ liệu
cho nhau. Ta xét bài toán hợp tác của các quá trình với
vùng dữ liệu chung có kích thước giới hạn: print spooling.
Cụ thể, khi một quá trình cần in một tập tin, nó nhập tên tập tin vào một
thư mục đặc biệt spooler. Một quá trình khác, dịch vụ in, sẽ kiểm tra xem
có tập tin nào trong thư mục spooler không, nếu có dịch vụ sẽ thực hiện
in. Sau khi in xong, dịch vụ in sẽ xóa tên tập tin khỏi thư mục spooler. Giả sử thư mục spooler có nhiều mục vào được đánh số 0,1,2,…. Mỗi
mục vào giữ một tên tập tin. Đồng thời có 2 biến dùng chung:
- Biến out: trỏ đến tập tin kế tiếp được in
- Biến in: trỏ đến mục vào trống kế tiếp của thư mục spooler.
Hai biến này có thể được giữ trong một tập tin 2 từ mà có thể truy cập
được từ tất cả các quá trình.
Giả sử tại một thời điểm, các mục vào 0 đến 3 rỗng, mục vào 4 đến 6 là
có dữ liệu. Đồng thời, hai quá trình A, B sắp hàng một tập tin cần in.
Tiến trình thực hiện của 2 quá trình như sau:
- Quá trình A đọc biến in và gán giá trị đọc được, 7, vào biến cục bộ
của nó, next_free_slot. Giả sử đến thời điểm này, quá trình A hết thời
hạn thực hiện chu kỳ CPU. Nên hệ điều hành gọi thủ tục chuyển ngữ
cảnh để chuyển CPU cho quá trình B.
- Quá trình B đọc biến in, và cũng có được giá trị 7. Sau đó, B gán tên
tập tin cần in của nó vào mục vào 7, và tăng in lên 1 giá trị. Kế tiếp, B
chuyển sang tác vụ khác. - Đến lượt quá trình A quay lại tiếp tục thực hiện. A sẽ tiếp tục thực
hiện ngay sau tác vụ bị ngắt. A đọc biến next_free_slot, lấy giá trị 7.
Do vậy, A ghi tên tập tin cần in vào mục vào 7. Tên tập tin của B tại
mục vào này bị xóa. Kế tiếp, A tính next_free_slot +1 và ghi giá trị
tính được vào biến in.
- Lúc này, dịch vụ in thực hiện in theo giá trị có trong biến in. Kết quả,
quá trình B sẽ không nhận được kết quả ở máy in.
Qua ví dụ, ta thấy khi hai (hay nhiều) quá trình cùng đọc/ghi vùng dữ liệu
chia sẻ thì kết quả thường phụ thuộc vào thứ tự thực hiện của các quá
trình, điều này được gọi là điều kiện cạnh tranh (race condition). Khi một
chương trình có chứa điều kiện cạnh tranh, việc kiểm tra có thể cho kết
quả đúng, nhưng khi thực hiện có thể có những kết quả ngoài dự đoán.
Đây chính là vấn đề cần giải quyết của bài toán đồng bộ.

Ta đã biết, để đảm bảo các chương trình có dùng chung tài nguyên sẽ cho
kết quả đúng là làm thế nào để các điều kiện cạnh tranh không xảy ra.
Ý tưởng chính là tìm các cách để ngăn chặn nhiều quá trình cùng đọc, ghi
vùng dữ liệu chia sẻ mở cùng một thời điểm. Nói cách khác, ta cần có
cách thức độc quyền truy cập (mutual exclusion) theo kiểu: nếu có một
quá trình đang dùng một biến chung (hay một tập tin chia sẻ) thì các quá
trình khác không thể thao tác trên biến (hay tập tin) đấy. Ví dụ trên minh
họa ràng buộc này, ta thấy điều kiện cạnh tranh xảy ra bởi vì quá trình B
khởi động sử dụng biến chung trước khi quá trình A kết thúc thao tác trên
biến chung. Như vậy, việc chọn tác vụ cơ sở thích hợp để đạt được độc quyền truy
cập là yếu tố cài đặt chính của thủ tục đồng bộ quá trình. Ta sẽ xét các
phương pháp lựa chọn trong các giải pháp đồng bộ.
Trong hệ điều hành, việc ngăn ngưà điện kiện cạnh tranh có thể được
hình thức hóa trong cách thức trừu tượng. Một quá trình có thể được chia
làm các phần thực hiện theo mã lệnh:
- Phần mã lệnh mà quá trình thực hiện độc lập không hợp tác với quá
trình khác.
- Đoạn lệnh của quá trình có chức năng thực hiện các tác vụ trên vùng
dữ liệu chung. Đoạn chương trình này có thể được gọi là vùng tương
tranh (critical region).
Do vậy, nếu ta đảm bảo ràng buộc: không có 2 (hay nhiều) quá trình hợp
tác thực hiện trên vùng tương tranh ở cùng 1 thời điểm, thì các điều kiện
cạnh tranh sẽ không xảy ra.
Tuy nhiên, ràng buộc trên chưa đủ để ngăn chặn các điều kiện cạnh tranh.
Ta cần 4 điều kiện để đảm bảo các điều kiện cạnh tranh không xảy ra
trong quá trình hợp tác giữa các quá trình:
- Không có hai quá trình thực hiện cùng một lúc trên vùng tương tranh.
Cụ thể, nếu có 1 quá trình đang thực hiện trên vùng tương tranh thì
các quá trình khác phải chờ.
- Không có quá trình nào phải chờ vô hạn để được thực hiện trên vùng
tương tranh.
- Một quá trình không thực hiện trên vùng tương tranh không thể ngăn
quá trình khác vào vùng tương tranh.
- Liên tục: khi không có quá trình nào đang thực hiện trên vùng tương
tranh thì chỉ những quá trình đang không thực hiện phần độc lập mới
có thể tham gia vào việc chọn quá trình.
Ví dụ sau minh họa cách thức độc quyền truy cập: hệ thống có hai quá
trình đang hợp tác.
- Quá trình A bắt đầu thực hiện trên vùng tương tranh ở thời điểm T1
- Ở thời điểm T2, quá trình B cần vào vùng tương tranh nhưng phải chờ
vì có một quá trình đang thực hiện ở đấy.
- Quá trình B chờ cho đến thời điểm T3 khi quá trình A kết thúc thực
hiện vùng tương tranh.
- Ở thời điểm T4, quá trình B kết thúc thực hiện trên vùng 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()
{
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.

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.

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

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á

- Mục đích của đồng bộ hoá 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êndùng chung và Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).
- Tính nhất quán của tài nguyên dùng chung là đảm bảo được tính đúng đắn, tính hơp lý,tính toàn vẹn của tài nguyên dùng chung
-Đồng bộ đảm bảo cho các tiến trình làm việc đồng bộ, ăn khớp với nhau vì thế nên sẽ nhanh hơn và dễ dàng hơn.đồng bộ thường là có chờ.
- vd: Thầy gọi 5 bạn lên nộp bài, thì bạn được thầy gọi đầu tiên sẽ lên nộp bài trước và 4 bạn còn lại sẽ đứng chờ để nộp bài tiếp theo.
- vd về tính toàn vẹn: 1 bạn lên bảng sữa bài và bạn thứ 2 ở dưới muốn chụp lại bài sữa của bạn đó thì bạn thứ 2 phải đợi cho đến khi nào bạn thứ 1 sữa xong thì mới chụp được chứ không thể chụp trong khi bạn thứ 1 vẫn còn đang đứng sữa bài đượ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 Operations).

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

Semaphore hay tạm gọi là truyền tin thị giác (optical telegraph) là một công cụ dùng để truyền tin qua phương tiện tín hiệu nhìn thấy được với tháp cao cùng với các phiến quay quanh trục (pivoting blades) hay các cánh quạt (paddles), các cửa chớp (shutters) trong một hình thể ma trận (matrix), hoặc là các cờ cầm tay...Thông tin được mã hóa theo vị trí của các thành phần cơ học; nó được đọc khi các phiến hoặc cờ nằm ở một vị trí đã ấn định.

Trong thời hiện đại, nó thường được ám chỉ đến một hệ thống truyền tín hiệu bằng hai lá cờ cầm tay. Hệ thống semaphore dùng hai cán cờ ngắn có cờ hình vuông là một trong các phần cơ bản của kỹ thuật Hướng đạo.

Những hình thức tín hiệu thị giác khác còn có cờ hiệu hàng hải, đèn hiệu, và gương hiệu.

Semaphore ra đời trước điện tín. Chúng nhanh hơn người đưa tin đi bằng ngựa trên một quãng đường xa, nhưng phí tổn nhiều và ít được bảo mật hơn điện tín mà thay thế nó sau đó. Khoảng cách mà một tín hiệu thị giác có thể truyền đi bị hạn chế bởi địa hình và thời tiết, vì vậy đa số các phương tiện truyền tín hiệu thị giác trong thực tế thường sử dụng nhiều trạm tiếp vận để nối liên lạc những khoảng cách xa hơn.

Hệ thống semaphore mới hơn dùng hai cán cờ ngắn có cờ hình vuông. Một người cầm cờ giữ chúng ở các vị trí khác nhau để truyền đi các mẫu tự và các số. Người cầm cờ giữ mỗi cờ trong mỗi tay, và đưa mỗi cánh tay của mình ở một trong 7 vị trí, các vị trí kế tiếp nhau cách nhau một góc 45 độ. Trừ khi ở vị trí nghỉ, hai cờ không thể chồng lên nhau. Màu cờ thì khác nhau dựa vào tín hiệu được truyền đi ở trên biển hay trên bờ. Màu đỏ và vàng cho cờ dùng ở biển trong khi màu trắng và xanh dương được dùng trên bờ.

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 Deadlock (Hiện tượng kẹt tiến trình).

Ví dụ 1:
Trong gia đình chỉ có 1 cái máy tính duy nhất (tài nguyên dùng chung), một thành viên đang sử dụng máy tính để làm việc, nếu có một người khác vào sau muốn sừ dụng máy tính thì phải đợi thành viên kia sử dụng xong mới được dùng.

Ví dụ 2:
Trong một công ty có duy nhất 1 chiếc máy Photocopy, nhân viên A đang photo tài liệu thì nhân viên B tới sau thì đợi A photo xong mới tới lượt cùa mình.

- Đoạn tương tranh là 1 đoạn mã trong chương trình của tiến trình người dùng.
Đoạn mã có tính chất khi thực hiện các lệnh trong đoạn tương tranh thì các đoạn đó có thể tác động đến tài nguyên dùng chung, biến dùng chung (count ++, count --) có thể sửa chữa những kết quả trong tài nguyên.

- "Loại trừ lẫn nhau" hay còn gọi là đoạn tương hỗ. Chỉ có 1 tiến trìnhđược rơi vào đoạn tương tranh mà thôi, có 1 tiến trình khác muốn tương tranh thì phải chờ HĐH cho phép.

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

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


Xét hai processes: P1 và P2.
Yêu cầu: lệnh S1 trong P1 cần được thực thi trước lệnh S2 trong P2
Định nghĩa semaphore “synch” dùng đồng bộ
Khởi động semaphore:synch.value= 0
Để đồng bộ hoạt động theo yêu cầu, P1 phải định nghĩa như sau:
S1;
signal(synch);
Và P2 định nghĩa như sau:
wait(synch);
S2;

Tổ chức truy xuất độc quyền với Semaphores: khái niệm semaphore cho phép bảo đảm nhiều tiến trình cùng truy xuất đến miền găng mà không có sự mâu thuẫn truy xuất. n tiến trình cùng sử dụng một semaphore s, e(s) được khởi gán là 1. Để thực hiện đồng bộ hóa, tất cả các tiến trình cần phải áp dụng cùng cấu trúc chương trình sau đây:

while (TRUE) {

Down(s)

critical-section ();

Up(s)

Noncritical-section ();

}


Tổ chức đồng bộ hóa với Semaphores: với semaphore có thể đồng bộ hóa hoạt động của hai tiến trình trong tình huống một tiến trình phải đợi một tiến trình khác hoàn tất thao tác nào đó mới có thể bắt đầu hay tiếp tục xử lý. Hai tiến trình chia sẻ một semaphore s, khởi gán e(s) là 0. Cả hai tiến trình có cấu trúc như sau:

P1:

while (TRUE) {

job1();
Up(s); //đánh thức P2

}

P2:

while (TRUE) {

Down(s); // chờ P1
job2();

}