Thảo luận Bài 7

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

Đảm bảo tính nhất quán của tài nguyên dùng chung.
- Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng 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

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

VD1:
Trong thư viện của trường học chỉ có 1 máy tính (tài nguyên dùng chung) , Sinh viên A vào sử dụng máy tính để nghiên cứu tư liệu .Sinh viên B vào sau muốn sừ dụng máy tính thì phài đợi SV A sử dụng xong mới dùng được .

VD2 :
Tong công ty , có 1 chiếc thang máy ( tài nguyên dùng chung ) , nhân viên A vào thang máy trước nên lên trước . Nhân viên B tới sau thì đợi lên sau .

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

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

Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S :
Chờ cho đến khi giá trị của đèn hiệu S > = 1 sau đó qua được lệnh chờ này và giá trị của đèn tự động giảm đi 1.
Ý nghĩa của hàm signal : Đèn S tăng lên 1

Admin
Phải là: Giá trị của đèn S được tăng thêm 1 !

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

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

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.

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

2 ứng dụng của đèn hiệu:

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.

2. Đảm bảo các tiến trình làm việc đúng thứ tự

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 sau:
semaphore synch = 0;
Cấu trúc P1:
S1
signal (synch) ;
Cấu trúc P2:
wait(synch);
S2

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

Mã của tiến trình Xei có cấu trúc như sau:

Code:

Typedef int semaphore;
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái
                              //0: đèn màu đỏ
                              //1: đèn màu xanh
While(1)
{
  Đi đến cầu;
  Wait(mutex);  //chờ đèn xanh
      Lên cầu;  //đoạn tương tranh, đèn màu đỏ
      Qua cầu; //đoạn tương tranh, đèn màu đỏ
  Signal(mutex); //đèn chuyển sang màu xanh
  Đi tiếp;
  Quay về theo cầu khác;
}

Do chiếc cầu yếu nên mỗi thời điểm chỉ có 1 xe được phép qua cầu. Những xe khác khi đi đến đầu cầu sẽ ngủ tại lệnh wait(mutex) vì đèn đỏ. Sau khi một xe đã lên cầu và qua cầu xong thì lệnh signal(mutex) được thực hiện, tăng đèn mutex lên 1, đèn chuyển sang màu xanh. Một xe sau sẽ được đánh thức và lên cầu. Trong trường hợp này vùng tranh chấp là cây cầu.

Đoạn tương tranh là đoạn mã của tiến trình, khi thực hiện thì ảnh hưởng đến vùng tranh chấp
VD: Vùng tranh chấp là bảng đen, mỗi thời điểm có một sinh viên thao tác trên đó, sau khi sinh viên đó xong thì sinh viên khác mới tiếp tục được thao tác trên bảng.

Admin
- Phân biệt đúng được 2 khái niệm khác nhau là: "Đoạn tương tranh" và "Vùng tranh chấp".
- Trong ví dụ trên chưa nêu được ví dụ của "Đoạn tương tranh" ! (Vùng tranh chấp là Bảng đen là đúng rồi)

• Đả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ụ : bạn a lên bản viết một lá đơn phần họ tên ghi là nguyễn văn a và phần ký tên là lê văn b. lúc sau đó bạn b lên bảng sửa lại phần ký tên cho đúng là nguyễn văn a. lúc đó phái dưới lớp có bạn c lấy máy ảnh chụp lại cái bảng đang lúc bạn b đang sửa lại phần ký tên mới gi là nguyễn văn, dẫn đến nội dung sai lệch, không hoàn chỉnh và thiếu nhất quán. đáng lẽ bạn c phải chờ bạn b thực hiện song công việc là sửa phần ký tên là nguyễn văn a song rồi mới chụp thì nội dung mới đú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).

_ Tên đầy đủ là Edsger Wybe Dijkstra, sinh ngày 11 tháng 5 năm 1930 tại Rotterdam, mất ngày 6 tháng 8 năm 2002 tại Nuenen sau một thời gian dài bị ung thư, ông 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).
_ 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.
_ 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".
_ Một năm sau khi ông mất, 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.

