Thảo luận Bài 7

Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một lúc trong hệ thống:

- Loại trừ hỗ tương: ít nhất một tài nguyên phải được giữ trong chế độ không chia sẻ; nghĩa là, chỉ một quá trình tại cùng một thời điểm có thể sử dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình yêu cầu phải tạm dừngcho đến khi tài nguyên được giải phóng.

- Giữ và chờ cấp thêm tài nguyên: quá trình phải đang giữ ít nhất một tài nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi quá trình khác.

- Không đòi lại tài nguyên từ quá trình đang giữ chúng: Các tài nguyên không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bởi quá trình đanggiữ nó, sau khi quá trình đó hoàn thành tác vụ.

-Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá trình {P0,P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1, P1đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ tài nguyên đang được giữ bởi quá trình P0.1

Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlock xảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiệnkhông hoàn toàn độc lập.

Khái niệm đèn hiệu :

- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}
signal (semaphore S)
{
S ++; // Tăng S lên 1
}

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

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

1. Giải quyết vấn đề VTT: Bằng đèn hiệu nhị phân
- Sử dụng đèn hiệu mutex với trạng thái ban đầu =1

+ Mã của tiến trình Pi bây giờ có cấu trúc:
Code:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) // (Đèn hiệu nhị phân)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
=> Loại trừ tính tương tranh, đảm bảo trong 1 thời điểm chỉ có 1 tiến trình ở đoạn tương tranh.

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

Giả sử P1 có mã S1,P2 có mã S2,cần tổ chức sao cho S2 chỉ thi hành sau S1.
+Ta dùng đèn hiệu sau:
semaphore synch = 0;
Cấu trúc P1:
S1
signal (synch) ;
Cấu trúc P2:
wait(synch);
S2

Giống nhau:
Cả mutex và semaphore đều được sử dụng để quản lý việc truy xuất của những process tới 1 tài nguyên (thường là vùng nhớ) được shared bởi các process này.

Khác nhau:
- Semaphore:
+ Tại một thời điểm có nhiều hơn 1 process được truy cập vào tài nguyên dùng chung được semaphore quản lý. (số lượng process này được giới hạn ở một số lượng nhất định-một số hữu hạn process được truy cập vào vùng tài nguyên dùng chung này).
- Mutex:
+ Tại một thời điểm chỉ có được 1 process được truy cập vào tài nguyên này, nếu tài nguyên này đã được chiếm giữ thì process khác phải chờ để tới lượt.
+ Khi tài nguyên này được "chiếm giữ" bởi 1 process thì mutex này sẽ được thiết lập trạng thái là false để các process khác không được action vào.

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 dung 1:
Xử lý 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

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

Thuật ngữ: Critical section là Đoạn tương tranh (đoạn mã găng, đoạn mã tới hạn)
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.
Đoạn tương tranh thường nằm giữa Entry Section (Đoạn đăng nhập, thường dùng wait(mutex)) và Exit Section (Đoạn đăng xuất, thường dùng signal(mutex)).

Vùng tranh chấp: là vùng chứa các biến dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ: Những chiếc xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp". Chiếc xe thứ nhất đang qua cầu thì đèn đang đỏ, các xe tiếp theo đứng chờ cho đến khi xe thứ nhất qua bên kia cầu, đèn xanh bật lên thì thứ hai tiếp tục qua cầu.

Code:

typedef int semaphore;
Semaphore mutex=1;
while (1)
{
  remainder section
  wait (mutex);
    critical section
  signal (mutex);
  remainder section
}

Ví dụ : Đoạn mã sau điều khiển hành vi của Xe_i trong bài toán "Xe qua cầu yếu":

Code:


Semaphore mutex=1; // Giá trị ban đầu của đèn mutex bằng 1 (màu Xanh)
while(1)
{
  Đi đến cầu;
  wait(mutex); // Chờ đến khi đèn Xanh và chuyển về Đỏ luôn
      Lên cầu;
      Qua cầu;
  signal(mutex); // Chuyển mutex từ Đỏ sang Xanh
  Đi tiếp;
  Quay về nhà theo đường khác;
}


* Lý do:
- Đả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ụ minh họa: Một trung tâm tin học chỉ có 1 phòng lab (tài nguyên dùng chung), lớp nào có ca học trước sẽ được vào phòng lab, các lớp có ca học sau phải chờ lớp có ca học trước hết giờ mới được vào phòng lab.

