1

TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN / ĐỒ ÁN CUỐI KÌ MÔN
NHẬP MÔN HỆ ĐIỀU HÀNH

SEMAPHORE

Người hướng dẫn: TS MAI NGỌC THẮNG
Người thực hiện: THÁI TRUNG TÍN - 51503315
NGUYỄN THỊ DIỆP- 51503312
Lớp : 15050301-15050302
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2016


2

TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN / ĐỒ ÁN CUỐI KÌ MÔN
NHẬP MÔN HỆ ĐIỀU HÀNH

SEMAPHORE

Người hướng dẫn: TS MAI NGỌC THẮNG
Người thực hiện: THÁI TRUNG TÍN - 51503315
NGUYỄN THỊ DIỆP - 51503312
Lớp : 15050301-15050302
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2016


3

LỜI CẢM ƠN
Trong suốt quá trình nghiên cứu về đề tài Ảo hóa
- CLoud, em đã gặp rất nhiều khó khăn từ cách tiếp cận và
trình bày ý tưởng nhưng nhờ có TS. Mai Ngọc Thắng - Khoa
Công nghệ thông tin - Trường đại học Tôn Đức Thắng - đã tận
tình hướng dẫn đã giúp em nhìn nhận vấn đề cụ thể, tiếp cận
đề tài dễ dàng.
Em xin chân thành cảm ơn thầy vì những lời chỉ bảo vô cùng
quý báu của thầy đã giúp em có những thu hoạch quý giá để
hoàn thành quá trình nghiên cứu này.
Bài thu hoạch này được thực hiện trong khoảng thời gian gần
3 tuần. Bước đầu đi vào thực tế, tìm hiểu về lĩnh vực sáng tạo
trong nghiên cứu khoa học, kiến thức của em còn hạn chế và
còn nhiều bỡ ngỡ. Do vậy, không tránh khỏi những thiếu sót
là điều chắc chắn, em rất mong nhận được những ý kiến đóng
góp quý báu của quý Thầy Cô và các bạn học cùng lớp để kiến
thức của em trong lĩnh vực này được hoàn thiện hơn.
Một lần nữa em xin chân thành cảm ơn.
TP.Hồ Chí Minh,ngày 22 tháng 11 năm 2016

Thái Trung Tín
Nguyễn Thị Diệp


4

ĐỒ ÁN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của riêng
tôi và được sự hướng dẫn của TS Mai Ngọc Thắng. Các nội
dung nghiên cứu, kết quả trong đề tài này là trung thực và
chưa công bố dưới bất kỳ hình thức nào trước đây. Những số
liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét,
đánh giá được chính tác giả thu thập từ các nguồn khác nhau
có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong đồ án còn sử dụng một số nhận xét,
đánh giá cũng như số liệu của các tác giả khác, cơ quan tổ chức
khác đều có trích dẫn và chú thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tôi
xin hoàn toàn chịu trách nhiệm về nội dung đồ án của
mình. Trường đại học Tôn Đức Thắng không liên quan đến
những vi phạm tác quyền, bản quyền do tôi gây ra trong quá
trình thực hiện (nếu có).
TP.Hồ Chí Minh,ngày 22 tháng 11 năm 2016
Tác giả
Thái Trung Tín
Nguyễn Thị Diệp


5


PHẦN XÁC NHẬN, ĐÁNH GIÁ CỦA
GIẢNG VIÊN
Phần xác nhận của giáo viên hướng dẫn

TP.Hồ Chí Minh,ngày 22 tháng 11 năm 2016
Thái Trung Tín
Nguyễn Thị Diệp
Phần đánh giá của giáo viên chấm bài

TP.Hồ Chí Minh,ngày 22 tháng 11 năm 2016
Thái Trung Tín
Nguyễn Thị Diệp


6

TÓM TẮT
Semaphore là giải pháp để giải quyết sự xung
đột trong đa tiến trình. Bài tiểu luận này đi tìm hiểu
về những đặc điểm cơ bản của semaphore và cách hoạt
động của semaphore trong một hệ thống đa tiến trình


Mục lục
1 Giải thuật Semaphore
1.1 Semaphore . . . . . . . . . .
1.1.1 Định nghĩa . . . . . .
1.2 Đồng bộ hóa tiến trình . . .
1.2.1 Semaphore . . . . . .

