Thảo luận Bài 7

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

Quá trình thường cần liên lạc với các quá trình khác. Ví dụ, trên hệ điều
hành Linux, đối tượng ống nối (pipeline) được dùng để chuyển kết quả
của một lệnh thành dữ liệu vào của một lệnh kế tiếp. Nói cách khác, đối
tượng ống nối cho phép chuyển kết quả của một quá trình thành dữ liệu
vào của quá trình khác.
Một phương thức giao tiếp khác là các quá trình cùng đọc/ghi chung một
(hay nhiều) vùng dữ liệu chung. Trong hệ thống đa chương, các quá trình
thực hiện đồng hành thì ràng buộc về đồng nhất dữ liệu ảnh hưởng chính
đến kết quả thực hiện của các quá trình hợp tác nhau.
Ví dụ: với mô hình sản xuất-tiêu thụ (chương 3), khi quá trình tiêu thụ
đọc một biến trong vùng dữ liệu chung. Giá trị đọc được phụ thuôc vào
thứ tự đọc là trước hay sau khi ghi giá trị lên biến của quá trình sản xuất.
Trong chương này, ta đề cập đến các kỹ thuật thông dụng để đảm bảo
tính đồng nhất hay thứ tự của quá trình truy cập vùng dữ liệu chung của
các quá trình hợp tác với nhau.

4.1 Bài toán đồng bộ
Mô hình hợp tác giữa các quá trình trong chương 3 dựa trên giả định là
các quá trình thực hiện bất đồng bộ. Do vậy chúng có thể chia sẻ dữ liệu
cho nhau. Trong chương này, ta xét bài toán hợp tác của các quá trình với
vùng dữ liệu chung có kích thước giới hạn: print spooling.
Cụ thể, khi một quá trình cần in một tập tin, nó nhập tên tập tin vào một
thư mục đặc biệt spooler. Một quá trình khác, dịch vụ in, sẽ kiểm tra xem
có tập tin nào trong thư mục spooler không, nếu có dịch vụ sẽ thực hiện
in. Sau khi in xong, dịch vụ in sẽ xóa tên tập tin khỏi thư mục spooler. Giả sử thư mục spooler có nhiều mục vào được đánh số 0,1,2,…. Mỗi
mục vào giữ một tên tập tin. Đồng thời có 2 biến dùng chung:
- Biến out: trỏ đến tập tin kế tiếp được in
- Biến in: trỏ đến mục vào trống kế tiếp của thư mục spooler.
Hai biến này có thể được giữ trong một tập tin 2 từ mà có thể truy cập
được từ tất cả các quá trình.
Giả sử tại một thời điểm, các mục vào 0 đến 3 rỗng, mục vào 4 đến 6 là
có dữ liệu. Đồng thời, hai quá trình A, B sắp hàng một tập tin cần in.
Tiến trình thực hiện của 2 quá trình như sau:
- Quá trình A đọc biến in và gán giá trị đọc được, 7, vào biến cục bộ
của nó, next_free_slot. Giả sử đến thời điểm này, quá trình A hết thời
hạn thực hiện chu kỳ CPU. Nên hệ điều hành gọi thủ tục chuyển ngữ
cảnh để chuyển CPU cho quá trình B.
- Quá trình B đọc biến in, và cũng có được giá trị 7. Sau đó, B gán tên
tập tin cần in của nó vào mục vào 7, và tăng in lên 1 giá trị. Kế tiếp, B
chuyển sang tác vụ khác. - Đến lượt quá trình A quay lại tiếp tục thực hiện. A sẽ tiếp tục thực
hiện ngay sau tác vụ bị ngắt. A đọc biến next_free_slot, lấy giá trị 7.
Do vậy, A ghi tên tập tin cần in vào mục vào 7. Tên tập tin của B tại
mục vào này bị xóa. Kế tiếp, A tính next_free_slot +1 và ghi giá trị
tính được vào biến in.
- Lúc này, dịch vụ in thực hiện in theo giá trị có trong biến in. Kết quả,
quá trình B sẽ không nhận được kết quả ở máy in.
Qua ví dụ, ta thấy khi hai (hay nhiều) quá trình cùng đọc/ghivùng dữ liệu
chia sẻ thì kết quả thường phụ thuộc vào thứ tự thực hiện của các quá
trình, điều này được gọi là điều kiện cạnh tranh (race condition). Khi một
chương trình có chứa điều kiện cạnh tranh, việc kiểm tra có thể cho kết
quả đúng, nhưng khi thực hiện có thể có những kết quả ngoài dự đoán.
Đây chính là vấn đề cần giải quyết của bài toán đồng bộ.
Trong phần còn lại của chương, ta đề cập xác định rõ các vấn đề tranh
chấp và các kỹ thuật để giải quyết các vấn đề này.

