1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Mụctiêucủamônhọc
z Cung cấp những khái niệm cơ bản về hệ điều
hành máy tính: phân loại, nguyên lý, cách làm
việc, phân tích thiết kế và chi tiết về một số hệ
điều hành cụ thể
z Yêu cầu sinh viên: Nắm vững các nguyên lý
cơ bản, làm tốt các bài tập để lấy đólàm cơ
sở - nguyên lý cho các vấn đề khác trong thiết
kế và cài đặt các hệ thống thông tin
z Chú ý liên hệ nội dung môn học với các tình
huống thực tế về khía cạnh quản lý, tổ chức
3
Nội dung
z Gồmcó6 phần chính:
z Tổng quan (3 tiết)
z Quảnlýtiến trình (12 tiết)
z Quảnlýlưutrữ (12 tiết)
z Hệ vào/ra (9 tiết)
z Bảovệ và an ninh (6 tiết)
z HệđiềuhànhLinux (optional) + Ôn tập(3 tiết)
4
Tài liệuthamkhảo
z Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Operating
System Concepts, 7th edition, John Wiley & Sons, Inc., 2005.

z Được sử dụng tài liệu
z Thi cuối kỳ:
z Thi viết 60-90 phút
z Được sử dụng tài liệu
8
Giớithiệu
9
Máy tính - tài nguyên máy tính
z Tài nguyên:
z CPU
z Bộ nhớ trong
z Đĩa cứng
z Thiết bị ngoại vi (máy in,
màn hình, bàn phím, card
giao tiếp mạng, USB )
10
Hệđiềuhànhlàgì?
z Hệđiều hành là mộtchương trình “trung gian”
(nhân – kernel) giữa NSD và máy tính :
z Quảnlýphầncứng máy tính (các tài nguyên)
z Cung cấp cho NSD môi trường làm việc tiệnlợi và
hiệuquả
Hệ
điều
hành
11
Các
chương
trình
hệ thống

z Thờigianthực (real-time)
z Nhúng (embedded)
z Cầm tay (portable)
z Đaphương tiện (multimedia)
z Chuyên dụng (special-purpose)
14
Các hệ xử lý theo lô đơngiản
z Thuậtngữ: Batch processing
z Các chương trình được đưa vào hàng chờ
z Máy tính thựchiệntuầntự các chương trình
củangườisử dụng
z Chương trình không có giao tiếpvớingười
sử dụng
15
Đachương trình
z Thuậtngữ: Multiprogramming
z Các chương trình đượcxếphàng
z Mộtchương trình đượcthựchiệnvàchiếm
giữ CPU cho đến khi (1) có yêu cầu vào/ra,
hoặc(2) kếtthúc
z Khi (1) hoặc(2) xảyra, chương trình khác sẽ
đượcthựchiện
z Tậndụng CPU tốthơnxử lý theo lô đơngiản
16
Phân chia thờigian/đanhiệm
Máy tính
Trạmlàmviệc
Trạmlàmviệc
Ngườisử dụng
Thờigian

z Quảnlýbộ nhớ trong
z Quảnlýtệp
z Quản lý vào/ra
z Quảnlýlưutrữ trên bộ nhớ ngoài
z Liên kếtmạng
z Bảovệ và an ninh
z Thông dịch lệnh
21
Các dịch vụ củahệđiềuhành
z Giao diệnvớingườisử dụng
z Thựchiệncácchương trình
z Thựchiện các thao tác vào/ra
z Quảnlýhệ thống tệp
z Truyền thông
z Phát hiệnlỗi
z Cấp phát tài nguyên
z “Kế toán”
z Đưaracáccơ chế bảovệ và an ninh
22
Các hàm hệ thống
z Các hàm hệ thống (system calls) cung cấp
giao diệnlậptrìnhtớicácdịch vụ do hệđiều
hành cung cấp
z Ví dụ trong hệđiềuhànhUnix:
z Tạomộttiếntrìnhmới: fork();
z Thoát khỏitiếntrìnhđang thựchiện: exit(1);
z fork và exit là các hàm hệ thống (Hàm HT)
23
Hàm HT điềukhiểntiếntrình
z Kếtthúctiến trình bình thường/bấtthường

