Re: Thảo luận Bài 7

nguyenthanhphongHC11TH2A 16/4/2012, 16:57

NguyenHongHaiI12C đã viết:

Thuật giải cho Xe_i:
While(1)
{
Đi đến cầu;
Wait (mutex);
lên cầu;
qua cầu;
Signal(mutex);
đi tiếp;
quay về theo cầu khác;
}

Admin
- Vẽ được hình là tốt !
- Tên đèn hiệu là mutex (không phải là minutes).
- Không cho biết tại sao mutex có tới 3 màu ?
- Cần giải thích cụ thể công việc đoạn mã trên ! (chỉ đưa ra code là không đủ thuyết phục !)

Mình xin góp ý giải thích doạn code:

Đầu tiên xe đi đến cầu. nếu đen mutex màu xanh tức là chưa có xe nào trên cầu ( chưa có tiến trình nào bước vào đoạn tương tranh ) thì xe được phép lên cầu và bước vào đoạn tương tranh, lúc này đèn mutex chuyễn sang đỏ. Trong lúc xe A đang qua cầu nếu có xe khác tới cầu gặp đèn đỏ thì nó phải ngủ chờ trước đèn tín hiệu. khi xe A qua cầu và rời khỏi cầu thì đèn mutex chuyển sang xanh báo hiệu xe kế tiếp có thể qua cầu. Lúc này HDH sẽ đánh thức một xe đang ngủ dậy để qua cầu. Cứ như thế các xe khác tiếp tục lên cầu và qua cầu.

Admin
- Giải thích tốt, nhưng chỉ đúng cho trường hợp Mutex có 2 màu Xanh-Đỏ. Chú ý: Trạng thái ban đầu của Mutex là Xanh.
- Cần giải thích lại cho trường hợp Mutex có 3 màu: Xanh lá cây (mã 2, trạng thái ban đầu) - Xanh da trời (mã 1) - Đỏ (mã 0) !

LeThanhTung (I11C) 16/4/2012, 21:31

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

lethanhsang_I12A 16/4/2012, 21:51

nguyenthanhphongHC11TH2A đã viết:
NguyenHongHaiI12C đã viết:

Thuật giải cho Xe_i:
While(1)
{
Đi đến cầu;
Wait (mutex);
lên cầu;
qua cầu;
Signal(mutex);
đi tiếp;
quay về theo cầu khác;
}

Admin
- Vẽ được hình là tốt !
- Tên đèn hiệu là mutex (không phải là minutes).
- Không cho biết tại sao mutex có tới 3 màu ?
- Cần giải thích cụ thể công việc đoạn mã trên ! (chỉ đưa ra code là không đủ thuyết phục !)
Mình xin góp ý giải thích doạn code:

Đầu tiên xe đi đến cầu. nếu đen mutex màu xanh tức là chưa có xe nào trên cầu ( chưa có tiến trình nào bước vào đoạn tương tranh ) thì xe được phép lên cầu và bước vào đoạn tương tranh, lúc này đèn mutex chuyễn sang đỏ. Trong lúc xe A đang qua cầu nếu có xe khác tới cầu gặp đèn đỏ thì nó phải ngủ chờ trước đèn tín hiệu. khi xe A qua cầu và rời khỏi cầu thì đèn mutex chuyển sang xanh báo hiệu xe kế tiếp có thể qua cầu. Lúc này HDH sẽ đánh thức một xe đang ngủ dậy để qua cầu. Cứ như thế các xe khác tiếp tục lên cầu và qua cầu.

Admin
- Giải thích tốt, nhưng chỉ đúng cho trường hợp Mutex có 2 màu Xanh-Đỏ. Chú ý: Trạng thái ban đầu của Mutex là Xanh.
- Cần giải thích lại cho trường hợp Mutex có 3 màu: Xanh lá cây (mã 2, trạng thái ban đầu) - Xanh da trời (mã 1) - Đỏ (mã 0) !

Đầu tiên xe đi đến cầu. nếu đen mutex màu xanh lá (mã 2) tức là chưa có xe nào trên cầu thì xe được phép lên cầu , lúc này đèn mutex chuyễn sang xanh da trời (mã 1). Trong lúc xe A đang qua cầu nếu xe B đến thì xe B được phép lên cầu, lúc này đèn mutex chuyễn sang màu đỏ (mã 0).Khi xe C đến có 3 trường hợp xảy ra:

