Bài giảng Hệ điều hành: Chương 2

ệ ề

H đi u hành

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ươ ế ả Ch ng 2: Qu n lý ti n trình

ổ

T ng quan

ề ế ồ i thi u t ng quan v ti n trình và lu ng

ệ ổ ố ế

ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ớ ề ơ ế ồ ế ộ • Gi • Đi u ph i ti n trình và lu ng ồ • C ch thông tin liên l c gi a các ti n trình ữ ạ • Đ ng b hoá ti n trình

ổ

ề ế

1. T ng quan v ti n trình và lu ngồ

ế

ế ấ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Khái ni m ti n trình ệ • Khái ni m ệ lu ngồ • Các tr ng thái c a ti n trình ạ ủ ế • Ch đ x lý c a ti n trình ủ ế ế ộ ử • C u trúc d li u kh i qu n lý ti n trình ả ố ữ ệ • Thao tác trên ti n trình ế • Ti n trế ồ ình và lu ng trên LINUX

ệ

ế

Khái ni m ti n trình

ộ ể ụ ộ • Ch

ỉ

ử • Ti n trình là m t ch

ỏ ệ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ươ ự ng trình là m t th c th th đ ng, ể ứ ự ị ề ch a đ ng các ch th đi u khi n máy tính ộ ể ế ụ . đ ti n hành m t tác v nào đó ươ ộ ế ng trình đang x lý, sở h u ữ – m t con tr l nh, ộ – t p các thanh ghi ậ – các bi n. ế

ế

ệ

Khái ni m ti n trình

• Ti n trình trong b ộ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế nhớ

ủ ế

ạ

Các tr ng thái c a ti n trình

ượ ẽ ạ • Khi m t ti n trình đ ộ ế c ch y, nó s thay

ượ ạ

ế

ệ

c x lý

c t o ra ượ ử ợ

ộ ự ệ

ổ ạ đ i tr ng thái – new: Ti n trình đang đ – running: Các l nh đang đ – waiting: Ti n trình đang đ i m t s ki n nào ế

đó

ợ ể ượ

c gán cho

– ready: Ti n trình đang đ i đ đ ử

ộ

ế m t quá trình x lý

ế

– terminated: Ti n trình k t thúc ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ủ ế

ạ

Các tr ng thái c a ti n trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế

ả

ố

Kh i qu n lý ti n trình PCB

ộ ế ữ thông tin c a m t ti n trình

ế ươ ng trình

ậ ị ả ộ ớ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ủ ư L u gi • Tr ng thái ti n tình ạ • B đ m ch ộ ế • Các thanh ghi CPU • Thông tin l p l ch CPU • Thông tin qu n lý b nh • Thông tin tài kho nả • Thông tin tr ng thái I/O

ấ

ả

ữ ệ C u trúc d li u kh i qu n lý ế ti n trình

ố

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế

Thao tác trên ti n trình

• H đi u hành cung c p các thao tác ch ủ

ấ ộ ế

ạ ậ ế ạ

ừ

ổ ộ ư

ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ệ ề ế y u sau đây trên m t ti n trình : – t o l p ti n trình (create) ế – k t thúc ti n trình (destroy) ế – t m d ng ti n trình (suspend) ế – tái kích ho t ti n trình (resume) ạ ế – thay đ i đ u tiên ti n trình

ạ ậ

ế

T o l p ti n trình

(1)

ộ ế • M t ti n trình có th t o l p nhi u ti n

ể ạ ậ ử ụ ế ộ ờ ọ ệ i g i h

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề trình m i b ng cách s d ng m t l ố th ng t ớ ằ ươ ứ ng ng

ạ ậ

ế

T o l p ti n trình

(2)

ế ớ

ả • đ nh danh cho ti n trình m i phát sinh • đ a ti n trình vào danh sách qu n lý c a h ủ ệ

ộ ư ế ị ư ế th ngố ị

ế ầ • xác đ nh đ u tiên cho ti n trình • t o PCB cho ti n trình ế • c p phát các tài nguyên ban đ u cho ti n

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ấ trình

ạ ậ

ế

T o l p ti n trình

(3)

ồ • Ti n trình cha ti p t c x lý đ ng hành v i ớ ế ụ ử

ti n trình con.

ế ế ế

• Ti n trình cha ch đ n khi m t ti n trình ộ ế ờ ế ế ặ ấ ả t c các ti n trình con

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ử con nào đó, ho c t ế k t thúc x lý.

ạ ậ

ế

T o l p ti n trình

(4)

#include #include #include int main() {