z Truyềnnhận các thông điệp
z Lấy thông tin trạng thái truyền thông
z Attach/detach các thiếtbịởxa
28
Các chương trình hệ thống
z Các chương trình hệ thống cung cấpmôitrường
thuậntiệnchoviệcthựchiện và phát triển
chương trình. Chúng được phân loạinhư sau:
z Thao tác vớitệp
z Thông tin về trạng thái củahệ thống
z Sửa đổitệp
z Hỗ trợ ngôn ngữ lậptrình
z Nạpvàthựchiệnchương trình
z Truyền thông
z Cách nhìn HĐH củaNSD đượcxácđịnh qua các
chương trình hệ thống, không thựcsự qua các hàm
hệ thống (system calls).
29
Cấutrúc HĐH: Đơngiản
z Thuậtngữ: Simple approach
z Ví dụ MS-DOS. (tương tự: UNIX thờigian
đầu)
Chương trình ứng dụng
Chương trình resident
Điềukhiểnthiếtbị
Điềukhiểnthiếtbị của
ROM-BIOS
30
Cấutrúc HĐH: Phân tầng
z Thuậtngữ: Layered apparoach

z Các hàm hệ thống
z Mộtsố cấutrúcphổ biếncủa HĐH
z Máy ảo
36
Tìm hiểuthêm
z Không bắtbuộc
z Bổ sung mộthàmhệ thống mới vào nhân
Linux và sử dụng hàm đó:
z Đọchướng dẫn trong giáo trình từ trang 74-78
z Thử nghiệm trên RedHat Fedora hoặc
Ubuntu/Debian
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Khái niệmtiếntrình
3
Tiếntrìnhlàgì?
z Thuật ngữ: Process
(tiến trình/quá trình)
z Là một chương trình
đang được thực hiện
z Đượcxemlàđơnvị
làm việc trong các HĐH
z Có hai loạitiến trình:
z Tiếntrìnhcủa HĐH

Control Block (PCB)
z Các thông tin:
z Trạng thái tiếntrình
z Con đếm
z Các thanh ghi
z Thông tin về lậplịch
z Thông tin về bộ nhớ
z Thông tin accounting
z Thông tin vào/ra
Số hiệutiến trình (Process
number)
Con đếm (program counter)
Các thanh ghi (registers)
Giớihạnbộ nhớ
Danh sách các tệp đang mở
…
Con trỏ Trạng thái tiếntrình
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
2
7
Lậplịch tiếntrình
8
Tạisaophảilậplịch?
z Số lượng NSD, số lượng tiến trình luôn lớn
hơnsố lượng CPU củamáytínhrất nhiều
z Tạimộtthời điểm, chỉ có duy nhấtmộttiến
trình đượcthựchiệntrênmộtCPU
z Vấn đề:
z Số lượng yêu cầusử dụng nhiềuhơnsố lượng tài
nguyên đangcó(CPU)

z Bộ lậplịch dài hạn (long-term scheduler)
z Thường dùng trong các hệ xử lý theo lô
z Đưatiếntrìnhtừ spool vào bộ nhớ trong
z Bộ lậplịch ngắnhạn (short-term scheduler)
z Còn gọilàbộ lậplịch CPU
z Lựachọntiếntrìnhtiếptheođượcsử dụng CPU
z Bộ lậplịch trung hạn (medium-term scheduler)
z Hay còn gọi là swapping (tráo đổi)
z Di chuyểntiếntrìnhđang trong trạng thái chờ giữa
bộ nhớ trong và bộ nhớ ngoài
12
Minh họabộ lậplịch trung hạn
CPU
Hàng chờ vào/ra
Hàng chờ sẵn
sàng thựchiện
Các tiếntrình
đang thựchiện
dở bị swap out
Vào/ra
swap out
swap in
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
3
13
Hàng chờ lậplịch tiếntrình
Hàng chờ sẵn
sàng thựchiện
Hàng chờ vào/ra Yêu cầuvào/ra
Hếtthờigian