TH1: xe A đã qua cầu và rời khỏi cầu, xe B vẫn trên cầu thì đèn mutex chuyển sang màu xanh da trời (mã 1), xe C được phép lên cầu khi đó đèn mutex chuyễn sang màu đỏ (mã 0).
TH2: Cả xe A và xe B đều đã qua cầu và rời khỏi cầu thì đèn mutex chuyễn sang màu xanh lá (mã 2), xe C được lên cầu và đèn mutex chuyễn sang màu xanh da trời (mã 1).
TH3: Cả 2 xe A và xe B đều còn trên cầu thì đen mutex vẫn đỏ (mã 0) xe C tới cầu gặp đèn đỏ thì nó phải ngủ chờ trước đèn tín hiệu. khi xảy ra TH1 hoặc TH2 thì đèn mutex chuyển sang xanh báo hiệu xe kế tiếp có thể qua cầu. Lúc này HDH sẽ đánh thức một xe đang ngủ dậy để qua cầu. Cứ như thế các xe khác tiếp tục lên cầu và qua cầu.

nguyen_tuan_phat_I12A 16/4/2012, 22:32

Semaphore hay tạm gọi là truyền tin thị giác (optical telegraph) là một công cụ dùng để truyền tin qua phương tiện tín hiệu nhìn thấy được với tháp cao cùng với các phiến quay quanh trục (pivoting blades) hay các cánh quạt (paddles), các cửa chớp (shutters) trong một hình thể ma trận (matrix), hoặc là các cờ cầm tay...Thông tin được mã hóa theo vị trí của các thành phần cơ học; nó được đọc khi các phiến hoặc cờ nằm ở một vị trí đã ấn định.

Trong thời hiện đại, nó thường được ám chỉ đến một hệ thống truyền tín hiệu bằng hai lá cờ cầm tay. Hệ thống semaphore dùng hai cán cờ ngắn có cờ hình vuông là một trong các phần cơ bản của kỹ thuật Hướng đạo.

Những hình thức tín hiệu thị giác khác còn có cờ hiệu hàng hải, đèn hiệu, và gương hiệu.

Semaphore ra đời trước điện tín. Chúng nhanh hơn người đưa tin đi bằng ngựa trên một quãng đường xa, nhưng phí tổn nhiều và ít được bảo mật hơn điện tín mà thay thế nó sau đó. Khoảng cách mà một tín hiệu thị giác có thể truyền đi bị hạn chế bởi địa hình và thời tiết, vì vậy đa số các phương tiện truyền tín hiệu thị giác trong thực tế thường sử dụng nhiều trạm tiếp vận để nối liên lạc những khoảng cách xa hơn.

Hệ thống semaphore mới hơn dùng hai cán cờ ngắn có cờ hình vuông. Một người cầm cờ giữ chúng ở các vị trí khác nhau để truyền đi các mẫu tự và các số. Người cầm cờ giữ mỗi cờ trong mỗi tay, và đưa mỗi cánh tay của mình ở một trong 7 vị trí, các vị trí kế tiếp nhau cách nhau một góc 45 độ. Trừ khi ở vị trí nghỉ, hai cờ không thể chồng lên nhau. Màu cờ thì khác nhau dựa vào tín hiệu được truyền đi ở trên biển hay trên bờ. Màu đỏ và vàng cho cờ dùng ở biển trong khi màu trắng và xanh dương được dùng trên bờ.

TranBinhCongLuanI12A 16/4/2012, 23:06

Semaphore: Được Dijkstra đề xuất vào năm 1965.
Semaphore có thể dùng để giải quyết vấn đề truy xuất độc quyền hay tổ chức phối hợp giữa các tiến trình.
Một semaphore s là một biến có các thuộc tính:
1. Một giá trị nguyên dương
2. Một hàng đợi lưu danh sách các tiết trình đang bị khóa(chờ) trên samaphore
3. Chỉ có hai thao tác đuocjw định nghĩa trên semaphore
- Down(s): giảm giá trị của semaphore đi 1 đơn vị. Nếu semaphore e(s)>0 và tiếp tục xử lý. Ngược lại, nếu e(s) <=0 tiến trình phải chờ đến khi e(s)>0
- Up(s): tăng giá trị semaphore lên 1 đơn vị. Nếu có một hoặc nhiều tiến trình đang chờ trên semaphore s, bị khóa bởi thao tác down, thì hệ thống sẽ chọn một trong các tiến trình này để kết thúc thao tác Down và cho tiếp tục xử lý.

