Bài giảng môn Hệ điều hành

pdf

236 trang ngocly 3910

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng môn Hệ điều hành", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_mon_he_dieu_hanh.pdf

Nội dung text: Bài giảng môn Hệ điều hành

H ðIU HÀNH 6/17/2009 Operating System 1 Tài liệu tham khảo He: SlideSlide bbàiài gi gi ngng http LêLêKh Kh ccNhiên NhiênÂn Ân,, gigiáốo tr trìnhình “ “HHđ điiuuh hànhành ccơơ bbnn”,”, ððHKHTNHKHTN TPHCMTPHCM TrTr nnH HnhnhNhi Nhi,, gigiáốo tr trìnhình “ “HHđ điiuuh hànhành nângnângcao cao”,”, ððHKHTNHKHTN TPHCMTPHCM 6/17/2009 Operating System 2
TổngTổng quan quan về về hệ hệ thống thống máy máy tính tính Kie áán tru ùcù ma ùùy tính go ààm 2 pha ààn ch ính : + HSA (Kiến trúc hệ thống phần cứng) + ISA (Kiến trúc bộ lệnh) 6/17/2009 Operating System 3 Kiến trúc máy tính CácCác thành thành phần phần chính chính củacủa hệ hệ thống thống máy máy tính: tính: + HSA (Kiến trúc hệ thống phần cứng) ĐểĐể có có thể thể hoạt hoạt động, động, bắtbắt buộc buộc phải phải có: có: • - Hệ thống xử lý • - Hệ thống lưu trữ • - Hệ thống nhập xuất 6/17/2009 Operating System 4
Kiến trúc máy tính HệHệ thống thống lưu lưu trữ trữ Bộ nhớ trong (RAM, ROM, Registers, Cache, Port) Bộ nhớ ngoài (HD, FD, CD, DVD, USB disk, ) 6/17/2009 Operating System 5 Kiến trúc máy tính CácCác thành thành phần phần chính chính củacủa hệ hệ thống thống máy máy tính: tính: + HSA (Kiến trúc hệ thống phần cứng) + ISA (Kiến trúc bộ lệnh) • - Kiểu dữ liệu • - Tập thanh ghi • - Tập lệnh 6/17/2009 Operating System 6
CPU Hệ thống xử lý Các chip xử lý khác Bộ nhớ trong HSA Hệ thống lưu trữ (RAM, ROM, Thanh ghi, Cache, ) Bộ nhớ ngoài (HD, FD, CD, DVD, USB disk, ) Hệ thống nhập xuất (Bàn phím, màn hình, chuột, loa, micro, modem, máy in, ) Kiểu Dữ Liệu ISA Tập Thanh Ghi Tập Lệnh 6/17/2009 Operating System 7 CácCác hệ hệ thống thống số số - Hệ nhị phân (cơ số 2): Hình thức thể hiện: 01001b, 11111001b, 11100b - Hệ thập phân (cơ số 10): Hình thức thể hiện: 9, 249, 28d, - Hệ thập lục phân (cơ số 16): Hình thức thể hiện: 9h, 0F9h, 1Ch, 6/17/2009 Operating System 8
CácCác kiểu kiểu dữ dữ liệu liệu trong trong máy máy tính tính - bit : đơn vị lưu trữ nhỏ nhất - Byte : đơn vị truy xuất của chương trình - Word : đơn vị truy xuất của máy tính (có kích thước phụ thuộc vào CPU & lưu ngược theo đơn vị Byte – xem ví dụ) - Chuỗi ký tự: lưu trữ theo thứ tự bình thường - Số BCD : lưu trữ mỗi chữ số của 1 số thập phân bằng một (hoặc nửa) Byte 6/17/2009 Operating System 9 TổTổ chức chức dữ dữ liệu liệu trên trên bộ bộ nhớ nhớ trong trong - Byte : đơn vị truy xuất bộ nhớ trong của phần mềm (gồm 8 bit - bit phải nhất là bit 0 & bit trái nhất là bit 7) - Word : đơn vị truy xuất của phần cứng (có kích thước phụ thuộc vào CPU) hoặc 1 kiểu dữ liệu của phần mềm (có kích thước phụ thuộc vào phần mềm tương ứng) - Chuỗi ký tự: lưu trữ theo thứ tự bình thường - Số nguyên : lưu ngược theo đơn vị Byte (khảo sát các ví dụ cụ thể) 6/17/2009 Operating System 10
TổTổ chức chức thanh thanh ghi: ghi: + Khái niệm thanh ghi: - Là các vùng nhớ nhỏ lưu dữ liệu trong các chip xử lý - Có tốc độ truy xuất rất nhanh & tần suất sử dụng cao + Kích thước thanh ghi: Tính theo đơn vị bit – tùy thuộc chức năng của chip Các thanh ghi trong CPU 8bit có kích thước 8bit, trong CPU 16bit có kích thước 16bit, trong CPU 32bit có kích thước 32bit đồng thời có luôn các thanh ghi của CPU 16 bit + Số lượng thanh ghi: Thường rất ít, tùy thuộc mức độ xử lý & thiết kế của chip CPU Intel 16 bit có 14 thanh ghi, phân thành 5 nhóm 6/17/2009 Operating System 11 TổTổ chức chức thanh thanh ghi ghi của của CPU CPU 1616 bit:bit: + Nhóm thanh ghi đoạn (Segment register): - CS (Code Segment): lưu chỉ số của segment chứa CT ngôn ngữ máy. - DS (Data Segment): lưu chỉ số segment chứa dữ liệu của CT. - ES (Extra Segment): lưu chỉ số segment chứa dữ liệu bổ sung của CT. - SS (Stack Segment): lưu chỉ số segment chứa ngăn xếp của CT. (Trên CPU 32bit có thêm 2 thanh ghi FS, GS có chức năng tương tự như ES) CT muốn truy xuất 1 vùng nhớ thì phải đưa chỉ số segment của vùng nhớ đó vào một thanh ghi đoạn 6/17/2009 Operating System 12
TổTổ chức chức thanh thanh ghi ghi của của CPU CPU 1616 bit:bit: + Nhóm thanh ghi con trỏ & chỉ mục (Pointer & Index Reg.) - IP (Instruction Pointer): lưu offset của ô nhớ chứa lệnh kế tiếp. - BP (Base Pointer): lưu offset của ô nhớ cần truy xuất. - SP (Stack Pointer): lưu offset đỉnh ngăn xếp. - SI (Source Index): lưu offset vùng nhớ nguồn cần đọc lên. - DI (Destination Index): lưu offset vùng nhớ đích cần ghi xuống. Mỗi thanh ghi trong nhóm này phải đi kèm với 1 thanh ghi trong nhóm thanh ghi đoạn mới biểu thị được vùng nhớ /ô nhớ cần truy xuất. 6/17/2009 Operating System 13 TổTổ chức chức thanh thanh ghi ghi của của CPU CPU 1616 bit:bit: + Nhóm thanh ghi đa dụng (General Register) - AX (Accumulator Register): lưu các dữ liệu số, giá trị mặc định, - BX (Base Register): đóng vai trò chỉ số mảng,, cũng có thể lưu dữ liệu - CX (Count Register): có thể dùng để định số lần lặp. - DX (Data Register): lưu dữ liệu /kết quả tính toán (~AX). Mỗi thanh ghi trong nhóm này đều cho phép sử dụng đến từng Byte, bằng cách thay chữ ‘X’ thành chữ ‘H’ để chỉ Byte cao, hoặc ‘L’ để chỉ Byte thấp (AH, BL, CL) Xem như có thêm 8 thanh ghi mới 6/17/2009 Operating System 14
TổTổ chức chức thanh thanh ghi ghi của của CPU CPU 1616 bit:bit: + Thanh ghi cờ (Flag Register) Không có tên, mỗi bit là 1 cờ, biểu diễn trạng trái của lệnh vừa thực hiện, hoặc đặt trạng trái cho lệnh thực hiện 6/17/2009 Operating System 15 HệHệ thống thống ngắt ngắt (Interrupt): (Interrupt): + Khái niệm: - Là các chương trình con (thủ tục /hàm) có sẵn trong máy - Các hàm ngắt không chỉ có sẵn trong ROM BIOS mà còn được Hệ Điều Hành bổ sung thêm - Hàm ngắt không có tên mà thay vào đó là 1 con số (0 FF) - Mỗi hàm ngắt lại chứa bên trong nó nhiều hàm con - Tham số in./output của hàm ngắt được truyền qua thanh ghi 6/17/2009 Operating System 16
HệHệ thống thống ngắt ngắt (Interrupt): (Interrupt): + Phân loại: Ngắtcứng Ngắtmềm Ngắt Ngắt Ngắt do Ngắt của trong ngoài người dùng tạo hệ thống Ngắt của Ngắt của BIOS HĐH 6/17/2009 Operating System 17 HệHệ thống thống ngắt ngắt (Interrupt): (Interrupt): + Chương trình ngắt: Thường gồm nhiều đoạn chương trình con bên trong, mỗi đoạn thực hiện 1 công việc cụ thể nào đó, chỉ số của đoạn thể hiện trong AH. Khi đó thân hàm ngắt có dạng (mã giả): switch (AH) { case 0: // hàm con 0 break; case 1: // hàm con 1 break; case N: // hàm con N break; 6/17/2009} Operating System 18
Mt S Thi t B ðĩa mm ðĩa cng Card màn hình 6/17/2009 Operating System 19 TổTổ chức chức dữ dữ liệu liệu trên trên đĩa đĩa từ từ + Cấu trúc vật lý : - Hình tròn, gồm nhiều mặt, mỗi mặt có nhiều đường tròn đồng tâm, trên các đường tròn có các cung tròn, thông thường mỗi cung chứa 4096 điểm từ (=4096bit = 512 byte) - Mỗi mặt có tương ứng 1 đầu đọc để đọc hoặc ghi dữ liệu. - Mỗi lần đọc /ghi ít nhất 1 cung tròn (512 B) - Các cung tròn, đường tròn & đầu đọc (hoặc mặt) có các từ gốc tương ứng là sector , track (hoặc cylinder ) & head. - Mỗi lần truy xuất (đọc hoặc ghi đĩa) chỉ có thể thực hiện 6/17/2009trên N sector liên tiếp (N>=1) Operating System 20
TổTổ chức chức dữ dữ liệu liệu trên trên đĩa đĩa từ từ + Cấu trúc vật lý : - Để truy xuất 1 sector cần phải chỉ ra vị trí của sector đó. Vị trí sector được thể hiện bằng 3 thông số: chỉ số sector, track & head - Head được đánh số theo thứ tự từ trên xuống bắt đầu từ 0, Track được đánh số theo thứ tự từ ngoài vào bắt đầu từ 0, Sector được đánh chỉ số theo thứ tự bắt đầu từ 1 theo chiều ngược với chiều quay của đĩa. - Địa chỉ của sector vật lý có ký hiệu : (sector, track, head) 6/17/2009 Operating System 21 TổTổ chức chức dữ dữ liệu liệu trên trên đĩa đĩa từ từ + Tổ chức đĩa logic: 0 1 2 3 4 N-1 - Là 1 dãy các sector được đánh chỉ số theo thứ tự tăng dần bắt đầu từ 0 - Đĩa thật sự là đĩa vật lý nhưng vì truy xuất phải dùng đến 3 tham số rất bất tiện nên khái niệm đĩa logic được đưa ra để dễ hiểu, dễ thao tác /tính toán hơn. - Mỗi sector trên đĩa logic tương ứng với 1 sector duy nhất trên đĩa vật lý sao cho sau khi truy xuất sector K thì truy xuất tiếp sang sector K+1 là nhanh hơn so với tất cả các sector khác. 6/17/2009 Operating System 22
ðĩa cng đĩa cng , hay cịn gi là cng (Hard Disk Drive -HDD ) là thi t b dùng đ lưu tr d li u trên b mt các tm đĩa hình trịn ph vt li u t tính . 6/17/2009 Operating System 23 ðĩa cng 6/17/2009 Operating System 24
ðĩa cng Trên mt track chia làm nhi u cung bng nhau là 1 sector và đư c đánh s t mt. Qua track mi đánh s li. S sector trên mi track là bng nhau . Cylinder là tp hp các track cĩ cùng s hi u trên tt c các mt. Cluster là tp hp các sector ( đĩa mm 1 cluster = 1 sector) 6/17/2009 Operating System 25 ðĩa cng ðơ n v cơ s ca đĩa là sector ( th ưng = 512 byte) ðĩa là thi t b xu t nh p theo kh i. Mt sector đư c xác đnh bng 2 cách : Sector tươ ng đi: sector vt lý xác đnh bi head ( đánh s t 0), track ( đánh s t 0) trên head và sector trên track ( đánh s t 1). Sector tuy t đi: sector logic xác đnh bi mt thơng tin. Cách đánh s xác đnh sector tuy t đi nh ư sau : đánh s ht trên mt cylinder sau đĩ tr v mt 0 đ đánh s ti p theo cho mt 0 ca cylinder ti p theo . 6/17/2009 Operating System 26
ðĩa cng Ví d: cho mt đĩa cng cĩ 160 mt, 640 cylinder và 80 sector/track. Hi cng cĩ dung lưng bao nhiêu MB? Dung lưng = S sector/ đĩa * 512 (byte) DL = S sector/cylinder * 640 * 512 (byte) DL = S sector/track * 160 * 640 * 512 (byte) DL = (80 * 160 * 640 * 5120) : (1024 2) (MB) 6/17/2009 Operating System 27 Card Màn Hình Ch t lưng màn hình ph thu c vào card màn hình . Cĩ 3 yu t đ xác đnh ch t lưng ca card màn hình : ð phân gi i ví d 800x600 S màu = s màu ca 1 pixel đư c quy đnh bi s bit màu qu n lý cho 1 pixel. Kích th ưc b nh = 1p * s trang . Trong đĩ 1p = đ phân gi i * s byte màu. (1p là mt trang màn hình ). 6/17/2009 Operating System 28
Card màn hình Ví d: 1 card màn hình s dng đ phân gi i 800x600 cĩ th hi n đư c 65536 màu. Tc đ load hình là 24 frame/s. Hi card màn hình này cĩ dung lưng là bao nhiêu Mb. 65536 màu = 2 16 màu = 2 byte màu Tc đ load hình 24 frame/s s trang là 24 Kích th ơc b nh = 1p * s trang = 1p * 24 Kích th ưc = đ phân gi i * s byte màu * 24 Kích th ưc = 800*600*2*24 (byte) ≈ 22 (MB) 6/17/2009 Operating System 29 Câu hi ơn tp 1/ Cho mt đĩa cng cĩ dung lưng 640 MB, đĩa này s dng 640 mt. Bi t s sector trên 1 track gp đơi s track trên mt mt. Hi s sector trên mt cylinder là bao nhiêu ? 2/ Cho mt card màn hình cĩ dung lưng 8 MB, s dng 24 frame/s. Hi card màn hình này cĩ th s dng đư c nh ng đ phân gi i thơng th ưng nào khi s màu hi n th là 256 màu. 3/T ìm cơng th c xác đnh s hi u sector tuy t đi t sector tươ ng đi và ng ưc li. 6/17/2009 Operating System 30
DL = S Sec /ðĩa * 512 (byte) DL = S Sec/m t * S Mt/ðĩa * 512 DL = S Sec/m t * S Mt * 512 DL = S Sec/Track * S Track/m t * S Mt * 512 DL = x * x/2 * 640 * 512 (byte) = 640 (MB) = 640*1024*1024 x? S Sec/Cyl = S Sec/Track * S Track/Cyl S Sec/Cyl = x * S Track/Cyl S Sec/Cyl = x * S mt/ðĩa 6/17/2009 Operating System 31 Tng quan v H điu hành Tr n Sơn Hi Khoa Tốn – Tin hc ði hc Sư ph m TPHCM Heavily reference to Operating System Slide of Hoang Than Anh Tuan, University of Pedagogy, HCMC 6/17/2009 Operating System 1
Ni dung •H điu hành là gì? • Vai trị và đc đim ca h điu hành •Lch s phát tri n ca h điu hành • Các ch c năng cơ bn ca h điu hành 6/17/2009 Operating System 2 H điu hành là gì? • Là mt ch ươ ng trình (ph n mm)! • Ch ươ ng trình đu tiên đưc ch y sau khi kh i đng. • ðiu ph i vi c thi hành các ph n mm khác • Cung cp các dch v thơng dng s dng bi ng ưi dùng và các ch ươ ng trình ng dng khác 6/17/2009 Operating System 3
ðnh ngh ĩa HðH •HðH là mt ch ươ ng trình ho t đng nh ư là mt trung gian gi a ng ưi dùng và ph n cng máy tính . •Mc đích ca HðH : –Ki m sốt và th c thi các ch ươ ng trình ng dng. –Qu n lý ti n trình –Qu n lý CPU –Giúp ng ưi s dng d s dng máy vi tính. –S dng tài nguyên ph n cng máy tính mt cách hi u qu –Qu n lý đĩa cng 6/17/2009–Qu n lý b nh Operating System 4 Vai trị ca HðH gcc gdb Ng ưi dùng OS Kernel diff grep ng dng Hard ware vi date HðH xterm emacs Ph n cng netscape 6/17/2009 Operating System 5
Vai trị ca HðH (tr ng th ái tĩnh ) (tt) 6/17/2009 Operating System 6 Vai trị ca HðH (tr ng thái đng) (tt) 6/17/2009 Operating System 7
Phân lp trong mt h th ng Ng ưi dùng Lp trình viên ð ng dng Thao ph c tác tp Ch c năng h tr K sư d tăng thi t k HðH dn dn H điu hành Ph n cng 6/17/2009 Operating System 8 Mơ hình khác Nhi u ng dng ng dng Mt System HðH calls HðH Mt Ph n cng Lnh Lnh đc quy n ca máy Ph n cng 6/17/2009 Operating System 9
HðH là mt PM cĩ tính ph n ng • Nĩ ch đi các s ki n (event). • Khi mt s ki n xy ra, HðH ph n ng. –HðH x lý s ki n đĩ. • Cĩ thêm mt ch ươ ng trình mu n ch y. • Cĩ thêm thi t b mi gn vào • Vi c x lý s ki n ph i tn càng ít th i gian càng tt. • Lo i s ki n – Ng t (interrupts) –Li gi h th ng (System calls) 6/17/2009 Operating System 10 Ng t • Ng t là mt cách th c mà ph n cng thơng báo cho HðH v các tình hu ng đc bi t địi hi HðH ph i lưu ý • Ng t làm cho CPU tm dng thi hành ch th k ti p • Thay vì đĩ, quy n điu khi n đưc chuy n sang cho HðH 6/17/2009 Operating System 11
Minh ha ng t Chương tr ình A LOAD Ax, [DS+120] MOV Bx, 5 Cĩ thi t b mi Ng t HðH ADD Ax, Ax, Bx x lý ng t STORE [DS+120], Ax 6/17/2009 Operating System 12 X lý ng t • B x lý ng t là mt ph n ca mã lnh HðH dùng đ thao tác liên quan đn hồn cnh phát sinh ra ng t – Các con tr tr đn các b x lý ng t đưc lưu trong vector ng t (interrupt vector ) – Vector ng t đưc lưu trong mt v trí b nh đưc đnh tr ưc 6/17/2009 Operating System 13
X lý ng t (tt) • Khi mt ng t xy ra: – CPU chuy n sang ch đ Kernel – Chuy n quy n điu khi n cho b x lý ng t thích hp – ða ch ca b x lý ng t đưc tìm th y bng cách s dng s th t ca ng t nh ư là mt ch s đ vector ng t: • Jump &int[interrupt#] 6/17/2009 Operating System 14 Vector ng t • ða ch vector ng t và s th t ng t là mt ph n trong đc t ph n cng •HðH ti các đa ch ng t vào trong vector ng t trong quá trình kh i đng 6/17/2009 Operating System 15
Các lo i ng t • Ng t khơng đng b đưc to ra bi các thi t b ngo i vi ti nh ng th i đim khơng th bi t tr ưc • Ng t bên trong (đng b) đưc to ra bi CPU do mt tình hu ng cĩ th lưng tr ưc – Tình hu ng gây li –Vn đ cĩ tính tm th i 6/17/2009 Operating System 16 Li gi h th ng •H điu hành cung cp mt tp hp các dch v h th ng (các ch c năng mà h điu hành cung cp, th ưng liên quan đn ph n cng). – Nh m giúp cho các ch ươ ng trình ng dng khơng cn quan tâm đn chi ti t ph n cng –Tp hp các li gi h th ng đưc gi là API ca HðH (OS API) – ðưc đĩng gĩi thành mt th ư vi n • Khi mt ch ươ ng trình mu n s dng mt dch v nào đĩ ca HðH chúng s phát sinh mt li gi h th ng (system call) . • Các li gi h th ng th ưng th y –M/đc/ghi/đĩng file –Ly ngày gi hi n ti –To ti n trình mi – Yêu cu thêm b nh 6/17/2009 Operating System 17
Ch ươ ng trình ng ưi dùng khơng th truy cp vào các cu trúc ni ti ca HðH ; ch cĩ th thơng qua li gi h th ng (protection! ) Cơ ch bo v phân lp ng dng Ch đ system user calls Cu tr úc Ch đ Các dch v kernel bên trong HðH HðH Ph n cng 6/17/2009 Operating System 18 Ch đ thi hành CPU • CPU h tr ít nh t là 2 ch đ thi hành (dual mode): • User mode (ch đ ng ưi dùng) – Mã lnh ca ch ươ ng trình ng ưi dùng • Kernel (supervisor, privileged, monitor, system) mode – Mã lnh ca HðH • Ch đ thi hành đưc ch ra bi mt bit trong word tr ng thái x lý (processor status word) (PSW) 6/17/2009 Operating System 19
Kernel Mode •Gn nh ư ki m sốt hồn tồn ph n cng: – Các ch th CPU đc bi t – Truy cp khơng gi i hn đn b nh , đĩa, 6/17/2009 Operating System 20 Các ch th ch cĩ trong Kernel mode •Ti/lưu các thanh ghi đc bi t • VD: các thanh ghi dùng đ đnh ngh ĩa các đa ch vùng nh cĩ th truy cp đưc • Ánh x các trang b nh đn khơng gian đa ch ca mt ti n trình xác đnh • Ch th đc mc đ ưu tiên ca ng t • Ch th đ kích ho t thi t b I/O 6/17/2009 Operating System 21
Bo v Kernel mode • ðon mã ca HðH thi hành ch đ Kernel – Ng t, li gi h th ng • Ch đon mã ca HðH mi đưc thi hành ch đ Kernel • ðon mã ca ng ưi dùng khơng bao gi đưc thi hành trong ch đ Kernel 6/17/2009 Operating System 22 Các li gi h th ng trong Unix •Process control –fork(), exec(), wait(), abort() •File manipulation –chmod(), link(), stat(), create() •Device manipulation –open(), close(), ioctl(), select() •Information maintenance –time(), acct(), gettimeofday() •Communications –socket(), accept(), send(), recv() 6/17/2009 Operating System 23
Câu hi HðH đc d li u vào, thi hành tính tốn, xu t ra kt qu và thốt. ðúng hay sai? SAI!!! HðH là mt ch ươ ng trình cĩ tính ph n ng (reactive program ) 6/17/2009 Operating System 24 Câu hi •H điu hành là gì. Ví d các h điu hành mà bn bi t. • Ng t là gì? •V mơ hình phân lp trong mt h th ng và trình bày vai trị ca h điu hành trong đĩ. • Tìm hi u các lnh trong MS-DOS. (dir, copy, copy con, del, ipconfig, netstat, ipconfg /all, nslookup, 6/17/2009 Operating System 25
Lch s phát tri n ca HðH 6/17/2009 Operating System 26 Lch s phát tri n HðH Tr n Sơn Hi Khoa Tốn – Tin hc ði hc Sư ph m TPHCM Heavily reference to Operating System Slide of Hoang Than Anh Tuan, University of Pedagogy, HCMC 6/17/2009 1
H điu hành là gì? • Th nào là mt h điu hành? –Mt nhà cung cp s tr u tưng hĩa –Mt nhà cp phát tài nguyên – Ngồi ra: •Mt điu ph i viên •Mt ng ưi bn: giúp máy tính d s dng •Mt phù th y: làm cho h th ng cĩ v cĩ nhi u hơn cái th t s nĩ cĩ (nhi u vi x lý, nhi u b nh hơn) – Cơng vi c ca h điu hành da theo ph n cng. 6/17/2009 2 HðH bao gm nh ng gì? File systems Device drivers Networking protocols System utilities Shells Libraries Accessories Browser 6/17/2009 3
Th i kỳ kh i đu ENIAC: (1945—1955) 2. D án ch to máy ENIAC (Electronic Numerical Integrator and Computer) đưc BRL (Ballistics Research Laboratory – Phịng nghiên cu đn đo quân đi M) bt đu vào năm 1943 dùng cho vi c tính tốn chính xác và nhanh chĩng các bng s li u đn đo cho tng lo i vũ khí mi. Các thơng s: -18000 bĩng đèn chân khơng - nng hơn 30 tn - Tiêu th mt lưng đin năng vào kho ng 140kW và chi m mt di n tích xp x 1393 m2 . - 5000 phép cng/ 1s - ðc bi t s dng h đm th p phân 6/17/2009 4 Lch s HðH : Lch s phát tri n ph n cng • Kh i đu: Khơng cĩ HðH » Máy tính là thi t b th c nghi m kỳ l. »Lp trình bng ngơn ng máy. » Dùng các bng tng đài đ điu khi n máy tính. » Ng ưi s dng ng i tr ưc bng điu khi n. » Khơng cĩ s ch ng nhau gi a vi c tính tốn, I/O và th i gian suy ngh ĩa ca ng ưi dùng. »Lp trình bng cách đư a phi u đc l vào bng tay. » ðã cĩ th ư vi n đưc vi t dùng chung cho mi ng ưi ti n thân ca h điu hành. » Vn đ: ch đi quá lâu, quá nhi u. 6/17/2009 5
Giai đon 1: máy tính đt, nhân cơng r. (1948 – 1975) •S dng máy tính hi u qu hơn: tách ri máy và ng ưi. •HðH h tr làm vi c theo lơ : mt ch ươ ng trình ti cơng vi c ca ng ưi dùng vào, thi hành nĩ và làm ti p cơng vi c k ti p. •Nu ch ươ ng trình li, HðH ghi li ni dung ca b nh và lưu li đâu đĩ. •S dng tài nguyên hi u qu hơn, nh ưng khĩ debug ! 6/17/2009 6 Các kênh d li u và ng t cho ph ép I/O và tính to án ch ng nhau. Vùng đm và x lý ng t đưc h tr bi h điu hành. Xu t hi n cơng vi c spool. Vn đ Ti n ích cịn th p; mi th i đim ch ch y mt cơng vi c. Khơng cĩ s bo v gi a các cơng vi c khác nhau. Cơng vi c cĩ th i gian thi hành ng n s ph i đi rt lâu nu nĩ đưc sp sau cơng vi c cĩ th i gian thi hành dài hơn. Gi i pháp Bo v ph n cng: bo v vùng nh và tái đnh v vùng nh . Lp trình đa ch ươ ng (Multiprogramming): nhi u ng ưi dùng cĩ th chia s cùng mt h th ng. Cơng vi c nh cĩ th nhanh chĩng đưc hồn thành. HðH ph i qu n lý tươ ng tác gi a các cơng vi c đng th i. HðH tr nên mt khoa hc quan tr ng. •OS/360 : HðH đu tiên thi t k cho mt h các máy tính: t máy tính nh nh t đn máy tính ln nh t. 6/17/2009 7
Vn đ •OS/360 đưc gi i thi u vào năm 1963; và đn năm 1968 nĩ mi th t s ho t đng. Hơn 1000 li khi phát hành •H th ng cc kỳ ph c tp. •Tt c đu là mã hp ng (assembly code). 6/17/2009 8 Giai đon 2:Máy tính r hơn - nhân cơng đt! (1975-1985) Giúp con ng ưi tăng năng su t. Chia s th i gian : cho phép nhi u ng ưi s dng máy tính cùng mt lúc. •Thi t b cu i r: mi ng ưi đu cĩ th mua. •D li u đưc lưu tr : dùng các h th ng file. •Th nghi m cung cp th i gian ph n hi ch p nh n đưc (tránh tình tr ng tranh ch p tài nguyên; s đ v (thrashing) ). Th tr ưng đưc đnh hưng bi các ng dng theo chi u dc. CTSS: •Phát tri n ti MIT. •Mt trong nh ng h th ng chia s th i gian đu tiên. •Tiên phong trong vi c lp lch 6/17/2009 9 •Kh i ngu n cho MULTICS.
MULTICS: •Hp tác phát tri n bi MIT, Bell Labs, General Electric. •Vi n cnh: mt máy tính h tr cho mi ng ưi. Mi ng ưi s mua dch v tính tốn nh ư là mua đin. •Rt nhi u ý tưng! •Xây dng rt khĩ so vi d tính. •Cơng ngh đã bt kp. 6/17/2009 10 UNIX: – Ken Thompson và Dennis Ritchie xây dng mt h th ng “do Lp trình viên vì lp trình viên”. – Ban đu đưc cài đt bng hp ng . ðưc vi t li bng C sau này. – Ý tưng mi: HðH cĩ th di chuy n đưc! – Các tr ưng ðH đưc cung cp đon mã đ tham kh o. – ðH Berkeley thêm vào h tr b nh o cho VAX. – DARPA ch n UNIX làm nn tng mng (arpanet). – UNIX tr thành HðH th ươ ng mi. – Các ý tưng quan tr ng đưc ph bi n thơng qua UNIX –HðH đưc vi t trên ngơn ng cp cao. –HðH cĩ th di chuy n đưc khơng ph thu c vào nn tng ph n cng. –Cơ ch đưng ng (pipe) –H th ng file cĩ th đưc np. 6/17/2009 11
Giai đon 3: Máy tính rt r - nhân cơng rt đt. (1981 - ) ðư a máy tính đn tng tr m đu cu i! CP/M: HðH th ươ ng mi đu tiên. IBM cn mt ph n mm cho PC mi ca h, nh ưng CP/M khơng nm bt đưc th i cơ. Ti p cn Bill Gates (Microsoft) đ xem h cĩ th xây dng mt cái vy khơng. Bill Gates mua 86-DOS, và to nên MS-DOS. Mc đích chính: hồn thành nhanh và ch y đưc các ch ươ ng trình CP/M hi n hành. HðH tr thành mt th vi n gm các th tc con và các lnh cĩ th thi hành đc. 6/17/2009 12 Personal workstations – The PERQ – The Xerox Alto – The SUN Workstation (Stanford University Network) Personal computers – The Apple II – The IBM PC – The Macintosh ng dng trong cơng nghi p – Word processors – Spreadsheets – Databases Th tr ưng chia theo chi u ngang – Hardware – Operating systems – Applications 6/17/2009 13
Graphical User Interfaces • Xerox Star: 1981 – Chu t, windows Xerox Star • Apple Lisa/Machintosh: 1984 – “Look and Feel” suit 1988 • Microsoft Windows: – Win 1.0 (1985) Single – Win 3.1 (1990) Level Windows 3.1 – Win 95 (1995) – Win NT (1993) HAL/Protection – Win 2000 (2000) No HAL/ – Win XP (2001) Full Prot 6/17/2009 14 Giai đon 4: Mng xu t hi n! Vi c kt ni tr nên quan tr ng, bc thi t. Ng ưi ta mu n chia s d li u ch khơng ph i ph n cng. ng dng mng đy đn cho nn cơng nghi p. •WWW •Email •News Vi c bo v và lp trình đa ch ng tr nên kém quan tr ng cho các máy tính cá nhân. Nĩ quan tr ng hơn cho các máy tính ch (server ) Th tr ưng ti p tc phân hĩa theo chi u ngang: •Cung cp dch v Internet •Thơng tin tr thành mt ph ươ ng ti n •Qu ng cáo trên máy tính. 6/17/2009 15
HðH ngày nay H th ng ln và ph c tp vi vơ s vn đ. – hàng tri u dịng lnh. – hàng tr ăm, hàng ngàn ng ưi phát tri n. Tươ ng tác ph c tp – Khơng đng b. – Ch y trên mi nn tng. – Phân lp ng ưi dùng theo nhu cu. – Hi u năng s dng! Khĩ hi u – Khơng cịn nh ư nguyên bn đưc to ra. – Quá ln đ cho mt ng ưi cĩ th nm bt đưc. – Khơng đưc ki m li đy đ (OS/360 phát hành vi 1000 li). – Khĩ d đốn hành đng; ti ưu ch yu da vào cm tính (đốn). 6/17/2009 16 6/17/2009 17
Phân lo i h điu hành • Theo s ng ưi dùng – Single và Multi user • Theo s tác v – Single và Mutil task • Theo giao di n – Command line và Graphic 6/17/2009 18 Câu Hi • Trình bày ng n gn v các giai đon phát tri n ca h điu hành. • Li t kê các h điu hành nhi u dùng và nhi u tác v. Win XP là h điu hành mutil user- mutil task nh ư Linux đúng khơng? • Li t kê các lnh cơ bn trong h điu hành Linux. 6/17/2009 19
Tĩm li • Khơng h điu hành • Batch monitor Multiprogramming • Time sharing Graphical UI • Th ư vi n API c a H ðiu Hành (như Windows API) • Network • PDA • Ki n trúc ca h điu hành MS-DOS? • Bài tp nghiên cu: tìm hi u và so sánh tp lnh trong MS-DOS và LINUX. 6/17/2009 20 Ti n trình Tr n Sơn Hi Khoa Tốn – Tin hc ði hc Sư ph m TPHCM Heavily reference to Operating System Slide of Hoang Than Anh Tuan, University of Pedagogy, HCMC 6/17/2009 Operating System 1
Ni dung • Khái ni m đa ch ươ ng • Ti n trình • Lu ng (ti u trình) • Khơng gian đa ch •S liên quan gi a ti n trình, ti u trình và khơng gian đa ch •Lp lch ti n trình 6/17/2009 Operating System 2 Ti n trình là gì? • Ti n trình = mt th hi n ca vi c thi hành mt ch ươ ng trình – Th ưng gi là “HeavyWeight Process” • Ti n trình là mt s tr u tưng hĩa cung cp bi HðH , ch ra nh ng gì là cn thi t đ thi hành mt ch ươ ng trình –Mt ng cnh tính tốn tách bi t cho mi ng dng • Ng cnh tính tốn – Tr ng thái CPU + khơng gian đa ch + mơi tr ưng 6/17/2009 Operating System 3
Ti n trình là gì? (tt) • Ti n trình th ưng gm cĩ hai ph n: –Mt dãy các lnh mà nĩ cn ph i thi hành • Code • Tr ng thái CPU – Các tài nguyên ca riêng nĩ • Tr ng thái b nh chính (khơng gian đa ch ) • Tr ng thái nh p xu t (file đang thao tác) 6/17/2009 Operating System 4 Tr ng thái CPU=Ni dung các thanh ghi • Word tr ng thái ti n trình (PSW) – ch đ thi hành, kt qu lnh cu i cùng, mc ng t • Thanh ghi lnh (IR) – Ch th hi n ti đang đưc thi hành •B đm ch ươ ng trình (PC) • Con tr ng ăn xp (SP) • Các thanh ghi cơng dng chung 6/17/2009 Operating System 5
Khơng gian đa ch • Data –D li u đnh tr ưc (th i đim biên dch) • Code – ðon mã ch ươ ng trình • Heap –D li u đưc cp phát đng • Stack –H tr li gi hàm 6/17/2009 Operating System 6 Mơi tr ưng • Các th c th bên ngồi – Thi t b đu cu i – File đang m – Kênh kt ni •Cc b •Vi các máy khác 6/17/2009 Operating System 7
Kh i điu khi n ti n trình (PCB) • Ng cnh tính tốn ca mi ti n trình đưc lưu trong mt kh i điu khi n ti n trình (Process Control Block: PCB) Process Control 6/17/2009 Operating System Block 8 Process control block (PCB) PCB kernel user CPU state PSW memory code IR files data accounting PC priority heap SP user general CPU registers purpose registers storage stack 6/17/2009 Operating System 9
Process State Priority Process number Program Counter Stack Pointer I/O Status Information Memory Information Base head Limits tail File Information Accounting Information PCB 12 Prio : 200 PCB 42 PCB 3 Prio 200 Prio 100 PCB 41 PCB 0 Prio 3 Prio 0 6/17/2009 Operating System 10 Chuy n đi ng cnh ti n trình • CPU chuy n đi ti n trình này sang ti n trình khác • Chuy n đi ng cnh (context switching) overhead • Tr ng thái ca ti n trình luơn thay đi 6/17/2009 Operating System 11
Chuy n đi tr ng thái ca ti n trình • Tr ng thái ca ti n trình – new : Ti n trình va đưc to (ch y ch ươ ng trình) – ready : Ti n trình sn sàng đ ch y – running : Ti n trình đang ch y (thi hành lnh) – waiting : Ti n trình ch đi mt s ki n – terminated : Ti n trình kt thúc thi hành lnh 6/17/2009 Operating System 12 Tr ng thái ca ti n trình (khác) terminated running schedule wait for event preempt created ready blocked event done 6/17/2009 Operating System 13
Mơi tr ưng UNIX running schedule user sys. call return interrupt ready interrupt zombie user running terminated preempt kernel schedule wait for event created ready blocked kernel event done 6/17/2009 Operating System 14 ðiu ph i ti n trình • Cĩ nhi u hàng đi: – ready queue: hàng đi ch a các ti n trình sn sàng ch y – I/O queue: hàng đi ch a các ti n trình sn sàng thi hành I/O •La ch n ti n trình nào điu ph i ti n trình 6/17/2009 Operating System 15
Ti n trình = Ch ươ ng trình ? main () main () Heap { { ; ; } } Stack A() { A() { A main } Program } Process •Mt ch ươ ng trình cĩ th cĩ nhi u ti n trình –M Notepad.exe xem file a.txt 1 ti n trình. –M Notepad.exe xem file b.txt 1 ti n trình. • Ch ươ ng trình nhìn t gĩc đ mã lnh ch là mt ph n ca ti n trình. 6/17/2009 Operating System 16 Nhi u ti n trình hp tác Proc 1 Proc 2 Proc 3 • Cĩ nh ng cơng vi c cn cĩ nhi u ti n trình hp tác vi nhau đ hồn thành . • Th i gian đ to ti n trình –To kh i PCB –To khơng gian đa ch • Th i gian chuy n đi các ti n trình •Cn cĩ mt cơ ch giao ti p: – Tách bi t khơng gian đa ch ca các ti n trình vi nhau – Ánh x vùng nh chia s – Truy n thơng đip • send() và receive() 6/17/2009 Operating System 17
Giao ti p bng Shared-Mem Data 2 Code Code Stack 1 Data Data Heap 1 Heap Heap Code 1 Stack Stack Stack 2 Shared Shared Data 1 Prog 2 Prog 1 Heap 2 Virtual Virtual Address Code 2 Address Space 2 Space 1 Shared • Giao ti p thơng qua thao tác đc/ghi trên vùng nh chung 6/17/2009 Operating System 18 Giao ti p gi a các ti n trình (IPC) • (Inter-Process Communication) Cơ ch cho phép các ti n trình giao ti p vi nhau và đng b hĩa hành đng ca chúng •H th ng thơng đip – các ti n trình giao ti p vi nhau khơng cn ph i qua các bi n dùng chung • IPC cung cp hai thao tác cơ bn: – send (message ) – receive (message ) •Nu ti n trình P và Q mu n giao ti p vi nhau, chúng ph i: – to mt đưng giao ti p gi a chúng – trao đi các thơng đip thơng qua send/receive 6/17/2009 Operating System 19
Ti u trình (Thread = LightWeight Process) • Ti u trình (lu ng): mt s thi hành (ho t đng) bên trong mt ti n trình •Mt ti n trình đa lu ng bao gm nhi u hat đng cùng tn ti và thi hành • Tách bi t: – Tr ng thái CPU, ng ăn xp • Chia s: –Mi th khác • Data, Code, Heap, mơi tr ưng – ðc bi t: Khơng gian đa ch (Ti sao?) 6/17/2009 Operating System 20 Ti u trình (tt) • MultiThreading = mt ch ươ ng trình đưc to ra bng mt s các hat đng đng th i. • HeaveWeight Process = Ti n trình vi duy nh t mt ti u trình 6/17/2009 Operating System 21
ðơ n ti u trình và đa ti u trình 6/17/2009 Operating System 22 Mt s ví d v ch ươ ng trình đa ti u trình • Database server: – Nhi u kt ni và cơ s d li u cùng mt lúc • Network Server: – Truy cp đng th i t mơi tr ưng mng –Mt ti n trình – nhi u thao tác đng th i – File Server, Web server, • Paralell Programming (cĩ nhi u CPU) – Chia ch ươ ng trình thành nhi u thread đ tn dng nhi u CPU – Cịn gi là Multi - Processing 6/17/2009 Operating System 23
H tr ti u trình •HðH – Ưu đim: lp lch ti u trình đưc th c hi n bi OS •Ti ưu hĩa CPU – Khuy t đim: nhi u ti u trình overhead •Mc ng ưi dùng – Ưu đim: overhead th p – Khuy t đim: OS khơng nh n ra c th • VD: mt ti u trình b block do I/O s block tt c các ti u trình khác cùng mt ti n trình 6/17/2009 Operating System 24 Chuy n đi tr ng thái ca Thread •Tươ ng t nh ư ti n trình: – new : Ti u trình đưc to mi – ready : Ti u trình đang ch đ ch y – running : Ti u trình đang đưc thi hành – waiting : Ti u trình đang ch s ki n – terminated : Ti u trình kt thúc thi hành • Thơng tin ti u trình lưu trong TCB 6/17/2009 Operating System 25
Lp trình đa ch ươ ng • Lp trình đa ch ươ ng : Cĩ nhi u cơng vi c (ti n trình, ti u trình) trong h th ng –Tn dng th i gian ch ng nhau ca CPU và I/O – Chia s th i gian trên mt CPU – Thi hành đng th i trên nhi u CPU –Kt hp c hai • Ưu đim? – Tính ph n hi nhanh, ti ưu hĩa, thi hành đng th i • Khuy t đim? – Overhead, ph c tp 6/17/2009 Operating System 26 Lp lch các ti n trình (STS) • Tình hu ng: – Cĩ nhi u ti n trình nh ưng ti mt th i đim ch cĩ mt ti n trình cĩ th đưc th c thi (tr ng thái là running) –Vn đ: ch n ti n trình nào đ th c thi bưc k ti p (t tr ng thái ready chuy n sang tr ng thái running) • Lp lch là thao tác quy t đnh ti n trình nào đưc quy n th c thi . 6/17/2009 Operating System 27
Lp lch (tt) • Gi s: –Mt ti n trình ch cĩ mt ti u trình (HeaveWeight Process) • Lưu ý: H điu hành lp lch mc ti u trình – Các ti n trình là đc lp vi nhau • Khơng cĩ hp tác, chia s tài nguyên vi nhau • Các ti n trình hp tác đng b hĩa ti n trình (ch ươ ng sau) – Mơ hình th c thi ca các ti n trình là mt chu i th i gian s dng CPU và I/O xen k nhau • Ch tp trung vào lp lch cho th i gian CPU 6/17/2009 Operating System 28 Lp lch (tt) • Ch ươ ng trình s s dng CPU trong mt kho ng th i gian. • Sau đĩ thi hành thao tác I/O • Ti p tc s dng CPU, 6/17/2009 Operating System 29
Tính ch t kh i vi c! ? Cĩ ph thu c kh i lưng cơng vi c khơng? Cĩ: –Nu mi cơng vi c đu s dng CPU ho c I/O nh ư nhau thì lp trình đa ch ươ ng khơng ci ti n tính ti ưu hat đng •Mt b cơng vi c hn hp s đưc to bi b lp lch dài hn (long-time scheduling) – Cơng vi c s đưc phân đnh là s dng nhi u CPU ho c nhi u I/O tùy thu c vào quá trình thi hành tr ưc đĩ ca nĩ • Quan tâm vào b lp lch ng n hn (Short- Time Scheduling) 6/17/2009 Operating System 30 Tiêu chu n đánh giá vi c lp lch •Ti thi u hĩa th i gian ph n hi (response time) •Ti thi u hĩa th i gian lu li trong h th ng (turnaround time) – Tturn around = Tkt thúc –Tbt đu •Ti đa hĩa throughput – Throughput = s cơng vi c x lý trong mt đơ n v th i gian • S cơng bng (Fairness) – Các ti n trình đu đưc đi x cơng bng. Khơng cĩ ti n trình nào ph i ch quá lâu •Ti ưu hĩa CPU (Efficient) 6/17/2009 Operating System 31
Turn around time Job 1 Job 2 Job 3 arrives arrives arrives Job1 Job2 Job3 Job 1 Job 2 Job 3 terminates terminates terminates Job3 Job1 Job2 Job 1 terminates Job 3 Job 2 terminates terminates 6/17/2009 Operating System 32 Th i gian ch y (Trun ) • Th i gian ch y = th i gian s dng CPU – Khơng tính th i gian ch IO dù th t s lúc đĩ ch ươ ng trình vn “đang ch y” •Bi vì theo STS: các ti n trình ph thu c nhi u vào I/O th ưng cĩ th i gian khá ng n – Trình so n th o!!! 6/17/2009 Operating System 33
Các đ đo thơng dng • Th i gian ph n hi (response time) <> Th i gian lưu li h th ng (turnaround time) • T s ph n hi slowdown=Tturn / Trun Kt th úc (T ðưa vào hàng đi turn) Bt đu ch y ho c ch IO (Tresp ) Twait Trun Tresp Tresp = Twait + Trun 6/17/2009 Operating System 34 Các đ đo khác • Th i gian ch đi: giá tr trung bình ca Twait •T s ph n hi (slowdown) slowdown=Tresp / Trun • Throughput: cc đi hĩa s ti n trình hồn thành trong mt đơ n v th i gian ph thu c vào chi ti t c th ca ti n trình ít hu dng. 6/17/2009 Operating System 35
Ti ưu hĩa CPU 1st I/O I/O 2nd I/O I/O 3rd I/O operation ends operation ends operation CPU idle idle idle Disk idle idle idle CPU Job1 Job2 Job1 idle Job2 Disk idle Job1 idle Job2 Job1 idle 6/17/2009 Operating System 36 Chi phí cho lp trình đa ch ươ ng • Overhead cho s chuy n đi –Lưu và ph c hi ng cnh s làm lãnh phí CPU • Gi m hi u năng –Tm bng lịng vi tài nguyên (ít hơn mong mu n) – Cache khơng hi u qu • Ph c tp –S đng b hĩa, điu khi n song song, tránh deadlock, cơ ch bo v 6/17/2009 Operating System 37
Lp lch ng n hn (STS) terminated running schedule wait for event preempt created ready blocked event done 6/17/2009 Operating System 38 Lp lch ng n hn (STS) (tt) •Mu thi hành ti n trình bao gm s chuy n đi liên ti p gi a s dng CPU và ch đi IO • CPU – I/O – CPU – I/O • Các ti n trình sn sàng đ thi hành đưc lưu trong mt hàng đi sn sàng (ch y) (ready (run ) queue) • STS lp lch cho các ti n trình t hành đi sn sàng mt khi CPU chuy n sang tr ng thái rnh. 6/17/2009 Operating System 39
Lp lch Off-line vs. On-line • Thu t tốn Off-line –Ly tt c thơng tin v tt c các cơng vi c cn ph i lp lch (bi t tr ưc tươ ng lai) – Cho ra trình t đã đưc lp lch – Khơng cn cơ ch cưng ép • Thu t tốn On-line – Cơng vi c xu t hi n vào nh ng th i đim khơng th đốn tr ưc (khơng bi t tr ưc tươ ng lai). –Rt ít thơng tin 4400 –Cn cơ ch cưng ép First-Come, First-Served (FCFS) •Lp lch các cơng vi c theo th t xu t hi n ca chúng. – Off-line FCFS lp lch theo th t xu t hi n trong d li u đu vào ca nĩ • Thi hành ln lưt mi cơng vi c cho đn khi hồn thành – Nguyên th y: hồn thành k c tính I/O – Hi n đi: dng li khi b block (gp I/O) • Cĩ c on-line ln off-line • ðơ n gi n, dùng làm cơ s đ phân tích các pp khác • Th i gian ph n hi kém 6/17/2009 Operating System 41
First-Come, First-Served • Ví d: Process Burst Time P1 24 P2 3 P3 3 – VD: 3 ti n trình vào hàng đi theo th t: P1 , P2 , P3 Sơ đ Gantt: P1 P2 P3 0 24 27 30 – Th i gian ch P1 = 0; P2 = 24; P3 = 27 – Th i gian ch trung bình: (0 + 24 + 27)/3 = 17 – Th i gian hồn thành trung bình: (24 + 27 + 30)/3 = 27 • ðim yu: Các ti n trình cĩ th i gian CPU ng n vào sau ti n trình cĩ th i gian CPU dài. 4422 First-Come, First-Served • ðim yu: – Gi s vào hàng đi theo th t: P2 , P3 , P1 Sơ đ Gantt: P2 P3 P1 0 3 6 30 – Th i gian ch P1 = 6;P2 = 0 ; P3 = 3 – Th i gian ch trung bình: (6 + 0 + 3)/3 = 3 – Th i gian hồn thành trung bình: (3 + 6 + 30)/3 = 13 • Tr ưng hp 2: – Th i gian ch trung bình tt hơn (3 < 17) – Th i gian hồn thành trung bình tt hơn (13 < 27) 6/17/2009 Operating System 43
Round Robin (RR) • Mơ hình FCFS: Khơng tt cho nh ng ti n trình th i gian ng n! – Ph thu c hồn tồn vào th t • Mơ hình Round Robin –Mi ti n trình s nh n đưc mt kho ng th i gian s dng CPU khá nh (time quantum ), th ưng là 10-100 milli giây – Sau khi kho ng th i gian này kt thúc, ti n trình s b cưng ch chuy n vào hàng đi sn sàng (khơng cho dùng CPU na). – Gi s cĩ n ti n trình trong hàng đi và time quantum là q ⇒ •Mi ln ch y ti n trình s cĩ ti đa q đơ n v th i gian • Khơng cĩ ti n trình nào ph i đi quá (n-1)q đơ n v th i gian • ðánh giá hi u năng – q ln ⇒ FCFS – q nh ⇒ th i gian overhead ln khơng hi u qu 6/17/2009 Operating System 44 Round Robin (q=20) • Ví d: Process Burst Time P1 53 P2 8 P3 68 P4 24 –Sơ đ Gantt: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 28 48 68 88 108 112 125 145 153 – Th i gian ch P1=(68-20)+(112-88)=72 P2=(20-0)=20 P3=(28-0)+(88-48)+(125-108)=85 P4=(48-0)+(108-68)=88 – Th i gian ch trung bình = (72+20+85+88)/4=66¼ – Th i gian hồn thành trung bình = (125+28+153+112)/4 = 104½ • ðánh giá: –Tt cho các ti n trình cĩ th i gian CPU ng n – Thêm th i gian chuy n đi ng cnh cho các ti n trình cĩ th i gian 4455 CPU dài
Câu Hi • Ví d: Process Burst Time P1 53 P2 8 P3 68 P4 24 –Sơ đ Gantt? – Th i gian ch P1? P2 ? P3? P4? – Th i gian ch trung bình ? – Th i gian hồn thành trung bình ? • Khi dùng Round Robin vi q =40, First Come- First Service và FCFS trong tr ưng hp xu nh t vi 4 process trên. 6/17/2009 Operating System 46 So sánh FCFS và Round Robin • Gi s th i gian chuy n đi ng cnh khơng đáng k, RR hay FCFS tt hơn? • Xét ví d: 10 ti n trình, mi ti n trình s dng 100s CPU q = 1s Tt c ti n trình vào hàng đi cùng 1 th i đim • Th i gian hồn thành: P # FIFO RR 1 100 991 2 200 992 9 900 999 10 1000 1000 –C RR và FCFS đu hồn thành 10 ti n trình ti cùng 1 th i đim – Th i gian ph n hi ca RR rt t! • Khơng nên dùng trong tr ưng hp các ti n trình cĩ th i gian s dng CPU gn nhau 6/17/2009 Operating System 47
Round Robin vi q khác nhau P2 P4 P1 P3 Best FCFS: [8] [24] [53] [68] 0 8 32 85 153 Quantum P1 P2 P3 P4 Average Best FCFS 32 0 85 8 31¼ Q = 1 84 22 85 57 62 Wait Q = 5 82 20 85 58 61¼ Q = 8 80 8 85 56 57¼ Time Q = 10 82 10 85 68 61¼ Q = 20 72 20 85 88 66¼ Worst FCFS 68 145 0 121 83½ Best FCFS 85 8 153 32 69½ Q = 1 137 30 153 81 100½ Complet Q = 5 135 28 153 82 99½ ion Q = 8 133 16 153 80 95½ Time Q = 10 135 18 153 92 99½ Q = 20 125 28 153 112 104½ 6/17/2009Worst FCFS 121 Operating153 System 68 145 121¾48 S cưng ch (Pre-emptive) • S cng ch là hành đng dng mt cơng vi c đang ch y đ lp lch cho cơng vi c khác • chuy n đi ng cnh – Ví d: Ti n trình P1 đang ch y (s dng CPU) dng ti n trình P1 li (chuy n ra hàng đi ready) và giao CPU cho ti n trình P2 nào đĩ. –Lưu ý: Ti n trình P1 khơng b dng bi thao 6/17/2009tác I/O ho c các Operating s ki Systemn khác 49
S dng s cưng ch • Thu t tốn SST on-line –Tươ ng thích vi s thay đi điu ki n • Vd: cĩ cơng vi c mi –B sung cho vi c thi u thơng tin • Vd: th i gian ch y •S cưng ch theo chu kỳ giúp h th ng nm trong tm ki m sốt •Ci thi n tính cơng bng 6/17/2009 Operating System 50 Các thu t tĩan ci ti n FCFS • Xét tr ưng hp tt nh t ca FCFS: ti n trình th i gian ng n vào tr ưc, ti n trình th i gian dài vào sau • Shortest Job First (SJF) : – Ch n ti n trình cĩ th i gian ch y là ít nh t (khơng ph thu c th t vào) – Cịn gi là “Shortest Time to Completion First” (STCF) • Shortest Remaining Time First (SRTF) : – Là mt phiên bn SJF cĩ cưng ch (Preemptive version of SJF): nu cĩ ti n trình mi vào và th i gian s dng CPU ít hơn th i gian cịn li ca ti n trình đang chi m CPU thì dng ti n trình đang ch y và chuy n quy n cho ti n trình mi vào. – Cịn gi là “Shortest Remaining Time to Completion First” (SRTCF) • Ý tưng chính – Cho phép cơng vi c cĩ th i gian thi hành CPU ng n ra ngồi CPU càng nhanh càng tt –Kt qu là th i gian ph n hi trung bình s tt hơn 6/17/2009 Operating System 51
Shortest Job First (SJF) • Cơngvi c cĩ th i gian ít nh t s đưc thi hành tr ưc • ð đo th i gian phàn hi là tt nh t Long job Short Short Long job • Ch cĩ off-line –Tt c các cơng vi c và th i gian thi hành ph i đư c bi t tr ưc 6/17/2009 Operating System 52 Shortest Remaining Time first (SRT) • Bi t: th i gian thi hành cơng vi c • Khơng bi t: th i đim cơng vi c bt đu (đưc np vào hàng đi) • Khi cĩ mt cơng vi c mi: Nu th i gian thi hành ca nĩ nh hơn th i gian thi hành cịn li ca cơng vi c đang đưc thi hành hi n ti thì: cưng ch dng cơng vi c đang thi hành hi n ti và lp lch cho cơng vi c va đưc to ra Ng ưc li, ti p tc cơng vi c hi n ti và chèn cơng vi c mi vào hàng đi theo th t th i gian cịn li ph i thi hành • Khi cơng vi c hi n ti kt thúc, ch n cơng vi c 6/17/2009 Operating System 53 nm đu hàng đi đ thi hành
So sánh SJF, SRTF, FCFS, RR • SJF vs SRTF –Tt nh t đ ti thi u hĩa th i gian ph n hi trung bình. (SJF: non-preemptive, SRTF: preemptive) – SRTF ít nh t là tươ ng đươ ng vi SJF • SRTF vs FCFS và RR –Nu th i gian s dng ca các ti n trình là nh ư nhau SRTF = FCFS –Nu th i gian s dng ca các ti n trình là bi n đng ln SRTF, RR giúp cho các ti n 6/17/2009trình cĩ th i gian Operating ng nSystem khơng ch quá lâu. 54 So sánh SJF, SRTF, FCFS, RR (tt) • SRTF cĩ th làm phát sinh tr ưng hp “đĩi CPU” (starvation) cho các ti n trình cĩ th i gian s dng CPU tươ ng đi lâu – Ví d: Tr ưng hp các ti n trình cĩ th i gian s dng ng n liên tc đưc đư a vào. ti n trình cĩ th i gian s dng dài s khơng đưc phép s dng CPU tình tr ng đĩi CPU (starvation). •C 4 ph ươ ng pháp đu yêu cu ph i bi t th i gian mà mt ti n trình s dùng CPU . – Làm sao bi t? 6/17/2009 Operating System 55
So sánh SJF, SRTF, FCFS, RR (tt) • Dùng SRTF đ làm cơ s đánh giá các ph ươ ng pháp khác (vì là ph ươ ng pháp ti ưu) v th i gian ph n hi trung bình. • Ưu đim – Th i gian ph n hi trung bình ca SRTF là tt nh t. • Khuy t đim – Ph i d đốn th i gian s dng CPU ca ti n trình – Khơng cơng bng 6/17/2009 Operating System 56 D đốn th i gian s dng CPU • Yêu cu ng ưi dùng nh p vào – Khĩ kh thi: ng ưi dùng khơng bi t – Ng ưi dùng cĩ th đư a vào th i gian thi hành ng n đ mong kt thúc cơng vi c sm • Adaptive (thích ng): D đốn tươ ng lai bng cách quan sát quá kh . –Nu trong quá kh ti n trình (ch ươ ng trình) th ưng dùng CPU nhi u (CPU-bound) thì cĩ th trong tươ ng lai nĩ s s dng nhi u. –Nu trong quá kh ti n trình (ch ươ ng trình) th ưng thao tác I/O (I/O bound) thì cĩ th trong tươ ng lai nĩ s s dng CPU ít. 6/17/2009 Operating System 57
D đốn th i gian s dng CPU (tt) •Gi ti là th i gian s dng CPU ti ln th i. • Ý tưng th i gian s dng CPU ti ln th n là: – Tn = f(t n-1, t n-2, ) α α α∈ – Tn = tn-1 + (1- )T n-1 ( [0,1] ) 6/17/2009 Operating System 58 Hàng đi ph n hi đa mc (Multilevel feedback queues) new jobs terminated quantum=10 quantum=20 quantum=40 FCFS 6/17/2009 Operating System 59
Multilevel feedback queues • ð ưu tiên đưc ng m đnh trong mơ hình này •Rt linh ho t • Tình tr ng đĩi CPU cĩ th cĩ Nhi u cơng vi c ng n vào => cơng vi c dài s b “đĩi” • Gi i pháp: – ð nguyên – Lão hĩa (aging) 6/17/2009 Operating System 60 FCFS Hi n ði •Mt ti n trình s ch m dt ho t đng và chuy n sang tr ng thái mi khi ht th i gian ho c đn th i đim truy xu t. • Ví d cho 2 ti n trình A(10,2,2) (th i gian ho t đng là 10, th i đim bt đu IO là 2 sau khi bt đu ti n trình; trong đĩ th i gian IO là 2) và B(8,2,2). Hi A B tr ng thái nào theo FCFS lúc 9,32? • A running và B ready 1 2 3 4 5 6 7 8 9 10 AR AR AIO AIO AR AR AR AR AR AR BR BR BIO BIO 6/17/2009 Operating System 61
Round Robin Hi n ði •Ti th i đim m cĩ 2 ti n trình: A running xong q và B IO xong thì th t đư a vào hàng đi là B tr ưc A sau . •Ti th i đim m A running xong q và A đn th i đim bt đu IO thì th i đim IO s đư a vào chu kỳ sau . • Ví d cho 2 ti n trình A(10,2,2) (th i gian 10 ho t đng, th i đim bt đu IO là 2 sau khi bt đu ti n trình; trong đĩ th i gian IO là 2 và bt đu IO) và B(9,3,2). Hi A B tr ng thái nào theo RR vi q=2 lúc 9,82? 6/17/2009 Operating System 62 A running xong q và B IO xong thì th t đư a vào hàng đi là B tr ưc A sau. A running xong q và A đn th i đim bt đu IO thì th i đim IO s đư a vào chu kỳ sau. Ví d A(10,2,2) và B(9,3,2). Tr ng thái nào theo RR vi q=2 lúc 9,82? B running và A ready 1 2 3 4 5 6 7 8 9 10 AR AR AIO AIO AR AR AR BR BR BR BIO BIO BR BR 63
Tĩm tt • Ti n trình = mt th hi n ca vi c thi hành mt ch ươ ng trình. • ða ch ươ ng = nhi u ti n trình cĩ th cùng đưc thi hành. Ti mi th i đim ch cĩ mt ti n trình tr ng thái đưc thi hành. •Lp lch = quy t đnh ti n trình nào s đưc chuy n tr ng thái t sn sàng sang ch y. 6/17/2009 Operating System 64 Tĩm tt (tt) • FCFS: Vào tr ưc s đưc cp phát CPU tr ưc – Ưu: đơ n gi n – Khuy t: ti n trình ng n s ch ti n trình dài. • Round Robin: Cp mi ti n trình mt kho ng th i gian đnh tr ưc (quantumn) khi nĩ nh n đưc CPU. – Ưu: Các ti n trình ng n s kt thúc nhanh chĩng – Khuy t: ti n trình cĩ th i gian s dng CPU gn nhau khơng hi u qu . 6/17/2009 Operating System 65
Tĩm tt • SJF/SRTF: Cp phát cho ti n trình cĩ th i gian thi hành/th i gian cịn li là ít nh t. – Ưu: th i gian ph n hi trung bình là tt nh t. – Khuy t: khĩ d đốn th i gian s dng CPU, khơng cơng bng. • Multi-level feedback: s dng nhi u hàng đi vi đ ưu tiên khác nhau. T đng chuy n đi mc đ ưu tiên ca các ti n trình. 6/17/2009 Operating System 66 Câu Hi • 1/ Cho A (10,0,4) B(8,2,1) và C(9,1,2). Hi khi T=11,32 thì A B C tr ng thái nào theo FCFS. • 2/ Cho A (10,1,2) B(10,3,2) và C(10,0,2). Hi khi T=9,82 thì A B C tr ng thái nào theo RR vi q=2. • 3/ Bài tp v nhà:vi t ch ươ ng trình input vào s ti n trình, thơng tin ca tng ti n trình. Output ra tr ng thái ca các ti n trình ti th i đim bt kỳ v sơ đ. 6/17/2009 Operating System 67
Giao ti p gi a các ti n trình 1-23, 38 86 1 Ni dung •Tng quan v giao ti p ti n trình (ti u trình) •Vn đ Producer/Consumer (s n xu t / tiêu th ) • Mi n g ăng • ðng b bng gi i pháp ph n c ng • Semaphores • Monitors • Truy n thơng đip • Các bài tốn c đin v đng b hĩa 2
Tng quan v giao ti p ti n trình • Ti n trình đc l p khơng nh h ưng và khơng b nh h ưng b i vi c th c thi c a các ti n trình khác. • Ti n trình h p tác (khơng đc l p) cĩ th nh hưng và b nh h ưng b i vi c th c thi c a các ti n trình khác. • Ưu đim c a vi c h p tác ti n trình: – Chia s thơng tin –Tăng t c tính tốn (x lý song song): th i gian I/O và th i gian CPU – Tính module hĩa – Ti n l i 3 Hp tác b ng vi c chia s • Các ti n trình s dng và cp nh p d li u chia s như c ác bi n, file và cơ s d li u dùng chung. • Thao tác ghi ph i đc l p t ng đơi m t đ ng ăn ng a tình tr ng đng đ, cĩ th dn đn tính khơng tồn v n d li u. • Các mi n g ăng dùng đ cung c p s tồn vn d li u. •Mt ti n trình địi h i mi n g ăng ph i khơng b ch mãi mãi: deadlock ho c starvation. 4
Hp tác b ng vi c giao ti p • Giao ti p cung c p ph ươ ng cách đ đng b hĩa nhi u ho t đng. • Cĩ kh năng deadlock –Mi ti n trình đu ch thơng đip t mt ti n trình khác. • Cĩ kh năng xy ra tình tr ng đĩi (starvation) – Hai ti n trình g i thơng đip cho nhau trong khi m t ti n trình khác ch thơng đip. 5 Ví d 1: h p tác ti u trình • Các ti u trình đc l p: Thread A Thread B x = 1; y = 2; • Các ti u trình cĩ hp tác v i nhau (y=0): Thread A Thread B x = 1; y = 2; x = y+1; y = y*2; – x=? •Mt cách đơ n gi n: x = bao nhiêu trong ví d sau Thread A Thread B x = 1; x = 2; 6
Khái ni m c ơ b n trong đng b hĩa • Thao tác nguyên t (Atomic Operation) : là thao tác mt khi ch y là luơn luơn hồn thành , khơng b ct ngang n a ch ng . – Là khái ni m c ơ b n đ to nên nguyên lý l p trình đa ch ươ ng – Ví d: phép load, store là thao tác nguyên t – Ví d: phép nhân 3*4.5 ??? • Lưu ý: Trong các bài tốn đng b hĩa, cn chú ý r ng m t ti u trình (ti n trình) cĩ th b ng t t i b t c th i đim nào. 7 Ví d 2: đng b hĩa ti n trình • Gi s cĩ 2 ti u trình: Thread A Thread B r1=0 load r1, M[i] r1=0 load r1, M[i] r1=1 add r1, r1, 1 r1=-1 sub r1, r1, 1 M[i]=1 store r1, M[i] M[i]=-1store r1, M[i] •Vn đ: 8
Vn đ ca đng b hĩa • Ti n trình (ti u trình) cĩ th b ly l i CPU bt c lúc nào (b cưng ch ho c khơng b cưng ch ). •D li u (bi n) cĩ th đưc chia s bi nhi u ti n trình (ti u trình) – Khơng b o đm s tồn v n d li u – Giá tr ca các bi n dùng chung khơng th đnh tr ưc, ph thu c vào quá trình th c thi ca các ti n trình. 9 Ví d 3: Mua s a Th i đim Ch ng V 3:00 Nhìn vào t lnh. Th y ht s a cho con 3:05 ði ra c a hàng 3:10 ðn c a hàng Nhìn vào t lnh. Th y ht s a cho con 3:15 Mua s a cho con ði ra c a hàng 3:20 Mang s a v b trong ðn c a hàng t 3:25 Mua s a cho con 3:30 Mang s a v b trong t 10
Mt vài khái ni m • ðng đ (Race condition) : tình hu ng mà nhi u ti n trình (ti u trình) cùng truy c p và thao tác d li u chia s mt cách đng th i. Giá tr d li u cu i cùng ph thu c vào s luân phiên thi hành c a các ti n trình. • Gi i quy t đng đ đng b hĩa 11 Mt vài khái ni m • ðng b hĩa (synchronization) : là cơng vi c s dng các thao tác nguyên t đ bo đm s hp tác gi a các ti n trình đt đưc kt qu mong mu n. • Lo i tr h t ng (đc quy n truy xu t) (mutual exclusion) : bo đm rng ch cĩ mt ti u trình (ti n trình) đưc quy n thao tác ti mt vùng nh ti mt th i đim. – Lo i tr các ti n trình khác làm vi c nh ư mình • Mi n găng (critical section) : đon mã ch cho phép mt ti u trình (ti n trình) thi hành ti mt th i đim. – Ti u trình (ti n trình) đưc gi là đi vào mi n găng. – Lo i tr h tươ ng và mi n găng là hai khái ni m cùng mt mc đích. 12
Gi i pháp 1 cho vi c mua sa • ðư a ra mt qui đnh (dùng mi ng gi y thơng báo): – Tr ưc khi đi mua sa dán mi ng gi y thơng báo – Mua sa v g b mi ng gi y thơng báo –Nu th y mi ng gi y thì khơng cn ph i đi mua (ch ) • ðư a cho máy tính th c hi n if (noMilk) { if (noNote) { leave Note; buy Milk; remove Note; } } 13 Gi i pháp 1 cho vi c mua sa if (noMilk) { if (noMilk) { if (noNote) { if (noNote) { leave Note; leave Note; buy Milk; buy Milk; remove Note; remove Note; } } } } vn cĩ kh năng sai 14
Gi i pháp 2 cho vi c mua sa • Gi i pháp 1 cĩ v “dán gi y thơng báo” quá tr Thread A Thread B leave note A; leave note B; if (noNote B) { if (noNoteA) { if (noMilk) { if (noMilk) { buy Milk; buy Milk; } } } } remove note A; remove note B; cĩ kh năng c hai ng ưi khơng ai đi mua sa 15 Gi i pháp 3 cho vi c mua sa Thread A Thread B leave note A; leave note B; while (note B) { if (noNote A) { do nothing; if (noMilk) { } buy milk; if (noMilk) { } buy milk; } } remove note B; remove note A; • A: nu th y B đã dán gi y thì ch (vịng while), ng ưc li mua sa. • B: nu th y A đã dán gi y thì g b gi y báo ca mình, nh ưng cho A mua. Ng ưc li thì đi mua. 16
Phân tích gi i pháp 3 if (noMilk) { buy milk; } đưc gi là mi n găng. Mc đích ca c 3 gi i pháp là bo v mi n găng này. Ti mt th i đim bt kỳ ch cĩ th cĩ nhi u nh t là mt ti n trình, ti u trình vào mi n găng. Phân tích •Rt ph c tp dù ví d rt đơ n gi n • ðon mã ca A và B khác nhau dù hai ng ưi cùng làm mt vi c. Nu cĩ rt nhi u ti u trình thì sao??? • Trong khi A ch đi, nĩ vn s dng CPU busy- waiting 17 Mi n găng (critical section) •Lp trình đa ch ươ ng cho phép song song theo lý thuy t đ s dng các thi t b hi u qu hơn. Nh ưng chúng ta đã tr giá bi tính đúng đn khơng cịn. • Do đĩ ch p nh n g b tính song song tính đúng đn 18
Vn đ mi n găng • n ti n trình đu tranh vi nhau đ s dng mt s d li u nào đĩ. •Mi ti n trình cĩ mt đon mã, gi là mi n găng (critical section (CS) ), ti đĩ d li u chia s đưc truy cp. •Vn đ: bo đm rng khi mt ti n trình đang th c thi trong mi n găng ca nĩ, khơng cĩ ti n trình nào khác đưc quy n th c thi trong mi n găng ca nĩ. 19 Ng cnh mi n găng (1) • Khi mt ti n trình thi hành đon mã thao tác trên d li u chia s (hay tài nguyên), chúng ta nĩi rng ti n trình đĩ đang trong mi n găng ca nĩ. • Vi c th c thi các mi n găng ph i cĩ tính duy nh t: ti bt kỳ th i đim nào, ch cĩ duy nh t mt ti n trình đưc quy n th c thi trong mi n găng ca nĩ (ngay c vi nhi u b x lý). • Vì vy mi ti n trình ph i yêu cu quy n tr ưc khi vào mi n găng. 20
Ng cnh mi n găng (2) • ðon mã th hi n yêu cu này đưc gi làEntry Section (ES). • Mi n găng (CS) cĩ th theo sau là Leave/Exit Section (LS). • Ph n đon mã cịn li là Remainder Section (RS). •Vn đ ca mi n găng là thi t k mt giao th c mà các ti n trình cĩ th s dng đ hành đng ca chúng s khơng ph thu c vào th t mà s thi hành ca chúng đưc chen vào. 21 Ng cnh mi n găng (3) repeat • Gi i pháp = cn entry section ph i ch ra các lnh critical section exit section đưc th c thi ca remainder section entry section và forever exit section • Khơng cĩ bt c s gi s nào v tc đ CPU và th t thi hành ca các ti n trình 22
Gi i pháp cho vn đ mi n găng • Cĩ 3 yêu cu mà mt gi i pháp đúng cn ph i th a mãn: 1. Mutual Exclusion : khơng cĩ 2 ti n trình cùng trong mi n găng mt lúc 2. Progress : Mt ti n trình bên ngồi mi n găng khơng đưc ng ăn cn các ti n trình khác vào mi n găng 3. Bounded Waiting : khơng cĩ ti n trình nào ph i ch vơ hn đ vào mi n găng • Ch cn mt trong ba điu ki n trên sai thì gi i pháp đư a ra là sai. 23 Phân lo i các gi i pháp cho CS • Gi i pháp ph n mm – Các thu t tốn mà tính đúng đn ca nĩ khơng da trên bt kỳ mt gi thuy t nào khác. • Gi i pháp ph n cng –Da trên các mã lnh máy đc bi t. • Gi i pháp HðH – Cung cp các hàm và cu trúc d li u cho lp trình viên thơng qua li gi h th ng. • Gi i pháp ngơn ng lp trình – – Là mt ph n ca ngơn ng . 24
Gi i pháp ph n mm • Xét tr ưng hp cĩ 2 ti n trình: – Thu t tốn 1, 2, 3 sai. – Thu t tốn 4 đúng (Peterson’s algorithm). •Tng quát hĩa cho tr ưng hp n ti n trình: – Thu t tốn Bakery. • Qui ưc: – 2 ti n trình: P0 và P1 – Ho c Pi, Pj – Ho c Larry và Jim 25 Cu trúc ca các ti n trình •Cu trúc tng quát ca ti n trình Pi (Pj) do { entry section critical section leave section remainder section } while (1) ; •Lưu ý: Các ti n trình cĩ th chia s các bi n dùng chung đ đng b hĩa ho t đng ca chúng. 26
Thu t tốn 1 • Ý tưng: s dng mt bi n luân phiên . – Bi n luân phiên mang giá tr nào thì ti n trình tươ ng ng đưc phép vào mi n găng. – Sau khi ra kh i mi n găng thì đt giá tr bi n luân phiên cho phép ti n trình cịn li vào mi n găng. 27 Thu t tốn 1- Larry/Jim version • Bi n dùng chung: – string turn ; kh i to turn = “Larry” ho c “Jim” – turn = “Larry” ⇒ Larry cĩ th vào trong mi n găng • Ti n trình Larry do { while (turn != “Larry”); critical section turn =“Jim”; remainder section } while (1) ; • Ti n trình Jim tươ ng t nh ưng hốn đi Larry và Jim. 28
Thu t tốn 1- Pi/Pj version • Bi n dùng chung: – int turn ; kh i to turn = 0 ⇒ – turn = i Pi cĩ th vào mi n găng • Ti n trình Pi do { while (turn != i) ; critical section turn = j ; remainder section } while (1) ; • Th a “mutual exclusion” và “bounded waiting”, nh ưng khơng th a “progress” (??? ). 29 Thu t tốn 1: khơng th a tính progress • Gi s Pi vào mi n găng đưc (turn = i). •Pi ra kh i mi n găng nh ưng quy n vào mi n găng cho Pj turn = j • Xét tr ưng hp Pj khơng thích vào mi n găng (do bn x lý mt vi c gì đĩ) và Pi mu n vào mi n găng tr li. Nh ưng turn = j Pi khơng vào mi n găng đưc. • Pj ngịai mi n găng nh ưng đã ng ăn cn khơng cho Pi vào mi n găng 30
Thu t tốn 2 • Ý tưng: dùng hai bi n cho hai ti n trình –Mt ti n trình A tr ưc khi vào mi n găng cn bo đm ti n trình B cịn li khơng mu n vào mi n găng. –Nu ti n trình B khơng mu n vào mi n găng, thì ti n trình A đt c báo hi u nĩ mu n vào mi n găng. Ng ưc li ph i ch . – Khi ra kh i mi n găng, ti n trình A đt giá tr bi n báo hi u cho bi n là nĩ khơng mu n vào mi n găng na 31 Thu t tốn 2 - Larry/Jim version • Bi n dùng chung – boolean flag-larry, flag-jim ; kh i to flag-larry = flag-jim = false – flag-larry= true ⇒ Larry sn sàng đ vào mi n găng • Ti n trình Larry do { while (flag-jim); flag-larry = true; critical section flag-larry = false; remainder section } while (1); 32
Thu t tốn 2 - Pi/Pj version • Bi n dùng chung – boolean flag[2] ; kh i to flag [0] = flag [1] = false ⇒ – flag [i] = true Pi sn sàng vào mi n găng • Ti n trình Pi do { while (flag[j]); flag[i] = true; critical section flag [i] = false; remainder section } while (1); • Th a mãn tính “progress”, nh ưng khơng th a mãn “mutual exclusion” và “bounded waiting”(??? ). 33 Thu t tốn 2: khơng th a mãn mutual exclusion Ti n trình 1: Ti n trình 2: do { do { while (flag-jim); while (flag-larry); flag-larry = true; critical section flag-jim = true; flag-larry = false; critical section remainder flag-jim = false; section } while (1); remainder section } while (1); 34
Thu t tốn 3 • Ý tưng: dùng hai bi n nh ư thu t tốn 2 nh ưng th hi n mong mu n vào mi n găng tr ưc khi quan tâm đn mong mu n ca ti n trình khác. – Nh m lo i b s vi ph m mutual exclusion 35 Thu t tốn 3 - Larry/Jim version • Bi n dùng chung – boolean flag-larry, flag-jim ; kh i to flag-larry = flag-jim = false – flag-larry= true ⇒ Larry sn sàng vào mi n găng • Ti n trình Larry do { flag-larry = true; while (flag-jim); critical section flag-larry = false; remainder section } while (1); 36
Thu t tốn 3 - Pi/Pj version • Bi n dùng chung – boolean flag[2] ; kh i to flag [0] = flag [1] = false ⇒ – flag [i] = true Pi mu n vào mi n găng • Ti n trình Pi do { flag[i] = true; while (flag[j]); critical section flag [i] = false; remainder section } while (1); • Th a mãn “mutual exclusion”, nh ưng khơng th a mãn “progress” và “bounded waiting”(??? ). 37 Thu t tốn 4 • Ý tưng: kt hp ý tưng ca thu t tốn 1, 2 và 3. Dùng mt bi n luân phiên và hai bi n đi di n cho hai ti n trình. – Th hi n mong mu n vào mi n găng ca mình tr ưc (đt giá tr tươ ng ng vi ti n trình) – Nh ưng quy n vào mi n găng cho ti n trình cịn li (đt giá tr bi n luân phiên) –Mt ti n trình ch đưc vào mi n găng khi cĩ mong mu n vào mi n găng và đn lưt mình 38 đưc vào mi n găng.
Thu t tốn 4 - Larry/Jim version •Kt hp bi n dùng chung ca thu t tốn 1 và 2/3. • Ti n trình Larry do { flag-larry = true; turn = “Jim”; while (flag-jim and turn = “Jim”); critical section flag-larry = false; remainder section } while (1); 39 Thu t tốn 4 - Pi/Pj version •Kt hp bi n dùng chung ca thu t tốn 1 và 2/3. • Ti n trình Pi do { flag [i]:= true; turn = j; while (flag [j] and turn = j); critical section flag [i] = false; remainder section } while (1); • Th a mãn c ba điu ki n gi i quy t vn đ mi n găng cho 2 ti n trình. 40
Thu t tốn 5 - Larry/Jim version • Nh ư thu t tốn 4, nh ưng hốn đi 2 câu lnh đu tiên cho nhau. • Ti n trình Larry do { turn = “Jim”; flag-larry = true; while (flag-jim and turn = “Jim”); critical section flag-larry = false; remainder section }while (1); 41 Thu t tốn Bakery • Mi n găng vi n ti n trình tranh ch p: • Tr ưc khi vào mi n găng, ti n trình nh n mt con s. Ti n trình cĩ con s nh nh t đưc vào mi n găng. •Nu hai ti n trình Pi và Pj nh n cùng mt s thì nu i < j, thì Pi đưc vào tr ưc, ng ưc li Pj đưc vào tr ưc. •B to s luơn to ra các con s theo th t tăng: 1,2,3,3,3,3,4,5 42
Thu t tốn Bakery • Ch n mt s: – max ( a0, , an-1) • Th t t vng (ticket #, PID #) –(a,b ) < ( c,d ) nu a < c ho c nu a = c và b < d •D li u dùng chung: boolean choosing[n]; int number[n]; Cu trúc d li u đưc kh i to bng false và 0. 43 Thu t tốn Bakery do { choosing[i] = true; number[i] = max(number[0], , number[n – 1]) +1; choosing[i] = false; for (j = 0; j < n; j++) { while (choosing[j]) ; while ((number[j]!=0) && ((number[j],j)<(number[i],i)) ; } critical section number[i] = 0; remainder section } while (1); 44
Ti n trình b li? •Nu c 3 điu ki n (ME, progress, bounded waiting) đu đưc th a thì mt gi i pháp hp l s khơng b nh hưng trong tr ưng hp ph n RS b li. • Tuy nhiên trong tr ưng hp nu li xy ra đúng trong mi n găng thì nĩ s chi m mi n găng vĩnh vi n. 45 Khuy t đim ca gi i pháp ph n mm • Gi i pháp ph n mm d b đ v. • Ti n trình đang yêu cu vào mi n găng tr ng thái “busy waiting” (vn tiêu tn CPU). •Nu mi n găng dài, s hi u qu hơn nu block các ti n trình đang ch . 46
Gi i pháp ph n cng: cm ng t • Khi trong mi n găng, các ti n trình khác khơng đưc chen Process Pi: repeat ngang vào mi n găng. disable interrupts critical section enable interrupts remainder section forever 47 Các ch th ph n cng đc bi t • Truy xu t đn mt vùng nh s khơng cho phép các ti n trình khác truy xu t vào cùng đa ch . •M rng: cung cp hai ch th nguyên t đ thi hành thao tác đc ghi trên cùng mt vùng nh . •S thi hành ca ch th này th a mãn “mutually exclusive”. •Cn b sung thêm cơ ch khác đ th a mãn 2 tính ch t cịn li. 48
Ch th test-và-set • Thu t tốn s dng testset cho • Mơ t trong Mutual Exclusion: – Bi n dùng chung b đưc kh i C++: to v 0 bool testset(int& i) – Ch duy nh t ti n trình Pi đt b=1 đưc vào CS { Process Pi: if (i==0) { repeat i=1; repeat{} return true; until testset(b); } else { CS return false; b:=0; } RS } forever 49 TestAndSet trong ph n cng • Ki m tra và thay đi ni dung ca mt word mt cách khơng th phân chia: boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; } 50
Mutual Exclusion vi TestAndSet • Bi n dùng chung: boolean lock = false; • Ti n trình Pi do { while (TestAndSet(lock)) ; critical section lock = false; remainder section } 51 Swap trong ph n cng • Hốn đi hai bi n (khơng th phân chia). void Swap(boolean &a, boolean &b) { boolean temp = a; a = b; b = temp; } 52
Mutual Exclusion vi Swap Bi n dùng chung: boolean lock = false; • Ti n trình Pi do { key = true; while (key == true) Swap(lock,key); critical section lock = false; remainder section } 53 Semaphores (1) • Là mt cơng c đng b hĩa đưc cung cp bi HðH khơng địi hi “busy waiting”. •Mt semaphore S là mt bi n nguyên mà ngồi lnh kh i to ra, ch cĩ th đưc truy xu t thơng qua hai thao tác đc quy n truy xu t và nguyên t: –wait(S) –signal(S) 54
CS vi n ti n trình •D li u dùng chung: semaphore mutex; // kh i to mutex = 1 • Ti n trình Pi: do { wait(mutex); critical section signal(mutex); remainder section } while (1); 55 Semaphores (2) • Truy cp vi 2 thao tác wait (S): while S≤≤≤ 0 do no-op ; S ; signal (S): S++; • ð tránh “busy waiting”: khi mt ti n trình ph i đi, nĩ s đưc đt vào hàng đi block. 56
Semaphores (3) • Semaphore bn ch t là mt cu trúc: type semaphore = record count: integer; queue: list of process end; var S: semaphore; • Khi mt ti n trình ph i đi mt semaphore S, nĩ s b block và đt vào hàng đi ca semaphore tươ ng ng. • Thao tác signal ly mt ti n trình t trong hàng đi và đt nĩ vào trong danh sách các ti n trình tr ng thái sn sàng. 57 Thao tác trên Semaphore wait(S): S.count ; if (S.count<0) { block this process place this process in S.queue } signal(S): S.count++; if (S.count<=0) { remove a process P from S.queue place this process P on ready list } 58
Cài đt semaphore (1) • ðnh ngh ĩa cu trúc: typedef struct { int value; struct process *L; } semaphore; • Gi s cĩ 2 thao tác cơ bn: – Block tm cho ti n trình ch . – wakeup( P) khơi ph c li s thi hành ca ti n trình b block P. 59 Cài đt semaphore • wait (S): S.value ; if (S.value < 0) { add this process to S.L; block; } signal (S): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } 60
Cơng c đng b hĩa ti n trình • B đưc thi hành sau A. • Dùng semaphore flag kh i to ban đu bng 0 • Mã: Pi Pj MM A wait (flag ) signal (flag ) B 61 Deadlock và Starvation • Deadlock: –Gi S và Q là hai semaphore đưc kh i to 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); MM signal (S); signal (Q); signal (Q) signal (S); • Starvation : khơng đưc ly ra kh i hàng đi block ca semaphore 62
Ưu khuy t đim ca Semaphore • Semaphore cung cp mt cơng c mnh m đ h tr cơ ch đc quy n truy xu t và đng b hĩa các ti n trình. • Tuy nhiên wait(S) và signal(S) nm ri rác các ti n trình. Vì vy, khĩ đ hi u ý ngh ĩa ca nĩ. •S dng ph i đúng trong tt c các process. •Mt ti n trình s dng khơng đúng s nh hưng đn các ti n trình khác. 63 • Vai trị lp trình viên nng n Monitors (1) • ðnh ngh ĩa tng quan: – Monitor là mt cu thành ca ngơn ng cp cao cung cp các ch c năng tươ ng đươ ng nh ư semaphore nh ưng d điu khi n hơn. – Monitor là mt cu thành ca ngơn ng cp cao h tr điu khi n truy cp đn d li u chia s. •Mt s ngơn ng h tr : • Concurrent Pascal, Modula-3, uC++, Java • Cĩ th đưc cài đt bng semaphore. 64
Monitors (2) • Monitor là mt module ph n mm ch a: –Mt hay nhi u th tc (thao tác) –Mt đon mã kh i to – Các bi n cc b • Tính ch t: – Các bi n cc b ch cĩ th đưc truy cp bi các th tc ca monitor. –Mt ti n trình vào monitor bng cách gi mt th tc ca nĩ. –Ti mt th i đim bt kỳ, ch cĩ duy nh t mt ti n trình cĩ th trong monitor. 65 Cu trúc monitor monitor monitor-name { shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } . . . procedure body Pn ( ) { . . . } . . . { initialization code } } 66
Mơ hình ca monitor 67 Các đc tr ưng ca monitor • Monitor bo đm s đc quy n, khơng cn ph i lp trình rõ ràng nh ư các ph ươ ng pháp khác. • Vì vy, d li u dùng chung đưc bo v bng cách đt nĩ vào trong monitor. • Cĩ th đng b hĩa các ti n trình bng cách s dng các bi n điu ki n đ bi u di n các điu ki n mà mt ti n trình cĩ th ph i ch tr ưc khi đưc thi hành trong monitor. 68
Monitor cĩ bi n điu ki n 69 ðiu ki n trong monitor (1) • ð cho phép mt ti n trình ch trong monitor, mt bi n điu kien ph i đưc khai báo, ví d: condition x, y; • Các bi n điu ki n ch cĩ th đưc truy xu t bên trong monitor. • Các bi n điu ki n ch cĩ th đưc s dng vi 2 thao tác cwait và csignal thi hành trên mt hàng đi đi kèm. 70
ðiu ki n trong monitor (2) • Thao tác cwait và csignal : –Li gi x.cwait(); or cwait(x); ngh ĩa rng ti n trình gi nĩ s b treo co đn khi ti n trình khác đánh th c. x.csignal(); or csignal(x); – Thao tác csignal khơi ph c mt và ch mt ti n trình b treo. Nu khơng cĩ ti n trình nào đang b treo, thì thao tác csignal khơng cĩ ý ngh ĩa. 71 Ng cnh c a monitor • Ch đi các ti n trình t hàng đi vào ho c hàng đi điu ki n. •Mt ti n trình t đt nĩ vào hàng đi cn bng li gi cwait(cn). • csignal(cn) ly ra mt ti n trình trong hàng đi điu ki n cn và đư a vào thi hành trong monitor. • Do đĩ csignal(cn) khĩa ti n trình đang gi nĩ và đt vào hàng đi kh n cp(tr khi csignal là thao 72 tác cu i).
Khuy t đim c a semaphore và monitor •S dng bi n dùng chung đ xác l p đc quy n truy xu t ho c đng b hĩa. • Trong m t h phân tán ho c mơi tr ưng mng, m i ti n trình cĩ mt khơng gian b nh riêng khơng th dùng chung bi n (b nh ) 73 Truy n thơng đip (messaging) • Cơng d ng: – Cho phép các ti n trình liên l c v i nhau mà khơng c n ph i cĩ các bi n dùng chung. • Hai thao tác nguyên t cơ bn: – send (destination, message ) ho c send (message ) – receive (source, message ) ho c receive (message ) • Kích th ưc c a thơng đip cĩ th c đnh 74 ho c linh ho t
Truy n thơng đip (2) • Tr ưng h p s dng: – Gi a các ti n trình trong cùng m t máy. – Gi a các ti n trình trong m ng ho c m t h phân tán. • Trong c hai trưng h p, ti n trình cĩ th ho c b khĩa ho c khơng b khĩa khi truy n ho c nh n thơng đip. 75 Truy n thơng đip (3) • Vì vy vi c truy n thơng đip cĩ th b khĩa ho c khơng b khĩa: –Nu b khĩa đng b (synchronous). –Nu khơng b khĩa khơng đng b (asynchronous ). • Thao tác send và receive cĩ th b khĩa ho c khơng b khĩa. 76
ðng b hĩa trong truy n thơng đip •Vi bên g i: t nhiên hơn nu khơng b khĩa sau khi g i: – Cĩ th gi nhi u thơng đip đn nhi u đa ch . – Nh ưng th ưng là mong đi s ph n h i t phía ng ưi nh n (tr ưng h p g i sai). •Vi bên nh n: t nhiên hơn nu b khĩa sau khi báo ch nh n: – Bên nh n th ưng c n thơng tin tr ưc khi ti p tc x lý . – Nh ưng cĩ th b khĩa v ĩnh vi n n u bên g i khơng th gi (b li). 77 Các cách truy n thơng đip • Truy n tr c ti p (direct communication): – Tên c a ti n trình đưc dùng cho đa ch ngu n và đa ch đích. • Truy n gián ti p: – Các thơng đip đưc g i đn m t “hp th ư” chung ch a m t hàng đi các thơng đip. – Bên g i đt thơng đip vào trong h p th ư, và bên nh n l y thơng đip t trong h p th ư đĩ ra. 78
Truy n tr c ti p • Các ti n trình ph i bi t rõ l n nhau: – send (P, message ) – gi m t thơng đip đn ti n trình P – receive (Q, message ) – nh n m t thơng đip t ti n trình Q • Tính ch t c a đưng truy n: – ðưc t đng t o. –Mt đưng truy n đưc liên k t v i duy nh t mt c p ti n trình đang trao đi thơng tin. –Mi c p cĩ đúng m t đưng truy n. – Cĩ th là mt chi u ho c hai chi u. 79 Truy n gián ti p • Các thơng đip đưc đư a vào và ly ra t trong hp th ư (cịn g i là cng – port) –Mi h p th ư cĩ mt id duy nh t. – Các ti n trình ch cĩ th liên l c v i nhau n u chúng chia s vi nhau m t h p th ư. • Tính ch t c a đưng truy n – ðưng truy n ch đưc thành l p khơng chúng chia s vi nhau m t h p th ư dùng chung. –Mt đưng truy n cĩ th đưc s dng b i nhi u ti n trình. –Mi c p ti n trình cĩ th cĩ nhi u đưng truy n. 80 – Cĩ th mt chi u ho c hai chi u.
Truy n gián ti p (2) • Thao tác –To m t h p th ư m i –Gi và nh n thơng đip qua h p th ư –Hy h p th ư • Các thao tác nguyên t : send (A, message ) – gi m t thơng đip đn h p th ư A. receive (A, message ) – nh n m t thơng đip t hp th ư A. 81 Truy n gián ti p (3) • Chia s hp th ư – P1, P 2, và P3 dùng chung h p th ư A. – P1 gi; P2 và P3 nh n. – Ai l y đưc th ư? • Gi i pháp cĩ th : – Cho phép m i đưng truy n ch cĩ đúng 2 ti n trình. – Cho phép t i m i th i đim ch cĩ mt ti n trình đưc th c hi n thao tác nh n. – Cho phép ng u nhiên ch n bên nh n và thơng báo cho bên g i bi t ai đã nh n. 82
Hp th ư và cng •Mt h p th ư cĩ th đưc dùng b i 2 ti n trình. •Mt h p th ư cĩ th đưc chia s gi a nhi u bên gi và bên nh n: •Cng là mt h p th ư liên kt m t bên nh n và nhi u bên g i – Dùng trong ng d ng client/server: server chính là bên nh n. 83 Mutual Exclusion v i truy n thơng đip •To m t h p th ư mutex Process Pi: dùng b i n ti n trình. var msg: message; • send() khơng b khĩa. repeat receive(mutex,msg); • receive() b khĩa khi CS mutex rng. send(mutex,msg); • Kh i t o: send( mutex , RS “go”); forever • Ti n trình Pi đu tiên thi hành receive() s vào trong mi n g ăng. Các ti n trình khác b khĩa đn khi ti n trình trên 84 kt th úc.
Các bài tốn c đin v đng b hĩa • Bài tốn Producer – Consumer • Bài tốn Readers – Writers • Bài tốn Tri t gia dùng b a 85 Bài tốn Producer – Consumer • Ti n trình s n xu t s n xu t thơng tin đưc tiêu th bi ti n trình tiêu th . •Ti b t c th i đim nào, m t ti n trình s n xu t cĩ th to d li u nào đĩ. •Ti b t c th i đim nào, m t ti n trình tiêu th cĩ th mu n l y m t s d li u nào đĩ. •D li u đưc l ưu vào trong b đm. •Nu vùng đm là hu h n, nhà sn xu t s b “khĩa” nu d li u m i s làm tràn b đm. •Nu vùng đm r ng, nhà tiêu th s b khĩa khi nĩ cn d li u. 86
Phân tích • Cĩ 3 v n đ cn đng b – Truy xu t đc quy n (Mutual Exclusion) – Khi đy thì khơng đưc s n xu t thêm – Khi r ng thì khơng đưc tiêu th thêm 87 Gi i pháp v i semaphore •Cn 3 semaphore – Mutex đ truy xu t đc quy n – Full đ ki m sốt đy – Empty đ ki m sốt r ng 88
Gi i pháp v i Semaphore (2) •D li u dùng chung semaphore full, empty, mutex; nextp, nextc; // con tr đ thêm vào, l y ra • Kh i t o: full = 0, empty = n, mutex = 1 89 Ti n trình Producer do { produce an item in nextp wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); } while (1); 90
Ti n trình Consumer do { wait(full) wait(mutex); remove an item from buffer to nextc signal(mutex); signal(empty); consume the item in nextc } while (1); 91 • Câu h i: – ðiu gì xy ra n u đo 2 câu l nh wait c a 1 trong 2 ti n trình??? – ðiu gì xy ra n u đo 2 câu l nh signal c a 1 trong 2 ti n trình??? 92
Gi i pháp v i Monitor •Cn l ưu m t vùng đm: ProducerI: – buffer: array[0 k-1] of items; repeat •Cn hai bi n điu ki n: produce v; – notfull: csignal(notfull) vùng đm ch ưa đy. append(v); – notemty: csignal(notempty) vùng đm ch ưa r foreverng. • Các bi n con tr : – nextin: con tr đ thêm vào. ConsumerI: – nextout: con tr đ ly ra. repeat – count: s mt hàng trong vùng đm. take(v); • Các th tc consume v; – append(): thêm vào m t m t hàng (Producer) forever – take(): l y ra m t m t hàng (Consumer) 93 Gi i pháp v i Monitor Monitor boundedbuffer: buffer: array[0 k-1] of items; nextin:=0, nextout:=0, count:=0: integer; notfull, notempty: condition; append(v): if (count=k) cwait(notfull); buffer[nextin]:= v; nextin:= nextin+1 mod k; count++; csignal(notempty); take(v): if (count=0) cwait(notempty); v:= buffer[nextout]; nextout:= nextout+1 mod k; count ; csignal(notfull); 94
Gi i pháp truy n thơng đip • Nhà sn xu t s đt các m t hàng (trong các thơng đip) vào trong h p th ư mayconsume . • mayconsume hành đng nh ư là vùng đm c a chúng ta: nhà tiêu th ch cĩ th tiêu th nêu c ĩ ít nh t m t thơng đip trong h p th ư đĩ. •Hp th ư mayproduce đưc kh i t o ban đu vi k thơng đip tr ng (k= kích th ưc vùng đm). • Kích th ưc c a mayproduce gi m xu ng khi mt m t hàng đưc s n xu t và tăng lên n95 u mt m t h àng đư c tiêu th . Gi i pháp truy n thơng đip (2) Producer: var pmsg: message; repeat receive(mayproduce, pmsg); pmsg := produce(); send(mayconsume, pmsg); forever Consumer: var cmsg: message; repeat receive(mayconsume, cmsg); consume(cmsg); send(mayproduce, null); forever 96
Bài tốn Readers - Writers • Nhi u thao tác đc và ghi di n ra đng th i trên m t c ơ s d li u. • Trong khi m t ti n trình đang ghi thì các ti n trình khác khơng đưc ghi hay đc c ơ s d li u. • Các thao tác đc cĩ th ti n hành đng th i. 97 Phân tích • Cĩ 3 v n đ cn đng b – Khi m t ti n trình đang ghi thì khơng m t ti n trình nào đưc đc. – Khi m t ti n trình đang đc thì khơng đưc ghi, và các ti n trình đc khác v n đc bình th ưng – ðc quy n truy xu t trên các bi n dùng chung 98
Gi i pháp v i semaphore •D li u dùng chung semaphore mutex, wrt; int readcount; • Kh i t o mutex = 1, wrt = 1, readcount = 0 99 Gi i pháp v i semaphore (2) • readcount lưu s ti n trình đang đc hi n t i. • mutex cung c ấp độc quy ền truy xu ất trên bi ến readcount. • wrt cung c p đc quy n truy xu t cho ti n trình ghi. 100
Ti n trình Writer wait(wrt); writing is performed signal(wrt); 101 Ti n trình Reader wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); reading is performed wait(mutex); readcount ; if (readcount == 0) signal(wrt); signal(mutex); 102
Bài tốn S n xu t / Tiêu th •Mt khuơn m u cho vi c h p tác gi a các ti n trình – Producer cung c p thơng tin đưc tiêu th bi m t ti n trình Consumer . 103 Bài tốn S n xu t / Tiêu th (2) •Cn m t vùng đm đ lưu c ác m c hàng đưc s n xu t và tiêu th sau đ ĩ: – unbounded-buffer : khơng gi i h n kích th ưc. – bounded-buffer : cĩ kích th ưc xác đnh. 104
Multiple Producers and Consumers 105 Ng cnh • Ti n trình s n xu t s n xu t thơng tin đưc tiêu th bi ti n trình tiêu th . •Ti b t c th i đim nào, m t ti n trình s n xu t cĩ th to d li u nào đĩ. •Ti b t c th i đim nào, m t ti n trình tiêu th cĩ th mu n l y m t s d li u nào đĩ. •D li u đưc l ưu vào trong b đm. •Nu vùng đm là hu h n, nhà sn xu t s b “khĩa” nu d li u m i s làm tràn b đm. •Nu vùng đm r ng, nhà tiêu th s b khĩa khi nĩ cn d li u. 106
Ý t ưng • Vùng đm đưc cài đt b i m ng vịng v i 2 con tr là in và out . • Bi n in tr đn v trí t do k ti p trong vùng đm. • Bi n out tr đn v trí mc hàng đu tiên. 107 Bounded-Buffer: Gi i pháp vùng nh chia s •D li u chia s #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; 108
Bounded-Buffer – Ti n trình SX item nextProduced; while (1) { while (((in + 1) % BUFFER_SIZE) == out); /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; 109 } Bounded-Buffer – Consumer Process item nextConsumed; while (1) { while (in == out); /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } 110
Vn đ • Các ti n trình đng hành th ưng c n chia s d li u và tài nguyên. •Nu khơng ki m sốt vi c truy xu t tài nguyên mt tính tồn v n d li u. • Hành đng thi hành b i các ti n trình đng hành s ph thu c và th t thi hành c a các ti n trình. 111 Ví d v s khơng tồn v n • Cĩ 2 ti n trình P1, P2 cùng chia xu t đn bi n a. static char a; • Các ti n trình cĩ th b ng t bt c lúc nào. void echo() { •Nu P1 b ng t sau khi nh p cin >> a; d li u và P2 thi hành hồn cout << a; tồn. } • Sau đĩ d li u xu t ra b i P1 s là kí t đc b i P2!!! 112
Tồn v n d li u •Bo v tồn v n d li u địi h i c ơ ch bo đm s thi hành m t cách cĩ th t ca các ti n trình h p tác. • Gi i pháp vùng nh chia s trên cho phép t i đa n-1 m c đưc trong vùng đm t i m t th i đim. – ðm s mc hi n t i đang trong vùng đm 113 Bounded-Buffer – b đm •D li u chia s #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; 114
Bounded-Buffer – ti n trình SX item nextProduced; while (1) { while (counter == BUFFER_SIZE); /* do nothing */ buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; 115 } Bounded-Buffer – Ti n trình TT item nextConsumed; while (1) { while (counter == 0); /* do nothing */ nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter ; } 116
Bounded-Buffer – bi n đm (1) • Câu l nh counter++; counter ; ph i là câu l nh nguyên t . • Câu l nh nguyên t là câu l nh khơng th b ng t. 117 Bounded-Buffer – Bi n đm (2) • count++: register1 = counter register1 = register1 + 1 counter = register1 • count : register2 = counter register2 = register2 – 1 counter = register2 118
Bounded-Buffer – Bi n đm (3) •Nu c hai nhà tiêu th và sn xu t đu c gng c p nh t vùng đm m t cách đng th i, cĩ th cĩ s thi hành xen l n các câu l nh. •S chen ngang ph thu c vào vi c lên l ch các ti n trình SX và TT. 119 Bounded-Buffer – Bi n đm (4) •Mt kh năng c ĩ th : producer: register1 = counter (register1 = 5) producer: register1 = register1 + 1 (register1 = 6 ) consumer: register2 = counter (register2 = 5 ) consumer: register2 = register2 – 1 (register2 = 4 ) producer: counter = register1 (counter = 6) 120 consumer: counter = register2 (counter =
ðng đ (race condition) • Race condition : tình hu ng mà nhi u ti n trình cùng truy c p và thao tác d li u chia s mt cách đng th i. D li u cu i cùng ph thu c vào ti n trình cu i cùng. • ð ngăn nga đng đ, các ti n trình đng hành ph i đưc đng b hĩa. 121 ðng đ do c p nh t d li u Chia s ẻ mức cân đối thu chi; Code for p1: Code for p2: . . . . . . balance += amount; balance += amount; . . . . . . Code for p1: Code for p2: . . . . . . Load R1, balance Load R1, balance Load R2, amount Load R2, amount Add R1, R2 Add R1, R2 Store R1, balance Store R1, balance . . . . . . 122
ðng đ do c p nh t d li u 123 Deadlock Trong m t deadlock, các quá trình khơng bao gi hồn thành vi c th c thi và các tài nguyên h th ng b bu c ch t, ng ăn ch n các quá trình khác bt đu. Tr ưc khi chúng ta th o lu n các ph ươ ng pháp khác nhau gi i quy t v n đ deadlock, chúng ta s mơ t các đc đim mà deadlock mơ t . 1
Deadlock Tr ưng h p deadlock cĩ th phát sinh n u 4 điu ki n sau x y ra cùng m t lúc trong h th ng: 1) Lo i tr h tương : ch mt quá trình t i cùng m t th i đim cĩ th s dng tài nguyên khơng chia s . N u m t quá trình khác yêu c u tài nguyên đĩ, quá trình yêu c u ph i t m d ng cho đn khi tài nguyên đưc gi i phĩng. 2) Gi và ch cp thêm tài nguyên: quá trình ph i đang gi ít nh t mt tài nguyên và đang ch đ nh n tài nguyên thêm mà hi n đang đưc gi bi quá trình khác. 3) Khơng địi li tài nguyên t quá trình đang gi chúng: Các tài nguyên khơng th b địi li; ngh ĩa là, tài nguyên cĩ th đưc gi i phĩng ch t ý b i quá trình đang gi nĩ, sau khi quá trình đĩ hồn thành tác v . 4) T n t i chu trình trong đ th cp phát tài nguyên: m t t p h p các quá trình {P0, P1, ,Pn} đang ch mà trong đ ĩ P0 đang ch mt tài nguyên đưc gi bi P1, P1 đang ch tài nguyên đang gi bi P2, ,Pn-1 đang ch tài nguyên đang đưc gi bi quá trình P0. 2 Tr ng thái an tồn Mt tr ng thái là an tồn n u h th ng cĩ th cp phát các tài nguyên t i m i quá trình trong mt vài th t và vn tránh deadlock. Hay nĩi cách khác, m t h th ng trong tr ng thái an tồn ch nu đĩ tn t i m t th t an tồn. 3
Tr ng thái an tồn Th t ca các quá trình là mt th t an tồn cho tr ng thái c p phát hi n hành n u đi v i m i th t Pi, các tài nguyên mà Pi yêu c u v n cĩ th đưc tho mãn bi tài nguyên hi n cĩ cng v i các tài nguyên đưc gi bi tt c Pj, v i j<i. Trong tr ưng h p này, n u nh ng tài nguyên mà quá trình Pi yêu c u khơng s n dùng t c thì thì Pi cĩ th ch cho đn khi t t c Pj hồn thành. Khi chúng hồn thành, Pi cĩ th đt đưc t t c nh ng tài nguyên nĩ cn, hồn thành các tác v đưc gán, tr v nh ng tài nguyên đưc c p phát cho nĩ và kt thúc. Khi Pi kt thúc, Pi+1 cĩ th đt đưc các tài nguyên nĩ cn 4 Tr ng thái an tồn Mt tr ng thái an tồn khơng là tr ng thái deadlock. Do đĩ, tr ng thái deadlock là tr ng thái khơng an tồn. Tuy nhiên, khơng ph i t t c tr ng thái khơng an tồn là deadlock 5
Các gi i pháp tránh deadlock Gi i pháp đ th cp phát tài nguyên: Nu khơng cĩ chu trình t n t i, thì vi c c p phát tài nguyên s đ li h th ng trong tr ng thái an tồn. Nu chu trình đưc tìm th y thì vi c c p phát s đt h th ng trong tr ng thái khơng an tồn. Do đĩ, quá trình Pi s ph i ch yêu c u c a nĩ đưc tho . 6 Các gi i pháp tránh deadlock Gi i thu t đ th cp phát tài nguyên khơng th áp d ng t i h th ng c p phát tài nguyên v i nhi u th hi n c a m i lo i tài nguyên. Gi i thu t tránh deadlock mà chúng ta mơ t ti p theo cĩ th áp d ng t i m t h th ng nh ưng ít hi u qu hơn cơ ch đ th cp phát tài nguyên. Gi i thu t này th ưng đưc g i là gi i thu t c a Banker . 7
Các gi i pháp tránh deadlock Nhi u c u trúc d li u ph i đưc duy trì đ cài đt gi i thu t Banker nh ư sau: • Available : m t vector cĩ chi u dài m hi n th s lưng tài nguyên s n dùng c a m i lo i. N u Available[j]= k, cĩ k th hi n c a lo i tài nguyên Rj s n dùng. • Max : m t ma tr n n x m đnh ngh ĩa s lưng t i đa yêu c u ca m i quá trình. N u Max[ i , j ] = k, thì quá trình Pi cĩ th yêu c u nhi u nh t k th hi n c a lo i tài nguyên Rj. • Allocation : m t ma tr n n x m đnh ngh ĩa s lưng tài nguyên c a m i lo i hi n đưc c p t i m i quá trình. N u Allocation[ i, j ] = k, thì quá trình Pi hi n đưc c p k th hi n ca lo i tài nguyên Rj. • Need : m t ma tr n n x m hi n th yêu c u tài nguyên cịn l i ca m i quá trình. N u Need[ i, j ] = k, thì quá trình Pi cĩ th cn thêm k th hi n c a lo i tài nguyên Rj đ hồn thành tác v ca nĩ. Chú ý r ng, Need[ i, j ]=Max[ i, j ]– Allocation [ i, j ]. 8 Gi i Thu t An Tồn Gi i thu t đ xác đnh h th ng tr ng thái an tồn hay khơng cĩ th đưc mơ t như sau : 1) G i Work và Finish là các vector cĩ chi u dài m và n tươ ng ng. Kh i t o Work:=Available và Finish[i]:=false cho i = 1, 2, ,n. 2) Tìm i th a: a) Finish[i] = false b) Need i ≤ Work. Nu khơng cĩ i nào th a, di chuy n t i b ưc 4 3) Work:=Work + Allocation i Finish[i] := true Di chuy n v bưc 2. 4) N u Finish[i] = true cho t t c i, thì h th ng đang tr ng thái an tồn. Gi i thu t này cĩ th yêu c u đ ph c t p mxn 2 thao tác đ quy t đnh tr ng thái là an tồn hay khơng. 9
Gi i Thu t Yêu C u C p Phát Tài Nguyên Cho Requesti là vector yêu c u cho quá trình Pi. N u Requesti[j] = k, thì quá trình Pi mu n k th hi n c a lo i tài nguyên Rj. Khi m t yêu cu tài nguyên đưc th c hi n b i quá trình Pi, thì các ho t đng sau đưc th c hi n: 1) N u Requesti ≤ Needi, di chuy n t i b ưc 2. Ngưc l i, phát sinh mt điu ki n l i vì quá trình v ưt quá yêu c u t i đa c a nĩ. 2) N u Requesti ≤ Available, di chuy n t i b ưc 3. Ngưc l i, Pi ph i ch vì tàinguyên khơng s n cĩ. 3) Gi s h th ng c p phát các tài nguyên đưc yêu c u t i quá trình Pi b ng cách thay đi tr ng thái sau: Available := Available – Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti; Nu k t qu tr ng thái c p phát tài nguyên là an tồn, thì Pi đưc cp phát tài nguyên c a nĩ. Tuy nhiên, n u tr ng thái m i là khơng an tồn, thì Pi ph i ch Requesti và tr ng thái c p phát tài nguyên c ũ đưc ph c h i. 10 Ví d: Tr ng Thái An Tồn Xét m t h th ng v i 5 quá trình t P0 t i P4, và 3 lo i tài nguyên A, B, C. Lo i tài nguyên A cĩ 10 th hi n, lo i tài nguyên B cĩ 5 th hi n và lo i tài nguyên C cĩ 7 th hi n. Gi s rng t i th i đim T0 tr ng thái hi n t i c a h th ng nh ư sau: 11
Ví d: Tr ng Thái An Tồn Chúng ta kh ng đnh r ng h th ng hi n trong tr ng thái an tồn. Th t v y, th t th a tiêu chu n an tồn (các tài nguyên mà Pi yêu c u v n cĩ th đưc tho mãn b i tài nguyên hi n cĩ cng v i các tài nguyên đưc gi bi t t c Pj, v i j<i.) 12 Ví d: Tr ng Th ái An To àn Gi s bây gi P1 yêu c u thêm m t th hi n lo i A và hai th hi n lo i C, vì th Request 1 = (1, 0, 2). ð quy t đnh yêu c u này cĩ th đưc c p tc thì hay khơng , trưc tiên chúng ta ph i ki m tra Request1 ≤ Available (ngh ĩa là, (1, 0, 2)) ≤ (3, 3, 2)) là đúng hay khơng. Sau đĩ, chúng ta gi s yêu c u này đt đưc và chúng ta đi đn tr ng thái m i sau: 13
Ví d: Tr ng Thái An Tồn Tuy nhiên, chúng ta c ũng th y r ng, khi h th ng trong tr ng thái này, m t yêu c u (3, 3, 0) bi P4 khơng th đưc gán vì các tài nguyên là khơng s n dùng. Mt yêu c u cho (0, 2, 0) b i P0 khơng th đưc c p m c dù tài nguyên là sn dùng vì tr ng thái k t qu là khơng an tồn. Hãy tính tốn và gi i thích rõ các ý trên? 14 Qu n lý b nh Memory management 1
Ni dung • Vì sao ph i qu n lý b nh • Khơng gian đa ch lơgic - khơng gian đa ch vt lý • Swapping •Cp phát b nh liên t c • Phân trang (Paging) • Phân đon (Segmentation) •Kt h p phân đon và phân trang Memory management 2 Vì sao ph i qu n lý b nh •Mt ch ươ ng trình mu n ch y thì ph i đưc n p vào trong b nh chính. –Vn đ: • Khi nào n p? •Np vào đâu? •Np nh ng ph n nào? • Qu n lý b nh giúp t i ưu hĩa ho t đng c a b nh Ti ưu hĩa s ti n trình cùng lúc trong b nh chính nâng cao tính đa ch ươ ng Tn d ng t i đa b nh ca máy tính Memory management 3
B nh • Là mt dãy các ơ nh liên tc nhau •Mi ơ nh (m t word) cĩ mt đa ch 0 • Ch ươ ng trình = t p các 4 MOV AX, 10 câu l nh (ch th máy) + d li u MOV BX, 20 8 •Np ch ươ ng trình vào b ADD AX, AX, BX 12 nh t các ch th và đ 16 d li u vào các ơ nh xác đnh ánh x gi a các ch th , d li u vào đa ch trong b nh Memory management 4 Ánh x ch th , d li u vào đa ch b nh Vi c ánh x ch th , d li u vào đa ch b nh cĩ th xy ra ti 3 th i đim: • Th i đim biên dch : nu đa ch vùng nh đưc bi t tr ưc thì mã lnh tuy t đi (cĩ đa ch tuy t đi) cĩ th đưc to ra ngay ti th i đim biên dch. Nu đa ch bt đu ca vùng nh b thay đi thì s ph i biên dch li. • Th i đim np: To ra các mã lnh cĩ th tái đnh v (relocatable code) nu đa ch vùng nh khơng th bi t ti th i đim biên dch. • Th i đim thi hành : Vi c kt hp mã lnh và đa ch s đưc trì hỗn cho đn lúc ch y ch ươ ng trình nu ti n trình đĩ cĩ th b di chuy n t phân đon nh này đn phân đon nh khác. Cn ph i cĩ h tr t ph n cng đ ánh x đa ch (ví d: thanh ghi cơ s và thanh ghi gi i hn (base registers, limit registers )). 5
Cơ ch np đng (Dynamic loading) • Các hàm s khơng đưc n p cho đn khi nĩ đưc g i •S dng b nh tt h ơn: các hàm khơng đưc s dng s khơng bao gi đưc np. • Cĩ ý ngh ĩa khi m t l ưng l n các mã l nh dùng đ x lý các tr ưng h p ít khi x y ra. • Khơng c n h tr t h điu hành. Memory management 6 Cơ ch liên k t đng (dynamic linking) • Liên k t lúc th c thi ti n trình. •Mt đon l nh nh , g i là stub , dùng đ đnh v hàm c a th ư vi n đang trong b nh . • Stub thi hành hàm v a tìm th y. •HðH c n ph i ki m tra xem hàm c n tìm cĩ nm trong b nh ca ti n trình hay khơng. Memory management 7
Overlays • Ch lưu trong b nh ch th và d li u đang c n. •Cn thi t khi m t ti n trình l n h ơn dung lưng nh cĩ th cp phát cho nĩ. Memory management 8 Mt s khái ni m • Khi m t ch ươ ng trình th c hi n, ni dung c a nĩ s đưc đư a vào b nh máy tính. • Khi đĩ, h điu hành ph i đnh ra mt vùng nh tr ng cho ch ươ ng trình ho t đng. • Thao tác này g i là location . Memory management 9
Mt s khái ni m • Sau mt th i gian ho t đng s cĩ mt s ch ươ ng trình kt thúc b nh b phân mnh. •Mt s ch ươ ng trình khác mu n ho t đng nh ưng các kh i nh tr ng cịn li khơng đ cp cho nĩ. • Khi đĩ h điu hành ph i th c hi n thao tác relocation đnh v li các ch ươ ng trình hi n cĩ đ to ra kh i nh tr ng ln nh t cho ch ươ ng trình. Memory management 10 Mt s khái ni m •Cơ ch overlay là cơ ch cho phép chia nh 1 ch ươ ng trình ra thành nhi u ph n. •Mi ph n là 1 trang (page). T i mt th i đim ch th c hi n m t ho c m t s trang. •S trang th c hi n m i l n là s khung trang k . Các ph n cịn l i s đưc đ li b nh ngồi. Memory management 11
Các k thu t thay th trang trong cơ ch overlay • Fifo: –Ví d: A c n th c hi n n i dung các page theo th t sau: 2 9 6 8 2 4 3 7 5 3 9. V i s khung trang k = 3. ( M i th i đim t i đa th c hi n đưc 3 trang). – ðu tiên 2 đưc n p vào b nh . 2 (tr ng thái b nh ) – Ti p theo 9 đưc n p vào b nh . 2 9 – Ti p theo 6 đưc n p vào b nh . 2 9 6 – Sau đĩ s thay 2 b i 8. 8 9 6 – Sau đĩ s thay 9 b i 2. 8 2 6 – ??? 8 2 4 – ??? 3 2 4 – ??? 3 7 4 – ??? 3 7 5 – ??? 3 7 5 – ??? 9 7 5 Memory management 12 Các k thu t thay th trang trong cơ ch overlay • Ít s dng nh t trong tươ ng lai : – Trang đưc thay th là trang ít s dng nh t trong tươ ng lai. Nu 2 trang trong tươ ng lai cĩ s ln xu t hi n bng nhau và khác 0 thì ta s ch n trang xa nh t đ thay th . Nu hai trang trong tươ ng lai đu khơng xu t hi n thì ch n trang đu tiên tính t trên xu ng. – Ví d: B cn th c hi n ni dung các page theo th t sau: 2 9 6 8 5 2 4 3 7 5 3 8 9. Vi s khung trang k = 3. ( Mi th i đim ti đa th c hi n đưc 3 trang). – ðu tiên 2 đưc np vào b nh . 2 (tr ng thái b nh ) – Ti p theo 9 đưc np vào b nh . 2 9 – Ti p theo 6 đưc np vào b nh . 2 9 6 – Sau đĩ s thay 6 bi 8. 2 9 8 – Sau đĩ s thay 9 bi 5. 2 5 8 – ??? 2 5 8 – ??? 4 5 8 – ??? 3 5 8 – ??? 3 5 7 – ??? 3 5 7 – ???Memory management 8 5 7 13 – ??? 9 5 7