4.2 Vấn đề tranh chấp
Ta đã biết, để đảm bảo các chương trình có dùng chung tài nguyên sẽ cho
kết quả đúng là làm thế nào để các điều kiện cạnh tranh không xảy ra.
Ý tưởng chính là tìm các cách để ngăn chặn nhiều quá trình cùng đọc, ghi
vùng dữ liệu chia sẻ mở cùng một thời điểm. Nói cách khác, ta cần có
cách thức độc quyền truy cập (mutual exclusion) theo kiểu: nếu có một
quá trình đang dùng một biến chung (hay một tập tin chia sẻ) thì các quá
trình khác không thể thao tác trên biến (hay tập tin) đấy. Ví dụ trên minh
họa ràng buộc này, ta thấy điều kiện cạnh tranh xảy ra bởi vì quá trình B
khởi động sử dụng biến chung trước khi quá trình A kết thúc thao tác trên
biến chung. Như vậy, việc chọn tác vụ cơ sở thích hợp để đạt được độc quyền truy
cập là yếu tố cài đặt chính của thủ tục đồng bộ quá trình. Ta sẽ xét các
phương pháp lựa chọn trong các giải pháp đồng bộ.
Trong hệ điều hành, việc ngăn ngưà điện kiện cạnh tranh có thể được
hình thức hóa trong cách thức trừu tượng. Một quá trình có thể được chia
làm các phần thực hiện theo mã lệnh:
- Phần mã lệnh mà quá trình thực hiện độc lập không hợp tác với quá
trình khác.
- Đoạn lệnh của quá trình có chức năng thực hiện các tác vụ trên vùng
dữ liệu chung. Đoạn chương trình này có thể được gọi là vùng tương
tranh (critical region).
Do vậy, nếu ta đảm bảo ràng buộc: không có 2 (hay nhiều) quá trình hợp
tác thực hiện trên vùng tương tranh ở cùng 1 thời điểm, thì các điều kiện
cạnh tranh sẽ không xảy ra.
Tuy nhiên, ràng buộc trên chưa đủ để ngăn chặn các điều kiện cạnh tranh.
Ta cần 4 điều kiện để đảm bảo các điều kiện cạnh tranh không xảy ra
trong quá trình hợp tác giữa các quá trình:
- Không có hai quá trình thực hiện cùng một lúc trên vùng tương tranh.
Cụ thể, nếu có 1 quá trình đang thực hiện trên vùng tương tranh thì
các quá trình khác phải chờ.
- Không có quá trình nào phải chờ vô hạn để được thực hiện trên vùng
tương tranh.
- Một quá trình không thực hiện trên vùng tương tranh không thể ngăn
quá trình khác vào vùng tương tranh.
- Liên tục: khi không có quá trình nào đang thực hiện trên vùng tương
tranh thì chỉ những quá trình đang không thực hiện phần độc lập mới
có thể tham gia vào việc chọn quá trình. Ví dụ sau minh họa cách thức độc quyền truy cập: hệ thống có hai quá
trình đang hợp tác.
- Quá trình A bắt đầu thực hiện trên vùng tương tranh ở thời điểm T1
- Ở thời điểm T2, quá trình B cần vào vùng tương tranh nhưng phải chờ
vì có một quá trình đang thực hiện ở đấy.
- Quá trình B chờ cho đến thời điểm T3 khi quá trình A kết thúc thực
hiện vùng tương tranh.
- Ở thời điểm T4, quá trình B kết thúc thực hiện trên vùng tương tranh.
4.3 Các giải pháp
Các giải pháp để ngăn chặn các điều kiện cạnh tranh khi có nhiều quá
trình hợp tác nhau có thể được chia thành hai nhóm dựa theo cách thức
tiếp cận: nhóm giải pháp chờ và bận (busy waiting), nhóm giải pháp ngủ
và thức dậy (sleep and wakeup).
4.3.1 Ngưng kích họat ngắt
Giải pháp đơn giản nhất là mỗi quá trình ngưng kích hoạt các ngắt ngay
sau khi bắt đầu thực hiện trên vùng tương tranh. Khi đó, các ngắt đồng hồ
xung không xảy ra, nên CPU không thể chuyển từ quá trình đang thực hiện sang quá trình khác. Do đó, quá trình hiện hành sẽ thực hiện đầy đủ
các lệnh cơ sở trong vùng tương tranh. Sau khi, quá trình “thóat” khỏi
vùng tương tranh, nó sẽ kích họat lại các ngắt.
Tổng quát, giải pháp này ít được chọn vì nó không thận trọng khi cho
người dùng có quyền tắt các ngắt của hệ thống. Giả sử rằng một trong các
ngắt đã tắt, và sau đó không thể bật ngắt này lên được. Điều này có thể
dẫn đến việc ngưng toàn bộ hệ thống. Hơn nữa, nếu hệ thống là hệ thống
đa xử lý (giả sử, hệ thống có hai CPU), việc ngưng sử dụng ngắt chỉ có
hiệu lực với CPU mà đang thực hiện lệnh của vùng tương tranh. Như thế,
CPU còn lại vẫn chạy và vẫn có thể cho phép quá trình khác thực hiện
trên vùng tương tranh.
Tuy nhiên, giải pháp này thuận tiện với hệ thống mà nhân tự ngưng kích
họat ngắt cho một vài lệnh khi đang cập nhật các biến chung.
Ta có thể kết luận: việc ngưng sử dụng ngắt là kỹ thuật thường dùng
trong bản thân các hệ điều hành, nhưng một cách tổng quát lại không
thích hợp với cơ chế độc quyền truy cập cho các quá trình của người
dùng.
4.3.2 Giải pháp chờ và bận
4.3.2.1 Giải pháp phần mềm
• Giải pháp dùng biến khóa
Trong giải pháp này, các quá trình, đang hợp tác, chia sẻ một biến (kiểu
nguyên) chung có vai trò khóa cho vùng dữ liệu chung.
Khởi đầu biến khóa có gía trị 0. Nếu có quá trình đang thực hiện trên
vùng tương tranh thì giá trị biến khóa là 1.
Nếu một quá trình muốn thực hiện trên vùng tương tranh, nó thực hiện
tuần tự như sau: - Kiểm tra giá trị của biến khóa.
- Nếu giá trị là 0 Æ quá trình bắt đầu thực hiện trên vùng tương tranh
và đặt biến khóa là 1.
- Nếu giá trị là 1: quá trình chờ và sau một khỏang thời gian t, quá trình
lập lại bước 1.
Tuy vậy, giải pháp này chứa một lỗ hỏng mà ta có thể thấy qua ví dụ sau:
giả sử một quá trình đọc biến khóa và có được giá trị 0. Trước khi nó đặt
giá trị khóa là 1, một quá trình khác được cấp CPU để thực hiện (bởi bộ
định thì). Quá trình mới cũng cần thực hiện trên vùng tương tranh và đặt
khóa là 1. Khi quá trình trước quay lại thực hiện, đến lượt nó sẽ đặt khóa
là 1 và thực hiện trên vùng tương tranh. Như vậy, hệ thống sẽ có 2 quá
trình cùng thực hiện trên vùng tương tranh.
• Giải pháp kiểm tra luân phiên
Giải pháp này được dùng cho 2 quá trình có chung vùng dữ liệu chia sẻ.
Hai quá trình cùng dùng một biến khóa chung turn được khởi gán là 0.
Biến này có 2 giá trị.
- Giá trị 0 biểu thị quá trình A được phép thực hiện trên vùng tương
tranh. Giá trị 1 biểu thị quá trình B được thực hiện trên vùng tương
tranh.
- Khi quá trình thực hiện xong trên vùng tương tranh, nó phải trả lại
quyền thực hiện trên đó cho quá trình khác bằng cách đặt lại giá trị
của biến turn. Biến khóa được dùng trong phương pháp chờ - bận gọi là khóa spin (spin
lock).
Giải pháp này ngăn chặn việc hai quá trình có thể cùng vào vùng tương
tranh. Tuy nhiên, nó có thể để hệ thống vi phạm yêu cầu một quá trình
không thực hiện trên vùng tương tranh không thể ngăn quá trình khác
thực hiện trên đó như trong tình huống giả định sau:
- Thời điểm t0, giả sử quá trình A kết thúc thực hiện trên vùng tương
tranh. Nó đặt biến turn là 1, và cho phép quá trình B thực hiện trên
vùng tương tranh.
- Thời điểm t1, quá trình B thực hiện nhanh trên vùng tương tranh. Kế
tiếp, cả hai quá trình đều không thực hiện trên đó, và biến turn được
đặt là 0.
- Thời điểm t2, quá trình A thực hiện nhanh vòng lặp, thóat khỏi vùng
tương tranh và đặt biến turn là 1. ở thời điểm này, biến turn có giá trị
1, và cả hai quá trình không thực hiện trên vùng tương tranh.
- Bất ngờ, quá trình A kết thúc cuối vòng lặp và quay lại đầu. Nó không
được phép thực hiện trên vùng tương tranh vì biến turn là 1, dù quá
trình B không thực hiện trên đó. Vì thế, quá trình A phải chờ cho đến
khi quá trình B quay lại thực hiện trên vùng tương tranh và đặt lại
biến turn là 0.
Vậy, ta thấy quá trình B không ở trong vùng tương tranh, nhưng lại ngăn
quá trình A vào vùng này.
• Giải pháp Peterson
Giải pháp này được đề nghị lần đầu bởi T. Derke (1965) với ý tưởng kết
hợp hai giải pháp trên để giải quyết các hạn chế của chúng. Năm 1981, Perteson cải tiến giải thuật Derke với cách thực hiện đơn giản hơn và
được gọi là giải thuật Perteson.
Giải thuật bao gồm 2 thủ tục được viết bằng C.
Trước khi thực hiện trên vùng tương tranh, mỗi quá trình gọi thủ tục
enter_region với tham số là ID của mình (giá trị 0 hay 1). Quá trình có
thể đợi cho đến khi an toàn để thực hiện trên đó. Sau khi thực hiện, quá
trình sẽ gọi thủ tục leave_region để biểu thị nó đã kết thúc và cho phép
quá trình khác có thể vào vùng tương tranh.
Để hiểu rõ giải thuật, ta xét ví dụ ở hình trên:
- Khởi đầu: không có quá trình nào ở vùng tương tranh.
- Quá trình A gọi thủ tục enter_region để yêu cầu được thực hiện trên
đó bằng cách đặt biến interested là TRUE và biến turn là ID của quá
trình.
- Sau đó, nếu quá trình B gọi thủ tục enter_region, nó sẽ phải chờ cho
đến khi biến interested là FALSE. Điều này chỉ xảy ra khi quá trình A
gọi thủ tục leave_region để thoát khỏi vùng tương tranh. - Giả sử, nếu cả hai quá trình cùng gọi enter_region thì chúng cùng đặt
biến turn là ID của mình. Giả sử quá trình B ghi sau, nên turn có giá
trị 1. Khi cả hai quá trình cùng vào vòng lặp while, quá trình A vào
vùng tương tranh. Quá trình B lặp lại và không vào vùng tương tranh.
4.3.2.2 Giải pháp đồng bộ dùng TLS
Phần này đề cập đến giải pháp bận – chờ dùng thiết bị cứng. một vài máy
tính đa xử lý có hỗ trợ lệnh
TSL RX,LOCK
Lệnh được gọi là Test and Set bao gồm 2 tác vụ được thực hiện chung
trên 1 chu kỳ xung:
- Đọc 1 nội dung của biến LOCK vào thanh ghi RX
- Gán 1 giá trị (khác 0) vào biến LOCK
Nếu có hai lệnh TLS cùng thực hiện trên 2 quá trình (trên 2 CPU) khác
nhau thì chúng sẽ được thực hiện tuần tự. Điều này cho phép dùng lệnh
TLS trong thủ tục đồng bộ.
Để sử dụng lệnh TLS, ta có thể dùng biến chung LOCK. Khi LOCK có
giá trị 0, quá trình bất kỳ có thể đặt nó là 1 dùng lệnh TLS và sau đó truy
cập vùng tương tranh. Sau khi thực hiện xong, quá trình trả lại giá trị của
LOCK là 0.
Ví dụ sau minh họa cách dùng TLS để cài đặt hai thủ tục enter_region và
leave_region của giải thuật Perteson.
enter_region:
TSL REGISTER,LOCK |copy LOCK to register and set LOCK to 1
CMP REGISTER,#0 |was LOCK zero?
JNE ENTER_REGION |if it was non zero, LOCK was set, so loop
RET |return to caller; critical region entered
leave_region:
MOVE LOCK,#0 |store a 0 in LOCK
RET |return to caller Thủ tục enter_region gồm 4 lệnh:
- Lệnh đầu sao chép biến LOCL vào thanh ghi và đặt LOCK là 1
- Lệnh kế kiểm tra xem LOCK là 0 ?
- Nếu LOCK là khác 0, thì biến LOCK được đặt, và quá trình quay lại
đầu thủ tục (chờ). Vòng lặp tiếp tục cho đến khi LOCK là 0.
Lúc này, vấn đề thực hiện trên vùng tương tranh được giải quyết trực
tiếp: trước khi thực hiện trên đó, quá trình gọi enter_region và chờ cho
đến khi LOCK là rỗi (0). Sau khi thực hiện trên vùng tương tranh, quá
trình lại gọi leave_region để đặt LOCK là 0. Tương tự như các giải pháp
khác, quá trình phải gọi enter_region và leave_region đúng thời điểm.
4.3.3 Các giải pháp sleep and wakeup
Cả hai giải pháp Perterson và giải pháp dùng TLS đều cần thời gian chờ
khi bận. Hướng tiếp cận này tiêu tốn thời gian CPU, nhưng có thể cũng
không hiệu quả. Ví dụ, xét một hệ thống có hai quá trình: A (với độ ưu
tiên cao) và B (với độ ưu tiên thấp) hợp tác trên một vùng tương tranh.
Hệ thống có giải thuật định thì sao cho: A được thực hiện ngay khi ở
hàng đợi sẵn sàng. Xét thời điểm mà B đang thực hiện trên vùng tương
tranh, và A ở hàng đợi sẵn sàng. Như vậy A phải đợi (trong vòng lặp),
nhưng B lại không được định thì. Vì thế B không có thể chạy để thóat
khỏi vùng tương tranh, và cũng phải đợi vô hạn để vào vùng tương tranh.
Tình huống này thỉnh thoảng được tham khảo như vấn đề đảo ngược độ
ưu tiên.
Do vậy, vấn đề đặt ra là khi quá trình cần thực hiện nhưng phải đợi thì nó
gọi thủ tục SLEEP để chuyển sang trạng thái ngủ (hay blocked) thay vì
chiếm giữ CPU. Khi quá trình khác dùng xong vùng tương tranh, nó sẽgọi thủ tục WAKEUP để chuyển quá trình đang “ngủ” sang trạng thái
họat động (“thức”). Giải pháp này được gọi là ngủ - thức.
Ví dụ, ta có thể áp dụng phương pháp này cho bài toán sản xuất – tiêu
thụ. Khi vùng đệm chung không còn chỗ trống để quá trình sản xuất ghi,
quá trình này sẽ tự gọi SLEEP và chuyển sang “ngủ”. Nó sẽ được “đánh
thức” khi quá trình tiêu thụ đã đọc 1 mục từ vùng đệm chung. Tương tự,
Khi vùng đệm rỗng, quá trình tiêu thụ cũng chuyển sang trạng thái ngủ
cho đến khi quá trình tiêu thụ đặt một giá trị mới vào vùng đệm và đánh
thức nó.
Hai quá trình có thể được cài đặt như sau: Để lưu giữ số mục trong vùng đệm, ta dùng biến count. Giả sử số mục
lớn nhất của vùng đệm là N.
- Quá trình sản xuất:
- Nếu count = N thì Æ chuyển sang trạng thái ngủ.
- Nếu không, ghi thêm 1 mục và tăng giá trị count.
- Quá trình tiêu thụ
- Nếu count = 0 Æ chuyển sang trạng thái ngủ
- Nếu count >0 thì đọc một mục và giảm count 1 đơn vị.
Tuy nhiên, ta thấy rằng điều kiện cạnh tranh giữa hai quá trình vẫn có thể
xảy ra. Ví dụ xét tình huống sau:
- Giả sử vùng đệm đang là rỗng, và quá trình tiêu thụ đọc biến count
với giá trị 0.
- Ở thời điểm, bộ định thì chuyển từ quá trình tiêu thụ sang quá trình
sản xuất. Quá trình sản xuất ghi một mục lên vùng đệm và tăng count
lên 1. Đồng thời, nó suy luận rằng count có giá trị 0 tức là quá trình
tiêu thụ đang ngủ. Nên quá trình sản xuất gởi tín hiệu WAKEUP đến
quá trình tiêu thụ.
- Thực tế, lúc này quá trình tiêu thụ ở hàng đợi sẵn sàng, không ở trạng
thái ngủ nên tín hiệu WAKEUP bị mất. Khi quá trình quay lại chu kỳ
kế tiếp, nó dựa vào giá trị count trước đó là 0 nên lại thực sự chuyển
sang trạng thái ngủ.
- Tiến trình thực hiện được lặp lại và dẫn đến vùng đệm bị lấp đầy bởi
quá trình tiêu thụ. Sau đó quá trình này cũng chuyển đến trạng thái
ngủ.
Æ Cả hai quá trình cùng ngủ không thời hạn. Vấn đề chủ yếu ở đây là tín hiệu WAKEUP bị mất. Vì thế, giải pháp là
dùng một bit lưu giữ tín hiệu WAKEUP đã được gởi, gọi là bit đợi
wakeup (wakeup waitting bit). Bit đợi wakeup được tính như sau:
- Khi tín hiệu WAKEUP được gởi đến một quá trình không ở trạng thái
ngủ thì bit được bật ON, biểu thị quá trình có một tín hiệu WAKEUP.
- Khi một quá trình đang chuyển sang trạng thái ngủ, nếu bit là ON thì
được chuyển thành OFF.
Khi có nhiều hơn hai quá trình cùng hợp tác trên vùng đệm, ta có thể
dùng mỗi quá trình 1 bit trạng thái và tạo thành 1 dãy (piggy bank) các tín
hiệu WAKEUP. Các giải pháp sau lần lượt đề nghị các phương pháp cài
đặt kỹ thuật này.
4.3.3.1 Giải pháp dùng semaphore
Giải pháp này dùng một biến nguyên để đếm số tín hiệu wakeup (đã được
gởi cho một quá trình) cần lưu giữ. Giải pháp được đề nghị bởi Dijkstra
(1965), gọi là semaphore, được tính như sau:
- Semaphore là 0 biểu thị không có tín hiệu wakeup được giữ
- Ngược lại, quá trình có tín hiệu wakeup được giữ.
Hai phép tóan down và up (tương ứng với hai thủ tục sleep và wakeup)
thực hiện các thao tác trên semaphore.
Phép toán down: kiểm tra giá trị của semaphore và:
- Nếu semaphore > 0 thì giảm semaphore đi 1 (tức là tiêu thụ một tín
hiệu wakeup đã lưu giữ trước đó) và thực hiện lệnh kế tiếp.
- Nếu semaphore =0 thì quá trình chuyển sang trạng thái ngủ và chờ
cho đến khi semaphore lớn hơn 0.
Phép toán up: tăng giá trị của semaphore lên 1. Khi gọi, thủ tục thực hiện
như sau: - Nếu một (vài) quá trình đang chờ trên semaphore (ở phép tóan down),
thì hệ thống sẽ chọn (ngẫu nhiên) một quá trình để thực hiện
(wakeup). Do vậy, sau một tác vụ up thì semaphore sẽ vẫn là 0 nhưng
có số quá trình đang chờ trên nó sẽ ít đi 1.
Tác vụ cài đặt semaphore và ngủ hay wakeup một quá trình là không thể
tách rời. Tức là chúng được thực hiện ghép thành 1 tác vụ đơn (atomic).
Hai phép toán này có thể được mô tả bằng mã giả như sau:
Với wait, signal biểu thị tuần tự up và down.
Bây giờ, ta xét lại bài toán sản xuất – tiêu thụ dùng semaphore. Để hai tác
vụ trên nó là đơn thì cách đơn giản nhất là cài đặt các tác vụ up, down
như các lời gọi hệ thống. Bài toán dùng 3 semaphore để biểu thị trạng
thái của vùng đệm và ràng buộc độc quyền truy cập:
- full: đếm số mục của vùng đệm đã có dữ liệu, được khởi gán là 0
- empty: đếm số mục của vùng đệm là rỗng, khởi gán bằng kích thước
vùng đệm.
- multex: đảm bảo rằng hai (nhiều) quá trình không thể đồng thời thao
tác trên vùng đệm, được khởi gán là 1. Nếu bài toán chỉ có hai quá
trình thì semaphore này gọi là semaphore nhị phân (chỉ có 2 giá trị). Mỗi quá trình cần thực hiện phép down trước khi vào vùng đệm chung và
thực hiện phép up ngay sau khi thóat khỏi vùng đệm để ràng buộc độc
quyền truy cập không bị vi phạm.
Quá trình sản xuất theo mã giả như sau:
Tương tự, ta có quá trình tiêu thụ:
Một kiểu dùng semaphore khác là ẩn các ngắt hệ thống. Mỗi thiết bị I/O
của hệ thống sẽ có 1 semaphore với giá trị đầu là 0. Ngay sau khi khởi
động thiết bị, bộ phận quản lý quá trình sẽ thực hiện phép down trên semaphore của thiết bị nên thiết bị bị chặn (block) ngay lập tức. Khi một
ngắt I/O được gọi, trình xử lý ngắt sẽ gọi phép up trên semaphore của nó
để cho phép quá trình liên quan được thực hiện I/O.
4.3.3.2 Giải pháp Multex
Khi ta không cần semaphore để đếm số mục trong vùng đệm chung thì
đồng bộ giữa các quá trình chỉ cần dùng semaphore đơn giản, gọi là
mutex. Các semaphore mutex được dùng để quản lý hiệu quả việc độc
quyền truy cập, và dễ cài đặt.
Một semaphore mutex là một biến gồm 2 giá trị (cho 2 trạng thái):
unlocked và locked. Do vậy, ta chỉ cần 1 bit để biểu diễn nó, nhưng thực
tế ta dùng 1 số nguyên. Cụ thể, giá trị 0 biểu thị trạng thái unlocked và
các giá trị khác nghĩa là locked.
Hệ thống cài đặt 2 thủ tục thao tác trên mutex: mutex_lock và
mutex_unlock. Khi một quá trình cần thực hiện trên vùng tương tranh, nó
gọi thủ tục mutex_lock.
Nếu mutex là unlocked, quá trình được phép thực hiện trên vùng tương
tranh. Ngược lại, quá trình bị lock cho đến khi được unlock bởi quá trình
khác (đã thực hiện xong trên vùng tương tranh) bằng cách dùng thur tục
mutex_unlocked. Nếu nhiều quá trình đang bị locked thì hệ thống sẽ
chọn (ngẫu nhiên) một quá trình để unlock.
4.3.3.3 Giải pháp monitor
Bài toán sản xuất – tiêu thụ với có chế đồng bộ dùng semaphore như trên
phụ thuộc nhiều vào thứ tự gọi các semaphore. Thực vậy, giả sử hai lời
gọi down trong quá trình sản xuất được gọi theo thứ tự ngược:
down(&mutex) Æ down(&empty) (thay vì down(&empty) Æ
down(&mutex)), nên mutex được giảm trước empty. Nếu vùng đệm chung đang đầy, quá trình sản xuất sẽ bị chặn với mutex là 0. Đến lượt
quá trình tiêu thụ thực hiện phép down trên mutex khi cần dùng vùng
đệm và cũng bị block. Như vậy, cả hai quá trình bị block vô hạn. Tình
huống này được gọi là treo (deadlock).
Hoare (1974) đề nghị một giải pháp, đồng bộ hóa mức cao gọi là
monitor, để khắc phục hạn chế trên. Ý tưởng chính là các thủ tục sử dụng
semaphore không được thay đổi thứ tự thực hiện của chúng.
Một monitor là tổ hợp của các thủ tục, các biến và các cấu trúc dữ liệu
được nhóm lại trong 1 modul (hay package). Các quá trình có thể gọi các
thủ tục trong một monitor nhưng không thể truy cập trực tiếp các dữ liệu
cục bộ từ các thủ tục bên ngoài monitor. Quy tắc này định nghĩa chung
trong các ngôn ngữ hướng đối tượng như Java. Ví dụ, một monitor được
viết bằng Pigdin Pascal: Để đảm bảo ràng buộc độc quyền truy cập, monitor cung cấp tính chất:
tại một thời điểm chỉ có 1 quá trình có thể họat động trong monitor.
Thực vậy, monitor là cấu trúc đặc biệt của 1 ngôn ngữ, nên trình biên
dịch sẽ thực hiện các thủ tục trong nó theo cách thức khác với các thủ tục
khác. Thông thường, khi một quá trình gọi một thủ tục của một monitor,
đầu tiên thủ tục sẽ kiểm tra xem có quá trình nào đang họat động trong
monitor không. Nếu có, quá trình cần gọi phải tạm ngưng cho đến khi
quá trình trên thóat khỏi monitor.
Vì thế, nếu phần thực hiện trên vùng tương tranh được ghép trong các thủ
tục của monitor, hệ thống sẽ đảm bảo rằng không có hai (nhiều) quá trình
cùng thực hiện trên vùng tương tranh ở cùng 1 thời điểm.
Tương tự với semaphore, hệ thống cũng cần cơ chế để block quá trình
khi chúng không được thực hiện trên vùng tương tranh. Trong giải pháp
trên, hệ thống dùng 2 semaphore full, empty. Ở đây, ta dùng các biến
điều kiện với hai phép toán trên chúng: wait và signal.
Khi một thủ tục monitor (qua một quá trình sản xuất) thấy rằng phải
ngưng (ví dụ, vùng đệm đầy), nó thực hiện phép wait trên các biến điều
kiện full. Tác vụ này thực hiện 2 công việc: ngưng quá trình và cho phép
quá trình khác thực hiện trên vùng tương tranh.
Quá trình tiêu thụ có thể gọi wakeup quá trình đang bị block bằng cách
thực hiện phép signal trên biến điều khiển của quá trình đang block. Để
ngăn ngừa hai quá trình cùng họat động trong monitor ở cùng một thời
điểm, ta cần một quy tắc xác định những gì sẽ thực hiện sau một phép
signal. Hansen đề nghị một phương pháp cho vấn đề này: một quá trình
thực hiện phép signal phải thoát khỏi monitor ngay lập tức. Nói cách
khác, câu lệnh signal (nếu có) phải là lệnh cuối trong một thủ tục
monitor. Hơn nữa, nếu phép signal được thực hiện trên một biến điều kiện mà có nhiều quá trình đang block thì chỉ một quá trình được chọn
(theo bộ định thì) để nhận signal.
Bài toán sản xuất – tiêu thụ dùng monitor được cài đặt dùng Pidgin
Pascal như sau:
Ở một thời điểm, chỉ một thủ tục monitor được dùng. Đồng thời, giả sử
vùng đệm có N mục.
Monitor cài đặt là ProducerConsumer chứa các biến điều kiện (full,
empty), hai thủ tục monitor thao thác trên vùng đệm chung(insert,
remove) và một semaphore count.
monitor ProducerConsumer
condition full, empty;
integer count;
procedure insert(item: integer);
begin
if count = N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty)
end;
function remove: integer;
begin if count = 0 then wait(empty);
remove = remove_item;
count := count 1;
if count = N 1 then signal(full)
end;
count := 0;
end monitor;
Hai phép toán wait, signal họat động khác với hai phép tương ứng sleep
và wakeup. Thực vậy, hai phép sau tạo ra một lỗi trong tình huống một
quá trình đang chuyển sang trạng thái ngủ, đồng thời theo trình tự thực
hiện, một quá trình cố gắng wakeup nó. Nhưng với hai phép đầu, tình
huống trên không xảy ra. Cụ thể, khi quá trình sản xuất nhận thấy vùng
đệm đầy, nó sẽ hoàn thành thực hiện phép wait mà không e rằng hệ thống
sẽ chuyển sang quá trình khác trước khi nó thực hiện xong phép wait.
Tóm lại, hai phương pháp semaphore và monitor được thiết kế với hệ
thống đa xử lý dùng chung một bộ nhớ chia sẻ (chứa vùng đệm chung). Nhưng khi mở rộng phạm vi các quá trình hợp tác trên hệ thống phân tán
gồm nhiều CPU. Các CPU có bộ nhớ riêng, và kết nối qua một LAN thì
các cơ sở của hai phương pháp này không thể áp dụng được. Phương
pháp semaphore dùng ở mức quá thấp và monitor cho có thể áp dụng
trong một vài ngôn ngữ lập trình. Do vậy, hệ thống cần các cơ chế trao
đổi thông tin giữa các máy.
4.3.3.4 Giải pháp truyền thông điệp
Phương pháp này áp dụng trên một hệ thống phân bố (các quá trình hợp
tác có thể chạy trên các máy tính khác nhau) bằng cách dùng các cơ sở
truyền tin send và receive theo dạng sau:
send(destination, &message);
receive(source, &message);
Giải pháp này dựa trên giả định rằng việc truyền thông điệp trên mạng là
hoàn hảo. Có nghĩa là hệ thống đảm bảo rằng một thông điệp được truyền
đúng đến máy nhận. Đồng thời, ta có thể giả sử rằng các thông điệp có
kích thước giống nhau.
Bài toán sản xuất – tiêu thụ được cụ thể hóa trong hệ thống phân tán như
sau:
- Vùng đệm chung có N mục được thay bằng N thông điệp
- Khởi đầu, quá trình tiêu thụ gởi N thông điệp rỗng cho quá trình sản
xuất.
- Khi quá trình sản xuất muốn ghi 1 mục, nó lấy một thông điệp rỗng để
ghi và gởi lại cho quá trình tiêu thụ.
Trong mô hình này, số thông điệp còn lại luôn là một giá trị hằng, nên
chúng có thể được lưu giữ trên một vùng nhớ có kích thước xác định.
void producer(void)
{ int item;
message m;
while (TRUE) {
item = produce_item(); /* generate someth
receive(consumer, &m); /* wait for an emp
build_message(&m, item); /* construct a mes
send(consumer, &m); /* send item to co
}
}
void consumer(void)
{
int item, i;
message m;
for (i = 0; i < N; i++) send(producer, &m);
while (TRUE) {
receive(producer, &m);
item = extract_item(&m);
send(producer, &m);
consume_item(item);
}
}
Nếu quá trình sản xuất thực hiện nhanh hơn quá trình tiêu thụ, số thông
điệp trống sẽ hết. Nên quá trình sản xuất sẽ bị chặn và đợi cho đến khi có
thông điệp trống. Ngược lại, tất cả thông điệp sẽ trống và đợi quá trình
sản xuất ghi dữ liệu. Tương tự quá trình tiêu thụ bị chặn và đợi một thông
điệp full.
Vấn đề còn lại và xác định địa chỉ cho thông điệp. Có hai phương pháp
cho định địa chỉ. Thứ nhất, mỗi quá trình có một địa chỉ và địa chỉ thông
điệp xác định theo địa chỉ quá trình. Ví dụ: địa chỉ của một quá trình xác định theo địa chỉ socket (địa chỉ máy + địa chỉ cổng I/O). Cách còn lại là
sử dụng một hộp thư (mailbox) của mỗi máy để lưu giữ thông điệp.

4.4 Các bài toán đồng bộ
4.4.1 Bài toán bộ đọc – bộ ghi
Trong mô hình truy cập cơ sở dữ liệu trên môi trường nhiều người dùng,
bài toán đồng bộ liên quan đến việc nhiều người cùng đọc, ghi trên một
số bảng cơ sở dữ liệu. Một quá trình đọc cơ sở dữ liệu gọi là bộ đọc
(reader). Quá trình cập nhật dữ liệu gọi là bộ ghi (writter).Ví dụ, một hệ
thống bán vé máy bay có nhiều quá trình cùng thực hiện thao tác đọc, ghi
trên cơ sở dữ liệu khách hàng. Có hai ràng buộc cần tuân thủ để đạt đồng
bộ đọc, ghi. Thứ nhất, tại một thời điểm, hệ thống cho phép chỉ một quá
trình cập nhật dữ liệu và nhiều quá trình đọc. Tương tự, ràng buộc thứ hai
là: khi một số quá trình đang đọc, không có quá trình nào được phép cập
nhật dữ liệu. Phần này, ta xét đến cách thức áp dụng các giải pháp trên
với bài toán reader – writter.
Giải pháp thông dụng là sử dụng một semaphore db để cài đặt cơ chế độc
quyền truy cập trên cơ sở dữ liệu. Số lượng các reader muốn truy cập dữ
liệu được biểu thị bởi biến rc. Cuối cùng semaphore mutex kiếm soát
việc truy cập đến rc.
typedef int semaphore;
semaphore mutex = 1;
semaphore db = 1;
int rc = 0;
Khi reader đầu tiên thực hiện phép down trên semaphore db để lây quyền
truy cập dữ liệu. Kế tiếp, các reader tăng giá trị bộ đếm rc lên 1, và truy
cập dữ liệu. Sau khi kết thúc truy cập, chúng giảm bộ đếm truy cập. Reader cuối thực hiên phép up trên semaphore db để cho phép writter
(đang đợi) được cập nhật dữ liệu.
void reader(void)
{
while (TRUE){
down(&mutex);
rc = rc + 1;
if (rc == 1) down(&db);
up(&mutex);
read_data_base();
down(&mutex);
rc = rc - 1;
if (rc == 0) up(&db);
up(&mutex);
use_data_read();
}
}
Tương tự với bài toán sản xuất – tiêu thụ, một writter cần thực hiện phép
down trên db để lấy quyền cập nhật dữ liệu. Sau khi cập nhật không,
writter phải tăng lại db lên 1.
void writer(void)
{
while (TRUE){
think_up_data();
down(&db);
write_data_base();
up(&db);
}
}
Giải pháp này phát sinh vấn đề khi có quá nhiều reader trên hệ thống. Cụ
thể, ta giả định một tình huống sau: - Khi một reader đang đọc dữ liệu, hệ thống có một (nhiều) reader khác
cùng đến. Hiển nhiên, các reader này được phép đọc dữ liệu chia sẻ.
- Sau đó, một writer cần cập nhật dữ liệu thì writer này phải chờ cho
đến khi không có reader nào đang đọc dữ liệu.
- Sau writer, các reader khác tiếp tục yêu cầu đọc dữ liệu và được chấp
nhận.
Æ Writer sẽ chờ gần như vô thời hạn.
Để ngăn ngừa tình huống này, ta có thể có hai giải pháp. Với giải pháp
thứ nhất, hệ thống xếp các reader yêu cầu đọc sau thời điểm của writer
phải đợi writer thay vì được chấp nhận. Tuy nhiên, giải pháp này có hiệu
năng không cao vì ít tính đồng bộ đọc-ghi.
Giải pháp thứ hai liên quan đến xác định độ ưu tiên đọc – ghi cho các
reader và writer.

4.4.2 Bài toán các triết gia ăn tối
Bài tóan này được đề nghị bởi Dijkstra (1965) để giải quyết vấn đề đồng
bộ hóa được gọi là “các triết gia ăn tối”. Bài toán được mô tả như sau: Năm triết gia cùng ăn tối quanh một bàn tròn. Trước mặt mỗi ông là một
đĩa thức ăn. Để ăn, mỗi người cần phải có 2 chiếc nĩa. Các chiếc nĩa được
đặt giữa 2 người. Hoạt động của các triết gia gồm: ăn và suy nghĩ. Khi
một triết gia đói, ông ta yêu cầu hai chiếc nĩa (trái và phải). Nếu cả hai
chiếc là rỗi, ông ta lấy nĩa để ăn, ngược lại ông ta phải chờ. Sau khi ăn
xong, ông ta đặt nĩa ở vị trí cũ và tiếp tục suy nghĩ.
Bài toán này được xem như bài toán kinh điển bao gồm nhiều vấn đề
như: đồng bộ hóa, cấp phát tài nguyên để tránh khóa chết.
Bài toán có thể được giải bằng cách dùng một semaphore mutex. Khi một
triết gia cần dùng nĩa, ông phải thực hiện phép down trên mutex. Sau khi
dùng nĩa xong, ông ta lại phải gọi up trên mutex. Từ quan điểm thực tế, ta
thấy với 5 chiếc nĩa, ta có thể cho phép hai ông cùng ăn ở một thời điểm.
Một cải tiến của giải pháp trên nhằm đảm bảo không xuất hiện khóa chết
và tối đa số triêt gia họat động đồng thời.
Giải pháp sử dụng một mảng của các biến trạng thái, state. Mỗi biến
trạng thái lưu giữ trạng thái của một triết gia: ăn (eating), nghĩ (thinking)
hay đói – hungry (tức là, yêu cầu dùng nĩa). Một triết gia chỉ có thể
chuyển sang trạng thái ăn nếu không có láng giềng nào đang ăn. Triết gia
láng giềng được định nghĩa bởi các giá trị LEFT, RIGHT. Ví dụ, triết gia
đang xét là 2, thì các láng giềng là 2, 3.
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N]; /* one semaphore per philosopher */ void philosopher(int i)
{
while (TRUE){
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i)
{
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_forks(i)
{
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}
Chương trình dùng một mảng các semaphore với mỗi semaphore cho một
triết gia. Vì vậy, một triết gia yêu cầu nĩa nhưng các nĩa đang bận thì phải
chờ. Chú ý rằng mỗi quá trình chạy thủ tục philosopher như hàm main.
Nhưng các thủ tục take_forks và put_forks không thể tách rời trên các
quá trình khác nhau.

4.5 Tóm tắt
Trong hệ thống đa chương các quá trình thường phải hợp tác với nhau để
tăng tốc độ xử lý. Khi có nhiều quá trình cùng thao tác trên vùng dữ liệu
chung, tính độc quyền truy cập phải được đảm bảo. Giải pháp chính là
đảm bảo rằng chỉ một quá trình thực hiện trên vùng tương tranh tại một
thời điểm.
Các giải pháp ban đầu để giải quyết vấn đề đều dựa trên nguyên tắc chờ -
bận. Hậu quả là một quá trình có thể chờ trong khi đang giữ CPU và làm
phí tổn CPU của hệ thống. Giải pháp semaphore khắc phục hạn chế trên.
Semaphore có thể áp dụng để giải quyết các vấn đề đồng bộ khác nhau,
đặc biệt là trong hệ thống hỗ trợ các thao tác nguyên tố (đơn).
Các bài toán đồng bộ cổ điển (bài toán sản xuất tiêu thụ, reader – writer,
năm triết giá ăn tối,…) cho phép ta phân lớp các vấn đề đồng bộ quá
trình. Các bài này cũng gợi ý chuẩn để kiểm tra các giải pháp cài đặt cơ
chế đồng bộ.
Hơn nữa, hệ điều hành cũng cung cấp cơ chế đảm bảo chống lỗi thời
gian. Monitor cung cấp cách thức hữu hiệu để cài đặt các vấn đề đồng bộ
trong hệ thống có nhiều cấu hình máy khác nhau.
Khi vấn đề đồng bộ được mở rộng trên hệ thống phân bố, giải pháp
truyền thông điệp cho phép đồng bộ hóa giữa các quá trình trên các máy
khác nhau.
4.6 Câu hỏi & Bài tập
1. Hệ thống có một cặp semaphore đếm với 2 tác vụ up, down. Cặp
semaphore dùng để lấy và giải phóng 2 tài nguyên trong 1 hoạt động
cơ sở. Tác vụ down của cặp semaphore được định nghĩa như sau: Hãy viết hai thủ tục lấy và giải phóng 2 tài nguyên bằng cách dùng cặp
semaphore trên.
2. Xét các quá trình thực hiện đồng thời sau:
Hãy đề nghị 1 giải pháp đồng bộ P1, P2, P3 sao cho các lệnh được thực
hiện theo thứ tự sau: lệnh a trước lệnh f, lệnh e trước lệnh h, lệnh g trước
lệnh c, và lệnh g trước lệnh i.
3. Bài tóan đọc, ghi được định nghĩa như sau: một quá trình chỉ có thể
đọc trên vùng tranh chấp nếu không có quá trình đang ghi hay đang
đợi để ghi lên vùng tranh chấp. Hãy đề nghị các biến chung và
semaphore để cài đặt giải pháp tổng quát cho bài tóan trên, và viết cấu
trúc sơ lược cho:
a. Thủ tục đọc
b. Thủ tục ghi
4. Giả sử hệ thống phân tán có hai quá trình P1, P2 thực hiện trên 2 CPU
Pi, Pj. P1 và P2 được đồng bộ hóa với semaphore nhị phân flag. a. Cho biết thứ tự thực hiện của các câu lệnh a,b,c,d trong 2 quá
trình trên. Giả sử rằng tác vụ down được định nghĩa: “đợi cho
đến khi ta nhận được thông điệp FF từ một quá trình đang thực
hiện trên 1 CPU bất kỳ”, và tác vụ up được định nghĩa: “gởi
một thông điệp FF đến tất cả CPU”.
b. Nếu hai hay nhiều quá trình dùng cài đặt trên của flag trong
họat động truy cập đồng bộ dữ liệu chung, thì chúng có thể dẫn
đến tình huống vi phạm điều kiện “độc quyền truy cập” không?

THỜI GIAN LOGIC VECTOR VÀ VẤN ĐỀ ĐỒNG BỘ HÓA CÁC TIẾN TRÌNH TRONG BÀI TOÁN BÃI ĐỖ XE NHIỀU CỔNG

TÓM TẮT Ngày nay, một trong những hướng nghiên cứu quan trọng trong hệ thống phân tán đó là vấn đề đồng bộ hóa các tiến trình sử dụng tài nguyên dùng chung. Để đạt được điều đó thì chúng ta phải đảm bảo được trật tự như nhau các thông điệp yêu cầu tài nguyên ở tất cả các trạm/máy chủ có trong hệ. Đề tài tập trung nghiên cứu vấn đề đồng bộ hóa các tiến trình của bài toán bãi đỗ xe nhiều cổng với hệ thống thời gian vector (Vector time) của Fidge, Mattern và Schmuck. Giải pháp này có thể  đảm bảo được trật tự nhân quả chặt chẽ của các sự kiện diễn ra trong hệ thống phân tán, đảm bảo các tiến trình trong bài toán hoạt động hoàn toàn ăn khớp với nhau và đạt được trạng thái gắn bó tài nguyên thông tin dùng chung.
 1. Đặt vấn đề Một hệ thống phân tán bất kỳ nào cũng được cấu tạo từ n thành phần. Các thành phần này có thể là các tiến trình hoặc các trạm, các nút hoặc các máy Server không dùng bộ nhớ chung và liên lạc với nhau bằng cách duy nhất là trao đổi thông điệp. Mỗi một thành phần như thế hoạt động như một otomat có nghĩa là nó triển khai các phép toán có khả năng thay đổi trạng thái của mình và của toàn hệ thống. Các phép toán thực hiện bằng một trong những thành phần vừa nêu phải được sắp xếp một cách tự nhiên theo những trình tự diễn ra. Nếu một tiến trình nào đó cho phép chứa nhiều luồng, trên hệ thống đơn bộ xử lý, đó chính là trật tự thực hiện các lệnh trên bộ xử lý này. Chính bộ xử lý này đảm nhận vai trò sắp xếp các sự kiện. Việc xác định trật tự các sự kiện trên hệ thống đa bộ xử lý là một vấn đề phức tạp liên quan đến những khó khăn trong việc duy trì một thời gian tuyệt đối gắn bó. Đối với hệ tin học phân tán, việc thống nhất các giá trị của đồng hồ vật lý để đồng bộ hóa các sự kiện là việc làm không khả thi vì những lý do sau đây:  Độ trễ của truyền thông.  Sự không thống nhất các đồng hồ vật lý theo một chuẩn nhất định.  Xử lý không theo thời gian thực. 2. Thời gian logic vector 1. Giới thiệu

Hệ thống đồng hồ vector được Fidge, Mattern và Schmuck đề xuất. Mỗi đồng hồ là một vector n chiều thể hiện bởi n phần tử không âm. Mỗi trạm Si nắm giữ một vector Hi [1..n], với Hi được gọi là đồng hồ cục bộ của trạm Si (i là số thứ tự của trạm Si trong hệ, 1≤ i ≤n , n là số trạm có trong hệ). Hi[j] cho thấy hiểu biết mới nhất của Si về thời gian cục bộ của trạm Sj. Như vậy thời gian vector cho ta thấy toàn cảnh của thời gian logic giữa các trạm. 2. Cập nhật đồng hồ logic    Các quy luật để một trạm Si cập nhật lại đồng hồ logic vector của mình:  Trước khi thực hiện một sự kiện bất kỳ, Si cập nhật lại thời gian logic của nó như sau:                                              Hi[i]=Hi[i] + d (Với d là một số gia)  Trước khi gửi một thông điệp m đi, trạm Si sẽ gán nhãn thời gian cho thông điệp ấy theo thời gian t mới nhất của trạm Si vào thời điểm gửi. Trạm Sj khi nhận được thông điệp sẽ cập nhật lại đồng hồ logic của nó theo công thức:                 Hj = sup( Hj ,t); Với sup(u,v)=w; w[i]=max(u[i],v[i]) (u, v, w là các vector n chiều; 1≤i≤n; 1≤i≤n) 3. So sánh hai vector Cho hai vector H1, H2 với kích thước thước n, chúng có thể được so sánh với nhau theo công thức sau đây:      H1≤H2 nếu H1[i]≤H2[i] với 1≤i≤ n      H1<H2 nếu H1≤H2 và not (H1=H2).      H1||H2 nếu not (H1<H2) and not (H2<H1).    
4.  Xác lập thứ tự nhân quả giữa hai sự kiện Việc xác lập trật tự nhân quả của hai sự kiện e1 và e2 bất kỳ được thực hiện dựa trên những quy luật sau đây: Quy tắc 1: Nếu hai sự kiện e1, e2 xảy ra trên cũng một trạm Si (i là số thứ tự của trạm trong hệ), khi đó e1e2 khi và chỉ khi  Hi(e1)<Hi(e2). Quy tắc 2: Nếu e1 là sự kiện gửi đi một thông điệp m trên một trạm, và e2 là sự kiện nhận đươc chính thông điệp đó thì e1e2. Quy tắc 3: Nếu hai sự kiện e1, e2 xảy ra trên hai trạm Si, Sj  bất kỳ trong hệ (i, j là số thứ tự của trạm) thì ta có e1e2  Hi(e1)<Hj(e2). Quy tắc 4 :Nếu hai sự kiện e1, e2  ta có  e1||e2  H(e1)||H(e2).  3. Bài toán bãi đỗ xe nhiều cổng Bài toán được phát biểu như sau: Có một bãi đỗ xe hiện đại trong đó có m chỗ để xe và n cổng vào/ra, tại mỗi cổng có người bảo vệ có nhiệm vụ phân phối cho các xe cụ thể.

Mô hình của bãi đỗ xe nhiều cổng  Trong bài toán, chúng ta xem các trạm gác là các Server, người thực giữ cổng là các chương trình cài đặt trên các Server, các chỗ trong bãi đỗ xe là các tài nguyên. Tại mỗi trạm sẽ có hai tiến trình, trong đó, một tiến trình phát có nhiệm vụ truyền đi các thông điệp: Thông điệp kiến nghị vào bãi, hoặc ra khỏi bãi, hoặc yêu cầu cung cấp, tiến trình nhận có nhiệm vụ nhận các thông điệp truyền đến nó.  Khi một xe yêu cầu vào vị trí đậu, có nghĩa là tiến trình yêu cầu tài nguyên dùng chung. Ngược lại, khi một xe yêu cầu ra khỏi vị trí đậu, nghĩa là tiến trình khuyến nghị giải phóng tài nguyên dùng chung. Bài toán đỗ xe có ít nhất là hai cổng, ở đây ta giả sử là có bốn cổng. Số lượng vị trí trong bãi là 25, mỗi cổng tương ứng với một trạm trên mạng. Mỗi trạm có một địa chỉ IP duy nhất định danh cho trạm và một Port để quy định dịch vụ hoạt động trên cổng đó.  Nói cách khác, hệ thống bãi đỗ xe là một hệ thống đa Server bao gồm Server1 (bảo vệ 1), Server2 (bảo vệ 2), Server3 (bảo vệ 3), Server4 (bảo vệ 4). Mỗi Server đều có một cơ sở dữ liệu riêng rẽ để chứa dữ liệu. Dữ liệu ở đây là các thông tin vào và ra của các xe. Như vậy, tại một trạm nào đó, một xe yêu cầu được vào bãi thì tiến trình phát tại trạm này sẽ phát sinh các thông điệp và gởi các thông điệp đến trạm khác và ngay cả chính nó. Những thông điệp này sẽ được nhận bởi các tiến trình nhận tạị trạm nhận và đưa vào hàng đợi cục bộ của nó. Phân tích bài toán bãi đỗ xe ở trên, chúng ta nhận thấy việc sắp xếp các thông điệp được phát ra từ các trạm là điều cực kỳ quan trọng để đảm bảo tính đồng bộ của dữ liệu nhằm quản lý tốt các dòng xe vào và ra. Vấn đề này đặt ra yêu cầu phải duy trì một thời gian tuyệt đối đồng bộ.    
4. Giải pháp cho bài toán bãi đỗ xe nhiều cổng Việc đồng bộ hóa các tiến trình vào và ra trong bài toán bãi đỗ xe được thực hiện nhờ giải thuật loại trừ tương hỗ phân tán nhờ dấu trên cơ sở thời gian vector. Gọi n là số trạm trong hệ, m1 là thông điệp yêu cầu vào bãi, m2 là thông điệp trả lời của tiến trình Pj cho tiến trình Pj khi nhận được thông điệp yêu cầu từ tiến trình Pi, m3 là thông điệp yêu cầu ra khỏi bãi của tiến trình Pi. Với i, j là số thứ tự của các trạm trong hệ, 1≤ i ≤n, 1≤ j ≤n, H1, H2, H3 là dấu của thông điệp m1, m2, m3 (Quy định thời gian logic tại thời điểm gởi thông điệp).    

Khi tiến trình Pi muốn vào bãi thì quá trình gửi và nhận thông điệp sẽ xảy ra như sau:  Pi gửi thông điệp yêu cầu vào m1 cho tất cả các tiến trình trong mạng Pj (với 1≤j≤n).  Pj nhận được thông điệp này thì đẩy thông điệp vào hàng đợi cục bộ của trạm và trả lời cho Pi bằng thông điệp m2.  Tại Pi sau khi nhận được thông điệp trả lời (từ tất cả các trạm) rồi dựa trên sự xem xét yêu cầu của nó xem có tiếp tục vào bãi không. Tiến trình Pi muốn ra khỏi bãi:  Pi gửi thông điệp yêu cầu ra m3 cho tất cả các tiến trình khác trong mạng.  Xóa yêu cầu vào tương ứng của nó trong hàng đợi cục bộ.  
5. Kết luận  Đề tài nhằm tập trung nghiên cứu về thời gian vector và vận dụng thời gian nhằm tiến hành đồng bộ hóa các tiến trình trong bài toán Bãi đỗ xe nhiều cổng và đạt được những kết quả sau: - Mô phỏng bài toán bãi đỗ xe là một hệ thống đa Server trong hệ phân tán.
- Xác lập trật tự nhân quả chặt chẽ của các thông điệp trên cơ sở thời gian vector.
- Dựa vào trật tự nhân quả chặt chẽ giữa các thông điệp, xây dựng giải pháp đồng bộ hóa dữ liệu giữa các trạm.
- Kết quả thu được cho thấy sự hợp lực chính xác giữa các bảo vệ của các trạm bằng cách trao đổi thông điệp đã đảm bảo điều khiển chính xác các dòng xe vào và ra. Những kết quả mà bài toán bãi đỗ xe đạt được là rất đáng khích lệ bởi vì nó có thể phát triển để giải quyết những bài toán tương tự đặt ra trong thực tế như bài toán đặt vé máy bay, đặt nơi du lịch, hoặc các ứng dụng lớn như thương mại điện tử, giáo dục điện tử…Đây là những bài toán cần phân tán các chức năng của nó trên các trạm để thời gian trả lại có kết quả tốt hơn. Do đó nó cần được mô phỏng như một hệ đa Server trong hệ phân tán.  Vì lượng thông tin của chúng rất lớn và nhu cầu giao dịch rất nhiều, do đó cần phân tán các giao dịch trên các trạm khác nhau để thời gian giao dịch nhanh chóng và chính xác, tránh lãng phí tài nguyên và tranh chấp tài nguyên. Muốn vậy, giải pháp xây dựng cần phải đảm bảo một sự đồng bộ dữ liệu giữa các trạm tại mọi thời điểm. Điều này ta hoàn toàn có thể tin tưởng ở kết quả thu được từ bãi toán Bãi đỗ xe.   Đề tài có thể được nghiên cứu tiếp theo những hướng sau: - Tiến hành giảm kích thước của nhãn thời gian vector khi đính vào thông điệp và gửi đi trên đường truyền. - Tạo lát cắt ổn định (Consistent Cut) và ảnh chụp quang cảnh hệ thống (Snapshot) nhằm xử lý trường hợp mạng bị sự cố, tiến hành khôi phục lại tình trạng ổn định của mạng trước sự cố.

Nhằm:
- Đảm bảo Tính nhất quán của tài nguyêndùng chung
- Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình).
Ví dụ:
- 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.
- Ban Ba lên bảng (Tài nguyên dùng chung) viết thông tin liên lạc của mình cho lớp, nếu bạn chưa viết xong mà bạn Bá lên sửa lại nội dung thông tin của bạn Ba thì dẫn đến mọi người trong lớp sẽ lấy thông tin của bạn Ba bị sai, do vậy việc đồng bộ có tác dụng rất lớn nghĩa là chờ bạn Ba viết xong, sau đó mới tới bạn Bá thì đảm bảo mọi người bên dưới sẽ lấy được thông tin của bạn Ba và bạn Bá chính xác.

- Đoạn tương tranh là 1 đoạn mã trong chương trình của tiến trình người dùng mà khi chạy chương trình đó nó tác động đến tài nguyên dùng chung, biến dùng chung (count ++, count --,...), làm thay đổi những kết quả trong tài nguyên.
- Vùng tranh chấp: là không gian tài nguyên dùng chung.

Có một cây cầu bị yếu, để đảm bảo cầu không bị sập thì các xe phải lần lượt qua cầu từng chiếc một. Để thực hiện công việc đó ta điều khiển như sau:
- Gắn 1 đèn hiệu ở đầu cầu (đèn hiệu có 2 màu xanh và đỏ)
- Các xe đi đến cầu và xếp hàng lần lượt (ở đầu cầu), xe thứ nhất đang ở trạng thái chờ đèn xanh để được qua cầu. Khi đèn hiệu được bật màu xanh thì xe thứ 1 đc phép qua cầu, khi xe lên cầu thì đèn hiệu chuyển sang màu đỏ, khi xe qua khỏi cầu thì đèn hiệu sẽ bật sang màu xanh, xe thứ 2 được phép lên cầu, cứ tiếp tục cho đến khi hết xe đợi qua cầu (Khi qua cầu thì các xe sẽ đi tiếp hoặc quay về theo cung đường khác). Để xử lý công việc điều khiển đó ta xây dựng chương trình với đoạn code như sau:

Code xe thứ i:

Semaphore S = 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(S);  //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(S); //đèn chuyển sang màu xanh
  Đi tiếp;
  Quay về theo đường khác;
}

Các tiến trình P1-P2-P3 dùng cơ chế liên tục kiểm tra semaphore hay dùng cơ chế sleep-weakup mình không bàn đến, chỉ nêu lên thuật giải chính.
Dùng semaphore S với ba giá trị 1-2-3, giá trị khởi tạo bằng 1;
-Khi các tiến trình vào hệ thống chúng sẽ xét semaphore nếu S==1 thì P1 được thực thì, P1 thực thi xong S++;
-Nếu xét S==2 thì P2 được thực thì, P2 thực thi xong S++;
Tương tự cho P3 xét S==3 thì thực thi, sau đó P3 gán S=0;

Bài 2: đồng bộ hóa công việc của 3 tiến trình sao cho P1 trước P2 và P3
Tương tự cách giả quyết bài 1 nhưng P2 và P3 xét Semaphore S==2||S==3 thì sẽ được thực thi, điều này đảm bảo P2 P3 có quyền ngang hàng như nhau. P2 hoặc P3 thực thi xong sẽ xét nếu S==2=> S++, nếu S==3=> S=0;

Bài tóan này được đề nghị bởi Dijkstra (1965) để giải quyết vấn đề đồng
bộ hóa được gọi là “các triết gia ăn tối”. Bài toán được mô tả như sau: Năm triết gia cùng ăn tối quanh một bàn tròn. Trước mặt mỗi ông là một
đĩa thức ăn. Để ăn, mỗi người cần phải có 2 chiếc nĩa. Các chiếc nĩa được
đặt giữa 2 người. Hoạt động của các triết gia gồm: ăn và suy nghĩ. Khi
một triết gia đói, ông ta yêu cầu hai chiếc nĩa (trái và phải). Nếu cả hai
chiếc là rỗi, ông ta lấy nĩa để ăn, ngược lại ông ta phải chờ. Sau khi ăn
xong, ông ta đặt nĩa ở vị trí cũ và tiếp tục suy nghĩ.
Bài toán này được xem như bài toán kinh điển bao gồm nhiều vấn đề
như: đồng bộ hóa, cấp phát tài nguyên để tránh khóa chết.
Bài toán có thể được giải bằng cách dùng một semaphore mutex. Khi một
triết gia cần dùng nĩa, ông phải thực hiện phép down trên mutex. Sau khi
dùng nĩa xong, ông ta lại phải gọi up trên mutex. Từ quan điểm thực tế, ta
thấy với 5 chiếc nĩa, ta có thể cho phép hai ông cùng ăn ở một thời điểm.
Một cải tiến của giải pháp trên nhằm đảm bảo không xuất hiện khóa chết
và tối đa số triêt gia họat động đồng thời.
Giải pháp sử dụng một mảng của các biến trạng thái, state. Mỗi biến
trạng thái lưu giữ trạng thái của một triết gia: ăn (eating), nghĩ (thinking)
hay đói – hungry (tức là, yêu cầu dùng nĩa). Một triết gia chỉ có thể
chuyển sang trạng thái ăn nếu không có láng giềng nào đang ăn. Triết gia
láng giềng được định nghĩa bởi các giá trị LEFT, RIGHT. Ví dụ, triết gia
đang xét là 2, thì các láng giềng là 2, 3.
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N]; /* one semaphore per philosopher */ void philosopher(int i)
{
while (TRUE){
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i)
{
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_forks(i)
{
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}
Chương trình dùng một mảng các semaphore với mỗi semaphore cho một
triết gia. Vì vậy, một triết gia yêu cầu nĩa nhưng các nĩa đang bận thì phải
chờ. Chú ý rằng mỗi quá trình chạy thủ tục philosopher như hàm main.
Nhưng các thủ tục take_forks và put_forks không thể tách rời trên các
quá trình khác nhau.

dựa vào ví dụ xe đi qua cầu yếu. để hai xe có mặt trên cầu cùng lúc ta chỉ cần sửa đèn hiệu nhị phân Semaphore =2. như vậy đèn hiệu sẽ có 3 màu. màu xanh lá , xanh dương, màu đỏ.
tương tự vậy ta có thể áp dụng cho 3 ,4 xe cùng trên cầu.
Thay đổi đèn hiệu nhị phân giúp ta không cần chỉnh sửa code

Edsger Wybe Dijkstra(11/5/1930-6/8/2002) 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.
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[2].

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ó [3], để đ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.)[4]

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

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

Semaphore synch = 0;

- Cấu trúc P1:
S1
signal(synch, 2);

- Cấu trúc P2:
wait(synch);
S2

- Cấu trúc P3:
wait(synch);
S3

Giải thích:
Tại thời điểm ban đầu: synch=0,
Khi tiến trình P2 được thực hiện, thì P2 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi tiến trình P3 được thực hiện, thì P3 sẽ bị khóa tại hàm wait(synch) do synch=0 cho đến khi synch>0.
Khi P1 thực hiện, S1 được thi hành xong thì lệnh signal(synch, 2); được 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 hiện.
=>P1 đi trước P2 và P3.

Edsger Wybe Dijkstra (phát âm tiếng Hà Lan: [ˈɛtsxər ˈwibə ˈdɛɪkstra] ( nghe); 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[2].
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ó [3], để đ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.)[4]
Ô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.

Giải thưởng Turing (A. M. Turing Award) là giải thưởng thường niên của Hiệp hội Khoa học Máy tính Association for Computing Machinery cho các cá nhân hoặc một tập thể với những đóng góp quan trọng cho cộng đồng khoa học máy tính.Giải thưởng thường được coi như là giải Nobel cho lĩnh vực khoa học máy tính. Giải thưởng được đặt theo tên của nhà bác học Alan Mathison Turing, nhà toán học người Anh, người được coi là cha đẻ của lý thuyết khoa học máy tính và trí tuệ nhân tạo.Từ năm 2007, giải thưởng có giá trị $250.000, được đồng tài trợ bởi Intel và Google.
Alan Mathison Turing là một trong những nhà khoa học lớn bị lãng quên của thế kỷ XX, cho dù ông là cha đẻ của các máy tính, hay ít nhất cũng là một phần lý thuyết của nó. Sự đóng góp to lớn của ông quyết định cho sự chiến thắng của phe Đồng Minh trong Thế chiến thứ hai. Nhưng có thể nhà cầm quyền nước Anh khuyến khích ông tự vận, vì những lý do tối mật, đã giấu tên ông?
Alan M. Turing sinh ngày 23 tháng 6 năm 1912 tại London. Cha làm trong ngành thu thuế tại Ấn độ và mẹ đi theo cha năm 1913, để lại bé Alan từ người giám hộ này tới người giám hộ khác trong các nội trú. Alan không phải là một học trò giỏi. Các giáo sư phê bình ông là học trò lơ đễnh. Năm 15 tuổi, ông gặp Christopher Morton, và hai người bạn này đã cùng nhau trao đổi đam mê khoa học. Sự liên hệ này hơi mập mờ giữa tình bạn và tình yêu. Nhưng Christopher mất vào tháng hai năm 1930 đã làm Turing bối rối.
Tuy vậy, ông cũng thi đậu vô trường King's College tại Cambridge. Tại đây ông phát triển tài năng vì nhờ nơi này không ai chế nhạo sự đồng tính luyến ái và bề ngoài khác biệt của ông. Tại trường, mỗi người giữ cá tính của riêng mình, ai sao mặc ai. Alan tóc tai quần áo bê bối và thường không cạo râu, thích đạp xe đạp và đeo cái đồng hồ nơi thắt lưng để coi thời gian đạp xe và với một mặt nạ phòng khí độc đeo trên mặt để phòng dị ứng phấn hoa (hay fever). Ngoài việc chơi thể thao cấp cao (chạy bộ), Alan còn thích những công trình về cơ học lượng tử của John Von Neumann.
Cho dù ông lập dị, nhưng khả năng toán học rực rỡ và những việc làm của ông thật đặc sắc. Năm 1924 Turing in một bài báo chứng tỏ rằng toán luôn chứa những trạng thái mà không thể chứng minh hay bị bắt bẻ. Ngoài lý luận trên, ông dự tính một cái máy có thể tính bất cứ con số nào. Cái máy đó bao gồm một bộ phận điều khiển (control unit) và một bộ nhớ, có thể hoàn thiện nhiều thao tác cơ bản: đọc, viết hay xóa những ký hiệu trên băng (tape), và cho băng chạy tới hay chạy lui. "Máy Turing" đơn giản này dùng làm mẫu cho các máy tính số sau này.
Ông cũng thích môn sinh học, đặc biệt là mạng nối giữa các dây thần kinh. Ông tự hỏi: "Tại sao các máy quá tài tình trong việc tính toán mà lại hạn chế sự mô phỏng những hành động tự nhiên giản dị nhất của người như đi, cầm cái ly...)?"
Trước tuổi 30, ông đã tưởng tượng những căn bản cho một máy tính số (digital computer) tân kỳ và dẫn đầu về lý thuyết cơ bản cho thông minh nhân tạo (artificial intelligence).
Là người phát minh tư tưởng một cái máy vạn năng (universal machine) , tìm ra lý do quan trọng tại sao một máy tính có thể làm rất nhiều chuyện. Tiếc thay Turing không còn sống để thấy sự tiến triển khổng lồ của ngành thông tin, máy tính. Nhà toán học người Anh này sống trong hai thế giới khác nhau.

Trước công chúng, ông là một nhà toán học tài ba, đã giúp Thế giới đại chiến lần II thắng nhờ giải được các mã số của phe Đức. Còn bên trong, Turing là một người nhát gan, hay mắc cỡ, lập dị và bị đối xử tàn bạo do cách sống riêng biệt của ông đã đưa ông đến cái chết đau thương lúc 41 tuổi.
Năm 1935, ông hiệu chính khái niệm một máy vạn năng để hình thức hóa khái niệm toán giải bằng algorithme. Máy của Turing có khả năng cả một quá trình algorithme. Những máy tính hiện đại là những thực hiện cụ thể máy của Turing.
Năm 1936, Turing đến Princeton University, nơi này ông lấy bằng PhD Toán học và làm việc với nhà toán học người Mỹ gốc Hongrie là John von Neumann (1903-1957), nổi tiếng nhờ Cơ học Lượng tử. Nhờ đó Turing học thêm về xác suất và logique.

Turing trở về Anh quốc năm 1938. Liền sau đó ông vào quân đội Anh cho cuộc chiến tranh sắp đến. Đầu Thế chiến thứ hai, quân đội Đức thắng nhiều trận vinh quang trên biển. Một trong những chìa khóa của các chiến thắng đó là máy viết mật mã Enigma, một máy mã hóa điện từ, để giúp bộ tham mưu Đức truyền những thông điệp cho các tàu ngầm, những thông điệp mà phe các nước Đồng Minh không thể giải được . Do đó quân đội Anh nhóm họp trong một nơi tối mật: cơ quan "bẻ mật mã" chuyên giải mật mã của máy Enigme của Đức. Họ gồm 10.000 người thư ký, các nhà nghiên cứu và ngay cả những người chơi đánh bài, nghĩa là làm tất cả mọi việc để hiểu cơ chế của máy Egnima. Khối Đồng Minh có được những sơ đồ của máy này từ đầu chiến tranh và muốn hiểu tin mật mã của Đức, nhưng họ không thành công.
Turing đến gặp của quân đội Anh tại Bletchley Park và đã giúp họ thiết kế máy tính Bombe, một máy tính rất nhanh có thể giải mã nhanh chóng bằng cách thử hàng ngàn code khác nhau. Turing làm việc với một nhà toán học khác, Gordon Welchman. Trước khi chiến tranh chấm dứt, ông đã cho ra đời một máy điện tử, máy Kolossus, dùng để giải mã tất cả những thông điệp Đức.
Sau chiến tranh, ông trở về làm việc tại Automatic Digital Machine, một computer lớn tại University of Manchester và tin rằng giữa người và máy chỉ khác tí xíu về xử lý tín hiệu. Ông sáng chế ra máy Turing Test để đo khả năng nhận thức cảm nghĩ. Turing đề nghị rằng một cái máy có thể xem như nhận thức đuợc nếu như nó lừa được những người hỏi nó nếu như nó ở một phòng và nói chuyện với một người đó ở phòng khác.
Thiên tài của Turing được Churchill công nhận. Churchill đã giao cho Turing nhiệm vụ làm một hệ thống thông tin tối mật để ông liên lạc với tổng thống Roosevelt. Nhân cơ hội đó, Turing qua Hoa kỳ và gặp Claude Shannon, người sáng lập ra thuyết Tin học và là người phát minh ra bit, 0-1.
Cũng trong thời kỳ chiến tranh mà ông hỏi cưới duy nhất một người: cô Joan Clarke. Cô Joan dạy Turing đan áo. Turing tặng cô quyển Tess of Uberville, tác giả Thomas Hardy và thú thật rằng ông có biệt nhãn với người cùng phái. Họ trở thành bạn của nhau từ đó. Turing không muốn những người láng giềng thấy mặt và sợ dị ứng với phấn hoa nên thường đi xe đạp và mang mặt nạ chống khí độc của chiến tranh. Có khi ông từ chối không ký tên lên thẻ kiểm tra chỉ vì trong hồ sơ có ghi câu "Tất cả mọi hình thức viết tay đều bị cấm". Ông viết: "Cái mà tôi thích không phải tạo ra bộ óc tài ba, mà chỉ cần một bộ óc ngu ngốc cỡ bộ óc của ông chủ tịch hãng điện thoại American Telephone và hãng điện báo Telegraph Company"
Vì thất vọng, ông đã ăn một trái táo có tẩm cyanur và mất đúng ngày lễ Pentecôte 7 tháng 6 năm 1954 tại Wilmslow, England.
Hội Alan Turing Memorial Fund (Tưởng niệm Alan Turing), thành lập từ năm 1996 thành lập một quỹ, quyên tiền để xây dựng một tượng kỷ niệm bằng đồng cho Turing. Đến cuối năm 2000 mới quyên được £15,000.
Tượng của Alan Mathison Turing tay cầm trái táo, để tưởng niệm cái chết đau đớn của ông.
Hãng Apple có cái logo trái táo cắn nửa chừng, cũng có ý như vậy? Đây chỉ là giai đoạn khai sinh của ngành này

- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi dùng xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.
* Giải pháp ngăn chặn Deadlock
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy
Ví dụ : kẹt xe giữa đường hay cầu , chỉ cần 1 cái j đó để nhấc các thành phần gây ra kẹt xe ở chỗ bị kẹt 1 thời gian để xe lưu thông là sẽ có thể giải quyết tình trạng này.
* Ngăn chặn deadlock (bằng cách phủ định 1 trong 4 điều kiện):
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
Loại bỏ điều kiện loại trừ tương hỗ (loại trừ lẫn nhau):
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
+ Các process gởi yêu cầu cho printer daemo

Loại bỏ điều kiện giữ và chờ tài nguyên:


Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới. Process khai báo tài nguyên và được cấp phát 1 lần. Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.


Loại bỏ điều kiện không lấy lại tài nguyên (không có tiếm quyền)


Lấy lại tài nguyên từ proces

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, thường dùng wait(mutex)) và Exit Section (Đoạn đăng xuất, thường dùng signal(mutex)).

Vùng tranh chấp: là vùng chứa các biến dùng chung mà các đoạn mã tương tranh tác động.
Ví dụ: Những chiếc 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.

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


Ví dụ : Đoạn mã sau điều khiển hành vi của Xei trong bài toán "Xe qua cầu yếu":

Code:

Semaphore mutex=1; // Giá trị ban đầu của đèn mutex bằng 1 (màu Xanh)
while(1)
{
Đi đến cầu;
wait(mutex); // Chờ đến khi đèn Xanh và chuyển về Đỏ luôn
Lên cầu;
Qua cầu;
signal(mutex); // Chuyển mutex từ Đỏ sang Xanh
Đi tiếp;
Quay về nhà theo đường khác;
}

- Tại 1 thời điểm chỉ có một process trong vùng tranh chấp.
- Process ở ngoài vùng tranh chấp không được ngăn cản process khác vào vùng tranh chấp.
- Không có process chờ đợi vô hạn định(starvation) để vào vùng tranh chấp.
- Không phụ thuộc vào tốc độ tương đối hay số lượng các process.
- Process chỉ ở trong vùng tranh chấp trong 1 khoảng thời gian nhất định.

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

đồng bộ hóa công việc của P1, P2, P3. sao cho:

a) P1 trước P2 và P3?
b) P1 và P2 trước P3?

