Bài giảng Hệ điều hành Operating Systems: Chương 1, 2, 3, 4

HeHeää ÑÑieieààuu HaHaøønhnh

Thời gian:

- Lý thuyết: 45 tiết - Thực hành: 30 tiết

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN KHOA KỸ THUẬT MÁY TÍNH

Điểm số:

- Đ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%

Heä Ñieàu Haønh (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

9/14/2010

Vũ Đức Lung

NNộộii dung

dung mônmôn hhọọcc

TTààii liliệệuu thamtham khkhảảoo

1. Trần Hạnh Nhi, Lê Khắc Nhiên Ân. Giáo trình hệ ñiều hành. Trung tâm phát triển công nghệ thông tin-ĐHQG.HCM, 2005.

2. Nguyễn Phú Trường. Giáo trình hệ ñiều hành. ĐH

Cần Thơ, 2005.

3. Silberschatz, Galvin, Gagne. Operating System

Concepts. Sixth edition, John Wiley & Sons,2003

4. Mark E. Russinovich and David A. Solomon, Microsoft Windows Internals, 4th Edition, Microsoft Press, 2004.

TàTàii liliệệuu chung chung:: http://groups.google.com/group/os-vdlung

Chương 1: Tổng quan về hệ điều hành Chương 2: Cấu trúc Hệ điều hành Chương 3: Quản lý tiến trình (Processes) Chương 4: Định thời CPU Chương 5: Đồng bộ hóa tiến trình Chương 6: Tắc nghẽn (Deadlocks) Chương 7: Quản lý bộ nhớ Chương 8: Bộ nhớ ảo ĐĐọọcc thêmthêm –– titiểểuu luluậậnn:: Chương 9: Hệ tống quản lý tập tin Chương 10: Hệ thống quản lý nhập/xuất Chương 11: Bảo vệ và an toàn hệ thống

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

1.1. ToToåångng quanquan 1.1.

• Giôùi thieäu

– Ñònh nghóa heä ñieàu haønh

ChChươươngng I:I: TTổổngng quanquan hhệệ đđiiềềuu hhàànhnh

– 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

9/14/2010

Vũ Đức Lung

nghóa ÑònhÑònh nghóa

ÑònhÑònh nghóa

nghóa ((tttt))

Hình chính xaùc hôn

Application programs

Web browser

Banking system

Airline reservation

Compilers

Editors

Command interpreter

System programs

• Heä ñieàu haønh laø gì? Ngöôøi duøng – Chöông trình trung gian giöõa phaàn

Operating system

Machine language

Hardware

Microprogramming

Physical devices

Hình cuûa Dror G. Feitelson

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

Caùc thaønh phaàn cuûa heä thoáng

CaùcCaùc thaønh

thaønh phaàn

phaàn cuûacuûa heäheä thoáng

thoáng ((tttt))

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 veäc söû duïng phaàn cöùng vaø cung caáp caùc dòch vuï cô baûn cho caùc öùng duïng. Caùc öùng duïng • Muïc tieâu Heä Ñieàu Haønh – Giuùp ngöôøi duøng deã daøng söû duïng heä thoáng. Phaàn cöùng – Quaûn lyù vaø caáp phaùt taøi nguyeân heä thoáng moät caùch hieäu quaû.

(cid:1) 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,... (cid:1) 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. (cid:1) Chöông trình öùng duïng (application programs)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

CaCaùùcc chchöùöùcc naêng

naêng chchíínhnh cucuûûaa OSOS

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. (cid:1) Döõ lieäu

CácCác dạng

dạng H HĐĐHH

(cid:1) Phaân chia thôøi gian xöû lyù vaø ñònh thôøi CPU

•

(cid:1) Phoái hôïp vaø ñoàng boä hoaït ñoäng giöõa caùc processes

(coordination & synchronization)

•

(cid:1) Quaûn lyù taøi nguyeân heä thoáng (thieát bò I/O, boä nhôù, file chöùa döõ

lieäu,…)

(cid:1) Thöïc hieän vaø kieåm soaùt access control, protection

Same machine, different operating systems: – IBM PC: DOS, Linux, NeXTSTEP, Windows, SCO Unix – DEC VAX: VMS, Ultrix-32, 4.3 BSD UNIX Same OS, different machines: UNIX – PC (XENIX 286, APPLE A/UX) – CRAY-Y/MP (UNICOS - AT&T Sys V) – IBM 360/370 (Amdahl UNIX UTS/580, IBM UNIX

AIX/ESA)

(cid:1) Duy trì söï nhaát quaùn (integrity) cuûa heä thoáng, kieåm soaùt loãi vaø

• 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,

Itanium

(cid:1) Cung caáp giao dieän laøm vieäc cho users

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

Dưới góc độ số chương trình được sử dụng cùng lúc

Dưới góc độ người dùng (truy xuất tài nguyên cùng lúc)

– Hệ điều hành đơn nhiệm – Hệ điều hành đa nhiệm

•Mạng ngang hàng •Mạng có máy chủ: LAN, WAN, ...

Dưới góc độ loại máy tính (cid:2)Hệ điều hành dành cho máy MainFrame (cid:2)Hệ điều hành dành cho máy Server (cid:2)Hệ điều hành dành cho máy nhiều CPU (cid:2)Hệ điều hành dành cho máy tính cá nhân (PC) (cid:2)Hệ điều hành dành cho máy PDA (Embedded OS - hệ điều hành nhúng) (cid:2)Hệ điều hành dành cho máy chuyên biệt (cid:2)Hệ điều hành dành cho thẻ chíp (SmartCard)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

HEÄ THOÁNG XÖÛ LYÙ ÑÔN CHÖÔNG

(cid:3) Ñôn chöông

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

– Một người dùng – Nhiều người dùng

Xuaát

Nhaäp

Maùy tính chính

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

–Hệ thống xử lý thời gian thực - Taùc vuï ñöôïc thi haønh tuaàn töï. - Boä giaùm saùt thöôøng tröïc, - CPU vaø caùc thao taùc nhaäp xuaát, - Xöû lyù offline, - Ñoàng boä hoùa caùc thao taùc beân ngoaøi - Spooling (Simultaneous Peripheral Operation On Line)

HEÄ THOÁNG XÖÛ LYÙ ÑA CHÖÔNG

(cid:3) Nhieàu taùc vuï saün saøng thi haønh cuøng moät thôøi ñieåm.

(cid:3) Khi moät taùc vuï thöïc hieän I/O, baét ñaàu taùc vuï khaùc.

• 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)