Đồng bộ công việc các tiến trình P1, P2, P3 sao cho P1 trước P2 và P3.


Giải :

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

- đoạn tương tranh (critical section problem) : là 1 phần trong một đoạn mã khi chạy sẽ tác động đến tài nguyên chung (ví dụ, vùng nhớ chung).
ví dụ: hai bạn a và b cùng tranh nhau lên bảng sửa bài tập của thầy cùng một lúc kết quả cả hai đều sửa sai.
- tính loại trừ lẫn nhau hay loại trừ tương hỗ(mutual exclusion): khi có một tiến trình đang ở trong đoạn tương tranh thì sẽ không có một tiến trình khác cũng ở trong đoạn tương tranh này.
ví dụ :khi bạn a lên bảng làm bài tập thì bạn b phải chờ khi đến lượt mình được lên.

HaHoangCongTien80 (113A) đã viết:Đồng bộ công việc các tiến trình P1, P2, P3 sao cho P1 trước P2 và P3.


Giải :

Thiếu 1 lệnh "signal (synch2);" trong P1 rồi bạn ơi.
Mình bổ xung :
P1
S1
signal (synch1);
signal (synch2);

Admin
- Phát hiện đúng !
- "Bổ Sung" chứ không phải "Bổ Xung" !

HaHoangCongTien80 (113A) đã viết:Đồng bộ công việc các tiến trình P1, P2, P3 sao cho P1 trước P2 và P3.


Giải :

giải thích rõ hơn về đường đi của nó đc ko

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.
Người nhận giải thưởng đầu tiên năm 1966, là Alan Perlis của viện Carnegie Institute of Technology. Năm 2006, Frances E. Allen của IBM là người phụ nữ đầu tiên và duy nhất cho đến nay được nhận giải thưởng.

