Thảo luận Bài 7

Trang 3 trong tổng số 8 trang Previous  1, 2, 3, 4, 5, 6, 7, 8  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Ví dụ về đồng bộ hoá

Bài gửi  phuongnguyen on 12/4/2012, 07:18


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.

phuongnguyen

Tổng số bài gửi : 27
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Khái niệm về đồng bộ hóa tiến trình

Bài gửi  TranThiAnhDao89I12C on 12/4/2012, 07:26

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

Tài nguyên dùng chung là vùng nhớ để chúng trao đổi thông tin với nhau.

Đồng bộ hóa tiến trình còn giúp tránh được hiện tượng Deadlock

TranThiAnhDao89I12C

Tổng số bài gửi : 25
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Đèn hiệu nhị phân để đảm bảo tính loại trừ lẫn nhau.

Bài gửi  TranThiAnhDao89I12C on 12/4/2012, 07:27

Đèn hiệu nhị phân chỉ có 2 trạng thái (xanh và đỏ - 1 và 0).
VD: Giả sử có 1 cây cầu ở đầu cầu có 1 cái đèn, trên đoạn đường đến cầu có các oto (vd oto1, oto2...) và cầu chỉ có tải trọng 1 chiếc oto đi qua tại 1 thời điểm khi duy chuyển qua cầu, đèn báo có 2 trạng thái 0 và 1 (đỏ và xanh), đèn xanh xe oto được phép đi, đỏ oto còn lại phải chờ đến lượt, giống như trạng thái wait(s);, signal(s).
- Đè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)

TranThiAnhDao89I12C

Tổng số bài gửi : 25
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Thiết kế đèn hiệu Mutex và lập trình cho công việc xe

Bài gửi  NguyenHongHaiI12C on 12/4/2012, 07:53



Thuật giải cho Xei:
While(1)
{
Đi đến cầu;
Wait (minutes);
lên cầu;
qua cầu;
Signal(minutes);
đ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 !)

NguyenHongHaiI12C

Tổng số bài gửi : 48
Join date : 18/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Đồng bộ hóa công việc các tiến trình P1, P2, P3 để sao cho P1, trước P2, P2 trước P3.

Bài gửi  NguyenHongHaiI12C on 12/4/2012, 07:59

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

Admin
Không thấy có lệnh signal(synch2) trong mã của P2 !

NguyenHongHaiI12C

Tổng số bài gửi : 48
Join date : 18/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Đồng bộ hóa công việc các tiến trình P1, P2, P3 để sao cho P1 trước P2,P3.

Bài gửi  NguyenHongHaiI12C on 12/4/2012, 08:02

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

Admin
- Giải thích thuyết phục !
- Chú ý: Sau khi thực hiện signal(synch, 2), HĐH có thể cho P3 vào cuộc trước P2 !

NguyenHongHaiI12C

Tổng số bài gửi : 48
Join date : 18/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Đồng bộ hóa công việc các tiến trình P1, P2, P3 để sao cho P1 ,P2 trước P3.

Bài gửi  NguyenHongHaiI12C on 12/4/2012, 08:04

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.

Admin
Giải thích tốt !

NguyenHongHaiI12C

Tổng số bài gửi : 48
Join date : 18/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập Lập trình đồng bộ hóa công việc 3 tiến trình P1, P2, P3 sao cho P1 và P2 trước P3

Bài gửi  nguyenthingocmai_I12A on 12/4/2012, 08:32

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 cho ý kiến.

nguyenthingocmai_I12A

Tổng số bài gửi : 26
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  nguyenthingocmai_I12A on 12/4/2012, 08:53

NguyenHongHaiI12C đã viết: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(synch1); S3,signal(synch2)
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.

Admin
Không thấy có lệnh signal(synch2) trong mã của P2 !

nguyenthingocmai_I12A

Tổng số bài gửi : 26
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Cau hoi cau 1: bai 7

Bài gửi  huynhthao.hc11th2a on 12/4/2012, 08:59

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