(cid:3) Boä xöû lyù vaø thieát bò thi haønh toaøn thôøi gian.

– Yeâu caàu ñoái vôùi heä ñieàu haønh

Taùc vuï

I/O

Boä xöû lyù

Keát thuùc taùc vuï

(cid:4) Ñò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.

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

(cid:4) Quaûn lyù boä nhôù (memory management) (cid:4) Ñònh thôøi CPU (CPU scheduling) (cid:4) Caáp phaùt taøi nguyeân (ñóa, maùy in,…) (cid:4) Baûo veä

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

HEÄ THOÁNG CHIA XEÛ THÔØI GIAN

(cid:3) Heä thoáng ña nhieäm (multitasking).

(cid:3) Laäp lòch CPU.

(cid:3) Thôøi gian chuyeån ñoåi giöõa caùc taùc vuï raát ngaén.

(cid:5) (cid:5) (cid:5) (cid:5) (cid:5)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung Boä xöû lyù

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 quaû vôùi users – Ñònh thôøi coâng vieäc (job scheduling) – Quaûn lyù boä nhôù (memory management) • Virtual memory – CPU luaân phieân thöïc thi giöõa caùc coâng vieäc – Quaûn lyù caùc quaù trình (process management) • 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) (cid:6) Ñònh thôøi CPU (cid:6) Ñoàng boä caùc quaù trình (synchronization) (cid:6) Giao tieáp giöõa caùc quaù trình (process communication) (cid:6) Traùnh deadlock – Moät coâng vieäc chæ ñöôïc chieám CPU khi noù naèm trong boä nhôù chính.

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

HEÄ THOÁNG ÑA XÖÛ LYÙ

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

• Heä thoáng song song (parallel, multiprocessor, hay tightly-

HEÄ THOÁNG ÑA XÖÛ LYÙ

(cid:3)Hai hoaëc nhieàu boä xöû lyù cuøng chia seû moät boä nhôù.

coupled system) – Nhieàu CPU – Chia seû computer bus, clock – Öu ñieåm

(cid:3) Master/Slave : moät boä xöû lyù chính kieåm soaùt moät soá boä xöû lyù 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

Boä

• Multiprocessor system ít toán keùm hôn multiple single- processor system: vì coù theå duøng chung taøi nguyeân (ñóa,…)

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

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

– 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) – 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 ÑA XÖÛ LYÙ

1.2. PHAÂN LOAÏI HEÄ ÑIEÀU HAØNH

• 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

HEÄ THOÁNG PHAÂN TAÙN (cid:3) Nhieàu maùy tính lieân keát vôùi nhau baèng ñöôøng truyeàn thoâng ñaëc bieät. (cid:3) Töông töï heä thoáng ña xöû lyù nhöng khoâng chia xeû boä nhôù.

• Caùc copy giao tieáp vôùi nhau khi caàn • (Windows NT, Solaris 5.0, Digital UNIX, OS/2, Linux)

Heä thoáng maùy tính 1

Heä thoáng maùy tính 2

Giao tieáp maïng

– Ñ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

Maïng

Boä xöû lyù

• (SunOS 4.0)

Boä nhôù

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

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) Caùc moâ hình heä thoáng phaân taùn – 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 – Client-server

– Ngöôøi duøng chæ thaáy moät heä thoáng ñôn nhaát – Öu ñieåm (cid:6) Server: cung caáp dòch vuï (cid:6) Client: coù theå söû duïng dòch vuï cuûa server – Peer-to-peer (P2P)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

Heä thoáng thôøi gian thöïc (real-time system)

Thieát bò caàm tay (handheld system)

(cid:6) Chia seû taøi nguyeân (resource sharing) (cid:6) Chia seû söùc maïnh tính toaùn (computational sharing) (cid:6) Ñoä tin caäy cao (high reliability) (cid:6) Ñ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 (cid:6) Caùc peer (maùy tính trong heä thoáng) ñeàu ngang haøng nhau (cid:6) Khoâng coù cô sôû döõ lieäu taäp trung (cid:6) Caùc peer laø töï trò (cid:6) Vd: Gnutella

• Heä thoáng thôøi gian thöïc (real-time system) • Thieát bò caàm tay (handheld system) – Söû duïng trong caùc thieát bò chuyeân duïng nhö ñieàu khieån caùc thöû nghieäm

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

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 – Personal digital assistant (PDA): Palm, Pocket-PC – Ñieän thoaïi di ñoäng (cellular phones) – Ñaëc tröng 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) • 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 • 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

1.3. LÒCH SÖÛ PHAÙT TRIEÅN CUÛA HEÄ ÑIEÀU HAØNH

(cid:3)Theá heä 1 (1945 - 1955)

(cid:3)Theá heä 4 (1980 -

- 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ã

(cid:3) Theá heä 2 (1955 - 1965)

) -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,…

(cid:3) Theá heä 3 (1965 - 1980)

- Xuaát hieä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

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

-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

Windows And Linux Evolution

Operating Systems Evolution

• Windows and Linux kernels are based on foundations

developed in the mid-1970s

IBSYS

IOCS

CTSS

1970

1980

1990

2000

OS/360

DOS/360

MULTICS

CP/CM5

RSX-11M

UNIX

TSO

RT-11

CP/M

UNIXV.7

VMS 1.0

MVS/370

DOS/VDSE

VM/370

V M S v1.0

4.1BSD

XENIX

MS-DOS 1.0

SYSTEM III

DR/DOS

SUN OS

4.2BSD

W in do w s N T 3.1

S erver 2003 W in d o w s 2000 W in d o w s X P N T 4.0

MVS/XA

SYSTEM V

