操作系統

第二章進程與線程

內容

基礎：進程描述及控制

■■避免：死鎖與饑餓

??解決：幾個經典問題

■關于：進程通信

。策略：進程調度

2

62.1ProcessDescriptionand

Control

Learningobjectiv

BytheendofthisIcctureyoushouIdbeabIcto

?ExpIainwhat5sProcess,SwappingandThread

?掌握分析進程的結構，PCB,Processimage（進程映像）

?描述進程的基本狀態及轉換規則與原因

?區別進程的掛起與阻塞狀態

?理解OS內核的主要功能

?理解ProcessControIPrimitives（原語）

?區別ProcessSwitchingvs.ModeSwitching

?區別Processvs.Thread

MajorRequirementsofanOperating

System

?InterleavetheexecutionofseveraprocessestomaximizeprocessorutiIization

whiIeprovidingreasonabIeresponsetime

?AIlocateresourcestoprocesses

?Supportinterprocesscommunicationandusercreationofprocesses

程序的執行順序

?程序順序執行

■程序順序執行時的特征：順序性、封閉性、可再現性

?程序并發執行

■程序并發執行時的特征：間斷性、非封閉性、不可再現性

?程序并發執行條件(Bernstein條件)

■R(P1)nW(P2)UW(P1)HR(P2)UW(P1)HW(P2)={}

Process

?Alsocalledatask

?ExecutionofanindividuaIprogram

■進程是程序在一個數據集合上的運行過程，是系統進行資源分配和調度的

一個獨立單位

■進程是可并發執行的程序在一個數據集合上的運行過程

?Canbetraced

■Iistthesequenceofinstructionsthatexecute

CharacteristicsofProcess

?Dynamic（動態性）

?Concurrency（并發性）

?Independent（獨立性）

?Asynchronous（異步性）

ProcessStructure

?Programs

?Datas

?PCB（ProcessControIBlock進程控制塊）

第8-9講進程狀態轉換

ProcessStates

?進程的并發執行

?進程的2狀態

?進程的5狀態

?進程狀態轉換圖

假設內存中有3個逆程A、B、C,他們的程序代碼已全部裝入內存。若A、

C兩進程需要執行12條指令，B進程需要執行4條指令，且B進程執行到第

4條指令處必須等待I/Oo如何跟蹤他們的執行過程？