NguyenThiNgocPhuoc(122A) đã viết:* Lý do:
- Đả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ụ minh họa: Một trung tâm tin học chỉ có 1 phòng lab (tài nguyên dùng chung), lớp nào có ca học trước sẽ được vào phòng lab, các lớp có ca học sau phải chờ lớp có ca học trước hết giờ mới được vào phòng lab.

Ngoài ra nó còn đảm bảo cho các tiến trình hoạt động trên một tài nguyên dùng chung mà không bị các tiến trình khác xâm phạm

Đồng bộ hóa tiến trình để giải quyết vấn đề dùng chung tài nguyên. Đảm bảo tính trước sau như một của tài nguyên.

- Tiến trình có thể lấy dữ liệu vọi vàng nên phải cân nhắc tính đúng đắn của dữ liệu trước khi lấy về.
- Đảm bảo các luồng có sự phối hợp "nhịp nhàng".

Nếu điều phối được các tính tiến trình hợp lý sẽ tránh được tình trạng kẹt tiến trình (deadlock).
Đèn hiệu có thể coi như một một "thiết bị" để giải quyết tranh chấp, trong máy tính, nó có thể là một biến.
- Đảm bảo mỗi thời điểm chỉ có một biến dùng chung (truy xuất tài nguyên).

- Đoạn tương tranh là đoạn mã trong chương trình điều phối để điều khiển công việc của tiến trình. Nhưng điểm đặc biệt ở đây là nó chỉ chứa các tài nguyên dùng chung với các tiến trình khác (đọc hoặc chỉnh sửa nội dung tài nguyên dùng chung).

Ví dụ: Trong bài toán sản xuất và tiêu thụ. Khi thực thực hiện lệnh in và lệnh count trong đoạn mã Producer đều ảnh hưởng và tranh chấp đến các lệnh khác. Vì bản thân các lệnh này phải truy xuất đến tài nguyên dùng chung. Cụ thể ở đây là bộ đệm Buffer_size.
Không chỉ riêng Producer mà ngay cả Consumer sẽ có những vùng tương tranh khác; cũng đọc, ghi, thay đổi dữ liệu trên các tài nguyên hệ thống. Đây cũng chính là những đoạn mã tương tranh liên quan.

TruongNhuNgoc (I22A) đã viết:Giống nhau:
Cả mutex và semaphore đều được sử dụng để quản lý việc truy xuất của những process tới 1 tài nguyên (thường là vùng nhớ) được shared bởi các process này.

Khác nhau:
- Semaphore:
+ Tại một thời điểm có nhiều hơn 1 process được truy cập vào tài nguyên dùng chung được semaphore quản lý. (số lượng process này được giới hạn ở một số lượng nhất định-một số hữu hạn process được truy cập vào vùng tài nguyên dùng chung này).
- Mutex:
+ Tại một thời điểm chỉ có được 1 process được truy cập vào tài nguyên này, nếu tài nguyên này đã được chiếm giữ thì process khác phải chờ để tới lượt.
+ Khi tài nguyên này được "chiếm giữ" bởi 1 process thì mutex này sẽ được thiết lập trạng thái là false để các process khác không được action vào.

cám ơn bạn mình hiểu được 1 tí rùi đó

#include
#include
#include
#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
char s[BUFFER_SIZE];
int in=0;
int out=0;
int nextProduced=1;
HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec; //Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);// vào đoạn tương tranh
//…Sắp sản phẩm vào Buffer
buffer[in]=nextProduced++;
switch ((int)p){
case 1:
s[in]=’P’;
break;
case 2:
s[in]=’p’;
break;
default:
s[in]=’S’;
};
in=(in+1)%BUFFER_SIZE;
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);// rời khỏi đoạn tương tranh
SuspendThread(GetCurrentThread());
}
}

