Thảo luận Bài 7

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

Câu 1: Trình bày mục đích của đồng bộ hóa công việc của các tiến trình. Nêu các ví dụ minh họa.

Câu 2: Trình bài khái niệm đoạn tương tranh và cách giải quyết vấn đề này.

Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của đèn hiệu.

Đoạn tương tranh là đoạn mã chương trình, điều khiển công việc của tiến trình có tính chất, mà khi thể hiện đoạn mã đó tác động tới tài nguyên dùng 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).

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

Khái niệm đèn hiệu:
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):

typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

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

- Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

Đồng bộ hóa công việc P1, P2, P3 sao cho :
1. P1 trước P2, P2 trước P3
2. P1 trước P2 và P3
3. P1, P2 trước P3
Bạn nào giải bài này rùi thì chỉ mình làm với. Help help help...

Giả sửa có 3 tiến trình P1, P2 và P3 có mã tương ứng là S1, S2 và S3

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 giá trị của synch lên 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.

Giả sửa có 3 tiến trình P1, P2 và P3 có mã tương ứng là S1, S2 và S3

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.

Giả sửa có 3 tiến trình P1, P2 và P3 có mã tương ứng là S1, S2 và S3

Semaphore synch1 = 0, synch2 = 0;

P1 P2 P3
S1 wait(synch1); wait(synch2);
signal(synch1); S2, signal(synch1); S3

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ài 1: Thiết kế lại đèn hiệu ở đầu cầu để cho tối đa được 2 chiếc ô tô cùng 1 lúc trên mặt cầu?
Trả lời: theo bài học thì hàm wait có giá trị truyền vào là mutex và mutex = 1, mình sẽ đổi giá trị đó thành 2 vậy khi xe 1 lên cầu thì giá trị mutex=1 và xe thứ 2 lên thì mutex=0 khi có chiếc thứ 3 tới nó sẽ chờ vì trong hàm wait có vòng lặp while(mutex<-0);, khi 1 xe đã xuống cầu thì nhờ vào hàm signal mà mutex=1, tiếp đó thì xe 3 được lên. Vậy cùng 1 lúc chỉ có 2 chiếc xe trên mặt cầu.
Bài 2: Đồng bộ công việc sao cho P1 trước P2, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:
Bài 3: Đồng bộ P1, P2, P3 sao cho P1 trước P2 và P3
Trả lời: Ta dùng đèn hiệu sau:
Bài 4: Đồng bọ P1, P2, P3 sao cho P1, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:
P\S: đây là cách giải của mình ai có cách giải khác thì post lên cho mọi người tham khảo .
Lưu ý: các bài giải trên không bít là đúng hay sai đây chỉ là ý kiến riêng của mình nên mong mọi người chỉ bảo thêm.[code]

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

Mình trả lời câu 1, tai sao phải đồng bộ hóa công việc và cho ví dụ:
Đồng bộ hóa công việc để bảo đảm tính nhất quán của tài nguyên dùng chung, để tài nguyên được sử dụng đúng đắn và hiệu quả nhất, tránh hiện tượng deadlock (hiện tượng kẹt tiến trình).
vd: nhà chỉ có 1 chiếc xe máy, mẹ lấy xe đi chợ , cả nhà phải chờ mẹ vê mới có xe để đi làm công việc của mình

Đoạn 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 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.

huynguyen đã viết: Mình trả lời câu 1, tai sao phải đồng bộ hóa công việc và cho ví dụ:
Đồng bộ hóa công việc để bảo đảm tính nhất quán của tài nguyên dùng chung, để tài nguyên được sử dụng đúng đắn và hiệu quả nhất, tránh hiện tượng deadlock (hiện tượng kẹt tiến trình).
vd: nhà chỉ có 1 chiếc xe máy, mẹ lấy xe đi chợ , cả nhà phải chờ mẹ vê mới có xe để đi làm công việc của mình

