Thảo luận Bài 7

-Đị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,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ỗ về phương diện thời gian:khi có 1 tiến trình ở trong đoạn tương tranh của nó thì không có tiến trình nào khác trong nhóm cũng trong tại đoạn như vậy(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,Critical Section,Exit Section và các remainder Section.
Code:
While(1)
{
Remainder section
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
Remainder section
}

Đồng bộ hóa công việc các tiến trình nhằm mục đích đảm bảo tính nhất quán của tài nguyên dùng chung và tránh được hiện tượng deadlock(hiện tượng kệt tiến trình).
Ví du: Hôm kiểm tra giữa kỳ đến giờ nộp bài bài các bạn tập trung chen lấn lẫn nhau để nộp tạo nên hiện tượng lộn xộn dẫn đến thầy nỗi giận không biết thu bài của ai. nếu chúng ta thống nhất với nhau từng nhóm có thầy kêu 5 người lên bảng rồi nộp lần lượt từng người, hết nhóm này tới nhóm khác thì lúc đó sẽ tránh được hiện tượng kẹt tiền trình.

Deadlock (Kẹt khoá) – Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bới một tiến trình khác trong nhóm.
Giả sử S và Q là 2 đèn hiệu với trị ban đầu là 1. Hai tiến trình P0 và P1 bị kẹt khi cùng vận hành 2 chuỗi lệnh sau:
P0 P1
wait (S); wait (Q);
wait (Q); wait (S);
M M
signal (S); signal (Q);
signal (Q); signal (S);
Starvation (Ách vô hạn định) – Chờ vô hạn tại đèn hiệu do các tiến trình được rút khỏi hàng chờ theo quy tắc LIFO (Last - In, First - Out) hoặc theo Độ ưu tiên cao hơn.

Admin đã viết:Thảo luận những vấn đề liên quan đến Bài 7.

Đèn hiệu nhị phân để đảm bảo tính loại trừ lẫn nhau.
Đèn hiệu nhị phân chỉ có 2 trạng thái (xanh và đỏ - 1 và 0).
VD: Giả sử có 1 cây cầu ở đầu cầu có 1 cái đèn, trên đoạn đường đến cầu có các oto (vd oto1, oto2...) và cầu chỉ có tải trọng 1 chiếc oto đi qua tại 1 thời điểm khi duy chuyển qua cầu, đèn báo có 2 trạng thái 0 và 1 (xanh và đỏ), đèn xanh xe oto được phép đi, đỏ oto còn lại phải chờ đến lượt, giống như trạng thái wait(s);, signal(s).
- Đè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).

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

Đề: đồng bộ hóa công việc của P1, P2, P3. sao cho:
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.

Mong thầy và các bạn góp ý.

Trình bày mục đích đồng bộ hóa công việc tiến trình

Đồng bộ hóa tiến trình là điều khiển công việc của luồng và tiến trình sao cho đáp ứng yêu cầu đặt ra của logic nghiệp vụ.
Mục đích của đồng bộ hóa tiến trình.
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
ví dụ: bài toán sản xuất tiêu thụ.
một bạn trong lớp lên bảng (tài nguyên dùng chung của lớp) ghi thông tin cá nhân nhưng chưa ghi xong thì bạn khác dưới lớp chụp lại thông tin trên sẽ không đúng. muốn lấy thông tin chính xác thì bạn dưới lớp cần lấy thông tin của bạn trên bảng ghi phải chờ bạn ấy ghi hết thông tin rồi mới chụp ảnh.
- Tránh Deadlock ( hiện tượng kẹt tiến trình).
ví dụ: hiện tượng kẹt xe khi có cảnh sát giao thông điều tiết phân luồng thì sẽ không còn kẹt xe nữa.



Khái niệm về đồng bộ hóa tiến trình