void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec); // vào đoạn tương tranh
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec); // rời khỏi đoạn tương tranh
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}
- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh nhằm đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Xét một giải pháp semaphore đúng cho bài toán Dining philosophers :
#define N 5
#define LEFT(i-1)%N
#define RIGHT(i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
int state[N];
semaphore mutex = 1;
semaphore s[N];//gan tri ban dau =0
//tiến trình mô phỏng triết gia thứ i
void philosopher( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
think(); // Suy nghĩ
take_forks(i); // yêu cầu đến khi có đủ 2 nĩa
eat(); // yum-yum, spaghetti
put_forks(i); // đặt cả 2 nĩa lên bàn lại
}
}
//kiểm tra điều kiện được ăn
void test ( int i) // i là triết gia thứ i : 0..N-1
{
if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!= EATING)
{
state[i] = EATING;
up(s[i]);
}
}
//yêu cầu lấy 2 nĩa
void take_forks ( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
down(mutex); // vào miền găng
state[i] = HUNGRY; // ghi nhận triết gia i đã đói
test(i); // cố gắng lấy 2 nĩa
up(mutex); // ra khỏi miền găng
down(s[i]); // chờ nếu không có đủ 2 nĩa
}
}
//đặt 2 nĩa xuóng
void put_forks ( int i) // i là triết gia thứ i : 0..N-1
{
while (TRUE)
{
down(mutex); // vào miền găng
state[i] = THINKING; // ghi nhận triết gia i ăn xong
test(LEFT); // kiểm tra ngườii bên trái đã có thể ăn?
test(RIGHT); // kiểm tra ngmái bên phải đã có thể ăn?
up(mutex); // ra khỏi miền găng
}
}


a)Tại sao phải đặt state[i] = HUNGRY trong take_forks ?
b)Giả sử trong put_forks, lËnh gán state[i] = THINKING đmợc thực hiện sau hai lệnh test(LEFT),
test(RIGHT). Điều này ảnh hưởng thế nào đến giải pháp cho 3 triết gia? Cho 100 triết gia?

Đồ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, đảm bảo yêu cầu của người dùng, tránh được hiện tượng Deadlock (kẹt tiến trình).

VD: trong thư viện của trường chỉ có 1 máy tính duy nhất (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 thì phải đợi sinh viên A xong việc thì mới được dùng.

Đoạn tương tranh: xét một hệ có n tiến trình P0, P1, ..., Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã đó là đoạn tương tranh.
Tính loại trừ lẫn nhau 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à/hoặc thay đổi tài nguyên dùng chung.
Các tiến trình tương tranh có cấu trúc gồm: Đoặn đăng nhập, Đoạn trương tranh, Đoạn đăng xuất và Đoạn còn lại.
Cách giải quyết vấn đề:
- 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 của nó.

Đồng bộ hóa tiến trình là đồng bộ hóa các luồng ở bên trong của tiến trình, là biết cách điều khiển các luồng cho chúng ăn nhập với nhau có trước có sau để đảm bảo tính nhất quán và tính toàn vẹn của tài nguyên dùng chung,và đảm bảo theo yêu cầu của người dùng.

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

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

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}

- Biến semEmpty dùng để chứa mục quản của đèn hiệu quản lý số vùng trống trong bộ đệm.
- Biến semFull dùng để chứa mục quản của đèn hiệu quản lý số sản phẩm trong bộ đệm.
- CritSec là đối tượng đèn hiệu kiểu mutex dùng để bảo vệ đoạn tương tranh để đảm bảo tính loại trừ lẫn nhau trong công việc của các tiến trình với tài nguyên dùng chung.

Khái niệm đèn hiệu :

- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S)
{
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}
signal (semaphore S)
{
S ++; // Tăng S lên 1
}

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

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

1. Giải quyết vấn đề VTT: Bằng đèn hiệu nhị phân
- Sử dụng đèn hiệu mutex với trạng thái ban đầu =1

+ Mã của tiến trình Pi bây giờ có cấu trúc:
Code:
typedef int semaphore;
semaphore mutex=1; // Binary Semaphore
while (1) // (Đèn hiệu nhị phân)
{
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}
=> Loại trừ tính tương tranh, đảm bảo trong 1 thời điểm chỉ có 1 tiến trình ở đoạn tương tranh.

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

Giả sử P1 có mã S1,P2 có mã S2,cần tổ chức sao cho S2 chỉ thi hành sau S1.
+Ta dùng đèn hiệu sau:
semaphore synch = 0;
Cấu trúc P1:
S1
signal (synch) ;
Cấu trúc P2:
wait(synch);
S2

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

PhamThiThao (I22B) đã viết:
Tại sao giá trị ban đầu của SemEmpty = 10 và giá trị ban đầu của SemFull = 0
tại sao vậy các bạn