VM/XA

AIX

OS/2

POSIX

MACH

WIN 3.0

WIN 3.1

4.3BSD

OSF/1

VMS 5.4

AIX/370

SYSTEM V.4

1970

1980

1990

2000

MVS/ES

VS/ESA

VM/ESA

AIX/ESA

SOLARIS 2

LINUX

4.4BSD

WIN NT

WIN 9X

WIN 2000

VMS 7.3

v2.0

v2.6

v2.3

v2.4

v2.2

WIN XP

LINUX 2.6

SOLARIS 10

Linux v1.0

U NIX p u blic U NIX V 6

U NIX b orn

WIN Server 2003

9/14/2010

Vũ Đức Lung

(see http://www.levenez.com for diagrams showing history of Windows & Unix) 34

Vũ Đức Lung

9/14/2010

Chöông II: II: CaáuCaáu TruùcTruùc HeäHeä ÑieàuÑieàu HaønhHaønh Chöông

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

•2.1.1. Quaûn lyù quaù trình (process management)

(cid:1) Caùc thaønh phaàn cuûa heä ñieàu haønh

(cid:1) Caùc dòch vuï heä ñieàu haønh cung caáp

(cid:1) Lôøi goïi heä thoáng (System call)

(cid:1) Caùc chöông trình heä thoáng (system programs)

(cid:1) Caáu truùc heä thoáng

- 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.

(cid:1) Maùy aûo (virtual machine)

- Caùc nhieäm vuï cuûa thaønh phaàn (cid:2) Taïo vaø huûy quaù trình (cid:2) Taïm dừng/thöïc thi tieáp (suspend/resume) quaù trình (cid:2) Cung caáp caùc cô cheá

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

– ñ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.2. Quaûn lyù boä nhôù chính

– Heä thoáng file (file system)

– 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

•2.1.3. Quaûn lyù file (file management)

quaûn lyù boä nhôù thích hôïp

– Caùc nhieäm vuï cuûa thaønh phaàn

– Caùc dòch vuï maø thaønh phaàn cung caáp

(cid:2) File (cid:2) Thö muïc

(cid:2) Theo doõi, quaûn lyù caùc vuøng nhôù troáng vaø ñaõ caáp phaùt (cid:2) Quyeát ñònh seõ naïp chöông trình naøo khi coù vuøng nhôù

troáng

(cid:2) Caáp phaùt vaø thu hoài caùc vuøng nhôù khi caàn thieát

(cid:2) Taïo vaø xoaù file/thö muïc. (cid:2) Caùc thao taùc xöû lyù file/thö muïc (mkdir, rename, copy, move, new,…)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

(cid:2) “AÙnh xaï” file/thö muïc vaøo thieát bò löu tröõ thöù caáp töông öùng (cid:2) Sao löu vaø phuïc hoài döõ lieäu

– Che daáu söï khaùc bieät cuûa caùc thieát bò I/O tröôùc

ngöôøi duøng

•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) – Boä nhôù chính: kích thöôùc nhoû, laø moâi tröôøng chöùa tin khoâng beàn vöõng

– Coù chöùc naêng

(cid:2) Cô cheá: buffering, caching, spooling (cid:2) Cung caáp giao dieän chung ñeán caùc trình ñieàu khieån

thieát bò (device-driver interface)

(cid:2) Quaûn lyù khoâng gian troáng treân ñóa(free space management) (cid:2) Caáp phaùt khoâng gian löu tröõ (storage allocation) (cid:2) Ñònh thôøi hoïat ñoäng cho ñóa (disk scheduling)

(cid:2) Boä ñieàu khieån caùc thieát bò (device driver) phaàn cöùng.

(cid:1) 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

9/14/2010

Vũ Đức Lung

=> 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

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñieàu haønh

2.1. CaùcCaùc thaønh 2.1.

thaønh phaàn

haønh phaàn cuûacuûa heäheä ñieàuñ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 – Laø giao dieän chuû yeáu giöõa ngöôøi duøng vaø OS • Ví duï: shell, mouse-based window-and-menu 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 – Khi user login – Kieåm soaùt vieäc truy caäp caùc taøi nguyeân trong heä thoáng • command line interpreter (shell) chaïy, vaø chôø nhaän leänh töø ngöôøi – 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ä 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:

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

2.2. CaùcCaùc dòchdòch vuïvuï heäheä ñieàuñieàu haønh 2.2.

haønh cung

cung caápcaáp

2.2. CaùcCaùc dòchdòch vuïvuï heäheä ñieàuñieàu haønh 2.2.

haønh cung

cung caápcaáp

Ngoaøi ra coøn caùc dòch vuï giuùp taêng hieäu suaát cuûa heä thoáng:

(cid:2) Cung caáp cô cheá kieåm soaùt ñaêng nhaäp/xuaát (login, log out) (cid:2) 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) (cid:2) 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 (cid:2) Taïo, huûy, vaø quaûn lyù quaù trình, heä thoáng (cid:2) Kieåm soaùt I/O (cid:2) Quaûn lyù boä löu tröõ thöù caáp (cid:2) Quaûn lyù boä nhôù chính (cid:2) Truy caäp heä thoáng file vaø cô cheá baûo maät

– Caáp phaùt taøi nguyeân (resource allocation)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

thoáng ((System call System call))

2.3. LôøiLôøi goïigoïi heäheä thoáng 2.3.

2.4. CaùcCaùc chöông 2.4.

chöông trình

thoáng trình heäheä thoáng

• Taøi nguyeân: CPU, boä nhôù chính, tape drives,… • OS coù caùc routine töông öùng – 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 – Keá toaùn (accounting) – Trao ñoåi thoâng tin giöõa caùc quaù trình qua hai caùch: • Nhaèm löu veát user ñeå tính phí hoaëc ñôn giaûn ñeå thoáng keâ. (cid:2) Chia xeû boä nhôù (Shared memory) (cid:2) 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 • Kieåm soaùt ñöôïc caùc truy xuaát taøi nguyeân cuûa heä thoáng (cid:2) Trong CPU, boä nhôù, treân thieát bò I/O (döõ lieäu hö, heát giaáy,…) (cid:2) 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)

