Thảo luận Bài 7

Alan Mathison Turing (23 tháng 6, 1912 – 7 tháng 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. Phép thử 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 đã hình 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 tất cả những gì tính được bằng thuật toán đều có thể tính được bằng máy Turing.

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 giải mật mã của hải quân Đức. Ông đã sáng chế ra nhiều kỹ thuật 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 cà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 1 trong những đồ án thiết kế đầu tiên của 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ăm1947 ô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, và trở nên quan tâm tới sinh học toán học. Ông đã viết bài báo về cơ sở hóa học của sự tạo hình, và ông cũng đã dự đoán được các phản ứng hóa học dao động chẳng hạn như phản ứng Belousov–Zhabotinsky, được quan sát thấy lần đầu tiên trong thập niên 1960.

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 chấp nhận dùng liệu pháp hoóc môn nữ (thiến hóa học) thay cho việc phải ngồi tù. Ông mất năm 1954, chỉ 2 tuần sau lần sinh nhật thứ 42, do ngộ độc xyanua. Một cuộc điều tra đã xác định nguyên nhân chết là tự tử, nhưng mẹ ông và một số người khác tin rằng cái chết của ông là một tai nạn. Ngày 10 tháng 9 năm 2009, sau một chiến dịch Internet, thủ tướng Anh Gordon Brown đã thay mặt chính phủ Anh chính thức xin lỗi về cách đối xử với Turing sau chiến tranh.

Các bước thực thi đèn hiệu trong windows.

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

Sau khi về đọc lại ví dụ "xe qua cầu yếu" xong mình có một chút thắc mắc về 1 vấn đề như sau: nếu đoạn code ở phần cuối cùng là "Xe Quay về theo cầu khác", vậy thì nếu cầu khác cũng là "một cầu yếu" vậy thì mình sẽ có 1 đoạn code while lồng while như sau:
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ề;
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ề;
}
}
Đoạn code này do mình tự suy nghị ra, mong thầy và các bạn góp ý dùm mình

NguyenVoDuyTan(I22A) đã viết:
Sau khi về đọc lại ví dụ "xe qua cầu yếu" xong mình có một chút thắc mắc về 1 vấn đề như sau: nếu đoạn code ở phần cuối cùng là "Xe Quay về theo cầu khác", vậy thì nếu cầu khác cũng là "một cầu yếu" vậy thì mình sẽ có 1 đoạn code while lồng while như sau:
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ề;
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ề;
}
}
Đoạn code này do mình tự suy nghị ra, mong thầy và các bạn góp ý dùm mình

Nếu thầy đã nói là ko tính trường hợp xe quay đầu ngược trở về thì mình cần thiết gì tính tiếp trường hợp xe quay về đi hướng khác, đi cầu khác nhỉ??? cũng quay lại giống như ban đầu, có 1 cây cầu yếu, có 1 cột đèn thôi. Mình thấy cho thêm trường hợp "while" lồng như bạn nói thì có vẻ hơi dư thừa đó

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

Mình xin bổ sung một vài ví dụ:
1.
Vùng tương tranh là cái bảng trong lớp. Ở 1 thời điểm nhất định chỉ có 1 sinh viên lên thao tác trên đó. Sau khi sinh viên đó thao tác xong thì sinh viện khác tiếp tục được lên bảng thao tác trên bảng tiếp và cứ lần lượt như thế. Cùng một lúc không thể có hai sinh viên cùng thao tác trên bảng...
2.
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Ba
..........(nội dung đơn).............


- Nội dung đơn này phải được đảm bảo tính toàn vẹn, ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
- Nếu vài tiến trình 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 sửa Lê Văn Ba phía trên thành Lê Văn Bá mà chưa kịp sửa Lê Văn Ba phía dưới, trong khi cùng lúc đó P2 lại in ra đoạn văn bản vừa rồi thì kết quả sẽ không nhất quán như sau:

Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Bá
..........(nội dung đơn).............