TranBinhCongLuanI12A 16/4/2012, 23:42

- Hai tiết trình cùng chia sẻ một bộ đệm có kích thước giới hạn. Một trong 2 tiến trình sẽ đóng vai trò là nhà sản xuất, tiến trình còn lại sẽ là nhà tiêu thụ, lấy dữ liệu từ bộ đệm ra để xử lý
- Để đồng bộ hóa hoạt động, cả 2 tiến trình phải tuân thủ các yêu cầu sau:
+ Tiến trình sản xuất không được ghi dữ liệu vào bộ đệm đã đầy
+ Tiến trình tiêu thụ không được đọc dữ liệu ở bộ đệm trống
+ Hai tiến trình sản xuất và tiêu thụ không được thao tác trên bộ đệm cùng 1 lúc
- Giải thuật Semaphore:

BufferSize = 3;// Giới hạn của bộ đệm
semaphore mutex = 1;// Kiểm soát truy xuất độc quyền
semaphore empty = BufferSize;//số chỗ trống
semaphore full = 0;//số chỗ đầy

Producer()
{
int item;
while(true)
{
produce_item(&item);// tạo dữ liệu mới
down(empty); // giảm số chỗ trống
down(mutex); // báo hiệu vào miền găng
enter_item(item); // đặt dữ liệu vào bộ đệm
up(empty); // ra khỏi miền găng
up(full); // tăng số chỗ đầy
}
}

Comsumer()
{
int item;
while(true)
{

down(full); // giảm số chỗ đầy
down(mutex); // báo hiệu vào miền găng
remove_item(item) // lấy dữ liệu từ bộ đệm
up(mutex); // ra khỏi miền găng
up(empty); // tăng số chỗ trống
comsumer_item(item);
}
}

lethianhnhat_I12A 17/4/2012, 07:24

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.

lethianhnhat_I12A 17/4/2012, 07:34

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

Ví dụ minh họa :

ĐƠ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 5 tháng 5 năm 2011
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 5 tháng 5 năm 2011
Người làm đơn
....(chữ ký)....
Lê Văn Bá

lethianhnhat_I12A 17/4/2012, 07:37

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

PhamQuangHien_I12A 17/4/2012, 09:19

Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây:
Yêu cầu độc quyền truy xuất (Mutual exclusion)
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lượng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:
• Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.
Yêu cầu phối hợp (Synchronization)
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình
ví dụ: một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó …

PhamQuangHien_I12A 17/4/2012, 10:13

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

Ví dụ về đoạn tương tranh
1/ Người lái xe qua cầu:
Semaphore s=1; // 0 đèn đỏ, 1 đèn xanh
Wait (s);
Lên cầu; // đoạn tương tranh
Qua cầu // đoạn tương tranh
Signal (s);

2/ Sản xuất-Tiêu thụ:
- Các đèn hiệu chung:
Semaphore semEmpty=10, semFull=0;
Semaphore critSec=1;
- Producer:
wait (semEmpty);
wait (critSec); // đoạn đăng nhập
đưa sản phẩm vào bộ đệm // đoạn tương tranh
signal (semFull); // đoạn tương tranh
signal (critSec); // đoạn đăng xuất

- Consumer:
wait (semFull);
wait (critSec); // đoạn đăng nhập
lấy sản phẩm ra khỏi bộ đệm // đoạn tương tranh
signal (semEmpty); // đoạn tương tranh
signal (critSec); // đoạn đăng xuất

DaoQuangTri38(I12A) 17/4/2012, 10:43

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

huynhthao.hc11th2a 17/4/2012, 11:35

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

vấn đề và cấu trúc mã của đoạn tương tranh

- Đ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 .
Ví dụ:
Code:
While(1)
{
Remainder section
Entry section // các tiến trình(1 lệnh hoặc chuỗi lệnh) được chờ tại đây.
Critical section //vùng tương tranh
Exit section
Remainder section
}