1.2.2 Sử dụng Semaphore .
1.2.3 Hiện thực Semaphore
2 Tài liệu tham khảo

7

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.

.
.
.

.
.
.
.
.
.

11
11
11
12
12
13
14
17


8

MỤC LỤC

DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT


MỤC LỤC


9

DANH MỤC CÁC BẢNG BIỂU, HÌNH
VẼ, ĐỒ THỊ


10

MỤC LỤC


Chương 1

Giải thuật Semaphore
1.1

Semaphore

1.1.1

Định nghĩa

Semaphore là một biến được bảo vệ (hay là một
kiểu dữ liệu trừu tượng), tạo thành một phương pháp
để hạn chế truy nhập tới tài nguyên dùng chung trong
môi trường đa lập trình (multiprogramming). Đây là
một phát minh của Edsger Dijkstra và được sử dụng
lần đâu tiên trong hệ điều hành Linux.
Semaphore là lời giải kinh điển cho bài toán bữa
tối của các triết gia (dining philosophers), mặc dù nó

không ngăn được hết các deadlock
Semaphores còn được sử dụng phổ biến trong các
ngôn ngữ lập trình - những ngôn ngữ mà về bản chất
không hỗ trợ những dạng khác của sự đồng bộ hóa.
Chúng cũng được sử dụng trong các kĩ thuật đồng bộ
ban đầu như trong các hệ điều hành. Xu hướng trong
sự phát triển của ngôn ngữ lập trình, dường như là
hướng vào các dạng cấu trúc đồng bộ hóa, giống như
đồng bộ hóa các kênh. Cộng thêm sự không đầy đủ
trong cách phân chia với deadlock, semaphore không
bảo vệ người lập trình khỏi các lỗi đơn giản trong việc
11


12

CHƯƠNG 1. GIẢI THUẬT SEMAPHORE

Hình 1.1: Bữa ăn triết gia

lấy một semaphore - cái mà luôn luôn được thay đổi
bởi các tiến trình đồng thời, và cũng quên giải phóng
semaphore sau khi lấy ra.
Bên cạnh semaphore đến, ta còn có "semaphore
chặn" (blocking semaphore). Đó là loại semaphore được
khởi tạo tại giá trị 0. Điều này có hiệu quả là bất cứ
luồng nào gọi P(S) sẽ bị chặn cho đến khi một luồng
khác chạy V(S). Loại cấu trúc này rất hữu dụng khi
cần điều khiển thứ tự thực thi giữa các luồng.
Loại semaphore đơn giản nhất là "semaphore nhị

phân", được dùng để điều khiển truy nhập tới một
tài nguyên duy nhất, loại này về bản chất không khác
mutex. Semaphore nhị phân thường được khởi tạo tại
giá trị 1. Khi tài nguyên đang được sử dụng, luồng
truy nhập gọi P(S) để giảm giá trị của nó về 0, và
khôi phục giá trị 1 bằng toán tử V khi tài nguyên sẵn
sàng được được thả ra.


1.2. ĐỒNG BỘ HÓA TIẾN TRÌNH

1.2
1.2.1

13

Đồng bộ hóa tiến trình
Semaphore

Giải pháp giải quyết vấn đề cho vùng tranh chấp
bắng phần cứng thường rất khó tổng quát hóa cho
các trường hợp phức tạp. Sau đây chúng ta sẽ tìm
hiểu một công cụ khá mạnh để giải quyết vấn đề vùng
tranh chấp đó là semaphore.
Semaphore là công cụ đồng bộ cung cấp bởi hệ
điều hành mà không đòi hỏi trạng thái đợi. Semaphore
S là một biến nguyên được truy nhập qua hai thao tác
đơn wait và signal.
Mã giả cho wait và signal được địng nghĩa như
sau:

Wait(s)
While (s<=0);
s - -;
Thao tác wait dùng để kiểm tra xem biến s có
không âm hay không nếu có bị blocked( làm while).Nếu
không thì làm và giảm s đi 1.
Signal(s)
s++;
Thao tác signal dùng để tăng biến s lên 1,nhằm
để cho phép thoát wait.
Việc hiệu chỉnh giá trị của biến semaphore trong
wait và signal phải được thực thi riêng biệt nghĩa là khi
một tiến trinhg nào hiệu chỉnh giá trị của semaphore
s thì không có tiến trình nào đồng thời hiệu chỉnh gái
trị này.