Câu 1: Trình bày muc đích đồng bộ hóa công việc của các tiến trình. Cho ví dụ minh họa.
Trả lời:
Mục đích của đồng bộ hóa công việc các tiến trình là đảm bảo tính nhất quán của tài nguyên dùng chung và tránh được hiên tượng Deadlock (hiện tượng kẹt tiến trình).
Ví dụ tránh được hiên tượng Deadlock.
Đảm bảo tính nhất quán của tài nguyên dùng chung là đảm bảo đúng đắn hợp lý, tính toàn vẹn của tài nguyên dùng chung. Ví dụ:
ĐON XIN VIỆC
Tôi tên là: Lê Văn Ba.
………………
Kí tên
Lê Văn Ba
So sánh đồng bộ hóa công việc của 1 tiến trình và đồng bộ hóa công việc của các tiến trình:
Khác nhau:
+ Đồng bộ hóa công việc của 1 tiến trình là đồng bộ các luồng bên trong của tiến trình, luồng cũng là bên trong của tiến trình đó.
+ Đồng bộ hóa công việc của các tiến trình là là tiến trình truyền thống nặng.
Giống nhau: Tiến trình của 1 tiến hay hay của các tiến trình cũng phải đồng bộ.Đồng bộ bảo đảm các luồng của tiến trình hoặc vav1 tiến trình làm việc ding91 thứ tự, trật tự và ăn khớp với nhau. Ví dụ: Khi nộp bài thi Thầy gọi 5 bạn lên nộp bài, và đứng xếp hàng, 1 bạn lên phía trên và 4 bạn phải đứng chờ khi bạn kia nộp xong thì 4 bạn lần lượt lên nộp bài.
Đồng bộ là phải có chờ, ko chờ sẽ xảy ra hiện tượng kẹt tiến trình (Deadlock)

huynhthao.hc11th2a

Tổng số bài gửi : 19
Join date : 23/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  TranTrungHienI12C on 12/4/2012, 09:34

Ví dụ minh họa về đồng bộ hóa giữa các tiến trình:

Trong một trận cầu bóng đá,huấn luyện viên đội A là tiến trình P1. Vào một thời điểm của trận đấu,huấn luyện viên A sẽ thay đổi người thi đấu,huấn luyện viên ghi thông tin cầu thủ cần thay vào giấy. Trọng tài bàn là tiến trình P2 sẽ tiếp nhận thông tin trên giấy của huấn luyện viên A,và cũng tại thời điểm đó,huấn luyện viên của đội B là tiến trình P3 cũng cần thay đổi người,và ghi thông tin lên giấy và đưa cho trọng tài bàn.Giả sữ trong thời điểm trọng tài bàn tiếp nhận,2 huấn luyện viên cùng ghi thông tin trên 1 tờ giấy,và trọng tài bàn vì lý do nhìn không kỹ,nên đánh số thay đổi cầu thủ không đúng giữa 2 đội và dẫn đến trận đấu bị gián đoạn.
avatar
TranTrungHienI12C

Tổng số bài gửi : 19
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamquangvu53(I12A) on 12/4/2012, 09:49

Vấn đề về đoạn tương tranh và Tính loại trừ lẫn nhau

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
}

ví dụ:
Vùng tương tranh là cái bảng. Ở 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.

phamquangvu53(I12A)

Tổng số bài gửi : 7
Join date : 23/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Khái niện đoạn tương tranh và loại trừ lẫn nhau. Cho ví dụ minh họa.

Bài gửi  Đỗ Phan Diễm Hương I12A on 12/4/2012, 10:20

- Đ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ụ:
ĐƠ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á

avatar
Đỗ Phan Diễm Hương I12A

Tổng số bài gửi : 13
Join date : 17/02/2012
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

Khái niệm đèn hiệu (Semaphores).Và 2 ứng dụng của đèn hiệu.

Bài gửi  Đỗ Phan Diễm Hương I12A on 12/4/2012, 10:22

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



avatar
Đỗ Phan Diễm Hương I12A

Tổng số bài gửi : 13
Join date : 17/02/2012
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

Mục đích đồng bộ hóa công việc tiến trình. Cho ví dụ minh họa

Bài gửi  Đỗ Phan Diễm Hương I12A on 12/4/2012, 10:32

