Thảo luận Bài 7

Nhà khoa học Edsger Dijkstra
Tiểu sử:
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.
Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization - một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.

Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 "A Case against the GO TO Statement" (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.

Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).

Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas.

Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó, để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như "Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn" (Computer Science is no more about computers than astronomy is about telescopes.)

Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

Mục đích của đồng bộ hóa công việc các tiến trình nhầm đảm bảo các tiến trình làm việc nhất quán, chờ lẫn nhau, sử dụng chung tài nguyên và tránh được hiện tượng kẹt tiến trình.

VD:
- có 2 bạn, bạn A đang làm bài tập, B rủ A đi chơi, để đồng bộ thì B phải chờ cho A làm bài xong rồi cùng đi chơi
- Cả lớp là tiến trình nặng, mỗi người là tiến trình nhẹ, thầy gọi 1 bạn lên bảng giải bài tập, muốn gọi bạn tiếp theo lên thì phải đợi bạn trước làm xong
VD trường hợp vi phạm nhất quán.
-Khi A đang soạn đơn xin việc và B lại sửa tên, bạn X chụp lại bảng => ghi tên và ký tên khác nhau => vi phạm nhất quán

Đồng bộ công việc các tiến trình P1, P2, P3 sao cho P1 và P2 trước P3.
Giả sử P1 có mã S1, P2 có mã S2, P3 có mã S3, cần tổ chức sao cho S3 chỉ thi hành sau S1 và S2.

Cách 1:
Cách 2:

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

Xét hai process: 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;

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

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 .

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

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


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


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


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


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

Alan Mathison Turing (23/6/1912 – 7/6/1954) là một nhà toán học, logic học và mật mã học người Anh thường được xem là cha đẻ của ngành khoa học máy tính. Thử thách Turing (Turing test) là một trong những cống hiến của ông trong ngành trí tuệ nhân tạo: thử thách này đặt ra câu hỏi rằng máy móc có khi nào đạt được ý thức và có thể suy nghĩ được hay không. Ông đã công thức hóa khái niệm thuật toán và tính toán với máy Turing, đồng thời đưa ra phiên bản của "Turing", mà ngày nay được đông đảo công chúng chấp nhận, về luận đề Church-Turing, một luận đề nói rằng bất cứ mô hình tính toán thiết thực nào đều có khả năng thấp hơn hoặc bằng khả năng của một máy Turing.
[You must be registered and logged in to see this image.][You must be registered and logged in to see this link.] alt="" />

Trong Đệ nhị thế chiến, Turing đã từng làm việc tại Bletchley Park, trung tâm giải mật mã của Anh, và một thời là người chỉ huy của Hut 8, một bộ phận của Anh có trách nhiệm trong việc giải mã của hải quân Đức. Ông đã sáng chế ra nhiều kỹ sảo hòng phá mật mã của Đức, trong đó có phương pháp nối các máy giải mã lại với nhau thành một bộ Bombe, một máy điện-cơ để tìm ra công thức gài đặt cho máy Enigma.

Sau chiến tranh, ông cộng tác tại Phòng thí nghiệm Vật lý Quốc gia (National Physical Laboratory), và đã tạo ra một trong những đồ án đầu tiên cho một máy tính có khả năng lưu trữ chương trình (stored-program computer), nhưng nó không bao giờ được kiến tạo thành máy. Năm 1947 ông chuyển đến Đại học Victoria tại Manchester để làm việc, đa số trên phần mềm cho máy Manchester Mark I, lúc đó là một trong những máy tính hiện đại đầu tiên.

Năm 1952, Turing bị kết án với tội đã có những hành vi khiếm nhã nặng nề, sau khi ông tự thú đã có quan hệ đồng tính luyến ái với một người đàn ông ở Manchester. Ông bị tù treo và phải dùng liệu pháp hoóc môn.

Turing qua đời năm 1954; cuộc điều tra cái chết của ông cho thấy ông đã tự tử bằng cách ăn một quả táo có tẩm thuốc độc xyanua.


Thời thơ ấu và thiếu niên

Mẹ của Alan mang thai ông vào năm 1911, tại Chatrapur, Ấn Độ. Cha ông, Julius Mathison Turing, lúc đó là một công chức trong ngành Dân chính Ấn Độ (Indian Civil Service), lúc đó vẫn dưới sự cai quản của chính phủ Anh. Julius và vợ mình, bà Ethel (nguyên họ là Stoney) muốn con mình lớn lên tại Anh, nên họ đã trở về Paddington, Luân Đôn, nơi Alan Turing được sinh ra vào ngày 23 tháng 6 năm 1912. Vì nhiệm vụ với ngành dân chính của cha ông vẫn còn, trong lúc Alan còn nhỏ, cha mẹ của ông thường phải di chuyển giữa Guildford (Anh) và Ấn Độ, để hai đứa con trai của họ cho các người bạn tại Anh giữ hộ, vì tình trạng y tế ở Ấn Độ còn thấp kém. Ngay từ lúc còn nhỏ, ông đã thể hiện các dấu hiệu thiên tài. Ông tự tập đọc trong vòng ba tuần, và có biểu lộ ham thích toán học, cùng với giải đáp các câu đố.