Đồng bộ hóa tiến trình là đồng bộ hóa các luồng ở bên trong của tiến trình, là biết cách điều khiển các luồng cho chúng ăn nhập với nhau có trước có sau để đảm bảo tính nhất quán và tính toàn vẹn của tài nguyên dùng chung,và đảm bảo theo yêu cầu của người dùng.
Tài nguyên dùng chung trong bài toán sản xuất tiêu thụ là Buffer, các biến In,Out
Ví dụ BUFFER_SIZE 10
Tài nguyên dùng chung là vùng nhớ để chúng trao đổi thông tin với nhau.
Tránh được hiện tượng Deadlock.
Trở lại vấn đề bài toán sản xuất – tiêu thụ với giải pháp mới dùng biến đếm Count.
Cấu trúc bộ nhớ đệm chung.
#define BUFFER_SIZE 10
typedef struct {
. . . // Mô tả các thành phần của 1 khoang chứa
} item;
item buffer [BUFFER_SIZE]; // Bộ nhớ đệm.
int in = 0; // Con trỏ tới vị trí trống kế kiếp.
int out = 0; // Con trỏ tới vị trí lấy tiếp theo.
int count= 0;// Đếm số sản phẩm có trong Buffer.




ví dụ về bài toán Đồng bộhóa
Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản:

if (taikhoan - tienrut >=0)

taikhoan = taikhoan - tienrut;

else

error(� khong the rut tien ! �);

Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau :

Sau khi đã kiểm tra điều kiện (taikhoan - tienrut >=0) và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.

P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 (do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.

Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0)-vì đã kiểm tra trong lượt xử lý trước- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống.

ĐƠN XIN NHẬP HỌC
Kính gửi: Trường Đại Học Mở TPHCM
Tôi tên là: Lương Thế Vinh
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 12 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Phùng Ngọc Huy

. 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ương Thế Vinh thì phía dưới cũng phải là Lương Thế Vinh.
. 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ương Thế Vinh phía trên thành Lương Thế Vĩnh, trong khi P2 (nhà sản xuất khác) sửa Lương Thế Vinh thành Lương Thế Vịnh, 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 NHẬP HỌC
Kính gửi: Trường Đại Học Mở TPHCM
Tôi tên là: Lương Thế Vĩnh
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 12 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Phùng Ngọc Huy

Vì 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 cho nên nội dung đơn phải thể hiện được tính toàn vẹn và nhất quán như sau:

ĐƠN XIN NHẬP HỌC
Kính gửi: Trường Đại Học Mở TPHCM
Tôi tên là: Lương Thế Vinh
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 12 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Lương Thế Vinh

Khái niệm đồng bộ: Đồng bộ là đảm bảo cho các tiến trình làm việc theo 1 trình tự và phối hợp nhịp nhàng.
Ví dụ: Trong siêu thị lúc tính tiền thì mọi người sẽ xếp hàng theo một dãy,và trình tự từng người lên tính tiền,người đầu tiên rồi đến người thứ hai và cứ thế đến người cuối cùng,trong khi một người lên tính tiền những người còn lại phải đứng chờ.

Mong thầy và các bạn góp ý thêm!

Đồng bộ là có chờ, chờ là cùng lúc làm việc với nhau cùng lúc, cùng đi chơi với nhau. Đồng bộ hóa công việc các tiến trình là tổ chức điều khiển công việc các luồng sao cho chúng làm việc với nhau cùng lúc, ăn khớp, có trước có sau để đảm bảo tính nhất quán, tính toàn vẹn của tài nguyên dùng chung, theo yêu cầu của người sử dụng.
o Tài nguyên dùng chung là I/O, buffer, bộ nhớ và các tiến trình truyền thống nặng cùng chia sẻ chay chung với nhau. Vùng nhớ là các vùng cùng trao đổi với nhau khi làm việc.
Ví dụ: khi 1 bạn nào đó tên Nguyễn Văn Anh lên bảng ghi tên mình (bộ nhớ dùng chung). Nhưng khi đang viết tên đến chữ Anh chưa xong, thì 1 bạn khác trong lớp chụp ảnh (nhà tiêu thụ), như vậy nội dung bạn đã chụp không đảm bảo tính nhất quán, tính toàn vẹn.
o Bên cạnh đó một khía cạnh khác của việc đồng bộ hóa các tiến trình là tránh hiện tượng Deadlock (hiện tượng kẹt tiến trình)
Ví dụ: Hiện tượng kẹt xe, khi ở mức cao điểm thì không có xe nào đi được, nhưng khi chú công an điều phối thì tình trang kẹt xe giảm đi đáng kể.

