Thảo luận Bài 7

Trang 5 trong tổng số 5 trang Previous  1, 2, 3, 4, 5

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

Định nghĩa đèn hiệu với 2 tác nguyên Wait(chờ) và Signal(báo hiệu)

Bài gửi  DaoVanHoang (I11C) on 3/11/2011, 16:56

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

DaoVanHoang (I11C)

Tổng số bài gửi : 24
Join date : 31/08/2011

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

Về Đầu Trang Go down

Khái niệm Đoạn tương tranh và Loại trừ lẫn nhau

Bài gửi  DaoVanHoang (I11C) on 3/11/2011, 17:00

- Ví dụ có n tiến trình { P0 , P1 ,....., Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên 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 Đ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 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).

DaoVanHoang (I11C)

Tổng số bài gửi : 24
Join date : 31/08/2011

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

Về Đầu Trang Go down

phát biểu bài toán SX-TT và trình bày thực giải và bộ đệm thực thi và mảng xoay vòng

Bài gửi  doanhongdao030(I11C) on 4/11/2011, 13:25

Phát biểu bài toán:
giả sử có bộ nhớ điệm (Buffer) bao gồm nhiều khoang (items) được tiến trình Producer lần lượt đưa các sản phẩm S1, S2, ... vào.
Tiến trình Consumer lần lượt lấy các sản phẩm ra theo đúng thứ tự.
Công việc của Producer phải đồng bộ với Consumer: Không được đưa sản phẩm vào khi Buffer đầy, không được lấy ra khi chưa có.
Trình bày thực giải:



doanhongdao030(I11C)

Tổng số bài gửi : 17
Join date : 01/09/2011

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

Về Đầu Trang Go down

Phát biểu bài toàn SX-TT sử dụng đẻn hiệu đồng bộ hóa

Bài gửi  doanhongdao030(I11C) on 4/11/2011, 13:44

Hai quá trình cùng chia sẻ 1 vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ tương hỗ để truy xuất vùng đệm và được khởi tạo giá trị bằng 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 đến giá trị n, biến semaphore full được khởi tạo đến giá trị 0.
Dữ liệu chia sẻ:
SEMAPHORE full, empty, mutex;
Khởi tạo:
full=0;
mutex=1;
empty=BUFFER_SIZE;



doanhongdao030(I11C)

Tổng số bài gửi : 17
Join date : 01/09/2011

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

Về Đầu Trang Go down

Đồng bộ hóa công việc tiến trình.

Bài gửi  PhamDuyPhuong87(I11C) on 8/11/2011, 17:27

.- Đả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ụ:
-Ban Dương Trung Tính lên bảng(bảng tài nguyên dùng chung) viết tên của mình, nếu bạn chưa viết xong (mới viết Duong Trung ) mà bạn khác chụp ảnh trên bảng để đưa lấy về sẽ dẫn đến thông tin bị sai( kết quả tên Tính ->Trung), nên việc đồng bộ có tác dụng rất lớn phải chờ bạn Tính viết xong sau đó mới chụp ảnh để thông tin chính xác.

PhamDuyPhuong87(I11C)

Tổng số bài gửi : 23
Join date : 31/08/2011

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

Về Đầu Trang Go down

K/N Đoạn Tương Tranh và Loại Trừ Lẫn Nhau

Bài gửi  PhamDuyPhuong87(I11C) on 8/11/2011, 17:31

- Giả sử có n tiến trình { P0 , P1 , ... , Pn-1 }. Mỗi tiến trình có đoạn mã gọi là Đoạn tương tranh ( ĐTT ) trong đó tiến trình có thể truy cập và thay đổi vùng nhớ, tập tin hay tài nguyên 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).

PhamDuyPhuong87(I11C)

Tổng số bài gửi : 23
Join date : 31/08/2011

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  NguyenThiThanhThuy(I11C) on 9/11/2011, 12:56

Edsger Wybe Dijkstra có nhiều đóng góp mang tính bước ngoặc trong lĩnh vực công nghệ thông tin như : đưa ra vấn đề đèn hiệu, deadlock,đồ thị cấp phát tài nguyên RAG,.... Ông đã đoạt giải thưởng Turing.

NguyenThiThanhThuy(I11C)

Tổng số bài gửi : 10
Join date : 07/09/2011

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  dongocthien (I11C) on 9/11/2011, 13:20

Đè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 (xanh và đỏ), đè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).

dongocthien (I11C)

Tổng số bài gửi : 51
Join date : 27/08/2011

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

Về Đầu Trang Go down

Vấn đề đoạn tương tranh

Bài gửi  dongocthien (I11C) on 9/11/2011, 13:22

- Giả sử có n tiến trình(p0.p1,…,pn-1).mỗi tiến trình có đoạn mã gọi là đoạn tương tranh,trong đó tiến trình có thể truy cập và thay đổi vùng nhớ,tập tin hay tài nguyên chung.
- Tính loại trừ lẫn nhau hay loại trừ tương hỗ về phương diện thời gian:khi có 1 tiến trình ở 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 trong tại đoạn như vậy(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,Critical Section,Exit Section và các remainder Section.
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
}

dongocthien (I11C)

Tổng số bài gửi : 51
Join date : 27/08/2011

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

Về Đầu Trang Go down

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

Bài gửi  lengocthuthao89 (i11c) on 9/11/2011, 13:25

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

lengocthuthao89 (i11c)

Tổng số bài gửi : 50
Join date : 13/09/2011

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

Về Đầu Trang Go down

Ví dụ Đồng bộ hóa tiếntrình

Bài gửi  lengocthuthao89 (i11c) on 9/11/2011, 13:34

1.
Tiếntrìnhghi P:
while (true) {
while (counter==SIZE) ;
buf[in] = nextItem;
in = (in+1) % SIZE;
counter++;
}
buf: Buffer
SIZE: cỡ của buffer
counter: Biến chung

Tiếntrình đọc Q:
while (true) {
while (counter==0) ;
nextItem = buf[out];
out = (out+1) % SIZE
counter--;
}
z Đây là bài toán vùng
đệmcógiớihạn
2.
Các toán tử ++ và -- có thể được cài đặt như sau:
counter++
register1 = counter;
register1 = register1 + 1;
counter = register1;