pid_t pid; pid =fork(); if (pid < 0) {

fprintf(stderr, "Fork Failed"); return 1;

} else if (pid == 0) { /* child process */ execlp("/bin/ls","ls",NULL); } else { /* parent process */ /* parent will wait for the child to complete */ wait (NULL) ; printf("Child Complete"); } return 0;

}

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế

K t thúc ti n trình

ệ ố ấ • thu h i các tài nguyên h th ng đã c p phát

ỏ ấ ả t c các danh sách

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ồ ế cho ti n trình ế ủ ả qu n lý c a h th ng ủ ỏ • h y ti n trình kh i t ủ ệ ố ủ ế • h y b PCB c a ti n trình

ạ

T m d ng ti n trình

tái kích

ế ạ ế

ừ ho t ti n trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ự

ươ

S đa ch

ng

(multiprogramming)

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế ộ ử

ủ ế

Ch đ x lý c a ti n trình

ề

• Ch đ không ế ộ ặ đ c quy n • Ch đ đ c ế ộ ặ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

quy n ề

C ch

ơ ế ho t đ ng

ạ ộ 2 ch đế ộ

ỏ ệ ề

ng trình ươ ưở • Chia s tài nguyên h th ng đòi h i h đi u ị ỗ i b l ng trình ệ ố ộ ươ ớ các ch ng t i

ẻ ả ằ ả hành đ m b o r ng m t ch ả không th ể nh h khác.

ể ạ ộ ươ

ng trình

thay

ặ

• Cung c p h tr ấ ữ ệ bi t gi a hai ph – 1. Ch đ ng ế ộ ườ ộ m t cho m t ng

ầ ứ ỗ ợ cho ph n c ng đ phân ứ ươ ng th c ho t đ ng. ạ ch y ch i dùng – ườ ử ụ i s d ng. – 2. Monitor mode (ch đ giám sát ho c ch đ ế ộ ế ộ ặ ệ ặ ươ thay m t cho h

ạ ch y ch

ng trình

ệ ố ề

h th ng) đi u hành.

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

C ch

ạ ộ 2 ch đế ộ ơ ế ho t đ ng (Cont.)

• Bit ch đ thêm vào ế ộ

ầ ứ

i ườ

ể ph n c ng máy tính đ ch raỉ ế ộ ệ ch đ hi n ế ộ hành: ch đ giám sát (0) ho cặ ch đế ộ ng dùng (1).

ặ ỗ

i

• Khi m t ng t ho c l

ắ ộ ầ ứ x y raả , ph n c ng ạ sang ch ế ể chuy n m ch độ giám sát. ặ

ề ch ỉ

• Các l nhệ đ c quy n ệ trong ự c ượ th c hi n đ ế ộ ch đ giám sát.

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

C ch

ạ ộ 2 ch đế ộ ơ ế ho t đ ng (Cont.) ệ

ệ ề ể • Các l nh đ c quy n là các l nh có th gây

ể ừ ế ộ ườ

ch đ ng

ế ộ i dùng sang ch đ

ặ ệ ố huy n t

ể

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ h i cho h th ng – L nh c ệ ạ h t nhân – Các l nh đi u khi n I/O ề ệ – Qu n lý timer ả – Qu n lý ng t ắ ả – . . .

Khái ni m ệ lu ngồ

ồ

ơ ả ầ ự ạ ộ ơ ồ ị ử ử • M t lu ng là m t đ n v x lý c b n trong M i lu ng x lý tu n t đo n

ế ỗ . ồ ph i

ồ

ử ầ ự ạ ủ trong 1 ti n trình. ề đo n code c a nó,

ỏ ệ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ộ ệ ố h th ng. code c a nóủ • M t lu ng ả ở ộ • 1 ti n trình có th có nhi u lu ng. ế ể • M i lu ng x lý tu n t ồ ỗ sở h u ữ – m t con tr l nh ộ – t p các thanh ghi ậ – vùng nh stack riêng ớ

Khái ni m ệ đa lu ngồ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ố ế

ề

2. Đi u ph i ti n trình

ề ớ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề • Khái ni m chung ệ • Các yêu c u v i quá trình đi u ph i ầ ố • T ch c ố ổ ứ đi u ph i

ề ề

ệ

ố Khái ni m v đi u ph i

ế ả ự ượ ọ ố ph i l a ch n ti n trình đ c

. ố ẽ ị ệ

ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ữ ả ọ ở ộ ề ố ể ử • B đi u ph i ộ ề ế ử x lý ti p theo • B phân ph i s ch u trách nhi m chuy n ể ộ ổ đ i ng c nh và trao CPU cho ti n trình ượ c ch n b i b đi u ph i đ x lý. đ