mấtkhoảng 1-1000 micro giây
16
Các thao tác với
tiếntrình
17
Tạotiếntrình
z HĐH cung cấp hàm create-process để tạo
mộttiếntrìnhmới
z Tiếntrìnhgọi đếnhàmcreate-process là tiến
trình cha (parent process)
z Tiếntrìnhđượctạorasaukhithựchiệnhàm
create-process là tiến trình con (child process)
z Sau khi tiến trình con đượctạo, tiến trình cha
có thể:
z Chờ tiến trình con kết thúc rồitiếptụcthựchiện
z Thựchiện “song song” vớitiến trình con
18
Cây tiếntrình
z Tiến trình cha có thể có
nhiềutiếntrìnhcon
z Mỗitiến trình con chỉ có
mộttiến trình cha
z Các tiếntrìnhcon có
thể tạoracáctiếntrình
con khác…
P
1
P
11
P

khi có lỗihoặccósự kiện)
z Bị hệ thống hoặctiến trình cha áp dụng hàm
abort hoặc kill do:
z Sử dụng quá quota tài nguyên
z Tiến trình con không còn cầnthiết
z Khi tiếntrìnhcha đãkết thúc (trong mộtsố HĐH)
21
Minh họatiếntrìnhtrongUNIX
#include <stdio.h>
main()
{
int pid=fork(); /* Tạotiếntrìnhmớibằng hàm fork() */
if (pid<0) { perror(“Cannot create process”); return(-1); }
else if (pid==0) { /* Tiến trình con */
execlp();
}
else { /* Tiếntrìnhcha */
wait(NULL); /* Nếu không có lệnh này tiến trình cha thựchiện
“song song” vớitiến trình con */
printf(“Child completed\n”);
return(0);
}
}
22
Hợptácgiữacáctiếntrình
z Các tiếntrìnhcóthể hoạt động độclập hoặc
hợptácvớinhau
z Các tiếntrìnhcầnhợptáckhi:
z Sử dụng chung thông tin
z Thựchiệnmộtsố nhiệmvụ chung

26
Minh họatruyền thông trựctiếp
z Mỗikếtnối đượcthiết
lậpchomộtcặptiến
trình duy nhất
z Mỗitiếntrìnhchỉ cần
biếttên/số hiệucủatiến
trình kia là truyền thông
được
z Tồntại duy nhấtmột
kếtnốigiữamộtcặp
tiếntrình
P
1
P
2
P
3
P
6
P
5
P
4
27
Truyền thông gián tiếp
z Các thông điệp đượcgửivànhận qua các
hộpthư (mailbox) hoặc qua các cổng (port)
z Hai toán tử:
z send(A, msg): Gửi msg đếnhộpthư A

thư
B
29
Vấn đề đồng bộ hóa
z Thuậtngữ: Synchronization
z Liên quan tớiphương thứccàiđặt các toán
tử send và receive:
z Phương thứccóchờ (blocking)
z Phương thức không chờ (non-blocking)
30
Các phương thứcsend/receive
Tiếntrìnhnhậntrả
lạikếtquả là msg
(nếunhận được)
hoặcbáolỗi(nếu
chưanhận được)
Tiếntrìnhtruyền không
phảichờ msg đến đích
để tiếptụcthựchiện
Non-blocking
Tiếntrìnhnhận
tạmdừng thực
hiệnchođếnkhi
msg đượcchuyển
tới
Tiếntrìnhtruyềnthông
điệpchờđếnkhimsg
đượcnhậnho
ặc msg
đượcphânphátđến

16 tiếntrìnhcon. Tiến trình cha chờ cho 16
tiến trình con này kếtthúcrồimớikết thúc
bằng hàm exit. Sử dụng các hàm fork và
wait để thựchiệnyêucầu.
z Hãy tìm mộtsố ví dụ thựctế minh họacho
các khái niệmlậplịch/hàng chờ trong tình
huống có nhiềungườisử dụng và ít tài
nguyên.
35
Bài tập
z Hãy viếtchương trình minh họachocáccơ
chế truyền thông non-blocking, blocking
z Hãy viếtchương trình minh họacáccơ chế
truyền thông điệpsử dụng buffer có độ dài n
trong hai trường hợp: n>0 và n=0
z Chú ý: Để làm hai bài tậptrêncầnsử dụng
hai tiến trình; có thể thựchiệnbàitậpvới
UNIX/Linux hoặc Windows
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Lậplịch CPU
3
Tạisaophảilậplịch CPU?
z Số lượng NSD, số lượng tiến trình luôn lớn

