Thảo luận Bài 7

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.

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

Admin
Môn học dùng từ "Luồng" thay cho "Tuyến" và "Tiểu trình" !

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

Mục đích của đồng bộ hóa công việc các tiến trình nhầm đảm bảo các tiến trình làm việc nhất quán, chờ lẫn nhau, sử dụng chung tài nguyên và tránh được hiện tượng kẹt tiến trình.

VD:
- có 2 bạn, bạn A đang làm bài tập, B rủ A đi chơi, để đồng bộ thì B phải chờ cho A làm bài xong rồi cùng đi chơi
- Cả lớp là tiến trình nặng, mỗi người là tiến trình nhẹ, thầy gọi 1 bạn lên bảng giải bài tập, muốn gọi bạn tiếp theo lên thì phải đợi bạn trước làm xong
VD trường hợp vi phạm nhất quán.
-Khi A đang soạn đơn xin việc và B lại sửa tên, bạn X chụp lại bảng => ghi tên và ký tên khác nhau => vi phạm nhất quán

Để loại bỏ các bất tiện của của giải pháp chờ đợi bận, chúng ta có thể tiếp cận
theo hướng cho một quá trình chưa đủ điều kiện vào miền tương trục chuyển sang
trạng thái nghẽn, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng
các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái quá trình. Hai thủ tục cơ
bản SLEEP và WAKEUP thường được sử dụng cho mục đích này.
SLEEP là một lời gọi hệ thống có tác dụng làm “nghẽn” (blocked) hoạt động
của quá trình gọi nó và chờ đến khi được một tiến trình khác “đánh thức”. Lời gọi hệ
thống WAKEUP nhận một tham số duy nhất: quá trình sẽ được kích hoạt trở lại (đặt
về trạng thái sẳn sàng).
Ý tưởng sử dụng SLEEP và WAKEUP như sau: khi một quá trình chưa đủ
điều kiện vào miền tương trục, nó gọi SLEEP để tự khoá đến khi có một quá trình
khác gọi WAKEUP để giải phóng nó. Một quá trình gọi WAKEUP khi ra khỏi miền
tương trục để đánh thức một quá trình đang chờ, tạo cơ hội cho quá trình này vào
miền tương trục.
int busy; // 1 nếu miền tương trục đang bị chiếm
int blocked; // đếm số lượng quá trình đang bị khoá
do{
if (busy) {
blocked = blocked + 1;
sleep();
}
else busy = 1;
}while (1);
Critical section
busy = 0;
if (blocked){
wakeup(process);
blocked = blocked -1;
}
Remainder section
Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy
ra tình trạng mâu thuẩn truy xuất trong một vài tình huống như sau: giả sử quá trình A
vào miền tương trục, và trước khi nó rời miền tương trục thì quá trình B được kích
hoạt. Quá trình B thử vào miền tương trục nhưng nó nhận thấy A đang ở trong đó, do
vậy B tăng giá trị biến blocked lên 1 và chuẩn bị gọi SLEEP để tự nghẽn. Tuy nhiên,
trước khi B có thể thực hiện SLEEP, quá trình A được kích hoạt trở lại và ra khỏi
miền tương trục. Khi ra khỏi miền tương trục, quá trình A nhận thấy có một quá trình
đang chờ (blocked=1) nên gọi WAKEUP và giảm giá trị blocked xuống 1. Khi đó tín
hiệu WAKEUP sẽ lạc mất do quá trình B chưa thật sự “ngủ” để nhận tín hiệu đánh
thức! Khi quá trình B được tiếp tục xử lý, nó mới gọi SLEEP và tự nghẽn vĩnh viễn!
Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra trạng thái
miền tương trục và việc gọi SLEEP hay WAKEUP là những hành động tách biệt, có
thể bị ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến
một quá trình chưa bị nghẽn sẽ lạc mất. Để tránh những tình huống tương tự, hệ điều
hành cung cấp những cơ chế đồng bộ hoá dựa trên ý tưởng của chiến lược “SLEEP
and WAKEUP” nhưng chưa được xây dựng bao gồm cả phương tiện kiểm tra điều
kiện vào miền tương trục giúp sử dụng an toàn.