ế

ể

ặ

Đ c đi m ti n trình

ủ ế ướ ướ ậ ủ ế ng xu t / nh p c a ti n trình ng x lý c a ti n trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ủ ế ử ụ ạ ế ấ • Tính h ấ • Tính h ử • Ti n trình t ử ươ ế ng tác hay x lý theo lô • Đ u tiên c a ti n trình ộ ư • Th i gian đã s d ng CPU c a ti n trình ờ ủ ế • Th i gian còn l ể ầ ờ i ti n trình c n đ hoàn t t

ố ộ

ề

ề Nguyên lý đi u ph i đ c quy n

• Cho phép m t ti n trình khi nh n đ ộ ế ề ậ ượ ế ế

ả ộ ẽ ặ ự ấ ử ho c t ệ nguy n gi t x lý

CPU s có quy n đ c chi m CPU đ n khi i phóng hoàn t CPU .

ẽ ả ề đi u ph i CPU s x y ra

khi: ử ố ể ừ ạ

tr ng thái đang x lý

• Ho t đ ng ạ ộ ế ạ ế

ị ế

– Khi ti n trình chuy n t sang tr ng thái b khóa – Khi ti n trình k t thúc

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ộ

ố ề Nguyên lý đi u ph i không đ c quy nề ạ ộ

ộ ế ừ ủ • Cho phép t m d ng ho t đ ng c a m t ti n

ẽ ả ề ạ ử . ẵ trình đang s n sàng x lý đi u ph i CPU s x y ra

khi: ử ố ể ừ ạ

tr ng thái đang x lý

ị

ể ừ ạ

ử

tr ng thái đang x lý

• Ho t đ ng ạ ộ ế ạ ế ạ ế

ể ừ ạ

ờ

– Khi ti n trình chuy n t sang tr ng thái b khóa – Khi ti n trình chuy n t sang tr ng thái ready – Khi ti n trình chuy n t

tr ng thái ch sang

ạ

tr ng thái

ế

– Khi ti n trình k t thúc

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề

ầ

ớ Các yêu c u v i quá trình đi u ph iố

ự

ằ ệ ủ

ợ

ệ ố

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ượ • S công b ng • Tính hi u q a • Th i gian đáp ng h p lý ứ ờ • Th i gian l u l ư ạ ờ • Thông l ố ng t i trong h th ng i đa

ử ụ

Các danh sách s d ng trong quá

ề trình đi u ph i

ố (1)

• danh sách s n sàng (ready list)

ế

ộ ng trú trong b nh chính và

ể

ẵ

ẵ – ch các ti n trình đang th ế ỉ ử ụ

ớ ạ ộ ẵ

ậ ộ

ườ ỉ ở ạ tr ng thái s n sàng ti p nh n CPU đ ho t đ ng – H đi u hành ch s d ng m t danh sách s n sàng cho ệ ề

ệ ố

toàn h th ng

ể

ộ

– ti n trình s đ

c chuy n sang m t danh sách

ờ ch khi

• danh sách ch đ i(waiting list) ờ ợ ẽ ượ ế ự ệ ả x y ra các s ki n ỗ

ộ

– m i m t tài nguyên ( thi ộ ờ ợ

ạ ế

ế ị t b ngo i vi ) có m t danh ờ ồ sách ch đ i riêng bao g m các ti n trình đang ch ượ ấ đ

c c p phát tài nguyên đó

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ử ụ

Các danh sách s d ng trong quá

ề trình đi u ph i

ố (2)

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ể

ề

ữ ổ Chuy n đ i gi a các danh sách ố đi u ph i

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề

ụ (job

ụ

ố Đi u ph i tác v scheduling) • Quy t đ nh l a ch n tác v nào đ ọ ạ

ế ể ự ộ

ế ị ứ ề

ươ ượ ư ự ế ị c đ a ủ ữ ệ ố và n p nh ng ti n trình c a vào h th ng ệ ớ ụ tác v đó vào b nh chính đ th c hi n • Ch c năng đi u ph i tác v quy t đ nh m c ụ ố ủ ệ ố ng c a h th ng

• Đ c kích ho t ạ ậ

ệ ố

ứ ộ đ đa ch ạ khi ượ – h th ng t o l p m t ti n trình – có m t ti n trình k t thúc x lý ụ

ộ ế ố

ạ ộ

ử ấ

ầ

ộ ế ế • Đi u ph i tác v có t n su t ho t đ ng

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề th p ấ

ề

ố ế Đi u ph i ti n trình

ẵ

ấ