counter--
register2 = counter;
register2 = register2 -1;
counter = register2;

P và Q có thể nhận được các giá trị khác nhau của
counter tại cùng 1 thời điểmnếunhưđoạnmã xanh
và đỏ thựchiệnxenkẽ nhau.

Giả sử P và Q thựchiện song song vớinhau
và giá trị của counter là 5:
register1 = counter; // register1=5
register1 = register1 + 1; // register1=6
register2 = counter; // register2=5
register2 = register2 -1; // register2=4
counter = register1; // counter=6 !!
counter = register2; // counter=4 !!

Lỗi: Cho phép P và Q đồng thờithao táctrên
biếnchungcounter. Sửalỗi:
register1 = counter; // register1=5
register1 = register1 + 1; // register1=6
counter = register1; // counter=6
register2 = counter; // register2=6
register2 = register2 -1; // register2=5
counter = register2; // counter=5


lengocthuthao89 (i11c)

Tổng số bài gửi : 50
Join date : 13/09/2011

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  PhamThiHoa-I91C on 10/11/2011, 01:29

tranphanhieu36_i11c đã viết:
NgoDucTuan (I11C) đã viết: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.


Chào bạn !
Đoạn code này trình bày về vấn đề thực thi đèn hiệu trong windows. Cụ thể là bài toán Producer-Consumer được đồng bộ bằng 2 đèn hiệu.

Đoạn code :
typedef int semaphore;
semaphore s = n;
wait (s);
signal (s);
là đoạn code theo định nghĩa nói về vấn đề này.

Còn đoạn code :
HANDLE s;
s=CreateSemaphore (0, n, max, t);
WaitForSingleObject (s, timeout);
ReleaseSemaphore (s, 1, NULL);
Là đoạn code cụ thể theo đoạn code định nghĩa ở trên được viết bằng C++

Mình sẽ giải thích song song cả hai đoạn code luôn, cũng như trong slide 7.14 đã chia làm 3 phần thì mình xin giải thích theo từng phần nha :

1. Đoạn code ở phần đầu ( 2 dòng đầu ) theo định nghĩa nói về tạo lập đèn hiệu và khởi tạo đèn hiệu.
typedef int semaphore; tạo 1 kiểu dữ liệu semaphore ( kiểu đèn hiệu, kiểu nguyên)
HANDLE s; ( Trong C++) cụ thể hơn là tạo 1 biến s ( coi như là semaphore) kiểu HANDLE(nhớ viết hoa hết nha) là kiểu mục quản đã được định nghĩa sẵn trong C++ bằng hàm thư viện
semaphore s = n;// tạo 1 biến s kiểu semaphore và gán dữ liệu đầu tiên cho nó lúc khởi tạo là n (đã cho trước)
s=CreateSemaphore (0, n, max, t); (Trong C++) gán giá trị khởi tạo cho biến s (kiểu HANDLE) bằng hàm CreateSemaphore() với 4 tham số bên trong là :
-1.Tham số đầu tiên bằng 0 không cần quan tâm
-2.Tham số thứ 2 là tham số truyền vào giá trị khởi tạo đầu tiên cho đèn hiệu (từ 0->max nha)
-3.Tham số thứ 3 là tham số max (giá trị tối đa được phép có của đèn hiệu)
-4.Tham số thứ 4 là tham số tên đèn hiệu (chuỗi ký tự nào đó hoặc là 0)
Nếu đặt nó là chuỗi ký tự thì s là Liên tiến trình
Nếu đặt nó là 0 thì nó là Nội tiến trình
Nếu bạn cần biết về liên tiến trình & nội tiến trình khác nhau chỗ nào thì bạn cứ hỏi sau nha !
Nói chung về đoạn code này là tạo đèn hiệu->Khởi tạo màu sắc đầu tiên cho đèn hiệu

2.Đoạn code thứ 2
wait(s);// Đây là hàm :
wait (semaphore s) { // s là kiểu semaphore ( hay còn gọi là đèn hiệu
while ( S <= 0 ); // chờ bận nếu s<=0 , (chờ bận nếu đèn đỏ )
S --; // Giảm s đi 1, khi bắt đầu thực hiện thì giảm màu đèn( có thể về màu thấp nhất hoặc màu thấp hơn)
}
Cụ thể trong C++
WaitForSingleObject (s, timeout);// đây là hàm tương đương chức năng với hàm wait bên trên với s là tên đèn truyền vào, và có thêm thông số thứ hai là timeout là thông số chờ với thời gian timeout(tính theo mili giây). Nều hết thời gian timeout mà đèn hiệu không bật thì vẫn thực thi đoạn code.
/* timeout = INFINITE (vô hạn) hoặc số mili giây chờ */

3.Đoạn code thứ 3
signal (s);// dưới đay là định nghĩa đơn giản hàm này
signal (semaphore S) {// tham số s là kiểu semaphore nha
S ++; // Tăng s lên 1, cũng như là đổi màu đèn hiệu khi thực hiện xong
}
Cụ thể trong C++
ReleaseSemaphore (s, 1, NULL);// Đây là hàm tương đương chức năng với hàm signal trên nhưng có thêm một số chức năng nâng cao.
-với thông đầu tiên ta truyền vào biến cụ thể kiểu HANDLE (ví dụ như là s ở trên) tương đương như là đèn hiệu cần tăng màu lên.
-với thông số thứ 2 là thông số số màu đèn hiệu cần tăng lên ( có thể 1, hay 2,3...)
-Thông số thứ 3 mình nghe thầy giảng là không dùng, cũng chẳng cần quan tâm, mà mình cũng chưa có thời gian để tìm hiểu. Bạn phải truyền vào nó là NULL hay 0 nha.

Admin: Tham số thứ 3 có thể là một biến nguyên v nào đó dùng để nhận giá trị của đèn hiệu trước khi tăng.