Đoạn tương tranh (Critical Section Problem) : là 1 đoạn mã trong chương trình của tiến trình tương tranh, được hệ điều hành cấp CPU cùng làm việc, cùng dùng tài nguyên chung.
Tính loại trừ lẫn nhau (loại trừ tương hỗ) – Mutual Exclusion: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập hoặc thay đổi tài nguyên dùng chung trong đoạn tương tranh mà thôi. Và các tiến trình khác có nhu cầu truy cập vào không được.
while (1)
{
Remainder section
Entry section
Critical xection
Exit section
Remainder section
}
Ví dụ: bạn trung lên bảng thì bạn Anh không được lên và ngược lại.

Ứng dụng của đèn 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).
*Ứng dụng:
-1.Giải quyết vấn đề VTT: Bằng đèn hiệu nhị phân

-Sử dụng đèn hiệu mutex với trạng thái ban đầu =1

+ Mã của tiến trình Pi bây giờ có cấu trúc:

Code:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) // (Đèn hiệu nhị phân)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
=> Loại trừ tính tương tranh, đảm bảo trong 1 thời điểm chỉ có 1 tiến trình ở đoạn tương tranh.

Semaphore: Được mô tả bằng biến nguyên với 2 tác nguyên là wait(chờ) và Signal(báo hiệu).

Đặc điểm : mỗi tiến trình chỉ phải kiểm tra quyền vào đoạn găng một lần sau đó hoặc nó được vào đoạn găng hoặc phải xếp hàng chờ.
Khi chờ tiến trình không phải làm gì hết. Một tiến trình nào đó khác, sau khi ra khỏi đoạn găng sẽ "dánh thức" tiến trình chờ để tiến trình này vào đoạn găng.

Wait(mutex): chuyển trạng thái tiến trình gọi sang blocked , và đặt tiến trình này vào hàng đợi trên biến điều kiện mutex.
Signal(mutex): nếu có một tiến trình đang bị khóa trong hàng đợi của mutex, tái kích hoạt tiến trình đó, và tiến trình gọi sẽ rời khỏi monitor.


tyepdef int semaphores; // định nghĩa kiểu đèn báo
wite (semaphore S)
{
  while(S <=0) //chờ bận nếu S<=0
  S--;
}

signal(semaphore S)
{
 S++; //Tăng S lên một
}

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

Nghĩa là : Mỗi thời điểm chỉ có một tiến trình được phép truy cập và hoặc thay đổi tài nguyên dùng chung.

(Tôi làm thì anh không làm hoặc anh làm thì tôi thôi).

Vi dụ1 :
Một bạn lên nộp bài bạn kia phải ngồi chờ ở bàn, không được lên mỗi thời điểm chỉ có một không được hơn một. (bắt buộc một bạn phải lên nộp bài, chứ không phải ai cũng chờ mà không ai chịu nộp --> đó không phải là loại trừ tương hỗ.)

Ví dụ 2:
Một bạn lên bảng sửa bài thì không ai được sửa nữa, không ai được chụp hình mà phải đợi sửa xong mới được chụp.

Londres 1912 - Manchester 1954






Ông là nhà Toán học - cha đẻ máy computer Colossus, phát minh software



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


Máy ColossusTrướ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.


John von NeumannNă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.


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

Bắt đầu từ năm 1966, Giải thưởng Turing đã được Association for Computing Machinery (Hiệp hội Máy tính) trao cho cá nhân có đóng góp kĩ thuật cho cộng đồng máy tính. Giải này được coi như tương đương với giải Nobel trong cộng đồng này.

Ngày 23 tháng 6 năm 2001 một bức tượng của Turing được đặt tại công viên Sackville Park của thành phố Manchester, giữa tòa nhà của Đại học Manchester trên phố Whitworth và khu gay village của phố Canal. Để kỉ niệm 50 năm ngày mất của ông, một tấm bảng kỉ niệm đã được khánh thánh tại nơi ông ở trước đây, Hollymeade, Wilslow, vào ngày 6 tháng 7 năm 2004.
Tấm bảng đánh dấu nơi ở cũ của Turing


Viện khoa học Alan Turing (Alan Turing Institute) được sáng lập bởi UMIST và Đại học Manchester vào mùa hè năm 2004.

Lễ kỉ niệm cuộc đời và sự nghiệp của Turing đã được tổ chức tại Đại học Manchester vào ngày 5 tháng 6 năm 2004 do British Logic Colloquium (Hội Logic Anh) và British Society for the History of Mathematics (Nhóm nghiên cứu Lịch sử Toán học Anh) tổ chức.

Vào ngày 28 tháng 10 năm 2004 a bức tượng đồng của Alan Turing, tạc bởi John W. Mills, được khánh thành tại Đại học Surrey. Bức tượng kỷ niệm 50 năm ngày Turing mất. Nó diễn tả Turing đang cầm sách đi trong viện đại học này.

Holtsoft đã sản xuất ngôn ngữ lập trình mang tên Turing. Ngôn ngữ này dành cho người mới bắt đầu lập trình và không tương tác trực tiếp với phần cứng.

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

Những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa
Mục đích của đồng bộ hóa công việc các tiến trình là đảm bảo Tính nhất quán của tài nguyên chung và Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )
+ Đả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) .
VD1: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab

Thực thi đèn hiệu trong windows

typedef int semaphore;
semaphore s = n;
wait (s);
signal (s);

HANDLE s;
s=CreateSemaphore (0, n, max, t);
WaitForSingleObject (s, timeout);
ReleaseSemaphore (s, 1, NULL);

Ai hiểu code nầy không giải thích gúp mình với
Cảm ơn mọi người nhiều lắm.

Khái niệm Đoạn tương tranh và Loại trừ lẫn nhau
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).

Đồng bộ hóa tiến trình là điều khiển công việc của luồng và tiến trình sao cho logic và đáp ứng yêu cầu đặt ra.
Mục đích của đồng bộ hóa tiến trình.
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
ví dụ: bài toán sản xuất tiêu thụ.
một bạn trong lớp lên bảng (tài nguyên dùng chung của lớp) ghi thông tin cá nhân nhưng chưa ghi xong thì bạn khác dưới lớp chụp lại thông tin trên sẽ không đúng. muốn lấy thông tin chính xác thì bạn dưới lớp cần lấy thông tin của bạn trên bảng ghi phải chờ bạn ấy ghi hết thông tin rồi mới chụp ảnh.
- Tránh Deadlock ( hiện tượng kẹt tiến trình).
ví dụ: hiện tượng kẹt xe khi có cảnh sát giao thông điều tiết phân luồng thì sẽ không còn kẹt xe .