ế • Ch n m t ti n trình ở ạ ọ ộ ế tr ng thái s n sàng ủ ớ ộ ượ ạ ( đã đ c n p vào b nh chính, và có đ ạ ộ ể tài nguyên đ ho t đ ng ) và c p phát CPU ự i nệ cho ti n trình đó th c h

ạ ộ ỗ ầ ấ ả • Có t n su t ho t đ ng cao, sau m i l n x y

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ầ ra ng t ắ

ề

Đi u ph i t

ố rung gian

ộ ề ụ ấ ố • K t h p c hai c p đ đi u ph i tác v và

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế ợ ả ế ti n trình

ế ượ

ề

ố

Chi n l

c đi u ph i FIFO

ượ ấ • CPU đ ế c c p phát cho ti n trình đ u tiên

ề

ệ ượ ầ ẵ ầu trong danh sách s n sàng có yêu c • Đi u ph i theo nguyên t c đ c quy n ề ố • Có th x y ra hi n t ờ ể ả ắ ộ ng tích lũy th i gian

ch ờ

ệ ớ ợ • Không phù h p v i các h phân chia th i ờ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

gian

ế ượ

ề

Chi n l

ố c đi u ph i xoay vòng

ừ ố ầ ượ ấ • b đi u ph i l n l

ộ t c p phát cho t ng ờ

ử ụ ộ ế ộ ề ế ti n trình trong danh sách m t kho ng th i ọ gian s d ng CPU g i là ử ụ

ả quantum ế ệ ề ờ

ế ấ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế • khi m t ti n trình s d ng CPU đ n h t ế th i gian quantum dành cho nó, h đi u ế ồ hành thu h i CPU và c p cho ti n trình k ti p trong danh sách

ế ượ

ố ư

ề

Chi n l

c đi u ph i u tiên

ượ ộ ộ ư c gán cho m t đ u tiên

ấ ẽ ượ c • ti n trình có đ u tiên cao nh t s đ

ộ ư ch n đ c p phát CPU đ u tiên

• M i ti n trình đ ỗ ế ươ ứ ng ng t ế ọ ả ể ấ ậ • Gi

ề ắ ộ ộ

• Tình tr ng ‘đói CPU’ (starvation) là m t ộ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ầ ể ố ớ ộ ư i thu t đi u ph i v i đ u tiên có th ề theo nguyên t c đ c quy n hay không đ c quy nề ạ ề ế ấ v n đ chính y u

ế ượ

ệ

ắ

ấ

Chi n l

c công vi c ng n nh t

ượ ự c t do, nó s đ • Khi CPU đ

ế ẽ ượ ấ ờ ầ

ế

ề c c p phát ấ ể cho ti n trình yêu c u ít th i gian nh t đ ấ ế k t thúc ti n trình ng n nh t. • Gi ể ộ ả ắ i thu t này cũng có th đ c quy n hay

ậ ộ không đ c quy n

ả

• Khó khăn th c s c a gi ờ ầ ử ậ i thu t SJF là c th i gian yêu c u x lý

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ủ ế ề ự ự ủ ể ế ượ t đ i c a ti n trình không th bi còn l

ế ượ

ề

Chi n l

ố ớ c đi u ph i v i nhi u (1) ộ ư

ớ

ề ứ ộ ư m c đ u tiên • phân l p các ti n trình tùy theo đ u tiên ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế ượ

ề

Chi n l

ề ứ ộ ư m c đ u tiên

ố ớ c đi u ph i v i nhi u (2)

ế

ộ

ượ ả

ố ề i thu t đi u ph i • gi

• các ti n trình có ộ ư cùng đ u tiên ụ c áp d ng m t đ ố ề ậ i thu t đi u ph i gi ể ề ợ thích h p đ đi u ph i ố ả ữ ườ ậ ả

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ậ gi a các nhóm, ng là gi th i thu t ề ộ không đ c quy n

ế ượ

ề

Chi n l

ổ ố ố c đi u ph i X s

ố • phát hành m t s vé s và phân ph i cho

ộ ố ố ệ ố các ti n trình trong h th ng ế ị ề ố ờ • Khi đ n th i đi m ra quy t đ nh đi u ph i,

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ỡ ữ ế ể ế ọ ẽ ế s ti n hành ch n 1 vé "trúng gi ẽ ượ trình nào s h u vé này s đ ế ả i", ti n ậ c nh n CPU

ạ

ữ

ơ ế

ế

ầ ấ ệ ạ

ữ

3. C ch thông tin liên l c gi a ế các ti n trình • Nhu c u liên l c gi a các ti n trình ạ ữ • Các v n đ n y sinh trong vi c liên l c ề ả ế gi a các ti n trình • Các c ch liên l c ạ ơ ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ầ