Admin
Bài này thuộc dạng Copy-Paste, quá "lý thuyết và rắc rối" mà thực chất mọi thứ đơn giản thôi, do đó cần diễn đạt lại cho đúng với những gì đã học !

Tiếp cận Semaphore được. Dijkstra đề xuất vào năm 1965. Một semaphore S
là một biến số nguyên (integer) được truy xuất chỉ thông qua hai thao tác nguyên tử:
wait và signal. Các thao tác này được đặt tên P (cho wait - chờ để kiểm tra) và V (cho
signal- báo hiệu để tăng). Định nghĩa cơ bản của wait trong mã giả là:
wait(S){
while (S≤0)
;//no-op
S--;
}
Định nghĩa cơ bản của signal trong mã giả là
signal(S){
S++;
}
Những sửa đổi đối với giá trị integer của semaphore trong các thao tác wait và
signal phải được thực thi không bị phân chia. Nghĩa là khi một quá trình sửa đổi giá
trị semaphore, không có quá trình nào cùng một lúc có thể sửa đổi cùng biến
semaphore đó. Ngoài ra, trong trường hợp của biến wait(S), kiểm tra giá trị integer
của S (S ≤ 0) và sửa đổi có thể của nó (S--) cũng phải được thực thi mà không bị ngắt.

Đoạn tương tranh và Loại trừ lẫn nhau là gì??? Đoạn tương tranh có phải là vùng tranh chấp không? Giải thích

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

LƯU Ý: ĐOẠN TƯƠNG TRANH KHÁC VÙNG TRANH CHẤP VÌ ĐOẠN TƯƠNG TRANH LÀ ĐOẠN MÃ KHI THỰC HIỆN THÌ NÓ ẢNH HƯỞNG ĐẾN VÙNG TRANH CHẤP

Admin
"Lưu ý" tốt. Chứng tỏ có nghe giảng. Thêm ví dụ minh hoạ thì thuyết phục hơn nữa !

- Tranh duoc hien tuong dealock
- Dam bao tinh nhat quan trong viec dung chung tai nguyen
VD: Ban A su dung bang viet ten minh la Nguyen Van A. Nhung ban chi viet toi Nguyen van. Mot ban khac su dung phan bang do viet ten minh la Tran Van B. ban B viet de len phan bang cua ban A. vi vay ko doc duoc ten ban A. Do do phai dong bo hoa tien trinh de tranh tinh trang do

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

Lý do:
- Đảm bảo tính nhất quán của tài nguyên dùng chung.
- Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab .

Thuật ngữ: Critical section là đoạn tương tranh, Đoạn mã găng,đoạn mã tới hạn.
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. Đoạn tương tranh thường nằm giữa Entry Section (Đoạn đăng nhập) và Exit Section (Đoạn đăng xuất).
Ví dụ minh họa : Trong slide 7.9 chương 7 ta có hai đoạn mã là đoạn tương tranh trong việc sử dụng đèn hiệu
1.wait (semaphore S) {
while ( S <= 0 ); // chờ bận nếu S<=0
S --; // Giảm S đi 1
}

2.signal (semaphore S) {
S ++; //Tăng S lên 1
}

Vùng tranh chấp: là vùng chứa các biến (hay nói chung là các tài nguyên) dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ :
bạn A lên bảng viết tên của bạn ấy lên bảng thì cái bảng là "vùng tranh chấp". Bạn B phải chờ bạn A viết tên của mình xong và nhấn đèn xanh thì bạn B mới lên bảng viết tiếp.
Trong ví dụ các chuyến xe qua chung 1 cây cầu có đèn hiệu thì cây cầu chính là "vùng tranh chấp". Chiếc xe thứ nhất đang qua cầu thì đèn đang đỏ, các xe tiếp theo đứng chờ cho đến khi xe thứ nhất qua bên kia cầu, đèn xanh bật lên thì thứ hai tiếp tục qua cầu.

typedef int semaphore;
semaphore mutex=1;
while (1) {
remainder section
wait (mutex);
critical section
signal (mutex);
remainder section
}

Admin
Hiểu bài !