Lúc Alan 6 tuổi, cha mẹ cho ông học tại trường St. Michael\'s. Bà hiệu trưởng của trường đã nhận thấy thiên tài của Alan từ lúc ban đầu, cũng như các giáo viên của ông sau này. Năm 1926, khi ông 14 tuổi, ông đến học tại trường nội trú Sherborne ở Dorset. Ngày khai giảng của khóa đầu xảy ra cùng ngày với một cuộc tổng đình công tại Anh, nhưng vì ông quyết trí muốn đến lớp, ông đã chạy xe đạp trên 60 dặm (100 km) từ Southampton đến trường, không có người dẫn, chỉ dừng lại và trọ qua đêm tại một quán trọ trên đường. Sự kiện này đã được báo chí địa phương tường trình.
Tuy có năng khiếu toán và khoa học, Turing không được các thầy cô coi trọng tại Sherborne, một trường công nổi tiếng và đắt đỏ (thật sự đây là một trường tư ở Anh nổi tiếng với tính từ thiện) vì trường này đánh giá các môn kinh điển cao hơn. Hiệu trưởng của ông đã viết thư cho cha mẹ ông nói "Tôi hy vọng rằng anh ta không rơi vào tình trạng lơ lửng, giữa trường nọ với trường kia. Nếu anh ta muốn ở lại Trường Công, thì anh ta nhất định phải đặt mục tiêu để trở thành một người có giáo dục. Còn nếu anh ta chỉ muốn trở thành một Nhà khoa học chuyên ngành thì tôi e rằng anh ta đang phung phí thời gian của mình tại Trường Công" .

Mặc dầu vậy, Turing vẫn biểu hiện năng khiếu trong các môn ông ưa thích. Ông đã giải được nhiều bài toán bậc cao trong năm 1927 trước khi học đến giải tích cơ bản. Khi ông 16 tuổi (1928), ông đã hiểu được các tác phẩm của Albert Einstein, không những nắm được nội dung, ông còn suy luận được về những thắc mắc của Einstein đối với các định luật của Newton về chuyển động trong một bài viết mà Einstein không nói thẳng ra.

Trong lúc học tại Sherborne, Turing đã ngầm yêu Christopher Morcom, một người bạn, nhưng mối tình không được đáp lại. Morcom qua đời một vài tuần trước khi ra trường vì bệnh lao đã mắc phải sau khi uống sữa bò có vi khuẩn lao lúc còn nhỏ. Turing rất đau lòng vì sự việc này.


Đại học và các nghiên cứu trong toán học

Vì Turing không chịu học các môn ngoài toán và khoa học, ông không nhận được học bổng để học tại Học viện Trinity của Đại học Cambridge, mà phải học tại Học viện King\'s của Đại học Cambridge từ năm 1931 đến 1934 và tốt nghiệp đại học với bằng danh dự. Năm 1935 ông được chọn làm nghiên cứu sinh tại trường King\'s, do sức thuyết phục của mình trong luận văn về hàm số độ sai của Gauss.

Trong bài viết nổi tiếng của ông, tựa đề "Các số khả tính, với áp dụng trong Vấn đề về lựa chọn" (On Computable Numbers, with an Application to the Entscheidungsproblem) - thuật toán lôgic - (đệ trình ngày 28 tháng 5 năm 1936), Turing tái dựng lại kết quả của Kurt Gödel hồi năm 1931 về những hạn chế trong chứng minh và tính toán, thay đổi thuật ngữ tường trình số học chính quy của Gödel, bằng cái mà ngày này người ta gọi là máy Turing, một dụng cụ chính quy và đơn giản. Ông đã chứng minh rằng một cái máy như vậy sẽ có khả năng tính toán bất cứ một vấn đề toán học nào, nếu vấn đề ấy có thể được biểu thị bằng một biểu trình thuật toán, ngay cả khi một cái máy Turing cụ thể như vậy không có mấy công dụng thực tiễn vì sự chậm chạp của nó so với những cơ chế khác.
Máy Turing, cho đến nay, vẫn là một vấn đề nghiên cứu trung tâm trong lý thuyết về máy tính. Ông còn tiếp tục chứng mình rằng vấn đề về lựa chọn (Entscheidungsproblem) là một vấn đề không có giải đáp, bằng cách đầu tiên chứng minh rằng nan đề ngưng hoạt động trong máy của Turing là một nan đề bất khả định; khó mà có thể quyết định được rằng một cái máy Turing nào đó sẽ ngưng hoạt động tại một điểm nào đó. Tuy chứng minh của ông được đăng công khai sau chứng minh tương tự của Alonzo Church đối với giải tích lambda (lambda calculus), chứng minh của Turing được coi là dễ hiểu và trực giác hơn. Chứng minh của ông còn nổi tiếng về đề bạt một cái "máy Turing vạn năng" (Universal (Turing) Machine), một ý tưởng rằng một cái máy như vậy có thể làm bất cứ việc gì mà các máy khác phải làm. Bài viết còn giới thiệu quan niệm về số khả định (definable number).