Figure3.1Snapshot<jfExampleExecution(Figure3」

ntlitslrixrtkmCyck13

Dispatcher

?操作系統重要組件

?負責進程、線程、作業的調度與分配

?提供多種調度算法如先來先服務、短作業優先、時間片輪轉等

?監測性能變化,如CPU使用率、10響應時間等

?Tiiheau

4|too

-1/0requ4ftlot

42。

io2

440log3

"e

麝

47”

"溜

?

5|12010

521201

33C??M?4InnefPrw(?“e?fflgw*3al

Two-StateProcessModeI

?Processmaybeinoneoftwostates

■Running（執行）

■Not-running（非執行）

Dispatch

Pause

（a）Statetransitiondl曄ram

Not-RunningProcessinaQueue

注：

?并非所有進程只要Not-running就處于ready（就緒）,有的需要blocked（阻塞）等待I/O完成

?Not-running又可分為ready和blocked兩種狀態

AFive-StateModeI

?Running（運行）

?Ready（就緒）

?Blocked（阻塞）

?New（創建）

?Exit（終止）

?Running：占用處理機（單處理機環境中，某一時刻僅一個進程占用處理機）

?Ready：準備執行

?Blocked：等待某事件發生才能執行，如等待I/O完成等

?New：進程已經創建，但未被OS接納為可執行進程

?Exit：因停止或取消，被OS從執行狀態釋放

Admit

Fivure36Five-StateProcessModel

?NulIfNew：新創建進程首先處于新狀態

?NewfReady：OS接納新狀態進程為就緒進程

?Ready->Running：OS只能從就緒進程中選一個進程

執行

?RunningExit：執行狀態的進程執行完畢,或被取

消，則轉換為退出狀態

?Running->Ready：分時系統中,時間片用完，或優

先級高的進程到來，將終止優先級低的進程的執行

?Running6Blocked：執行進程需要等待某事件發生。

通常因進程需要的系統調用不能立即完成，而阻塞

?Blocked-Ready：當阻塞進程等待的事件發生，就

轉換為就緒狀態

?Ready.Exit：某些系統允許父進程在任何情況下終

止其子進程。若一個父進程終止，其子孫進程都必須終

止。

?BlockedExit：同前

ProwM.A

Fi?ure3.6ProcessStatesforTrace<>fFi13J

UsingTwoQueues

Krnd,QIM-IM*

AdmitDh|Mtch

PFIKYWH-

Tlnw<Mit

E*ent1Queue

Kvcnl!Event1Wall

Occurs

E、cnt2Queue

Ewnl2Event2Wall

Occur.

E、cnl”Queue

>>cntn?cnlnWalt

Occurs

<blMuldnleblockedciueiws

Swapping（對換技術，交換技術）

將內存中暫時不能運行的進程，或暫時不用的數據和程序，Swapping-out到

外存，以騰出足夠的內存空間，把已具備運行條件的進程，或進程所需要的數

據和程序，Swapping-in內存。

Swapping（對換技術，交換技術）

note

應該保證進程執行時間比交換時間長

交換空間通常作為磁盤的一整塊，且獨立于文件系統

普通的交換技術一般很少使用，交換技術的一些變體任然在UNIX等系統中使用

SuspendedProcesses

?ProcessorisfasterthanI/OsoaIIprocessescouIdbe

waitingforI/O

?Swaptheseprocessestodisktofreeupmorememory

?Blockedstatebecomessuspendstatev/henswappedtodisk

ReasonsforProcessSuspension

SwappingTheoperatingsystemneedstoreleasesufficientmain

memorytobringinaprocessthatisreadytoexecute

OtherOSreasonTheoperatingsystemmaysuspendabackgroundorutility

processoraprocessthatissuspectedofcausingaproblem

InteractiveuserrequestAusermaywishtosuspendexecutionofaprogramfor

purposesofdebuggingorinconnectionwiththeuseofa

resource

TimingAprocessmaybeexecutedperiodically(eg.an

accountingorsystemmonitoringprocess)andmaybe

suspendedwhilewaitingforthenexttimeinterval

ParentprocessrequestAparentprocessmaywishtosuspendexecutionofa

descendenttoexamineormodifythesuspendedprocess,or

tocoordinatetheactivityofvariousdescendents

被掛起進程的特征

?不能立即執行

?可能是等待某事件發生。若是，則阻塞條件獨立于掛起條件，即使

阻塞事件發生，該進程也不能執行

?使之掛起的進程為：自身、其父進程、OS

?只有掛起它的進程才能使之由掛起狀態轉換為其他狀態

Suspendvs.BIocked（掛起與阻塞）

問題

1?是否只能掛起阻塞進程？

2?如何激活一個掛起進程?

Suspenvs.BIocked

d區分兩個概念：

??進程是否等待事件，阻塞與否

?進程是否被換出內存，掛起與否

4種狀態組合：

?Ready：進程在內存，準備執行

Blocked：進程在內存，等待事件

Ready,Suspend：進程在外存，只要調入內存

即可執行

Blocked,Suspend：進程在外存，等待事件

注:

處理機可調度執行的進程有兩種：

?新創建的進程

?或換入一個以前掛起的進程

通常為避免增加系統負載，系統會換入一個以前掛起的進程執行。

OneSuspendState

Admit

NewReady

Suspend

SuspendBlocked

此方案存在問題!

Twonewstates

—Blocked,suspend

—Ready,suspend

TwoSuspendStates

Acthate

Blnckd/

BUI

Stipend

(b)WithTwoSuspendStates

具有掛起狀態的進程狀態轉換

?BlockedBlocked.Suspend：OS通常將阻塞進程換出，

以騰出內存空間

?BIocked,Suspend.Ready,Suspend:當BIocked,

Suspend進程等待的事件發生時，可以將其轉換為Ready,

Suspend

?Ready,SuspendReady：OS需要調入一個進程執行時

?ReadyReady,Suspend：一般,OS掛起阻塞進程。但有

時也會掛起就緒進程，釋放足夠的內存空間

?NewReady,Suspend(NewReady)：新進程創建后,可

以插入到Ready隊列或Ready,Suspend隊列。若無足夠的內

存分配給新進程,則需要NewReady,Suspend

具有掛起狀態的進程狀態轉換（續）

?Blocked,SuspendBlocked：當BIocked,Suspend隊列中有一個進程的阻塞事

件可能會很快發生,則可將一個Blocked,Suspend進程換入內存，變為Blocked

?RunningReady,Suspend：當執行進程的時間片用完時，會轉換為Ready。

或,一個高優先級的Blocked,Suspend進程正好變為非阻塞狀態，OS可以將執

行進程轉換為Ready,Suspend狀態

?AIIExit；通常，RunningExito但某些OS中，父進程可以終止其子進程，

使任何狀態的進程都可轉換為退出狀態

ProcessDescription

?問題：

OS如何感知進程、控制進程及其所用的系統資源?

p〃

Virtiuil

Mem?y

ComfMitrr

Resources

3.9Prwessesa?dResources(reMMirceadkxrationat<HM?snapshotintime)

OperatingSystemControlStructures

?Informationaboutthecurrentstatusofeachprocessand

resource

?Tablesareconstructedforeachentitytheoperating

systemmanages

一MemoryTables

-I/OTables

FiIeTables

ProcesTable

Fimirc3.10Genera]Structure*OiM*ratiiwSystemControlTnNc

MemoryTables

?AIlocationofmainmemo-ytoprocesses.

?AIlocationofsecondarymemorytoprocesses.

?Protectionattributesforaccesstosharedmemoryregions.

?InformalionneededtomanagevirtuaImemory（虛擬存儲）

I/OTables

?I/OdeviceisavailabIeorassigned.

?Statusof1/0operation.

?Locationinmainmemorybeingusedasthesourceor

destinationofthe1/0transfer.

FiIeTables

?Existenceoffiles.

?Locationonsecondarymemory.

?CurrentStatus.

?Attributes.

?Some!imesthisinformationismaintainedbyafiIe-managementsystem.

ProcessTabIe

?Whereprocessislocated.

?Attributesnecessaryforitsmanagement.

?ProcessID

?Processstate

?Locationinmemory

ProcessLocation

?ProcessincIudessetofprogramstobeexecuted.

?DatalocationsforIocaIandglobaIvariables.

?Anydefinedconstants.

?Stack.

?ProcesscontroIbIock(PCB)

?CoIlectionofattributes.

?Processimage(進程映像)

?CoIlectionofprogram,data,stack,andattributes.

Processimage

?UserData

?UserProgram

?SystemStack：存放系統及過程調用地址、參數

?ProcessControIBlock(PCB)：OS感知進程、控制進程的數據結構

ProcessControIBlock

?簡稱PCB：是OS控制和管理進程時所用的基本數據結構

?作用：PCB是相關進程存在于系統中的唯一標志；系統根據PCB而感知相關

進程的存在。

?內容：通常情況下，PCB包含Identifiers（標識）、狀態、控制、指針等

多種信息。

ProcessControIBlock（PCB）

?Processidentification

?Identifiers

?Identifierofthisprocess（進程ID）

?Identifieroftheprocessthatcreated

thisprocess（parentprocess）（父進程ID）

?Useridentifier（用戶ID）

ProcessControIBlock

?ProcessorStateInformation

■User-VisibIeRegisters（用戶可見寄存器）

?Auser-visibleregisterisonethatmaybereferencedbymeans

ofthemachineIanguagethattheprocessorexecutes.

?Typically,therearefrom8to32oftheseregisters,although

someRISCimplementationshaveover100.

ProcessControIBlock

?ProcessorStateInformation

?ControIandStatusRegisters

Thereareavarietyofprocessorregistersthatareemployedto

controItheoperationoftheprocessor.Theseinclude

?Programcounter:Containstheaddressofthe

nextinstructiontobefetched.

?Conditioncodes:ResuItofthemostrecent

arithmeticorlogicaIoperation(e.g.rsign,

zero,carry,equaI,overflow).

?Statusinformation:Includesinterrupt

enabled/disabledflags,executionmode.

ProcessControIBlock

?ProcessorStateInformation

?StackPointers

?Eachprocesshasoneormorelast-in-first-out(LIFO)

systemstacksassociatedwithit.

?AstackisusedtostoreparametersandcaIIing

addressesforprocedureandsystemcaIIs.

?Thestackpointerpointstothetopofthestack.

ProcessControIBlock

?ProcessControlInforma11on

?ScheduIingandStateInformation

?Processstate:definesthereadinessofthe

processtobescheduledforexecution(e.g.,

running,ready,waiting,haIted).

?Priority:OneormorefieIdsmaybeusedto

describethescheduIingpriorityofthe

process.

?Scheduling-relatedinformation:ThiswiII

dependonthescheduIingaIgorithmused.

?Event:Identityofeventtheprocessis

awaitingbeforeitcanberesumed

ProcessControIBlock

?ProcessControIInformation

?DataStructuring

?AprocessmaybeIinkedtootherprocess

inaqueue,ring,orsomeotherstructure.

?Aprocessmayexhibitaparent-chiId

(creator-created)reIationshipwith

anotherprocess.

?TheprocesscontroIblockmaycontain

pointerstootherprocessestosupport

thesestructures.

ProcessControIBlock

?ProcessControIInformation

?IntorprocessCommunication

?Variousflags,signaIs,andmessagesmaybeassociated

withcommunicationbetweentwoindependentprocesses.

?ProcessPrivileges

?Processesaregrantedprivilegesintermsofthememory

thatmaybeaccessedandthetypesofinstructionsthat

maybeexecuted.

ProcessControIBlock

?ProcessControIInformation

?MemoryManagement

?Thissectionmayincludepointerstosegment

and/orpagetablesthatdescribethevirtuaI

memoryassignedtothisprocess.

?ResourceOwnershipandUtiIization

?ResourcescontroIledbytheprocessmaybe

indicatedysuchasopenedfiles.Ahistory

ofutiIizationoftheprocessororother

resourcesmayaIsobeincluded;this

informationmaybeneededbythescheduIer.

ProcessControIBlock

Pnxr^

kknlinoiliimkknllfk?atk?iklrntlfkjitlim

1PFWTM%

FrucnaurStaleFroreMTStaleFruce?oStaleL<

InformationInformationInfurmatiuafBlock

Prncf('untruiFrwe*CunlruiC<jolrt4

InhirmilliMiInTormnllimInhirmatkm

[RrStockl?erSUK<txrsuct

FrhateIwrFrhateIwFfivateIf

AcklreviSpacrAcklFMSpacrAckirmSpore

<Fru(*ramNDaUi?(Prufu-an*^Dalai<Pruuram.DaUi

ShftrcdActinoSharedAdrtmftSharedAddrvw

SpaceSpaceSpace

Pnwv^1FnrKVM2PFIKV^A.

Figure3.12txerPrixTe-Memory

TypicalFunctionofanOSKernel（資源管理功能）

?ProcessManagement：進程創建和終止、調度、狀態轉換、同步和通

信、管理PCB

?MemoryManagement：為進程分配地址空間、對換、段/頁管理

?I/OManagement：緩存管理、為進程分配I/O通道和設備

TypicalFunctionofanOSKernel（支撐功能）

?InterrupthandIing（中斷處理）

?Timing（時鐘管理）

?Primitive（原語）：AtomicOperation

?Accounting（統計）

?Monitoring（監測）

ProcessControIPrimitives（原語）

?ProcessSwitch,進程切換

?CreateandTerminate,創建與終止

?BlockandWakeup,阻塞與喚醒

?SuspendandActivate,掛起與激活

WhentoSwitchaProcess

?Clockiinterrupt

?processhasexecutedforthemaximumaIlowabIetimesIice

（時間片）

?I/Ointerrupt

?MemoryfauIt（存儲訪問失效）

?memoryaddressisinvirtuaImemorysoitmustbebrought

intomainmemory

WhentoSwitchaProcess

?Trap（陷阱）

?erroroccurred

?maycauseprocesstobemovedtoExitstate

?SupervisorcaII（管理程序調入）

?suchasfiIeopen

ChangeofProcessState

?SavecontextofprocessorincIudingprogramcounterandotner

registers

?UpdatethePCBoftheprocessthatiscurrentlyrunning

?MovePCBtoappropriatequeue-ready,bIocked

?Selectanotherprocessforexecution

ChangeofProcessState

?UpdatethePCBoftheprocessselected

?Updatememory-managementdatastructures

?Restorecontextoftheselectedprocess

ProcessSwitchingvs.Mode

Switching

?ProcessSwitch,是作用于進程之間的一種操作。

當分派程序收回當前進程的CPU并準備把它分派

給某個就緒進程時，該操作將被引用。

?ModeSwitch,是進程內部所引用的一種操作。當

進程映像所包含的程序引用核心子系統所提供的

系統調用時，該操作將被引用。

ProcessGreation

?Submissionofabatchjob

?UserIogson

?Createdtoprovideaservicesuchasprint

?Processcreatesanotherprocess

ProcessGreation（creat。原語,步

驟）

1.為進程分配一個唯一標識號ID:主進程表中增加一個新的表項

2?為進程分配空間：用戶地址空間、用戶棧空間、PCB空間。若

共享已有空間，則應建立相應的鏈接。

3.初始化PCB:進程標識、處理機狀態信息、進程狀態

4.建立鏈接：若調度隊列是鏈表，則將新進程插入到就緒或（就

緒，掛起）鏈表

5.建立或擴展其他數據結構

ProcessTermination（終止）

?BatchjobissuesHalt\nstruction

?Userlogsoff

?Quit（退出）anappIication

?ErrorandfauItconditions

ReasonsforProcessTermination

?NormaIcompletion,正常結束

?TimeIimitexceeded,超時終止，執行時間超過預計時間

?MemoryunavaiIable,內存不足，無法為進程分配所需的內存空間

?Boundsviolation,越界訪問

?Protectionerror,企圖使用未允許用的數據，或操作方式錯

?Arithmeticerror,計算錯，如除零，或企圖存儲硬件允許的最大數

?Timeoverrun,超時等待某事件發生

ReasonsforProcessTermination

?I/Ofailure,如找不到文件或多次重試仍無法讀寫文件,或無效操作

?InvaIidinstruction,企圖執行不存在的指令

?PriviIegedinstruction,企圖執行特權指令

?Datamisuse,數據類型不符，或未初始化

?Operatingsystemintervention,操作員或OS干預，如發生死鎖的時候

?Parentterminates,sochiIdprocessesterminate

?Parentrequest

ProcessTermination（destroy。原語,

步驟）

1.根據被終止進程的標識符ID,找到其PCB,讀出該進程的狀態；

2.若該進程為執行狀態，則終止其執行，調度新進程執行；

3.若該進程有子孫進程，則立即終止其所有子孫進程

4.將該進程的全部資源，或歸還給其父進程，或歸還給系統

5.將被終止進程（的PCB）從所在的隊列中移出，等待其它程序來

搜集信息

ProcessBlockandWakeup（阻塞的原

因）

?請求系統服務

?啟動某種操作：如I/O

?新數據尚未到達

?無新工作可做

ProcessBIockandWakeup(原語)

?阻塞原語block。

當出現阻塞事件，進程調用阻塞原語將自己阻塞。狀態

變為“阻塞狀態”,并進入相應事件的阻塞隊列

?喚醒原語wakeup()

當阻塞進程期待的事件發生，有關進程調用喚醒原語，

將等待該事件的進程喚醒。狀態變為Ready,插入就緒隊列

ProcessBIockandWakeup(原語)

?掛起原語suspend()

當出現掛起事件，系統利用掛起原語將指定進程或阻

塞狀態進程掛起。進程從內存換到外存，狀態改變：

ReadyReady,Suspend;BIocked

Blocked,Suspend,插入相應隊列

?激活原語active()

當激活事件發生，系統利用激活原語將指定進程激活。

進程從外存換入到內存,狀態改變：Ready.Suspend

Ready;Blocked,SuspendBlocked,插入相應隊列

Thread(線程)

?Anexecutionstate(running,ready,etc.)

?Savedthreadcontextwhennotrunning.

?Hasanexecutionstack.

?Someper-threadstaticstorageforIocaIvariables.

?Accesstothememoryandresourcesofitsprocess.

?aIIthreadsofaprocesssharethis.

Siiigle-llirviMiccIMultitlireaded

Prix^ssModelPr<>cv**sModel

Iser

Acklre**

Space

Eiuiire4.2SingleThreudvdandMultithreadedProcessMcxkls

BenefitsofThreads

?Takeslesstimetocreateanewthreadthana

process.

?Lesstimetoterminateathreadthanaprocess.

?Lesstimetoswitchbetweentwothreadswithin

thesameprocess.

?Sineethreadswithinthesameprocessshare

memoryandfiIes,theycancommunicatewith

eachotherwithoutinvokingthekerneI.

Threads

?SuspendingaprocessinvoIvessuspendingaIIthreadsof

theprocess

?sinceaIIthreadssharethesameaddressspace.

?Terminationofaprocess,terminatesaIIthreadswithin

theprocess.

MuItithreading

?OperatingsystemsupportsmuItipIethreadsof

executionwithinasingIeprocess.

?MS-DOSsupportsasingIethread.

?UNIXsupportsmuItipIeuserprocessesbutonIy

supportsonethreadperprocess.

?Windows2000,SoIaris,Linux,Mach,andOS/2

supportmuItipIethreads.

rmiltlpirpnmw*multiplepnCTM**

oneIhrvxlperpncwmultiplethrvachperpr1n

ImtriKtliiciIrace

Eiuure4.1TlirvmlsaixiPr?MessrsIANDE97

ThreadStates

?KeystatesforathreadRunning,Ready,Blocked.

?Operstionsassociatedwithachangeinthreadstate.

?Spawn（派生），Spawnanotherthread

?Block

?Unblock

?Finish

User-LeveThreads

?AIIthreadmanagementisdonebytheappIication.

?ThekerneIisnotawareoftheexistenceofthreads.

?描述此類線程的數據結構以及控制此類線程的原語在核外子系統中實現。

KerneI-LeveIThreads

?W2KrLinux,andOS/2areexamplesotthisapproach.

?Ker