Đoạn code này mình nghĩ bạn nên nghĩ nó giống như ví dụ đèn giao thông của thầy, giờ mình phải đi học rồi nên nếu bạn cần sẽ gửi sau để bạn tìm hiểu kỹ hơn.
Với hàm wait() và signal() bạn nên tìm hiểu kỹ hơn trong định nghĩa lại ở slide 7.14 trong chương 7 tài liệu thầy gửi để rõ hơn nha. Trong slide đó hàm còn có thêm 1 số chức năng nữa đó.
Với 3 hàm cụ thể trong C++ nếu bạn muốn biết code trong nó là gì thì nhắn tin cho mình, mình sẽ gửi cho nha, Nhưng nếu bạn không có nhiều thời gian thì đầu tiên mình nghĩ là nên học cách sử dụng nó trước (như mình đã trình bày ở trên) rồi tìm hiểu kỹ sau.

Bài trả lời của mình nếu có gì sai sót hay thiếu gì thì mong thầy và các bạn bổ sung. Nhưng về cơ bản mình nghĩ là nó đúng, vì mình trình bày theo bài giảng của thầy trên lớp.
Cảm ơn bạn đã hỏi ! Smile
Bài giải thích code của bạn đầy đủ thật, cảm ơn bạn nhiều

PhamThiHoa-I91C

Tổng số bài gửi : 29
Join date : 16/09/2011

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  PhamThiHoa-I91C on 10/11/2011, 01:42