• 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

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

(cid:1) 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 • Vd: open, read, write file – 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öõ. – Soaïn thaûo file: nhö file editor – Hoã trôï ngoân ngöõ laäp trình: nhö compiler, assembler, interpreter – 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++,…) – 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 – Giao tieáp: nhö email, talk, web browser (cid:2) Qua thanh ghi (cid:2) 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 (cid:1) Ngöôøi duøng chuû yeáu laøm vieäc thoâng qua caùc system program (khoâng laøm (cid:2) Qua stack vieäc “tröïc tieáp” vôùi caùc system call)

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

(cid:1) Caáu truùc ñôn giaûn (monolithic) UNIX: goàm hai phaàn coù theå taùch rôøi nhau

(cid:1) 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.

(cid:2) 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

9/14/2010

Vũ Đức Lung

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

(cid:1) Caáu truùc phaân taàng: HÑH ñöôïc chi thaønh nhieàu lôùp (layer).

(cid:1) Caáu truùc phaân taàng:

Caáu truùc phaân taàng cuûa MS-DOS

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

2.5. CaáuCaáu truùc 2.5.

thoáng truùc heäheä thoáng

(cid:1) 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:

(cid:1) Vi nhaân: phaân chia module theo microkernel (CMU Mach OS, 1980) (cid:1) Chuyeån moät soá chöùc naêng cuûa OS töø kernel space sang user space (cid:1) 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

(cid:2) Laàn ñaàu tieân ñöôïc aùp duïng cho HÑH THE (Technische Hogeschool Eindhoven) Lôùp 5 user programm (cid:2) Lôùp döôùi cuøng: hardware (cid:2) Lôùp treân cuøng laø giao tieáp vôùi user (cid:2) Lôùp treân chæ phuï thuoäc lôùp döôùi (cid:2) 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 Lôùp 4 Taïo buffer cho thieát bò I/O goïi bôûi lôùp treân (cid:2) 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ôù (cid:2) 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

moät module

(cid:1) Giao tieáp giöõa caùc module qua cô cheá truyeàn thoâng ñieäp

Application Application

POSIX POSIX application application

OS/2 OS/2 application application

File File server server

POSIX POSIX server server

OS/2 OS/2 server server

+ 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)

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

Microkernel

2.6. MaùyMaùy aûoaûo 2.6.

• Töø OS layer ñeán maùy aûo (virtual machine)

(cid:1) Hieän thöïc yù nieäm VM

Intel x86 Application

Intel x86 VM

VM interpretation

programming interface

Solaris kernel

processes – 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 ? processes processes 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

Sun hardware

Virtual machine system model

Non-virtual machine system model

9/14/2010

Vũ Đức Lung

9/14/2010

Vũ Đức Lung

kernel VM1 processes kernel VM3 2. Caùc leänh Intel (x86) ñöôïc maùy aûo kernel Intel chuyeån thaønh leänh töông öùng cuûa heä thoáng Sun. hardware kernel VM2 Virtual-machine implementation hardware

ChChööôngông III:

III: TieTieá

(Process) ánn trtrììnhnh (Process)

3.1. KhaKhaùùii nienieäämm côcô babaûûnn 3.1.

(cid:1) Caùi gì goïi caùc hoaït ñoäng 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

(cid:1) Quaù trình (process)

Moät quaù trình bao goàm

– moät chöông trình ñang thöïc thi

(cid:1) Khaùi nieäm cô baûn (cid:1) Traïng thaùi quaù trình (cid:1) Khoái ñieàu khieån quaù trình (Process control block) (cid:1) Ñònh thôøi quaù trình (Process Scheduling) (cid:1) Caùc taùc vuï ñoái vôùi quaù trình (cid:1) Söï coäng taùc giöõa caùc quaù trình (cid:1) Giao tieáp giöõa caùc quaù trình

Vũ Đức Lung

Khoa KTMT

3.1. KhaKhaùùii nienieäämm côcô babaûûnn 3.1.

chöông trình => quaù trình

Caùc böôùc naïp chöông trình vaøo boä nhôù

(cid:1) Duøng load module ñeå bieåu dieãn chöông trình thöïc thi ñöôïc (cid:1) Layout luaän lyù cuûa process image

Process image in main memory

Executable binary file (load module)

start address

program code

data

stack

Vũ Đức Lung

Khoa KTMT

3.2.Traïïng ng thathaùùii quaquaùù trtrììnhnh 3.2.Tra

(cid:1) Caùc traïng thaùi cuûa quaù trình (process states):

3.1. KhaKhaùùii nienieäämm côcô babaûûnn 3.1. KhôKhôûûii tataïïoo quaquaùù trtrììnhnh

(cid:1) Caùc böôùc heä ñieàu haønh khôûi taïo quaù trình

– Text section (program code), data section (chöùa global variables) – program counter (PC), process status word (PSW), stack pointer (SP), memory management registers,…

– Caáp phaùt moät ñònh danh duy nhaát (process number hay process identifier, pid) cho quaù trình – 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.

Vũ Đức Lung

Khoa KTMT

– 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 (cid:3) 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,…)

3.2.Traïïng ng thathaùùii quaquaùù trtrììnhnh 3.2.Tra

(cid:1) Chuyeån ñoåi giöõa caùc traïng thaùi cuûa quaù trình

(cid:1) Chuoãi traïng thaùi cuûa quaù

terminated terminated