(thuậtngữ: CPU-burst)
z Khi tiếntrìnhthựchiện các thao tác vào ra: Sử
dụng thiếtbị vào/ra (thuậtngữ: I/O burst)
6
Microsoft
Office
Outlook
CPU-burst
Adobe
Photoshop
CPU-burst
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
2
7
Hai loạitiếntrìnhchính
z Căn cứ theo cách sử dụng CPU của tiến
trình, có hai loại tiến trình:
z Tiếntrìnhloại CPU-bound: Tiếntrìnhcómộthoặc
nhiều phiên sử dụng CPU dài
z Tiếntrìnhloại I/O-bound: Tiến trình có nhiều
phiên sử dụng CPU ngắn(tứclàthờigianvàora
nhiều)
8
Bộ lậplịch ra hoạt động khi…
1. Mộttiến trình chuyểntừ trạng thái running
sang waiting
2. Mộttiến trình chuyểntừ trạng thái running
sang ready
3. Mộttiến trình chuyểntừ trạng thái waiting
sang ready

11
Lậplịch preemptive
z Hiệuquả hơnlậplịch non-preemptive
z Thuậttoánphứctạphơn non-preemptive và
sử dụng nhiều tài nguyên CPU hơn
z Ví dụ: Microsoft Windows XP, Linux, UNIX
sử dụng lậplịch preemptive
12
Bộđiềuphối (dispatcher)
z Nhiệmvụ:
z Chuyểntrạng thái (context switch)
z Chuyểnvề user-mode
z Thựchiệntiến trình theo trạng thái đãlưu
z Cầnhoạt động hiệuquả (tốc độ nhanh)
z Thờigiancần để bộđiềuphốidừng mộttiến
trình và thựchiệntiến trình khác gọilàđộ trễ
(latency) củabộđiềuphối
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
3
13
Các tiêu chí đánh giá lậplịch
z Khả năng tậndụng CPU (CPU utilization):
Thể hiệnqua tảiCPU –làmộtsố từ 0% đến
100%.
z Trong thựctế các hệ thống thường có tảitừ 40%
(tảithấp) đến 90% (tảicao)
z Thông lượng (throughput): Là số lượng các
tiến trình hoàn thành trong một đơnvị thời
gian
14

trình trong hàng chờ ready
z Thờigianchờ trung bình (average waiting time):
t
averagewaiting
=t
waiting
/ n, n là số lượng tiến trình trong
hàng chờ
16
Các tiêu chí đánh giá lậplịch
z Thờigianđáp ứng (response time): Là
khoảng thờigiantừ khi tiếntrìnhnhận được
mộtyêucầuchođếnkhibắt đầu đáp ứng
yêu cầu đó
z t
res
= t
r
– t
s
, trong đó t
r
là thời điểmnhậnyêu
cầu, t
s
là thời điểmbắt đầu đáp ứng yêu cầu
17
Đánh giá các thuậttoánlậplịch
XấuTốtThờigianđáp ứng (response
time)

thựchiệntương ứng là 24ms, 3ms, 6ms
z Giả sử 3 tiếntrìnhxếphàngtheothứ tự P
1
, P
2
,
P
3
. Khi đótacóbiểu đồ Gantt như sau:
z Thờigianchờ củacáctiếntrìnhlà: P
1
chờ
0ms, P
2
chờ 24ms, P
3
chờ 27ms
z Thờigianchờ trung bình: (0+24+27)/3=17ms
P
1
P
2
P
3
0242733
21
Ví dụ FCFS 1b
z Xét ba tiếntrìnhtrongvídụ 1a vớithứ tự xếp
hàng P
3

sau P.
z “Lớn”: Sử dụng nhiềuthờigianCPU vàvàora
z “Nhỏ”: Sử dụng ít thời gian CPU và vào ra
z Thuậttoánlậplịch đượcsử dụng là FCFS.:
z Hiệntượng xảy ra: CPU, thiếtbị vàoracónhiều
thờigianrỗi, thờigianchờ trungbìnhcủacác
tiến trình cao
23
Ví dụ convoy effect
Hàng chờ sẵn
sàng thựchiện
Hàng chờ vào/ra
Yêu cầuvào/ra
Hếtthờigian
sử dụng CPU
Tạomộttiến
trình con
Chờ ngắt
CPU
Vào/ra
Tiến trình con
thựchiện
Ngắtxuấthiện
Q
3
(10) Q
2
(10) Q
1
(10) P (40)

