ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CNTT
        
ĐỒ ÁN NGUYÊN LÝ HDH
Đề tài:
TÌM HIỂU GIẢI PHÁP ĐỒNG BỘ SEMAPHORE
ỨNG DỤNG GIẢI QUYẾT BÀI TOÁN
DINING- PHILOSOPHER
GVHD: Nguyễn Văn Nguyên

ĐÀ NẴNG – 11/2014
LỜI CAM ĐOAN
Tôi xin cam đoan :
1 Những nội dung trong luận văn này là do tôi thực hiện dưới sự
hướng dẫn trực tiếp của thầy Nguyễn Văn Nguyên
2 Mọi tham khảo dùng trong đồ án đều được trích dẫn rõ ràng tên
tác giả, tên công trình, thời gian, địa điểm công bố.
3 Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá,
tôi xin chịu hoàn toàn trách nhiệm.
Sinh viên
MỤC LỤC
CHƯƠNG 1 GIỚI THIỆU 1
1.1. KHÁI NIỆM ĐỒNG BỘ

1
1.2. CÁC KHÁI NIỆM LIÊN QUAN

1
1.2.1. Vấn đề đoạn găng 1
1.2.2. Các điều kiện thỏa mãn đoạn găng 2


Đồ án HDH
Chương 1 GIỚI THIỆU
1.1. Khái niệm đồng bộ
Một tiến trình đông bộ là một tiến trình mà nó có thể tương tác hoặc bị tác động
bởi 1 tiến trình khác đang thực thi trong hệ thống. Đồng tiến trình có lẽ hoặc trực
tiếp chia sẻ 1 không gian địa chỉ ( có nghĩa là, cả mã nguồn và dữ liệu), hoặc được
cho phép để chia sẻ dữ liệu chỉ thông qua các files. Một trường hợp chính tắc đạt
được khi sử dụng các tiến trình đơn giản hoặc các tuyến. Cùng nhập vào chia sẻ dữ
liệu có thể kết quả dẫn đến xung khắc dữ liệu. Trong đồ án này, em muốn đề cập
đến các kỹ thuật khác nhau để đảm bảo sự thực thi của đa tiến trình, đó là chia sẻ
một không gian địa chỉ lôgic có nghĩa là làm cho dữ liệu xử lý không bị gián đoạn.
1.2. Các khái niệm liên quan
1.2.1. Vấn đề đoạn găng
Xem xét một hệ thống bao gồm n tiến trình {P
0
, P
1
, …, P
n-1
}. Mỗi tiến trình có
một đoạn mã lệnh, được gọi là đoạn găng, trong đó tiến trình có lẽ đang thay đổi
biến chung, cập nhật một bảng, viết một tệp, những gì tương tự thế. đặc trưng quan
trọng của hệ thống là, khi một tiến trình đang thực thi trong đoạn găng của nó,
không có một tiến trình nào khác được phép thực thi trong đoạn găng của nó. Vì
vậy, việc thực thi của đoạn găng bởi tiến trình tranh chấp đúng lúc. Vấn đề đoạn
găng thiết kế một giao thức mà tiến trình có thể sử dụng để hợp tác. Mỗi tiến trình
phải chấp nhận yêu cầu để nhập vào đoạn găng của nó. Phần mã lệnh thực hiện yêu
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
1

Return rv;
}
Định nghĩa cấu trúc TestAndSet
Vấn đề doạn găng có thể được giải thích một cách đơn giản trong một môi
trường đơn tiến trình nếu chúng ta có thể ngăn cấm gián đoạn xảy ra trong khi một
biến dùng chung bị thay đổi. Ở dạng này ta có thể chắc chắn rằng thứ tự hiện tại của
cấu trúc sẽ được phép thực thi không cần đến quyền ưu tiên. Không có cấu trúc nào
khác có thể chạy, nên không có thay đổi bất ngờ được làm nên để biến chia sẻ.
Tiếc thay, giải pháp này không khả thi trong môi trường đa tiến trình. Vô hiệu
hoá ngắt trên một đa tiến trình có thể mất nhiều thời gian, như 1 thông báo bị chặn
đến tất cả các tiến trình. Thông báo này làm dừng độ trễ đi vào mỗi đoạn găng, và
hệ thống bị giảm hiệu quả. Còn về vấn đề tương tác trên đồng hồ hệ thống, nếu
đồng hồ được cập nhật bởi ngắt.
Nhiều máy móc vì vậy đưa ra cấu trúc phần cứng đặc biệt cho phếp chúng ta
hoặc kiểm tra và thay đổi nội dung của một từ hoặc trao đổi nội dung của hai từ, tự
động- có nghĩa là, như một dơn vị không ngắt. Chúng ta có thể sử dụng cấu trúc dặc
biệt đó để giải quyết vấn đề đoạn găng trong mối quan hệ kiểu đơn giản. thêm vào
đó thảo luận một cấu trúc dặc biệt cho một máy đặc biệt, chúng ta trừu tượng hoá
khái niệm chính bên cạnh loại cấu trúc.
Cấu trúc TestAndSet có thể được định nghĩa
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
3
Đồ án HDH
Do {While (TestAndSet (lock));
Critical section
Lock = false;
remainder section
} while(1);
Thực hiện loại bỏ tranh chấp với TestAndSet
Void Swap(boolean &a, boolean &b) {

Thuật toán này không thoả mãn yêu cầu bouded-waiting. Chúng ta biểu diễn
một thuật toán mà sử dụng cấu trúc TestAndSet. Thuật toán này thoả mãn tất cả các
yêu cầu của đoạn găng. Cấu trúc dữ liệu thông thường là
boolean waiting[n];
boolean lock;
những cấu trúc dữ liệu trên được khởi tạo là false. để giải quyết yêu cầu loại bỏ
tranh chấp gặp phải, chúng ta chú ý răng tiến trình P
i
có thẻ nhập vào đoạn găng chỉ
nếu hoặc waiting[i]== false hoặc key == false. Giá trị của key có thể trở thành false
chỉ nếu TestAndSet được thực thi. Tiến trình đầu tiên thực thi TestAndSet sẽ tìm
key == false; tất cả các tiến trình khác phải đợi. Biến waiting[i] là false chỉ nếu các
tiến trình khác rời khỏi đoạn găng của nó; chỉ đuy nhất waiting[i] thiêt lập là false,
đang duy trì yêu cầu tranh chấp.
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
5
Đồ án HDH
Để giải thích yêu cầu tiến trình đã gặp, chúng ta chú ý rằng đối số biểu diễn cho
tranh chấp còn ứng dụng tại đây, từ một tiến trình thoát ra khỏi đoạn găng hoặc thiết
lập lock là false, hoặc thiết lập waiting[j] là false. Cả hai cho phép tiến trình nhập
vào đoạn găng để xử lý.
Để giải thích yêu cầu bouded-waiting gặp phải, chúng ta chú ý rằng khi một tiến
trình rời khỏi đoạn găng của nó, nó quét trên mảng đang đợi trong chu kỳ lệnh
(i+1,i+2,…,n-1,0,…,i-1). Nó được thiết kế tiến trình đầu tiên trong tập lệnh này
nhập vào đoạn (waiting[j] == true) như tăng lên môt để nhập vào đoạn găng. Bất kỳ
một tiến trình đang đợi nào nhập vào đoạn găng của nó sẽ cho kết quả trong vòng n-
1 trở lại. Không may thiết kế phần cứng, thi hành tự động cấu trúc TestAndSet trên
đa tiến trình là tác vụ không quan trọng. Như bổ sung thi hành được xảy ra trong
những cuốn sách trên cấu trúc máy tính.
Do {

Critical_section();
Lock = 0;
Non critical_section();
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
7
Đồ án HDH
}
Sử dụng biến khoá
Giả sử P
0
đi vào đoạn găng của nó, sau khi hoàn thành nó ra khỏi đoạn găng và
thiết lập lock = 1, lúc này tiến trình P
1
tiếp tục đi vào đoạn găng, nhưng chưa kịp xử
lí xong thì có tiến trình P
2
cũng cần nhập vào đoạn găng để xử lý, và tiến trình P
2
có
mức độ ưu tiên cao hơn P
1
vậy lúc đó tiến trình P
1
phải dừng lại để P
2
chạy thực
hiện, nhưng P
1
lại đang ở trog đoạn găng chăn không cho P
2

Khi một Tiến Trình (TT) muốn đi vào đoạn găng thì nó được kiểm tra để được
phép vào hay không. Nếu không được thì TT đó phải chờ trong vòng lặp chờ cho
đến khi vòng lặp thoát.
Điều này không những làm lãng phí thời gian CPU mà nó còn đưa lại những
hiệu quả không mong đợi. Giả sử một máy tính cần xử lí hai TT
- TT L có độ ưu tiên thấp.
- TT H có độ ưu tiên cao hơn.
Nguyên tắc của bộ lập lịch là TT H sẽ được thực thi bất cứ lúc nào nó trong
danh sách sẵn sàng. Tại thời điểm nào đó, lúc đó TT L đang ở trong đoạn găng thì
TT H chuyển sang trạng thái sẵn sàng để thực thi (ví dụ : hoàn thành một thao tác
nhập xuất) nhưng TT H lại đang trong vòng lặp chờ, Khi đó TT L không bao giờ
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
9
Đồ án HDH
lập lịch trong lúc TT H đang thực thi. TT L sẽ không có cơ hội để đi vào đoạn
găng. Vì vậy TT H lặp vô hạn, tình huống này đôi khi gây ra vấn đề đảo ngược độ
ưu tiên.
Chúng ta hãy xem một vài cách trao đổi thông tin cổ điển, cách này sẽ chặn thay
vì phải lãng phí thời gian CPU khi TT không được phép vào đoạn găng. Cách đơn
giản nhất là dùng cặp trạng thái "sleep" và "wakeup". Sleep là là lời gọi hệ thống
xảy ra khi cần chặn một TT, nghĩa là TT đó sẽ bị chặn đến khi TT khác đánh thức
nó dậy. Lời gọi wakeup nhận một tham số, xảy ra khi TT cần được đánh thức. Việc
lựa chọn một trong hai trạng thái sleep và wakeup cần có một tham số, đó là một địa
chỉ bộ nhớ được sử dụng để chuyển từ trạng thái thức thành trạng thái ngủ.
Vấn đề người sản xuất và người tiêu thụDương Văn Sơn
- Ta có thể xem vấn đề người sản xuất - người tiêu thụ như là vấn đề bộ đệm
có kích thước giới hạn. Hai TT cùng chia sẽ một bộ đệm có kích thước cố định.
Người sản xuất đưa thông tin vào bộ đệm còn người tiêu thụ lấy thông tin ra khỏi
bộ đệm( tổng quát có thể có m người sản xuất và n người tiêu thụ, đơn giản chúng
ta chỉ xét trường hợp có 1 người sản xuất và một ngươi tiêu thụ)

while (TRUE){
if (count==0) sleep();
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
11
Đồ án HDH
remove_Item();
count = count -1;
if (count ==N-1) wakeup(producer);
consume_Item();
}
}
Giải pháp Sleep and Wakeup cho bài toán producer-consumer
Bây giờ chúng ta sẽ kiểm tra lại các mâu thuẫn điều kiện, nó có thể dẫn đến sự
cố, vì việc truy cập đến biến count không thể kiểm soát được. Tình huống sau dẫn
đến lỗi., bộ đệm bây giờ là rỗng và người tiêu thụ vừa kiểm tra biến count thì thấy
count=0, tại thời điểm này bộ lập lịch quyết định tạm dừng thực thi người tiêu thụ
và chuyển sang thực thi người sản xuất. người sản xuất đưa một Item vào bộ đệm
rồi tăng count lên 1, chú ý rằng count bây giờ là 1. Vì trước đó count là 0 và do đó
người tiêu thụ phải được ngủ. Lúc này người sản xuất gọi wakeup để dánh thức
người tiêu thụ dậy.
Thật không may, người tiêu thụ chưa thật sự ngủ, do đó tín hiệu wakeup gởi đi
bị đánh mất. Khi người tiêu thụ tiếp tục thực thi, nó kiểm tra giá trị của biến count
và nhận thấy count =0 do đó nó rơi vào trạng thái ngủ, sớm hay muộn thì người tiêu
thụ cũng đưa các Item vào bộ đệm và làm cho nó đầy, lúc này người tiêu thụ sẽ đi
vào trạng thái ngủ. Kết quả là cả hai đều ngủ vĩnh viễn.
Thực chất ,vấn đề ở đây là tín hiệu wakeup gởi đi bị đánh mất, nếu nó không
bị đánh mất thị mọi thứ sẽ hoạt động bình thường, một cách giải quyết là ta thêm
một bit chờ việc gọi wakeup được gởi đến một TT mà TT đó vẫn đang thức, thì bit
này sẽ được bật lên. Sau đó, khi TT đi vào trạng thái sleep, nếu bít chờ đánh thức
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn

một quá trình phải chờ trên một semaphore,nó được thêm vào danh sách các quá
trình L.Một thao tác signal xóa một quá trình ra khỏi danh sách các quá trình đang
chờ và đang đánh thức quá trình đó.
Thao tác semaphore wait bây giờ được định nghĩa như sau:
void wait(semaphore S){
S.value ;
If (S.value < 0){
Thêm quá trình này tới danh sách các quá trình S.L;
block();
}
}
Thao tác semaphore signal được định nghĩa như sau:
void signal(semaphore S){
S.value++;
if(S.value <= 0){
xoá một quá trình ra khỏi hàng đợi S.L;
wakeup(P);
}
}
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
14
Đồ án HDH
Thao tác block() tạm dừng quá trình gọi thao tác đó.Thao tác wakeup tiếp tục
thực thi qua trình bị nghẽn P.Hai thao tác này được cung cấp bởi hệ điều hành như
những lời gọi hệ thống cơ bản.
1.3.6. Giải pháp monitor:
Liên lạc giữa các TT sử dụng semaphore trông có vẻ dễ dàng, nhưng chưa hẳn
đã vậy. Như đoạn chương trình trên, nếu thao tác DOWN thực hiện trước khi đưa
vào hoặc lấy một Item ra khỏi bộ đệm. Giả sử ta đảo ngược trật tự của hai thao tác
DOWN trong đoạn mã của producer, thì mutex được tăng lên 1 trước khi empty

là chỉ có một TT có thể hoạt động trong một monitor tại bất kì thời điểm nào. Các
monitor là cấu trúc của ngôn ngữ lập trình, do đó trình biên dịch biết được chúng là
đoạn chương trình đặc biệt và gọi các thủ tục này khác với các thủ tục bình thường
khác. Diển hình, khi một TT gọi một thủ tục monitor, đầu tiên một vài chỉ lệnh của
thủ tục sẽ kểm tra xem các TT khác có đang hoạt động trong phạm vi monitor, nếu
có lời gọi TT sẽ bị trì hoãn cho đến khi TT khác rời khỏi monitor. Nếu không có TT
nào sử dụng monitor thì lời gọi TT có thể được thực hiện.
Trình biên dịch có nhiệm vụ biên dịch, cài đặt loại trừ lẫn nhau trên lối vào
monitor, nhưng cách đơn giản là sử dụng một semaphore nhị phân. Vì trình biên
dịch ( không phải là nhà lập trình) sắp xếp việc loại trừ lẫn nhau, do đó nó ít bị lỗi
hơn. Trong bất cứ tình huống nào, người lập trình không cần biết cách mà trình biên
dịch sắp xếp các nguyên tắc loại trừ lẫn nhau. Trình biên dịch tự tất cả các đoạn
găng vào thủ tục monitor, và sẽ không có hai TT nào thực hiện trong đoạn găng
cùng một lúc.
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
16
Đồ án HDH
Mặc dù monitor cung cấp cách cài đặt loại trừ lẫn nhau dễ dàng như ta thấy ở
trên, nhưng điều đó chưa đủ. Chúng ta cần một TT bị chặn khi không thể xử lí.
Trong vấn đề giữa người sản xuất và người tiêu thụ, dễ dàng để kiểm tra bộ đệm là
đầy hay rỗng trong các thủ tục monitor. Nhưng làm thế nào để người sản xuất bị
chặn lại khi nó nhận ra bộ đệm đã đầy ?.
Giải pháp nằm trong các biến điều kiện, cùng vời hai phép toán trong chúng là
wait và signal. Khi một thủ tục monitor nhận ra rằng nó không thể tiếp tục (ví dụ :
producer nhận thấy bộ đệm đã đầy) nó đợi trên một vài biến điều kiện. Động tác
này sẽ đưa TT vào trạng thái bị chặn, nó cũng cho một TT trước đây bị chặn trở nên
sẵn sàng để đi vào monitor.
Các TT khác như người tiêu thụ có thể đánh thức người sản xuất đang ngủ bằng
cách Signal các biến điều kiện của người sản xuất. Để tránh trường hợp hoạt động
cùng một lúc trong monitor, chúng ta cần một nguyên tắc điều gì sẽ xảy ra sau phép