VVíí duduïï /* test.c */ int main(int argc, char** argv) {

admit

dispatch

newnew

exit

printf(“Hello world\n"); exit(0);

}

ready ready

running running

trình test nhö sau (tröôøng hôïp toát nhaát): – new – ready – running – waiting (do chôø I/O khi goïi

interrupt

Bieân dòch chöông trình trong Linux gcc test.c –o test

I/O or event wait

I/O or event completion

waiting waiting

Vũ Đức Lung

Khoa KTMT

3.3.Process control block 3.3.Process control block

(cid:1) Ñaõ thaáy laø moãi quaù trình trong heä thoáng ñeàu ñöôïc caáp phaùt moät Process

Thöïc thi chöông trình test ./test printf) – ready – running – terminated Trong heä thoáng seõ coù moät quaù trình test ñöôïc taïo ra, thöïc thi vaø keát thuùc.

(cid:1) PCB laø moät trong caùc caáu truùc döõ lieäu quan

Control Block (PCB)

troïng nhaát cuûa heä ñieàu haønh vaø goàm: Löu ñoà chuyeån CPU töø quaù trình naøy ñeán quaù trình khaùc

Vũ Đức Lung

Khoa KTMT

QuaQuaûûnn lylyùù cacaùùcc quaquaùù trtrììnhnh: : cacaùùcc hahaøøngng ññôôïïii

YeâuYeâu cacaààuu ññooááii vôvôùùii heheää ññieieààuu hahaøønhnh veveàà quaquaûûnn lylyùù quaquaùù trtrììnhnh

(cid:1) Hoã trôï söï thöïc thi luaân phieân giöõa nhieàu quaù trình

(cid:1) Ví duï

caùc PCB

- 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

process number

running

(cid:1) Phaân phoái taøi nguyeân heä thoáng hôïp lyù

– Hieäu suaát söû duïng CPU – Thôøi gian ñaùp öùng

ready

(cid:1) Cung caáp cô cheá giao tieáp vaø ñoàng boä hoaït ñoäng caùc quaù trình

waiting

(cid:1) Cung caáp cô cheá hoã trôï user taïo/keát thuùc quaù trình

Coù gì sai trong ví duï?

Vũ Đức Lung

Khoa KTMT

– traùnh deadlock, trì hoaõn voâ haïn ñònh,…

(Process 3.4. ÑÑònhònh thôthôøøii quaquaùù trtrììnhnh (Process 3.4. Scheduling) Scheduling)

CaCaùùcc hahaøøngng ññôôïïii ññònhònh thôthôøøii (Scheduling (Scheduling queues) queues)

(cid:1) Haøng ñôïi coâng

(cid:1) Taïi sao phaûi ñònh thôøi?

(cid:1) Haøng ñôïi saün

vieäc-Job queue – Ña chöông (Multiprogramming)

(cid:1) …

(cid:3) Coù vaøi quaù trình chaïy taïi caùc thôøi ñieåm (cid:3) Muïc tieâu: taän duïng toái ña CPU saøng-Ready queue (cid:1) Haøng ñôïi thieát bò- Device queues – Chia thôøi(Time-sharing)

(cid:1) Moät soá khaùi nieäm cô baûn

(cid:3) Users töông taùc vôùi moãi chöông trình ñang thöïc thi (cid:3) Muïc tieâu: toái thieåu thôøi gian ñaùp öùng

Vũ Đức Lung

Khoa KTMT

(Scheduler) 3.5. BoBoää ññònhònh thôthôøøii (Scheduler) 3.5.

CaCaùùcc hahaøøngng ññôôïïii ññònhònh thôthôøøii (Scheduling (Scheduling queues) queues)

(cid:1) Boä ñònh thôøi coâng vieäc (Job scheduler) hay boä ñònh thôøi daøi

(long-term scheduler)

(cid:1) Boä ñònh thôøi CPU hay boä ñònh thôøi ngaén (cid:1) Caùc quaù trình coù theå moâ taû nhö:

– Caùc boä ñònh thôøi (scheduler) – Caùc haøng ñôïi ñònh thôøi (scheduling queue)

– 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

Vũ Đức Lung

Khoa KTMT

trung gian(medium

term gian(medium--term

3.6. CaCaùùcc tataùùcc vuvuïï ññooááii vôvôùùii quaquaùù trtrììnhnh 3.6.

BoBoää ññònhònh thôthôøøii trung scheduling) scheduling)

(cid:1) Ñoâi khi heä ñieàu haønh (nhö time-sharing system) coù theâm

(cid:1) Taïo quaù trình môùi (process creation)

Löu ñoà haøng ñôïi cuûa ñònh thôøi quaù trình

medium-term scheduling ñeå ñieàu chænh möùc ñoä ña chöông cuûa heä thoáng

(cid:1) Medium-term scheduler

Vũ Đức Lung

Khoa KTMT

– 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) (cid:3) Ví duï: (Unix) Khi user ñaêng nhaäp heä thoáng, moät command interpreter (shell) seõ ñöôïc taïo ra cho user (cid:4) 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öø boä nhôù sang ñóa (swap out) – 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.

CaâyCaây quaquaùù trtrììnhnh trong

Linux/Unix trong Linux/Unix

3.6.Caùùc c tataùùcc vuvuïï ññooááii vôvôùùii quaquaùù trtrììnhnh 3.6.Ca

(cid:1) Ví duï

(cid:1) 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

(cid:3) Quaù trình cha vaø con chia seû moïi taøi nguyeân (cid:3) Quaù trình con chia seû moät phaàn taøi nguyeân cuûa cha – Trình töï thöïc thi

Vũ Đức Lung

Khoa KTMT

cha/con VeVeàà quanquan heheää cha/con

VVíí duduïï tataïïoo process

fork() process vôvôùùii fork()

(cid:1) Khoâng gian ñòa chæ (address space)

#include #include int main (int argc, char *argv[]){

(cid:3) Quaù trình cha vaø con thöïc thi ñoàng thôøi (concurrently) (cid:3) Quaù trình cha ñôïi ñeán khi caùc quaù trình con keát thuùc.

int pid; /* create a new process */ pid = fork();

(cid:1) Ví duï trong UNIX/Linux

if (pid > 0){

– 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.

printf(“This is parent process”); wait(NULL); exit(0);

} else if (pid == 0) {

ñoàng boä

printf(“This is child process”); execlp(“/bin/ls”, “ls”, NULL); exit(0);

} else {

printf(“Fork error\n”); exit(-1);

}

Vũ Đức Lung

Khoa KTMT

3.6.Caùùc c tataùùcc vuvuïï ññooááii vôvôùùii quaquaùù trtrììnhnh ((tttt)) 3.6.Ca

