Thảo luận Bài 7

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

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.

Danh sách những người nhận giải:

Năm	Người nhận	Trích dẫn
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	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
....	.....	............................
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	Flag of the United StatesBarbara 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	Flag of the United StatesCharles 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.

Trích: http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_Turing

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

LƯU Ý: ĐOẠN TƯƠNG TRANH KHÁC VÙNG TRANH CHẤP VÌ ĐOẠN TƯƠNG TRANH LÀ ĐOẠN MÃ KHI THỰC HIỆN THÌ NÓ ẢNH HƯỞNG ĐẾN VÙNG TRANH CHẤP

Ví dụ sau minh họa cách thức độc quyền truy cập: hệ thống có hai quá trình đang hợp tác.
- Quá trình A bắt đầu thực hiện trên vùng tương tranh ở thời điểm T1

- Ở thời điểm T2, quá trình B cần vào vùng tương tranh nhưng phải chờ

vì có một quá trình đang thực hiện ở đấy.

- Quá trình B chờ cho đến thời điểm T3 khi quá trình A kết thúc thực hiện vùng tương tranh.
- Ở thời điểm T4, quá trình B kết thúc thực hiện trên vùng tương tranh

.- Giả sử có n tiến trình { P0, P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên chung.

- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.

- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

*************ví dụ minh họa**********
Tôi đang làm thì anh phải nghỉ, anh làm thì tôi nghỉ hay là bạn Tính lên bảng thì bạn An không lên bảng được (bạn An phải ngồi chờ bạn Tính làm xong và đi xuống bảng thì khi đó bạn An mới được lên bảng ghi) => sẽ tác động đến tài nguyên dùng chung, trong cùng 1 thời điểm thì chỉ có 1 tiến trình được tác động đến tài nguyên dùng chung (tính loại trừ)

các bạn ơi chỉ giúp mình cách đưa hình lênh diễn đàn với,minh đưa bài lênh mà không có hình ,hic hic

câu 4: đồ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 ý.

buithithudung24 (i11c) đã viết:- 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).

LƯU Ý: ĐOẠN TƯƠNG TRANH KHÁC VÙNG TRANH CHẤP VÌ ĐOẠN TƯƠNG TRANH LÀ ĐOẠN MÃ KHI THỰC HIỆN THÌ NÓ ẢNH HƯỞNG ĐẾN VÙNG TRANH CHẤP

ví dụ về vùng tranh chấp
Vùng tranh chấp là cái bảng. Ở 1 thời điểm chỉ có 1 sinh viên lên thao tác trên đó. Sau khi sinh viên đó xong thì sinh viện khác với được lên bảng thao tác.
=> Cái bảng nói tới ở trên là "Vùng tranh chấp".

Bài toán như sau: “Lập trình bài toán sản xuất tiêu thụ được đồng bộ bằng 2 đèn hiệu SemEmpty và SemFull”.

Producer:
Wait (SemEmpty);
Wait (Mutex);
Buffer [in] = sp mới; //xếp sản phẩm vào bộ đệm
in = (in + 1) % BUFFER_SIZE;
Signal (SemFull);
Signal(Mutex);
Consumer:
Wait (SemFull);
Wait (Mutex);
p = Buffer [out] //lấy sản phẩm ra khỏi bộ đệm
out = (out + 1) % BUFFER_SIZE;
Signal (SemEmpty);
Signal (Mutex);
Lưu ý:
Giá trị ban đầu của Mutex là 1.
Giá trị ban đầu của SemFull là 0.
Giá trị ban đầu của SemEmpty là BUFFER_SIZE.

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

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

TrinhThiPhuongThaoI11C đã viết:

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty X
Tôi tên là: Nguyễn Văn A
.........(nội dung đơn).........
TP.HCM, ngày 20 tháng 10 năm 2011
Người làm đơn
............(chữ ký).............
Nguyễn Văn A

Nội dung đơn này phải đảm bảo tính toàn vẹn( Integrity), ví dụ: Phía trên là Nguyễn Văn A thì phía dưới cũng phải là Nguyễn Văn A.
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 Nguyễn Văn A phía trên thành Nguyễn Văn An, trong khi P2(nhà sản xuất khác) sửa Nguyễn Văn A phía dưới thành Nguyễn Văn Ân, 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.