nguyenvulinh_i11c đã viết:1. Giới thiệu Trong cơ sở dữ liệu (CSDL) thời gian thực, điều khiển tương tranh không chỉ duy trì các ràng buộc nhất quán của CSDL mà còn thoả mãn các yêu cầu về thời gian của các giao tác truy nhập CSDL. Các thuật toán điều khiển tương tranh [6] và lập lịch [8] đã được nhiều người nghiên cứu ([6], [8]). Sự phát triển của giao thức khoá thời gian thực thường bao gồm lập lịch ưu tiên kết hợp giao thức khoá. Ví dụ, chúng ta có thể sử dụng khoá hai pha để điều khiển tương tranh và sử dụng thuật toán hạn sớm nhất (earliest deadline) để thiết kế các mức ưu tiên cho các giao tác. Rất tiếc, việc thực hiện này có thể dẫn đến không kiểm soát được sự đảo ngược mức ưu tiên, nghĩa là một giao tác có mức ưu tiên cao có thể sẽ phải đợi một giao tác có mức ưu tiên thấp hơn thời gian xác định.Ví dụ 1: Giả sử T1, T2, T3 là ba giao tác được sắp xếp theo thứ tự giảm dần của mức ưu tiên với T1 có mức ưu tiên cao nhất. Giả sử rằng T1 và T3 truy nhập cùng một dữ liệu X. Giả sử tại thời điểm t1 giao tác T3 nhận một khoá ghi trên X. Trong khi T3 đang thực hiện thì giao tác T1 có mức ưu tiên cao nhất đến và cố gắng nhận khoá đọc trên dữ liệu X. Giao tác T1 sẽ bị trì hoãn, vì dữ liệu X đang được ghi bởi T3. Chúng ta có thể cho rằng T1 là giao tác có mức ưu tiên cao nhất sẽ bị trì hoãn đến tận khi T3 hoàn thành và giải phóng khoá trên X. Tuy nhiên, khoảng trì hoãn có thể không tồn tại mãi, bởi vì giao tác T3 có thể nhận được ưu tiên cao của mức ưu tiên giao tác T2 khi T2 không cần truy nhập vào dữ liệu X. Sự ưu tiên cao của giao tác T3 làm cho T1 sẽ tiếp tục trì hoãn đến tận khi T2 và ngăn cản thực hiện của các giao tác khác. Khoảng trì hoãn trong ví dụ 1 có thể kéo dài tuỳ ý. Tình trạng này có thể khắc phục một phần nếu các giao tác không cho phép thay đổi được ưu tiên cao. Tuy nhiên giải pháp này chỉ thích hợp cho các giao tác thực hiện rất ngắn, bởi vì nó tạo ra sự không cần thiết phải trì hoãn. Ví dụ, một giao tác với mức ưu tiên thấp mà thực hiện lâu khi đó, một giao tác khác đòi hỏi truy nhập tới cùng tập dữ liệu có thể sẽ bị trì hoãn và như thế hệ thống sẽ không hiệu quả. Mục đích của bài báo này là xây dựng giao thức R/WPCP (Read/Write Priority Ceiling Protocol) quản lý mức ưu tiên để điều khiển tương tranh tránh được sự chết nghẽn (deadlock) và giảm sự trì hoãn làm cho hệ thống thực hiện hiệu quả hơn.2. Giao thức R/WPCP Trước tiên chúng tôi xin giới thiệu tóm lược một số khái niệm cơ sở liên quan đến giao thức R/WPCP (Read/Write Priority Ceiling Protocol).2.1. Khái niệm cơ bản CSDL gồm tập q các đối tượng dữ liệu (x, y, z) và tập T =(Ti, iÊ n) các giao tác. Mỗi giao tác có thể thực hiện trong CSDL ở thời điểm li không xác định trước. Khi thực hiện giao tác đó có thể đọc một số đối tượng dữ liệu, thực hoặc một số tính toán riêng và sau có thể thực hiện một số thao tác ghi trên cùng các đối tượng dữ liệu đó. Mỗi giao tác có thể đọc và ghi dữ liệu trong quá trình thực hiện . Mỗi giao tác sử dụng khóa hai pha phải yêu cầu các giao tác tham gia nhận tất cả các khoá trước khi giải phóng khoá. Một giao tác khi chưa giải phóng khoá đã chiếm giữ, nó không thể nhận một khoá mới. Hơn nữa chúng ta giả thiết rằng các giao tác sẽ thiết lập một mức ưu tiên theo thuật toán lập lịch. Với giao thức khoá hai pha và xác định mức ưu tiên chúng ta có thể gặp phải vấn đề không kiểm soát được việc đảo ngược mức ưu tiên như đã được trình ở trên. Tuy nhiên vấn đề này có thể được giải quyết bởi R/WPCP. Từ đó chúng ta có những nhận xét sau:Nhận xét 1: Luật thừa kế ưu tiên [7] trong ngữ cảnh của lịch ưu tiên cho phép một giao tác T có mức ưu tiên cao có thể ưu tiên cho giao tác có mức ưu tiên thấp thực hiện khi T bị trì hoãn bởi một giao tác khác. Luật kế thừa ưu tiên khảng định khi một giao tác T làm trì hoãn thực hiện giao tác có mức ưu tiên cao hơn, T sẽ thực hiện kế thừa tại mức ưu tiên cao nhất của tất cả các giao tác bị trì hoãn. Để làm rõ nhận xét này chúng ta xét các trường hợp ở ví dụ 1. Giả sử giao tác T1 bị trì hoãn bởi T3. Giao thức kế thừa mức ưu tiên yêu cầu giao tác T3 thực hiện giao tác tại mức ưu tiên của T1 đến tận khi nó giải phóng khoá trên được dữ liệu X. Như vậy, giao tác T2 sẽ không được ưu tiên hơn T3 một khi giao tác T3 giải phóng khoá trên dữ liệu X. T3 trở về xác định mức của nó và ngay lập tức được ưu tiên bởi T1. Như vậy kế thừa ưu tiên sẽ giảm thời gian trì hoãn của các giao tác có mức ưu tiên cao nhất.Nhận xét 2: Để kiểm soát được thứ tự ưu tiên của các giao tác, chúng ta sử dụng ba tham biến cho mỗi dữ liệu trong CSDL để quản lý: - mức ưu tiên ghi cao nhất WCeil(X) là mức ưu tiên của giao tác ưu tiên cao nhất có thể ghi X. - mức ưu tiên tuyệt đối cao nhất ACeil (X) là mức ưu tiên của giao tác ưu tiên cao nhất có thể đọc hoặc ghi X. - mức ưu tiên R/W cao nhất RWCeil (X) là ưu tiên Read Write cao nhất đối với dữ liệu X được xác định tại thời điểm chạy. Giao tác T không thể có khoá đọc (ghi) đối với dữ liệu và thực hiện các thao tác của nó nếu mức ưu tiên của giao tác T không cao hơn mức ưu tiên cao nhất RWCeil (X). Chúng ta gọi đây là luật cao nhất (Ceil Rule). Để hiểu rõ luật này chúng ta ký hiệu như sau: Sysceili chỉ ra mức ưu tiên cao nhất(RWCeil(X)) trong số tất cả các giao tác Ti khoá X. Sysceili cũng được xác định động trong mỗi lần chạy khi Ti yêu cầu khoá một dữ liệu. Pi là mức ưu tiên của giao tác Ti. Trong thuật toán, điều kiện để điều khiển giao tác truy nhập dữ liệu là giao tác Ti không thể có khoá đọc (ghi) một dữ liệu X trừ khi mức ưu tiên của nó cao hơn Sysceili, nghĩa là Pi > Sysceili. Theo luật cao nhất, nếu một giao tác có Write-Lock trên dữ liệu X, khi đó X không thể được đọc/ghi bởi các giao tác khác. Để đảm bảo điều kiện này, chúng ta đặt RWCeil(X) = ACeil(X). Vì ACeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể đọc (ghi) dữ liệu X, nó ngăn cản các giao tác khác từ việc đọc (ghi) trên dữ liệu X đến tận khi khoá trên X được giải phóng. Khi một giao tác có khoá đọc dữ liệu X, chúng ta đặt RWCeil (X) bằng WCeil (X) vì WCeil (X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi X, nó ngăn cản những giao tác khác từ việc ghi dữ liệu X theo luật cao nhất. Tuy nhiên các giao tác đọc với mức ưu tiên cao hơn WCeil (X) có thể chia sẻ khoá đọc trên X. Tính chất quan trọng của giao thức này là ngăn cấm các giao tác đọc với mức ưu tiên thấp hơn hoặc bằng mức ưu tiên Wceil (X) để chia sẻ khoá đọc trên X. Trong trường hợp khác, các giao tác đọc với mức ưu tiên thấp hơn hoặc bằng mức ưu tiên ghi cao nhất thì không thể chia sẻ khoá đọc trên dữ liệu. Nếu chúng ta cho phép các giao tác đọc với mức ưu tiên thấp chia sẻ khoá đọc dữ liệu, khi đó một giao tác ghi có mức ưu tiên cao cần ghi đối với dữ liệu X thì giao tác đó phải đợi các giao tác đọc khác đang thực hiện. Nghĩa là một giao tác có thể bị trì hoãn bởi nhiều giao tác có mức ưu tiên thấp hơn. Việc quản lý mức ưu tiên mục đích của RWCeil (X) đảm bảo mỗi giao tác thực hiện tại mức ưu tiên cao hơn mức ưu tiên mà có thể được kế thừa bởi các giao tác ưu tiên. Khi một giao tác T có khoá ghi một dữ liệu X, RWCeil (X) thể hiện mức ưu tiên cao nhất mà T có thể kế thừa qua X. Ví dụ khi T có khoá ghi trên X, nó có thể làm trì hoãn giao tác có mức ưu tiên cao nhất mà giao tác đó có thể đọc (ghi) X và vì thế T sẽ kế thừa mức ưu tiên của TH. Do đó, RWCeil (X) khi ghi được định nghĩa bằng ACeil (X). Ngoài ra, khi T là một giao tác với mức ưu tiên thấp giữ một khoá đọc trên đối tượng dữ liệu X và giao tác T có mức ưu tiên cao nhất có thể yêu cầu một khoá ghi trên X. Giao tác T có thể trì hoãn Tw và kế thừa mức ưu tiên của Tw. Từ đó, RWCeil (X) khi đọc sẽ được xác định là WCeil (X). Với R/WPCP, một giao tác T không thể nhận một khoá và thực hiện trừ khi mức ưu tiên của giao tác cao hơn tất cả RWCeil (X). Vì mức ưu tiên cao nhất RWCeil(X) là mức ưu tiên cao nhất tại thời điểm hiện tại giao tác có thể thực hiện. Sự điều phối thứ tự ưu tiên của các giao tác đưa đến một số tính chất thú vị: giao thức R/WPCP có thể giúp tránh được deadlock và có thể trì hoãn duy nhất một lần. Ví dụ 2: Giả sử rằng chúng ta có 3 giao tác T0ư, T1, T2 sắp xếp theo thứ tự ưu tiên giảm dần. Cũng giả thiết rằng chúng truy nhập dữ liệu (X1, X2, X3) như sau: T0 = {.., Write lock (X0), Unlock (X0),..} T1 = {.., Read lock (X1), Write lock (X2),.., Unlock (X2), Unlock (X1),..} T2 = {.., Read lock (X2), Write lock (X1),.., Unlock (X1), Unlock (X2),..} Đầu tiên chúng ta thiết lập mức ưu tiên cho mỗi dữ liệu như sau: WCeil (X1) và ACeil(X1) là mức ưu tiên của T2 và T1 tương ứng là P2 và P1. WCeil (X2) và ACeil (X2) bằng P1. WCleil (X0) và ACeil (X0) bằng P0. Tại thời điểm to, T2 bắt đầu thực hiện. Tại thời điểm t1, T2 thực hiện Readlock (X2) và RWCeil (X2) đặt bằng WCeil (X2) và bằng P1. Khi nhận được khoá dữ liệu X2, thì T2 bắt đầu thực hiện. Tại thời điểm này giao tác T1 khởi tạo và có mức ưu tiên cao hơn. Khi T1 thực hiện Read lock (X1) tại thời điểm t2 nhưng hệ thống không thể chia sẻ. Theo lịch chúng ta thấy rằng T1 có mức ưu tiên là P1 không cao hơn RWCeil (X2) (đã được ký hiệu cũng bằng P1). Do đó, bộ lập lịch này sẽ làm trì hoãn giao tác T1 và bỏ qua sự đòi hỏi lock (X1) như vậy T1 bị trì hoãn bởi T2. Giao tác T2 bây giờ kế thừa mức ưu tiên của T1 và lại tiếp tục thực hiện. Vì T1 bị từ chối khi nhận khoá trên dữ liệu X1 và bị trì hoãn dẫn đến xảy ra deadlock. Nhưng khả năng deadlock giữa T1 và T2 được ngăn cản nếu T1 đã được nhận khoá trên dữ liệu X1 thì T1 có thể đợi cho tới tận khi T2 giải phóng khoá trên dữ liệu X2, ngoài ra T2 cũng có thể đợi T1 giải phóng khoá trên X1. Một trường hợp khác, giả sử rằng tại thời điểm t3, trong khi T2 vẫn đang trong việc thực hiện các thao tác của chúng thì giao tác To có mức ưu tiên cao nhất đến và cố gắng nhận một khoá ghi dữ liệu Xo. Vì mức ưu tiên của To cao hơn RWCeil (X2) nên giao tác To sẽ tiếp tục thực hiện các công việc của nó và vì thế T2 bị trì hoãn. Tại thời điểm t4, To hoàn thành việc thực hiện và T2 tiếp tục được thực hiện (vì T1 đã bị trì hoãn bởi T2). Giao tác T2 tiếp tục thực hiện đọc trên dữ liệu X2 và nhận khoá ghi trên dữ liệu X1. Tại thời điểm t5, T2 giải phóng X1. Tại thời điểm t6 khi T2 giải phóng X2. T1 có mức ưu tiên cao hơn T2 vì thế nó nhận được khoá và thực hiện hoàn thành. Cuối cùng T2 tiếp tục thực hiện cho đến khi hoàn thành. Chú ý: To không bao giờ bị trì hoãn. Giao tác T1 đã bị trì hoãn bởi giao tác T2 có mức ưu tiên thấp hơn trong khoảng [t2, t3] và [t4, t6]. Tuy nhiên, hai khoảng đó tương đương với khoảng mà T2 cần khoá trên hai dữ liệu X2 và X1. Vì vậy khoảng trì hoãn của T1 bằng khoảng thực hiện giao tác của giao tác T2 có mức ưu tiên thấp hơn. Như vậy tính chất của giao tác này là mỗi giao tác T có thể bị trì hoãn tại duy nhất một giao tác có mức ưu tiên thấp hơn đến tận khi giao tác làm cho trì hoãn tạm ngưng chính nó hoặc hoàn thành.2.2. Định nghĩa và các tính chất của giao thức R/WPCP Giả thiết rằng chúng ta đưa ra trong mô hình CSDL tập trung, tập các giao tác truy nhập theo thứ tự FCFS, và một giao tác không thể nhận khoá trên một dữ liệu khi nó đã có khoá và không xảy ra deadlock với chính khoá đó, và cũng không có các khóa đọc ( ghi) có thể được thực hiện trên một dữ liệu. Ký hiệu: các giao tác có thứ tự {T1..Tn} theo mức ưu tiên giảm dần, với T1 có mức ưu tiên cao nhất. Ti là giao tác thứ i, Pi chỉ mức ưu tiên của giao tác Ti. Định nghĩa 4: Chúng ta sử dụng ký hiệu dữ liệu trong cơ sở dữ liệu như là một bộ của CSDL quan hệ. Một khoá có thể là khoá đọc (ghi). Một giao tác T giữ khoá đọc (ghi) trên dữ liệu X ta nói rằng có khoá đọc (ghi) trên dữ liệu X. Mức ưu tiên cao nhất của dữ liệu, Write Priority Ceiling (WCeil(X)) được định nghĩa là mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi dữ liệu X. ACeil (X) là mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể đọc(ghi) dữ liệu X. Khi một dữ liệu X có khoá ghi, RWCeil(X) được định nghĩa bằng ACeil(X). Khi một đơn vị dữ liệu X có khoá đọc, RWCeil(X) được định nghĩa bằng WCeil(X). Chúng ta định nghĩa R/WPCP như sau: 1. Giao tác T là một giao tác có mức ưu tiên cao nhất đang thực hiện trên bộ vi xử lý được xác định. Trước khi giao tác T có thể đọc (ghi) dữ liệu X khi đó T phải nhận khoá đọc (ghi) trên dữ liệu X, các giao tác phải thoả mãn giao thức khoá hai pha và tất cả các khoá sẽ đựơc giải phóng tại thời điểm kết thúc của các giao tác. 2. Ký hiệu X* là dữ liệu với mức ưu tiên cao nhất của tất cả các dữ liệu có khoá được giữ bởi các giao tác khác giao tác T (RWCeil(X*)). Khi giao tác T nhận khoá trên dữ liệu X. T sẽ bị trì hoãn và khoá trên dữ liệu X sẽ bị từ chối, nếu mức ưu tiên của giao tác T không cao hơn mức ưu tiên RWCeil(X*). Trong trường hợp này, giao tác T sẽ bị trì hoãn bởi giao tác đang giữ khoá trên X*. Nếu giao tác T có mức ưu tiên cao hơn RWCeil(X*) thì T nhận khoá trên X. Dưới điều kiện này sẽ không có xung đột đọc ghi trên dữ liệu X, và chúng ta không cần kiểm tra nếu X đã có khoá. 3. Nếu giao tác T làm trì hoãn các giao tác có mức ưu tiên cao hơn khi đó T sẽ kế thừa mức ưu tiên PH là mức ưu tiên cao nhất của giao tác bị trì hoãn bởi T. Ví dụ nếu một giao tác T3 có mức ưu tiên thấp làm trì hoãn một giao tác T2 có mức ưu tiên trung bình và T2 làm trì hoãn giao tác T1 có mức ưu tiên cao nhất thì giao tác T2 đầu tiên sẽ kế thừa mức ưu tiên của T1. Tiếp theo T3 sẽ kế thừa mức ưu tiên của T1 từ T2. 4. Khi giao tác T không thực hiện thì có thể luôn ưu tiên các giao tác khác thực hiện tại mức ưu tiên thấp. Nhận xét: Dưới giao thức này, chúng ta không cần kiểm tra xung đột đọc ghi, ví dụ khi một dữ liệu X được nhận khoá ghi của giao tác T, RWCeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể truy nhập X. Vì vậy giao tác này sẽ bị trì hoãn bởi một giao tác có mức ưu tiên cao có thể ghi (đọc) dữ liệu X. Trường hợp khác, giả sử rằng, dữ liệu X nhận khoá đọc của giao tác T chiếm giữ thì RWCeil(X) bằng mức ưu tiên của giao tác có mức ưu tiên cao nhất có thể ghi dữ liệu X. Vì vậy, giao tác ghi dữ liệu X sẽ có mức ưu tiên không lớn hơn mức ưu tiên RWCeil sẽ bị trì hoãn. Chỉ những giao tác đọc X và có mức ưu tiên cao hơn giao tác RWCeil sẽ được phép đọc khoá trên X. Dưới R/WPCP Dead lock không thể xảy ra và mỗi giao tác có thể bị trì hoãn duy nhất một lần. Sau đây chúng ta sẽ chứng minh các tính chất của R/WPCP.2.3. Chứng minh các tính chất Bổ đề 1: Dưới R/WPCP, mỗi giao tác sẽ thực hiện tại một mức ưu tiên cao hơn mức ưu tiên mà các giao tác được ưu tiên có thể kế thừa. Chứng minh: Từ định nghĩa của R/WPCP khi một giao tác T giữ khoá của một dữ liệu, mức ưu tiên cao nhất T có thể kế thừa bằng mức ưu tiên cao nhất RWCeil của giao tác khoá dữ liệu. Vì vậy khi một giao tác TH có mức ưu tiên cao hơn mức ưu tiên cao nhất RWCeil của dữ liệu được khoá bởi giao tác T, giao tác Th sẽ thực hiện tại mức ưu tiên cao hơn mức ưu tiên mà các giao tác được ưu tiên có thể kế thừa.Định lý 1: Giao thức R/WPCP tránh được chết nghẽn (Deadlock). Chứng minh: Giả sử Deadlock xảy ra . Ký hiệu: P là mức ưu tiên cao nhất của tất cả các giao tác được liên quan trong Deadlock. Sự chuyển mức ưu tiên kế thừa do đó tất cả các giao tác liên quan trong Deadlock cuối cùng sẽ thừa kế cùng mức ưu tiên cao nhất P. Điều này trái với bổ đề 1. Chúng ta giả sử rằng một thao tác chính nó sẽ không bị trì hoãn trong khi thực hiện. Nghĩa là nếu một thao tác T chỉ là một giao tác trong một bộ xử lý và nếu T đã thực hiện khi đó T sẽ chạy đến tận khi hoàn thành. Dưới giả thiết này, chúng ta thấy rằng một giao tác T có thể bị trì hoãn một lần bởi giao tác TL có mức ưu tiên thấp hơn. Tiếp theo, chúng ta chứng minh rằng giao tác có thể bị trì hoãn ít nhất một lần nếu có nhiều giao tác với mức ưu tiên thấp.Bổ đề 2: Giao thức R/WPCP, trong suốt quá trình thực hiện của giao tác T hoặc chính nó bị trì hoãn hoặc T có thể bị trì hoãn duy nhất một lần bởi một hoặc nhiều giao tác có mức ưu tiên thấp hơn. Chứng minh: Giả sử rằng giao tác T bị trì hoãn bởi giao tác TL có mức ưu tiên thấp. Theo định lý 1, sẽ không có Deadlock và vì thế giao tác TL sẽ tồn tại ở một số thời điểm ví dụ t1. Tại thời điểm t1, TL được kế thừa mức ưu tiên của T. Vì TL không thể đợi lâu nó có thể kế thừa một mức ưu tiên cao hơn mức ưu tiên của chính nó. Tuy nhiên TL không thể thực hiện chạy đến tận khi T hoàn thành hoặc chính nó bị trì hoãn.Định lý 2: Dưới R/WPCP một giao tác T có thể bị trì hoãn duy nhất một lần bởi các giao tác có mức ưu tiên thấp hơn đến tận khi T thực hiện xong hoặc chính nó bị trì hoãn. Chứng minh: Giả sử rằng T bị trì hoãn bởi n giao tác có mức ưu tiên thấp hơn. Do bổ đề 2, T bị trì hoãn bởi n giao tác có mức ưu tiên thấp hơn T1, T2,.., Tn. ở đây mức ưu tiên của Ti được giả thiết cao hơn hoặc bằng Ti+1. Dưới giao thức này, một giao tác có thể luôn luôn được ưu tiên bởi một giao tác có mức ưu tiên cao hơn. Vì thế, giao tác có mức ưu tiên thấp không thể làm trì hoãn giao tác có mức ưu tiên cao hơn. Do đó các giao tác và T1..Tn phải được thực hiện. Giả thiết T bị trì hoãn bởi Tn và Tn kế thừa mức ưu tiên của T. Vì T có thể bị trì hoãn bởi Tn, mức ưu tiên của giao tác T không thể cao hơn mức ưu tiên cao nhất P mà có thể được kế thừa từ Tn. Một trường hợp khác, theo bổ đề 1, mức ưu tiên của Tn -1 cao hơn P. Suy ra mức ưu tiên của Tn-1 cao hơn mức ưu tiên của giao tác T. Điều này trái với giả thiết mức ưu tiên của T cao hơn mức ưu tiên T1, T2,.., Tn. Định lý được chứng minh.3. Kết luận Trong bài báo chúng tôi đã giới thiệu các tính chất của giao thức R/WPCP. Đây là giao thức kết hợp giữa 2PL với lịch điều khiển mức ưu tiên thời gian thực. Sau đó chúng tôi đã chứng minh giao thức này giúp giải quyết được vấn đề chết nghẽn (Deadlock) của hệ thống và có thể bị trì hoãn duy nhất một lần bởi các giao tác có mức ưu tiên thấp hơn. Bài báo này đóng góp một phần trong việc phát triển các giao thức điều khiển tương tranh mới trong CSDL thời gian thực.Tài liệu tham khảo[1] A Bestavros, J.lin and Sany Hyuk Son, Real Time Database Systems: Issuse and Application, Kluwer Academic publishers, 1997. Đoàn Văn Ban, Hồ Văn Hương, Đặc tả hình thức điều khiển tương tranh trong cơ sở dữ liệu thời gian thực. Hội thảo Quốc gia công nghệ thông tin, Huế, 6 - 2000. Đoàn Văn Ban, Hồ Văn Hương, A Formal Verification of the Concurrency Control in Duration Calculus. Conference at Institute of Mathematics, 8 - 2000. Đoàn Văn Ban, Hồ Văn Hương, Tính nhất quán lâm thời trong cơ sở dữ liệu thời gian thực, xemina tháng 10-2000, Khoa Toán Cơ Tin, Đại học khoa học tự nhiên. Đoàn Văn Ban, Hồ Văn Hương, Lịch giao tác với các ràng buộc thời gian, Conference at Hue University, 4-2001. J. R. Haritsa, M. J. Carey, and M. Livny, “Data Access Scheduling in Firm Real Time Database Systems``, The Journal of Real Time Systems, 4, pp. 203 241, 1992. Lui Sha at all, ” Priority Inheritance Protocol: An Approach to Real Time Synchronization”, IEEE, 1990. R. Abbott and H. Garcia Molina, Scheduling Real Time Transactions: A Performance Evaluation``, ACM Transaction on Database System, Vol 17, N3, 1992.
Bài của bạn cũng tương đối hay nhưng đọc không nỗi vì không được chọn lọc và trình bày không biết chỗ nào

PhamThiHoa-I91C

Tổng số bài gửi : 29
Join date : 16/09/2011

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

Về Đầu Trang Go down

Ví dụ đồng bộ hóa (3),(4)

Bài gửi  TRANTHINHPHAT (I11C) on 10/11/2011, 10:44

Ví dụ đồng bộ hóa (3)
Giả sử P và Q thực hiện song song với nhau
và giá trị của counter là 5:
register1 = counter; // register1=5
register1 = register1 + 1; // register1=6
register2 = counter; // register2=5
register2 = register2 - 1; // register2=4
counter = register1; // counter=6 !!
counter = register2; // counter=4 !!

Ví dụ đồng bộ hóa (4)
Lỗi: Cho phép P và Q đồng thời thao tác trên
biến chung counter. Sửa lỗi:
register1 = counter; // register1=5
register1 = register1 + 1; // register1=6
counter = register1; // counter=6
register2 = counter; // register2=6
register2 = register2 - 1; // register2=5
counter = register2; // counter=5

TRANTHINHPHAT (I11C)

Tổng số bài gửi : 52
Join date : 29/08/2011
Age : 27
Đến từ : THU DAU MOT, BINH DUONG

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

Về Đầu Trang Go down

Nhu cầu đồng bộ hóa

Bài gửi  DangMinhQuang(I11C) on 10/11/2011, 10:45

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 đó …

DangMinhQuang(I11C)

Tổng số bài gửi : 9
Join date : 05/09/2011

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

Về Đầu Trang Go down

Ví dụ giải pháp của Peterson

Bài gửi  TRANTHINHPHAT (I11C) on 10/11/2011, 10:48

Ví dụ 1
Giả sử có 2 tiến trình P0 và P1 với hai đoạn
mã găng tương ứng CS0 và CS1
Sử dụng một biến nguyên turn với giá trị khởi
tạo 0 hoặc 1 và mảng boolean flag[2]
turn có giá trị i có nghĩa là Pi được phép thực
hiện CSi (i=0,1)
nếu flag[i] là TRUE thì tiến trình Pi đã sẵn
sàng để thực hiện CSi

Ví dụ 2
Mã lệnh của Pi:
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j) ;
CSi;
flag[j] = FALSE;
REMAINi;
} while (1);