1/ Người lái xe qua cầu yếu:
Semaphore s=1; // 0 đèn đỏ, 1 đèn xanh
wait (s);
Lên cầu; // đoạn tương tranh
Qua cầu // đoạn tương tranh
signal (s);

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

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

Admin
Trình bày tốt !

Để bắt đầu với Windows 7 Speech Recognition, click Start, Control Panel, Speech Recognition, hoặc đơn giản gõ “speech recognition” vào ô tìm kiếm Start và nhấn Enter.

Trong lần đầu tiên bạn khởi động Windows 7 Speech Recognition, chương trình sẽ giới thiệu qua những tùy chọn và cấu hình cơ bản. Màn hình chào sẽ giải thích các chức năng cơ bản của nhận dạng giọng nói.

Sử dụng microphone tốt

Lựa chọn kiểu microphone bạn sẽ dùng. Tốt nhất là loại headphone có mic kèm theo.

Một trong những yếu tố quan trọng nhất của nhận dạng giọng nói là chất lượng và vị trí của microphone. Nếu công cụ Windows 7 Speech Recognition không nghe rõ những gì bạn ra lệnh, hiệu quả thực hiện sẽ giảm sút đáng kể.

Bạn có thể sử dụng bất kỳ loại microphone nào làm đầu vào âm thanh, tuy nhiên kiểu headphone có mic gắn kèm rất được khuyên dùng. Lý do là vì thiết kế của nó cho phép giữ vị trí microphone luôn ở ngay trước miệng bạn. Nếu bạn không thích đeo headphone trên đầu cả ngày, có thể cân nhắc sử dụng mic USB.

Thiết lập ban đầu

Lựa chọn có cho phép Windows 7 Speech Recognition quét e-mail
và các tài liệu của bạn hay không.

Windows 7 Speech Recognition có thể học cách nhận dạng chất giọng và lối dùng từ của bạn bằng cách xem qua các tài liệu, e-mail trên máy tính. Việc nắm rõ những từ ngữ bạn thường dùng sẽ giúp Windows 7 nhận dạng giọng nói của bạn chính xác và hiệu quả hơn rất nhiều. Nếu bạn cảm thấy lo lắng về vấn đề bảo mật riêng tư, bạn có thể lựa chọn vô hiệu hóa tính năng này.

Lựa chọn kích hoạt Windows 7 Speech Recognition ở chế độ Manual hoặc Voice.

Không phải lúc nào bạn cũng muốn Windows 7 nghe và làm theo mọi điều bạn nói. Chẳng hạn như khi bạn đang nói chuyện điện thoại, nếu công cụ nhận dạng giọng nói vẫn đang hoạt động thì khó mà tưởng tượng được Windows 7 sẽ làm những gì. Bạn có thể đặt chế độ kích hoạt để quyết định phản ứng của Windows 7 Speech Recognition sau khi bạn ra lệnh “stop listening” (dừng nghe). Nếu bạn chọn chế độ Manual (kích hoạt bằng tay), bạn phải click vào biểu tượng microphone hoặc nhấn tổ hợp phím Ctrl + Windows để kích hoạt trở lại. Nếu bạn đặt chế độ Voice, công cụ Speech Recognition sẽ chuyển sang trạng thái chờ, và bạn có thể kích hoạt trở lại bằng cách nói “start listening” (bắt đầu nghe).

Bạn có thể in một bản danh sách những câu lệnh bằng giọng nói thường gặp để tiện sử dụng.

Windows 7 cung cấp danh sách những câu lệnh thường gặp để dẫn bạn qua những chức năng cơ bản của nhận dạng giọng nói. Thay vì dùng chuột để click một biểu tượng trên màn hình desktop, bạn chỉ cần nói “click”. Ví dụ, để click chọn biểu tượng Computer, bạn nói “click Computer”. Nếu bạn muốn mở, bạn nói “double-click Computer” thay vì dùng chuột để click đúp. Nếu bạn không biết xử lý thế nào với Windows 7 trong trường hợp cụ thể, bạn có thể hỏi “What can I say?”, Windows 7 Speech Recognition sẽ cho bạn danh sách các câu lệnh có thể dùng. Hãy in danh sách đó để tiện sử dụng như một bản hướng dẫn cầm tay.