- Edsger Wybe Dijkstra( 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ó [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).
- Ô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.

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 ngủ tại hàm wait(synch1) do synch1=0; P3 ngủ 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 ngủ 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ẽ ngủ 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ẽ ngủ 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.

Sau khi tham khảo 1 số bài viết của những anh chị khóa trước, mình làm lại câu 2 bài tập về nhà như sau, mong được thầy và các bạn góp ý

Khi tham gia giao thông vào giờ cao điểm. Nếu tất cả mọi người tham gia giao thông đều đi đúng luật, đúng hiệu lệnh(đồng bộ). Thì sẽ tránh được tình trạng kẹt xe và sẽ lưu thông được dễ dàng hơn.

Trình bày khái niệm đoạn tương tranh và giải quyết vấn đề này
-Khái niệm: Đoạn tương tranh là một đoạn mã trong chương trình,điều khiển công việc của tiến trình nhưng đặc biệt ở chỗ nó chứa các lệnh liên quan tới tài nguyên chung với các tiến trình khác (đọc hay sửa nội dung 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).

-Giải quyết vấn đề tương tranh phải thỏa các điều kiện sau:
+ Loại trừ lẫn nhau (Mutual Exclusion): mỗi thời điểm chỉ có một tiến trình vận hành trong đoạn tương tranh.
Vd: Khi bạn A đang lên bảng làm bài thì bạn B không được lên,bạn B phải đợi cho tới khi bạn A xuống thì bạn B mới được lên.
+ Tiến triển (Progress): Không có tiến trình nào phải chờ vô hạn tại Entry Section(Đoạn Đăng nhập) của nó.
Vd: Bạn A và bạn B có thể lên bảng cùng lúc.

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

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

- Đ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.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ:
ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Ba
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 29 tháng 03 năm 2013
Người làm đơn
....(chữ ký)....
Lê Văn Ba


. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:
ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Bàng
. .........(nội dung đơn).............
TP Hồ Chí Minh, ngày 29 tháng 03 năm 2013
Người làm đơn
....(chữ ký)....
Lê Văn Bá

Mỗi tiến trình đều có mức độ ưu tiên, tiến trình nào có mức độ ưu tiên cao hơn sẽ được cấp CPU trước, các tiến trình nào có mức độ ưu tiên bằng nhau thì tiến trình nào đến trước thì sẽ được nhường CPU trước (FCFS). Ngoài ra, mức độ ưu tiên còn được xác định theo nhiều tiêu chí khác nhau.
=> Vậy những tiến trình nào có độ ưu tiên bằng nhau cùng tồn tại, cùng truy cập tài nguyên (khả năng chia sẻ của tài nguyên là có hạn) được gọi là tiến trình tương tranh.
Cấu trúc mã của tiến trình tương tranh
while(1)
{
remainder section //Đoạn còn lại
entry section //Đoạn đăng nhập
critical section //Đoạn tương tranh
exit section //Đoạn đăng xuất
remainder section //Đoạn còn lại
}
Vấn đề tương tranh:
* Loại trừ lẫn nhau: mỗi thời điểm chỉ có một tiến trình nằm trong đoạn tương tranh.
* Phải đảm bảo tiến trình đang truy cập tài nguyên thì tiến trình khác không được truy cập.
* Không để xảy ra tình trạng bế tắc (deadlock) khi hai hoặc nhiều tiến trình khác không thể thực hiện do chờ lẫn nhau.
* Không để xảy ra tình trạng chờ quá lâu mà không đến lượt sử dụng tài nguyên.
Giải quyết:
* Trao đổi thông tin giữa các tiến trình bằng cách chia sẻ vùng nhớ chung hoặc gửi thông điệp.
* Sử dụng các lệnh máy đặc biệt (đèn hiệu) đảm bảo các tiến trình không bị ngắt khi đang truy cập tài nguyên.

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

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

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

NguyenVanSang(I22A) đã 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).

Ví dụ : Khi dùng một tài khoản để đăng nhập Facebook hoặc Y!M trên máy tính A và vẫn giữ tình trạng đăng nhập đó. Rồi ta cũng dùng tài khoản đó để đăng nhập ở máy tính B thì vẫn được nhưng tài khoản sẽ bị đăng xuất ở máy tính A.