Ví dụ: Tại ngã 4, huớng nào đèn xanh được đi còn đèn đỏ phải đứng lại. Giao nhau của 4 huớng là tài nguyên dùng chung chính vì vậy tất cả phải đồng bộ nếu không sẽ xảy ra tai nạn hoặc kẹt xe (deadlock)...Ví dụ của bạn hơi khó hiểu mình đóng góp xíu...

- Đồng bộ hóa các tiến trình nhằm mục đích đảm bảo tính nhất quán, tính đúng đắn về tài nguyên dùng chung của các tiến trình.
VD máy tính: Lấy bài toán sản xuất tiêu thụ làm ví dụ. Hàm sleep(1) nhằm mục đích đồng bộ hóa các tiến trình, chờ một khoảng để khi show buffer ra ngoài màn hình biến “in” đã tăng lên 1 => đảm bảo tính đúng đắn của dữ liệu. Nếu không có sleep(1), tại thời điểm đó biến in vẫn còn lưu giá trị củ.
VD thực tế: khi thầy giáo viết lên bảng 1 câu chưa hoàn tất “Biên dịch khác với phiên”. Một bạn học sinh đã lấy máy ảnh chụp lại nội dung đó và không chờ cho đến khi thầy giáo kết thúc “Biên dịch khác với phiên dịch” => Không nhất quán về dữ liệu.

- Ngoài ra, nhờ đồng bộ hóa các tiến trình mà các tiến trình hoạt động phối hợp với nhau mượt hơn, êm ả hơn → Tránh gây ra tình trạng kẹt tiến trình (deadlock).
VD máy tính: Khi máy tính vận hành nhiều tiến trình cùng một thời điểm. Nếu hệ điều hành không đứng ra đồng bộ (yêu cầu chương trình này đứng chờ cho đến khi một chương trình khác hoàn thành) mà cho tiến trình hoạt động tự do, chiếm CPU sẽ dẫn đến trình trạng treo máy.
VD thực tế: Mỗi một xe máy trên đường là một tiến trình, cùng nhau sử dụng tài nguyên dùng chung là mặt đường. Nếu không có công an giao thông (hệ điều hành) đứng ra điều phối, hướng dẫn đường đi khi đông xe thì sẽ bị kẹt xe => Đồng bộ để bảo vệ tài nguyên là rất quan trọng.

Ví dụ thực tế về đồng bộ hóa: Thầy chia lop thành 2 nhóm, nhóm lên bảng xếp hàng để chụp hình, nhóm còn lại làm nhiệm vụ chụp hình. Nếu nhóm bên dưới không chờ nhóm trên bảng xếp hàng ngay ngắn, chuẩn bị chụp hình thì sẽ có những bức hình lộn xộn, thậm chí có bạn nhắm mắt. Nếu nhóm chụp hình chờ 1 chút sẽ có những bức hình đẹp, việc đó gọi là đồng bộ hóa.

- Đoạn tương tranh là đoạn mã trong chương trình điều khiển công việc các tiến trình với tính chất là khi thực hiện đoạn mã đó thì tác động đến tài nguyên dùng chung.
- Để giải quyết vấn đề đoạn tương tranh người ta sẽ áp dụng “tính loại trừ lẫn nhau” nghĩa là chỉ có một tiến trình được vận hành trong một thời điểm ở đoạn mã đó, nếu có tiến trình khác cần làm việc trên cùng đoạn tương tranh thì phải đợi cho đến khi tiến trình đang vận hành ra khỏi đoạn tương tranh.
- Các tiến trình tương tranh có cấu trúc:

Chú thích:
- Đoạn còn lại: (nằm ngoài đoạn tương tranh) không gây ảnh hưởng gì đến tài nguyên dùng chung.
- Đoạn đăng nhập: báo cho các tiến trình khác biết rằng đang có 1 tiến trình đang vận hành đoạn mã tương tranh.
- Đoạn tương tranh: đoạn mã khi thực thi sẽ gây ảnh hưởng đến tài nguyên dùng chung.
- Đoạn đăng xuất: báo cho các tiến trình khác biết rằng hiện chưa có tiến trình vận hành đoạn mã tương tranh.

Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra]; 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
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[2].
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ó [3], để đ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.)[4]
Ô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.

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

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

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