TRANTHINHPHAT (I11C)

Tổng số bài gửi : 52
Join date : 29/08/2011
Age : 27
Đến từ : THU DAU MOT, BINH DUONG

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

Về Đầu Trang Go down

Cài đặt semaphore theo cấu trúc

Bài gửi  TRANTHINHPHAT (I11C) on 10/11/2011, 10:54



- Khắc phục chờ bận: Chuyển vòng lặp chờ
thành việc sử dụng toán tử block (tạm dừng)
- Để khôi phục thực hiện từ block, ta có toán tử
wakeup
- Khi đó để cài đặt, ta có cấu trúc dữ liệu mới
cho semaphore:
typedef struct {
int value; // Giá trị của semaphore
struct process *L; // Danh sách tiến trình chờ...
} semaphore;

*

void wait(semaphore *S)
{
S->value--;
if (S->value<0) {
Thêm tiến trình gọi
toán tử vào s->L;
block();
}
}

*
void signal(semaphore *S)
{
S->value++;
if (S->value<=0) {
Xóa một tiến trình P
ra khỏi s->L;
wakeup(P);
}
}

TRANTHINHPHAT (I11C)

Tổng số bài gửi : 52
Join date : 29/08/2011
Age : 27
Đến từ : THU DAU MOT, BINH DUONG

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  LeThanhHai27(I11C) on 3/12/2011, 13:31