Vào phần tùy chọn để thay đổi cấu hình.

Bước cuối cùng trong khâu thiết lập ban đầu là lựa chọn để Windows 7 Speech Recognition tự chạy mỗi khi khởi động Windows hay không. Bạn có thể xem lại các tùy chọn vừa thay đổi bằng cách click Advanced Speech Options phía bên trái trên bảng điều khiển Control Panel Speech Recognition. Ngoài ra bạn có thể nói “Show Speech Options”.

“Luyện tai” cho máy tính

Tính năng luyện nghe của Speech Recognition yêu cầu bạn đọc chính tả
để máy tính làm quen với chất giọng của bạn.

Điều đầu tiên bạn cần làm với Windows 7 Speech Recognition đó là luyện cho chương trình hiểu được sắc thái phát âm và chất giọng của bạn. Để bắt đầu, chọn Speech Recognition Voice Training từ Speech Recognition control panel.
Phần hướng dẫn của Windows 7 Speech Recognition sẽ giới thiệu đến bạn
tính năng đọc chính tả cho Windows.

Đọc chính tả là tính năng phổ thông và hết sức hữu dụng để làm việc hiệu quả nhờ công nghệ nhận dạng giọng nói. Phần hướng dẫn của Windows 7 Speech Recognition về tính năng đọc chính tả sẽ giới thiệu cho các bạn từng bước chi tiết để đọc cho máy tính ghi chép, bao gồm cả thêm dấu chấm câu bằng cách nói “period”, “question mark”...

Khi Speech Recognition mắc sai sót, bạn có thể dùng câu lệnh bằng giọng nói để sửa lỗi sai.

Trong quá trình làm việc, khó tránh khỏi những trường hợp Windows 7 Speech Recognition hiểu câu nói của bạn không chuẩn. Trong trường hợp này, Microsoft sẽ giải thích cho bạn cách xác định từ ngữ cần sửa và cách dùng câu lệnh bằng giọng nói để chọn từ ngữ thay thế.

Bạn có thể dùng những câu lệnh như “delete” hay “undo” để sửa lỗi.

Trong trường hợp bạn thay đổi ý về những gì vừa nói ra, bạn có thể dùng những câu lệnh như “undo”, “undo that”, “delete that” để xóa từ hoặc cụm từ gần nhất.

Để sửa nhiều hơn một từ, chọn nguyên một đoạn văn bản.

Bạn cũng có thể xóa nhiều từ xác định bằng cách nói “delete” kèm theo từ bạn muốn xóa. Để xóa nguyên đoạn văn bản một cách hiệu quả hơn, bạn có thể chỉ rõ đoạn văn bản đó bằng cách chọn từ bắt đầu + “through” + từ kết thúc đoạn, sau đó nói “delete that”. Nếu bạn xóa nhầm, ra lệnh “undo that” để lấy lại đoạn văn. Nếu bạn muốn bỏ chọn đoạn và tiếp tục làm việc, nói “clear selection.”

Câu lệnh “new line” và “new paragraph” cho phép bạn xuống dòng.

Khi bạn đọc chính tả một lá thư hay một tài liệu dài, bạn cần sử dụng các câu lệnh như “new paragraph” (đoạn mới) hoặc “new line” (dòng mới) để yêu cầu Windows 7 Speech Recognition kết đoạn hoặc kết câu và xuống dòng.

Làm việc với Windows giống như cách mà bạn yêu cầu ai đó mở ứng dụng bằng chuột.

Windows 7 Speech Recognition có thể làm được nhiều việc hơn nữa, không chỉ là viết chính tả. Công cụ này cho phép bạn dùng câu lệnh để mở các ứng dụng và làm việc với hệ thống qua giọng nói. Ví dụ, để mở WordPad bạn nói “Start” thay vì dùng chuột click vào biểu tượng Start trên màn hình Windows 7. Sau đó bạn tiếp tục nói “All Programs” để vào danh sách ứng dụng, “Accessories” để vào tiếp thư mục Accessories. Cuối cùng chọn WordPad bằng cách nói “WordPad”.

Nếu bạn muốn mở mục Insert trên menu, chỉ việc nói “Insert”.