Đồng bộ hóa trong sản xuất tiêu thụ
Ví dụ ở một công ty có sản xuất 1 sản phẩm nào đó, có nhà sản xuất và nhà tiêu thụ.Nhà sản xuất khi sản xuất xong sản phẩm sẽ đưa vào kho chứa hàng --> Khi đó nhà tiêu thụ sẽ đưa sản phẩm trong kho hàng đi tiêu thụ. Để hoạt động sản xuất trơn tru, tiến trình trong chu trình sản xuất thì không được xếp sản phẩm khi chưa hoàn chỉnh vào kho chưa hàng và không được để xảy ra việc có 2 nhà sản xuất cùng ghi vào 1 lúc.

bài 2: đồng bộ công việc p1,p2,p3 sao cho p1 trước p2, p2 trước p3.

Giải

Giả sử P1 có mã là S1, P2 có mã là S2, P3 có mã là S3.

Semaphore synch1 = 0;

Semaphore synch2 = 0;

cấu trúc P1:	cấu trúc P1:	cấu trúc P1:
S1	wait(synch1)	wait(synch2)
signal(synch1);	S2	S3
	signal(synch2);

Đoạn tương tranh và loại trừ lẫn nhau hay loại trừ tương hỗ
ví dụ:
ĐƠN XIN VIỆC

Kính gửi:
Tôi tên là: Nguyễn Văn A
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 13 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Nguyễn Văn A

- Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là 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 B, 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 C, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:

ĐƠN XIN VIỆC

Kính gửi:
Tôi tên là: Nguyễn Văn B
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 13 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Nguyễn Văn C

Giả sử P1 có mã là S1, P2 có mã là S2, P3 có mã là S3.

Semaphore synch1 = 0;

Semaphore synch2 = 0;

Bài 3: P1 trước P2,P3

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	wait(synch1)	wait(synch2)
signal(synch1)	S2	S3
signal(synch2)

Bài 4: P1,P2 trước P3.

cấu trúc P1:	cấu trúc P2:	cấu trúc P3:
S1	S2	wait(synch1)
signal(synch1)	signal(synch2)	wait(synch2)

Đồng bộ công việc sao cho 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.

Mục đích của đồng bộ hóa công việc các tiến trình
- Đồng bộ hóa công việc của tiến trình cũng như đồng bộ hóa công việc của luồng.
- Đồng bộ làm cho các tiến trình làm việc có trật tự không hổn loạn.
- Đảm bảo các tiến trình làm việc có chờ đợ nhau 1 cách logic.
* Vd về tính nhất quán của tài nguyên dùng chung: các sv là các luồng, cái bảng là tài nguyên dùng chung, các sv viết thông tin lên bảng, thì thông tin đó được chia sẽ cho tất cả các sv.
* Vd về vi phạm tính đúng đắn và nhất quán: là 2 sv cùng sửa nội dung cái bảng cùng 1 lúc, 2 sv đó làm việc cùng 1 lúc thì nội dung sẽ k nhất quán -> không đồng bộ.
* vd về tính đồng bộ: các bạn được thầy gọi lên nộp bài theo mục quản, thầy gọi 1 lượt 5 bạn và làn lượt nộp bài, ai đến trc thì nộp trc 1 cách có thứ tự.

Các bạn góp ý vài dòng nào

KN: Đoạn tương tranh là đoạn mã trong chương trình điều khiển công việc của tiến trình nhưng đặc biệt ở chổ nó chứa các lệnh liên quan đến tài nguyên dùng chung, với các tiến trình khác (đọc hay sửa nội dung, tài nguyên dùng chung).

Vấn đề đoạn tương tranh(critical-section Problem)

-giả sứ có n tiến trình(P0,P1, P2...Pn). Mỗi tiến trình có 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 ĐTT của nó thì không có tiến trình 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à 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).

Giải quyết vấn đề tương tranh phải thỏa các điều kiện sau:

-Loại trừ lẫn nhau (Mutual Exclusion): Mỗi thời điểm chỉ có 1 tiến trình vận hành trong đoạn tương tranh.

-Tiến triển(Progress). Không có tiến trình nào phải chờ vô hạn tại đoạn Đăng nhập của nó.