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

người dùng •Mạng ngang hàng •Mạng có máy chủ: LAN, WAN, ... 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 15 Dưới góc độ hình thức xử lý –Hệ thống xử lý theo lô –Hệ thống chia sẻ –Hệ thống song song –Hệ thống phân tán –Hệ thống xử lý thời gian thực 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 16 HEÄ THOÁNG XÖÛ LYÙ ÑÔN CHÖÔNG  Ñôn chöông - Taùc vuï ñöôïc th i haønh tuaàn töï. - Boä giaùm saùt thöôøng tröïc, - CPU vaø caùc th ao taùc nhaäp xuaát, - Xöû lyù offline, - Ñoàng boä hoùa caùc thao taùc beân ngoaøi - Sp ooling (Simultaneous Periph eral Op eration On Line) Nhaäp Xuaát Maùy tính chính 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 17 HEÄ THOÁNG XÖÛ LYÙ ÑA CHÖÔNG Boä xöû lyù Keát thuùc taùc vuï Taùc vuï I/O  Nhieàu taùc vuï saün saøng thi haønh cuøng moät thôøi ñieåm.  Khi moät taùc vuï thöïc hieän I/O, baét ñaàu taùc vuï khaùc.  Boä xöû lyù vaø thieát bò thi haønh toaøn thôøi gian. 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 18 • Multiprogrammed systems – Nhieàu coâng vieäc ñöôïc naïp ñoàng thôøi vaøo boä nhôù chính – Khi moät tieán trình thöïc hieän I/O, moät tieán trình khaùc ñöôïc thöïc thi – Taän duïng ñöôïc thôøi gian raûnh, taêng hieäu suaát söû duïng CPU (CPU utilization) – Yeâu caàu ñoái vôùi heä ñieàu haønh Ñònh thôøi coâng vieäc (job scheduling): choïn job trong job pool treân ñóa vaø naïp noù vaøo boä nhôù ñeå thöïc thi. Quaûn lyù boä nhôù (memory management) Ñònh thôøi CPU (CPU scheduling) Caáp phaùt taøi nguyeân (ñóa, maùy in,) Baûo veä 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 49/14/2010 Vũ Đức Lung 19 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 20 HEÄ THOÁNG CHIA XEÛ THÔØI GIAN  Heä thoáng ña nhieäm (multitasking).  Laäp lòch CPU.  Thôøi gian chuyeån ñoåi giöõa caùc taùc vuï raát ngaén.  Boä xöû lyù 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 21 • Time-sharing systems – Multiprogrammed systems khoâng cung caáp khaû naêng töông taùc hieäu quaû vôùi users – CPU luaân phieân thöïc thi giöõa caùc coâng vieäc • Moãi coâng vieäc ñöôïc chia moät phaàn nhoû thôøi gian CPU (time slice, quantum time) • Cung caáp töông taùc giöõa user vaø heä thoáng vôùi thôøi gian ñaùp öùng (response time) nhoû (1 s) – Moät coâng vieäc chæ ñöôïc chieám CPU khi noù naèm trong boä nhôù chính. – Khi caàn thieát, moät coâng vieäc naøo ñoù coù theå ñöôïc chuyeån töø boä nhôù chính ra thieát bò löu tröõ (swapping), nhöôøng boä nhôù chính cho coâng vieäc khaùc. HEÄ THOÁNG CHIA XEÛ THÔØI GIAN 9/14/2010 Vũ Đức Lung 22 • Yeâu caàu ñoái vôùi OS trong heä thoáng time-sharing – Ñònh thôøi coâng vieäc (job scheduling) – Quaûn lyù boä nhôù (memory management) • Virtual memory – Quaûn lyù caùc quaù trình (process management)  Ñònh thôøi CPU  Ñoàng boä caùc quaù trình (synchronization)  Giao tieáp giöõa caùc quaù trình (process communication)  Traùnh deadlock – Quaûn lyù heä thoáng file, heä thoáng löu tröõ – Caáp phaùt hôïp lyù caùc taøi nguyeân – Baûo veä (protection) HEÄ THOÁNG CHIA XEÛ THÔØI GIAN 9/14/2010 Vũ Đức Lung 23 HEÄ THOÁNG ÑA XÖÛ LYÙ Boä xöû lyù Boä xöû lyù Boä nhôù chính Hai hoaëc nhieàu boä xöû lyù cuøng chia seû moät boä nhôù.  Master/Slave : moät boä xöû lyù chính kieåm soaùt moät soá boä xöû lyù I/O 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 24 • Heä thoáng song song (parallel, multiprocessor, hay tightly- coupled system) – Nhieàu CPU – Chia seû computer bus, clock – Öu ñieåm • Naêng xuaát heä thoáng (System throughput): caøng nhieàu processor thì caøng nhanh xong coâng vieäc • Multiprocessor system ít toán keùm hôn multiple single- processor system: vì coù theå duøng chung taøi nguyeân (ñóa,) • Ñoä tin caäy: khi moät processor hoûng thì coâng vieäc cuûa noù ñöôïc chia seû giöõa caùc processor coøn laïi HEÄ THOÁNG ÑA XÖÛ LYÙ 59/14/2010 Vũ Đức Lung 25 • Phaân loaïi heä thoáng song song – Ña xöû lyù ñoái xöùng (symmetric multiprocessor - SMP) • Moãi processor vaän haønh moät identical copy cuûa heä ñieàu haønh • Caùc copy giao tieáp vôùi nhau khi caàn • (Windows NT, Solaris 5.0, Digital UNIX, OS/2, Linux) – Ña xöû lyù baát ñoái xöùng (asymmetric multiprocessor) • Moãi processor thöïc thi moät coâng vieäc khaùc nhau • Master processor ñònh thôøi vaø phaân coâng vieäc cho caùc slave processors • (SunOS 4.0) HEÄ THOÁNG ÑA XÖÛ LYÙ 9/14/2010 Vũ Đức Lung 26 HEÄ THOÁNG PHAÂN TAÙN  Nhieàu maùy tính lieân keát vôùi nhau baèng ñöôøng truyeàn thoâng ñaëc bieät.  Töông töï heä thoáng ña xöû lyù nhöng khoâng chia xeû boä nhôù. Giao tieáp maïng Boä xöû lyù Boä nhôù Heä thoáng maùy tính 1 Giao tieáp maïng Boä xöû lyù Boä nhôù Heä thoáng maùy tính 2 Maïng 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 9/14/2010 Vũ Đức Lung 27 • Heä thoáng phaân taùn (distributed system, loosely-coupled system) – Moãi processor coù boä nhôù rieâng, caùc processor giao tieáp qua caùc keânh noái nhö maïng, bus toác ñoä cao – Ngöôøi duøng chæ thaáy moät heä thoáng ñôn nhaát – Öu ñieåm  Chia seû taøi nguyeân (resource sharing)  Chia seû söùc maïnh tính toaùn (computational sharing)  Ñoä tin caäy cao (high reliability)  Ñoä saün saøng cao (high availability): caùc dòch vuï cuûa heä thoáng ñöôïc cung caáp lieân tuïc cho duø moät thaønh phaàn hardware trôû neân hoûng HEÄ THOÁNG PHAÂN TAÙN 9/14/2010 Vũ Đức Lung 28 • Heä thoáng phaân taùn (tt) Caùc moâ hình heä thoáng phaân taùn – Client-server  Server: cung caáp dòch vuï  Client: coù theå söû duïng dòch vuï cuûa server – Peer-to-peer (P2P)  Caùc peer (maùy tính trong heä thoáng) ñeàu ngang haøng nhau  Khoâng coù cô sôû döõ lieäu taäp trung  Caùc peer laø töï trò  Vd: Gnutella HEÄ THOÁNG PHAÂN TAÙN 9/14/2010 Vũ Đức Lung 29 Heä thoáng thôøi gian thöïc (real-time system) • Heä thoáng thôøi gian thöïc (real-time system) – Söû duïng trong caùc thieát bò chuyeân duïng nhö ñieàu khieån caùc thöû nghieäm khoa hoïc, ñieàu khieån trong y khoa, daây chuyeàn coâng nghieäp, thieát bò gia duïng, quaân söï – Raøng buoäc veà thôøi gian: hard vaø soft real-time Phaân loaïi – Hard real-time • Haïn cheá (hoaëc khoâng coù) boä nhôù phuï, taát caû döõ lieäu naèm trong boä nhôù chính (RAM hoaëc ROM) • Yeâu caàu veà thôøi gian ñaùp öùng/xöû lyù raát nghieâm ngaët, thöôøng söû duïng trong ñieàu khieån coâng nghieäp, robotics, – Soft real-time • Thöôøng ñöôïc duøng trong lónh vöïc multimedia, virtual reality vôùi yeâu caàu meàm deûo hôn veà thôøi gian ñaùp öùng 9/14/2010 Vũ Đức Lung 30 • Thieát bò caàm tay (handheld system) – Personal digital assistant (PDA): Palm, Pocket-PC – Ñieän thoaïi di ñoäng (cellular phones) – Ñaëc tröng • Boä nhôù nhoû (512 KB – 128 MB) • Toác ñoä processor thaáp (ñeå ít toán pin) • Maøn hình hieån thò coù kích thöôùc nhoû vaø ñoä phaân giaûi thaáp. • Coù theå duøng caùc coâng ngheä keát noái nhö IrDA, Bluetooth, wireless Thieát bò caàm tay (handheld system) 69/14/2010 Vũ Đức Lung 31 1.3. LÒCH SÖÛ PHAÙT TRIEÅN CUÛA HEÄ ÑIEÀU HAØNH Theá heä 1 (1945 - 1955) - Thieát keá, xaây döïng, laäp trình, thao taùc: ñeàu do 1 nhoùm ngöôøi - Löu treân phieáu ñuïc loã  Theá heä 2 (1955 - 1965) - Xuaát h ieän söï phaân coâng coâng vieäc - Heä thoáng söû ly ù theo loâ ra ñôøi, löu treân baêng töø - Hoaït ñoäng döôùi söï ñieàu khieån ñaëc bieät cuûa 1 chöông trình  Theá heä 3 (1965 - 1980) -Ra ñôøi heä ñieàu haønh, khaùi nieäm ña chöông - HÑH chia seû thôøi gian nhö CTSS cuûa MIT - MULTICS, UNIX 9/14/2010 Vũ Đức Lung 32 1.3. LÒCH SÖÛ PHAÙT TRIEÅN CUÛA HEÄ ÑIEÀU HAØNH Theá heä 4 (1980 - ) -Ra ñôøi maùy tính caù nhaân, IBM PC - HÑH MS-DOS, MacOS (Apple Macintosh), MS Windows, OS/1 - Linux, QNX, HÑH maïng, 9/14/2010 Vũ Đức Lung 33 Operating Systems Evolution 55 60 65 70 75 80 85 90 95 00 03 IOCS DOS/360 DOS/VDSE VS VS/ESA OS/360 MVS/370 MVS/XA MVS/ES TSO IBSYS CTSS CP/CM5 VM/370 VM/XA VM/ESA SYSTEM III SYSTEM V SYSTEM V.4 MULTICS UNIX UNIXV.7 AIX/370 AIX SUN OS POSIX SOLARIS 2 4.1BSD 4.2BSD 4.3BSD 4.4BSD MACH OSF/1 AIX/ESA XENIX MS-DOS 1.0 CP/M DR/DOS OS/2WIN 3.0 WIN NT WIN 2000 WIN 9X WIN XP LINUX RSX-11M VMS 1.0 VMS 5.4 VMS 7.3 WIN 3.1 SOLARIS 10 RT-11 LINUX 2.6 WIN Server 2003 9/14/2010 Vũ Đức Lung 34 Windows And Linux Evolution • Windows and Linux kernels are based on foundations developed in the mid-1970s 1970 1980 1990 2000 VM S v1 .0 W in do w s N T 3. 1 NT 4 .0 W in do ws 2 00 0 W in do ws X P Se rv er 2 00 3 1970 1980 1990 2000 UN IX b or n UN IX p ub lic UN IX V 6 Li nu x v1 .0 v2 .0 v2 .2 v2 .3 v2 .4 v2 .6 (see for diagrams showing history of Windows & Unix) 19/14/2010 Vũ Đức Lung 1 Chöông II: Caáuá Truùcù Heää Ñieàuà Haønhø
Caùc thaønh phaàn cuûa heä ñieàu haønh
Caùc dòch vuï heä ñieàu haønh cung caáp
Lôøi goïi heä thoáng (System call)
Caùc chöông trình heä thoáng (system programs)
Caáu truùc heä thoáng
Maùy aûo (virtual machine) 9/14/2010 Vũ Đức Lung 2 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø - Quaù trình (hay tieán trình – process) laø gì? - Quaù trình khaùc chöông trình ôû ñieåm gì? - Moät quaù trình caàn caùc taøi nguyeân cuûa heä thoáng nhö CPU, boä nhôù, file, thieát bò I/O, ñeå hoaøn thaønh coâng vieäc. - Caùc nhieäm vuï cuûa thaønh phaàn  Taïo vaø huûy quaù trình  Taïm dừng/thöïc thi tieáp (suspend/resume) quaù trình  Cung caáp caùc cô cheá – ñoàng boä hoaït ñoäng caùc quaù trình (synchronization) – giao tieáp giöõa caùc quaù trình (interprocess communication) – khoáng cheá tắc nghẽn (deadlock) •2.1.1. Quaûn lyù quaù trình (process management) 9/14/2010 Vũ Đức Lung 3 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø – Boä nhôù chính laø trung taâm cuûa caùc thao taùc, xöû lyù – Ñeå naâng caoù hieäu suaát söû duïng CPU, heä ñieàu haønh caàn quaûn lyù boä nhôù thích hôïp – Caùc nhieäm vuï cuûa thaønh phaàn  Theo doõi, quaûn lyù caùc vuøng nhôù troáng vaø ñaõ caáp phaùt  Quyeát ñònh seõ naïp chöông trình naøo khi coù vuøng nhôù troáng  Caáp phaùt vaø thu hoài caùc vuøng nhôù khi caàn thieát •2.1.2. Quaûn lyù boä nhôù chính 9/14/2010 Vũ Đức Lung 4 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø – Heä thoáng file (file system)  File  Thö muïc – Caùc dòch vuï maø thaønh phaàn cung caáp  Taïo vaø xoaù file/thö muïc.  Caùc thao taùc xöû lyù file/thö muïc (mkdir, rename, copy, move, new,)  “AÙnh xaï” file/thö muïc vaøo thieát bò löu tröõ thöù caáp töông öùng  Sao löu vaø phuïc hoài döõ lieäu •2.1.3. Quaûn lyù file (file management) 9/14/2010 Vũ Đức Lung 5 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø – Che daáu söï khaùc bieät cuûa caùc thieát bò I/O tröôùc ngöôøi duøng – Coù chöùc naêng  Cô cheá: buffering, caching, spooling  Cung caáp giao dieän chung ñeán caùc trình ñieàu khieån thieát bò (device-driver interface)  Boä ñieàu khieån caùc thieát bò (device driver) phaàn cöùng. •2.1.4. Quaûn lyù heä thoáng I/O (I/O system management) 9/14/2010 Vũ Đức Lung 6 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø – Boä nhôù chính: kích thöôùc nhoû, laø moâi tröôøng chöùa tin khoâng beàn vöõng => caàn heä thoáng löu tröõ thöù caáp ñeå löu tröõ beàn vöõng caùc döõ lieäu, chöông trình – Phöông tieän löu tröõ thoâng duïng laø ñóa töø, ñóa quang – Nhieäm vuï cuûa heä ñieàu haønh trong quaûn lyù ñóa  Quaûn lyù khoâng gian troáng treân ñóa(free space management)  Caáp phaùt khoâng gian löu tröõ (storage allocation)  Ñònh thôøi hoïat ñoäng cho ñóa (disk scheduling)
Söû duïng thöôøng xuyeân => aûnh höôûng lôùn ñeán toác ñoä cuûa caû heä thoáng => caàn hieäu quaû •2.1.5. Quaûn lyù heä thoáng löu tröõ thöù caáp (secondary storage management) 29/14/2010 Vũ Đức Lung 7 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø Trong heä thoáng cho pheùp nhieàu user hay nhieàu process dieãn ra ñoàng thôøi: – Kieåm soaùt quaù trình ngöôøi duøng ñaêng nhaäp/xuaát vaø söû duïng heä thoáng – Kieåm soaùt vieäc truy caäp caùc taøi nguyeân trong heä thoáng – Baûo ñaûm nhöõng user/process chæ ñöôïc pheùp söû duïng caùc taøi nguyeân daønh cho noù – Caùc nhieäm vuï cuûa heä thoáng baûo veä  Cung caáp cô cheá kieåm soaùt ñaêng nhaäp/xuaát (login, log out)  Phaân ñònh ñöôïc söï truy caäp taøi nguyeân hôïp phaùp vaø baát hôïp phaùp (authorized/unauthorized)  Phöông tieän thi haønh caùc chính saùch (enforcement of policies) Chính saùch: caàn baûo veä döõ lieäu cuûa ai ñoái vôùi ai •2.1.6. Heä thoáng baûo veä 9/14/2010 Vũ Đức Lung 8 2.1. Caùcù thaønhø phaànà cuûaû heää ñieàuà haønhø – Laø giao dieän chuû yeáu giöõa ngöôøi duøng vaø OS • Ví duï: shell, mouse-based window-and-menu – Khi user login • command line interpreter (shell) chaïy, vaø chôø nhaän leänh töø ngöôøi duøng, thöïc thi leänh vaø traû keát quaû veà. – Caùc leänh ->boä ñieàu khieån leänh ->heä ñieàu haønh – Caùc leänh coù quan heä vôùi caùc vieäc:  Taïo, huûy, vaø quaûn lyù quaù trình, heä thoáng  Kieåm soaùt I/O  Quaûn lyù boä löu tröõ thöù caáp  Quaûn lyù boä nhôù chính  Truy caäp heä thoáng file vaø cô cheá baûo maät •2.1.7. Heä thoáng thoâng dòch leänh 9/14/2010 Vũ Đức Lung 9 2.2. Caùcù dòch vuïï heää ñieàuà haønhø cung caápá – Thöïc thi chöông trình – Thöïc hieän caùc thao taùcï I/O theo yeâu caàu cuûa chöông trình – Caùc thao taùc treân heä thoáng file • Ñoïc/ghi hay taïo/xoùa file – Trao ñoåi thoâng tin giöõa caùc quaù trình qua hai caùch:  Chia xeû boä nhôù (Shared memory)  Chuyeån thoâng ñieäp (Message passing) – Phaùt hieän loãi  Trong CPU, boä nhôù, treân thieát bò I/O (döõ lieäu hö, heát giaáy,)  Do chöông trình: chia cho 0, truy caäp ñeán ñòa chæ boä nhôù khoâng cho pheùp. 9/14/2010 Vũ Đức Lung 10 2.2. Caùcù dòch vuïï heää ñieàuà haønhø cung caápá Ngoaøi ra coøn caùc dòch vuï giuùp taêng hieäu suaát cuûa heä thoáng: – Caáp phaùt taøi nguyeân (resource allocation) • Taøi nguyeân: CPU, boä nhôù chính, tape drives, • OS coù caùc routine töông öùng – Keá toaùn (accounting) • Nhaèm löu veát user ñeå tính phí hoaëc ñôn giaûn ñeå thoáng keâ. – Baûo veä (protection) • Hai quaù trình khaùc nhau khoâng ñöôïc aûnh höôûng nhau • Kieåm soaùt ñöôïc caùc truy xuaát taøi nguyeân cuûa heä thoáng – An ninh (security) • Chæ caùc user ñöôïc pheùp söû duïng heä thoáng môùi truy caäp ñöôïc taøi nguyeân cuûa heä thoáng (vd: thoâng qua username vaø password) 9/14/2010 Vũ Đức Lung 11 2.3. Lôøiø goïiï heää thoángá (System call) • Duøng ñeå giao tieáp giöõa quaù trình vaø heä ñieàu haønh – Cung caáp giao dieän giöõa quaù trình vaø heä ñieàu haønh • Vd: open, read, write file – Thoâng thöôøng ôû daïng thö vieän nhò phaân (binary libraries) hay gioáng nhö caùc leänh hôïp ngöõ. – Trong caùc ngoân ngöõ laäp trình caáp cao, moät soá thö vieän laäp trình ñöôïc xaây döïng döïa treân caùc thö vieän heä thoáng (ví duï Windows API, thö vieän GNU C/C++ nhö glibc, glibc++,) – Ba phöông phaùp truyeàn tham soá khi söû duïng system call  Qua thanh ghi  Qua moät vuøng nhôù, ñòa chæ cuûa vuøng nhôù ñöôïc göûi ñeán heä ñieàu haønh qua thanh ghi  Qua stack 9/14/2010 Vũ Đức Lung 12 2.4. Caùcù chöông trình heää thoángá
Chöông trình heä thoáng (system program, phaân bieät vôùi application program) goàm – Quaûn lyù heä thoáng file: nhö create, delete, rename, list – Thoâng tin traïng thaùi: nhö date, time, dung löôïng boä nhôù troáng – Soaïn thaûo file: nhö file editor – Hoã trôï ngoân ngöõ laäp trình: nhö compiler, assembler, interpreter – Naïp, thöïc thi, giuùp tìm loãi chöông trình: nhö loader, debugger – Giao tieáp: nhö email, talk, web browser –
Ngöôøi duøng chuû yeáu laøm vieäc thoâng qua caùc system program (khoâng laøm vieäc “tröïc tieáp” vôùi caùc system call) 39/14/2010 Vũ Đức Lung 13 2.5. Caáuá truùcù heää thoángá
Caáu truùc ñôn giaûn (monolithic) – MS-DOS: khi thieát keá, do giôùi haïn veà dung löôïng boä nhôù neân khoâng phaân chia thaønh caùc module (modularization) vaø chöa phaân chia roõ chöùc naêng giöõa caùc phaàn cuûa heä thoáng. Caáu truùc phaân taàng cuûa MS-DOS 9/14/2010 Vũ Đức Lung 14 2.5. Caáuá truùcù heää thoángá
Caáu truùc ñôn giaûn (monolithic) UNIX: goàm hai phaàn coù theå taùch rôøi nhau  Nhaân (cung caáp file system, CPU scheduling, memory management, vaø moät soá chöùc naêng khaùc) vaø system program 9/14/2010 Vũ Đức Lung 15 2.5. Caáuá truùcù heää thoángá
Caáu truùc phaân taàng: HÑH ñöôïc chi thaønh nhieàu lôùp (layer).  Lôùp döôùi cuøng: hardware  Lôùp treân cuøng laø giao tieáp vôùi user  Lôùp treân chæ phuï thuoäc lôùp döôùi  Moät lôùp chæ coù theå goïi caùc haøm cuûa lôùp döôùi vaø caùc haøm cuûa noù ñöôïc goïi bôûi lôùp treân  Moãi lôùp töông ñöông moät ñoái töôïng tröøu töôïng: caáu truùc döõ lieäu + thao taùc  Phaân lôùp coù lôïi ích gì? Gôõ roái (debugger, kieåm tra heä thoáng, thay ñoåi chöùc naêng) 9/14/2010 Vũ Đức Lung 16 2.5. Caáuá truùcù heää thoángá
Caáu truùc phaân taàng:  Laàn ñaàu tieân ñöôïc aùp duïng cho HÑH THE (Technische Hogeschool Eindhoven) Phaàn cöùngLôùp 0 Laäp lòch CPULôùp 1 Quaûn lyù boä nhôùLôùp 2 Device driver thao taùc maøn hìnhLôùp 3 Taïo buffer cho thieát bò I/OLôùp 4 user programmLôùp 5 9/14/2010 Vũ Đức Lung 17 2.5. Caáuá truùcù heää thoángá
Vi nhaân: phaân chia module theo microkernel (CMU Mach OS, 1980)
Chuyeån moät soá chöùc naêng cuûa OS töø kernel space sang user space
Thu goïn kernel => microkernel, microkernel chæ bao goàm caùc chöùc naêng toái thieåu nhö quaûn lyù quaù trình, boä nhôù vaø cô cheá giao tieáp giöõa caùc quaù trình
Giao tieáp giöõa caùc module qua cô cheá truyeàn thoâng ñieäp ApplicationApplication File server File server OS/2 application OS/2 application OS/2 server OS/2 server POSIX application POSIX application POSIX server POSIX server Microkernel moät module 9/14/2010 Vũ Đức Lung 18 2.5. Caáuá truùcù heää thoángá
Vi nhaân: - Lôïi ích: deã môû roäng HÑH - Moät soá HÑH hieän ñaïi söû duïng vi nhaân: + Tru64 UNIX (Digital UNIX tröôùc ñaây): nhaân Mach + Apple MacOS Server : nhaân Mach + QNX – vi nhaân cung caáp: truyeàn thoâng ñieäp, ñònh thôøi CPU, giao tieáp maïng caáp thaáp vaø ngaét phaàn cöùng + Windows NT: chaïy caùc öùng duïng khaùc nhau win32, OS/2, POSIX (Portable OS for uniX) 49/14/2010 Vũ Đức Lung 19 2.6. Maùyù aûoû • Töø OS layer ñeán maùy aûo (virtual machine) Non-virtual machine system model Virtual machine system model hardware kernel processes kernelkernelkernel VM3VM2VM1 processes processes Virtual-machine implementation hardware processes programming interface 9/14/2010 Vũ Đức Lung 20 2.6. Maùyù aûoû
Hieän thöïc yù nieäm VM – Laøm theá naøo ñeå thöïc thi moät chöông trình MS-DOS treân moät heä thoáng Sun vôùi heä ñieàu haønh Solaris ? 1. Taïo moät maùy aûo Intel beân treân heä ñieàu haønh Solaris vaø heä thoáng Sun 2. Caùc leänh Intel (x86) ñöôïc maùy aûo Intel chuyeån thaønh leänh töông öùng cuûa heä thoáng Sun. Sun hardware Solaris kernel VM interpretation Intel x86 VM Intel x86 Application 11Vũ Đức LungKhoa KTMT Ch ö ô n g III: T ie áá n tr ìn h ( Pro ce ss)
K ha ùi nieäm cô ba ûn
Tra ïng tha ùi qua ù trình
K hoái ñieàu khieån qua ù trình (P ro c e ss con tro l b lo ck)
Ñ ònh thôøi qua ù trình (Pro cess Sc heduling )
Ca ùc ta ùc vuï ñoái vôùi qua ù trình
Söï coäng ta ùc giöõa ca ùc qua ù trình
G ia o tieáp giöõa ca ùc qua ù trình 2Vũ Đức LungKhoa KTMT 3.1. Khaùùi nieääm cô baûûn
Caùi g ì go ïi caùc ho aït ño än g cuûa CPU? – Heä thoáng boù (Batch system): jobs – Time-shared systems: user programs, tasks – Caùc hoaït ñoäng laø töông töï => goïi laø process
Quaù t rì nh (p ro ce ss) – moät chöông trình ñang thöïc thi Mo ät q u aù trìn h b ao g o àm – Text section (program code), data section (chöùa global variables) – program counter (PC), process status word (PSW), stack pointer (SP), memory management registers, 3Vũ Đức LungKhoa KTMT 3.1. Khaùùi nieääm cô baûûn Caùc böôùc naïp chöông trình vaøo boä nhôù 4Vũ Đức LungKhoa KTMT 3.1. Khaùùi nieääm cô baûûn program code data Executable binary file (load module) program code data stack Process image in main memory
Du øn g load m odule ñ e å b ie åu d ie ã n ch ö ô n g trìn h th ö ï c th i ñ ö ô ïc
Lay o u t lu aän ly ù cu ûa pro ce ss im age start address chöông trình => quaù trình 5Vũ Đức LungKhoa KTMT 3.1. Khaùùi nieääm cô baûûn
Caùc b öô ùc he ä ñ ie àu h aøn h k hô ûi taïo qu aù trìn h – Caáp phaùt moät ñònh danh duy nhaát (process number hay process identifier, pid) cho quaù trình – Caáp phaùt khoâng gian nhôù ñeå naïp quaù trình – Khôûi taïo khoái döõ lieäu Process Control Block (PCB) cho quaù trình  PCB laø nôi heä ñieàu haønh löu caùc thoâng tin veà quaù trình – Thieát laäp caùc moái lieân heä caàn thieát (vd: saép PCB vaøo haøng ñôïi ñònh thôøi,) Khôûûi taïïo quaùù trình 6Vũ Đức LungKhoa KTMT 3.2.Traïïng thaùùi quaùù trình
Caùc t raïng t haùi c uûa quaù t rì nh (p ro cess state s): – new: quaù trình vöøa ñöôïc taïo – ready: quaù trình ñaõ coù ñuû taøi nguyeân, chæ coøn caàn CPU – running: caùc leänh cuûa quaù trình ñang ñöôïc thöïc thi – waiting: hay laø blocked, quaù trình ñôïi I/O hoaøn taát, tín hieäu. – terminated: quaù trình ñaõ keát thuùc. 27Vũ Đức LungKhoa KTMT 3.2.Traïïng thaùùi quaùù trình readyready runningrunning dispatch interrupt I/O or event completion I/O or event wait newnew terminatedterminated waitingwaiting admit exit
Ch uy e ån ño åi g iöõa caùc traïng th aùi cu ûa q u aù trình 8Vũ Đức LungKhoa KTMT 3.2.Traïïng thaùùi quaùù trình /* test.c */ int main(int argc, char** argv) { printf(“Hello world\n"); exit(0); } Bie â n d òch ch ö ô n g trìn h tro n g Lin u x gcc test.c –o test Th ö ï c th i ch ö ô n g trìn h te st ./test Tro n g h e ä th o án g se õ co ù mo ät q u aù trìn h test ñ ö ô ïc taïo ra, th ö ï c th i v aø k e át th u ùc.
Ch uoãi traïng th aùi cu ûa qu aù trìn h te st n hö sau (tröô øn g h ô ïp to át nh aát): – new – ready – running – waiting (do chôø I/O khi goïi printf) – ready – running – terminated Ví duïï 9Vũ Đức LungKhoa KTMT 3.3.Process control block
Ñaõ th aáy laø mo ã i q u aù trìn h tro n g h e ä th o án g ñ e àu ñ ö ô ïc caáp p h aùt mo ät Pr oce s s Contro l Bl ock ( PCB)
PCB laø mo ät tro n g c aùc caáu tru ùc d ö õ lie äu q u an tro ïn g n h aát cu ûa h e ä ñ ie àu h aøn h v aø g o àm: - Traïng thaùi quaù trình: new, ready, running, - Boä ñeám chöông trình - Caùc thanh ghi - Thoâng tin laäp thôøi bieåu CPU: ñoä öu tieân, - Thoâng tin quaûn lyù boä nhôù - Thoâng tin taøi khoaûn: löôïng CPU, thôøi gian söû duïng, - Thoâng tin traïng thaùi I/O 10Vũ Đức LungKhoa KTMT 3.3.Process control block Löu ñoà chuyeån CPU töø quaù trình naøy ñeán quaù trình khaùc 11Vũ Đức LungKhoa KTMT Yeâuâ caààu ñoáái vôùùi heää ñieààu haøønh veàà quaûûn lyùù quaùù trình
Hoã trô ï söï th öïc th i lu aân ph ieân g iöõa nhie àu q u aù trìn h – Hieäu suaát söû duïng CPU – Thôøi gian ñaùp öùng
Ph aân p h oái taøi ng uy eân h e ä th oáng hô ïp ly ù – traùnh deadlock, trì hoaõn voâ haïn ñònh,
Cu ng caáp cô che á g iao tie áp v aø ñ o àn g bo ä ho aït ño än g caùc qu aù trình
Cu ng caáp cô che á h oã trô ï u se r taïo/ke át th u ùc qu aù trình 12Vũ Đức LungKhoa KTMT running ready waiting Quaûûn lyùù caùùc quaùù trình: caùùc haøøng ñôïïi 7 11 4 2 17 19 11 process number caùc PCB Coù gì sai trong ví duï?
Ví d u ï 313Vũ Đức LungKhoa KTMT 3.4. Ñònh thôøøi quaùù trình (Process Scheduling)
Taïi sao p h aûi ñ òn h th ô øi? – Ña chöông (Multiprogramming)  Coù vaøi quaù trình chaïy taïi caùc thôøi ñieåm  Muïc tieâu: taän duïng toái ña CPU – Chia thôøi(Time-sharing)  Users töông taùc vôùi moãi chöông trình ñang thöïc thi  Muïc tieâu: toái thieåu thôøi gian ñaùp öùng
Mo ät so á k h aùi n ie äm cô b aûn – Caùc boä ñònh thôøi (scheduler) – Caùc haøng ñôïi ñònh thôøi (scheduling queue) 14Vũ Đức LungKhoa KTMT Caùùc haøøng ñôïïi ñònh thôøøi (Scheduling queues)
Haøn g ñ ô ïi co â n g v ie äc-Jo b q u e u e
Haøn g ñ ô ïi saün saøn g -Re ad y q u e u e
Haøn g ñ ô ïi th ie át bò- De v ice q u e u e s
15Vũ Đức LungKhoa KTMT Caùùc haøøng ñôïïi ñònh thôøøi (Scheduling queues) Löu ñoà haøng ñôïi cuûa ñònh thôøi quaù trình 16Vũ Đức LungKhoa KTMT 3.5. Boää ñònh thôøøi (Scheduler)
Bo ä ñ òn h th ôøi coân g v ie äc (Jo b sche du le r) h ay bo ä ñ ònh thô øi d aøi (lo n g -te rm sch ed u le r)
Bo ä ñ òn h th ôøi CPU h ay b oä ñ òn h th ô øi ng aén
Caùc q u aù trình co ù th eå moâ taû n hö : – Quaù trình höôùng I/O (I/O bound process) – Quaù trình höôùng CPU (CPU bound process) Thôøi gian thöïc hieän khaùc nhau => keát hôïp haøi hoøa giöõa chuùng 17Vũ Đức LungKhoa KTMT Boää ñònh thôøøi trung gian(medium-term scheduling)
Ñoâi k h i h eä ñ ie àu h aøn h (nh ö time -sh arin g sy stem) co ù th eâm me d iu m-te rm sch ed u lin g ñ eå ñ ie àu chæn h möùc ño ä ñ a ch öô ng cu ûa h e ä th o án g
Medi um-t erm sc hedul er – chuyeån quaù trình töø boä nhôù sang ñóa (swap out) – chuyeån quaù trình töø ñóa vaøo boä nhôù (swap in) 18Vũ Đức LungKhoa KTMT 3.6. Caùùc taùùc vuïï ñoáái vôùùi quaùù trình
Taïo q u aù trìn h mô ùi (p ro ce ss cre atio n ) – Moät quaù trình coù theå taïo nhieàu quaù trình môùi thoâng qua moät lôøi goïi heä thoáng create-process (vd: haøm fork trong Unix)  Ví duï: (Unix) Khi user ñaêng nhaäp heä thoáng, moät command interpreter (shell) seõ ñöôïc taïo ra cho user Quaù trình ñöôïc taïo laø quaù trình con cuûa quaù trình taïo (quaù trình cha). Quan heä cha-con ñònh nghóa moät caây quaù trình. 419Vũ Đức LungKhoa KTMT Caâyâ quaùù trình trong Linux/Unix
Ví d u ï 20Vũ Đức LungKhoa KTMT 3.6.Caùùc taùùc vuïï ñoáái vôùùi quaùù trình
Taïo q u aù trìn h mô ùi – Quaù trình con nhaän taøi nguyeân: töø HÑH hoaëc töø P cha – Chia seû taøi nguyeân cuûa quaù trình cha  Quaù trình cha vaø con chia seû moïi taøi nguyeân  Quaù trình con chia seû moät phaàn taøi nguyeân cuûa cha – Trình töï thöïc thi  Quaù trình cha vaø con thöïc thi ñoàng thôøi (concurrently)  Quaù trình cha ñôïi ñeán khi caùc quaù trình con keát thuùc. 21Vũ Đức LungKhoa KTMT Veàà quan heää cha/con
Kh oâng g ian ñ òa ch æ (add re ss sp ace ) – Khoâng gian ñòa chæ cuûa quaù trình con ñöôïc nhaân baûn töø cha – Khoâng gian ñòa chæ cuûa quaù trình con ñöôïc khôûi taïo töø template.
Ví d u ï tron g UNIX/Lin u x – System call fork() taïo moät quaù trình môùi – System call exec() duøng sau fork() ñeå naïp moät chöông trình môùi vaøo khoâng gian nhôù cuûa quaù trình môùi ñoàng boä 22Vũ Đức LungKhoa KTMT Ví duïï taïïo process vôùùi fork() #include #include int main (int argc, char *argv[]){ int pid; /* create a new process */ pid = fork(); if (pid > 0){ printf(“This is parent process”); wait(NULL); exit(0); } else if (pid == 0) { printf(“This is child process”); execlp(“/bin/ls”, “ls”, NULL); exit(0); } else { printf(“Fork error\n”); exit(-1); } } 23Vũ Đức LungKhoa KTMT 3.6.Caùùc taùùc vuïï ñoáái vôùùi quaùù trình (tt)
Taïo q u aù trìn h mô ùi 
Ke át th uùc q u aù trìn h – Quaù trình töï keát thuùc  Quaù trình keát thuùc khi thöïc thi leänh cuoái vaø goïi system routine exit – Quaù trình keát thuùc do quaù trình khaùc (coù ñuû quyeàn, vd: quaù trình cha cuûa noù)  Goïi system routine abort vôùi tham soá laø pid (process identifier) cuûa quaù trình caàn ñöôïc keát thuùc – Heä ñieàu haønh thu hoài taát caû caùc taøi nguyeân cuûa quaù trình keát thuùc (vuøng nhôù, I/O buffer,) 24Vũ Đức LungKhoa KTMT 3.7. Coääng taùùc giöõaõ caùùc quaùù trình
Tro n g qu aù trình thöïc th i, caùc q u aù trình co ù th e å c oäng t aùc (co o p e rate ) ñ e å h o aøn th aønh coân g v ie äc
Caùc q u aù trình co än g taùc ñ eå – Chia seû döõ lieäu (information sharing) – Taêng toác tính toaùn (computational speedup)  Neáu heä thoáng coù nhieàu CPU, chia coâng vieäc tính toaùn thaønh nhieàu coâng vieäc tính toaùn nhoû chaïy song song – Thöïc hieän moät coâng vieäc chung  Xaây döïng moät phaàn meàm phöùc taïp baèng caùch chia thaønh caùc module/process hôïp taùc nhau
Söï co än g taùc g iöõa caùc qu aù trình yeâu caàu he ä ñ ie àu h aøn h h oã trô ï cô ch e á g iao tieáp v aø cô che á ño àn g b o ä h o aït ñ o än g cuûa caùc q u aù trìn h 525Vũ Đức LungKhoa KTMT Baøøi toaùùn ngöôøøi saûûn xuaáát-ngöôøøi tieâuâ thuïï (producer-consumer )
Ví d u ï co än g taùc g iöõa caùc q u aù trình : baøi t oaùn produc er-c onsumer – Producer taïo ra caùc döõ lieäu vaø consumer tieâu thuï, söû duïng caùc döõ lieäu ñoù. Söï trao ñoåi thoâng tin thöïc hieän qua buffer  unbounded buffer: kích thöôùc buffer voâ haïn (khoâng thöïc teá).  bounded buffer: kích thöôùc buffer coù haïn. – Producer vaø consumer phaûi hoaït ñoäng ñoàng boä vì  Consumer khoâng ñöôïc tieâu thuï khi producer chöa saûn xuaát  Producer khoâng ñöôïc taïo theâm saûn phaåm khi buffer ñaày. 26Vũ Đức LungKhoa KTMT 3.8.Giao tieááp lieânâ quaùù trình (Interprocess communication-IPC)
IPC laø cô che á cun g caáp bô ûi h e ä ñ ieàu h aønh nh aèm g iu ùp caùc qu aù trìn h – giao tieáp vôùi nhau – vaø ñoàng boä hoaït ñoäng maø khoâng caàn chia seû khoâng gian ñòa chæ
IPC co ù th eå ñö ô ïc cun g caáp bô ûi me ssag e p assing system 27Vũ Đức LungKhoa KTMT Heää thoááng truyeààn thoângâ ñieääp Message passing system
Laøm th e á n aøo ñ e å caùc q u aù trìn h g iao tie áp n h a u ? Caùc v aán ñ e à: – Ñaët teân (Naming)  Giao tieáp tröïc tieáp – send(P, msg): göûi thoâng ñieäp ñeán quaù trình P – receive(Q, msg): nhaän thoâng ñieäp ñeán töø quaù trình Q  Giao tieáp giaùn tieáp: thoâng qua mailbox hay port – send(A, msg): göûi thoâng ñieäp ñeán mailbox A – receive(B, msg): nhaän thoâng ñieäp töø mailbox B – Ñoàng boä hoùa (Synchronization): blocking send, nonblocking send, blocking receive, nonblocking receive – Taïo vuøng ñeäm (Buffering): duøng queue ñeå taïm chöùa caùc message  Khaû naêng chöùa laø 0(Zero capacity hay no buffering)  Bounded capacity: ñoä daøi cuûa queue laø giôùi haïn  Unbounded capacity: ñoä daøi cuûa queue laø khoâng giôùi haïn 28Vũ Đức LungKhoa KTMT Tie åå u trìn h (lu o àà n g ) - Th re ad
Tie åu trình (tie án trìn h n he ï-ligh twe igh t p ro ce ss): laø moät ñô n v ò cô b aûn söû d u ïn g CPU, go àm: – Thread ID, PC, Registers, stack vaø chia seû chung code, data, resources (files) 29Vũ Đức LungKhoa KTMT PCB vaøøTCB trong moââ hình multithreads pid Threads list Context (Mem, global ressources) Scheduling statistic Relatives ( Dad, children) PCB tid State (State, details) Context (IP, local stack) Thread Control Block TCB 30Vũ Đức LungKhoa KTMT Lô ïï i ích cu ûû a tie áá n tr ìn h ñ a lu o àà n g
Ñaùp öùn g n h anh : Ch o p h eùp chö ôn g trìn h tieáp tu ïc thöïc th i k h i mo ät b o ä p h aän b ò k ho ùa h o aëc mo ät h o aït ñ oän g d aøi
Ch ia seû taøi ng uy eân : tieát k ie äm k hoân g g ian nh ôù
Kin h te á: taïo v aø ch uy eån n gö õ caûnh nhan h hô n tie án trìn h VD: tro n g So laris 2 , taïo p ro ce ss ch aäm h ôn 30 laàn, ch uy eån ch aäm h ô n 5 laàn
Tro n g mu ltip ro ce sso r: coù the å thöïc h ie än so ng so ng 631Vũ Đức LungKhoa KTMT Tieååu trình ngöôøøi duøøng (User thread) Khái niệm tiểu trình được hỗ trợ bởi một thư viện hoạt động trong user mode T1 Kernel T2 User mode Kernel mode T3 LWP1 LWP2 P1 P2 32Vũ Đức LungKhoa KTMT Tiểu trìn h hạt n h aân (K e r n e lâ th re ad ) Khái niệm tiểu trình được xây dựng bên trong hạt nhân T1 T2 HDH System call User mode Kernel mode 33Vũ Đức LungKhoa KTMT 11Khoa KTMT Chöông IV: Ñònh thôøøi CPU
Khaùi nieäm cô baûn
Caùc boä ñònh thôøi – long-term, mid-term, short-term
Caùc tieâu chuaån ñònh thôøi CPU
Caùc giaûi thuaät ñònh thôøi – First-Come, First-Served (FCFS) – Round-Robin (RR) – Shortest Job First (SJF) vaø Shortest Remaining Time First (SRTF) – Priority Scheduling – Highest Response Ratio Next (HRRN) – Multilevel Queue – Multilevel Feedback Queue 2Khoa KTMT Khaùi nieäm cô baûn
Trong caùc heä thoáng multitasking – Thöïc thi nhieàu chöông trình ñoàng thôøi laøm taêng hieäu suaát heä thoáng. – Taïi moãi thôøi ñieåm, chæ coù moät process ñöôïc thöïc thi. Do ñoù, caàn phaûi giaûi quyeát vaán ñeà phaân chia, löïa choïn process thöïc thi sao cho ñöôïc hieäu quaû nhaát→ chieán löôïc ñònh thôøi CPU.
Ñònh thôøi CPU – Choïn moät process (töø ready queue) thöïc thi. – Vôùi moät multithreaded kernel, vieäc ñònh thôøi CPU laø do OS choïn kernel thread ñöôïc chieám CPU. 3Khoa KTMT Caùc boä ñònh thôøi readyready runningrunning suspended ready suspended ready suspended blocked suspended blocked newnew terminatedterminated blockedblocked Long-term scheduling Long-term scheduling Medium-term scheduling Medium-term scheduling Short-term scheduling 4Khoa KTMT Caùc boä ñònh thôøi
Long-term scheduling – Xaùc ñònh chöông trình naøo ñöôïc chaáp nhaän naïp vaøo heä thoáng ñeå thöïc thi – Ñieàu khieån möùc ñoä multiprogramming cuûa heä thoáng – Long term scheduler thöôøng coá gaéng duy trì xen laãn CPU-bound vaø I/O-bound process
Medium-term scheduling – Process naøo ñöôïc ñöa vaøo (swap in0, ñöa ra khoûi (swap out) boä nhôù chính – Ñöôïc thöïc hieän bôûi phaàn quaûn lyù boä nhôù vaø ñöôïc thaûo luaän ôû phaàn quaûn lyù boä nhôù. 5Khoa KTMT Caùc boä ñònh thôøi (tt) • Short term scheduling
Xaùc ñònh process naøo trong ready queue seõ ñöôïc chieám CPU ñeå thöïc thi keá tieáp (coøn ñöôïc goïi laø ñònh thôøi CPU, CPU scheduling)
Short term scheduler coøn ñöôïc goïi vôùi teân khaùc laø dispatcher
Boä ñònh thôøi short-term ñöôïc goïi moãi khi coù moät trong caùc söï kieän/interrupt sau xaûy ra: – Ngắt thôøi gian (clock interrupt) – Ngaét ngoaïi vi (I/O interrupt) – Lôøi goïi heä thoáng (operating system call) – SignalChöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn 6Khoa KTMT Dispatcher
Dispatcher seõ chuyeån quyeàn ñieàu khieån CPU veà cho process ñöôïc choïn bôûi boä ñònh thôøi ngaén haïn
Bao goàm: – Chuyeån ngöõ caûnh (söû duïng thoâng tin ngöõ caûnh trong PCB) – Chuyeån cheá ñoä ngöôøi duøng – Nhaûy ñeán vò trí thích hôïp trong chöông trình öùng duïng ñeå khôûi ñoäng laïi chöông trình (chính laø program counter trong PCB)
Coâng vieäc naøy gaây ra phí toån – Dispatch latency: thôøi gian maø dispatcher döøng moät process vaø khôûi ñoäng moät process khaùc 27Khoa KTMT Caùc tieâu chuaån ñònh thôøi CPU
User-oriented – Thôøi gian ñaùp öùng (Response time): khoaûng thôøi gian process nhaän yeâu caàu ñeán khi yeâu caàu ñaàu tieân ñöôïc ñaùp öùng (time- sharing, interactive system) → cöïc tieåu – Thôøi gian quay voøng (hoaøn thaønh) (Turnaround time): khoaûng thôøi gian töø luùc moät process ñöôïc naïp vaøo heä thoáng ñeán khi process ñoù keát thuùc → cöïc tieåu – Thôøi gian chôø (Waiting time): toång thôøi gian moät process ñôïi trong ready queue → cöïc tieåu
System-oriented – Söû duïng CPU (processor utilization): ñònh thôøi sao cho CPU caøng baän caøng toát → cöïc ñaïi – Coâng baèng (fairness): taát caû process phaûi ñöôïc ñoái xöû nhö nhau – Thoâng löôïng (throughput): soá process hoaøn taát coâng vieäc trong moät ñôn vò thôøi gian → cöïc ñaïi. 8Khoa KTMT Hai yeáu toá cuûa giaûi thuaät ñònh thôøi
Haøm choïn löïa (selection function): duøng ñeå choïn process naøo trong ready queue ñöôïc thöïc thi (thöôøng döïa treân ñoä öu tieân, yeâu caàu veà taøi nguyeân, ñaëc ñieåm thöïc thi cuûa process,), ví duï • w = toång thôøi gian ñôïi trong heä thoáng • e = thôøi gian ñaõ ñöôïc phuïc vuï • s = toång thôøi gian thöïc thi cuûa process (bao goàm caû “e”) 9Khoa KTMT Hai yeáu toá cuûa giaûi thuaät ñònh thôøi (tt)
Cheá ñoä quyeát ñònh (decision mode): choïn thôøi ñieåm thöïc hieän haøm choïn löïa ñeå ñònh thôøi. Coù hai cheá ñoä – Khoâng tröng duïng (Non-preemptive)  Khi ôû traïng thaùi running, process seõ thöïc thi cho ñeán khi keát thuùc hoaëc bò blocked do yeâu caàu I/O – Tröng duïng (Preemptive)  Process ñang thöïc thi (traïng thaùi running) coù theå bò ngaét nöûa chöøng vaø chuyeån veà traïng thaùi ready bôûi heä ñieàu haønh  Chi phí cao hôn non-preemptive nhöng ñaùnh ñoåi laïi baèng thôøi gian ñaùp öùng toát hôn vì khoâng coù tröôøng hôïp moät process ñoäc chieám CPU quaù laâu. 10Khoa KTMT Preemptive vaø Non-preemptive
Hàm định thời được thực hiện khi (1) Chuyển từ trạng thái running sang waiting (2) Chuyển từ trạng thái running sang ready (3) Chuyển từ trạng thái waiting, new sang ready (4) Kết thúc thực thi 1 và 4 không cần lựa chọn loại định thời biểu, 2 và 3 cần
Trường hợp 1, 4 được gọi là định thời nonpreemptive
Trường hợp 2, 3 được gọi là định thời preemptive Thực hiện cơ chế nào khó hơn? Tại sao? 11Khoa KTMT Khaûo saùt giaûi thuaät ñònh thôøi
Service time = thôøi gian process caàn CPU trong moät chu kyø CPU-I/O
Process coù service time lôùn laø caùc CPU-bound process 285 564 443 622 301 Service Time Arrival Time Process load store add store read from file wait for I/O inc store write to file load store add store read from file wait for I/O wait for I/O  I/O burst CPU burst CPU burst CPU burst I/O burst I/O burst moät chu kyø CPU-I/O 12Khoa KTMT 1. First-Come First-Served (FCFS)
Haøm löïa choïn: Tieán trình naøo yeâu caàu CPU tröôùc seõ ñöôïc caáp phaùt CPU tröôùc; Process seõ thöïc thi ñeán khi keát thuùc hoaëc bò blocked do I/O
Cheá ñoä quyeát ñònh: non-preemptive algorithm
Hieän thöïc : söû duïng haøng ñôïi FIFO (FIFO queues) – Tieán trình ñi vaøo ñöôïc theâm vaøo cuoái haøng ñôïi – Tieán trình ñöôïc löïa choïn ñeå xöû lyù ñöôïc laáy töø ñaàu cuûa queues 0 5 10 15 20 P1 P2 P3 P4 P5 addrun 313Khoa KTMT FCFS Scheduling
Ví duï : Process Burst Time P1 24 P2 3 P3 3
Giaû söû thöù töï vaøo cuûa caùc tieán trình laø  P1, P2, P3
Thôøi gian chôø  P1 = 0;  P2 = 24;  P3 = 27;
Thôøi gian chôø trung bình  (0+24+27)/3 = 17 0 24 27 30 P1 P2 P3 Gantt Chart for Schedule 14Khoa KTMT FCFS Scheduling
Ví duï: Process Burst Time P1 24 P2 3 P3 3
Giaû söû thôøi gian vaøo cuûa caùc tieán trình laø  P2, P3, P1
Thôøi gian chôø :  P1 = 6; P2 = 0; P3 = 3;
Thôøi gian chôø trung bình  (6+0+3)/3 = 3 , toát hôn.. 0 3 6 30 P1P2 P3 Gantt Chart for Schedule 15Khoa KTMT 2. Shortest-Job-First(SJF) Scheduling
Ñònh thôøi bieåu coâng vieäc ngaén nhaát tröôùc
Khi CPU ñöôïc töï do, noù seõ caáp phaùt cho tieán trình yeâu caàu ít thôøi gian nhaát ñeå keát thuùc ( tieán trình ngaén nhaát)
Lieân quan ñeán chieàu daøi thôøi gian söû duïng CPU cho laàn tieáp theo cuûa moãi tieán trình. Söû duïng nhöõng chieàu daøi naøy ñeå laäp lòch cho tieán trình vôùi thôøi gian ngaén nhaát. 16Khoa KTMT 2. Shortest-Job-First(SJF) Scheduling
Hai hình thöùc (Schemes): – Scheme 1: Non-preemptive( tieán trình ñoäc quyeàn CPU)  Khi CPU ñöôïc trao cho quaù trình noù khoâng nhöôøng cho ñeán khi noù keát thuùc chu kyø xöû lyù cuûa noù – Scheme 2: Preemptive( tieán trình khoâng ñoäc quyeàn)  Neáu moät tieán trình CPU môùi ñöôïc ñöa vaøo danh saùch vôùi chieàu daøi söû duïng CPU cho laàn tieáp theo nhoû hôn thôøi gian coøn laïi cuûa tieán trình ñang xöû lyù noù seõ döøng hoaït ñoäng tieán trình hieän haønh (hình thöùc naøy coøn goïi laø Shortest- Remaining-Time-First (SRTF).) – SJF laø toái öu – cho thôøi gian chôø ñôïi trung bình toái thieåu vôùi moät taäp tieán trình cho tröôùc 17Khoa KTMT Non-Preemptive SJF Scheduling
Ví duï : Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 0 8 16 P1 P2P3 Gantt Chart for Schedule P4 127 Average waiting time = (0+6+3+7)/4 = 4 18Khoa KTMT Preemptive SJF Scheduling (hay Sortest Remaining Time First - SRTF)
Ví duï 1: Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 0 7 16 P1 P2P3 Gantt Chart for Schedule P4 115 Average waiting time = (9+1+0+2)/4 = 3 P2 P1 2 4 Process Arrival TimeBurst Time P1 0 8 P2 1 4 P3 2 9 P4 3 5 VD2: 419Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF
Coù theå xaûy ra tình traïng “ñoùi” (starvation) ñoái vôùi caùc process coù CPU-burst lôùn khi coù nhieàu process vôùi CPU- burst nhoû ñeán heä thoáng.
Cô cheá non-preemptive khoâng phuø hôïp cho heä thoáng time sharing (interactive)
Giaûi thuaät SJF ngaàm ñònh ra ñoä öu tieân theo burst time
Caùc CPU-bound process coù ñoä öu tieân thaáp hôn so vôùi I/O-bound process, nhöng khi moät process khoâng thöïc hieän I/O ñöôïc thöïc thi thì noù ñoäc chieám CPU cho ñeán khi keát thuùc 20Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF
Tương ứng với mỗi process cần có độ dài của CPU burst tiếp theo
Hàm lựa chọn: chọn process có độ dài CPU burst nhỏ nhất
Chứng minh được: SJF tối ưu trong việc giảm thời gian đợi trung bình
Nhược điểm: Cần phải ước lượng thời gian cần CPU tiếp theo của process
Giải pháp cho vấn đề này? 21Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF (Thời gian sử dụng CPU chính là độ dài của CPU burst)
Trung bình tất cả các CPU burst đo được trong quá khứ
Nhưng thông thường những CPU burst càng mới càng phản ánh đúng hành vi của process trong tương lai
Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ (exponential averaging) – τn+1 = a tn + (1 - a) τn , 0 ≤ a ≤ 1 – τn+1 = a tn + (1- a) a tn-1 ++ (1- a)jaτn-j++ (1- a)n+1aτ0 – Nếu chọn a = ½ thì có nghĩa là trị đo được tn và trị dự đoánτn được xem quan trọng như nhau. 22Khoa KTMT Dự đoán thời gian sử dụng CPU Độ dài CPU burst đo được Độ dài CPU burst dự đoán, với a = ½ và τ0 = 10 23Khoa KTMT 3. Priority Scheduling
Moãi process seõ ñöôïc gaùn moät ñoä öu tieân
CPU seõ ñöôïc caáp cho process coù ñoä öu tieân cao nhaát
Ñònh thôøi söû duïng ñoä öu tieân coù theå: – Preemptive hoaëc – Nonpreemptive 24Khoa KTMT Gaùn ñoä öu tieân
SJF laø moät giaûi thuaät ñònh thôøi söû duïng ñoä öu tieân vôùi ñoä öu tieân laø thôøi-gian-söû-duïng-CPU-döï-ñoaùn
Gaùn ñoä öu tieân coøn döïa vaøo: – Yeâu caàu veà boä nhôù – Soá löôïng file ñöôïc môû – Tæ leä thôøi gian duøng cho I/O treân thôøi gian söû duïng CPU – Caùc yeâu caàu beân ngoaøi ví duï nhö: soá tieàn ngöôøi duøng traû khi thöïc thi coâng vieäc 525Khoa KTMT 3. Priority Scheduling
Vaán ñeà: trì hoaõn voâ haïn ñònh – process coù ñoä öu tieân thaáp coù theå khoâng bao giôø ñöôïc thöïc thi
Giaûi phaùp: laøm môùi (aging) – ñoä öu tieân cuûa process seõ taêng theo thôøi gian
Vd: 26Khoa KTMT 4. Ñònh thôøi luaân phieân (Round Robin -RR)
Moãi process nhaän ñöôïc moät ñôn vò nhoû thôøi gian CPU (time slice, quantum time), thoâng thöôøng töø 10-100 msec ñeå thöïc thi. Sau khoaûng thôøi gian ñoù, process bò ñoaït quyeàn vaø trôû veà cuoái haøng ñôïi ready.
Neáu coù n process trong haøng ñôïi ready vaø quantum time = q thì khoâng coù process naøo phaûi chôø ñôïi quaù (n − 1)q ñôn vò thôøi gian.
Hieäu suaát – Neáu q lôùn: RR ⇒ FCFS – Neáu q nhoû (q khoâng ñöôïc quaù nhoû bôûi vì phaûi toán chi phí chuyeån ngöõ caûnh)
Thôøi gian chôø ñôïi trung bình cuûa giaûi thuaät RR thöôøng khaù lôùn nhöng thôøi gian ñaùp öùng nhoû 27Khoa KTMT Ví duï Round Robin
Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 0 P1 P4P3 Gantt Chart for Schedule P1P2 20 P3 P3 P3P4 P1 37 57 77 97 117 121 134 154 162 turnaround time trung bình lôùn hôn SJF, nhöng ñaùp öùng toát hôn 28Khoa KTMT RR vôùi time quantum = 1  Thôøi gian turn-around trung bình cao hôn so vôùi SJF nhöng coù thôøi gian ñaùp öùng trung bình toát hôn.  Öu tieân CPU-bound process  I/O-bound process thöôøng söû duïng raát ít thôøi gian cuûa CPU, sau ñoù phaûi blocked ñôïi I/O  CPU-bound process taän duïng heát quantum time, sau ñoù quay veà ready queue ⇒ ñöôïc xeáp tröôùc caùc process bò blocked 29Khoa KTMT Time quantum vaø context switch Process time = 10 quantum context switch 0 1 2 3 4 5 6 7 8 9 10 0 106 0 10 12 6 1 0 1 9 30Khoa KTMT Thời gian hoàn thành và quantum time
Thời gian hoàn thành trung bình (average turnaround time) không chắc sẽ được cải thiện khi quantum lớn 631Khoa KTMT Quantum vaø response time
Quantum time phaûi lôùn hôn thôøi gian duøng ñeå xöû lyù clock interrupt (timer) vaø thôøi gian dispatching
Neân lôùn hôn thôøi gian töông taùc trung bình (typical interaction) 32Khoa KTMT Quantum time cho Round Robin*
Khi thực hiện process switch thì OS sẽ sử dụng CPU chứ không phải process của người dùng (OS overhead) – Dừng thực thi, lưu tất cả thông tin, nạp thông tin của process sắp thực thi
Performance tùy thuộc vào kích thước của quantum time (còn gọi là time slice), và hàm phụ thuộc này không đơn giản
Time slice ngắn thì đáp ứng nhanh – Vấn đề: có nhiều chuyển ngữ cảnh. Phí tổn sẽ cao.
Time slice dài hơn thì throughput tốt hơn (do giảm phí tổn OS overhead) nhưng thời gian đáp ứng lớn – Nếu time slice quá lớn, RR trở thành FCFS. 33Khoa KTMT Quantum time cho Round Robin
Quantum time và thời gian cho process switch: – Nếu quantum time = 20 ms và thời gian cho process switch = 5 ms, như vậy phí tổn OS overhead chiếm 5/25 = 20% – Nếu quantum = 500 ms, thì phí tổn chỉ còn ≈ 1%  Nhưng nếu có nhiều người sử dụng trên hệ thống và thuộc loại interactive thì sẽ thấy đáp ứng rất chậm – Tùy thuộc vào tập công việc mà lựa chọn quantum time – Quantum time nên lớn trong tương quan so sánh với thời gian cho process switch – Ví dụ với 4.3 BSD UNIX, quantum time là 1 giây 34Khoa KTMT Round Robin
Nếu có n process trong hàng đợi ready, và quantum time là q, như vậy mỗi process sẽ lấy 1/n thời gian CPU theo từng khối có kích thước lớn nhất là q – Sẽ không có process nào chờ lâu hơn (n - 1)q đơn vị thời gian
RR sử dụng một giả thiết ngầm là tất cả các process đều có tầm quan trọng ngang nhau – Không thể sử dụng RR nếu muốn các process khác nhau có độ ưu tiên khác nhau 35Khoa KTMT Round Robin: nhược điểm
Các process dạng CPU-bound vẫn còn được “ưu tiên” – Ví dụ:  Một I/O-bound process sử dụng CPU trong thời gian ngắn hơn quantum time và bị blocked để đợi I/O. Và  Một CPU-bound process chạy hết time slice và lại quay trở về hàng đợi ready queue (ở phía trước các process đã bị blocked) 36Khoa KTMT 5. Highest Response Ratio Next
Choïn process keá tieáp coù giaù trò RR (Response ratio) lôùn nhaát.
Caùc process ngaén ñöôïc öu tieân hôn (vì service time nhoû) timeservice expected timeservice expected ingspent wait time + =RR 737Khoa KTMT 6. Multilevel Queue Scheduling
Haøng ñôïi ready ñöôïc chia thaønh nhieàu haøng ñôïi rieâng bieät theo moät soá tieâu chuaån nhö – Ñaëc ñieåm vaø yeâu caàu ñònh thôøi cuûa process – Foreground (interactive) vaø background process,
Process ñöôïc gaùn coá ñònh vaøo moät haøng ñôïi, moãi haøng ñôïi söû duïng giaûi thuaät ñònh thôøi rieâng
Heä ñieàu haønh caàn phaûi ñònh thôøi cho caùc haøng ñôïi. – Fixed priority scheduling: phuïc vuï töø haøng ñôïi coù ñoä öu tieân cao ñeán thaâp. Vaán ñeà: coù theå coù starvation. – Time slice: moãi haøng ñôïi ñöôïc nhaän moät khoaûng thôøi gian chieám CPU vaø phaân phoái cho caùc process trong haøng ñôïi khoaûng thôøi gian ñoù. Ví duï: 80% cho haøng ñôïi foreground ñònh thôøi baèng RR vaø 20% cho haøng ñôïi background ñònh thôøi baèng giaûi thuaät FCFS. 38Khoa KTMT Multilevel Queue Scheduling*
Ví dụ phân nhóm các quá trình System Processes Interactive Processes Batch Processes Student Processes Độ ưu tiên thấp nhất Độ ưu tiên cao nhất 39Khoa KTMT 7. Haøng ñôïi phaûn hoài ña caáp Multilevel Feedback Queue
Vaán ñeà cuûa multilevel queue – process khoâng theå chuyeån töø haøng ñôïi naøy sang haøng ñôïi khaùc⇒ khaéc phuïc baèng cô cheá feedback: cho pheùp process di chuyeån moät caùch thích hôïp giöõa caùc haøng ñôïi khaùc nhau.
Multilevel Feedback Queue – Phaân loaïi processes döïa treân caùc ñaëc tính veà CPU-burst – Söû duïng decision mode preemptive – Sau moät khoaûng thôøi gian naøo ñoù, caùc I/O-bound process vaø interactive process seõ ôû caùc haøng ñôïi coù ñoä öu tieân cao hôn coøn CPU-bound process seõ ôû caùc queue coù ñoä öu tieân thaáp hôn. – Moät process ñaõ chôø quaù laâu ôû moät haøng ñôïi coù ñoä öu tieân thaáp coù theå ñöôïc chuyeån ñeán haøng ñôïi coù ñoä öu tieân cao hôn (cô cheá nieân haïn, aging). 40Khoa KTMT 7. Multilevel Feedback Queue
Ví duï: Coù 3 haøng ñôïi – Q0 , duøng RR vôùi quantum 8 ms – Q1 , duøng RR vôùi quantum 16 ms – Q2 , duøng FCFS 41Khoa KTMT 7. Multilevel Feedback Queue (tt)
Ñònh thôøi duøng multilevel feedback queue ñoøi hoûi phaûi giaûi quyeát caùc vaán ñeà sau – Soá löôïng haøng ñôïi bao nhieâu laø thích hôïp? – Duøng giaûi thuaät ñònh thôøi naøo ôû moãi haøng ñôïi? – Laøm sao ñeå xaùc ñònh thôøi ñieåm caàn chuyeån moät process ñeán haøng ñôïi cao hôn hoaëc thaáp hôn? – Khi process yeâu caàu ñöôïc xöû lyù thì ñöa vaøo haøng ñôïi naøo laø hôïp lyù nhaát? 42Khoa KTMT So saùnh caùc giaûi thuaät
Giaûi thuaät ñònh thôøi naøo laø toát nhaát?
Caâu traû lôøi phuï thuoäc caùc yeáu toá sau: – Taàn xuaát taûi vieäc (System workload) – Söï hoã trôï cuûa phaàn cöùng ñoái vôùi dispatcher – Söï töông quan veà troïng soá cuûa caùc tieâu chuaån ñònh thôøi nhö response time, hieäu suaát CPU, throughput, – Phöông phaùp ñònh löôïng so saùnh 843Khoa KTMT Đọc thêm
Policy và Mechanism
Định thời trên hệ thống multiprocessor
Đánh giá giải thuật định thời CPU
Định thời trong một số hệ điều hành thông dụng
Nguồn: Operating System Concepts. Sixth Edition. John Wiley & Sons, Inc. 2002. Silberschatz, Galvin, Gagne