Ví dụ khác về vùng tương tranh.
Vùng tương tranh là cái bảng trong lớp. Ở 1 thời điểm chỉ có 1 sinh viên lên thao tác trên đó. Sau khi sinh viên đó xong thì sinh viện khác với được lên bảng thao tác trên bảng tiếp. Cùng một lúc không thể có hai sinh viên cùng thao tác trên bảng...
Vùng hay Đoạn tương tranh Đoạn Găng là đoạn mã của tiến trình, còn cái bảng nói tới ở trên là Vùng tranh chấp !

NguyenXuanTri28 đã viết:- Đ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).

Cấu trúc mã của tiến trình tương tranh.
while (1)
{
Remainder section
Entry section
Critical section
Exit section
Remainder section
}

ThanhThao04(I11C) đã viết:Bài toán như sau: “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.

Thông tin rất bổ ích, thanks bạn

Một chiếc cầu yếu mỗi thời điểm chỉ cho 1 xe được qua. Đèn hiệu S ở đầu cầu có 2 trạng thái Xanh (mã 1) và Đỏ (mã 0), các lệnh Lên cầu và Qua cầu trong code của mỗi lái xe thuộc Đoạn tương tranh (do ảnh hưởng tài nguyên dùng chung). Code đó như sau:
Mỗi xe muốn lên cầu, phải thực hiện lệnh wait(S) để xem đèn đã Xanh chưa. Nếu Xanh, giá trị của đèn S bị trừ đi 1 (Xanh->Đỏ) và các lệnh Lên cầu và Qua cầu lần lượt được thực hiện. Xe sau không thể lên được do đèn S đang đỏ.

Khi xe qua cầu xong, lệnh signal(S) thực hiện: Giá trị của S (đang bằng 0) được tăng lên 1, tức thành màu Xanh. Xe sau đang "ngủ" tại lệnh wait(S) của nó, được "Người gác cầu" (chính là Hệ điều hành) đánh thức và qua được wait(S) để Lên và Qua cầu,..........

phamdieptuan (I11C) đã viết:câu 4: đồ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 ý.

Đề nghị bạn giải thích rõ câu b giùm. Mình chưa hiểu rõ !!! THANKS

caotanthanh(I11c) đã viết:các bạn ơi chỉ giúp mình cách đưa hình lênh diễn đàn với,minh đưa bài lênh mà không có hình ,hic hic

Thứ 1 là bạn có thể : up lên 1 trang nào khác vd như upanh.com rùi past link vào là ok.
Thứ 2 là bạn dùng sẵn chức năng của diễn đàn tên nó là Host an Image, vào đó bạn chỉ cần up ảnh cần đưa lên là ok.



Chúc bạn thành công nhé.

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

phamdieptuan (I11C) đã viết:câu 4: đồ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 ý.

Cám ơn bạn vì bài giải nhưng thật sự mình chưa hiểu rõ lắm!

Xét hai tiến trình P1 và P2
Yêu cầu: lệnh S1 trong P1 cần 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;

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

- Tranh duoc hien tuong dealock
- Dam bao tinh nhat quan trong viec dung chung tai nguyen
VD: Ban A su dung bang viet ten minh la Nguyen Van A. Nhung ban chi viet toi Nguyen van. Mot ban khac su dung phan bang do viet ten minh la Tran Van B. ban B viet de len phan bang cua ban A. vi vay ko doc duoc ten ban A. Do do phai dong bo hoa tien trinh de tranh tinh trang do

phamdieptuan (I11C) đã viết:câu 4: đồ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 ý.

Mình hiểu bài của bạn . Nhưng ở câu b yêu cầu đề bài là P1 trước P2 và P3 và theo như cách của bạn thì P2 sẽ chạy trước P3 giờ mình muốn P3 chạy trước P2 có được ko (tất nhiên ko phải yêu cầu bài nhưng mình muốn thế) , vì trên lớp mình có nghe thấy nói khi các tiến trình đi vào vùng tương tranh ko cần phải theo thứ tự , nghĩa là ở trường hợp này P3 nằm sau P2 nhưng nó được đưa vào trong vùng tương tranh trước P2 .

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

Xét 2 process: P1 và P2
Yêu cầu: lệnh S1 trong P1 đượ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ộ họat độ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;