Ra lệnh cho Windows 7 bằng giọng nói là một quá trình hoàn toàn thuộc về trực giác, bởi lẽ nó đơn giản như việc bạn đọc ra những gì bạn thấy. Chẳng hạn như thay vì click Insert trên menu, bạn chỉ việc nói “Insert”. Sau đó bạn có thể chọn một trong những tùy chọn sẵn có bằng cách đọc tên nó, ví dụ “Date and Time”.

Nói “Click” hoặc “Double-Click” kèm theo tên biểu tượng hoặc tên thư mục để làm việc với chúng giống như cách bạn dùng chuột.

Để mở thư mục hoặc chạy chương trình, bạn cần nói những câu lệnh miêu tả hành động như khi bạn đang dùng chuột bình thường. Ví dụ, để chọn thư mục Pictures, bạn nói “click Pictures”, để mở thư mục Sample Pictures, bạn nói “double-click Sample Pictures”.

“Show desktop” đưa bạn trở lại màn hình chính của Windows. Tiếp tục nói “right-click” để mở menu ngữ cảnh, giống như cách bạn click chuột phải.

Bạn có thể ẩn toàn bộ các cửa sổ hiện hành để trở lại màn hình desktop của Windows 7 bằng cách nói “show desktop”. Để mở menu ngữ cảnh của ứng dụng đang chọn, bạn nói “right-click” thay vì click chuột phải như bình thường.

ĐƠN XIN VIỆC
Kính gửi: Giám đốc công ty X
Tôi tên là: Nguyễn Văn A
.........(nội dung đơn).........
TP.HCM, ngày 20 tháng 10 năm 2011
Người làm đơn
............(chữ ký).............
Nguyễn Văn A


Nội dung đơn này phải đảm bảo tính toàn vẹn( Integrity), ví dụ: Phía trên là Nguyễn Văn A thì phía dưới cũng phải là Nguyễn Văn A.
Nếu vài tiến trình(hơn 1) cùng sửa đơn trên một lúc( không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ: Giả sử tiến trình P1(nhà sản xuất) sửa Nguyễn Văn A phía trên thành Nguyễn Văn An, trong khi P2(nhà sản xuất khác) sửa Nguyễn Văn A phía dưới thành Nguyễn Văn Ân, mà có tiến trình P3( nhà tiêu thụ) nào đó "lấy" đơn về dùng( để in ra) thì kết quả sẽ không nhất quán.

Admin
- Hiểu vấn đề !
- Tuy nhiên, cần chỉ ra cách làm sao để Nội dung dùng chung "đúng" được !

Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra]; 11 tháng 5, 1930 tại Rotterdam – 6 tháng 8, 2002 tại Nuenen), là nhà khoa học máy tính Hà Lan. Ông được nhận giải thưởng Turing cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình Không lâu trước khi chết, ông đã được nhận giải Bài báo ảnh hưởng lớn trong lĩnh vực tính toán phân tán của ACM dành cho bài báo đã khởi đầu cho ngành con Tự ổn định. Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.



Tiểu sử
Dijkstra học vật lý lý thuyết tại Đại học Leiden, nhưng ông đã nhanh chóng nhận ra rằng ông quan tâm đến lập trình hơn.

Thời kỳ đầu, ông làm việc tại Trung tâm toán học, Viện nghiên cứu quốc gia về toán học và khoa học máy tính tại Amsterdam, ông còn giữ chức vị giáo sư tại Đại học Kỹ thuật Eindhoven, Hà Lan. Đầu thập kỷ 1970, ông làm cộng tác nghiên cứu tại Burroughs Corporation, sau đó giữ vị trí Schlumberger Centennial Chair ngành Khoa học máy tính tại Đại học Texas tại Austin, Mỹ. Ông nghỉ hưu năm 2000.
Trong các đóng góp của ông cho ngành khoa học máy tính có thuật toán đường đi ngắn nhất, còn được biết với tên Thuật toán Dijkstra, hệ điều hành THE và cấu trúc semaphore để phối hợp hoạt động của nhiều bộ vi xử lý và nhiều chương trình. Một khái niệm khác trong lĩnh vực tính toán phân tán đã được khởi đầu nhờ Dijkstra là self-stabilization - một cách khác để đảm bảo tính đáng tin cậy của hệ thống. Thuật toán Dijkstra được sử dụng trong SPF, Shortest Path First, dùng trong giao thức định tuyến OSPF, Open Shortest Path First.