3.7. CoCoäängng tataùùcc gigiööõaõa cacaùùcc quaquaùù trtrììnhnh 3.7.

(cid:1) Trong quaù trình thöïc thi, caùc quaù trình coù theå coäng taùc

(cid:1) Taïo quaù trình môùi (cid:5)

(cooperate) ñeå hoaøn thaønh coâng vieäc

(cid:1) Keát thuùc quaù trình

(cid:1) Caùc quaù trình coäng taùc ñeå

– 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

(cid:1) Söï coäng taùc giöõa caùc quaù trình yeâu caàu heä ñieàu haønh hoã trôï cô cheá giao tieáp vaø cô cheá ñoàng boä hoaït ñoäng cuûa caùc quaù trình

Vũ Đức Lung

Khoa KTMT

– Quaù trình töï keát thuùc (cid:3) Quaù trình keát thuùc khi thöïc thi leänh cuoái vaø goïi system routine – Chia seû döõ lieäu (information sharing) – Taêng toác tính toaùn (computational speedup) (cid:3) Neáu heä thoáng coù nhieàu CPU, chia coâng vieäc tính toaùn thaønh exit 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ù) (cid:3) 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 (cid:3) 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,…)

BaBaøøii toatoaùùnn ngngööôôøøii sasaûûnn xuaxuaáátt--ngngööôôøøii tieâutieâu thuthuïï consumer ) (producer--consumer ) (producer

3.8.Giao tietieáápp lieânlieân quaquaùù trtrììnhnh 3.8.Giao Interprocess communication ((Interprocess

IPC) communication--IPC)

(cid:1) IPC laø cô cheá cung caáp bôûi heä ñieàu haønh nhaèm giuùp caùc quaù

(cid:1) Ví duï coäng taùc giöõa caùc quaù trình: baøi toaùn producer-consumer

trình – 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æ

– 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

(cid:1) IPC coù theå ñöôïc cung caáp bôûi message passing system

(cid:3) unbounded buffer: kích thöôùc buffer voâ haïn (khoâng thöïc teá). (cid:3) bounded buffer: kích thöôùc buffer coù haïn.

– Producer vaø consumer phaûi hoaït ñoäng ñoàng boä vì

Vũ Đức Lung

Khoa KTMT

thoâng ññieieääpp

TieTieå

åuu trtrììnhnh ((luoluoà

Thread àngng) ) -- Thread

HeHeää thothoáángng truye truyeàànn thoâng Message passing system Message passing system (cid:1) Laøm theá naøo ñeå caùc quaù trình giao tieáp nhau? Caùc vaán ñeà:

(cid:1) Tieåu trình(tieán trình nheï-lightweight process): laø moät ñôn vò cô

– Ñaët teân (Naming)

(cid:3) Giao tieáp tröïc tieáp

baûn söû duïng CPU, goàm: – 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

(cid:3) Consumer khoâng ñöôïc tieâu thuï khi producer chöa saûn xuaát (cid:3) Producer khoâng ñöôïc taïo theâm saûn phaåm khi buffer ñaày.

– receive(Q, msg): nhaän thoâng ñieäp ñeán töø quaù trình Q

(cid:3) 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

(cid:3) Khaû naêng chöùa laø 0(Zero capacity hay no buffering) (cid:3) Bounded capacity: ñoä daøi cuûa queue laø giôùi haïn (cid:3) Unbounded capacity: ñoä daøi cuûa queue laø khoâng giôùi haïn

Vũ Đức Lung

Khoa KTMT

PCB vavaøøTCBTCB trong PCB

trong moâmoâ hhììnhnh

LôLôï

ïii ííchch cucuû

ûaa tietieá

ánn trtrììnhnh ññaa luoluoà

àngng

multithreads multithreads

(cid:1) Ñaùp öùng nhanh: Cho pheùp chöông trình tieáp tuïc thöïc thi khi moät

PCB

pid

boä phaän bò khoùa hoaëc moät hoaït ñoäng daøi

Thread Control Block TCB

Threads list

(cid:1) Chia seû taøi nguyeân: tieát kieäm khoâng gian nhôù

tid

Context

State

(cid:1) Kinh teá: taïo vaø chuyeån ngöõ caûnh nhanh hôn tieán trình

(Mem, global ressources…)

(State, details)

VD: trong Solaris 2, taïo process chaäm hôn 30 laàn, chuyeån chaäm

Relatives

Context

hôn 5 laàn

( Dad, children)

(IP, local stack…)

(cid:1) Trong multiprocessor: coù theå thöïc hieän song song

Scheduling statistic

Vũ Đức Lung

Khoa KTMT

resources (files)

(User thread) TieTieååuu trtrììnhnh ngngööôôøøii duduøøngng (User thread)

TiTiểểuu trtrììnhnh hhạạtt nhaân(Kernel

thread) nhaân(Kernel thread)

User mode

LWP2

LWP1

System call

Kernel mode

HDH

Kernel mode

Kernel

Khái niệm tiểu trình được xây dựng bên trong hạt nhân

Vũ Đức Lung

Khoa KTMT

Vũ Đức Lung

Khoa KTMT

Khái niệm tiểu trình được hỗ trợ bởi một thư viện hoạt động trong user mode

Khaùi nieäm cô baûn

ChChööôngông IV:

IV: ÑÑònhònh thôthôøøii CPUCPU

(cid:1) 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ä

– long-term, mid-term, short-term

thoáng.

– Taïi moãi thôøi ñieåm, chæ coù moät process ñöôïc thöïc thi. Do ñoù,

(cid:1) Khaùi nieäm cô baûn (cid:1) Caùc boä ñònh thôøi

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.

– First-Come, First-Served (FCFS) – Round-Robin (RR) – Shortest Job First (SJF) vaø Shortest Remaining

(cid:1) Ñò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.

Time First (SRTF) – Priority Scheduling – Highest Response Ratio Next (HRRN) – Multilevel Queue – Multilevel Feedback Queue

Khoa KTMT

Caùc boä ñònh thôøi

(cid:1) Long-term scheduling

newnew

(cid:1) Caùc tieâu chuaån ñònh thôøi CPU (cid:1) Caùc giaûi thuaät ñònh thôøi

– 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 Long-term scheduling Long-term scheduling

ready ready

suspended suspended ready ready

running running

– Ñ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 Medium-term scheduling Short-term scheduling vaø I/O-bound process (cid:1) 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ôù.

blocked blocked

terminated terminated

suspended suspended blocked blocked

Khoa KTMT

Caùc boä ñònh thôøi (tt)

Dispatcher

(cid:1) Dispatcher seõ chuyeån quyeàn ñieàu khieån CPU veà cho

• Short term scheduling (cid:1) 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

(cid:1) Bao goàm:

ñeå thöïc thi keá tieáp (coøn ñöôïc goïi laø ñònh thôøi CPU, CPU scheduling)

(cid:1) Short term scheduler coøn ñöôïc goïi vôùi teân khaùc laø dispatcher (cid:1) 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:

Medium-term scheduling

(cid:1) Coâng vieäc naøy gaây ra phí toån

– 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)