- Đồng bộ hóa công việc tiến trình là đồng bộ hóa công việc các luồng trong các tiến trình
- Đả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,toàn vẹn,hợp lí của tài nguyên dùng chung
VD: Cả lớp là 1 tiến trình chung,các sinh viên là các luồng,bảng là tài nguyên dùng chung,có thông báo gì sẽ được ghi lên bảng,các sinh viên sẽ ghi chép lại
avatar
Đỗ Phan Diễm Hương I12A

Tổng số bài gửi : 13
Join date : 17/02/2012
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  nguyenvanhonglac_0066 on 12/4/2012, 10:48

Thực thi bài toán sản xuất, tiêu thụ được đồng bộ bằng đèn hiệu:

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.

nguyenvanhonglac_0066

Tổng số bài gửi : 15
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  LuongGiaDuc(I12A) on 12/4/2012, 10:53

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


LuongGiaDuc(I12A)

Tổng số bài gửi : 29
Join date : 10/03/2012
Age : 27
Đến từ : TPHCM

Xem lý lịch thành viên

Về Đầu Trang Go down

Ứng dụng đèn hiệu

Bài gửi  LuongGiaDuc(I12A) on 12/4/2012, 10:54

1. Giải quyết vấn đề VTT.
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
}


2. 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 : Cấu trúc P2 :
S1 wait (synch);
signal (synch); S2

LuongGiaDuc(I12A)

Tổng số bài gửi : 29
Join date : 10/03/2012
Age : 27
Đến từ : TPHCM

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  nguyenvanhonglac_0066 on 12/4/2012, 11:07

Giải bài tập đồng bộ hóa công việc của P1, P2, P3 sao cho:

BT1) P1 trước P2, P2 trước P3?
BT2) P1 trước P2 và P3?
BT3) 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

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

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

BT3) 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 ý? Very Happy

nguyenvanhonglac_0066

Tổng số bài gửi : 15
Join date : 16/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

Tính nhất quán của tài nguyên dùng chung là gi ?

Bài gửi  phamphihung55 on 12/4/2012, 11:18

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

P/s: có sai sót gì xin thầy giúp ạ !!!
avatar
phamphihung55

Tổng số bài gửi : 83
Join date : 16/02/2012
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamduyI12A on 12/4/2012, 12:17

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

vài dòng đóng góp Very Happy

phamduyI12A

Tổng số bài gửi : 20
Join date : 19/02/2012
Age : 27
Đến từ : TPHCM

Xem lý lịch thành viên

Về Đầu Trang Go down

1 số bài toán về đồng bộ hóa tiến trình

Bài gửi  thailongI12C on 12/4/2012, 12:36

Mình tìm đc 1 số bài toán về đồng bộ hóa,mạn phép post lên đây để các bạn cùng tham khảo Very Happy
Bài 1.Bài toán Tạo phân tử H2O
  • Đồng bộ hoạt động của một phòng thí nghiệm sử dụng nhiều tiến trình đồng hành sau để tạo các phân tử H2O:

Code:
MakeH() // Mỗi tiến trình MakeH tạo 1 nguyên tử H
{
Make-Hydro();
}
MakeO() // Mỗi tiến trình MakeO tạo 1 nguyên tử O
{
Make-Oxy();
}
MakeWater() /* Tiến trình MakeWater hoạt động đồng hành
với các tiến trình MakeH, MakeO, chờ có đủ 2 H và 1 O để tạo H2O */
{
while (T)
Make-Water(); //Tạo 1 phân tử H2O
}
Bài 2.Bài toán Cây cầu cũ
Để tránh sụp đổ, người ta chỉ có cho phép tối đa 3 xe lưu thông đồng thời qua một cây cầu rất cũ. Hãy xây dựng thủ tục ArriveBridge(int direction) và ExitBridge() kiểm soát giao thông trên cầu sao cho :
  • Tại mỗi thời điểm, chỉ cho phép tối đa 3 xe lưu thông trên cầu.

  • Tại mỗi thời điểm, chỉ cho phép tối đa 3 xe lưuthông cùng hướng trên cầu.

  • Mỗi chiếc xe khi đến đầu cầu sẽ gọi ArriveBridge(direction) để kiểm tra điều kiện lên cầu, và khi đã qua cầu được sẽ gọi ExitBridge() để báo hiệu kết thúc.

  • Giả sử hoạt động của mỗi chiếc xe được mô tả bằng một tiến trình Car() sau đây:

Code:
Car(int direction) /* direction xác định hướng di chuyển của mỗi chiếc xe.*/
{
RuntoBridge(); // Đi về phía cầu
ArriveBridge(direction);
PassBridge(); // Qua cầu
Exit Bridge();
RunfromBridge(); // Đã qua cầu
}
Bài 3. Bài toán Qua sông
Để vượt qua sông, các nhân viên Microsof và các Linux hacker cùng sử dụng một bến sông và phải chia sẻ một số thuyền đặc biệt. Mỗi chiếc thuyền này chỉ cho phép chở 1 lần 4 người, và phải có đủ 4 người mới khởi hành được. Để bảo đảm an toàn cho cả 2 phía, cần tuân thủ các luật sau :
a. Không chấp nhận 3 nhân viên Microsoft và 1 Linux hacker trên cùng một chiếc thuyền.
b. Ngược lại, không chấp nhận 3 Linux hacker và 1 nhân viên Microsoft trên cùng một chiếc thuyền.
c. Tất cả các trường hợp kết hợp khác đều hợp pháp.
d. Thuyền chỉ khởihành khi đã có đủ 4 hành khách.
  • Cần xây dựng 2 thủ tục HackerArrives() và EmployeeArrives() được gọi tương ứng bởi 1 hacker hoặc 1 nhân viên khi họ đến bờ sông để kiểm tra điều kiện có cho phép họ xuống thuyền không ? Các thủ tục này sẽ sắp xếp những người thích hợp có thể lên thuyền. Những người đã được lên thuyền khi thuyền chưa đầy sẽ phải chờ đến khi người thứ 4 xuống thuyền mới có thể khởi hành qua sông. (Không quan tâm đến số lương thuyền hay việc thuyền qua sông rồi trở lại…Xem như luôn có thuyền để sắp xếp theo các yêu cầu hợp lệ)

  • Giả sử hoạt động của mỗi hacker được mô tả bằng một tiến trình Hacker() sau đây:

Code:
Hacker()
{
RuntoRiver(); // Đi đến bờ sông
HackerArrives (); // Kiểm tra điều kiện xuống thuyền
CrossRiver(); // Khởi hành qua sông
}
và hoạt động của mỗi nhân viên được mô tả bằng một tiến trình Employee() sau đây:
Employee()
{
RuntoRiver(); // Đi đến bờ sông
EmployeeArrives (); // Kiểm tra điều kiện xuống thuyền
CrossRiver(); // Khởi hành qua sông
}
Bài 4. Bài toán Điều phối hành khách xe bus
  • Hãy tưởng tượng bạn chịu trách nhiệm kiểm soát hành khách lên xe bus tại một trạm dừng.
    Mỗi xe bus có đủ chỗ cho 10 hành khách. Trong đó 4 chỗ chỉ dành cho khách ngồi xe lăn, 6 chỗ còn lại chỉ dành cho khách bình thường.

  • Công việc của bạn là cho khách lên xe theo đúng qui định chỗ, khi xe đầy khách sẽ khởi hành. Có thể có nhiều xe và nhiều hành khách vào bến cùng lúc, nguyên tắc điều phối sẽ xếp khách vào đầy một xe, cho xe này khởi hành rồi mới điều phối cho xe khác.

  • Giả sử hoạt động điều phối khách của bạn cho 1 chiếc xe bus được mô tả qua tiến trình

  • GetPassengers(); hoạt động của mỗi hành khách tùy loại được mô tả lần lượt bằng tiến trình

  • WheelPassenger() và NonWheelPassenger() sau đây , hãy sửa chữa các đoạn code, sử dụng cơ chế semaphore để thực hiện các nguyên tắc đồng bộ hoá cần thiết.