Ông còn nổi tiếng với đánh giá thấp về lệnh GOTO trong lập trình máy tính. Bài báo năm 1968 "A Case against the GO TO Statement" (EWD215) được xem là một bước quan trọng tiến tới việc lệnh GOTO bị thay thế dần trên quy mô lớn bởi các cấu trúc lập trình chẳng hạn như vòng lặp while. Phương pháp này còn được gọi là Lập trình có cấu trúc. Dijkstra đã rất hâm mộ ngôn ngữ lập trình ALGOL 60, và đã làm việc trong nhóm cài đặt trình biên dịch đầu tiên cho ngôn ngữ này.

Từ những năm 1970, mối quan tâm chính của Dijkstra là kiểm định hình thức (formal verification). Quan niệm phổ biến thời đó là người ta nên đưa ra một chứng minh toán học về tính đúng đắn của chương trình sau khi đã viết chương trình đó. Dijkstra đã phản đối rằng các chứng minh thu được rất dài và nặng nề, và rằng chứng minh đó không đem lại hiểu biết về việc chương trình đã được phát triển như thế nào. Một phương pháp khác là dẫn xuất chương trình (program derivation), để "phát triển chứng minh và chương trình một cách đồng thời". Người ta bắt đầu bằng một đặc tả toán học về những gì mà một chương trình cần phải thực hiện, sau đó áp dụng các biến đổi toán học đối với đặc tả đó cho đến khi nó được chuyển thành một chương trình chạy được. Chương trình thu được khi đó được gọi là "đúng đắn theo cách xây dựng" (correct by construction).

Dijkstra còn nổi tiếng với các bài luận của ông về lập trình; ông là người đầu tiên tuyên bố rằng việc lập trình có đặc điểm cố hữu là khó khăn và phức tạp đến mức các lập trình viên cần phải khai thác mọi kỹ thuật và các phương pháp trừu tượng hóa có thể để hy vọng có thể quản lý được độ phức tạp của nó một cách thành công. Ông còn nổi tiếng với thói quen viết tay cẩn thận các bản thảo bằng bút máy. Các bản thảo này được gọi là EWD, do Dijkstra đánh số chúng bằng tiết đầu tố EWD. Ông thường phân phát các bản phô-tô của bản EWD mới cho các đồng nghiệp của mình; những người nhận được lại phô-tô và tiếp tục phân phát các bản sao, bằng cách đó các bản EWD được phát tán khắp cộng đồng khoa học máy tính quốc tế. Các chủ đề chính là về khoa học máy tính và toán học, ngoài ra còn có các báo cáo công tác, thư và các bài phát biểu. Hơn 1300 bài EWD đã được quét thành ảnh, số lượng được chuyển thành dạng điện tử để phục vụ nghiên cứu ngày càng tăng, chúng được lưu trữ và cung cấp trực tuyến tại Đại học Texas.

Dijkstra đã là một trong những người tiên phong trong nghiên cứu về tính toán phân tán. Có người còn cho là một số bài báo của ông đã thiết lập ngành nghiên cứu này. Cụ thể, bài báo "Self-stabilizing Systems in Spite of Distributed Control" của ông đã khởi đầu ngành con Self-stabilization.
Dijkstra còn được ghi nhận là cả đời chỉ sở hữu duy nhất một chiếc máy tính (vào cuối đời) và họa hoằn mới thực sự sử dụng nó, để đi đôi với quan niệm của ông rằng khoa học máy tính trừu tượng hơn chứ không chỉ là lập trình, quan niệm này được thể hiện trong nhiều câu nói nổi tiếng chẳng hạn như "Khoa học máy tính đối với máy tính cũng như thiên văn học đối với kính thiên văn" (Computer Science is no more about computers than astronomy is about telescopes.)