Hầu hết thời gian giữa năm 1937 và 1938, ông cư trú tại Đại học Princeton, nghiên cứu dưới sự chỉ đạo của Alonzo Church. Năm 1938, ông đạt được bằng Tiến sĩ tại trường này. Luận văn của ông giới thiệu quan niệm tính toán tương đối (relative computing). Trong quan niệm này, nhiều máy Turing được ghép lại, trở thành một cái máy tiên tri (oracle machine), cho phép nghiên cứu những phương trình không thể giải được nếu chỉ sử dụng một cái máy Turing mà thôi.

Sau khi quay trở lại Cambridge vào năm 1939, ông thính dự giảng đường của Ludwig Wittgenstein về nền tảng của toán học (foundations of mathematics). Hai người tranh cãi và bất đồng ý kiến một cách kịch liệt. Trong khi Turing bảo vệ lập trường của chủ nghĩa hình thức (formalism), thì Wittgenstein lại tranh cãi rằng toán học được đánh giá quá mức, và bản thân nó không thể tìm ra bất cứ một chân lý cuối cùng nào (absolute truth) (Wittgenstein 1932/1976).


Giải mật mã
Hầu hết thời gian giữa năm 1937 và 1938, ông cư trú tại Đại học Princeton, nghiên cứu dưới sự chỉ đạo của Alonzo Church. Năm 1938, ông đạt được bằng Tiến sĩ tại trường này. Luận văn của ông giới thiệu quan niệm tính toán tương đối (relative computing). Trong quan niệm này, nhiều máy Turing được ghép lại, trở thành một cái máy tiên tri (oracle machine), cho phép nghiên cứu những phương trình không thể giải được nếu chỉ sử dụng một cái máy Turing mà thôi.
Sau khi quay trở lại Cambridge vào năm 1939, ông thính dự giảng đường của Ludwig Wittgenstein về nền tảng của toán học (foundations of mathematics). Hai người tranh cãi và bất đồng ý kiến một cách kịch liệt. Trong khi Turing bảo vệ lập trường của chủ nghĩa hình thức (formalism), thì Wittgenstein lại tranh cãi rằng toán học được đánh giá quá mức, và bản thân nó không thể tìm ra bất cứ một chân lý cuối cùng nào (absolute truth) (Wittgenstein 1932/1976).

Máy bombe của Turing và Welchman

Chỉ trong vài tuần sau khi đến Bletchley Park[2], Turing đã sáng chế ra một cái máy cơ-điện tử (electromechanical machine) giúp vào việc giải mã máy Enigma, đặt tên là máy bombe, lấy tên theo cái máy "bomba" được sáng chế tại Ba Lan. Máy bombe, với một nâng cấp được đề bạt bởi nhà toán học Gordon Welchman, trở thành dụng cụ chủ yếu dùng để đọc nguồn tin truyền qua lại từ máy Enigma.

Máy bombe dò tìm công thức cài đặt của khối quay trong máy Enigma, và nó cần phải có một bộ mã (crib), tức là một dòng chữ chưa mã hóa và một dòng mật mã tương ứng. Với mỗi dự kiến cài đặt của khối quay, máy bombe hoàn thiện một chuỗi các tiến trình suy luận lôgic, dựa vào bộ mã, dùng các cấu kết mạch điện tử đã được lắp ráp. Máy bombe lùng tìm và phát hiện mâu thuẫn khi nó xảy ra, loại bỏ công thức cài đặt gây nên sự mâu thuẫn ấy, rồi tiếp tục lùng tìm một công thức khác, hợp lý hơn. Đa số các công thức cài đặt khả quan đều gây nên sự mâu thuẫn, và bị loại bỏ, chỉ để lại một số ít các công thức khả dĩ để được nghiên cứu chi tiết hơn. Máy bombe của Turing lần đầu tiên được lắp ráp vào ngày 18 tháng 3 năm 1940. Có đến trên 200 cái máy bombe như vậy vẫn đang hoạt động khi chiến tranh kết thúc

Hut 8 và máy Enigma của hải quân Đức