PhamDucPhuong(I12A) 17/4/2012, 22:10

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

VoTrongQuyet-I12A 17/4/2012, 22:28

Thiết kế đèn tín hiệu cho 1 xe qua cầu
while (1)
{/*tạo sản phẩm trong nextProduced*/
while (counter==BUFFER_SIZE); /*không làm gì cả*/
buffer[in] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;
counter++;
}

while (1){
while (counter == 0) ; /*không làm gì cả*/
nextConsumed = buffer[out];
out = ( out + 1 ) % BUFFER_SIZE;
counter--;

Câu 3: Trình bày ứng dụng thứ 2 của đè hiệu để đảm bảo được đúng thứ tự cần thiết trong công việc của các tiến trình:
Semaphore Synch = 0.

P1
while (TRUE) {
while (lock == 1); // wait
lock = 1;
critical-section ();
lock = 0;
Noncritical-section ();}
P2
while (TRUE) {
while (lock == 1); // wait
lock = 1;
critical-section ();
lock = 0;
Noncritical-section ();}
/*tiêu thụ sản phẩm trong nextConsumed*/
}

DaoQuangTri38(I12A) 17/4/2012, 22:46

Vấn đề về đoạn tương tranh:
Các tiến trình tác động liên quan đến thao tác tài nguyên dùng chung, sử dụng các mã lệnh trong quá trình thực hiện thì xảy ra tranh chấp gọi là đoạn tương tranh.
Tính loại trừ lẫn nhau: tại một thời điểm chỉ có thể chấp nhận cho một tiến trình đăng nhập(được chờ ở vùng đang nhập) và vùng tương tranh để thực thi. Khi thực thi xong sẽ thông báo cho các tiến trình đang chờ ở vùng đăng nhập tiếp tục thực hiện.
Code:
While(1)
{
Remainder section // chưa ảnh hưởng đến tài nguyên dùng chung
Entry section // các tiến trình(1 lệnh hoặc chuỗi lệnh) được chờ tại đây.
Critical section //vùng tương tranh
Exit section // tiến trình thực hiện xong thoát và thông báo cho tt kế tiếp thực thi.
Remainder section
}

letannghia(I12A) 17/4/2012, 22:52

- 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) .
Ví dụ:

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.

PhamDucPhuong(I12A) 17/4/2012, 22:53

TranPhiLong (I11C) đã viết:Thực thi đèn hiệu trong windows

typedef int semaphore;
semaphore s = n;
wait (s);
signal (s);

HANDLE s;
s=CreateSemaphore (0, n, max, t);
WaitForSingleObject (s, timeout);
ReleaseSemaphore (s, 1, NULL);

Ai hiểu code nầy không giải thích gúp mình với
Cảm ơn mọi người nhiều lắm.

có gì sai mọi người góp ý nhé
typedef int semaphore;
semaphore s = n;
wait (s);
signal (s);

HANDLE s; //định nghĩa kiểu đèn hiệu
s=CreateSemaphore (0, n, max, t); //tạo đèn hiệu với n:giá trị ban đầu của đèn hiệu,max: giá trị tối đa của đèn hiệu, t: tên của đèn hiệu
WaitForSingleObject (s, timeout); //đèn hiệu sẽ chờ trong một khoảng thời gian timeout,timeout = INFINITE hoặc số milli giây chờ
ReleaseSemaphore (s, 1, NULL);//tăng giá trị của đèn hiệu lên 1

Theo định nghĩa	Thực thi trong Visual C++
typedef int semaphore; semaphore s = n;	HANDLE s; s=CreateSemaphore (0, n, max, t);
wait (s);	WaitForSingleObject (s, timeout);
signal (s);	ReleaseSemaphore (s, 1, NULL);

nguyenhuutrang_11h1010135 18/4/2012, 00:19

Mục đích của đồng bộ hóa các tiến trình

Mục đích của đồng bộ hóa 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 và tránh hiện tượng Deadlock (hiện tượng kẹt tiến trình).

Trong đó, đảm bảo tính nhất quán của tài nguyên dùng chung là đảm bảo tính đúng đắn, tính hợp lý, tính toàn vẹn của tài nguyên dùng chung.