tranphanhieu36_i11c đã viết:
NgoDucTuan (I11C) đã viết: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.


Chào bạn !
Đoạn code này trình bày về vấn đề thực thi đèn hiệu trong windows. Cụ thể là bài toán Producer-Consumer được đồng bộ bằng 2 đèn hiệu.

Đoạn code :
typedef int semaphore;
semaphore s = n;
wait (s);
signal (s);
là đoạn code theo định nghĩa nói về vấn đề này.

Còn đoạn code :
HANDLE s;
s=CreateSemaphore (0, n, max, t);
WaitForSingleObject (s, timeout);
ReleaseSemaphore (s, 1, NULL);
Là đoạn code cụ thể theo đoạn code định nghĩa ở trên được viết bằng C++

Mình sẽ giải thích song song cả hai đoạn code luôn, cũng như trong slide 7.14 đã chia làm 3 phần thì mình xin giải thích theo từng phần nha :

1. Đoạn code ở phần đầu ( 2 dòng đầu ) theo định nghĩa nói về tạo lập đèn hiệu và khởi tạo đèn hiệu.
typedef int semaphore; tạo 1 kiểu dữ liệu semaphore ( kiểu đèn hiệu, kiểu nguyên)
HANDLE s; ( Trong C++) cụ thể hơn là tạo 1 biến s ( coi như là semaphore) kiểu HANDLE(nhớ viết hoa hết nha) là kiểu mục quản đã được định nghĩa sẵn trong C++ bằng hàm thư viện
semaphore s = n;// tạo 1 biến s kiểu semaphore và gán dữ liệu đầu tiên cho nó lúc khởi tạo là n (đã cho trước)
s=CreateSemaphore (0, n, max, t); (Trong C++) gán giá trị khởi tạo cho biến s (kiểu HANDLE) bằng hàm CreateSemaphore() với 4 tham số bên trong là :
-1.Tham số đầu tiên bằng 0 không cần quan tâm
-2.Tham số thứ 2 là tham số truyền vào giá trị khởi tạo đầu tiên cho đèn hiệu (từ 0->max nha)
-3.Tham số thứ 3 là tham số max (giá trị tối đa được phép có của đèn hiệu)
-4.Tham số thứ 4 là tham số tên đèn hiệu (chuỗi ký tự nào đó hoặc là 0)
Nếu đặt nó là chuỗi ký tự thì s là Liên tiến trình
Nếu đặt nó là 0 thì nó là Nội tiến trình
Nếu bạn cần biết về liên tiến trình & nội tiến trình khác nhau chỗ nào thì bạn cứ hỏi sau nha !
Nói chung về đoạn code này là tạo đèn hiệu->Khởi tạo màu sắc đầu tiên cho đèn hiệu

