Thảo luận Bài 7

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

Mục đích của đồng bộ hoá công việc các tiến trình là đảm bảo Tính nhất quán của tài nguyêndùng chung và Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).

Trình bày những lý do đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa.
- 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 chung
+Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )

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 là 1 đoạn mã trong chương trình của HĐH. Đoạn mã có tính chất khi thực hiện các lệnh trong đoạn tương tranh thì các đoạn đó có thể tác động đến tài nguyên dùng chung, biến dùng chung (count ++, count --), có thể sửa chữa những kết quả trong tài nguyên.
- "Loại trừ lẫn nhau" hay còn gọi là đoạn tương hỗ. Chỉ có 1 tiến trìnhđược rơi vào đoạn tương tranh mà thôi, có 1 tiến trình khác muốn tương tranh thì phải chờ HĐH cho phép.

Admin
Đoạn tương tranh là 1 đoạn mã trong chương trình của tiến trình người dùng (không phải của HĐH).

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

- Đè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 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.
Tài nguyên dùng chung trong bài toán sản xuất tiêu thụ là Buffer, các biến In,Out
Ví dụ BUFFER_SIZE 10
Tài nguyên dùng chung là vùng nhớ để chúng trao đổi thông tin với nhau.
Tránh được hiện tượng Deadlock.
Trở lại vấn đề bài toán sản xuất – tiêu thụ với giải pháp mới dùng biến đếm Count.
Cấu trúc bộ nhớ đệm chung.
#define BUFFER_SIZE 10
typedef struct {
. . . // Mô tả các thành phần của 1 khoang chứa
} item;
item buffer [BUFFER_SIZE]; // Bộ nhớ đệm.
int in = 0; // Con trỏ tới vị trí trống kế kiếp.
int out = 0; // Con trỏ tới vị trí lấy tiếp theo.
int count= 0;// Đếm số sản phẩm có trong Buffer.

Admin
"Chế biến" không trọn vẹn !

Xét hai process: P1 và P2
Yêu cầu: lệnh S1 trong P1 cần được thực thi trước lệnh S2 trong P2
Định nghĩa semaphore “synch” dùng đồng bộ
Khởi động semaphore:synch.value= 0
Để đồng bộ hoạt động theo yêu cầu, P1 phải định nghĩa như sau:
S1;
signal(synch);
Và P2 định nghĩa như sau:
wait(synch);
S2;

-- Đả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ụ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 chung và Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )
+ Đả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) .
VD1: 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

CountThread trong Linux


#include
#include

const int numThreads = 10;
const int iterations = 1000000;

int count;

void *CountThread (void *iterations){
int n, i, x;

n=(int) iterations;

for (i=0; i x=count;
x++;
count=x;
}
}

main(){
pthread_t handles[numThreads];
int i;

count=0;

// Tạo các luồng
for (i=0; i CountThread, (void *)iterations);

// Chờ các luồng kết thúc
for (i=0; i
printf("* Giá trị của Count là:%d \n", count);
getchar();
}

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

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

- Có 5 triết gia ngồi ăn trên 1 bàn tròn.
- Mỗi người cần 2 chiếc đũa để ăn.
- Trên bàn, chỉ có 5 chiếc đũa xếp xoay vòng và xen kẽ mỗi người.
- Người nào có đủ 2 chiếc đũa sẽ sử dụng và ăn được.

=> Bài toán này minh hoạ sự khó khăn trong việc phân phối tài nguyên giữa các process sao cho không xả ra deadlock và starvation.

Đoạn tương tranh là doạn mã cho tiến trình mà khi thực hiện nó truy cập, tác động và thay đổi được tài nguyên dùng chung.
Còn đoạn mã ko truy cập, tác động và thay đổi được tài nguyên dùng chung là đoạn còn lại

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.

Tên đầy đủ của ông là Alan Mathison Turing (sinh ngày 23/6/1912 – mất ngày 7/6/1954):
Ông 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 đã công thức hóa khái niệm thuật toán và tính toán với máy Turing, đồng thời đưa ra phiên bản của "Turing", mà ngày nay được đông đảo công chúng chấp nhận, về luận đề Church-Turing, một luận đề nói rằng bất cứ mô hình tính toán thiết thực nào đều có khả năng thấp hơn hoặc bằng khả năng của một máy Turing.

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

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

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

Admin
Đã giảng trên lớp: "Cái bảng" không phải là Vùng (hay Đoạn) Tương tranh, mà là "Vùng Tranh chấp" !

hoanggiangI12C đã 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ụ 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 !

Mình xin bổ sung một vd:

- 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 Tám, 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:

Edsger Wybe Dijkstra (người Hà Lan) phát minh ra khái niệm semaphore trong khoa học máy tính vào năm 1972
Semaphore được sử dụng lần đầu tiên trong cuốn sách “The operating system” của ông Edsger Wybe Dijkstra (1930-2002)

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)

Edsger Wybe Dijkstra (sinh ngày 11/5/1930 tại Rotterdam – mất ngày 6/8/2002 tại Nuenen):
Ô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). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).

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

Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.

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

Giả sử có n tiến trình . 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ỗ 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 và thay đổi tài nguyên chung.
- Các tiến trình có cấu trúc mã bao gồm :

Đoạn đăng nhập
Đoạn tương tranh
Đoạn đăng xuất
Đoạn còn lại

Vậy để giải quyết vấn đề này thì phải thỏa các ĐK sau :

Loại trừ lẫn nhau : 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 : Không có tiến trình nào phải chờ vô hạn tại Đoạn đăng nhập

Giới thiệu ứng dụng thứ nhất của đèn hiệu để đảm bảo tính loại trừ tương hổ trong công việc của các tiến trình đồng hành song song.
Đoạn tương tranh là một đoạn mã của tiến trình mà khi thực hiện nó truy cập và tác động đến tài nguyên dùng chung