– 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) – Signal Chöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn

Khoa KTMT

– Dispatch latency: thôøi gian maø dispatcher döøng moät process vaø khôûi ñoäng moät process khaùc

Hai yeáu toá cuûa giaûi thuaät ñònh thôøi

Caùc tieâu chuaån ñònh thôøi CPU

(cid:1) Haøm choïn löïa (selection function): duøng ñeå choïn

(cid:1) User-oriented

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”)

– 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

(cid:1) System-oriented

– 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

Khoa KTMT

Hai yeáu toá cuûa giaûi thuaät ñònh thôøi (tt)

Preemptive vaø Non-preemptive

(cid:1) Hàm định thời được thực hiện khi

(cid:1) 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)

(cid:2) 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)

– 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.

(cid:2) 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

Thực hiện cơ chế nào khó hơn? Tại sao?

(cid:2) 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

Khaûo saùt giaûi thuaät ñònh thôøi

1. First-Come First-Served (FCFS)

(cid:1) 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

CPU burst

load store add store read from file

moät chu kyø CPU-I/O

Process

(cid:1) Cheá ñoä quyeát ñònh: non-preemptive algorithm (cid:1) Hieän thöïc : söû duïng haøng ñôïi FIFO (FIFO queues)

I/O burst

Arrival Time

Service Time

wait for I/O

– 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

CPU burst

inc store write to file

wait for I/O

I/O burst

CPU burst

load store add store read from file

I/O burst

P1 P2 P3 P4 P5

wait for I/O (cid:22)

run

add

(cid:1) Service time = thôøi gian process caàn CPU trong moät chu kyø

CPU-I/O

(cid:1) Process coù service time lôùn laø caùc CPU-bound process Khoa KTMT

Khoa KTMT

(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 (cid:1) Trường hợp 1, 4 được gọi là định thời nonpreemptive (cid:1) Trường hợp 2, 3 được gọi là định thời preemptive

FCFS Scheduling

(cid:1) Giaû söû thôøi gian vaøo cuûa caùc tieán

(cid:1) Ví duï :

(cid:1) Giaû söû thöù töï vaøo cuûa caùc tieán

(cid:1) Ví duï:

trình laø

(cid:2) P2, P3, P1

(cid:1) Thôøi gian chôø :

(cid:2) P1, P2, P3 (cid:1) Thôøi gian chôø

(cid:2) P1 = 6; P2 = 0; P3 = 3;

(cid:1) Thôøi gian chôø trung bình

(cid:2) (6+0+3)/3 = 3 , toát hôn..

Process P1 P2 P3

Burst Time 24 3 3

(cid:2) P1 = 0; (cid:2) P2 = 24; (cid:2) P3 = 27;

Process P1 P2 P3

Burst Time 24 3 3

(cid:1) Thôøi gian chôø trung bình

(cid:2) (0+24+27)/3 = 17

Gantt Chart for Schedule

P2 P3

Khoa KTMT

2. Shortest-Job-First(SJF) Scheduling

(cid:1) Hai hình thöùc (Schemes):

(cid:1) Ñònh thôøi bieåu coâng vieäc ngaén nhaát tröôùc (cid:1) Khi CPU ñöôïc töï do, noù seõ caáp phaùt cho tieán trình yeâu caàu ít

trình laø

thôøi gian nhaát ñeå keát thuùc ( tieán trình ngaén nhaát)

(cid:1) 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.

– Scheme 1: Non-preemptive( tieán trình ñoäc quyeàn CPU) (cid:2) 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) (cid:2) Neáu moät tieán trình CPU môùi ñöôïc ñöa vaøo danh saùch vôùi

Khoa KTMT

Non-Preemptive SJF Scheduling

Preemptive SJF Scheduling (hay Sortest Remaining Time First - SRTF)

(cid:1) Ví duï :

(cid:1) Ví duï 1:

Process Arrival TimeBurst Time 7 P1 4 P2 1 P3 4 P4

0 2 4 5

Process Arrival TimeBurst Time P1 P2 P3 P4

0 2 4 5

7 4 1 4

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

Gantt Chart for Schedule

Average waiting time = (0+6+3+7)/4 = 4

Process Arrival TimeBurst Time 8 P1 4 P2 9 P3 5 P4

0 1 2 3

Average waiting time = (9+1+0+2)/4 = 3

Khoa KTMT

VD2:

Nhaän xeùt veà giaûi thuaät SJF

(cid:1) 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.

(cid:1) Tương ứng với mỗi process cần có độ dài của CPU burst tiếp theo (cid:1) Hàm lựa chọn: chọn process có độ dài CPU burst nhỏ nhất (cid:1) Chứng minh được: SJF tối ưu trong việc giảm thời gian đợi trung

bình

(cid:1) Cô cheá non-preemptive khoâng phuø hôïp cho heä thoáng

(cid:1) Nhược điểm: Cần phải ước lượng thời gian cần CPU tiếp theo của

time sharing (interactive)

process

(cid:1) Giaûi thuaät SJF ngaàm ñònh ra ñoä öu tieân theo burst time