Hai gian nhà trong sân trước chuồng ngựa tại Bletchley Park. Turing đã từng làm việc tại đây trong những năm 1939–1940 cho đến khi ông chuyển sang Hut 8
Vào tháng 12 năm 1940, Turing khám phá ra hệ thống chỉ thị của máy Enigma của hải quân Đức, một hệ thống chỉ thị phức tạp hơn tất cả các hệ thống chỉ thị khác đang được dùng bởi các chi nhánh trong quân đội. Turing cũng sáng chế ra công thức xác suất Bayes (Bayesian), một kỹ thuật trong thống kê được đặt tên là "Banburismus", để giúp vào việc giải mã Enigma của hải quân Đức. Banburismus cho phép loại bỏ một số công thức cài đặt của khối quay của máy Enigma, giảm lượng thời gian kiểm nghiệm các công thức cài đặt cần thiết trên các máy bombe.
Vào mùa xuân năm 1941, Turing đính hôn với một nhân viên cùng làm việc tại Hut 8, tên là Joan Clarke, nhưng chỉ đến mùa hè, cả hai đã thoả thuận hủy bỏ cuộc hôn nhân.

Tháng 7 năm 1942, Turing sáng chế ra một kỹ sảo, đặt tên là Turingismus hoặc Turingery, dùng vào việc chống lại máy mật mã Lorenz. Rất nhiều người lầm tưởng rằng Turing là một nhân vật quan trọng trong việc thiết kế máy tính Colossus, song điều này không phải là một sự thật [3].

Tháng 11 năm 1942, Turing du lịch sang Mỹ và bắt liên lạc với những nhân viên phân tích mật mã của hải quân Mỹ tại Washington, D.C., thông báo cho họ biết về máy Enigma của hải quân Đức, cùng với sự việc lắp ráp máy bombe. Ông đồng thời trợ lý việc kiến tạo các công cụ truyền ngôn bảo mật (secure speech) tại Bell Labs. Tháng 3 năm 1948, ông quay trở lại Bletchley Park. Trong khi ông vắng mặt, Hugh Alexander thay thế ông làm trưởng phòng Hut 8, tuy trên thực tế Hugh Alexander đã nắm quyền trưởng phòng trong một thời gian khá lâu. Turing rất ít quan tâm đến việc quản lý công việc hằng ngày của bộ phận. Turing trở thành cố vấn chung về phân tích mật mã tại Bletchley Park.

Trong những ngày sau rốt của chiến tranh, ông tự trau dồi về công nghệ điện tử, trong khi chịu trách nhiệm (được sự hỗ trợ của kỹ sư Donald Bayley) thiết kế một cái máy di động - mật hiệu là Delilah - cho phép thông tin truyền âm bảo mật (secure voice). Với xu hướng ứng dụng trong các công dụng khác, máy Delilah thiếu khả năng truyền sóng radio trường tuyến (long-distance radio transmission), và không được sử dụng trong chiến tranh vì sự hoàn thành của nó quá muộn. Tuy Turing đã thao diễn chức năng của máy cho các quan chức cấp trên, bằng cách mật mã hóa và giải mã một bản ghi âm lời nói của Winston Churchill, máy Delilah vẫn không được chọn và sử dụng.

Trong năm 1945, Turing đã được tặng huy chương OBE (Order of the British Empire) vì thành tích phục vụ trong cuộc chiến tranh.


Những máy tính đầu tiên và kiểm nghiệm của Turing

Từ năm 1945 đến năm 1947, Turing đã làm việc tại Phòng thí nghiệm Vật lý Quốc gia (National Physical Laboratory). Tại đây, ông thiết kế máy tính ACE (Automatic Computing Engine - Máy tính tự động). Ngày 19 tháng 2 năm 1946, ông đệ trình một bản thiết kế hoàn chỉnh đầu tiên của Anh về máy tính với khả năng lưu trữ lập trình (xem kiến trúc Von Neumann). Tuy ông đã thành công trong việc thiết kế máy ACE, song do những trì hoãn trong việc khởi công đề án, ông trở nên thất vọng và chán nản. Cuối năm 1947, ông quay trở lại Cambridge, bắt đầu một năm nghỉ ngơi của mình (sabbatical year). Trong khi ông đang nghỉ ngơi tại Cambridge, công việc xây dựng máy ACE đã bị huỷ bỏ hoàn toàn, trước khi nó được khởi công xây dựng. Năm 1949, ông trở thành phó giám đốc phòng thí nghiệm máy tính (computing laboratory) của Đại học Manchester, và viết phần mềm cho một trong những máy tính đầu tiên — máy Manchester Mark I. Trong thời gian này, ông tiếp tục làm thềm những công việc trừu tượng, và trong bài viết "Vi tính máy móc và trí thông minh" (Computing machinery and intelligence) - tờ Mind, tháng 10 năm 1950 - ông nói đến vấn đề về "trí tuệ nhân tạo" (artificial intelligence) và đề đạt một phương thức kiểm nghiệm, mà hiện giờ được gọi là kiểm nghiệm Turing (Turing test), một cố gắng định nghĩa tiêu chuẩn cho một cái máy được gọi là "có tri giác" (sentient).
Năm 1948, Turing, hiện đang làm việc với một người bạn học cũ, D.G. Champernowne, bắt đầu viết một chương trình đánh cờ vua cho một máy tính chưa từng tồn tại. Năm 1952, tuy thiếu một máy tính đủ sức để thi hành phần mềm, Turing đã chơi một ván cờ. Trong ván cờ này, ông bắt trước cái máy tính, đợi nửa tiếng đồng hồ trước khi đi một quân cờ. Ván cờ đã được ghi chép lại; phần mềm thua người bạn đồng hành của Turing, Alick Glennie, song lại thắng người vợ của ông Champernowne.