- 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ự khóa mình (Block Itseft) 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ừ trạng 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 thuật giải cụ thể.

Khai báo :
Semaphore semEmpty=10, semFull=0, critsec=1;

Thuật giải dành cho nhà sản xuất :producer

Wait(semEmpty);
Wait(critsec);
Đưa sản phẩm vào bộ nhớ đệm
Signal(semFull);
Signal(critsec);


Thuật giải dành cho nhà tiêu thụ : Consumer

Wait(semFull);
Wait(critsec);
Lấy sp ra khỏi bộ nhớ đệm
Signal(semEmpty);
Signal(critsec);

Giả sử có hai tiến trình P1 và P2 thực hiện công việc của 1 kế toán, và cùng chia sẻ 1 vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút 1 khoản tiền tienrut từ tài khoản:
if (taikhoan - tienrut >= 0)
taikhoan = taikhoan - tienrut;
else
error( " không thể rút tiền !");

Giả sử trong tài khoản còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau:
-Sau khi đã kiểm tra điều kiện ( taikhoan - tienrut >=0 ) và nhận được kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.
-P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 ( do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.
-Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện ( taikhoan - tienrut >= 0) vì đã được kiểm tra trong đợt xử lý trước, mà nó sẽ thực hiện rút tiền. Giá trị của taikhoan sẽ được cập nhật lại thành -100. Tình huống lỗi xảy ra !

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

code dành cho tiến trình người lái xe (đoạn tương tranh);

*Khai báo :
----------------------------------------------------
Semaphore SemEmpty =10 ; semfull =0;
semaphore crictsec =1 ;
----------------------------------------------------------
* semafore s // 0 :đèn đỏ
// 1 :đèn xanh

wait (s)
lên cầu ;
qua cầu ;
=> đoạn tương tranh là lên cầu và qua cầu
signal (s);

* proceducer (nhà sản xuất )
wait (sem Empty)
wait (Critsec)
signal (Semfull) // đưa sản phẩm vào bô đệm ( đoạn tương tranh)
signal (Critsec); // đoạn đăng xuất ra đoạn tương tranh.

Consumer (luồng tiêu thụ)
wait (semfull);
wait (Critsec);
signal (semEmpty) // lấy sản phẩm ra bộ đệm (đoạn tương tranh)
signal (Critsec) //đoạn đăng xuất ra đoạn tương tranh.

----
các bạn xem qua và góp ý thêm nhé !!!!

Phương pháp đồng bộ hóa đèn hiệu được E.W.Dijstra đề xuất năm 1965 và được trao tặng danh hiệu Turing do hiệp hội các nhà tin học Mỹ lập ra và trao tặng . Một Semaphone S là một biến kiểu nguyên (integer) được truy suất với hai thao tác nguyên là
+ Hàm Wait ( ) : là một hàm không chia được, có một biến truyền vào là biến S kiểu đèn hiệu
+ Hàm Signal (báo hiệu) có tham số truyền vào là đèn hiệu hàm này không chờ, chỉ tăng đèn hiệu lên.
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 ( tring 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 Operationns)
Những sửa đổi đối với giá trị Integer của semaphore trong các thao tác Wait ( ) và Signal ( ) phải được thực thi không bị phân chia. Nghĩa là khi một tiến trình sửa đổi giá trị semaphore , không có tiến trình nào cùng một lúc có thể sửa đổi cùng biến semaphore đó. Ngoài ra , trong trường hợp của biến wait (s), kiểm tra giá trị integer của S (Sδ0) và sửa đổi có thể của nó (S--) cũng phải được thực thi mà không bị ngắt.
Trình bày 2 ứng dụng của đèn hiệu
+ Ứng dụng 1: Giải quyết vấn đề vùng tương tranh.
Mã của tiến trình Pi bây giờ có cấu trúc:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) { // (Đèn hiệu nhị phân)
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}