1
Q
2
Q
3
100 110 120 130
130
P
Rỗi
140
Q
1
Q
2
Q
3
150 160 180
180
P
z Giả sử P là tiến trình “lớn” có chu kỳ sử dụng CPU trong 40ms
và vào ra trong 50ms
z Q
1
, Q
2
, Q
3
là 3 tiến trình “nhỏ”cóchukỳ sử dụng CPU trong
10ms và vào ra trong 10ms
z Thứ tự xếp hàng: P, Q

vớilậplịch ngắnhạn
z Đọc ở nhà: Dựđoán t
nextburst
bằng công thức
trung bình mũ (exponential average) trang
160-162 trong giáo trình
z SJF không tối ưu đượcvớilậplịch ngắnhạn
z SJF thường đượcápdụng cho lậplịch dài hạn
27
Lậplịch có độ ưutiên
z Thuậtngữ: Priority scheduling
z Mỗitiếntrìnhđượcgắnmộtthamsố lậplịch gọilàđộ
ưutiênp, với p là mộtsố thực
z Tiếntrìnhcóđộ ưutiêncaonhất đượcsử dụng CPU
z Qui ướctrongmônhọcnày:
z TiếntrìnhP
1
và P
2
có độ ưutiênp
1
, p
2
tương ứng
z p
1
>p
2
có nghĩalàtiếntrìnhP
1

Ví dụ lậplịch có độ ưutiên
z Xét 5 tiến trình như trong
bảng vớithứ tự trong hàng
chờ là P
1
, P
2
, P
3
, P
4
, P
5
z Sử dụng thuậttoánlậplịch
có ưu tiên, ta có thứ tự
thựchiệncủacáctiếntrình
như sau biểu đồ dưới
z Thờigianchờ trung bình là
(1+6+16+18)/5=8.2ms
3
1
4
5
2
10
1
2
1
5
P

(5)
18
19
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
6
31
Round-robin (RR)
z Còn gọilàlậplịch quay vòng
z Đượcthiếtkếđểáp dụng cho các hệ phân
chia thời gian (time-sharing)
z RR hoạt động theo chếđộpreemptive
z Tham số lượng tử thời gian (time quantum)
t
quantum
: Mỗitiếntrìnhđượcsử dụng CPU
trong nhiềunhấtbằng t
quantum
, sau đó đến
lượttiến trình khác
32
Round-robin (RR)
z Hiệuquả của RR phụ thuộc độ lớncủa
t
quantum
z Nếu t
quantum
nhỏ thì hiệuquả của RR giảmvìbộ
điềuphốiphảithựchiệnnhiềuthaotácchuyển
trạng thái, lãng phí thờigianCPU
z Nếu t

z RR lậplịch các tiến trình như sau:
P
2
P
3
P
1
P
3
P
1
P
1
P
1
P
1
P
1
0
4 7 11 15 17 21 25 29 33
z
Thờigianchờ
z P
1
: 0+(11-4)+(17-15)=9ms
z P
2
: 4ms
z P

z Hàng chờ các tiếntrìnhhệ thống
z Hàng chờ các tiếntrìnhcótương tác
z Hàng chờ các tiến trình là editor
z Hàng chờ các tiếntrìnhhoạt động theo lô
z Hàng chờ các tiếntrìnhthựctậpcủasinhviên
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
7
37
Lậplịch vớihàngchờđamức
có phảnhồi
z Thuậtngữ: Multilevel feedback-queue
scheduling
z Thuậttoánlậplịch kiểu này nhằmkhắcphục
nhược điểm không mềmdẻo củalậplịch với
hàng chờđamức
z Ý tưởng chính: Cho phép tiến trình chuyểntừ
hàng chờ này sang hàng chờ khác, trong khi
lậplịch với hàng chờđamức không cho phép
điềunày
38
Lậplịch vớihàngchờđamức
có phảnhồi
z Cách thựchiện:
z Độ dài phiên sử dụng CPU và thờigianđãnằm
tronghàngchờ là tiêu chuẩnchuyểntiếntrình
giữa các hàng chờ
z Tiến trình chiếmnhiềuthờigianCPU sẽ bị
chuyểnxuống hàng chờ có độ ưutiênthấp
z Tiếntrìnhnằm lâu trong hàng chờ sẽđược
chuyển lên hàng chờ có độ ưutiêncaohơn