ế

ữ

ế

ạ Nhu c u liên l c gi a các ti n trình ự ầ

ể ộ ậ ạ ớ ẫ

ợ

• Các ti n trình là nh ng th c th đ c l p , ữ ư nh ng chúng v n có nhu c u liên l c v i nhau để – Chia s thông tin ẻ – H p tác hoàn thành tác v

ụ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ấ

ề ả ữ

ế ề ẩ

ệ Các v n đ n y sinh trong vi c ạ liên l c gi a các ti n trình ế ườ ng minh hay ti m n (explicit

• Liên k t t

ộ naming/implicit naming) • Liên l c theo ch đ đ ng b hay không ế ộ ồ

ạ ộ ồ đ ng b ạ ệ ố ữ • Liên l c gi a các ti n trình trong h th ng ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ệ ố ậ t p trung và h th ng phân tán

ạ ằ

ệ

Liên l c b ng tín hi u (1)

ề ệ ầ ự • Tín hi u là m t c ch ph n m m t ộ ơ ế

ươ ng t ế ộ ế ắ ứ

ư nh các ng t c ng tác đ ng đ n các ti n trình. ộ ệ ượ ử ụ ể c s d ng đ thông báo

ả

ộ ả ữ ễ ễ • M t tín hi u đ ế • M i ti n trình s ỗ ế ề ộ ự ệ cho ti n trình v m t s ki n nào đó x y ra. ở h u m t b ng bi u di n

ệ

ệ ẽ ươ ứ ộ các tín hi u khác nhau. • V i m i tín hi u s có t ng ng m t trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ỗ ớ ệ . ử x lý tín hi u

ạ ằ

ệ

Liên l c b ng tín hi u (2)

ở ệ ượ ở c g i đi b i :

ộ ế

ệ ề

ở ế ộ ế

ở ế

• Các tín hi u đ – Ph n c ng ầ ứ – H t nhân h đi u hành g i đ n m t ti n trình ạ – M t ti n trình g i đ n m t ti n trình khác ộ ế – Ng ườ

i dùng

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ằ

ệ

Liên l c b ng tín hi u (3)

ộ ế ệ ộ • Khi m t ti n trình nh n m t tín hi u, nó có ậ

ộ

ặ ị

ệ

ử

ậ

ặ

ệ

ể ử ự th x s theo m t trong các cách sau : – B qua tín hi u ệ – X lý tín hi u theo ki u m c đ nh ể – Ti p nh n tín hi u và x lý theo cách đ c bi ệ

t

ỏ ử ế ủ ế c a ti n trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ằ

ệ

Liên l c b ng tín hi u (4)

ệ ấ không • Liên l c b ng tín hi u mang tính ch t

ế • H n n a các ti n trình không th ki m tra

ể ể ệ ớ c s ki n t ng ng v i tín hi u có

ể

ế ố ổ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ằ ộ ồ đ ng b ơ ữ ượ ự ệ ươ ứ đ ậ ự ả th t s x y ra ? • các ti n trình ch có th thông báo cho nhau ỉ ế ề ộ v m t bi n c nào đó, mà không trao đ i ữ ệ d li u

ườ

ố

ạ ằ Liên l c b ng đ

ng ng (1)

ộ ộ ự ế ạ

ậ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

c chuy n đ n làm d li u nh p cho ộ • M t pipe là m t kênh liên l c tr c ti p gi a ữ ữ ệ ế hai ti n trình : d li u xu t c a ti n trình ế ể ượ này đ ướ ạ ế ti n trình kia d ấ ủ ế ữ ệ i d ng m t dòng các byte

ườ

ố

ạ ằ Liên l c b ng đ

ng ng (2)

ọ ế

ẽ

ể • Ti n trình đ c pipe s b khóa n u pipe ẽ ị ữ ả ợ ế tr ng, nó s ph i đ i đ n khi pipe có d ấ li u đ truy xu t.

ế ố ệ ế ầ ế

ẽ ả ợ ế ỗ ố

ộ ơ ế ạ • Liên l c b ng pipe là m t c ch liên l c

• Ti n trình ghi pipe s b khóa n u pipe đ y, ẽ ị ể nó s ph i đ i đ n khi pipe có ch tr ng đ ứ ữ ệ ch a d li u. ạ ằ ề m t chi u (unidirectional)

ế ố

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ế ộ ộ • ch cho phép k t n i hai ti n trình có quan ỉ ệ h chacon, và trên cùng m t máy tính.

ớ ùng nh chia

ạ ằ Liên l c b ng v sẻ(1)

