Bài giảng Hệ điều hành - Chương 2: Khái niệm về quá trình

Chöông 2

KHAÙI NIEÄM VEÀ QUAÙ TRÌNH

-4.1-

Noäi dung

Khaùi nieäm cô baûn

Ñònh thôøi process (CPU scheduling)

Caùc taùc vuï treân process (taïo process, keát thuùc

process)

Söï coäng taùc giöõa caùc process

Interprocess Communication (IPC)

Moâ hình giao tieáp Client-Server

-4.2-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

1

Khaùi nieäm cô baûn

OS thöïc thi nhieàu chöông trình khaùc nhau

– Batch system: jobs

– Time-shared systems: user programs, tasks

– Job ≈ process

Process

– moät chöông trình ñang thöïc thi (executing program).

Moät process bao goàm caùc phaàn

– Text section(program code), data section(global variable), stack

(local variable,…)

– Hardware: Program Counter(PC), Process Status Word (PSW),

Stack Pointer (SP), Memory Management Registers

So saùnh process vaø program

– Process = active <> passive = programing

-4.3-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Process Control Block (PCB)

Chöùa caùc thoâng tin öùng vôùi moãi process.

– Process ID, parent process ID

– Credentials (user ID, group ID, effective ID,...)

– Traïng thaùi process : new, ready, running, waiting…

– Program counter: ñòa chæ cuûa leänh keá tieáp seõ thöïc thi

– Caùc thanh ghi CPU

– Thoâng tin duøng ñeå ñònh thôøi CPU: priority,...

– Thoâng tin boä nhôù: base/limit register, page tables…

– Thoâng tin thoáng keâ: CPU time, time limits…

– Thoâng tin traïng thaùi I/O: danh saùch thieát bò I/O ñöôïc

caáp phaùt, danh saùch caùc file ñang môû,...

– Con troû (pointer) ñeán PCBs khaùc.

-4.4-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

2

Process Control Block (PCB)

-4.5-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

User Processes in Virtual Memory

Process

Identification

Process

Control

Block

ProcessState

Information

ProcessState

Information

ProcessState

Information

ProcessControl

Information

ProcessControl

Information

ProcessControl

Information

UserStack

PrivateUser

AddressSpace

(Programs,Data)

PrivateUser

AddressSpace

(Programs,Data)

PrivateUser

AddressSpace

(Programs,Data)

…

SharedAddress

Space

SharedAddress

Space

SharedAddress

Space

Process1

Process2

Processn

-4.6-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

3

Caùc böôùc naïp process vaøo boä nhôù

Linker: keát hôïp caùc object modules thaønh moät file nhò phaân coù

theå thöïc thi (executable binary file) goïi laø load module

Loader: naïp load module vaøo boä nhôù chính

-4.7-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Loader

Process

ControlBlock

Program

Code

Program

Code

Data

ExecutableBinaryFile

(LoadModule)

Stack

ProcessImagein

MainMemory

Program Æ Process

-4.8-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

4

Yeâu caàu ñoái vôùi OS

OS phaûi hoã trôï söï thöïc thi luaân phieân giöõa nhieàu process

ñeå toái öu hieäu suaát CPU vôùi moät thôøi gian ñaùp öùng coù

theå chaáp nhaän ñöôïc (reasonable response time) → ñònh

thôøi CPU

OS phaûi phaân phoái taøi nguyeân heä thoáng (resources) cho

processes (boä nhôù, thieát bò I/O,...) ñoàng thôøi phaûi traùnh

hieän töôïng deadlock

OS phaûi cung caáp cô cheá giao tieáp giöõa caùc process

khaùc nhau (inter-process communication), cô cheá ñoàng

boä hoaït ñoäng caùc process (synchronization)

OS phaûi cung caáp cô cheá hoã trôï cho user taïo vaø huûy caùc

process.

-4.9-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Caùc traïng thaùi cuûa process

Khi thöïc thi, process chuyeån töø traïng thaùi naøy

sang traïng thaùi khaùc, bao goàm

– New: process môùi vöøa ñöôïc taïo ra (ñöôïc boû vaøo job

queue)

– Ready: process chôø ñöôïc chieám CPU ñeå laøm vieäc

(ñöôïc xeáp vaøo ready queue)

– Running: caùc leänh cuûa process ñang ñöôïc thöïc hieän.

– Waiting: process chôø moät söï kieän naøo ñoù xaûy ra, ví

duï moät thao taùc I/O vöøa hoaøn taát,... (xeáp vaøo waiting

queue)

– Terminated: söï thöïc thi cuûa process keát thuùc

-4.10-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

5