2.Đoạn code thứ 2
wait(s);// Đây là hàm :
wait (semaphore s) { // s là kiểu semaphore ( hay còn gọi là đèn hiệu
while ( S <= 0 ); // chờ bận nếu s<=0 , (chờ bận nếu đèn đỏ )
S --; // Giảm s đi 1, khi bắt đầu thực hiện thì giảm màu đèn( có thể về màu thấp nhất hoặc màu thấp hơn)
}
Cụ thể trong C++
WaitForSingleObject (s, timeout);// đây là hàm tương đương chức năng với hàm wait bên trên với s là tên đèn truyền vào, và có thêm thông số thứ hai là timeout là thông số chờ với thời gian timeout(tính theo mili giây). Nều hết thời gian timeout mà đèn hiệu không bật thì vẫn thực thi đoạn code.
/* timeout = INFINITE (vô hạn) hoặc số mili giây chờ */

3.Đoạn code thứ 3
signal (s);// dưới đay là định nghĩa đơn giản hàm này
signal (semaphore S) {// tham số s là kiểu semaphore nha
S ++; // Tăng s lên 1, cũng như là đổi màu đèn hiệu khi thực hiện xong
}
Cụ thể trong C++
ReleaseSemaphore (s, 1, NULL);// Đây là hàm tương đương chức năng với hàm signal trên nhưng có thêm một số chức năng nâng cao.
-với thông đầu tiên ta truyền vào biến cụ thể kiểu HANDLE (ví dụ như là s ở trên) tương đương như là đèn hiệu cần tăng màu lên.
-với thông số thứ 2 là thông số số màu đèn hiệu cần tăng lên ( có thể 1, hay 2,3...)
-Thông số thứ 3 mình nghe thầy giảng là không dùng, cũng chẳng cần quan tâm, mà mình cũng chưa có thời gian để tìm hiểu. Bạn phải truyền vào nó là NULL hay 0 nha.