Code:
GetPassenger()
{
ArriveTerminal(); // tiếp nhận một xe vào bến
OpenDoor(); // mở cửa xe, thủ tục này xem như đã có
for (int i=0; i<4; i++) // tiếp nhận các hành khách ngồi xe lăn
{
ArrangeSeat(); // đưa 1 khách vào chỗ
}
for (int i=0; i<6; i++) // tiếp nhận các hành khách bình thường
{
ArrangeSeat(); // đưa 1 khách vào chỗ
}
CloseDoor(); // đóng cửa xe, thủ tục này xem như đã có
DepartTerminal(); // cho một xe rời bến
}
WheelPassenger()
{
ArriveTerminal(); // đến bến
GetOnBus(); // lên xe
}
NonWheelPassenger()
{
ArriveTerminal(); // đến bến
GetOnBus(); // lên xe
}

thailongI12C

Tổng số bài gửi : 35
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

ví dụ về việc đồng bộ hóa các luồng trong tiến trình

Bài gửi  LuongHueChanh_I12A on 12/4/2012, 12:41


lớp học chúng ta là một tiến trình, mỗi bạn sinh viên là một luồng trong đó
bảng xanh chính là thanh ghi là tài nguyên sử dụng chung cho tất cả các luồng
khi thầy giảng bài, hoặc khi các bạn lên bảng làm bài chính là cập nhật dữ liệu cho thanh ghi

các luồng của tiến trình sử dụng dữ liệu từ thanh ghi sau khi thông tin trên đó được cập nhật
ví dụ như khi có 1 bạn lên bảng làm bài, các bạn bên dưới không nên vội vàng chép bài trên bảng
phải đợi sau khi thầy xác nhận bài đúng hoặc bài sai, có chỉnh sửa rồi thì mới ghi bài trên bảng vào vở

tương tự cho quá trình nộp bài kiểm tra
vì lớp có rất đông sinh viên, nên cần phải tổ chức tốt việc nộp bài, để tránh làm mất bài, sót bài của các bạn
do đó, chia nhỏ tiến trình nộp bài thành nhiều luồng: mỗi lần chỉ có 5 sinh viên lên nộp theo thứ tự
1nguoi nộp - 4nguoi còn lại chờ khi nào bạn kia kí tên và nộp bài xong thì lần lượt lên nộp
mỗi lượt 5 bạn cho đến khi hết danh sách
lợi ích:
tránh được việc quá tải cho việc phải nhận và sắp xếp bài trong một thời điểm
các luồng đồng bộ, nhịp nhàng, sẽ nhanh hơn vì giảm được thời gian xử lý sai xót xảy ra
tránh được tình trạng hỗn loạn do quá đông người cùng lên nộp bài cùng lúc

LuongHueChanh_I12A

Tổng số bài gửi : 11
Join date : 17/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

NHU CẦU ĐỒNG BỘ HÓA

Bài gửi  plminhhoangI12A on 12/4/2012, 13:07

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:
1. 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ẻ.
2. 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 đó …
VD về đồng bộ hóa:
VD1:1 trường học chỉ có 1 phòng lab dùng chung.Nếu lớp có giờ học trước thì được vào học đầu tiên,các lớp khác phải chờ lớp đầu tiên học xong mới được vào phòng lab.
VD2:
ĐƠN XIN VIỆC
Kính gửi:cty ABC
Tôi tên là:Nguyễn Văn A
.......................
Ký tên
Nguyễn Văn A
Đơn xin việc trên bảo đảm tính nhất quán do cùng họ tên
ĐƠN XIN VIỆC
Kính gửi:cty ABC
Tôi tên là:Nguyễn Văn B
.......................
Ký tên
Nguyễn Văn A
Không nhất quán do không trùng họ tên

plminhhoangI12A

Tổng số bài gửi : 19
Join date : 22/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  NguyenHongHaiI12C on 12/4/2012, 13:30

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

Admin
- Nội dung tốt !
- Nên trình bàysao cho "nổi" hơn !

NguyenHongHaiI12C

Tổng số bài gửi : 48
Join date : 18/02/2012

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  Sponsored content


Sponsored content


Về Đầu Trang Go down

Trang 3 trong tổng số 8 trang Previous  1, 2, 3, 4, 5, 6, 7, 8  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết