Bài giảng Hệ điều hành (Operating Systems): Chương 1, 2, 3, 4 - TS. Vũ Đức Lung

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

155
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Hệ điều hành (Operating Systems) - Chương 1, 2, 3, 4 gồm có những nội dung chính sau đây: Tổng quan về hệ điều hành, cấu trúc Hệ điều hành, quản lý tiến trình (Processes), định thời CPU. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ điều hành (Operating Systems): Chương 1, 2, 3, 4 - TS. Vũ Đức Lung

Heä Heä Ñieà ieàu Haø Haønh nh Thời gian: TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN - Lý thuyết: 45 tiết KHOA KỸ THUẬT MÁY TÍNH - Thực hành: 30 tiết Điểm số: Heä Ñieàu Haønh - Điểm thi giữa k : 20% - Điểm thực hành hoặc làm bài tiểu luận: 30% - Điểm thi cuối HK: 50% (Operating Systems) • Khoa Kỹ thuật máy tính • GV: TS. Vũ Đức Lung • Email: lungvd@uit.edu.vn 9/14/2010 Vũ Đức Lung 1 9/14/2010 Vũ Đức Lung 2 Nội dung môn học Tài liệ liệu tham khả khảo Chương 1: Tổng quan về hệ điều hành 1. Trần Hạnh Nhi, Lê Khắc Nhiên Ân. Giáo trình hệ Chương 2: Cấu trúc Hệ điều hành ñiều hành. Trung tâm phát triển công nghệ Chương 3: Quản lý tiến trình (Processes) thông tin-ĐHQG.HCM, 2005. Chương 4: Định thời CPU 2. Nguyễn Phú Trường. Giáo trình hệ ñiều hành. ĐH Chương 5: Đồng bộ hóa tiến trình Cần Thơ, 2005. Chương 6: Tắc nghẽn (Deadlocks) 3. Silberschatz, Galvin, Gagne. Operating System Concepts. Sixth edition, John Wiley & Chương 7: Quản lý bộ nhớ Sons,2003 Chương 8: Bộ nhớ ảo 4. Mark E. Russinovich and David A. Solomon, Đọc thêm – tiể tiểu luậ luận: Microsoft Windows Internals, 4th Edition, Chương 9: Hệ tống quản lý tập tin Microsoft Press, 2004. Chương 10: Hệ thống quản lý nhập/xuất Tài Tài liệ liệu chung: chung: Chương 11: Bảo vệ và an toàn hệ thống http://groups.google.com/group/os-vdlung 9/14/2010 Vũ Đức Lung 3 9/14/2010 Vũ Đức Lung 4 1.1. Toå Toång ng quan Chươ Chương ng I: • Giôùi thieäu Tổng quan hệ điều hành – Ñònh nghóa heä ñieàu haønh – Caáu truùc heä thoáng maùy tính – Caùc chöùc naêng chính cuûa heä ñieàu haønh 9/14/2010 Vũ Đức Lung 5 9/14/2010 Vũ Đức Lung 6 1
Ñònh nghóa Ñònh nghóa (tt) tt) • Heä ñieàu haønh laø gì? Hình chính xaùc hôn – Chöông trình trung gian giöõa phaàn Ngöôøi duøng cöùng maùy tính vaø ngöôøi söû duïng, coù chöùc naêng ñieàu khieån vaø phoái hôïp Banking Airline Web browser Application programs veäc söû duïng phaàn cöùng vaø cung caáp system reservation caùc dòch vuï cô baûn cho caùc öùng Compilers Editors Command interpreter duïng. Caùc öùng duïng System programs Operating system • Muïc tieâu Machine language – Giuùp ngöôøi duøng deã daøng söû duïng Heä Ñieàu Haønh Hardware Microprogramming heä thoáng. Physical devices – Quaûn lyù vaø caáp phaùt taøi nguyeân heä Phaàn cöùng thoáng moät caùch hieäu quaû. Hình cuûa Dror G. Feitelson 9/14/2010 Vũ Đức Lung 7 9/14/2010 Vũ Đức Lung 8 Caùc thaønh phaàn cuûa heä thoáng Caùc thaønh phaàn cuûa heä thoáng (tt) tt) Phaàn cöùng (hardware) Bao goàm caùc taøi nguyeân cô baûn cuûa maùy tính nhö CPU, boä nhôù, caùc thieát bò I/O,... Heä ñieàu haønh (operating system) Phaân phoái taøi nguyeân, ñieàu khieån vaø phoái hôïp caùc hoaït ñoäng cuûa caùc chöông trình trong heä thoáng. Chöông trình öùng duïng (application programs) Söû duïng taøi nguyeân heä thoáng ñeå giaûi quyeát moät vaán ñeà tính toaùn naøo ñoù cuûa ngöôøi söû duïng, ví duï: compilers, database systems, video games, business programs. Döõ lieäu 9/14/2010 Vũ Đức Lung 9 9/14/2010 Vũ Đức Lung 10 Caù Caùc chöù chöùc naêng chí chính cuû cuûa OS Các dạng HĐH Phaân chia thôøi gian xöû lyù vaø ñònh thôøi CPU • Same machine, different operating systems: Phoái hôïp vaø ñoàng boä hoaït ñoäng giöõa caùc processes – IBM PC: DOS, Linux, NeXTSTEP, Windows, SCO Unix (coordination & synchronization) – DEC VAX: VMS, Ultrix-32, 4.3 BSD UNIX Quaûn lyù taøi nguyeân heä thoáng (thieát bò I/O, boä nhôù, file chöùa döõ • Same OS, different machines: UNIX lieäu,…) – PC (XENIX 286, APPLE A/UX) – CRAY-Y/MP (UNICOS - AT&T Sys V) Thöïc hieän vaø kieåm soaùt access control, protection – IBM 360/370 (Amdahl UNIX UTS/580, IBM UNIX Duy trì söï nhaát quaùn (integrity) cuûa heä thoáng, kieåm soaùt loãi vaø AIX/ESA) • Windows NT, XP, 2000, 2003 phuïc hoài heä thoáng khi coù loãi (error recovery) – Intel i386 (i486 an NT 4.0), Alpha, PowerPC, MIPS, Cung caáp giao dieän laøm vieäc cho users Itanium 9/14/2010 Vũ Đức Lung 11 9/14/2010 Vũ Đức Lung 12 2
1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH Dưới góc độ loại máy tính Dưới góc độ số chương trình được sử dụng cùng lúc Hệ điều hành dành cho máy MainFrame – Hệ điều hành đơn nhiệm Hệ điều hành dành cho máy Server – Hệ điều hành đa nhiệm Hệ điều hành dành cho máy nhiều CPU Dưới góc độ người dùng (truy xuất tài nguyên cùng lúc) – Một người dùng Hệ điều hành dành cho máy tính cá nhân (PC) – Nhiều người dùng Hệ điều hành dành cho máy PDA (Embedded OS - hệ điều •Mạng ngang hàng hành nhúng) •Mạng có máy chủ: LAN, WAN, ... Hệ điều hành dành cho máy chuyên biệt Hệ điều hành dành cho thẻ chíp (SmartCard) 9/14/2010 Vũ Đức Lung 13 9/14/2010 Vũ Đức Lung 14 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH HEÄ THOÁNG XÖÛ LYÙ ÑÔN CHÖÔNG Dưới góc độ hình thức xử lý –Hệ thống xử lý theo lô Ñôn chöông - Taùc vuï ñöôïc thi haønh tuaàn töï. –Hệ thống chia sẻ - Boä giaùm saùt thöôøng tröïc, –Hệ thống song song - CPU vaø caùc thao taùc nhaäp xuaát, –Hệ thống phân tán - Xöû lyù offline, –Hệ thống xử lý thời gian thực - Ñoàng boä hoùa caùc thao taùc beân ngoaøi - Spooling (Simultaneous Peripheral Operation On Line) Maùy tính Nhaäp chính Xuaát 9/14/2010 Vũ Đức Lung 15 9/14/2010 Vũ Đức Lung 16 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH HEÄ THOÁNG XÖÛ LYÙ ÑA CHÖÔNG • Multiprogrammed systems – Nhieàu coâng vieäc ñöôïc naïp ñoàng thôøi vaøo boä Nhieàu taùc vuï saün saøng thi haønh cuøng moät thôøi ñieåm. 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 Khi moät taùc vuï thöïc hieän I/O, baét ñaàu taùc vuï khaùc. – 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 Boä xöû lyù vaø thieát bò thi haønh toaøn thôøi gian. Ñònh thôøi coâng vieäc (job scheduling): choïn job trong job pool treân ñóa vaø naïp Taùc vuï I/O 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,…) Boä xöû lyù Keát thuùc taùc vuï Baûo veä 9/14/2010 Vũ Đức Lung 17 9/14/2010 Vũ Đức Lung 18 3
1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH 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ù 9/14/2010 Vũ Đức Lung 19 9/14/2010 Vũ Đức Lung 20 HEÄ THOÁNG CHIA XEÛ THÔØI GIAN HEÄ THOÁNG CHIA XEÛ THÔØI GIAN • Time-sharing systems • Yeâu caàu ñoái vôùi OS trong heä thoáng time-sharing – Multiprogrammed systems khoâng cung caáp khaû naêng töông taùc hieäu – Ñònh thôøi coâng vieäc (job scheduling) quaû vôùi users – Quaûn lyù boä nhôù (memory management) – CPU luaân phieân thöïc thi giöõa caùc coâng vieäc • Virtual memory • Moãi coâng vieäc ñöôïc chia moät phaàn nhoû thôøi gian CPU (time slice, – Quaûn lyù caùc quaù trình (process management) quantum time) Ñònh thôøi CPU Ñoàng boä caùc quaù trình (synchronization) • 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) Giao tieáp giöõa caùc quaù trình (process communication) Traùnh deadlock – Moät coâng vieäc chæ ñöôïc chieám CPU khi noù naèm trong boä nhôù chính. – Quaûn lyù heä thoáng file, heä thoáng löu tröõ – Khi caàn thieát, moät coâng vieäc naøo ñoù coù theå ñöôïc chuyeån töø boä nhôù – Caáp phaùt hôïp lyù caùc taøi nguyeân chính ra thieát bò löu tröõ (swapping), nhöôøng boä nhôù chính cho coâng – Baûo veä (protection) vieäc khaùc. 9/14/2010 Vũ Đức Lung 21 9/14/2010 Vũ Đức Lung 22 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH HEÄ THOÁNG ÑA XÖÛ LYÙ HEÄ THOÁNG ÑA XÖÛ LYÙ • Heä thoáng song song (parallel, multiprocessor, hay tightly- coupled system) Hai hoaëc nhieàu boä xöû lyù cuøng chia seû moät boä nhôù. – Nhieàu CPU – Chia seû computer bus, clock Master/Slave : moät boä xöû lyù chính kieåm soaùt moät soá boä xöû lyù – Öu ñieåm I/O • 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- Boä Boä processor system: vì coù theå duøng chung taøi nguyeân (ñóa,…) xöû lyù xöû lyù • Ñ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 Boä nhôù chính 9/14/2010 Vũ Đức Lung 23 9/14/2010 Vũ Đức Lung 24 4
HEÄ THOÁNG ÑA XÖÛ LYÙ 1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH • Phaân loaïi heä thoáng song song HEÄ THOÁNG PHAÂN TAÙN – Ña xöû lyù ñoái xöùng (symmetric multiprocessor - SMP) Nhieàu maùy tính lieân keát vôùi nhau baèng ñöôøng truyeàn • Moãi processor vaän haønh moät identical copy cuûa heä ñieàu thoâng ñaëc bieät. haønh Töông töï heä thoáng ña xöû lyù nhöng khoâng chia xeû boä • Caùc copy giao tieáp vôùi nhau khi caàn nhôù. • (Windows NT, Solaris 5.0, Digital UNIX, OS/2, Linux) – Ña xöû lyù baát ñoái xöùng (asymmetric multiprocessor) Heä thoáng maùy tính 1 Heä thoáng maùy tính 2 • 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 Giao tieáp maïng Giao tieáp maïng slave processors Maïng • (SunOS 4.0) Boä xöû lyù Boä xöû lyù Boä nhôù Boä nhôù 9/14/2010 Vũ Đức Lung 25 9/14/2010 Vũ Đức Lung 26 HEÄ THOÁNG PHAÂN TAÙN HEÄ THOÁNG PHAÂN TAÙN • Heä thoáng phaân taùn (distributed system, loosely-coupled system) • Heä thoáng phaân taùn (tt) – Moãi processor coù boä nhôù rieâng, caùc processor giao tieáp qua caùc keânh Caùc moâ hình heä thoáng phaân taùn noái nhö maïng, bus toác ñoä cao – Client-server – Ngöôøi duøng chæ thaáy moät heä thoáng ñôn nhaát Server: cung caáp dòch vuï – Öu ñieåm Client: coù theå söû duïng dòch vuï cuûa server Chia seû taøi nguyeân (resource sharing) – Peer-to-peer (P2P) Chia seû söùc maïnh tính toaùn (computational sharing) Caùc peer (maùy tính trong heä thoáng) ñeàu ngang haøng nhau Ñoä tin caäy cao (high reliability) Khoâng coù cô sôû döõ lieäu taäp trung Ñoä saün saøng cao (high availability): caùc dòch vuï cuûa heä thoáng ñöôïc Caùc peer laø töï trò cung caáp lieân tuïc cho duø moät thaønh phaàn hardware trôû neân hoûng Vd: Gnutella 9/14/2010 Vũ Đức Lung 27 9/14/2010 Vũ Đức Lung 28 Heä thoáng thôøi gian thöïc Thieát bò caàm tay (real-time system) (handheld 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 • Thieát bò caàm tay (handheld system) khoa hoïc, ñieàu khieån trong y khoa, daây chuyeàn coâng nghieäp, thieát bò gia – Personal digital assistant (PDA): Palm, Pocket-PC duïng, quaân söï – Ñieän thoaïi di ñoäng (cellular phones) – Raøng buoäc veà thôøi gian: hard vaø soft real-time – Ñaëc tröng Phaân loaïi • Boä nhôù nhoû (512 KB – 128 MB) – Hard real-time • Toác ñoä processor thaáp (ñeå ít toán pin) • Haïn cheá (hoaëc khoâng coù) boä nhôù phuï, taát caû döõ lieäu naèm trong boä • Maøn hình hieån thò coù kích thöôùc nhoû vaø ñoä phaân giaûi thaáp. nhôù chính (RAM hoaëc ROM) • Coù theå duøng caùc coâng ngheä keát noái nhö IrDA, Bluetooth, wireless • 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 9/14/2010 caàu meàm deûo hôn veà thôøVũi gian ñaùp öùng Đức Lung 29 9/14/2010 Vũ Đức Lung 30 5
1.3. LÒCH SÖÛ PHAÙT TRIEÅN CUÛA HEÄ ÑIEÀU HAØNH 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 Theá heä 4 (1980 - ) - Löu treân phieáu ñuïc loã -Ra ñôøi maùy tính caù nhaân, IBM PC Theá heä 2 (1955 - 1965) - HÑH MS-DOS, MacOS (Apple Macintosh), MS Windows, OS/1 - Xuaát hieän söï phaân coâng coâng vieäc - Linux, QNX, HÑH maïng,… - 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 31 9/14/2010 Vũ Đức Lung 32 Operating Systems Evolution Windows And Linux Evolution • Windows and Linux kernels are based on foundations IOCS IBSYS developed in the mid-1970s 55 60 CTSS 1970 1980 1990 2000 65 DOS/360 OS/360 MULTICS CP/CM5 RSX-11M 70 UNIX .0 03 Se ow 000 er P TSO 1 0 3. RT-11 v1 rv s X 20 4. CP/M T in 2 75 S N UNIXV.7 NT VMS 1.0 W ows VM DOS/VDSE MVS/370 VM/370 s w d 4.1BSD XENIX MS-DOS 1.0 do 80 SYSTEM III d DR/DOS in SUN OS in 4.2BSD W W 85 VS MVS/XA VM/XA SYSTEM V AIX POSIX OS/2 MACH WIN 3.0 AIX/370 OSF/1 4.3BSD VMS 5.4 WIN 3.1 90 SYSTEM V.4 1970 1980 1990 2000 VS/ESA MVS/ES VM/ESA AIX/ESA SOLARIS 2 95 LINUX 4.4BSD WIN NT WIN 9X lic .0 b v1 n 00 V6 .0 pu .6 v2.2 v2.3 .4 VMS 7.3 WIN 2000 r bo v2 v2 x v2 IX nu IX IX 03 LINUX 2.6 WIN XP UN UN Li SOLARIS 10 UN WIN Server 2003 (see http://www.levenez.com for diagrams showing history of Windows & Unix) 9/14/2010 Vũ Đức Lung 33 9/14/2010 Vũ Đức Lung 34 6
Chöông II: Caáu Truùc Heä Ñieàu Haønh 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh •2.1.1. Quaûn lyù quaù trình (process management) Caùc thaønh phaàn cuûa heä ñieàu haønh - Quaù trình (hay tieán trình – process) laø gì? Caùc dòch vuï heä ñieàu haønh cung caáp - 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 Lôøi goïi heä thoáng (System call) bò I/O,… ñeå hoaøn thaønh coâng vieäc. - Caùc nhieäm vuï cuûa thaønh phaàn Caùc chöông trình heä thoáng (system programs) Taïo vaø huûy quaù trình Caáu truùc heä thoáng Taïm dừng/thöïc thi tieáp (suspend/resume) quaù trình Cung caáp caùc cô cheá Maùy aûo (virtual machine) – ñ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) 9/14/2010 Vũ Đức Lung 1 9/14/2010 Vũ Đức Lung 2 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh •2.1.2. Quaûn lyù boä nhôù chính •2.1.3. Quaûn lyù file (file management) – Boä nhôù chính laø trung taâm cuûa caùc thao taùc, xöû lyù – Heä thoáng file (file system) – Ñeå naâng caoù hieäu suaát söû duïng CPU, heä ñieàu haønh caàn File quaûn lyù boä nhôù thích hôïp Thö muïc – Caùc nhieäm vuï cuûa thaønh phaàn – Caùc dòch vuï maø thaønh phaàn cung caáp Theo doõi, quaûn lyù caùc vuøng nhôù troáng vaø ñaõ caáp phaùt Taïo vaø xoaù file/thö muïc. Quyeát ñònh seõ naïp chöông trình naøo khi coù vuøng nhôù Caùc thao taùc xöû lyù file/thö muïc (mkdir, rename, copy, move, troáng new,…) “AÙnh xaï” file/thö muïc vaøo thieát bò löu tröõ thöù caáp töông öùng Caáp phaùt vaø thu hoài caùc vuøng nhôù khi caàn thieát Sao löu vaø phuïc hoài döõ lieäu 9/14/2010 Vũ Đức Lung 3 9/14/2010 Vũ Đức Lung 4 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh •2.1.4. Quaûn lyù heä thoáng I/O (I/O system management) •2.1.5. Quaûn lyù heä thoáng löu tröõ thöù caáp (secondary storage management) – Che daáu söï khaùc bieät cuûa caùc thieát bò I/O tröôùc – Boä nhôù chính: kích thöôùc nhoû, laø moâi tröôøng chöùa tin khoâng beàn vöõng ngöôøi duø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 – Coù chöùc naêng – Phöông tieän löu tröõ thoâng duïng laø ñóa töø, ñóa quang Cô cheá: buffering, caching, spooling – Nhieäm vuï cuûa heä ñieàu haønh trong quaûn lyù ñóa Cung caáp giao dieän chung ñeán caùc trình ñieàu khieån Quaûn lyù khoâng gian troáng treân ñóa(free space management) thieát bò (device-driver interface) Caáp phaùt khoâng gian löu tröõ (storage allocation) Ñònh thôøi hoïat ñoäng cho ñóa (disk scheduling) Boä ñieàu khieån caùc thieát bò (device driver) phaàn cöùng. 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û 9/14/2010 Vũ Đức Lung 5 9/14/2010 Vũ Đức Lung 6 1
2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh 2.1. Caùc thaønh phaàn cuûa heä ñieàu haønh •2.1.6. Heä thoáng baûo veä •2.1.7. Heä thoáng thoâng dòch leänh Trong heä thoáng cho pheùp nhieàu user hay nhieàu process dieãn ra ñoàng thôøi: – Laø giao dieän chuû yeáu giöõa ngöôøi duøng vaø OS – Kieåm soaùt quaù trình ngöôøi duøng ñaêng nhaäp/xuaát vaø söû duïng heä thoáng • Ví duï: shell, mouse-based window-and-menu – Kieåm soaùt vieäc truy caäp caùc taøi nguyeân trong heä thoáng – Khi user login – Baûo ñaûm nhöõng user/process chæ ñöôïc pheùp söû duïng caùc taøi nguyeân • 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à. daønh cho noù – Caùc leänh ->boä ñieàu khieån leänh ->heä ñieàu haønh – Caùc nhieäm vuï cuûa heä thoáng baûo veä – Caùc leänh coù quan heä vôùi caùc vieäc: Cung caáp cô cheá kieåm soaùt ñaêng nhaäp/xuaát (login, log out) Taïo, huûy, vaø quaûn lyù quaù trình, heä thoáng Phaân ñònh ñöôïc söï truy caäp taøi nguyeân hôïp phaùp vaø baát hôïp phaùp Kieåm soaùt I/O (authorized/unauthorized) Quaûn lyù boä löu tröõ thöù caáp Phöông tieän thi haønh caùc chính saùch (enforcement of policies) Quaûn lyù boä nhôù chính Chính saùch: caàn baûo veä döõ lieäu cuûa ai ñoái vôùi ai Truy caäp heä thoáng file vaø cô cheá baûo maät 9/14/2010 Vũ Đức Lung 7 9/14/2010 Vũ Đức Lung 8 2.2. Caùc dòch vuï heä ñieàu haønh cung caáp 2.2. Caùc dòch vuï heä ñieàu haønh cung caáp – Thöïc thi chöông trình Ngoaøi ra coøn caùc dòch vuï giuùp taêng hieäu suaát cuûa heä thoáng: – Thöïc hieän caùc thao taùcï I/O theo yeâu caàu cuûa chöông trình – Caáp phaùt taøi nguyeân (resource allocation) – Caùc thao taùc treân heä thoáng file • Taøi nguyeân: CPU, boä nhôù chính, tape drives,… • Ñoïc/ghi hay taïo/xoùa file • OS coù caùc routine töông öùng – Trao ñoåi thoâng tin giöõa caùc quaù trình qua hai caùch: – Keá toaùn (accounting) Chia xeû boä nhôù (Shared memory) • Nhaèm löu veát user ñeå tính phí hoaëc ñôn giaûn ñeå thoáng keâ. Chuyeån thoâng ñieäp (Message passing) – Baûo veä (protection) – Phaùt hieän loãi • Hai quaù trình khaùc nhau khoâng ñöôïc aûnh höôûng nhau Trong CPU, boä nhôù, treân thieát bò I/O (döõ lieäu hö, heát giaáy,…) • Kieåm soaùt ñöôïc caùc truy xuaát taøi nguyeân cuûa heä thoáng Do chöông trình: chia cho 0, truy caäp ñeán ñòa chæ boä nhôù khoâng – An ninh (security) cho pheùp. • 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 9 9/14/2010 Vũ Đức Lung 10 2.3. Lôøi goïi heä thoáng (System call) call) 2.4. Caùc chöông trình heä thoáng • Duøng ñeå giao tieáp giöõa quaù trình vaø heä ñieàu haønh Chöông trình heä thoáng (system program, phaân bieät vôùi application – Cung caáp giao dieän giöõa quaù trình vaø heä ñieàu haønh program) goàm • Vd: open, read, write file – Quaûn lyù heä thoáng file: nhö create, delete, rename, list – Thoâng thöôøng ôû daïng thö vieän nhò phaân (binary libraries) hay gioáng – Thoâng tin traïng thaùi: nhö date, time, dung löôïng boä nhôù troá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 – Soaïn thaûo file: nhö file editor xaây döïng döïa treân caùc thö vieän heä thoáng (ví duï Windows API, thö – Hoã trôï ngoân ngöõ laäp trình: nhö compiler, assembler, interpreter vieän GNU C/C++ nhö glibc, glibc++,…) – Naïp, thöïc thi, giuùp tìm loãi chöông trình: nhö loader, debugger – Ba phöông phaùp truyeàn tham soá khi söû duïng system call Qua thanh ghi – Giao tieáp: nhö email, talk, web browser 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 Ngöôøi duøng chuû yeáu laøm vieäc thoâng qua caùc system program (khoâng laøm Qua stack vieäc “tröïc tieáp” vôùi caùc system call) 9/14/2010 Vũ Đức Lung 11 9/14/2010 Vũ Đức Lung 12 2
2.5. Caáu truùc heä thoáng 2.5. Caáu truùc heä thoáng Caáu truùc ñôn giaûn (monolithic) Caáu truùc ñôn giaûn (monolithic) UNIX: goàm hai phaàn coù theå taùch rôøi nhau – MS-DOS: khi thieát keá, do giôùi Nhaân (cung caáp file system, CPU scheduling, memory haïn veà dung löôïng boä nhôù neân management, vaø moät soá chöùc naêng khaùc) vaø system program 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 13 9/14/2010 Vũ Đức Lung 14 2.5. Caáu truùc heä thoáng 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). Caáu truùc phaân taàng: Lôùp döôùi cuøng: hardware Laàn ñaàu tieân ñöôïc aùp duïng cho HÑH THE (Technische Hogeschool Lôùp treân cuøng laø giao tieáp vôùi user Eindhoven) Lôùp treân chæ phuï thuoäc lôùp döôùi Lôùp 5 user programm 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 Lôùp 4 Taïo buffer cho thieát bò I/O Moãi lôùp töông ñöông moät ñoái töôïng tröøu töôïng: caáu truùc döõ lieäu + Lôùp 3 Device driver thao taùc maøn hình thao taùc Lôùp 2 Quaûn lyù boä nhôù 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) Lôùp 1 Laäp lòch CPU Lôùp 0 Phaàn cöùng 9/14/2010 Vũ Đức Lung 15 9/14/2010 Vũ Đức Lung 16 2.5. Caáu truùc heä thoáng 2.5. Caáu truùc heä thoáng Vi nhaân: phaân chia module theo microkernel (CMU Mach OS, 1980) Vi nhaân: Chuyeån moät soá chöùc naêng cuûa OS töø kernel space sang user space - Lôïi ích: deã môû roäng HÑH Thu goïn kernel => microkernel, microkernel chæ bao goàm caùc chöùc naêng - Moät soá HÑH hieän ñaïi söû duïng vi nhaân: toái thieåu nhö quaûn lyù quaù trình, boä nhôù vaø cô cheá giao tieáp giöõa caùc quaù + Tru64 UNIX (Digital UNIX tröôùc ñaây): nhaân Mach trình + Apple MacOS Server : nhaân Mach Giao tieáp giöõa caùc module qua cô cheá truyeàn thoâng ñieäp + 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 moät module + Windows NT: chaïy caùc öùng duïng khaùc nhau win32, OS/2, POSIX Application Application OS/2 POSIX POSIX (Portable OS for uniX) OS/2 application File application application application File OS/2 POSIX POSIX server server OS/2 server server server server Microkernel 9/14/2010 Vũ Đức Lung 17 9/14/2010 Vũ Đức Lung 18 3
2.6. Maùy aûo 2.6. Maùy aûo • Töø OS layer ñeán maùy aûo (virtual machine) Hieän thöïc yù nieäm VM – Laøm theá naøo ñeå thöïc thi moät chöông trình processes MS-DOS treân moät heä thoáng Sun vôùi heä ñieàu haønh Solaris ? Intel x86 Application processes processes 1. Taïo moät maùy aûo Intel beân treân heä ñieàu Intel x86 VM processes haønh Solaris vaø heä thoáng Sun VM interpretation programming kernel kernel kernel interface VM1 VM2 VM3 2. Caùc leänh Intel (x86) ñöôïc maùy aûo Solaris kernel kernel Virtual-machine Intel chuyeån thaønh leänh töông öùng cuûa Sun hardware implementation heä thoáng Sun. hardware hardware Non-virtual machine Virtual machine system model system model 9/14/2010 Vũ Đức Lung 19 9/14/2010 Vũ Đức Lung 20 4
Chö Chöông III: Tieá Tieán trì trình (Process) 3.1. Khaù Khaùi nieä nieäm cô baû baûn Khaùi nieäm cô baûn Caùi gì goïi caùc hoaït ñoäng cuûa CPU? – Heä thoáng boù (Batch system): jobs Traïng thaùi quaù trình – Time-shared systems: user programs, tasks Khoái ñieàu khieån quaù trình (Process control block) – Caùc hoaït ñoäng laø töông töï => goïi laø process Ñònh thôøi quaù trình (Process Scheduling) Quaù trình (process) Caùc taùc vuï ñoái vôùi quaù trình – moät chöông trình ñang thöïc thi Söï coäng taùc giöõa caùc quaù trình Giao tieáp giöõa caùc quaù trình Moät quaù trình bao goàm – Text section (program code), data section (chöùa global variables) – program counter (PC), process status word (PSW), stack pointer (SP), memory management registers,… Khoa KTMT Vũ Đức Lung 1 Khoa KTMT Vũ Đức Lung 2 3.1. Khaù Khaùi nieä nieäm cô baû baûn 3.1. Khaù Khaùi nieä nieäm cô baû baûn Caùc böôùc naïp chöông trình vaøo boä nhôù chöông trình => quaù trình Duøng load module ñeå bieåu dieãn chöông trình thöïc thi ñöôïc Layout luaän lyù cuûa process image Executable binary file Process image in (load module) main memory start address program program code code data data stack Khoa KTMT Vũ Đức Lung 3 Khoa KTMT Vũ Đức Lung 4 3.1. Khaù Khaùi nieä nieäm cô baû baûn 3.2.Traï 3.2.Traïng ng thaù thaùi quaù quaù trì trình Khôû Khôûi taï taïo quaù quaù Caùc traïng thaùi cuûa quaù trình (process states): trì trình – new: quaù trình vöøa ñöôïc taïo Caùc böôùc heä ñieàu haønh khôûi taïo quaù trình – ready: quaù trình ñaõ coù ñuû taøi nguyeân, chæ coøn caàn CPU – Caáp phaùt moät ñònh danh duy nhaát (process number hay process – running: caùc leänh cuûa quaù trình ñang ñöôïc thöïc thi identifier, pid) cho quaù trình – waiting: hay laø blocked, quaù trình ñôïi I/O hoaøn taát, tín hieäu. – Caáp phaùt khoâng gian nhôù ñeå naïp quaù trình – terminated: quaù trình ñaõ keát thuùc. – 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,…) Khoa KTMT Vũ Đức Lung 5 Khoa KTMT Vũ Đức Lung 6 1
3.2.Traï 3.2.Traïng ng thaù thaùi quaù quaù trì trình 3.2.Traï 3.2.Traïng ng thaù thaùi quaù quaù trì trình Chuyeån ñoåi giöõa caùc traïng thaùi cuûa quaù trình Ví duï duï Chuoãi traïng thaùi cuûa quaù /* test.c */ trình test nhö sau (tröôøng hôïp new terminated terminated int main(int argc, char** argv) { toát nhaát): new admit dispatch exit printf(“Hello world\n"); – new exit(0); } – ready ready ready running – running running Bieân dòch chöông trình trong Linux gcc test.c –o test – waiting (do chôø I/O khi goïi printf) interrupt Thöïc thi chöông trình test – ready I/O or event I/O or ./test – running completion event wait waiting Trong heä thoáng seõ coù moät quaù trình test – terminated waiting ñöôïc taïo ra, thöïc thi vaø keát thuùc. Khoa KTMT Vũ Đức Lung 7 Khoa KTMT Vũ Đức Lung 8 3.3.Process control block 3.3.Process control block Ñaõ thaáy laø moãi quaù trình trong heä thoáng ñeàu ñöôïc caáp phaùt moät Process Löu ñoà Control Block (PCB) chuyeån CPU PCB laø moät trong caùc caáu truùc döõ lieäu quan töø quaù trình troïng nhaát cuûa heä ñieàu haønh vaø goàm: naøy ñeán quaù trình khaùc - 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 Khoa KTMT Vũ Đức Lung 9 Khoa KTMT Vũ Đức Lung 10 Yeâu caà caàu ñoái vôù vôùi heä heä ñieà ieàu haø haønh nh veà veà quaû quaûn lyù lyù quaù quaù trì trình Quaû Quaûn lyù lyù caù caùc quaù quaù trì trình: nh: caù caùc haø haøng n g ñ ô ïi Hoã trôï söï thöïc thi luaân phieân giöõa nhieàu quaù trình Ví duï caùc PCB – Hieäu suaát söû duïng CPU – Thôøi gian ñaùp öùng running 7 process number Phaân phoái taøi nguyeân heä thoáng hôïp lyù – traùnh deadlock, trì hoaõn voâ haïn ñònh,… ready Cung caáp cô cheá giao tieáp vaø ñoàng boä hoaït ñoäng caùc quaù trình 11 4 2 17 Cung caáp cô cheá hoã trôï user taïo/keát thuùc quaù trình waiting 19 11 Coù gì sai trong ví duï? Khoa KTMT Vũ Đức Lung 11 Khoa KTMT Vũ Đức Lung 12 2
3.4. Ñònh thôø thôøi quaù quaù trì trình (Process Caù Caùc haø haøng ng ñôïi ñònh thôø thôøi (Scheduling Scheduling) queues) Taïi sao phaûi ñònh thôøi? Haøng ñôïi coâng vieäc-Job queue – Ña chöông (Multiprogramming) Haøng ñôïi saün Coù vaøi quaù trình chaïy taïi caùc thôøi ñieåm saøng-Ready queue Muïc tieâu: taän duïng toái ña CPU Haøng ñôïi thieát bò- Device queues – 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á khaùi nieäm cô baûn – Caùc boä ñònh thôøi (scheduler) – Caùc haøng ñôïi ñònh thôøi (scheduling queue) Khoa KTMT Vũ Đức Lung 13 Khoa KTMT Vũ Đức Lung 14 Caù Caùc haø haøng ng ñôïi ñònh thôø thôøi (Scheduling 3.5. Boä Boä ñònh thôø thôøi (Scheduler) queues) Boä ñònh thôøi coâng vieäc (Job scheduler) hay boä ñònh thôøi daøi (long-term scheduler) Boä ñònh thôøi CPU hay boä ñònh thôøi ngaén Caùc quaù trình coù theå moâ taû nhö: – 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 Löu ñoà haøng ñôïi cuûa ñònh thôøi quaù trình Khoa KTMT Vũ Đức Lung 15 Khoa KTMT Vũ Đức Lung 16 Boä Boä ñònh thôø thôøi trung gian(medium- gian(medium-term scheduling) 3.6. Caù Caùc taù taùc vuï vuï ñoái vôù vôùi quaù quaù trì trình Ñoâi khi heä ñieàu haønh (nhö time-sharing system) coù theâm Taïo quaù trình môùi (process creation) medium-term scheduling ñeå ñieàu chænh möùc ñoä ña chöông cuûa – Moät quaù trình coù theå taïo nhieàu quaù trình môùi thoâng qua moät lôøi heä thoáng goïi heä thoáng create-process (vd: haøm fork trong Unix) Medium-term scheduler Ví duï: (Unix) Khi user ñaêng nhaäp heä thoáng, moät command interpreter (shell) seõ ñöôïc taïo ra cho user – chuyeån quaù trình töø boä nhôù sang ñóa (swap out) Quaù trình ñöôïc taïo laø quaù trình con cuûa quaù trình taïo (quaù trình – chuyeån quaù trình töø ñóa vaøo boä nhôù (swap in) cha). Quan heä cha-con ñònh nghóa moät caây quaù trình. Khoa KTMT Vũ Đức Lung 17 Khoa KTMT Vũ Đức Lung 18 3
Caây quaù quaù trì trình trong Linux/Unix 3.6.Caù 3.6.Caùc taù taùc vuï vuï ñoái vôù vôùi quaù quaù trì trình Ví duï Taïo quaù trình 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. Khoa KTMT Vũ Đức Lung 19 Khoa KTMT Vũ Đức Lung 20 Veà Veà quan heä heä cha/con Ví duï duï taï taïo process vôù vôùi fork() #include Khoâng gian ñòa chæ (address space) #include int main (int argc, char *argv[]){ – Khoâng gian ñòa chæ cuûa quaù trình con ñöôïc nhaân baûn töø cha int pid; – Khoâng gian ñòa chæ cuûa quaù trình con ñöôïc khôûi taïo töø template. /* create a new process */ pid = fork(); Ví duï trong UNIX/Linux – System call fork() taïo moät quaù trình môùi if (pid > 0){ printf(“This is parent process”); – System call exec() duøng sau fork() ñeå naïp moät chöông trình môùi wait(NULL); vaøo khoâng gian nhôù cuûa quaù trình môùi exit(0); } else if (pid == 0) { printf(“This is child process”); execlp(“/bin/ls”, “ls”, NULL); ñoàng boä exit(0); } else { printf(“Fork error\n”); exit(-1); } } Khoa KTMT Vũ Đức Lung 21 Khoa KTMT Vũ Đức Lung 22 3.6.Caù 3.6.Caùc taù taùc vuï vuï ñoái vôù vôùi quaù quaù trì trình (tt) tt) 3.7. Coä Coäng ng taù taùc giö giöõa caù caùc quaù quaù trì trình Taïo quaù trình môùi Trong quaù trình thöïc thi, caùc quaù trình coù theå coäng taùc (cooperate) ñeå hoaøn thaønh coâng vieäc Keát thuùc quaù trình Caùc quaù trình coäng taùc ñeå – Quaù trình töï keát thuùc – Chia seû döõ lieäu (information sharing) Quaù trình keát thuùc khi thöïc thi leänh cuoái vaø goïi system routine – Taêng toác tính toaùn (computational speedup) exit 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 – Quaù trình keát thuùc do quaù trình khaùc (coù ñuû quyeàn, vd: quaù trình – Thöïc hieän moät coâng vieäc chung cha cuûa noù) Xaây döïng moät phaàn meàm phöùc taïp baèng caùch chia thaønh caùc Goïi system routine abort vôùi tham soá laø pid (process identifier) module/process hôïp taùc nhau cuûa quaù trình caàn ñöôïc keát thuùc Söï coäng taùc giöõa caùc quaù trình yeâu caàu heä ñieàu haønh hoã trôï 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 cheá giao tieáp vaø cô cheá ñoàng boä hoaït ñoäng cuûa caùc quaù trình thuùc (vuøng nhôù, I/O buffer,…) Khoa KTMT Vũ Đức Lung 23 Khoa KTMT Vũ Đức Lung 24 4
Baø Baøi toaù toaùn ngö ngöôøi saû saûn xuaá xuaát-ngö ngöôøi tieâu thuï thuï 3.8.Giao tieá tieáp lieân quaù quaù trì trình (producer- (producer-consumer ) (Interprocess communication- communication-IPC) Ví duï coäng taùc giöõa caùc quaù trình: baøi toaùn producer-consumer IPC laø cô cheá cung caáp bôûi heä ñieàu haønh nhaèm giuùp caùc quaù – Producer taïo ra caùc döõ lieäu vaø consumer tieâu thuï, söû duïng caùc döõ trình lieäu ñoù. Söï trao ñoåi thoâng tin thöïc hieän qua buffer – giao tieáp vôùi nhau unbounded buffer: kích thöôùc buffer voâ haïn (khoâng thöïc teá). – vaø ñoàng boä hoaït ñoäng bounded buffer: kích thöôùc buffer coù haïn. maø khoâng caàn chia seû khoâng gian ñòa chæ – Producer vaø consumer phaûi hoaït ñoäng ñoàng boä vì IPC coù theå ñöôïc cung caáp bôûi message passing system 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. Khoa KTMT Vũ Đức Lung 25 Khoa KTMT Vũ Đức Lung 26 Heä Heä thoá thoáng ng truyeà truyeàn thoâng ñieä ieäp Tieå Tieåu trì trình (luoà luoàng) ng) - Thread Message passing system Laøm theá naøo ñeå caùc quaù trình giao tieáp nhau? Caùc vaán ñeà: Tieåu trình(tieán trình nheï-lightweight process): laø moät ñôn vò cô – Ñaët teân (Naming) baûn söû duïng CPU, goàm: Giao tieáp tröïc tieáp – Thread ID, PC, Registers, stack vaø chia seû chung code, data, – send(P, msg): göûi thoâng ñieäp ñeán quaù trình P resources (files) – 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 Khoa KTMT Vũ Đức Lung 27 Khoa KTMT Vũ Đức Lung 28 PCB vaø vaøTCB TCB trong moâ hình Lôï Lôïi ích cuû cuûa tieá tieán trì trình ña luoà luoàng ng multithreads PCB Ñaùp öùng nhanh: Cho pheùp chöông trình tieáp tuïc thöïc thi khi moät pid Thread Control Block TCB boä phaän bò khoùa hoaëc moät hoaït ñoäng daøi Threads list Context tid Chia seû taøi nguyeân: tieát kieäm khoâng gian nhôù (Mem, global State Kinh teá: taïo vaø chuyeån ngöõ caûnh nhanh hôn tieán trình ressources…) (State, details) Relatives VD: trong Solaris 2, taïo process chaäm hôn 30 laàn, chuyeån chaäm Context hôn 5 laàn ( Dad, children) (IP, local stack…) Scheduling statistic Trong multiprocessor: coù theå thöïc hieän song song Khoa KTMT Vũ Đức Lung 29 Khoa KTMT Vũ Đức Lung 30 5
Tieå Tieåu trì trình ngö ngöôøi duø duøng ng (User thread) Tiể Tiểu trì trình hạt nhaân(Kernel thread) T1 T2 T3 User mode LWP1 LWP2 T1 T2 User mode System call Kernel mode P2 Kernel HDH P1 mode Kernel Khái niệm tiểu trình được hỗ trợ bởi một thư viện hoạt động trong user mode Khái niệm tiểu trình được xây dựng bên trong hạt nhân Khoa KTMT Vũ Đức Lung 31 Khoa KTMT Vũ Đức Lung 32 Khoa KTMT Vũ Đức Lung 33 6
Chö Chöông IV: Ñònh thôø thôøi CPU Khaùi nieäm cô baûn Khaùi nieäm cô baûn Trong caùc heä thoáng multitasking Caùc boä ñònh thôøi – Thöïc thi nhieàu chöông trình ñoàng thôøi laøm taêng hieäu suaát heä – long-term, mid-term, short-term thoáng. Caùc tieâu chuaån ñònh thôøi CPU Caùc giaûi thuaät ñònh thôøi – Taïi moãi thôøi ñieåm, chæ coù moät process ñöôïc thöïc thi. Do ñoù, – First-Come, First-Served (FCFS) caàn phaûi giaûi quyeát vaán ñeà phaân chia, löïa choïn process thöïc – Round-Robin (RR) thi sao cho ñöôïc hieäu quaû nhaát → chieán löôïc ñònh thôøi CPU. – Shortest Job First (SJF) vaø Shortest Remaining Time First (SRTF) Ñònh thôøi CPU – Priority Scheduling – Choïn moät process (töø ready queue) thöïc thi. – Highest Response Ratio Next (HRRN) – Vôùi moät multithreaded kernel, vieäc ñònh thôøi CPU laø do OS – Multilevel Queue choïn kernel thread ñöôïc chieám CPU. – Multilevel Feedback Queue Khoa KTMT 1 Khoa KTMT 2 Caùc boä ñònh thôøi Caùc boä ñònh thôøi new new Long-term scheduling Long-term Long-term – Xaùc ñònh chöông trình naøo ñöôïc chaáp nhaän naïp vaøo heä thoáng scheduling scheduling ñeå thöïc thi – Ñieàu khieån möùc ñoä multiprogramming cuûa heä thoáng Medium-term – Long term scheduler thöôøng coá gaéng duy trì xen laãn CPU-bound suspended scheduling vaø I/O-bound process suspended ready Short-term ready ready ready scheduling Medium-term scheduling – Process naøo ñöôïc ñöa vaøo (swap in0, ñöa ra khoûi (swap out) boä nhôù chính running running – Ñöôï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ôù. Medium-term suspended suspended scheduling blocked blocked terminated blocked blocked terminated Khoa KTMT 3 Khoa KTMT 4 Caùc boä ñònh thôøi (tt) Dispatcher • Short term scheduling Dispatcher seõ chuyeån quyeàn ñieàu khieån CPU veà cho Xaùc ñònh process naøo trong ready queue seõ ñöôïc chieám CPU process ñöôïc choïn bôûi boä ñònh thôøi ngaén haïn ñeå thöïc thi keá tieáp (coøn ñöôïc goïi laø ñònh thôøi CPU, CPU Bao goàm: scheduling) – Chuyeån ngöõ caûnh (söû duïng thoâng tin ngöõ caûnh trong PCB) Short term scheduler coøn ñöôïc goïi vôùi teân khaùc laø dispatcher – Chuyeån cheá ñoä ngöôøi duøng Boä ñònh thôøi short-term ñöôïc goïi moãi khi coù moät trong caùc söï – Nhaûy ñeán vò trí thích hôïp trong chöông trình öùng duïng ñeå khôûi kieän/interrupt sau xaûy ra: ñ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 – Ngắt thôøi gian (clock interrupt) – Dispatch latency: thôøi gian maø dispatcher döøng moät process vaø – Ngaét ngoaïi vi (I/O interrupt) khôûi ñoäng moät process khaùc – Lôøi goïi heä thoáng (operating system call) – Signal Chöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn Khoa KTMT 5 Khoa KTMT 6 1
Caùc tieâu chuaån ñònh thôøi CPU Hai yeáu toá cuûa giaûi thuaät ñònh thôøi User-oriented 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 – 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- döïa treân ñoä öu tieân, yeâu caàu veà taøi nguyeân, ñaëc ñieåm sharing, interactive system) → cöïc tieåu thöïc thi cuûa process,…), ví duï – Thôøi gian quay voøng (hoaøn thaønh) (Turnaround time): khoaûng thôøi • w = toång thôøi gian ñôïi trong heä thoáng gian töø luùc moät process ñöôïc naïp vaøo heä thoáng ñeán khi process • e = thôøi gian ñaõ ñöôïc phuïc vuï ñoù keát thuùc → cöïc tieåu • s = toång thôøi gian thöïc thi cuûa process (bao goàm caû “e”) – 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. Khoa KTMT 7 Khoa KTMT 8 Hai yeáu toá cuûa giaûi thuaät ñònh thôøi (tt) Preemptive vaø Non-preemptive Cheá ñoä quyeát ñònh (decision mode): choïn thôøi ñieåm thöïc Hàm định thời được thực hiện khi hieän haøm choïn löïa ñeå ñònh thôøi. Coù hai cheá ñoä (1) Chuyển từ trạng thái running sang waiting (2) Chuyển từ trạng thái running sang ready – Khoâng tröng duïng (Non-preemptive) (3) Chuyển từ trạng thái waiting, new sang ready Khi ôû traïng thaùi running, process seõ thöïc thi cho (4) Kết thúc thực thi ñeán khi keát thuùc hoaëc bò blocked do yeâu caàu I/O 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 duïng (Preemptive) Trường hợp 1, 4 được gọi là định thời nonpreemptive Process ñang thöïc thi (traïng thaùi running) coù theå bò Trường hợp 2, 3 được gọi là định thời preemptive ngaét nöûa chöøng vaø chuyeån veà traïng thaùi ready bôûi heä ñieàu haønh Thực hiện cơ chế nào khó hơn? Tại sao? 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. Khoa KTMT 9 Khoa KTMT 10 Khaûo saùt giaûi thuaät ñònh thôøi 1. First-Come First-Served (FCFS) load store 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 add store CPU burst CPU tröôùc; Process seõ thöïc thi ñeán khi keát thuùc hoaëc bò blocked do I/O moät chu kyø read from file CPU-I/O Cheá ñoä quyeát ñònh: non-preemptive algorithm Arrival Service wait for I/O I/O burst Process Hieän thöïc : söû duïng haøng ñôïi FIFO (FIFO queues) Time Time – Tieán trình ñi vaøo ñöôïc theâm vaøo cuoái haøng ñôïi inc store 1 0 3 – Tieán trình ñöôïc löïa choïn ñeå xöû lyù ñöôïc laáy töø ñaàu cuûa queues CPU burst write to file 2 2 6 wait for I/O I/O burst 3 4 4 0 5 10 15 20 load store 4 6 5 add store CPU burst P1 5 8 2 read from file P2 P3 wait for I/O I/O burst P4 P5 run add 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 Khoa KTMT 11 Khoa KTMT 12 2
FCFS Scheduling FCFS Scheduling Ví duï : Giaû söû thöù töï vaøo cuûa caùc tieán Ví duï: Giaû söû thôøi gian vaøo cuûa caùc tieán trình laø trình laø Process Burst Time P2, P3, P1 Process Burst Time P1, P2, P3 P1 24 Thôøi gian chôø : P1 24 Thôøi gian chôø P1 = 6; P2 = 0; P3 = 3; P1 = 0; P2 3 Thôøi gian chôø trung bình P2 3 P2 = 24; P3 3 (6+0+3)/3 = 3 , toát hôn.. P3 3 P3 = 27; Thôøi gian chôø trung bình (0+24+27)/3 = 17 Gantt Chart for Schedule Gantt Chart for Schedule P1 P2 P3 P2 P3 P1 0 24 27 30 0 3 6 30 Khoa KTMT 13 Khoa KTMT 14 2. Shortest-Job-First(SJF) Scheduling 2. Shortest-Job-First(SJF) Scheduling Ñònh thôøi bieåu coâng vieäc ngaén nhaát tröôùc Hai hình thöùc (Schemes): Khi CPU ñöôïc töï do, noù seõ caáp phaùt cho tieán trình yeâu caàu ít – Scheme 1: Non-preemptive( tieán trình ñoäc quyeàn CPU) thôøi gian nhaát ñeå keát thuùc ( tieán trình ngaén nhaát) Khi CPU ñöôïc trao cho quaù trình noù khoâng nhöôøng cho ñeán Lieân quan ñeán chieàu daøi thôøi gian söû duïng CPU cho laàn tieáp khi noù keát thuùc chu kyø xöû lyù cuûa noù theo cuûa moãi tieán trình. Söû duïng nhöõng chieàu daøi naøy ñeå laäp – Scheme 2: Preemptive( tieán trình khoâng ñoäc quyeàn) lòch cho tieán trình vôùi thôøi gian ngaén nhaát. 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 Khoa KTMT 15 Khoa KTMT 16 Preemptive SJF Scheduling Non-Preemptive SJF Scheduling (hay Sortest Remaining Time First - SRTF) Ví duï : Ví duï 1: Process Arrival TimeBurst Time Process Arrival TimeBurst Time P1 0 7 P1 0 7 P2 2 4 P2 2 4 P3 4 1 P3 4 1 P4 5 4 P4 5 4 Gantt Chart for Schedule VD2: P1 P3 P2 P4 Gantt Chart for Schedule Process Arrival TimeBurst Time P1 0 8 0 P1 P2 P3 P2 P4 P1 7 8 12 16 P2 1 4 Average waiting time = (0+6+3+7)/4 = 4 0 2 4 5 7 11 16 P3 2 9 Average waiting time = P4 3 5 (9+1+0+2)/4 = 3 Khoa KTMT 17 Khoa KTMT 18 3
Nhaän xeùt veà giaûi thuaät SJF 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 Tương ứng với mỗi process cần có độ dài của CPU burst tiếp theo process coù CPU-burst lôùn khi coù nhieàu process vôùi CPU- Hàm lựa chọn: chọn process có độ dài CPU burst nhỏ nhất burst nhoû ñeán heä thoáng. Chứng minh được: SJF tối ưu trong việc giảm thời gian đợi trung Cô cheá non-preemptive khoâng phuø hôïp cho heä thoáng bình time sharing (interactive) Nhược điểm: Cần phải ước lượng thời gian cần CPU tiếp theo của process Giaûi thuaät SJF ngaàm ñònh ra ñoä öu tieân theo burst time Giải pháp cho vấn đề này? 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 Khoa KTMT 19 Khoa KTMT 20 Nhaän xeùt veà giaûi thuaät SJF Dự đoán thời gian sử dụng CPU (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ứ Độ dài CPU burst Nhưng thông thường những CPU burst càng mới càng phản đo được á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) Độ dài CPU burst dự đoán, với a = ½ và τ0 = 10 – τ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. Khoa KTMT 21 Khoa KTMT 22 3. Priority Scheduling Gaùn ñoä öu tieân Moãi process seõ ñöôïc gaùn moät ñ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ä CPU seõ ñöôïc caáp cho process coù ñoä öu tieân cao nhaát öu tieân laø thôøi-gian-söû-duïng-CPU-döï-ñoaùn Ñònh thôøi söû duïng ñoä öu tieân coù theå: Gaùn ñoä öu tieân coøn döïa vaøo: – Preemptive hoaëc – Yeâu caàu veà boä nhôù – Nonpreemptive – 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 Khoa KTMT 23 Khoa KTMT 24 4