Admin: Tham số thứ 3 có thể là một biến nguyên v nào đó dùng để nhận giá trị của đèn hiệu trước khi tăng.

Đoạn code này mình nghĩ bạn nên nghĩ nó giống như ví dụ đèn giao thông của thầy, giờ mình phải đi học rồi nên nếu bạn cần sẽ gửi sau để bạn tìm hiểu kỹ hơn.
Với hàm wait() và signal() bạn nên tìm hiểu kỹ hơn trong định nghĩa lại ở slide 7.14 trong chương 7 tài liệu thầy gửi để rõ hơn nha. Trong slide đó hàm còn có thêm 1 số chức năng nữa đó.
Với 3 hàm cụ thể trong C++ nếu bạn muốn biết code trong nó là gì thì nhắn tin cho mình, mình sẽ gửi cho nha, Nhưng nếu bạn không có nhiều thời gian thì đầu tiên mình nghĩ là nên học cách sử dụng nó trước (như mình đã trình bày ở trên) rồi tìm hiểu kỹ sau.

Bài trả lời của mình nếu có gì sai sót hay thiếu gì thì mong thầy và các bạn bổ sung. Nhưng về cơ bản mình nghĩ là nó đúng, vì mình trình bày theo bài giảng của thầy trên lớp.
Cảm ơn bạn đã hỏi ! Smile

Bài của bạn giái thích khá chi tiết, cảm ơn bạn nhé.

LeThanhHai27(I11C)

Tổng số bài gửi : 16
Join date : 01/09/2011

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

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