z Thuậtngữ: Queueing model
z Dựatrênlýthuyếtxácsuất, quá trình ngẫu nhiên. Tài
liệuthamkhảo:
z Leonard Kleinrock, Queueing Systems: Volume I – Theory
(Wiley Interscience, New York, 1975)
z Leonard Kleinrock, Queueing Systems: Volume II –
Computer Applications (Wiley Interscience, New York, 1976)
z Ưu điểm: So sánh đượccácthuật toán lậplịch trong
mộtsố trường hợp
z Hạnchế: Phứctạpvề mặttoánhọc, lớpcácthuật
toán phân tích so sánh đượccònhạnchế
44
Mô phỏng
z Thuậtngữ: Simulation
z Thựchiện các tình huống giảđịnh trên máy
tính để đánh giá hiệuquả củacácthuật toán
lậplịch, kiểm nghiệmcáckếtquả lý thuyết
z Mô phỏng thường tốnthờigianCPU và
không gian lưutrữ
z Đượcsử dụng nhiều trong công nghiệp
z Ví dụ các hệ mô phỏng mạng (có module
hàng chờ): OPNET, NS-2, Qualnet
45
Cài đặtthử trong thựctế
z Mô phỏng có thể xem như “qui nạp không
hoàn toàn”
z Có thể xây dựng hệ thống thử trong thựctế
z Ưu điểm: Đánh giá đượchiệuquả thựcsự
khi sử dụng
z Nhược điểm:

effect sao cho thờigianrỗicủathiếtbị vào ra
ít hơnthờigianrỗicủaCPU. Giả sử có 4 tiến
trình, trong đó P là tiếntrình“lớn”, Q
1
, Q
2
, Q
3
là các tiến trình “nhỏ” đượcnằm trong hàng
chờ theo thứ tự: P, Q
1
, Q
2
, Q
3
z Tìm hai ví dụ trong thựctế về hàng chờđa
mức và hàng chờđamứccóphảnhồivàgiải
thích các ví dụ này.
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Đồng bộ hóa tiếntrình
3
Ví dụđồng bộ hóa (1)
TiếntrìnhghiP:

1
;
z counter
register
2
= counter;
register
2
= register
2
-1;
counter = register
2
;
z Các toán tử ++ và có thểđượccàiđặtnhư sau:
P và Q có thể nhận được các giá trị khác nhau của
counter tại cùng 1 thời điểmnếunhưđoạnmãxanh
và đỏ thựchiệnxenkẽ nhau.
5
Ví dụđồng bộ hóa (3)
z Giả sử P và Q thựchiện song song vớinhau
và giá trị của counter là 5:
register
1
= counter; // register
1
=5
register
1
= register

=5
register
1
= register
1
+ 1; // register
1
=6
counter = register
1
; // counter=6
register
2
= counter; // register
2
=6
register
2
= register
2
-1; // register
2
=5
counter = register
2
; // counter=5
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
2
7
Tương tranh và đồng bộ

z Đặc điểm quan trọng mà hệ n tiến trình này
cầncólà: KhimộttiếntrìnhP
i
thựchiện đoạn
mã CS
i
thì không có tiếntrìnhP
j
nào khác
đượcphépthựchiện CS
j
z MỗitiếntrìnhP
i
phải “xin phép” (entry
section) trướckhithựchiện CS
i
và thông báo
(exit section) cho các tiến trình khác sau khi
thựchiện xong CS
i
.
10
Khái niệmvềđoạnmãgăng (3)
z Cấu trúc chung của P
i
để thựchiện đoạnmã
găng CS
i
.
do {

REMAIN
i
; // Remainder section
} while (TRUE);
12
Giải pháp cho đoạnmãgăng
z Giải pháp cho đoạnmãgăng cầnthỏa mãn 3
điềukiện:
z Loạitrừ lẫn nhau (mutual exclusion): Nếu P
i
đang
thựchiện CS
i
thì P
j
không thể thựchiện CS
j
∀j≠i.
z Tiếntriển (progress): Nếu không có tiếntrìnhP
i
nào
thựchiện CS
i
và có m tiếntrìnhP
j1
, P
j2
, , P
jm
muốn