Đoạn tương tranh là mã khi thực hiện đoạn mã thì ảnh hưởng đến vùng tranh chấp, các code trong mã khi sử dụng chugn ảnh hưởng đến miền, vùng tranh chấp.
Ví dụ : giả sử có một cây cầu ở đấu cầu có 1 đèn mutex ( có 2 trạng thái xanh và đỏ) 2 ô tô tìm cách lên cầu nhưng trọng tải của cầu chỉ chịu được 1 ô tô khi lên cầu và ô tô khác phải chờ, đoạn qua cầu thuộc đoạn tương tranh, cầu chính là tài nguyên dùng chung, và lệnh qua cầu thuộc đoạn tương tranh.
Chúng ta có thể sử dụng semaphores để giải quyết vấn đề vùng tranh chấp với n tiến trình. N tiến trình chia sẻ 1 biến semaphore, mutex được khởi tạo.
Ứng dụng 2 : Đảm bảo công việc trật tự của các tiến trình.
Chúng ta cũng có thể sử dụng Semaphores để giải quyết vấn đề đồng bộ khác nhau
Thí dụ ,để xem xét hai tiến trình đang thực thi đồng hành : P1 với câu lệnh S1 và P2 với câu lệnh S2. Chúng ta tổ chức sao cho S2 được thực thi chỉ sau khi S1 đã hoàn thành , thực hiện bằng cách P1 và P2 chia sẻ một semaphore chugn Synch được khời tạo 0 và bằng cách chèn các câu lệnh Semaphore synch = 0;
Cấu trúc P1 Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2

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

Mình xin được bổ sung thêm 1 số ý về khái niệm Đèn Hiệu:

Đèn hiệu là một biến được bảo vệ hoặc một kiểu dữ liệu trừu tượng tạo ra sự trừu tượng hoá đơn giản nhưng hữu dụng để kiểm soát truy cập của nhiều tiến trình đến một tài nguyên chung trong môi trường lập trình song song.
Một cách nhìn về đèn hiệu là một bản ghi có bao nhiêu đơn vị của một tài nguyên có thể sử dụng, gắn với các tác vụ điều chỉnh bản ghi đó một cách an toàn (nghĩa là không tạo ra race condition) khi yêu cầu hoặc giải phóng các đơn vị và đợi đến khi một đơn vị rảnh rỗi nếu cần. Đèn hiệu là một công cụ hữu ích để chống race condition và khoá chết, tuy nhiên việc sử dụng nó không đảm bảo rằng chương trình không gặp phải các vấn đề trên. Đèn hiệu cho phép một số lượng tuỳ ý tài nguyên gọi là đèn hiệu đếm (counting semaphore) trong khi đèn hiệu bị giới hạn trong giá trị 0 và 1 được gọi là đèn hiệu nhị phân (binary semaphores).
Khái niệm đèn hiệu được phát minh bởi nhà nghiên cứu người Hà Lan Edsger Dijkstra

Ví dụ 1: Đèn hiệu được dùng trong lĩnh vực truyền thông: 1 số điện thoại chỉ nhận được 1 cuộc gọi duy nhất tại 1 thời điểm.Giả sử khi bạn gọi đến 1 số điện thoại. trường hợp số điện thoại đó đang nhận 1 cuộc gọi khác thì bạn sẽ nhận được thông báo "cuộc gọi bận" bên phía bên này, điều đó cũng có nghĩa là Đèn hiệu đang ở trạng thái báo bận, còn khi gọi đến mà có tín hiệu "tút tút (wait...)" thì cuộc gọi đó có thể thực hiện, đèn hiệu ở trạng thái active

Ví dụ 2: Đèn hiệu dùng trong thông báo trạng thái của xe taxinếu bạn để ý trên xe taxi đều có 1 tấm bản nhỏ với đèn báo. khi xe có khách thì đèn báo này tắt, khi xe không có khách thì đèn báo này bật sáng để người đón xe dễ phân biệt

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

if (taikhoan - tienrut >=0)

taikhoan = taikhoan - tienrut;

else

error(� khong the rut tien ! �);

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

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

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

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

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