Ví dụ về tính nhất quán :

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty A
Tôi tên là: Đông Phương Vũ
..........(nội dung đơn).............

TP Hồ Chí Minh, ngày 18 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Đông Phương Vũ

Ví dụ về tránh hiện tượng Deadlock

Phòng máy thực hành của Đại học Mở là một tài nguyên dùng chung. Lớp này thực hành xong thì lớp khác mới được vào thực hành.

nguyenthihongtham_I12C 18/4/2012, 11:03

Câu 1: thế nào là đồng bộ hóa các tiến trình.
Đồng bộ hóa tiến trình là hợp nhất các tài nguyên dùng chung để đàm bảo tính nhất quán , toàn vẹn và đúng đắn hợp lý.
Ví dụ : Một cửa hàng kinh doanh điện thoại với các sản phẩm bán ra đều là linh kiện điện thoại thì khi lập bảng hiệu quảng cáo các mặt hàng trên bảng quảng cáo này tất nhiên phải là hình ảnh của linh kiện điện thoại chứ không thể là máy tình hay cá gì khác.
Câu 2: trình bày khái niệm đoạn tương tranh và tính loại trừ tương hỗ , 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.
Vấn đề về đoạn tương tranh:
Các tiến trình tác động liên quan đến thao tác tài nguyên dùng chung, sử dụng các mã lệnh trong quá trình thực hiện thì xảy ra tranh chấp gọi là đoạn tương tranh.
Tính loại trừ lẫn nhau: tại một thời điểm chỉ có thể chấp nhận cho một tiến trình đăng nhập(được chờ ở vùng đang nhập) và vùng tương tranh để thực thi. Khi thực thi xong sẽ thông báo cho các tiến trình đang chờ ở vùng đăng nhập tiếp tục thực hiện.

Ứng dụng thứ 1 của đèn hiệu :
giải quyết các vấn đề đoạn 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
}
Trong một thời điểm chỉ có một hoặc nhiều tiến trình phù hợp được thực thi trong điều kiện cho phép, không cho quá nhiều tiến trình thực thi gây quá tải.
Ví dụ, Vì cây cầu yếu nên trong một lúc chỉ cho một xe qua cầu , các xe khác phải xếp hàng đợi bên bờ cầu cho tới khi chiếc xe kia qua thì mới được lên cầu.

TranVanBao(I12A) 18/4/2012, 12:08

- Đ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. Đ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.
Ví dụ về Đoạn Tương Tranh:
ĐƠN XIN VIỆC
Kính gửi: Công ty ABC
Tôi tên là: Trần A
.........(nội dung đơn).........

TP.HCM, ngày 10 tháng 04 năm 2012
Người làm đơn
............(chữ ký).............
Trần A

Nội dung đơn này phải đảm bảo tính nhất quán, toàn vẹn( Integrity), ví dụ: Phía trên là Trần A thì phía dưới cũng phải là Trầ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 Trần A phía trên thành Nguyễn Văn An, trong khi P2(nhà sản xuất khác) sửa Trần A phía dưới thành Nguyễn Văn Ân, mà có tiến trình P3( nhà tiêu thụ) nào đó "lấy" đơn về dùng( để in ra) thì kết quả sẽ không nhất quán.

TranVanBao(I12A) 18/4/2012, 12:12

-Định nghĩa: Semaphore là một cờ hiệu trong thực thi đa tuyến, nếu một tuyến cần sử dụng tài nguyên nó sẽ thông báo với semaphore.
-Khởi đầu Semaphore mang giá trị dương. Tuyến yêu cầu sử dụng tài nguyên bằng cách gọi hàm sem_wait(), semaphore sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphore vẫn còn >0, nó sẽ tự động làm giảm giá trị đi 1 và cho phép tuyến sử dụng tài nguyên.
-Nếu giá trị Semaphore <=0 hệ thống sẽ tạm thời dừng tuyến.
-Khi một tuyến sử dụng xong tài nguyên nó gọi hàm sem_post() để trả quyền sử dụng tài nguyên lại cho Semaphore cấp phát cho lần sử dụng khác.
Ứng dụng Semaphore:
-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.

NgoXuanQuoc_(102C) 18/4/2012, 12:16

