Uploaded by
Nguyễn Hoàng Lân
0% found this document useful [0 votes]
276 views
5 pages
Original Title
Cay Cay Cu.docx
Copyright
© © All Rights Reserved
Available Formats
DOCX, PDF, TXT or read online from Scribd
Share this document
Did you find this document useful?
Is this content inappropriate?
0% found this document useful [0 votes]
276 views5 pages
Cay Cay Cu
Uploaded by
Nguyễn Hoàng Lân
Jump to Page
You are on page 1of 5
Search inside document
Reward Your Curiosity
Everything you want to read.
Anytime. Anywhere. Any device.
No Commitment. Cancel anytime.
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
Đồ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
Đè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. 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
Semaphore synch = -1;
P1 P2 P3S1 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
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
NguyenHongHaiI12C đã viết:a] P1 trước P2, P2 trước P3Semaphore 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
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
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.
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
- Đ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á
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 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 ý?
nguyenvanhonglac_0066 Tổng số bài gửi : 15 Join date : 16/02/2012
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 ạ !!!
- Đồ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
phamduyI12A Tổng số bài gửi : 20 Join date : 19/02/2012 Age : 33 Đến từ : TPHCM
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
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 :
- 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.
- 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.
- Tất cả các trường hợp kết hợp khác đều hợp pháp.
- 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