14

CHƯƠNG 1. GIẢI THUẬT SEMAPHORE

Hình 1.2: Wait và Signal

1.2.2

Sử dụng Semaphore

Chúng ta có thể sử dụng semaphore để giải quyết
vấn đề vùng tranh chấp cho n tiến trình. N tiến trình
chia sẻ 1 biến semaphore.Mutex (thay thế cho multual

exclusion) được khởi tạo ban đầu là 1. Tổ chức của 1
tiến trình P(i)có thể được mô tả như sau:
Do
{
Wait(multex);
Critical section;
Signal(multex);
Remainder section;
}while(1);
Ví dụ sau đấy sử dụng semaphore để giải quyết
vấn đề đồng thời cho 2 tiến trình P1 và P2 .P1 và P2
chạy đồng thời, P1 thực hiện thực thi lệnh S1, P2 thực
thi lệnh S2,giả sử S2 được thực thi sau S1.Chúng ta
giải quyết vấn đề trên bằng cách cho P1 và P2 chia sẻ
1 biến semaphore S được khởi tạo ban đầu là 0.


1.2. ĐỒNG BỘ HÓA TIẾN TRÌNH

15

Chèn dòng lệnh sau:
S1;
Signal(s);
Vào trong tiến trình P1 và chèn dòng lệnh:
Wait(s);
S2;
Bởi vì giá trị ban đầu của s là 0 nên P2 chỉ thực
thi khi P1 thực thi xong lệnh signal(s) để tăng giá trị
s lên 1, khi đó lệnh wait trong P2 được thực thi xong

và S2 sẽ được thi hành nhưng sau S1.
1.2.3

Hiện thực Semaphore

Bất lợi chính trong giải quyết vấn đề vùng tranh
chấp là các tiến trình sẽ rơi vào trạng thái đợi (lặp
liên tục) khi tài nguyên mà nó yêu cầu đang được cấp
phát cho tiến trình khác.Việc lặp lại liên tục của tiến
trình sẽ gây nên vấn đề lãng phí hiệu suất CPU.
Để giải quyết vấn đề ,ta có thể hiệu chỉnh định
nghĩa của thao tác wait và signal của semaphore.Khi
1 tiến trình thực thi thao tác wait và nhận thấy giá
trị semaphore nhỏ hơn 0,nó phải đợi.Tuy nhiên,hơn
là đợi tiến trình tự blocked nó. Thao tác blocked đặt
tiến trình vào hang đợi kết nối với semaphore và trạng
thái của tiên strinhf sẽ được chuyển sang trạng thái
đợi.Sau đó điều khiển sẽ được chuyển đến bộ định thời
CPU để lựa chọn 1 tiến trình khác để thực thi.
Tiến trình bị blocked ,đợi semaphore S nên được
khởi động lại khi mà các tiến trình khác thực thi thao
tác signal.Tiến trình được khởi đọng lại bằng thao tác
wakeup,thao tác này thay đổi tiến trình từ trạng thái


16

CHƯƠNG 1. GIẢI THUẬT SEMAPHORE

ssowij sang trạng thái sẵn sang .Sau đó được đặt vào

trong hang đợi sẵn sàng.
Semaphore được định nghĩa như sau:
Typedef struct
{
Int value;//khởi tạo bằng 1
Struct process *L;
}semaphore;
Mỗi semaphore có 1 giá trị integer và một danh
sách liệt kê các tiến trình (hay gọi là hàng đợi).Khi 1
tiến trình phải chờ trên semaphore nó bọ Blocked và
được thêm vào hàng đợi semaphore.
Thao tác wait của semaphore:
Void wait(semaphore S)
{
S.value–;
If(S.value<0){
Add this process to S.L;
Block();//block tiến trình này
}
}
Thao tác signal:
Void signal (semaphore S)
{
S.value++;
If(S.value<=0){
Remove a process P from S.L;
Wakeup(P); //đặt tien trinh P vào ready list
}



1.2. ĐỒNG BỘ HÓA TIẾN TRÌNH

}

17


18

CHƯƠNG 1. GIẢI THUẬT SEMAPHORE


Chương 2

Tài liệu tham khảo
Nguyễn Thanh Hiên, Nguyễn Hồng Vũ, Phạm
Nguyễn Huy Phương , 2014, Hệ Điều Hành , Hà Nội.

19