TranMinhTuan143(I12A) đã viết:Đề: đồng bộ hóa công việc của P1, P2, P3. sao cho:
a) P1 trước P2, P2 trước P3?
b) P1 trước P2 và P3?
c) P1 và P2 trước P3?

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

a) P1 trước P2, P2 trước P3
Semaphore synch1 = 0, synch2 = 0;
P1 P2 P3
S1 wait(synch1); wait(synch2);
signal(synch1); S2

signal(synch2); S3

Khi P1 dc thực hiện, thì P2 bị khóa tại hàm wait(synch1) do synch1=0; P3 bị khóa tại hàm wait(synch2) do synch2=0. Sau khi S1 dc thi hành thì synch1 sẽ tăng lên 1 do signal(synch1).
Lúc này P2 sẽ dc thực hiện(synch1 =1), nhưng P3 vẫn bị khóa do synch2 =0, sau khi S2 thi hành xong thì synch2 =1(signal(synch2)) lúc này P3 mới dc thực hiện.
=> P1 trước P2, P2 trước P3.

b) P1 trước P2 và P3
Semaphore synch = 0;
P1 P2 P3
S1 wait(synch); wait(synch);
signal(synch, 2); S2 S3

Tại thời điểm ban đầu: synch=0,
Khi tiến trình P2 được thực hiện, thì P2 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi tiến trình P3 được thực hiện, thì P3 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi P1 thực hiện ,S1 được thi hành xong thì lệnh signal(synch, 2); dc thực thi, tức là tăng synch = 2.
Khi đó synch>0 ,tiến trình P2 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=1).
Đồng thời P3 được thực hiện và hàm wait(synch) sẽ giảm giá trị synch xuống 1 đơn vị (synch=0).
->P2 và P3 cùng thực hện.
=>P1 đi trước P2 và P3.

c) P1 và P2 trước P3
Semaphore synch = -1;
P1 P2 P3
S1 S2 wait(synch);
signal(synch); signal(synch); S3

Tại thời điểm ban đầu: P1 và P2 đang thực hiện lệnh S1, S2, lúc này synch=-1.
Lúc này P3 đang bị khóa tại hàm wait(synch) đợi khi synch >0.
Khi P1 thực hiện, S1 dc thi hành xong thì hàm signal(synch) sẽ tăng synch lên 1 và synch= 0. P3 lúc này vẫn bị khóa do synch=0.
Khi P2 thực hiện, S2 dc thi hành xong thì hàm signal(synch) sẽ tăng synch lên 1 và synch= 1.
Lúc này P3 mới dc thực hiện.
=>P1 và P2 trước P3.

Mong thầy và các bạn góp ý.

Câu B giải thích như bạn thì khá khó hiểu Crying or Very sad

Qua tìm hiểu mình xin góp ý bổ sung giải thích như sau:

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 tức là bị khóa tại hàm kiểm tra điều kiện while (S<=0). Hàm này sẽ kiểm tra synch đã lớn hơn 0 chưa và chờ cho đến khi synch>0 thì hàm S2 sẽ được thực hiện.

- 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 tức là bị khóa tại hàm kiểm tra điều kiện while (S<=0). Hàm này sẽ thường xuyên kiểm tra synch đã lớn hơn 0 chưa và chờ cho đến khi synch>0 thì hàm S3 sẽ được thực hiện.

Đây là ý kiến của mình, các bạn góp ý thêm nhé. Very Happy

TranVanBao(I12A) 18/4/2012, 12:22