ai hiểu rõ vấn đề này nói rõ dùm mình đc ko?

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

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

Semaphore hoạt động tương tự cơ chế ngủ và đánh thức, tuy nhiên nó được hỗ trợ để không xảy ra ngắt trong quá trình đặt giá trị cho biến cờ hiệu ( biến count là một ví dụ điển hình).

Ý tưởng Semaphore được E. W. Dijkstra công bố năm 1995.

Semaphore có các loại: Counting Semaphore (dùng phương pháp đếm), Binary Semaphore (dùng phương pháp cờ hiệu). Nhìn chung cách thức hoạt động là như nhau (sẽ được đề cập trong đoạn sau).

Trong phần này sẽ dùng Counting Semaphore làm ví dụ.

Cơ chế này dùng một cấu trúc dữ liệu đơn giản gồm hai thành phần. Một biến int Count và một hàng đợi chứa các process ở trạng thái blocked.

Mô tả hoạt động Semaphore: Lúc đầu ta khởi tạo giá trị của Semaphore là 1. Giá trị 1 có ý nghĩa tại một thời điểm chỉ cho phép 1 process ở trong miền tranh chấp. Khi có một process yêu cầu vào miền tranh chấp, nó phải kiểm tra biến count, nếu dương thì cho phép vào miền tranh chấp đồng thời giảm count một đơn vị. Ngược lại nếu kiểm tra count <= 0 tức là đã tồn tại một process trong miền tranh chấp, lúc này process hiện đang yêu cầu vào miền tranh chấp sẽ chuyển thành trạng thái Blocked và được đưa vào hàng đợi trong Semaphore, dĩ nhiên khi được đưa vào hàng đợi Semaphore vẫn tiếp tục giảm biến count một đơn vị.