công nhận chúng và sắp xếp việc loại trừ lẫn nhau bằng một cách nào đó.
Vấn đề khác vời các monitor và cũng giống như các semaphore là chúng thiết kế
để giải quyết vấn đề loại trừ lẫn nhau trên một hoặc nhiều CPU mà các CPU này có
thể truy cập đến bộ nhớ chung bằng cách đặt các semaphore trong bộ nhớ chia sẽ và
bảo vệ chúng với các chỉ lệnh TSL, chúng ta có thể tránh xung đột. Khi chúngta
muốn phân phối hệ thống có nhiều CPU, mỗi CPU có một bộ nhớ riêng, hoặc kết
nối của một mạng cục bộ, thì không thể kết hợp được các tình năng riêng tư của
chúng được.
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
18
Đồ án HDH
Chương 2 BÀI TOÁN
2.1. Bài toán dining-philosopher theo giải pháp semaphore
2.1.1. Yêu cầu bài toán:
Có 5 triết gia vừa suy nghĩ vừa ăn tối.Các triết gia ngồi trên một bàn tròn xung
quanh có 5 chiếc ghế,mỗi chiếc ghế được ngồi bởi một triết gia.Chính giữa bàn là
một bát cơm và 5 chiếc đũa.
Khi một triết gia suy nghĩ,ông ta không giao tiếp với triết gia khác.Thỉnh thoảng
khi một triết gia cảm thấy đói,ông ta chọn 2 chiếc đũa gần nhất(hai chiếc đũa nằm
giữa ông ta với 2 láng giềng trái và phải).Một triết gia có thể lấy một chiếc đũa tại
một thời điểm.Chú ý,ông ta không thể lấy chiếc đũa mà nó đang được dùng bởi
người láng giềng.Khi một triết gia đói và có hai chiếc đũa cùng một lúc,ông ta ăn
mà không đặt đũa xuống.Khi triết gia ăn xong,ông ta đặt đũa xuống và bắt đầu suy
nghĩ tiếp
.
Hình 2-1: Sơ đồ bàn ăn của các triết gia
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
19
Đồ án HDH
2.1.2. Giải pháp

Khởi tạo biến blocktime
Khởi tạo blocking semaphore cho các hiền triết
Khởi tạo semaphore mutex cho các đũa
Tạo n (=PhiloNum) tuyến
Cài đặt bộ xử lý tín hiệu ALRM
2.2. Kết quả
Hình 2-2:Kết quả chạy chương trình
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
21
Đồ án HDH
PHỤ LỤC
Chương trình nguồn:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#include <signal.h>
#include <time.h>
#define PhiloNum 5 //so luong cac hien triet tren ban an
#define Timeofprogram 10//thoi gian thuc hien chuong trinh
char PhState[PhiloNum]; // trang thai cua 1 hien triet
//- : suy nghi,a: dang an, d: doi
int ChState[PhiloNum]; // trang thai cua 1 cay dua
// 0 : tu do, 1: dang bi chiem dung
sem_t semaphore[PhiloNum]; //danh sach cac semaphore cua cac cay dua
sem_t philosem[PhiloNum];//danh sach cac semaphore cua cac hien triet
int t=0;//bien dem thoi gian (giay)
GVHD: Nguyễn Văn Nguyên SVTH: Mai Phước Tuấn
22