Đồng bộ hóa tiến trình là điều khiển công việc của luồng và tiến trình sao cho đáp ứng yêu cầu đặt ra của logic nghiệp vụ.
Mục đích của đồng bộ hóa tiến trình.
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
ví dụ: bài toán sản xuất tiêu thụ.
một bạn trong lớp lên bảng (tài nguyên dùng chung của lớp) ghi thông tin cá nhân nhưng chưa ghi xong thì bạn khác dưới lớp chụp lại thông tin trên sẽ không đúng. muốn lấy thông tin chính xác thì bạn dưới lớp cần lấy thông tin của bạn trên bảng ghi phải chờ bạn ấy ghi hết thông tin rồi mới chụp ảnh.
- Tránh Deadlock ( hiện tượng kẹt tiến trình).
ví dụ: một trường học chỉ có 1 phòng máy (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng máy 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 học.

NgoXuanQuoc_(102C) 18/4/2012, 12:27

- Bài dưới này mình đọc được tại box Hoàn chỉnh kiến thức I11C thấy rất hay nên up lại cho mọi người cùng đọc.
- Các bạn nên thường xuyên sang diễn đàn các lớp trước đây tham khảo, có nhiều bài rất bổ ích đó Smile

tranphanhieu36_i11c đã viết:
TangHuynhThanhThanh I11C đã viết:
thanhnam06511c đã viết:...
Mình bổ sung 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.

Admin
Một ví dụ thiết thực !

Thưa thầy và các bạn !
Về ví dụ rút tiền ở tài khoản ATM này em thấy có một số vấn đề đáng lưu ý sau nữa về vấn đề đồng bộ hóa tiến trình.
Về ví dụ sử dụng tài khoản ATM của bạn thì đúng là đã giải quyết vấn đề tương hỗ ( mỗi thời điểm thì có một tiến trình vào và sử dụng vùng nhớ chung - tài khoản ) nhưng là bằng chia sẻ thời gian "time out" nên vẫn xảy ra lỗi. Bởi vì kiểm tra điều kiện rồi nhưng không thực hiện luôn mà lại thực hiện sau để cho bộ nhớ chung vậy là rất dễ sai hay xảy ra lỗi. Kiểm tra điều kiện nằm ngoài vùng tương tranh.
Theo em vấn đề rút tiền này thì mỗi lần có lệnh gì liên quan tới vùng nhớ chung ( tài khoản ) thì phải kiểm tra xong rồi thực hiện lệnh cùng 1 lúc luôn. Trước khi vào kiểm tra tài khoản thì phải dùng đèn hiệu để tại mỗi thời điểm chỉ cho một người dùng vào kiểm tra duy nhất. Việc kiểm tra tài khoản và thực hiện lệnh (rút tiền) đều cùng nằm trong đoạn tương tranh thì sẽ không xảy ra lỗi trên.

Ví dụ của bạn hay nhưng mà cũng như về ví dụ qua cầu thì khi 1 xe đến, kiểm tra thấy đèn xanh và được quyền qua cầu nhưng lại không qua liền mà ngồi chơi ở bên góc cầu 10 phút (chưa vào đoạn tương tranh nên đèn vẫn còn màu xanh nên xe khác vẫn được kiểm tra và qua cầu ). Rồi lát nữa chẳng cần kiểm tra nữa mà cứ thế qua cầu khi đèn hiệu đã có thể thay đổi bởi xe khác ->Sai.
=> Kiểm tra xong là phải qua cầu liền, nếu chưa qua thì lần qua sau thì phải kiểm tra lại, quyền được phép qua cầu chỉ có hiệu lực khi kiểm tra.

Admin
- Em hiểu bài tốt, nhất là nêu được: "Trước khi vào kiểm tra tài khoản thì phải dùng đèn hiệu để tại mỗi thời điểm chỉ cho một người dùng vào kiểm tra duy nhất. Việc kiểm tra tài khoản và thực hiện lệnh (rút tiền) đều cùng nằm trong đoạn tương tranh thì sẽ không xảy ra lỗi trên".
- Tất nhiên, cần thực hiện lệnh signal(s) sau khi trừ Tài khoản, để đèn s chuyển sang xanh và cho phép tiến trình khác thao tác với Tài khoản vừa giảm.
- Với Bài toán "Xe qua cầu yếu", trong đoạn tương tranh đâu có lệnh "Ngồi chờ 10 phút" (chỉ có 2 lệnh là Lên cầu và Qua cầu), tất cả do Lập trình cụ thể cả. Mặt khác, giả sử có "Ngồi 10 phút", thì chỉ xe này mới có quyền chuyển đèn từ Đỏ sang Xanh vì theo code của nó lệnh Qua cầu thực hiện xong mới đến lệnh signal(s). Những xe khác khi đến đầu cầu, đang "Ngủ" tại lệnh wait(s) mà (vì đèn s đang Đỏ) !

-----------------------------------------------------------------------------------------------------------------------
"You can turn the sky green and make the grass look blue, but you can’t stop me from loving you."

Sponsored content

Thảo luận Bài 7