Trong trường hợp có 1 process đã ra khỏi miền tranh chấp, nó sẽ thực hiện đánh thức một process trong hàng đợi của Semaphore để process đó vào được miền tranh chấp, đồng thời nó tăng biến count lên một đơn vị. (Xem hình để thấy được hoạt động của Semaphore).


Nhận xét:

Khi sử dụng Counting Semaphore, ta có thể thông qua biến count để xác định được số process nằm trong hàng đợi chính là giá trị tuyệt đối của biến count.
Đặc biệt là các quá trình SemWait, SemSignal (Trong tài liệu khác là Down, Up hoặc p, v) khi được thực hiện không được ngắt giữa chừng. Một số giải pháp để cấm ngắt là dùng phần cứng hoặc phần mềm (TSL).

Binary Semaphore: Hoạt động tương tự với Couting Semaphore, tuy nhiên biến count lúc này sẽ đóng vai trò là một giá trị bool mang ý nghĩa có hay không một process đang ở trong miền tranh chấp.

Giải quyết bài toán Producer, Consumer với Semaphore

Giải trình: Sử dụng 3 Semaphore.

Semaphore mutex để đảm bảo chỉ có 1 process vào ở trong miền tranh chấp
Semaphore full để xác định khi bộ nhớ đệm đã đầy để block producer.
Semaphore empty để xác định khi bộ nhớ đệm đang trống để block consumer.