Ông qua đời tại Nuenen, Hà Lan vào ngày 6 tháng 8, năm 2002 sau một thời gian dài bị ung thư. Năm sau, giải thưởng PODC Influential Paper Award in distributed computing (bài báo ảnh hưởng trong lĩnh vực tính toán phân tán) của tổ chức ACM (Association for Computing Machinery) đã được đổi tên thành Giải thưởng Dijkstra để vinh danh ông.

Thuật toán Dijkstra là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm.
Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và
các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh
có thể xem như độ dài của các con đường (và do đó là không âm). Chúng
ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra
sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn
khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh
A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.
Thuật toán
Ta quản lý một tập hợp động S. Ban đầu S={s}.

Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.

Chứng minh
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.

Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.

Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy.

Mã

Thời gian chạy
Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O( n^2+m ). Tuy nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp sẽ là O( (n+m)*log2(n) ).

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

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

Câu 5: Thực thi bài toán sản xuất và tiêu thụ được đồng bộ bằng ba đè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.

cảm ơn những đóng góp của các bạn

PhamQuocAnh02 (113A) đã viết:• Đả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ụ : bạn a lên bản viết một lá đơn phần họ tên ghi là nguyễn văn a và phần ký tên là lê văn b. lúc sau đó bạn b lên bảng sửa lại phần ký tên cho đúng là nguyễn văn a. lúc đó phái dưới lớp có bạn c lấy máy ảnh chụp lại cái bảng đang lúc bạn b đang sửa lại phần ký tên mới gi là nguyễn văn, dẫn đến nội dung sai lệch, không hoàn chỉnh và thiếu nhất quán. đáng lẽ bạn c phải chờ bạn b thực hiện song công việc là sửa phần ký tên là nguyễn văn a song rồi mới chụp thì nội dung mới đúng.

- Mục đích của đồng bộ hóa công việc của các tiến trình nhằm đảm bảo tính nhất quán tính toàn vẹn của tài nguyên dùng chung và tránh được hiện tượng ket(dealdock)
ví dụ:
-Ban lớp trưởng lên bảng(Tài nguyên dùng chung) viết tên email số điện thoại của mình cho lớp, nếu bạn chưa viết xong mà bạn khác chụp ảnh trên bảng để đưa về xử lý sẽ dẫn đến thông tin bị sai, do vậy việc đồng bộ có tác dụng rất lớn nghĩa là chờ bạn lớp trưởng viết xong(nghĩa là có chờ) sau đó mới chụp ảnh lấy về thì đảm bảo thông tin chính xác.

Admin
- Ví dụ tốt !
- Cần chú ý soạn thảo cho Chuẩn và Đúng chính tả !

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.

Bài toán như sau: “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”.

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.

Một chiếc cầu yếu mỗi thời điểm chỉ cho 1 xe được qua. Đèn hiệu S ở đầu cầu có 2 trạng thái Xanh (mã 1) và Đỏ (mã 0), các lệnh Lên cầu và Qua cầu trong code của mỗi lái xe thuộc Đoạn tương tranh (do ảnh hưởng tài nguyên dùng chung). Code đó như sau:
wait(S);
Lên cầu;
Qua cầu;
signal(S);
Mỗi xe muốn lên cầu, phải thực hiện lệnh wait(S) để xem đèn đã Xanh chưa. Nếu Xanh, giá trị của đèn S bị trừ đi 1 (Xanh->Đỏ) và các lệnh Lên cầu và Qua cầu lần lượt được thực hiện. Xe sau không thể lên được do đèn S đang đỏ.

Khi xe qua cầu xong, lệnh signal(S) thực hiện: Giá trị của S (đang bằng 0) được tăng lên 1, tức thành màu Xanh. Xe sau đang "ngủ" tại lệnh wait(S) của nó, được "Người gác cầu" (chính là Hệ điều hành) đánh thức và qua được wait(S) để Lên và Qua cầu,..........

NguyenVuLinh12053_I11C đã viết: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).

Cảm ơn bạn nhiều , mình còn hơi lơ mơ một chút nhưng coi lại bài này thấy đỡ hơn chút .

trantrungnam-HC11TH2A đã viết:Mục đích của đồng bộ hoá 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êndùng chung và Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).

Bạn có thể chú thích thêm về hình không bạn, mình chưa hiểu lắm về hình cho lắm. Thanks