1966: Alan J. Perlis-Cho những ảnh hưởng trong các kỹ thuật lập trình và xây dựng chương trình dịch
1967: Maurice V. Wilkes -Giáo sư Wilkes được biết tới như là người thiết kế và xây dựng EDSAC, máy tính đầu tiên với hàm nội chứa (internally stored). Ông là đồng tác giả với Wheeler và Gill của tập sách "Preparation of Programs for Electronic Digital Computers" xuất bản 1951
1968: Richard Hamming- Cho các đóng góp về các phương pháp số, các hệ thống tự mã hóa, phát hiện và sửa lỗi sai
1969: Marvin Minsky-Trí tuệ nhân tạo
1970: James H. Wilkinson-Cho những nghiên cứu về phân tích số cho việc sử dung các máy tính số tốc độ cao, những đóng góp về Đại số tuyến tính và phân tích lỗi ngược
1971: John McCarthy-Cho những đóng góp về Trí tuệ nhân tạo "The Present State of Research on Artificial Intelligence"
1972: Edsger W. Dijkstra-Là người đóng góp chủ yếu cho ngôn ngữ lập trình ALGOL. Ông cũng nổi tiếng với thuật toán Dijkstra
1973: Charles W. Bachman-Cho những đóng góp đáng chú ý của ông về công nghệ database
1974: Donald E. Knuth-Với những cống hiến cho việc phân tích giải thuật và thiết kế ngôn ngữ lập trình, và đặc biệt với tác phẩm kinh điển Nghệ thuật lập trình "The Art of Computer Programming"
1975: Allen Newell và Herbert A. Simon-Với những đóng góp quan trọng cho chuyên ngành trí tuệ nhân tạo , tâm lý học về nhận thức chủ quan (psychology of human cognition), và xử lý chuỗi
1976: Michael O. Rabin và Dana S. Scott-Với bài báo "Finite Automata and Their Decision Problem" (Automat hữu hạn và bài toán quyết định) đã giới thiệu các ý tưởng về máy phi bất định nondeterministic machines, đã làm sáng tỏ rất nhiều khái niệm có giá trị.
1977: John Backus- đã đóng góp nhiều công sức cho việc thiết kế các hệ thống ngôn ngữ lập trình bậc cao, tiêu biểu là FORTRAN, và các bài báo phôi thai cho các thủ tục hình thức của đặc tả các ngôn ngữ lập trình
1978 Robert W. Floyd Có ảnh hưởng sâu sắc đến các phương pháp luận của việc xây dựng hiệu quả các phần mềm tin cậy, đặt nền móng cho nhiều chuyên ngành hẹp của khoa học máy tính: lý thuyết phân tích ngữ pháp, ngữ nghĩa của các ngôn ngữ lập trình, tự động kiểm tra chương trình program verification, tự động tổng hợp chương trình, và phân tích giải thuật
1979: Kenneth E. Iverson-Với những nỗ lực tiên phong trong ngôn ngữ lập trình và các ký pháp toán học tạo nên một lĩnh vực chuyên ngành máy tính mớilaf APL, cho những đóng góp của ông về thực hiện hệ tương tác, đào tạo sự dụng APL, và lý thuyết và ứng dụng ngôn ngữ lập trình
1980: C. Antony R. Hoare-Cho những đóng góp cơ bản về thiết kế và định nghĩa ngôn ngữ lập trình. Ông cũng là tác giả của giải thuật sắp xếp nổi tiếng Quick sortvà ngôn ngữ CSP
1981: Edgar F. Codd-Với những đóng góp nền tảng cho lý thuyết và vận dụng các hệ thống quản trị cơ sở dữ liệu, đặc biệt là cơ sở dữ liệu quan hệ
1982: Stephen A. Cook-Góp phần thúc đẩy và mở rộng việc nhận thức về độ phức tạp tính toán
1983: Ken Thompson và Dennis M. Ritchie-Với việc phát triển lý thuyết hệ điều hành và đặc biệt là hệ điều hành UNIX
1984: Niklaus Wirth-Cho việc phát triển các ngôn ngữ lập trình mới EULER, ALGOL-W, MODULA và PASCAL
1985: Richard M. Karp-Với những đóng góp liên tục về lý thuyết lập trình bao gồm việc phát triển các giải thuật hiệu quả cho luồng mạng và các bài toán tối ưu tổ hợp, định ra khả năng tính toán thời gian đa thức và các khái niệm về hiệu quả giải thuật, và đóng góp nổi bật về lý thuyết NP-đầy đủ NP-completeness
1986: John Hopcroft và Robert Tarjan-Cho những đóng góp căn bản về phân tích thiết kế cấu trúc dữ liệu và giải thuật
1987: John Cocke- Cho những đóng góp quan trọng trong việc thiết kế và lý thuyết hóa chương trình dịch, kiến trúc các hệ thống lớn và phát triển các tập lệnh đơn giản trong máy tính (RISC)
1988: Ivan Sutherland-Cho việc tiên phong trong lĩnh vực đồ họa computer graphics, khởi đầu với chương trình Sketchpad
1989: William (Velvel) Kahan-Cho những đóng góp cơ bản về phân tích sốnumerical analysis. Một trong những chuyên gia đầu ngành về tính toán dấu phẩy động floating-point.
1990: Fernando J. Corbató-Đi đầu trong việc tổ chức và dẫn dắt sự phát triển của các hệ thống máy tính mục đích chung, large-scale, chia sẻ thời gian và nguồn lực, CTSS vàMultics.
1991: Robin Milner-Cho ba thành tựu quan trọng: 1) LCF, cơ chế hóa Logic Scott's of của hàm khả tính (Computable Functions), 2) ML, ngôn ngữ đầu tiên có tính đa hình type inference cùng với kiểu "an toàn" type-safe và cơ chế bắt ngoại lệ exception-handling ; 3) Các hệ thống truyền thông giải tíchCCS, lý thuyết tông quát về tương tranh concurrency. Ông cũng đồng thời khái quát hóa full abstraction, nghiên cứu các mối quan hệ ngữ nghĩa thao tác. operational.
1992: Butler W. Lampson-Cho những đóng góp cho việc phát triển môi trường tính toán cá nhân và phân tán.
1993: Juris Hartmanis và Richard E. Stearns-Thiết lập nền tảng cho lý thuyết độ phức tạp tính toán.
1994: Edward Feigenbaum và Raj Reddy-Tiên phong trong việc xây dựng các hệ thống lớn về trí tuệ nhân tạo, chứng minh tầm quan trọng thực tiễn và khả năng thương mại của trí tuệ nhân tạo.
1995: Manuel Blum- Ghi nhận cho những đóng góp cơ bản về lý thuyết độ phức tạp tính toán và các ứng dụng trong cryptography và program checking.
1996: Amir Pnueli- Giới thiệu temporal logic vào khoa học máy tính và các hệ thống verification.
1997: Douglas Engelbart- Đóng góp về tính toán tương tác
1998: Jim Gray- Đóng góp về cơ sở dữ liệu và xử lý giao dịch
1999: Frederick P. Brooks, Jr. Những đóng góp về kiến trúc máy tính, hệ điều hành và kỹ nghệ phần mềm.
2000: Andrew Chi-Chih Yao Đóng góp về lý thuyết tính toán, pseudorandom number generation, cryptography, và communication complexity.
2001: Ole-Johan Dahl và Kristen Nygaard- Những ý tưởng cơ bản về lập trình hướng đối tượng.
2002: Ronald L. Rivest, Adi Shamir và Leonard M. Adleman- Những đóng góp về mã hóa khóa công khai public-key cryptography, RSA (mã hóa).
2003: Alan Kay- Với các ý tưởng cội nguồn về các ngôn ngữ lập trình hướng đối tượng vàSmalltalk.
2004: Vinton G. Cerf và Robert E. Kahn- Đóng góp cho internetworking, bao gồm thiết kế và triển khai các giao thức Internet' TCP/IP.
2005: Peter Naur- Với những đóng góp về thiết kế ngôn ngữ lập trình.
2006: Frances E. Allen- Những đóng góp về lý thuyết và thực nghiệm tối ưu hóa các kỹ thuật chương trình dịch.
2007: Edmund M. Clarke, E. Allen Emerson và Joseph Sifakis- Phát triển kiểm tra mô hình Model-Checking.
2008: Barbara Liskov- Những đóng góp cho cơ sở lý thuyết và thực tiễn của ngôn ngữ lập trình và thiết kế hệ thống, đặc biệt về trừu tượng hóa dữ liệu, khả năng chịu lỗi và tính toán phân tán
2009: Charles P. Thacker- Tiên phong trong thiết kế và hiện thực Alto, mô hình máy tính cá nhân đầu tiên, và những đóng góp của ông với Ethernet và máy tính bảng cá nhân.

VuMinhTan (113A) đã viết:

HaHoangCongTien80 (113A) đã viết:Đồng bộ công việc các tiến trình P1, P2, P3 sao cho P1 trước P2 và P3.


Giải :

giải thích rõ hơn về đường đi của nó đc ko

Đầu tiên bạn có thể cho P1 hoặc P2 hoặc P3 cái nào đến trước cũng được. Theo đề bài ta có P1 chạy trước P2 và P3 nên ở P2 và P3 có dòng chờ Wait(synch1) và Wait(Synch2). Theo điều kiện thì đèn hiệu synch phái >= 1 thì mới vượt qua dòng đợi này nên P2 và P3 tạm thời ngũ tại đây. Lúc này P1 sẽ chạy, dòng signal(synch) có vai trò tăng synch1 và synch2 lên 1. Lúc này Synch1 và synch2 đều = 1, thỏa điều kiện nên P2 và P3 được phép chạy.
Bài này lời giải chưa chính xác lắm. Chổ P1 bạn cần thêm 1 dòng signal(Synch2) nữa.
Có gì thiếu sót mọi người bổ sung nha. ^^