Löu ñoà 5-traïng thaùi process

dispatch

admit

new

exit

terminated

ready

running

interrupt

blocked

I/O or

eventwait

I/O orevent

completion

Chæ coù moät process ôû traïng thaùi running treân moãi processor taïi moät

thôøi ñieåm

Coù theå coù nhieàu process ôû traïnh thaùi ready vaø waiting

-4.11-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Ví duï veà traïng thaùi process

test.c

Chuoãi traïng thaùi cuûa

process test nhö sau:

void main()

{

– new

printf(“Hello World\n");

– ready

}

– running

– blocked (chôø I/O)

– ready

Bieân dòch trong Linux/Unix

$ gcc test.c –o test

Thöïc thi chöông trình test

– running

– terminated

$ ./test

Trong heä thoáng seõ coù moät

process test ñöôïc taïo

ra, thöïc thi vaø keát thuùc.

-4.12-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

6

Caùc traïng thaùi cuûa process (t.t)

Traïng thaùi New

– OS thöïc hieän caùc taùc vuï caàn thieát ñeå taïo process

» Taïo moät ñònh danh cho process (process identifier – pid)

» Taïo caùc caáu truùc ñeå quaûn lyù process

– Memory table, file table, Process Control Block (PCB),...

– Process môùi taïo ra coù theå chöa ñöôïc thöïc thi ngay, bôûi vì taøi

nguyeân heä thoáng coù haïn, thoâng thöôøng chæ phuïc vuï moät process

taïi moät thôøi ñieåm. Process coù theå ñaët trong boä nhôù thöù caáp ñeå

tieát kieäm khoâng gian boä nhôù chính

Traïng thaùi Terminated

– Process khoâng coøn ñöôïc thöïc thi nöõa

– Process vaø caùc caáu truùc quaûn lyù process khoâng caàn thieát seõ bò

xoùa.

-4.13-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Caùc traïng thaùi cuûa process (t.t)

Neáu process ñang trong traïng thaùi ready hay

running vaø bò suspend, noù seõ rôi vaøo traïng thaùi

suspended ready

Neáu process ñang trong traïng thaùi blocked vaø bò

suspend, noù seõ rôi vaøo traïng thaùi suspended

blocked

Traïng thaùi suspend coù theå thay ñoåi neáu users

hoaëc OS thöïc hieän taùc vuï resume.

Process coù theå chuyeån töø traïng thaùi suspended

blocked sang suspended ready neáu coù söï kieän

I/O töông öùng laøm cho quaù trình ñoù bò blocked

xaûy ra.

-4.14-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

7

Caùc traïng thaùi cuûa process (t.t)

Process bò suspend trong caùc tröôøng hôïp sau

– User muoán taïm döøng quaù trình thöïc thi cuûa process

ñeå xem keát quaû thöïc hieän, phaùt hieän loãi,…

– Ngöôøi quaûn trò heä thoáng coù theå suspend moät soá

process ñeå thu hoài moät soá taøi nguyeân vaø OS coù theå

caáp phaùt cho process khaùc nhaèm giaûm tình traïng quaù

taûi trong heä thoáng

– Tröôøng hôïp coù tranh chaáp taøi nguyeân giöõa caùc

process, suspend coù theå giuùp heä thoáng thoaùt khoûi tình

traïng deadlock (tham khaûo theâm phaàn Deadlock)

Khi rôi vaøo traïng thaùi suspend, process ñöôïc swap ra heä

thoáng löu tröõ thöù caáp, nhöôøng choã trong boä nhôù cho

process khaùc.

-4.15-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Löu ñoà 7-traïng thaùi cuûa process

admit

new

exit

terminated

dispatch

ready

running

time-out

event

wait

event

occur

resume

suspend

blocked

suspend

resume

event

occur

suspended

ready

suspended

blocked

-4.16-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

8

Traïng thaùi process trong Unix

fork()

created

preempted

enough

memory

return

touser

notenough

memory

preempt

user

running

swapout

swapin

ready

swapped

ready

torun

return

reschedule

system call,

interrupt

kernel

running

wake-up

interrupt,

interruptreturn

sleep

exit

swapout

swapped

sleep

asleep

zoombie

-4.17-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Traïng thaùi Unix process (t.t)

User Running: process thöïc thi ôû user-mode

Kernel Running: process thöïc thi ôû kernel-mode

Ready To Run (in memory): trong haøng ñôïi ready

Pre-empted: haøng ñôïi ready ñaëc bieät, process töø kernel-

mode veà user-mode nhöng bò OS ñoaït quyeàn (preempt),

thöïc hieän chuyeån ngöõ caûnh vaø chuyeån quyeàn ñieàu khieån

cho process khaùc.

Asleep (in Memory): traïng thaùi blocked, chôø söï kieän

(event) hoaëc taùc vuï I/O

Swapped-Ready: process saün saøng nhöng caàn phaûi naïp

process töø boä nhôù thöù caáp.

Swapped-Sleep: Ñang ñôïi (blocked) thì bò swap out ra boä

nhôù thöù caáp, nhöôøng boä nhôù chính cho process khaùc.

-4.18-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

9

Ñònh thôøi Process – Muïc tieâu

Multiprogramming

– Coù nhieàu process phaûi thöïc thi luaân phieân nhau

– Cöïc ñaïi hieäu suaát cuûa CPU

Time Sharing

– Cho pheùp users töông taùc khi chöông trình ñang chaïy

– Toái thieåu thôøi gian ñaùp öùng

-4.19-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Caùc haøng ñôïi ñònh thôøi (queue)

Job queue (New): chöùa caùc process môùi ñöôïc taïo ra

trong heä thoáng

Ready queue (Ready): chöùa caùc process ñang naèm

trong boä nhôù chính saün saøng ñôïi ñöôïc thöïc thi

Device queues (Waiting): chöùa caùc process ñang chôø

moät thieát bò I/O, moät söï kieän I/O

Process ñöôïc chuyeån töø haøng ñôïi naøy sang haøng ñôï

khaùc trong suoát quaù trình thöïc thi cuûa noù

Caùc haøng ñôïi ñònh thôøi ñöôïc hieän thöïc baèng danh saùch

lieân keát (linked list)

– Caùc lieân keát laø caùc con troû trong khoái PCB

-4.20-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

10

Haøng ñôïi Ready & I/O Device

-4.21-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Ñònh thôøi Process

Long-term

Scheduler

Short-term

Scheduler

Jobqueue

-4.22-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

11

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

Long-term scheduler (or job scheduler)

– Choïn process naøo seõ ñöôïc ñöa vaøo ready queue (töø

New chuyeån sang Ready)

Short-term scheduler (or CPU scheduler)

– Choïn process naøo seõ ñöôïc chieám CPU ñeå xöû lyù (töø

Ready chuyeån sang Running)

Medium-term scheduler

– Chuyeån process töø boä nhôù chính sang sang boä nhôù

thöù caáp (nhöng vaãn naèm trong khoâng gian boä nhôù aûo);

khi naøo caàn thì naïp process töø boä nhôù thöù caáp vaøo boä

nhôù chính.

-4.23-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

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

Short-term schedule thöôøng xaûy ra raát thöôøng xuyeân

(milli giaây) → phaûi thöïc thi nhanh

Long-term schedule thöôøng thöïc hieän khoâng thöôøng

xuyeân (giaây, phuùt) → coù theå thöïc hieän chaäm

– Long-term scheduler ñieàu khieån möùc ñoä multi-programming

– Neân choïn xen keõ giöõa I/O-bound vaø CPU- bound processes

Thoâng thöôøng, process chia laøm 2 loaïi chính

– I/O-bound process: phaàn lôùn thôøi gian thöïc thi duøng ñeå thöïc hieän

caùc taùc vuï I/O, thôøi gian chieám CPU ít hôn.

– CPU-bound process: thôøi gian thöïc thi chuû yeáu laø caùc taùc vuï tính

toaùn, chieám CPU nhieàu hôn so vôùi thöïc hieän caùc taùc vuï I/O.

-4.24-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

12

Chuyeån ngöõ caûnh (context switch)

Context

Switch

-4.25-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Chuyeån ngöõ caûnh (t.t)

Khi CPU chuyeån sang thöïc thi moät process khaùc, heä

thoáng phaûi löu traïng thaùi cuûa process hieän taïi ñang thöïc

thi vaø naïp traïng thaùi cuûa process môùi seõ thöïc thi.

Ngöõ caûnh (context) cuûa moät process ñöôïc bieåu dieãn

trong khoái PCB cuûa process ñoù.

Thôøi gian chuyeån ngöõ caûnh (context-switch time) laø moät

trong caùc phí toån (overhead) maø heä thoáng phaûi gaùnh

chòu; do ñoù, phaûi coù chieán löôïc chuyeån ngöõ caûnh hôïp lyù

ñeå ñaït hieäu quaû xöû lyù cao.

Chi phí chuyeån ngöõ caûnh phuï thuoäc söï hoã trôï caáp

hardware, phuï thuoäc phöông thöùc quaûn lyù boä nhôù,…

-4.26-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

13

Caùc böôùc chuyeån ngöõ caûnh

Löu ngöõ caûnh CPU, bao goàm thanh ghi leänh - program

counter (PC) vaø caùc thanh ghi khaùc.

Caäp nhaät PCB cuûa process ñang thöïc thi: ghi nhaän traïng

thaùi hieän taïi vaø moät soá thoâng tin caàn thieát khaùc

Chuyeån PCB cuûa process ñang thöïc thi ñeán haøng ñôïi

töông öùng: ready, waiting

Thöïc hieän vieäc choïn process khaùc ñeå thöïc thi (short-

term scheduler)

Caäp nhaät PCB cuûa process ñöôïc choïn thöïc thi.

Phuïc hoài ngöõ caûnh CPU cuûa process ñöôïc choïn (neáu coù)

-4.27-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Chuyeån ngöõ caûnh xaûy ra khi naøo?

Chuyeån ngöõ caûnh coù theå xaûy ra khi OS chieám laïi

quyeàn ñieàu khieån CPU, chaúng haïn nhö

– System Call

»Ñöôïc goïi töôøng minh trong chöông trình (ví duï:

system call môû/ñoùng file). Process goïi system call

coù theå seõ bò blocked chôø thöïc hieän system call.

– Trap

»Moät loãi ñaõ xaûy ra. Process coù theå chuyeån vaøo traïng

thaùi Exit vaø keát thuùc thöïc thi.

– Interrupt

»Quyeàn ñieàu khieån chuyeån sang cho Interrupt

Handler.

-4.28-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

14

Caùc ví duï veà Interrupt

Clock:

– process ñaõ heát thôøi gian ñöôïc chieám CPU ñeå thöïc thi (time slice,

quantum) vaø phaûi chuyeån sang traïng thaùi ready.

I/O

– Neáu coù processes ñang chôø söï kieän I/O naøy thì chuyeån process

ñoù sang traïng thaùi ready.

– Sau ñoù, tieáp tuïc thöïc thi process hieän taïi hoaëc choïn moät process

khaùc coù ñoä öu tieân cao hôn.

Memory fault

– Ñòa chæ boä nhôù ñöôïc tham chieáu naèm trong boä nhôù aûo vaø phaûi

ñöôïc naïp vaøo boä nhôù chính.

– Process ñang thöïc thi phaûi chuyeån sang traïng thaùi blocked (chôø

hoaøn taát taùc vuï I/O)

-4.29-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Medium Term Scheduling

OS coù theå suspend moät soá process, nghóa laø chuyeån

caùc process ñoù ra boä nhôù thöù caáp (ñóa cöùng, meàm…)

Medium-term

Scheduler

Suspend

Medium-term

Scheduler

Short-term

Scheduler

Job

queue

Long-term

Scheduler

-4.30-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

15

Taïo process (process creation)

Process ñöôïc taïo ra khi naøo?

– Coù moät coâng vieäc (job) môùi yeâu caàu ñöôïc thöïc hieän.

– Khi user ñaêng nhaäp (log on) → command interpreter (Unix shell)

– Do OS taïo ra ñeå cung caáp dòch vuï cho user (ví duï:in moät file)

– Sinh ra bôûi moät process, ví duï

» user program coù theå taïo ra nhieàu process

Caùc böôùc OS khôûi taïo process

– Gaùn moät ñònh danh duy nhaát (unique process identifier)

– Caáp phaùt khoâng gian nhôù cho process image.

– Khôûi taïo process control block (PCB)

» Moät soá giaù trò maëc ñònh (ví duï: traïng thaùi=New, khoâng coù thieát

bò I/O, khoâng môû files...)

– Thieát laäp caùc moái lieân heä caàn thieát

» Ví duï: theâm process môùi vaøo linked list cuûa haøng ñôïi ñònh thôøi

-4.31-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Moái quan heä cha/con

Process cha taïo ra caùc process con, caùc process con

taïo ra nhieàu process khaùc,... vaø cöù nhö theá taïo thaønh

moät caây process trong heä thoáng.

3 caùch chia seû taøi nguyeân (resource sharing)

– Process cha vaø con chia seû moïi taøi nguyeân

– Process con chia seû moät phaàn taøi nguyeân cuûa cha

– Process cha vaø con khoâng chia seû taøi nguyeân naøo

Trình töï thöïc thi

– Process cha vaø con thöïc thi ñoàng thôøi (concurrently)

– Process cha ñôïi ñeán khi caùc process con keát thuùc.

-4.32-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

16

Caây process trong UNIX

pid=0

root

swapper

user1

pid=1

pagedaemon

init

user2

user3

-4.33-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Moái quan heä cha/con (t.t)

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

– Khoâng gian ñòa chæ cuûa process con ñöôïc nhaân baûn töø cha

– Khoâng gian ñòa chæ cuûa process con ñöôïc naïp chöông trình khaùc.

Ví duï trong UNIX/Linux

– System call fork() taïo moät process môùi

– System call execlp() duøng sau fork() ñeå naïp moät chöông trình

môùi vaøo khoâng gian nhôù cuûa process môùi

Cha

fork()

execlp()

ProcessCha

Con

-4.34-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

17

Ví duï taïo process vôùi fork()

#include <stdio.h>

int main (int argc, char *argv[])

{

int

pid;

/* create a new process */

pid = fork();

if ( pid < 0 )

{

printf(“Fork error\n”);

exit(-1);

}

else if ( pid == 0 )

{

printf(“This is child process”);

execlp(“/bin/ls”, “ls”, NULL);

exit(0);

}

else

{

printf(“This is parent process”);

exit(0);

}

-4.35-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Keát thuùc thöïc thi process

Keát thuùc bình thöôøng (normal completion)

Vöôït giôùi haïn thôøi gian (time limit exceeded)

Khoâng ñuû boä nhôù (memory unavailable)

Xaâm phaïm vuøng nhôù caám (memory bounds

violation)

Loãi baûo veä (protection error)

– Ví duï: ghi vaøo file coù thuoäc tính read-only

Loãi soá hoïc (arithmetic error): chia cho 0, traøn

soá,...

Time overrun

– process chôø moät söï kieän laâu hôn moät khoaûng thôøi

gian toái ña ñöôïc xaùc ñònh tröôùc

-4.36-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

18

Keát thuùc thöïc thi process (t.t)

Thöïc hieän thaát baïi taùc vuï I/O

Leänh khoâng hôïp leä (invalid instruction)

Privileged instruction

Söï can thieäp cuûa OS

– Ví duï: OS can thieäp khi coù deadlock xaûy ra

Process cha yeâu caàu keát thuùc thöïc thi moät

process con

Process cha keát thuùc keùo theo caùc process con

cuõng keát thuùc

-4.37-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Söï coäng taùc giöõa caùc process

Moät process thöïc thi ñoäc laäp thì khoâng aûnh höôûng vaø

khoâng bò aûnh höôûng bôûi caùc process khaùc trong heä

thoáng. Tuy nhieân, moät soá process coù theå coäng taùc, trao

ñoåi döõ lieäu vôùi nhau ñeå hoaøn thaønh coâng vieäc.

Öu ñieåm cuûa söï coäng taùc

– Chia seû thoâng tin

– Hieäu suaát tính toaùn cao

Söï coäng taùc cuûa caùc process yeâu caàu OS hoã trôï cô cheá

giao tieáp (communication) vaø cô cheá ñoàng boä hoaït ñoäng

cuûa caùc process (synchronization)

-4.38-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

19

Baøi toaùn Producer-Consumer

Moâ hình cho söï coäng taùc giöõa caùc process, producer taïo

ra caùc thoâng tin, döõ lieäu vaø consumer tieâu thuï, söû duïng

caùc döõ lieäu ñoù. Söï trao ñoåi thoâng tin thöïc hieän qua buffer:

– unbounded-buffer: kích thöôùc buffer khoâng giôùi haïn.

– bounded-buffer: kích thöôùc buffer coù giôùi haïn.

Producer vaø consumer phaûi ñöôïc ñoàng boä hoaït ñoäng

– Consumer khoâng theå söû duïng moät döõ lieäu maø producer chöa kòp

taïo ra.

– Producer khoâng ñöôïc taïo theâm saûn phaåm khi buffer ñaõ ñaày

(bounded buffer)

Hieän thöïc buffer

– Shared memory

– Interprocess communication facility (IPC)

-4.39-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Ví duï Shared Bounded-Buffer

Shared memory

#defineBUFFER_SIZE10

typedefstruct{

...

– Shared buffer: danh saùch xoay

voøng.

» in: vò trí ghi keát tieáp

» out: vò trí ñoïc keá tieáp

}item;

» BUFFER_SIZE: kích thöôùc

cuûa buffer (chæ ñöôïc duøng

BUFFER_SIZE – 1 phaàn töû)

item buffer[BUFFER_SIZE];

intin=0;

intout=0;

Producer vaø consumer chia seû

moät buffer chung

Programmer phaûi hieän thöïc

ñoaïn maõ truy xuaát buffer chung

cho producer vaø consumer

-4.40-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

20

Bài giảng Hệ điều hành - Chương 2: Khái niệm về quá trình - Thoại Nam