0
và P
1
với hai đoạn
mã găng tương ứng CS
0
và CS
1
z Sử dụng mộtbiến nguyên turn vớigiátrị khởi
tạo0 hoặc1 vàmảng boolean flag[2]
z turn có giá trị i có nghĩalàP
i
đượcphépthực
hiện CS
i
(i=0,1)
z nếu flag[i] là TRUE thì tiếntrìnhP
i
đãsẵn
sàng để thựchiện CS
i
14
Ví dụ: giảiphápcủa Peterson
z Mã lệnh của P
i
:
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j) ;

ông
Edsger Wybe Dijkstra
(1930-2002)
18
Định nghĩa
z Semaphore là mộtbiến nguyên, nếu không tính
đếntoántử khởitạo, chỉ có thể truy cập thông
qua hai toán tử nguyên tố là wait (hoặcP) và
signal (hoặcV).
z P: proberen – kiểmtra(tiếng Hà Lan)
z V: verhogen–tăng lên (tiếng Hà Lan)
z Các tiếntrìnhcóthể sử dụng chung semaphore
z Các toán tử là nguyên tốđểđảmbảo không xảy
ra trường hợpnhư ví dụđồng bộ hóa đãnêu
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
4
19
Toán tử wait và signal
wait(S) // hoặcP(S)
{
while (S<=0);
S ;
}
z Toán tử wait: Chờ khi
semaphore S âm và
giảmS đi1 nếuS>0
signal(S) // hoặcV(S)
{
S++;
}

wait(synch);
O
2
;

z Xét hai tiếntrìnhP
1
và P
2
, P
1
cầnthựchiện
toán tử O
1
, P
2
cầnthựchiện O
2
và O
2
chỉ
đượcthựchiện sau khi O
1
đãhoànthành
z Giải pháp: Sử dụng semaphore synch = 0
22
Cài đặt semaphore cổđiển
z Định nghĩacổđiểncủawait chotathấytoán
tử này có chờ bận (busy waiting), tứclàtiến
trình phảichờ toán tử wait kết thúc nhưng

{
S->value++;
if (S->value<=0) {
Xóa mộttiếntrìnhP
ra khỏis->L;
wakeup(P);
}
}
Cài đặt semaphore theo cấutrúc
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
5
25
Semaphore nhị phân
z Là semaphore chỉ nhậngiátrị 0 hoặc1
z Cài đặt semaphore nhị phân đơngiảnhơn
semaphore không nhị phân (thuậtngữ:
counting semaphore)
26
Mộtsố bài toán
đồng bộ hóa cơ bản
27
Bài toán vùng đệmcógiớihạn
z Đãxétở ví dụđầu tiên (the bounded-buffer
problem)
z Ta sử dụng 3 semaphore tên là full, empty và
mutex để giải quyết bài toán này
z Khởitạo:
z full: Số lượng phầntử buffer đãcódữ liệu(0)
z empty: Số lượng phầntử buffer chưacódữ liệu(n)
z mutex: 1 (Chưacótiến trình nào thựchiện đoạn

z Bài toán 1: reader không phảichờ,trừ khi writer đã đượcphép
ghi vào CSDL (hay các reader không loạitrừ lẫn nhau khi đọc)
z Bài toán 2: Khi writer đãsẵn sàng ghi, nó sẽ được ghi trong
thời gian sớm nhất (nói cách khác khi writer đã sẵn sàng,
không cho phép các reader đọcdữ liệu)
30
Bài toán tiếntrìnhđọc-ghi số 1
z Sử dụng các semaphore vớigiátrị khởitạo:
wrt (1), mutex (1)
z Sử dụng biến rcount (khởitạo0) để đếmsố
lượng reader đang đọcdữ liệu
z wrt: Đảmbảoloạitrừ lẫn nhau khi writer ghi
z mutex: Đảmbảoloạitrữ lẫnnhaukhicập
nhậtbiến rcount
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com