ề • Cho nhi u ti n trình cùng truy xu t đ n

ọ ộ ấ ế ớ vùng nh chia

ế ớ m t vùng nh chung g i là sẻ (shared memory).

ộ ẻ ồ ạ ộ ậ ớ i đ c l p v i

• M t vùng nh chia s t n t ớ .

ấ ế

ế các ti n trình ộ ế ế ớ

ủ ỉ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Khi m t ti n trình mu n truy xu t đ n vùng ố ả ế ắ ớ nh này, ti n trình ph i k t g n vùng nh ị chung đó vào không gian đ a ch riêng c a ế ừ t ng ti n trình

ớ ùng nh chia

ứ ươ

ạ ằ Liên l c b ng v sẻ(2) ng th c này làm phát

• ph

ả ự

sinh các khó khăn trong vi c ệ ẹ ữ ả b o đ m s toàn v n d li u (ệ coherence) ụ ể • không th áp d ng hi u qu ả

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ệ trong các h phân tán ệ

ạ ằ

ổ

ệ ề ẩ

Liên l c b ng trao đ i thông đi pệ • H đi u hành cung c p các hàm IPC chu n ấ

ộ ậ

ộ

ị

ề ệ

ổ ữ ệ ở ạ d ng có

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

(Interprocess communication) – Send(message) : g i m t thông đi p ệ ở – Receive(message) : nh n m t thông đi p ệ • Đ n v truy n thông tin trong c ch trao ơ ế ơ ệ nên các ộ ổ đ i thông đi p là m t thông đi p ể ế ti n trình có th trao đ i d li u ấ c u trúc

ạ ằ

Liên l c b ng socket (1)

ề t b truy n thông hai

ng t

ộ ế ị nh t p tin ộ ầ

• M t socket là m t thi ự ư ậ • m i socket là m t thành ph n trong m t ộ ữ ộ ề ươ chi u t ỗ ố ố

ạ ự

ụ ề

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

m i n i nào đó gi a các máy trên m ng máy ọ tính và các thao tác đ c/ghi chính là s trao ứ ữ ổ ữ ệ đ i d li u gi a các ng d ng trên nhi u máy khác nhau.

ạ ằ

Liên l c b ng socket (2)

ể ự ệ ế ầ • Đ th c hi n liên l c b ng socket, c n ti n ạ ằ

ớ

ộ ị thể liên l c ạ trong ch ế đ ộ không

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

hành các thao tác :: – T o l p hay m m t socket ở ộ ạ ậ – G n k t m t socket v i m t đ a ch ỉ ộ ế ắ – Liên l c : có ạ ố ế ố ế hay có n i k t n i k t

ạ ằ

Liên l c b ng socket (3)

ế ộ • Liên l c trong ch đ không liên k t ế

– hai ti n trình liên l c v i nhau không k t n i ế ố ạ ớ

ỉ ườ

ệ

ị

– m i thông đi p ph i kèm theo đ a ch ng ả

i

ạ ế ự ế tr c ti p ỗ nh n. ậ

ệ ủ ọ

ườ

– ng đ

ườ ở ượ ở ế ộ

ệ

c g i nhi u l n,

ộ

ắ ắ i g i không ch c ch n thông đi p c a h c ậ i nh n, c g i đ n ng – m t thông đi p có th đ ể ượ ở – hai thông đi p đệ ược g i theo m t th t ở ườ

ể ế

ậ

ộ

ề ầ ứ ự i nh n theo m t th t

nào đó ứ ự

có th đ n tay ng khác.

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ ằ

Liên l c b ng socket (4)

ế ộ ố ế theo mô hình • Liên l c trong ch đ n i k t

ờ ọ ệ ố

i g i h th ng listen và accept

ổ

ử ụ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ạ client – server – server s d ng l ử ụ ể ố ế ớ đ n i k t v i client – client và server có th trao đ i thông tin b ng ằ ể cách s d ng các primitive send và receive

ế

ồ

ộ

4. Đ ng b hoá ti n trình

ồ ế ộ ng b hoá ti n trình

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Nhu c u đầ • Gi ả • Gi ả i pháp « busy waiting » i pháp « sleep and wakeup »

ề

ấ

ộ

ầ Yêu c u đ c quy n truy xu t (Mutual exclusion)

ể ử ụ ạ ẻ tài nguyên không th chia s i

ử ụ

ế

ề ả ộ • H th ng có ệ ố ộ ế ậ ỉ ấ ch ch p nh n m t ti n trình s d ng t ể ờ ộ m t th i đi m • N u nhi u ti n trình s d ng tài nguyên ề ế ế ả ơ ả ờ ồ đ ng th i, có nguy c x y ra các k t qu ượ ự không d đoán đ c • C n b o đ m ti n trình đ c quy n truy ế

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ầ ấ ả xu t tài nguyên