- SemEmpty: là biến dùng để quản lý số lượng khoang trống trong bộ đệm
- SemFull: là biến dùng để quản lý số lượng khoang đã có sản phẩm trong bộ đệm
- BUFFER_SIZE = 10 : mặc định bộ đệm này chỉ có 10 khoang trống.
Nguyên nhân giá trị ban đầu của SemEmpty = 10 và SemFull = 0 là khi bắt đầu hoạt động thì trong bộ đệm chưa có sản phẩm nào hết nên số khoang trống (SemEmpty ) là 10 và số khoang có sản phẩm(SemFull ) là 0.
vd:
Khi trong bộ đệm có 1 sản phẩm, lúc này SemEmpty = 9 và SemFull = 1
Khi trong bộ đệm có 2 sản phẩm, lúc này SemEmpty = 8 và SemFull = 2

Admin
- semEmpty và semFull là các biến kiểu HANDLE nên chứa Mục quản của các đèn tương ứng !
- Giá trị và Mục quản của đèn là 2 khái niệm khác nhau !

HoBaoQuoc_I22B đã viết:

PhamThiThao (I22B) đã viết:tại sao vậy các bạn

Theo mình được biết:
semEmpty =10 là vì semEmpty dùng để chứa mục quản của đèn hiệu và quản lý vùng trống trong bộ đệm nên giá trị nó bằng 10
semFull=0 là vì dùng để chứa sản phẩm trong bộ đệm nên giá trị ban đầu nó sẽ bằng 0.
Mong các bạn và thầy góp ý thêm...

Theo mình hiểu thì semEmpty, semFull không phải mục quản của đèn hiệu đâu bạn

CÂU 7.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, cho vd minh họa ?

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

CÂU 7.2 : Trình bày vấn đề đoạn tương tranh và cách giải quyết nó ( đoạn tương tranh là 1 đoạn mã trong trình điều khiển công việc của các tiến trình – nhưng đb ở chỗ nó là 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 lại tài nguyên dùng chung) ?

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.

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
CÂU 7.3 : Trình bày khái niệm đèn hiệu (Semaphore) ?
Định nghĩa kiểu Đè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.

wait (semaphore S)
{
while ( S <= 0 );
S --;
}

signal (semaphore S)
{
S ++;
}

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

Đè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
CÂU 7.4 : Phát biểu bài toán sản xuất – tiêu thụ với thuật giải đồng bộ hóa công việc các tiến trình bằng 3 đèn hiệu (2 chính 1 phụ) ?

- Tiến trình sản xuất (Producer) tạo ra dòng thông tin để tiến trình tiêu thụ (Consumer) sử dụng.
- Ví dụ: Compiler và Assembler vừa là nhà sản xuất vừa là nhà tiêu thụ. Compiler tạo ra mã dùng cho Assembler, tiếp theo Assembler sản sinh mã máy làm đầu vào cho Loader hoặc Linkage Editor.
- Phát biểu bài toán: Bộ nhớ đệm Buffer bao gồm một số hữu hạn các khoang chứa (Items). Producer lần lượt đưa các sản phẩm S1, S2,…vào các khoang của Buffer. Consumer lấy sản phẩm ra theo đúng thứ tự. Công việc của các tiến trình phải đồng bộ với nhau: không đưa ra sản phẩm khi hết chỗ trống, không lấy được sản phẩm khi chưa có.
- Thuật giải đồng bộ hoá bằng 3 đèn hiệu: semFull (quản lý số sản phẩm có trong bộ đệm, giá trị ban đầu bằng 0), semEmpty (quản lý số khoang còn trống, giá trị ban đầu bằng số khoang của bộ đệm) và Mutex (đảm bảo tính loại trừ tương hỗ, nghĩa là mỗi thời điểm chỉ có 1 tiến trình sản xuất hay tiêu thụ được truy cập/cập nhật tài nguyên dùng chung, giá trị ban đầu bằng 1).
o Thuật giải cho Producer:
wait(semEmpty);
wait(Mutex);
// Đưa sản phẩm vào Buffer
..........................
signal(semFull);
signal(Mutex);
o Thuật giải cho Consumer:
wait(semFull);
wait(Mutex);
// Lấy sản phẩm từ Buffer
..........................
signal(semEmpty);
signal(Mutex);
Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0.
– Dữ liệu chia sẻ:
SEMAPHORE full, empty, mutex;
– Khởi tạo:
full = 0;
empty = BUFFER_SIZE;
mutex = 1;

Khái niệm đ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.

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

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

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

Mục đích của đồng bộ hóa tiến trình-ví dụ
- 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ụ:
-Chương trình dowload phim được cài đặt download 3 tập cùng 1 lúc theo thứ tự thì muốn download tập 4 phải chờ download xong 3 tập trước mới được down.