Thảo luận Bài 7

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

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

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

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 22:19

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.


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 ?

Đoạn tương tranh là đoạn mã chương trình, điều khiển công việc của tiến trình có tính chất, mà khi thể hiện đoạn mã đó tác động tới tài nguyên dùng chung.

- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.

- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

PhamThiThao (I22B)

Tổng số bài gửi : 54
Join date : 19/03/2013

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

Về Đầu Trang Go down

Bai 7: Dong bo hoa tien trinh

Bài gửi  TranAnhTam(I22B) on 19/4/2013, 20:15

Một cửa hiệu cắt tóc có một thợ, một ghế cắt tóc và N ghế cho khách đợi. Nếu không có
khách, thợ cắt tóc sẽ ngồi vào ghế cắt tóc và ngủ thiếp đi. Khi một khách hàng vào tiệm, anh ta
phải đánh thức người thợ. Nếu một khách hàng vào tiệm khi người thợ đang bận cắt tóc cho khách
hàng khác, người mới vào sẽ ngồi chờ nếu có ghế đợi trống, hoặc rời khỏi tiệm nếu đã có N người
đợi (hết ghế). Xây dựng một giải pháp với semaphore để thực hiện đồng bộ hoá hoạt động của thợ
và khách hàng trong cửa hiệu cắt tóc này

TranAnhTam(I22B)

Tổng số bài gửi : 19
Join date : 28/03/2013

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

Về Đầu Trang Go down

Bài 7: Đồng bộ hóa tiến trình

Bài gửi  TranAnhTam(I22B) on 19/4/2013, 20:36

Để 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ột chiếc thuyền này chỉ cho phép chở 1 lần 4 người, và phải
có đủ 4 ngườii 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 khác đều hợp pháp.
d. Thuyền chỉ khởi hà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:
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
}





TranAnhTam(I22B)

Tổng số bài gửi : 19
Join date : 28/03/2013

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

Về Đầu Trang Go down

Ví dụ: Xe qua cầu yếu

Bài gửi  nguyenhoanglam_I22B on 21/4/2013, 23:23

Mã của tiến trình Xei có cấu trúc như sau:

Code:
Typedef int semaphore;
Semaphore mutex = 1; //đèn hiệu nhị phân, có hai trạng thái
//0: đèn màu đỏ
//1: đèn màu xanh
While(1)
{
Đi đến cầu;
Wait(mutex); //chờ đèn xanh
Lên cầu; //đoạn tương tranh, đèn màu đỏ
Qua cầu; //đoạn tương tranh, đèn màu đỏ
Signal(mutex); //đèn chuyển sang màu xanh
Đi tiếp;
Quay về theo cầu khác;
}

Do chiếc cầu yếu nên mỗi thời điểm chỉ có 1 xe được phép qua cầu. Những xe khác khi đi đến đầu cầu sẽ ngủ tại lệnh wait(mutex) vì đèn đỏ. Sau khi một xe đã lên cầu và qua cầu xong thì lệnh signal(mutex) được thực hiện, tăng đèn mutex lên 1, đèn chuyển sang màu xanh. Một xe sau sẽ được đánh thức và lên cầu. Trong trường hợp này vùng tranh chấp là cây cầu.

nguyenhoanglam_I22B

Tổng số bài gửi : 16
Join date : 12/03/2013

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

Về Đầu Trang Go down

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ộ trong công việc của các tiến trình đồng hành song song cùng tranh chấp tài nguyên chung

Bài gửi  TrỉnhToQuyen(I12A) on 11/6/2013, 21:28

- 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á

TrỉnhToQuyen(I12A)

Tổng số bài gửi : 23
Join date : 10/03/2013

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

Về Đầu Trang Go down

Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S , Ý nghĩa của hàm signal

Bài gửi  TrỉnhToQuyen(I12A) on 11/6/2013, 21:31

Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S :
Chờ cho đến khi giá trị của đèn hiệu S > = 1 sau đó qua được lệnh chờ này và giá trị của đèn tự động giảm đi 1.
Ý nghĩa của hàm signal : Đèn S tăng thêm 1

TrỉnhToQuyen(I12A)

Tổng số bài gửi : 23
Join date : 10/03/2013

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

Về Đầu Trang Go down

Câu 3: Trình bày khái niệm đèn hiệu và 2 ứng dụng của nó

Bài gửi  TrỉnhToQuyen(I12A) on 11/6/2013, 21:32

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

TrỉnhToQuyen(I12A)

Tổng số bài gửi : 23
Join date : 10/03/2013

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  NguyenTienDat (I22A) on 16/6/2013, 18:49

TrỉnhToQuyen(I12A) đã viết:Ý nghĩa của hàm Wait áp dụng cho đèn hiệu S : 
Chờ cho đến khi giá trị của đèn hiệu S > = 1 sau đó qua được lệnh chờ này và giá trị của đèn tự động giảm đi 1.
Ý nghĩa của hàm signal : Đèn S tăng thêm 1
Ý nghĩa của hàm signal: Giá trị của đèn S được tăng thêm 1 mới đúng chứ nhỉ 

NguyenTienDat (I22A)

Tổng số bài gửi : 19
Join date : 10/03/2013
Age : 25

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 10 trong tổng số 10 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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