Tạo mẫu hình và sinh toán học

Turing nghiên cứu vấn đề sinh toán học (mathematical biology) từ năm 1952 cho đến khi qua đời năm 1954, đặc biệt về hình thái học (morphogenesis). Năm 1952, ông đã cho xuất bản một bài viết về vấn đến này, dưới cái tên "Cơ sở hoá học của hình thái học" (The Chemical Basis of Morphogenesis). Điểm trọng tâm thu hút sự chú ý của ông là việc tìm hiểu sự sắp xếp lá theo chu trình của dãy số Fibonacci, sự tồn tại của dãy số Fibonacci trong cấu trúc của thực vật. Ông dùng phương trình phản ứng phân tán, cái mà hiện nay là trung tâm của nghành Tạo mẫu hình (pattern formation). Những bài viết sau này của ông không được xuất bản, cho mãi đến năm 1992, khi loạt các cuốn "Những nghiên cứu và sáng chế của A.M. Turing" (Collected Works of A.M. Turing) được xuất bản.

- Ví dụ 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ỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở 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 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 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).

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

Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra] ( nghe); 11 tháng 5, 1930 tại Rotterdam – 6 tháng 8, 2002 tại Nuenen), là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình. Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Tự ổn định. Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.
Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization - một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.
Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 "A Case against the GO TO Statement" (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.
Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).
Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas.
Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó , để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như "Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn" (Computer Science is no more about computers than astronomy is about telescopes.)
Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

Vấn đề về đoạn tương tranh và Tính loại trừ lẫn nhau

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
}

- Đè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
+ Ý nghĩa hàm wait áp dụng cho đèn hiệu S: chờ cho đến khi giá trị của đèn hiệu S lớn hơn 1 sau đó qua được lệnh chờ này và giá trị của đèn giảm đi 1.
+ Ý nghĩa hàm signal: tăng giá trị của đèn lên 1.

Ý nghĩa:
- Giải quyết đoạn tương tranh.
- Bảo đảm các tiến trình làm việc đúng thứ tự

Đồng bộ các tiến trình P1, P2, P3 sau cho P1,P2 đi trước P3.

semaphore synch = -1;

P1	P2	P3
S1	S2	wait(synch);
signal(synch);	signal(synch);

đồng bộ hóa công việc của P1, P2, P3. sao cho: P1 trước P2, P2 trước P3?

ai bek giải nào

VuMinhTan (113A) đã viết:đồng bộ hóa công việc của P1, P2, P3. sao cho: P1 trước P2, P2 trước P3?

ai bek giải nào

Theo như đề bài bạn đưa ra thì mình có cách giải như thế này.
Giả sử P1 có mã S1, P2 có mã S2, P3 có mã S3, cần tổ chức sao cho S3 chỉ thi hành sau S2 và S2 chỉ thi hành sau S1.

- Với tác nguyên Wait có vòng lặp vô tận kiểm tra biến đếm S có nhỏ hơn 0 hay không, điều đó làm cho các tiến trình có thể tự khoá mình (Block Itself) và chuyển sang trạng thái waiting, sau đó xếp vào hàng chờ của đèn hiệu. Trình điều phối CPU có thể chọn tiến trình khác trong hàng chờ Ready để thực hiện.

- Khi một tiến trình nào đó thực hiện lệnh Signal(S), một tiến trình P nào đó đang chờ tại S được lựa chọn và đánh thức bằng lệnh WakeUP(P) để chuyển P từ trang thái Waiting sang trạng thái Ready. Lúc này trình điều phối có thể cho P thực thi ngay hay không còn tuỳ thuộc vào giải thuật cụ thể.

Người ta thường nhắc một câu nói rất hay của Franz Neumann: "Phát hiện ra một chân lý mới là niềm hạnh phúc tuyệt vời, còn sự thừa nhận dường như không góp được gì thêm". Câu nói đó dường như để nói về Perelman, người đa từ chối mọi giải thưởng dành cho mình với thành tựu chứng minh giả thuyết Poincaré, còn nói chung thì câu đó cũng chỉ đúng được một nửa! Theo Niels Bohr, câu nói ngược lại càng đúng, nghĩa là các giải thưởng - sự thừa nhận của cộng đồng- là điều hết sức quan trọng đối với mỗi nhà khoa học. Vì lẽ đó mà đến nay có rất nhiều giải thưởng dành để tôn vinh các nhà khoa học đạt những thành tựu kiệt xuất. Nổi tiếng và uy tín nhất có lẽ là giải Nobel, tiếc rằng giải thưởng đó không dành cho toán học. Vậy nên, các nhà toán học phải đặt ra một giải thưởng tương tự cho ngành khoa học của mình: Giải thưởng Fields. Hầu như mọi người đều thống nhất rằng, Giải thưởng Fields trong toán học là “tương đương” với giải Nobel của các ngành khoa học khác, xét về uy tín và tầm cao của các thành tựu được giải.

Bài viết này nhằm giới thiệu sơ qua lịch sử giải thưởng Fields, và nói đôi điều về sự phát triển của toán học khoảng 60-70 năm gần đây, nếu nhìn qua các giải thưởng Fields.

Tuy nhiên, toán học hiện đại cũng gần như nghệ thuật hiện đại và thơ ca, mỗi người hiểu và cảm nhận theo cách của mình. Bởi thế, khi nói về cùng một thành tựu, có người thì ca ngợi hết lời, người khác lại cho là nó hoàn toàn vô ích!

Một ít lịch sử
Không ai biết chính xác tại sao Nobel, khi đặt giải thưởng cho các ngành khoa học, lại loại toán học ra ngoài. Có nhiều lời đồn đại rằng, nguyên nhân là mối quan hệ không bình thường của Mittag-Leffler với vợ của Nobel. Mittag-Leffler là nhà toán học nổi tiếng nhất của Thuỵ Điển thời đó, và nếu có giải thưởng giành cho toán học thì hầu chắc chắn, ông sẽ là người đầu tiên nhận được. Tuy nhiên, lời đồn đó không đúng, vì Nobel chưa có vợ bao giờ! Người ta cũng đồn rằng quan hệ giữa Nobel và Mittag-Leffler không được tốt. Mặc dù không có tài liệu nào ghi nhận, nhưng có vẻ như lời đồn đó có cơ sở. Ít nhất thì Fields đó từng nói đến điều đó. Năm 1890 Nobel đã lật ngược đề nghị của Mittag-Leffler về việc dành một ghế giáo sư cho Sophia Kovalevskaia tại Trường đại học Stockholm. Nhưng cũng thật trớ trêu, những năm đầu tiên sau khi Nobel qua đời (1896), chính Mittag-Leffler là người đóng vai trò quyết định trong việc xét trao giải thưởng Nobel, và làm cho giải thưởng đó trở thành giải thưởng quốc tế uy tín nhất.

Có thể nói, lịch sử của Giải thưởng Fields bắt đầu từ buổi họp của Uỷ ban Đại hội quốc tế tại trường Đại học Toronto tháng 11 năm 1923, bàn về việc tổ chức Đại hội vào năm 1924 tại Toronto, lúc đó Fields là Chủ tịch của Uỷ ban. Fields đề nghị lập ra một giải thưởng nhằm ghi nhận những công trình vừa kiệt xuất, vừa có nhiều hứa hẹn phát triển trong tương lai. Có lẽ đó là điều khác biệt đầu tiên giữa giải thưởng Fields và giải Nobel: trong khi giải Nobel gần như ghi nhận cống hiến của cả một đời người, thì Fields nhằm mục đích hướng đến tương lai: vừa tôn vinh thành tựu đạt được, vừa khuyến khích những phát triển tiếp theo. Vì thế, Giải thưởng chỉ được trao cho những nhà toán học không quá 40 tuổi vào năm họp Đại hội. Đối với toán học, việc hạn chế ở tuổi 40 khá hợp lý: trong thực tế, phần lớn các nhà toán học đạt được thành tựu xuất sắc nhất của mình trong lứa tuổi đó. Một điều khác biệt nữa là giải Nobel được trao hàng năm, trong khi giải Fields chỉ được trao bốn năm một lần, vào các kì Đại hội toán học thế giới.

Giải thưởng Fields được trao lần đầu năm 1936 ở Oslo, và lần thứ hai năm 1950 ở Cambridge. Vì người được xét trao giải thưởng phải có tuổi đời không quá 40, mà khoảng cách giữa lần trao giải thưởng thứ nhất và thứ hai lại quá lớn, nên nhiều người sinh ra trong khoảng từ năm 1900 đến năm 1910 không có cơ hội được xét thưởng. Trong số đó có những nhà toán học kiệt xuất như A. Kolmogorov, H. Cartan, A. Weil, J. Leray, L. Pontriagin, S. S. Chern, S. Whitney.

Lúc đầu, Hội toán học quốc tế quyết định chỉ trao không quá hai giải thưởng trong mỗi kỳ đại hội. Tuy nhiên, tại Đại hội năm 1966 đã đạt được thoả thuận là, do sự phát triển mạnh mẽ của toán học, mỗi kỳ Đại hội có thể xét trao đến 4 giải thưởng.

Theo đề nghị ban đầu của Fields, Giải thưởng phải có tính chất thuần tuý quốc tế, nên không được gắn với tên của bất kỳ quốc gia hay cá nhân nào. Tuy vậy, trái với ý định ban đầu của ông, Giải thưởng được mang tên “Huy chương Fields” ngay lần đầu tiên được trao, năm 1936 tại Đại hội Toán học thế giới ở Oslo (khi đó Fields không còn nữa). Có một điều thú vị cũng cần được nhắc đến, đó là Đại hội quyết định rằng ông Chủ tịch cần phải gặp Thủ tướng Canada để thoả thuận, nếu có thể, về một quỹ thường xuyên, có lãi suất, giành cho giải thưởng. Tuy nhiên, sự thoả thuận đó chưa bao giờ đạt được, và giá trị bằng tiền của Giải thưởng Fields hiện nay là vào khoảng 15.000 đôla Canada, tức khoảng 10.000 đôla Mỹ. Vì thế, khi ta nói rằng “giải thưởng Fields tương đương giải thưởng Nobel trong các ngành khoa học khác” là nói về giá trị khoa học và vinh dự của giải thưởng, chứ hoàn toàn không phải là sự “tương đương” về tiền bạc! Có lẽ điều đó cũng có phần hợp lý, vì nói chung toán học chẳng “tương đương” được với lĩnh vực nào, nếu xét theo thu nhập của những người đứng hàng đầu trong mỗi lĩnh vực!
Fields đã cố gắng để đẩy nhanh việc trao giải thưởng, nhưng ông đổ bệnh tháng 5 năm 1932, và qua đời ba tháng sau đó. Trước khi mất, ông đề nghị góp 47.000 đôla của mình vào quỹ giải thưởng. Đề nghị được chấp nhận, và một uỷ ban gồm G. D. Birkhoff, Caratheodory, E. Cartan, Severi và Takagi được thành lập để xét trao giải lần đầu tiên tại Đại hội Oslo 1936. Họ đã chọn Lars Ahlfors của Phần Lan và Jesse Douglas của Hoa Kì.
Từ sau năm 1936, tình hình thế giới trở nên căng thẳng, và tiếp sau đó là Đại chiến thế giới lần thứ hai. Các Đại hội toán học không tổ chức được. Đại hội đầu tiên sau chiến tranh nhóm họp năm 1950 ở Cambridge, Massachusetts, Hoa Kì. Tại đại hội này, Laurent Schwartz và Atle Selberg được trao giải thưởng Fields.
Chính Fields đề nghị huy chương phải bằng vàng có giá trị ít nhất là 200 đôla (tính theo thời điểm 1933, có giá trị hơn ngày nay nhiều!), có kích thước hợp lý, khoảng 7,5 cm đường kính. Vì tính quốc tế của nó, các dòng chữ trên huy chương phải viết bằng tiếng Hy Lạp hoặc Latin.
Huy chương Fields được đúc bốn năm một lần tại Sở đúc tiền Hoàng gia Canada, và được thiết kế bởi nhà điêu khắc R.Tait McKenzie.

Mặt trước của tấm huy chương có hình khuôn mặt Archimedes nhìn từ bên phải. Trước mặt ông là dòng chữ tiếng Hy Lạp có nghĩa là “khuôn mặt của Archimedes”. Dòng chữ “RTM, MCNXXXIII” là viết tắt tên tác giả huy chương, nhà điêu khắc Robert Tait McKenzie, và năm 1933 (chữ số La Mã, nhưng viết sai! Lẽ ra phải là MCMXXXIII).
Dòng chữ TRANSIRE SUUM PECTUS MUNDOQUE POTIRI, tiếng latin, có nghĩa là “hãy hướng đến sự hiểu biết và làm cho bạn trở thành chủ nhân của vũ trụ”. Đó là câu trong tác phẩm Astronomica của nhà thơ La Mã Manilius từ thế kỷ thứ 1.

Mặt sau của huy chương có cành ôliu và dòng chữ “CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBUERE”, trong tiếng latin có nghĩa là “Các nhà toán học từ khắp thế giới họp tại đây tặng huy chương này vì công trình xuất sắc” . Còn ở mặt sau còn có hình một mặt cầu Archimedes nội tiếp trong một hình trụ (nhắc đến bài toán cầu phương nổi tiếng của Archimedes).

Tên của người được tặng Giải thưởng được khắc bên vành của huy chương. Kể từ khi đặt ra giải thưởng, đã có những nhà toán học sau đây được khắc tên mình vào huy chương:

1936: Lars Valerian AHLFORS ; (Phần lan) Jesse DOUGLAS (Hoa Kì)
1950: Laurent SCHWARTZ (Pháp); Atle SELBERG (Na Uy)
1954:Kunihiko KODAIRA (Nhật); Jean-Pierre SERRE (Pháp)
1958: Klaus Friedrich ROTH (Anh); René THOM (Pháp)
1962: Lars HORMANDER (Thuỵ Điển); John Willard MILNOR (Hoa Kì)
1966: Michael Francis ATIYAH (Anh); Paul Joseph COHEN (Hoa Kì)
Alexander GROTHENDIECK (Pháp); Stephen SMALE (Hoa Kì)
1970: Alan BAKER (Anh); Heisuke HIRONAKA (Nhật);
Sergey NOVIKOV (Liên Xô); John Griggs THOMPSON (Hoa Kì)
1974: Enrico BOMBIERI (Italia); David Bryant MUMFORD (Hoa Kì)
1978: Pierre René DELIGNE (Bỉ); Charles Louis FEFFERMAN (Hoa Kì)
Gregori MARGULIS (Liên Xô); Daniel G. QUILLEN (Hoa Kì)
1982: Alain CONNES (Pháp); William P. THURSTON (Hoa Kì)
Shing-Tung YAU (Hoa Kì)
1986: Simon K. DONALDSON (Anh); Gerd FALTINGS (Đức)
Michael H. FREEDMAN (Hoa Kì)
1990: Vladimir DRINFELD (Liên Xô); Vaughan F.R. JONES (New
Zealand); Shigefumi MORI (Nhật); Edward WITTEN (Hoa Kì)
1994: Jean BOURGAIN (Bỉ); Pierre-Louis LIONS (Pháp);
Jean-Christophe YOCCOZ (Pháp); Efim ZELMANOV (Nga)
1998: Richard E. BORCHERDS (Hoa Kì); W. Timothy GOWERS (Anh)
Maxim KONTSEVICH (Nga); Curtis T. MCMULLEN (Hoa Kì)
2002: Laurent LAFFORGUE (Pháp); Vladimir VOEVODSKY (Nga)

2006: Grigory PERELMAN (Nga); Andrey OKOUNKOV (Nga)
Terence TAO (Australia); Wedelin WERNER (Pháp)

[b]Ngày 19/8/2010 là một ngày trọng đại đối với lịch sử toán học và khoa học Việt Nam, khi thêm một cái tên nữa được khắc vào Huy chương Fields: Ngô Bảo Châu.[/b]

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 nhằm đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

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

Có bạn bào thực sự hiểu bài 7 không?mình không hiểu lắm,nhờ mấy bạn trợ giúp.

VuMinhTan (113A) đã viết:đồng bộ hóa công việc của P1, P2, P3. sao cho:

a) P1 trước P2 và P3?
b) P1 và P2 trước P3?

ai hiểu rõ vấn đề này nói rõ dùm mình đc ko oa oa.........

a) thực hiện công việc đồng bộ sao cho P1 thực hiện trước nhất, sau đó đến P2 or P3 không phân biệt thứ tự ai vào trước thực hiện trước.
b) tương tự trên thực hiện sao cho P1 và P2 thi hành trước sau đó đến P3

Đồng bộ hóa công việc của các tiến trình để các tiến trình chạy một cách có trật tự, đảm bảo tính nhất quán của tài nguyên dùng dung.

Nhất quán: Có chờ lẫn nhau. Ví dụ: nhà sản xuất chưa hoàn tất tính toán nhà tiêu thụ đã lấy sản phẩm dẫn đến kết quả sai, không đảm bảo tính toàn vẹn.

Tài nguyên dùng chung: là các mảng buffer ( bài toán sản xuất và tiêu thụ )

Nếu như các luồng làm việc không đúng trật tự, không đúng công việc sẽ dẫn đến kết quả sai. Ví dụ hàm sleep để trễ một chút, để đồng bộ ).

Đồng bộ hóa tránh được tình trạng dead clock: các tiến trình rơi vào trạng thái treo không làm việc được.

Ví dụ bài toán sản xuất tiêu thụ có biến count để đếm số sản phẩm trong bộ đệm, gán bằng 0 khi chưa có sản phẩm nào.
vòng lặp lẩn quẩn bên trong khi count =0 và chờ đến khi count !=0 tức là có sản phẩm thì nhà tiêu thụ mới lấy về.
kiểm tra chỗ trống để xếp vào bộ đệm.
Nhà sản xuất không được xếp thêm vào bộ đệm nếu như không còn chỗ trống, nhà tiêu thụ không được lấy sản phẩm khi không có sản phẩm nào trong bộ đệm. Công việc của nhà sản xuất nhà tiêu thụ được đồng bộ hóa.