ầ

ố ợ

ệ ố

Yêu c u ph i h p (Synchronization) ệ ủ ề ố ộ ự ng quan v t c đ th c hi n c a ể hai ti n trình trong h th ng là không th bi

• M i t ố ươ ế ế ướ c t tr ư ữ ế ố

ợ ụ

ạ ộ ả ồ ầ ộ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Nh ng có nh ng tình hu ng các ti n trình ệ ầ c n h p tác trong vi c hoàn thành tác v , ủ khi đó c n ph i đ ng b hóa ho t đ ng c a ế các ti n trình

ấ

ể

ề

ạ

ề V n đ tranh đo t đi u khi n (race condition) (1)

1 và P2 th c hi n công

ệ ế • có hai ti n trình P

ự ẻ ế taikhoan

ề ệ ế ả

vi c k toán, và cùng chia s bi n ả ph n ánh thông tin v tài kho n – if (taikhoan tienrut >=0) – taikhoan = taikhoan tienrut; – else – error(« khong the rut tien ! »);

• Gi

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ả ả ử s trong tài kho n hi n còn 800, P ố ố mu n rút 500 và P ệ 2 mu n rút 400

ấ

ạ

ề

ể

ệ

ể

• P1 ki m tra đi u ki n (taikhoan tienrut >=0)

ệ ề

ấ

ề V n đ tranh đo t đi u khi n (race condition) (2) ề và ử , h đi u hành c p phát CPU

ờ ế h t th i gian x lý cho P2. ể

ậ ượ ế

c k t

ề • P2 ki m tra cùng đi u ki n trên, nh n đ ẫ

ệ ư c c p nh t l

ề 1 v n ch a rút ti n) và rút 400. Giá ậ ạ ượ ậ i là 400 ẽ ế ụ ử ạ c tái kích ho t và ti p t c x lý, nó s

ề

ạ

ệ ượ ử

ướ

i đi u ki n (taikhoan tienrut c mà t x lý tr ẽ ạ ượ ị ủ taikhoan s l i đ

c

ệ ậ

ỗ ả

ả qu là 400 (do P ị ủ taikhoan đ tr c a ượ • Khi P1 đ ể không ki m tra l ể >=0)vì đã ki m tra trong l ề ự th c hi n rút ti n. Giá tr c a ố ậ c p nh t thành 100. Tình hu ng l

i x y ra !

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ề

Mi n găng (critical section)

(1)

ả ươ ng trình trong đó có kh năng

ấ ề mi n găng

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Đo n ch ạ ẫ ả x y ra các mâu thu n truy xu t trên tài ượ ọ c g i là nguyên chung đ (critical section). – if (taikhoan tienrut >=0) – taikhoan = taikhoan tienrut;

ề

Mi n găng (critical section)

(2)

ề

ả

t bài toán mi n

• M t ph ươ ộ ầ

ề

ế ố i quy t t ng pháp gi ệ ề găng c n thõa mãn 4 đi u ki n – Không có hai ti n trình cùng ở ế trong mi n găng cùng

lúc.

ả

ặ

thi

ư ề ố ượ

– Không có gi ế

ề

ạ

– M t ti n trình t m d ng bên ngoài mi n găng không

ệ ề ố ộ ự ế t nào đ t ra cho s liên h v t c đ ộ ử ủ c a các ti n trình, cũng nh v s l ng b x lý trong ệ ố h th ng ộ ế ượ

ề c ngăn c n các ti n trình khác vào mi n găng ể ượ ả

ả ế

ạ

ờ

ừ ế – Không có ti n trình nào ph i ch vô h n đ đ

c vào

ề

mi n găng

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ả

Gi

i pháp « busy waiting »

ế ờ ệ

i pháp c a Peterson

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ị • S d ng các bi n c hi u ử ụ • S d ng vi c ki m tra luân phiên ệ ể ử ụ • Gi ủ ả • C m ng t ắ ấ • Ch th TSL (TestandSet) ỉ

ử ụ

ế ờ ệ S d ng các bi n c hi u

while (TRUE) { while (lock == 1); // wait

lock = 1; criticalsection (); lock = 0; Noncriticalsection ();

}

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ử ụ

ể ệ S d ng vi c ki m tra luân phiên

while (TRUE) { while (turn != 1); // while (TRUE) { while (turn != 0); //

wait criticalsection (); turn = 0; Noncriticalsection (); wait criticalsection (); turn = 1; Noncriticalsection ();

ế ấ } (b) C u trúc ti n trình ế ấ } (a) C u trúc ti n trình A

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ả