(cid:1) Giải pháp cho vấn đề này?

(cid:1) 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

Dự đoán thời gian sử dụng CPU

Nhaän xeùt veà giaûi thuaät SJF

Độ dài CPU burst đo được

(Thời gian sử dụng CPU chính là độ dài của CPU burst) (cid:1) Trung bình tất cả các CPU burst đo được trong quá khứ (cid:1) 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

(cid:1) Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ

Độ dài CPU burst dự đoán, a = ½ và τ với

0 = 10

(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.

Khoa KTMT

3. Priority Scheduling

Gaùn ñoä öu tieân

(cid:1) 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

(cid:1) Gaùn ñoä öu tieân coøn döïa vaøo:

(cid:1) Moãi process seõ ñöôïc gaùn moät ñoä öu tieân (cid:1) CPU seõ ñöôïc caáp cho process coù ñoä öu tieân cao nhaát (cid:1) Ñònh thôøi söû duïng ñoä öu tieân coù theå:

– Preemptive hoaëc – Nonpreemptive

Khoa KTMT

– 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

3. Priority Scheduling

4. Ñònh thôøi luaân phieân (Round Robin -RR)

(cid:1) Moãi process nhaän ñöôïc moät ñôn vò nhoû thôøi gian CPU

(cid:1) 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

(cid:1) Giaûi phaùp: laøm môùi (aging) – ñoä öu tieân cuûa process seõ

(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.

taêng theo thôøi gian

(cid:1) Vd:

(cid:1) 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.

(cid:1) Hieäu suaát

(cid:1) 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û

Khoa KTMT

RR vôùi time quantum = 1

Ví duï Round Robin

(cid:1) Time Quantum = 20

Process Burst Time 53 P1 17 P2 68 P3 24 P4

Gantt Chart for Schedule

P4 P1

P3 P3

(cid:3) 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. (cid:3) Öu tieân CPU-bound process

97 117 121 134

154 162

– 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)

turnaround time trung bình lôùn hôn SJF, nhöng ñaùp öùng toát hôn

Khoa KTMT

Time quantum vaø context switch

Thời gian hoàn thành và quantum time

(cid:1) Thời gian hoàn thành trung bình (average turnaround time) không

quantum

chắc sẽ được cải thiện khi quantum lớn

Process time = 10

context switch

Khoa KTMT

(cid:2) 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 (cid:2) 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

Quantum time cho Round Robin*

Quantum vaø response time

(cid:1) Khi thực hiện process switch thì OS sẽ sử dụng CPU chứ không phải process

(cid:1) Quantum time phaûi lôùn hôn thôøi gian duøng ñeå xöû lyù clock interrupt (timer) vaø thôøi gian dispatching

(cid:1) Time slice ngắn thì đáp ứng nhanh

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 (cid:1) 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

(cid:1) Neân lôùn hôn thôøi gian töông taùc trung bình (typical interaction)

(cid:1) Time slice dài hơn thì throughput tốt hơn (do giảm phí tổn OS overhead) nhưng

– Vấn đề: có nhiều chuyển ngữ cảnh. Phí tổn sẽ cao.

Khoa KTMT

Quantum time cho Round Robin

Round Robin

(cid:1) Quantum time và thời gian cho process switch:

thời gian đáp ứng lớn – Nếu time slice quá lớn, RR trở thành FCFS.

(cid:1) 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

(cid:1) 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

Khoa KTMT

Round Robin: nhược điểm

5. Highest Response Ratio Next

(cid:1) Các process dạng CPU-bound vẫn còn được “ưu tiên”

time spent wait

time

– 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% (cid:2) 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 nhau – 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

=RR

+ ing expected service expected service time

(cid:1) Choïn process keá tieáp coù giaù trò RR (Response ratio) lôùn

nhaát.

(cid:1) Caùc process ngaén ñöôïc öu tieân hôn (vì service time nhoû)

Khoa KTMT

– Ví dụ: (cid:2) 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à (cid:2) 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)

6. Multilevel Queue Scheduling

Multilevel Queue Scheduling*

(cid:1) Haøng ñôïi ready ñöôïc chia thaønh nhieàu haøng ñôïi rieâng

(cid:1) Ví dụ phân nhóm các quá trình

Độ ưu tiên cao nhất

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,…

System Processes

(cid:1) 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

(cid:1) Heä ñieàu haønh caàn phaûi ñònh thôøi cho caùc haøng ñôïi.

Interactive Processes

– Fixed priority scheduling: phuïc vuï töø haøng ñôïi coù ñoä öu tieân

Batch Processes

Student Processes

– 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.

Độ ưu tiên thấp nhất

Khoa KTMT

7. Multilevel Feedback Queue

7. Haøng ñôïi phaûn hoài ña caáp Multilevel Feedback Queue

(cid:1) Ví duï: Coù 3 haøng ñôïi

(cid:1) Vaán ñeà cuûa multilevel queue

– process khoâng theå chuyeån töø haøng ñôïi naøy sang 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

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.

(cid:1) 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).

Khoa KTMT

So saùnh caùc giaûi thuaät

7. Multilevel Feedback Queue (tt)

(cid:1) Ñò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?

cao ñeán thaâp. Vaán ñeà: coù theå coù starvation.

thôøi nhö response time, hieäu suaát CPU, throughput,…

– 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?

– Phöông phaùp ñònh löôïng so saùnh

– Khi process yeâu caàu ñöôïc xöû lyù thì ñöa vaøo haøng ñôïi

naøo laø hôïp lyù nhaát?

Khoa KTMT

(cid:1) Giaûi thuaät ñònh thôøi naøo laø toát nhaát? (cid:1) 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

Đọc thêm

(cid:1) Policy và Mechanism (cid:1) Định thời trên hệ thống multiprocessor (cid:1) Đánh giá giải thuật định thời CPU (cid:1) Định thời trong một số hệ điều hành thông dụng

(cid:1) Nguồn: Operating System Concepts. Sixth Edition. John Wiley & Sons, Inc.

2002. Silberschatz, Galvin, Gagne

Khoa KTMT