ESGER DIJKSTRA

Edsger Wybe Dijkstra (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.

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.

Bài toán bữa tối của các triết gia (Dining Philosophers)

Vấn đề Bữa ăn tối của các triết gia : 5 nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học cần dùng 2 cái nĩa để có thể ăn spaghetti . Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Mỗi nhà triết học sẽ suy ngẫm các triết lý của mình đến khi cảm thấy đói thì dự định lần lượt cầm 1 cái nĩa bên trái và 1 cái nĩa bên phải để ăn. Nếu cả 5 nhà triết học đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti . Đây chính là tình trạng tắc nghẽn.(Deadlock)

1.Điều kiện xuất hiện tắc nghẽn (Deadlock)

   Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:

           Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

           Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.

           Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sủ dụng chúng xong.

           Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên ( Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau : tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.

   Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.
2.Đồ thị cấp phát tài nguyên
Có thể sử dụng một đồ thị để mô hình hóa việc cấp phát tài nguyên. Đồ thị này có 2 loại nút : các tiến trình được biễu diễn bằng hình tròn, và mỗi tài nguyên được hiển thị bằng hình vuông

3.Các phương pháp xử lý tắc nghẽn

   Chủ yếu có ba hương tiếp cận để xử lý tắc nghẽn :

           Sử dụng một nghi thức (protocol) để bảo đảm rằng hệ thống không bao giờ xảy ra tắc nghẽn.

           Cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.

           Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn.
4.Ngăn chặn tắc nghẽn

   Để tắc nghẽn không xảy ra, cần bảo đảm tối thiểu một trong 4 điều kiện cần không xảy ra:

           Tài nguyên không thể chia sẻ : nhìn chung gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một số tài nguyên về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ.

           Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp đặt một trong hai cơ chế truy xuất sau :

               Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý .

               => phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý . Ngoài ra nếu tiến trình chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.

               Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ , sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới.

               => phương pháp này làm phát sinh các khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.

           Không thu hồi tài nguyên: cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khoá và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm sự toàn vẹn dữ liệu .

           Tồn tại một chu kỳ: tránh tạo chu kỳ trong đồ thị bằng cách cấp phát tài nguyên theo một sự phân cấp như sau :

               gọi R = {R1, R2,...,Rm} là tập các loại tài nguyên.

               Các loại tài nguyên được phân cấp từ 1-N.

               Ví dụ : F(đĩa) = 2, F(máy in) = 12

               Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định : khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri).
5.Tránh tắc nghẽn

   Ngăn cản tắc nghẽn là một mối bận tâm lớn khi sử dụng tài nguyên. Tránh tắc nghẽn là loại bỏ tất cả các cơ hội có thể dẫn đến tắc nghẽn trong tương lai. Cần phải sử dụng những cơ chế phức tạp để thực hiện ý định này.

   Một số khái niệm cơ sở

           Trạng thái an toàn : trạng thái A là an toàn nếu hệ thống có thể thỏa mãn các nhu cầu tài nguyên (cho đến tối đa) của mỗi tiến trình theo một thứ tự nào đó mà vẫn ngăn chặn được tắc nghẽn.

           Một chuỗi cấp phát an toàn: một thứ tự của các tiến trình là an toàn đối với tình trạng cấp phát hiện hành nếu với mỗi tiến trình Pi nhu cầu tài nguyên của Pi có thể được thỏa mãn với các tài nguyên còn tự do của hệ thống, cộng với các tài nguyên đang bị chiếm giữ bởi các tiến trình Pj khác, với j
           Một trạng thái an toàn không thể là trạng thái tắc nghẽn. Ngược lại một trạng thái không an toàn có thể dẫn đến tình trạng tắc nghẽn.

   Chiến lược cấp phát : chỉ thỏa mãn yêu cầu tài nguyên của tiến trình khi trạng thái kết quả là an toàn!

   Giải thuật xác định trạng thái an toàn

       Cần sử dụng các cấu trúc dữ liệu sau :
Giải thuật xác định trạng thái an toàn

   Cần sử dụng các cấu trúc dữ liệu sau :

       int Available[NumResources];
       /* Available[r]= số lượng các thể hiện còn tự do của tài nguyên r*/
       int Max[NumProcs, NumResources];
       /*Max[p,r]= nhu cầu tối đa của tiến trình p về tài nguyên r*/
       int Allocation[NumProcs, NumResources];
       /* Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p*/
       int Need[NumProcs, NumResources];
       /* Need[p,r] = Max[p,r] - Allocation[p,r]*/

       1.Giả sử có các mảng  

           int Work[NumProcs, NumResources] = Available;
           int Finish[NumProcs] = false;

       2.Tìm  i sao cho

           Finish == false
           Need[i] <= Work[i]
           Nếu không có i như thế, đến bước 4.

       3. Work = Work + Allocation[i];
          Finish[i] = true;
          Đến bước 2

       4.Nếu Finish[i] == true với mọi i, thì hệ thống ở trạng thái an toàn.

Giải thuật yêu cầu tài nguyên

   Giả sử tiến trình Pi yêu cầu k thể hiện của tài nguyên r.

       1.Nếu k <= Need[i], đến bước 2
          Ngược lại, xảy ra tình huống lỗi

       2.Nếu k <= Available[i],đến bước 3
          Ngược lại, Pi phải chờ

       3.Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật tình trạng hệ thống như sau:

               Available[i] = Available[i] - k;
               Allocation[i]= Allocation[i]+ k;
               Need[i] = Need[i] - k;

               Nếu trạng thái kết quả là an toàn, lúc này các tài nguyên trên sẽ được cấp phát thật sự cho Pi

               Ngược lại, Pi phải chờ
[i]6.Phát hiện tắc nghẽn


   Cần sử dụng các cấu trúc dữ liệu sau :

       int Available[NumResources];
       // Available[r]= số lượng các thể hiện còn tự do của tài nguyên r
       int Allocation[NumProcs, NumResources];

       // Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p

       int Request[NumProcs, NumResources];
       // Request[p,r] = số lượng tài nguyên r tiến trình p yêu cầu thêm

  Giải thuật phát hiện tắc nghẽn

     1. int Work[NumResources] = Available;
        int Finish[NumProcs];

        for (i = 0; i < NumProcs; i++)
            Finish = (Allocation[i] == 0);

     2. Tìm  i sao cho
        Finish[i] == false
        Request[i] <= Work
        Nếu không có i như thế, đến bước 4.

     3. Work = Work + Allocation[i];
        Finish[i] = true;
        Đến bước 2

     4. Nếu Finish[i] == true với mọi i,
        thì hệ thống không có tắc nghẽn
        Nếu Finish[i] == false với một số giá trị i,
        thì các tiến trình   mà  Finish[i] == false sẽ ở trong
        tình trạng tắc nghẽn.
[i]7.Hiệu chỉnh tắc nghẽn


   Khi đã phát hiện được tắc nghẽn, có hai lựa chọn chính để hiệu chỉnh tắc nghẽn :

   Đình chỉ hoạt động của các tiến trình liên quan

       Cách tiếp cận này dựa trên việc thu hồi lại các tài nguyên của những tiến trình bị kết thúc. Có thể sử dụng một trong hai phương pháp sau :

           Đình chỉ tất cả các tiến trình trong tình trạng tắc nghẽn

           Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình gây tắc nghẽn : để chọn được tiến trình thích hợp bị đình chỉ, phải dựa vào các yếu tố như độ ưu tiên, thời gian đã xử lý, số lượng tài nguyên đang chiếm giữ , số lượng tài nguyên yêu cầu...

   Thu hồi tài nguyên

       Có thể hiệu chỉnh tắc nghẽn bằng cách thu hồi một số tài nguyên từ các tiến trình và cấp phát các tài nguyên này cho những tiến trình khác cho đến khi loại bỏ được chu trình tắc nghẽn. Cần giải quyết 3 vấn đề sau:

           Chọn lựa một nạn nhân: tiến trình nào sẽ bị thu hồi tài nguyên ? và thu hồi những tài nguyên nào ?

           Trở lại trạng thái trước tắc nghẽn: khi thu hồi tài nguyên của một tiến trình, cần phải phục hồi trạng thái của tiến trình trở lại trạng thái gần nhất trước đó mà không xảy ra tắc nghẽn.

           Tình trạng « đói tài nguyên »: làm sao bảo đảm rằng không có một tiến trình luôn luôn bị thu hồi tài nguyên

Bài 1: Thiết kế lại đèn hiệu ở đầu cầu để cho tối đa được 2 chiếc ôtô cùng 1 lúc trên mặt cầu?
Trả lời: Theo bài học thì hàm wait có giá trị truyền vào là “mutex” và mutex = 1, thì ở đây mình sẽ đổi mutex = 2 (thêm 1 đèn màu xanh da trời chẵn hạn) vậy khi xe 1 lên cầu thì giá trị mutex=1 và xe thứ 2 lên thì mutex=0 khi có chiếc thứ 3 tới nó sẽ chờ vì trong hàm wait có vòng lặp while(mutex< 0); (đèn đỏ), khi 1 xe đã xuống cầu thì nhờ vào hàm signal mà mutex=1, tiếp đó thì xe 3 được lên. Vậy cùng 1 lúc chỉ có 2 chiếc xe trên mặt cầu.

Bài 2: Đồng bộ công việc sao cho P1 trước P2, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:
semaphore synch1 = 0;
semaphore synch2 = 0;
Cấu trúc P1:
S1
signal(synch1); Cấu trúc P2:
wait(synch1)
S2
signal(synch2); Cấu trúc P3:
wait(synch2)
S3

Bài 3: Đồng bộ P1, P2, P3 sao cho P1 trước P2 và P3
Trả lời: Ta dùng đèn hiệu sau:
semaphore synch1 = 0;
semaphore synch2 = 0;
Cấu trúc P1:
S1
signal(synch1);
signal(synch2); Cấu trúc P2:
wait(synch1)
S2 Cấu trúc P3:
wait(synch2)
S3

Bài 4: Đồng bộ P1, P2, P3 sao cho P1, P2 trước P3
Trả lời: Ta dùng đèn hiệu sau:
semaphore synch1 = 0;
semaphore synch2 = 0;
Cấu trúc P1:
S1
signal(synch1); Cấu trúc P2:
S2
signal(synch2); Cấu trúc P3:
wait(synch1);
wait(synch2)
S3

4 nguyên nhân dẫn đến deadlock:
- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi dùng xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.

Trình bày giải pháp ngăn chặn Deadlock
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy
Ví dụ đời thường: Kẹt xe giữa đường hay cầu, chỉ cần 1 cái cần cẩu để nhấc các thành phần gây ra kẹt xe ở chỗ bị kẹt 1 thời gian để xe lưu thông là sẽ có thể giải quyết tình trạng này.

- Đ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ộ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:

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