ủ

Gi

i pháp c a Peterson

ạ i

while (TRUE) { int j = 1i; // j là ti n trình còn l

ế interesse[i]= TRUE; turn = j; while (turn == j && interesse[j]==TRUE); criticalsection (); interesse[i] = FALSE; Noncriticalsection ();

}

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ấ

ắ

C m ng t

ấ ấ ả ắ • cho phép ti n trình c m t ế

ắ ướ ề t c các ng t ụ ồ c khi vào mi n găng, và ph c h i ng t

ỏ tr khi ra kh i mi n găng.

ả ề ắ ồ

ừ ạ

ể ạ ử ể ấ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

• Khi đó, ng t đ ng h cũng không x y ra, do ồ ậ ệ ố v y h th ng không th t m d ng ho t ủ ế ộ đ ng c a ti n trình đang x lý đ c p phát ế CPU cho ti n trình khác

ỉ

ị

Ch th TSL (TestandSet)

TestandSetlock(boolean target){ TestandSetlock = target; target = TRUE; } while (TRUE) { while (TestandSetlock(lock));

criticalsection (); lock = FALSE; Noncriticalsection ();

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

}

ậ Nh n xét

ả ả

• Các gi ể ụ ể ộ ệ ề ờ

ế i pháp bu c ti n trình ph i liên t c ệ ể ki m tra đi u ki n đ phát hi n th i đi m ề c vào mi n găng thích h p đ

ề ợ ượ ể

ệ ờ ụ ấ ế ậ ử ụ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ờ ẫ ụ ế • Vi c ki m tra nh th tiêu th r t nhi u ư ế th i gian s d ng CPU, do v y ti n trình đang ch v n chi m d ng CPU

ả

Gi

i pháp « sleep and wakeup »

while (TRUE) { if (busy){ blocked = blocked + 1; sleep(); } else busy = 1; criticalsection (); busy = 0; if(blocked){ wakeup(process); blocked = blocked 1; } Noncriticalsection ();

}

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

Semaphore (1)

ộ • m t semaphore s là m t ộ bi nế có các thu c ộ

tính sau:

ươ e(s) ng

ộ ộ

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ờ • M t giá tr nguyên d ị • M t hàng đ i ế ư ợ f(s) l u danh sách các ti n ị s trình đang b khóa (ch ) trên semaphore

Semaphore (2)

ỉ ượ ị • Ch có hai thao tác đ c đ nh nghĩa trên

ả

semaphore – Down(s): gi m giá tr c a semaphore

ế

ượ ạ c l

s đi 1 đ n ơ ị ủ ế ụ ử ị ị ế v n u semaphore có tr e(s) > 0, và ti p t c x ờ ả ế lý. Ng i, n u e(s) < 0, ti n trình ph i ch ế đ n khi e(s) >0

ị ủ

ộ

ế

ơ ờ

ế

ẽ ọ

ế ụ ử

ố ế

– Up(s): tăng giá tr c a semaphore ị s lên 1 đ n v . ặ ề N u có m t ho c nhi u ti n trình đang ch trên Down, thì h ệ ở ị semaphore s, b khóa b i thao tác ể ế ộ th ng s ch n m t trong các ti n trình này đ Down và cho ti p t c x lý k t thúc thao tác

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ổ ứ

ấ ộ

ề

ớ

T ch c truy xu t đ c quy n v i Semaphores

– while (TRUE) { – Down(s) – criticalsection (); – Up(s) – Noncriticalsection (); – }

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

ổ ứ ồ

ộ

ớ

T ch c đ ng b hóa v i Semaphores

– P1: – while (TRUE) { – job1();

Up(s); //đánh th c P2ứ

– } – P2: – while (TRUE) { – Down(s); // ch P1ờ

job2();

– }

Dang Minh Quan: Institute of IT for Economics-NEU, 2011

Monitors (1)

ệ • Monitor là m t c u trúc đ c bi ộ ấ

ặ ấ ồ t bao g m ữ ệ ế

ỉ

ữ ệ ở

ủ ụ ị

ộ ế

ờ

ộ

ủ ụ các th t c, các bi n và c u trúc d li u có ộ các thu c tính sau – Các bi n và c u trúc d li u bên trong monitor ấ ế ể ượ ch có th đ c thao tác b i các th t c đ nh nghĩa bên trong monitor đó. (encapsulation). – T i m t th i đi m, ch có m t ti n trình duy ỉ c ho t đ ng bên trong m t monitor