Giải quyết vấn đề Đoạn Tương Tranh.
Mã của tiến trình Pi có cấu trúc:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) { // (Đèn hiệu Nhị phân)
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
Giả sử P1 có mã S1 , P2 có mã S2 , cần tổ chức sao cho S2 chỉ thi hành sau S1 .
Ta dùng đèn hiệu như sau:
semaphore synch = 0;
Cấu trúc P1 : Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2

Đị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 là 1 đoạn mã trong chương trình của HĐH. Đ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.
VD: Bạn Tính đang ghi tên trên bảng thì bạn An không được ghi hoặc bạn Thanh không được chụp ảnh...
- Đoạn tương tranh là đoạn mã khi thực hiện ảnh hưởng đến vùng tranh chấp, các code trong mã khi sử dụng ảnh hưởng đến miền. Vùng tranh chấp là đoạn tương tranh.

Semaphore là một biến được bảo vệ (hay là một kiểu dữ liệu trừu tượng), tạo thành một phương pháp để hạn chế truy nhập tới tài nguyên dùng chung trong môi trường đa lập trình (multiprogramming). Đây là một phát minh của Edsger Dijkstra và được sử dụng lần đâu tiên trong hệ điều hành THE.
-Giá trị của semaphore được khởi tạo bằng số các tài nguyên tương đương được chia sẻ cái mà cài đặt điều khiển. Trong trường hợp đặc biệt, khi mà chỉ có một tài nguyên tương đương được chia sẻ, semaphore được gọi là semaphore nhị phân. Trong trường hợp khái quát, semaphore thường được gọi là biến đếm semaphore.
Chú ý rằng việc tăng biến s không thể bị gián đoạn, và toán tử P cũng không được gián đoạn sau khi nhận ra biến s có giá trị khác 0. Điều này có thể được thực hiện bằng cách sử dụng một lệnh đặc biệt như test-and-set (kiểm tra và thiết lập) nếu tập lệnh của kiến trúc máy hiện hành hỗ trợ nó, hoặc bằng cách bỏ qua các ngắt để ngăn tiến trình khác kích hoạt (đối với các hệ thống chỉ có 1 bộ vi xử lý).
-Các cái tên kinh điển P và V xuất phát từ tiếng Hà Lan. Chữ V trong verhoog nghĩa là "tăng". Một vài lời giải thích đưa ra cho chữ P (bao gồm passeer có nghĩa là "vượt qua", probeer có nghĩa là thử, và pakken với nghĩa "nắm lấy"), nhưng thực ra Dijkstra viết rằng ông dùng P để đại diện cho từ tự tạo portmanteau prolaag,[1] là viết tắt của probeer te verlagen, hay "kiểm-tra-để-giảm".[2][ 3].This
-Giá trị của một semaphore là số đơn vị tài nguyên đang ở trạng thái rỗi. (Nếu chỉ có một tài nguyên, người ta sẽ sử dụng một "semaphore nhị phân" với các giá trị 0 và 1.) Toán tử P đợi (busy waiting) hoặc đang ngủ cho đến khi một tài nguyên hết bận, khi đó, nó lập tức chiếm quyền sử dụng tài nguyên đó. V là toán tử đảo ngược; nó thả một tài nguyên sau khi tiến trình đã sử dụng xong tài nguyên đó. Init chỉ được dùng để khởi tạo semaphore trước tất cả các yêu cầu sử dụng nào. Các toán tử P và V phải có tính chất nguyên tố, nghĩa là không có tiến trình nào có thể chặn giữa quá trình thực hiện một trong các toán tử này để chạy một toán tử khác trên cùng một semaphore đó.
- Trong các sách giáo trình tiếng Anh, và trong ngôn ngữ lập trình ALGOL 68, các toán tử P và V thường được gọi lần lượt là down và up. Trong các tài liệu công nghệ phần mềm, các toán tử này được gọi là wait (đợi) và signal (đánh tín hiệu), hoặc take (lấy) và release (thả), hoặc pend (giữ) và post (công bố).
Để tránh tình trạng busy-waiting, một semaphore có thể có một cấu trúc hàng đợi gồm các tiến trình. Nếu một tiến trình thực hiện một thao tác P đối với một semaphore có giá trị 0, tiến trình này được đưa vào hàng đợi của semaphore. Khi một tiến trình khác dùng toán tử V để tăng giá trị của semaphore, và có tiến trình nằm trong hàng đợi, thì một tiến trình trong đó được lấy ra khỏi hàng đợi và tiếp tục chạy.

Ứng dụng semaphore hiện nay
Semaphores được sử dụng phổ biến trong các ngôn ngữ lập trình - những ngôn ngữ mà về bản chất không hỗ trợ những dạng khác của sự đồng bộ hóa. Chúng cũng được sử dụng trong các kĩ thuật đồng bộ ban đầu như trong các hệ điều hành. Xu hướng trong sự phát triển của ngôn ngữ lập trình, dường như là hướng vào các dạng cấu trúc đồng bộ hóa, giống như đồng bộ hóa các kênh. Cộng thêm sự không đầy đủ trong cách phân chia với deadlock, semaphore không bảo vệ người lập trình khỏi các lỗi đơn giản trong việc lấy một semaphore - cái mà luôn luôn được thay đổi bởi các tiến trình đồng thời, và cũng quên giải phóng semaphore sau khi lấy ra.