操作系统-第4章2课时

《操作系统原理》第4章进程管理教师：苏曙光华

技大学学院12主要内容进程概念线程概念进程/线程控制临界资源和临界区同步和互斥信号量和P,V操作经典同步问题重点进程概念和编程应用线程概念和编程应用同步的概念和P-V操作原理同步的编程应用1.进程概念Process3回顾：操作系统的功能之一——进程管理i是内存全局可见变量，运行结果会是什么？程序A

1）

……2）

i

=

100

;……printf(

“A:

i

=

%d.”,i)程序B

1）

……2）

i

=

200

;……printf(“B:i=%d。”,i)结论：在分时（并发）环境下，“程序”的概念不足以描述其运行过程或确保结果正确！→

“进程”概念结果2：A:i=200.×结果3：A:i=100.√结果1：A:

i

=

100.

√

B:

i

=

200.√B:

i

=

200.√B:

i

=

100.

×4程序运行在并发环境中的问题运行过程不确定结果不可再现程序运行 扰（开放性）解决方案：对运行过程施加相互制约引入新概念：进程描述和管理程序的“运行过程”——进程5Windows中查看进程67进程定义进程是程序在某个数据集合上的一次运行活动。进程的特征动态性进程是程序的一次执行过程，动态产生/消亡并发性进程可以同其他进程一起向前推进；异步性进程按各自速度向前推进独立性进程是系统分配资源和调度CPU的单位；8进程与程序的区别动态性进程是动态的：程序的一次执行过程程序是静态的：一组指令的有序集合生命期进程是暂存的：在内存驻留程序是长存的：在介质上长期保存。程序和进程的对应一个程序可能有多个进程。一个进程可以涉及多个程序。9进程的类型按使用资源的权限系统进程：指系统内核相关的进程。用户进程：运行于用户态的进程。按对CPU的依赖性偏CPU进程：计算型进程偏I/O进程：侧重于I/O的进程其他标准…Linux进程分类（按运行特点分）1)交互进程2)批处理进程3)守护进程（

daemon进程）服务程序,随系统启动而启动。很多系统服务通过守护进程完成。守护进程的名字往往以字母‘d’结尾独立于控制终端10常见守护进程httpd：Web服务器Apache守护进程，可用来提供HTML文件以及CGI动态内容服务crond：cron是Unix下的一个传统程序，该程序周期地运行用户调度的任务。klogin：登陆守护进程。iptables：iptables

守护进程。cups：cups(Common

UNIX

Printing

System)是通用UNIX打印守护进程11控制终端在Linux中，每一个与用户进行交流的界面称为终端。每一个从终端开始运行的进程都依附于该终端，当该终端关闭时，其中的进程都会自动关闭。这个终端就称为这些进程的控制终端.守护进程能突破它的控制终端的限制，即使控制终端被关闭，它也不会被关闭，除非系统关闭时才退出。如果想让某个进程不因为终端关闭而关闭，就必须把这个进程变成一个守护进程。1213进程的状态运行状态（Running）进程已经占有CPU，在CPU上运行。就绪状态（Ready）具备运行条件但由于无CPU，暂时不能运行阻塞状态（Block）【等待（Wait）】因为等待某项服务完成或信号来到而不能运行的状态例如等待：系统调用，I/O操作，合作进程的服务或信号…就绪阻塞

进程状态的变迁进程的状态可以依据一定的条件相互转化。服务：I/O操作信号：事件（EVENT）运行就绪运行：进程调度运行就绪：时间片到；被抢占运行阻塞：服务请求；等待信号阻塞就绪：服务完成；信号来到14具有新建(new)和终止(terminate)状态的进程状态运行状态就绪状态新建状态提交进程调度终止状态退出阻塞状态时间片到等待I/O或事件I/O或事件完成15支持挂起(suspend)和解挂(resume)操作的进程状态挂起(suspend)和解挂(resume

，激活activate)挂起：用户或OS将进程有意暂停；解挂：将挂起的进程继续。阻塞：就绪：运行阻塞（阻塞时挂起）和活动阻塞（正常阻塞）；就绪（就绪时挂起）和活动就绪（正常就绪）。就绪：挂起活动就绪 就绪：挂起活动阻塞就绪阻塞阻塞阻塞：挂起活动就绪：解挂活动阻塞：解挂就绪：期待的事件/信号发生16支持挂起(suspend)和解挂(resume)操作的进程状态活跃就绪56就绪7运行108阻塞活跃阻塞917思考题1.在单CPU的系统中有N个进程运行进程最多几个，最少几个？就绪进程最多几个，最少几个？等待进程最多几个，最少几个？2.有没有下列状态转换？阻塞 运行就绪

等待

就绪运行阻塞18Linux进程的状态可运行态就绪：TASK_RUNNING在就绪队列中等待调度。运行：正在运行阻塞（等待）态浅度：TASK_INTERRUPTIBLE（可中断）可被其他进程的信号或时钟中断唤醒。深度：TASK_UNINTERRUPTIBLE（不可中断）不能被其他进程通过信号和时钟中断唤醒。僵死态：TASK_ZOMBIE进程终止执行，

大部分资源挂起态：TASK_STOPPED进程被挂起。19fork()TASK_RUNNING就绪TASK_INTERRUPTIBLE浅度阻塞当前进程时间片耗尽资源到位

wake_up_interruptible()或收到信号wake_up()资源到位wake_up()schedule()收到信号SIGCONTwake_up()TASK_ZOMBIE僵死do_exit()ptrace()schedule()TASK_STOPPED挂起TASK_UNINTERRUPTIBLE深度阻塞等待资源到位

占有CPU

等待资源到位sleep_on()

执行

interruptible_sleep_on()schedule()

schedule()2021进程的描述进程控制块(Process

Control

Block，PCB)描述进程的状态、资源、和相关进程的关系的一种数据结构。PCB是进程的标志创建进程时创建PCB；进程撤销后PCB同时撤销。进程1:PCB1进程2:PCB2进程3:PCB3……….……….….数据进程＝程序＋PCBPCB3代码进程程序22PCB的数据结构PCB中的基本成员name（ID）：进程名称（标识符）status：状态next：指向下一个PCB的指针start_addr：程序地址priority：优先级cpu_status：现场保留区(堆栈)comm_info：进程通信机制process_family：own_resource：资源23Linux的进程控制块PCB：task_structstruct

task_struct（1）进程状态（2）调度信息（3）标识符（4）

进程通信信息（5）

信息（6）时间和计时器（7）文件系统（8）虚拟内存信息（9）处理器信息24Linux进程描述符SOURCEINSIGHT25Task_struct

{ //

linux/sched.hVolatile

long

state;Long

counter;Long

priorityUnsigned

long

signals;

//

pending

sigsUnsigned

long

blocked;

//masked

sigsInt

pid,

pgrp,

uid,

euid,

gid,

egid;减至0后进入就绪。signals

：信号处理函数的。priblocked：阻塞的信号pid，uid，gid：和进程标识有关struct

linux_binfmt;struct

task_struct

p_opptr; //

ptr

to

original

parent（原始父进程）struct

struct

task_struct

p_pptr;

//

ptr

to

immediate

parent

（父进程）task_struct

p_cptr;

//

ptr

to

most

recent

child

（

子进程）struct

task_struct

p_ysptr;

//ptr

to

following

sibling（新兄弟）struct

task_struct

p_osptr;

//ptr

to

previous

sibling（老兄弟）struct

task_struct

*next_task;

//

in

process

liststruct

task_struct

*prev_task;

//

in

processliststruct

task_struct

*next_run;

//

in

ready

queuestruct

task_struct

*prev_run;

//in

ready

queuep_pptr等：和进程链表，遍历进程相关系有关26fs等：和文件系统相关mm：和内存相关struct

mm_struct

mm[1];Unsigned

long

kernel_stack_page;Unsigned

long

saved_kernel_stack;Struct

fs_struct

fs[1];Long

utime,

stime,

cutime,

cstime,

start_time;Struct

sem_queue

*semslee

;Struct

wait_queue

*wait_chldexit;Struct

sigaction

sigaction[32];Struct

rlimit

rlim[RLIM_NLIMITS];Struct

thread_struct

tss;

//

includes

saved

registersUnsigned

long

policy;

//

SCHED_FIFO,SCHED_RR,SCHED_OTHERUnsigned

long

rt_priority;//

for

SMPsInt

processor,

last

processor;Int

lock_depth;…}policy等：和进程调度策略相关27进程队列或进程遍历相关的成员struct

task_struct

*next_task,

*prev_task;所有进程放在一个双向链表中：task

list28进程

关系相关的成员变量2930和内存相关的成员变量p->mm

指向mm_struct结构进程的地址空间。p->active_mm

指向mm_struct结构进程的当前活动地址空间。和文件相关的成员变量p->fs，文件系统信息：root

和挂载点；当前工作 和挂载点。p->files字段包含了文件句柄表。31和进程标识相关的成员变量LINUX进程的标识PIDPPID：父进程IDPGID：进程组IDLINUX进程的用户标识UID：用户IDGID：用户组ID获取进程标识的典型函数每个进程有唯一

：PID除init进程外，每个进程都可用kill命令杀死。当一个新进程ID达到系统最大值时，系统重新使用最小且当前未用的PID号。父进程ID：PPID3233获取进程标识的典型函数获取进程ID和父进程IDpid_t

getpid(void)pid_t

getppid(void)函数成功返回进程PID或PPID，失败返-1。实例int

main(int

argc,char

*argv[]){printf(“This

program‘s

pid

is

%d\n”,getpid( ));return

0;}34进程组号（PGID）进程组是一个或多个进程的集合。当进程生成子进程时，OS自动创建一个进程组。获取进程PGIDextern

pid_tgetpgid

(

pid_t

pid)参数pid为要获得进程组号的进程号执行成功返回PGID，失败则返回-1进程的用户ID用户ID当root创建新用户时，每个用户分配一个ID（UID）。可以ls–l命令查看一个文件的用户UID信息。[root@localhost

～]#

ls

-l

/etc/passwd-rw-r--r--

1

root

root

1582

Mar

19

06:37

/etc/passwd//属性文件数拥有者group

文件大小日期文件名文件的创建者为root，即UID

为root进程UID用于表示进程的创建者，只有进程的创建者和root用户才有权限对进程进行操作。真实用户IDextern

uid_t

getuid

(void)执行成功返回进程UID；执行失败则返回-13536进程用户组号（GID）GID创建进程的用户所在组号为该进程的进程用户组号。获取GIDextern

uid_t

getgid

(void)执行成功将返回GID。执行失败则返回-1进程的上下文进程的上下文Context，进程运行环境≈

PCB分时系统的进程切换过程进程的上下文在CPU

换换进进程的上下文进入CPU（从栈上来）换出进程的上下文离开CPU

（到栈上去）37进程切换的过程(例子：P0和P1)上下文切换CPU额外开销与硬件环境相关38进程的队列【课后看】多个进程在系统中的组织形式有效管理进程队列的形式线性方式方式索引方式39Windwos进程在内存中的结构32位系统4GB=用户空间+内核空间。代码段初始化数据段数据段用户空间:0~3GB内核空间:3GB~4GB组成1）代码段2）数据段3）堆栈段未初始化数据段堆栈用户空间内核空间402.进程控制41进程控制的概念进程控制的概念在进程生存全期间，对其全部行为的控制四个典型的控制行为创建撤消阻塞唤醒控制

段：原语由若干指令构成的具有特定功能的函数具有原子性，其操作不可分割4243进程控制原语创建原语撤消原语阻塞原语唤醒原语进程创建功能创建一个具有指定标识（ID）的进程参数进程标识、优先级、进程起始地址、CPU初始状态、资源 等。44创建进程的过程创建一个空白PCB赋予进程标识符ID为进程分配空间初始化PCB默认值相应的进程队列新进程 就绪队列45进程创建原语的伪代码Create(Si,Mi,Pi)

//CPU的状态,内存,优先级{p

=

Get_New_PCB(

);pid

=

Get_New_PID(

);p->ID

=

pid;p->CPU_State

=

Si;p->Memory

=

Mi;p->Priority

=

Pi;//分配新的PCB//分配进程的PID//设置进程的PID//CPU的状态//内存//优先级p->Status.Type="Ready";//进程状态p->Status.Lis

t

=

RL;……Insert(RL,

p);Scheduler(

);//进程队列RL：Ready

List//将进程p

就绪队列//调度程序}4647进程撤销功能撤消一个指定的进程收回进程所占有的资源，撤消该进程的PCB进程撤销的时机/事件正常结束异常结束外界干预参数被撤消的进程名（ID）撤销原语的实现在PCB队列中检索出该PCB获取该进程的状态。若该进程处在运行态，立即终止该进程。【递归】检查是否有子进程，先“撤销”子进程。进程占有的资源将进程从PCB队列中移除4849进程阻塞功能停止进程的执行，变为阻塞。阻塞的时机/事件请求系统服务（由于某种原因，OS不能立即满足进程的要求）启动某种操作（进程启动某操作，阻塞等待该操作完成）新数据尚未到达（A进程要获得B进程的中间结果，A进程等待）无新工作可作（进程完成任务后，自我阻塞，等待新任务到达）参数阻塞原因不同原因构建有不同的阻塞队列。阻塞原语的实现停止运行将PCB

“运行态”改“阻塞态”相应原因的阻塞队列转调度程序5051进程唤醒功能唤醒处于阻塞队列当中的某个进程。引起唤醒的时机/事件系统服务由不满足到满足完成新数据到达进程提出新请求（服务）参数被唤醒进程的标识3.Linux和Windows进程控制5253Linux进程控制进程的创建在Linux系统初启时，只生成1号进程(初始化进程)其他进程由当前进程通过系统调用fork(

)建立。fork( )执行流程分配task_struct结构为新进程堆栈分配物理页。拷贝父进程的内容正文段、用户数据段及系统数据段task_struct的大部分内容，并对子进程中有别于父进程的项进行初始化。把新进程的task_struct结构地址保存在task指针数组中。子进程由fork( )创建后，通常处于就绪状态。Unix/Linux执行用户命令使可以建立进程54进程的阻塞父进程通过系统调用wait( )等待子进程结束wait( )的参数指定父进程等待的子进程。如果子进程尚未终止，则父进程被阻塞。进程的撤销进程结束自己时，可通过系统调用exit( )来实现。首先，

进程占用的大部分资源关闭文件描述符、

内存等其次，进程进入“僵死”状态，并返回状态参数，使等待其结束的父进程取得参数被唤醒执行。55创建进程——fork#include

<sys/types.h>#include

<unistd.h>pid_tfork(void);例：

pid_t

pid

=

fork(

);fork的调用者称父进程，新建的进程称子进程。子进程是父进程的

。关于fork

的返回值：pid▲在子进程中，pid

=0▲在父进程中，pid>0父进 子进程并发运行。56子进程是父进程的

。父进

子进程并发运行。思考：下面程序在屏幕上将输出什么内容？//文件名testfork.c

，测试fork函数intmain(void){fork(

);printf(“This

string

will

be

output

twice!\n”);return

0;}[root@localhost

~]#

./testforkThis

stringwill

be

output

twice!This

string

will

be

output

twice!57思考：下面程序在屏幕上将输出什么内容？fork()函数创建进程intmain(void){pid_tpid;pid

=

fork(

);if(

pid

=

=0

)printf(

“String

in

child

Process!\n”

);elseif(pid

>

0)printf(

“String

in

parent

Process!\n”

);}屏幕输出3：String

in

child

Process!String

in

parent

Process!关于fork

的返回值：pid在子进程中，pid=0在父进程中，pid>0屏幕输出4：String

in

parent

Process!String

in

child

Process!58fork执行的示意fork创建一个子进程，父进程并与之并发59fork函数的三个版本传统版本——单一函数创建进程地址空间；读入可执行文件；开始执行UNIX版本——分创建和执行两步fork函数：exec函数：当前进程创建子进程可执行文件并载入进程空间执行Linux版本——写时父进程的资源被设置为只读，当父进程或子进程试图修改某些内容时，内核才在修改前将该部分进行拷贝——写时fork()的实际开销只是父进程的页表以及给子进程创建唯一的PCB。60fork函数的实现（do_fork( )

）/kernel/fork.cint

do_fork

(unsigned

long

clone_flags,unsigned

long

stack_start,struct

pt_regs

*regs,unsigned

long

stack_size);为子进程分配task_struct空间；初始化子进程task_struct；父进程的file，fs，sighand，mm等信息；……6162int

do_fork

{

//开始struct

task_struct

*p;//分配物理页面存放task_struct结构和内核空间的堆栈p

=

alloc_task_struct(

);//把当前进程task_struct结构中所有内容都拷贝到新进程中*p

=

*current;//判断用户进程数量是否超过了最大限制，否则不许forkif

((&p->user->processes)

>=

p->rlim[RLIMIT_NPROC].rlim_cur))goto

bad_fork_free;//子进程初始状态设TASK_UNINTERRUPTIBLEp->state

=

TASK_UNINTERRUPTIBLE;/*

拷贝进程的所有信息*/copy_files(clone_flags,p);copy_fs(clone_flags,p);copy_mm(clone_flags,p);//进程创建后与父进程

起来形成一个进程组list_add(&p->thread_group,

¤t->thread_group);/*唤醒进程，将其挂入可执行队列等待被调度*/wake_up_process(p);}

//do_fork

结束63进程的终结进程结束调用exit()或在main函数中return被信号和异常

终结进程终结时要

其占用的资源并报告给父进程。通过系统调用由内核函数do_exit()完成。回收各种内核数据结构，设置状态为僵死TASK_ZOMBIE将其所有子进程托付给init进程调用schedule( )函数，选择一个新进程运行。64void

exit(int

status);可利用参数status传递进程结束时的状态调用exit后的进程不是马上

，而是变为僵尸状态，放弃了几乎所有内存空间，不再被调度，但保留有pcb信息供wait收集，包括：正常结束还是异常结束（被退出）占用总系统cpu时间缺页中断次数收到信号的数目……6566Windows进程进程是被加载到内存的、正在运行的应用程序实例。进程由内核对象和地址空间所组成内核对象PCB地址空间包括代码/数据/堆/栈/堆上动态分配的空间/Windows进程CreateProcess创建新进程创建进程内核对象，创建虚拟地址空间装载EXE和/或DLL的代码和数据到地址空间中创建主线 线程内核对象启动主线程，进入主函数（main）67BOOL

CreateProcess(LPCTSTR

lpApplicationName, //

指定可运行模块LPTSTR

mandLine,

//指定可运行模块命令行即参数LPSECURITY_ATTRIBUTES

lpProcessAttributes，LPSECURITY_ATTRIBUTES

lpThreadAttributes,BOOL

bInheritHandles,DWORD

dwCreationFlags,

//创建标志LPVOID

lpEnvironment,LPCTSTR

lpCurrentDirectory,LPSTARTUPINFO

lpStartupInfo,LPPROCESS_INFORMATION

lpProcessInformation);

//lpProcessInformation:接收新进程的识别信息68Windows创建进程的其它函数WinExec运行指定的程序S

Execute（）可以关联文件和EXE6970结束进程主函数返回ExitProcessVOID

ExitProcess(UINT

uExitCode)TerminateProcessTerminateProcess

(HANDLE

hProcess,UINT

uExitCode

)5.线程71线程传统进程的特点：进程内函数或模块间只能顺序执行！现代OS进程：允许多个路径（函数或模块）并发执行。word：至少4个路径（函数或模块）进程键盘输入§格式化§拼写检查§ 打印网络程序：至少3个路径接收§处理§发送路径：线程(Thread)多个路径并发执行7273线程（Thread）目的：提高系统的并发度线程是进程内的一个可执行实体，且能被CPU调度。进程内可以有多个线程，线程可以并发。和进程有相似操作和状态线程基本不拥有资源，共享进程的全部资源除程序计数器、一组寄存器、栈之外线程的创建和管理开销比进程小74Windows线程基本概念当创建进程时，系统自动创建一个主线程。主线程可以创建其他线程。提供多个并发路径，加快执行效率，提高交互性能。线程的创建AfxBeginThread

（MFC库）CreateThread（WINAPI库）CreateRemoteThread（WINAPI库）线程函数的原型UINT

ThreadProc

(LPVOID

lpParam)CreateThread在调用者的进程空间创建一个新的线程函数HANDLE

CreateThread(LPSECURITY_ATTRIBUTES

lpThreadAttributes,//安全属性DWORD

dwStackSize,

//线程堆栈大小LPTHREAD_START_ROUTINE

lpStartAddress,//线程函数LPVOID

lpParameter,

//线程函数参数DWORD

dwCreationFlags,

//创建标志LPDWORD

lpThreadId

//线程ID);75CreateRemoteThread创建 线程：在

进程的地址空间创建线程HANDLE

CreateRemoteThread(HANDLE

hProcess, //

目标进程LPSECURITY_ATTRIBUTES

lpThreadAttributes, //

安全属性DWORD

dwStackSize, //

堆栈大小LPTHREAD_START_ROUTINE

lpStartAddress, //

线程函数LPVOID

lpParameter, //

线程参数DWORD

dwCreationFlags,

//创建标志LPDWORD

lpThreadId

//线程ID);76Linux

线程线程的创建

pthread_create(

)int pthread_create(

pthread_t

*

thread,pthread_attr_t

*attr,void

*(*start_routine)(void

*),void

*

arg);参数：thread：返回的线程句柄；attr：指定线程的属性；start_routine：线程函数 地址；arg：线程函数的参数7778Linux

线程线程的退出pthread_exit

(void

*

retval

)参数：retval：线程退出的返回值两个线程分别输出o,

World795.临界区和临界资源80两个并发进程的运行：结果可能出错且不可再现i是内存全局可见变量问题：如何使并发的结果正确呢？程序A

1

程序B

1）

……

）

……2）

i

=

100

;

2）

i

=

200

;3）

……

3）

……printf(“A:i=%d.”,i)

4）printf(“B:i=%d。”,i)……

5）…………

6）……结果1：A:

i

=

100.

√

B:

i

=

200.√结果2：A:

i

=

200.

×

B:

i

=

200.√结果3：A:

i

=

100.

√

B:

i

=

100.

×81程序A

1）

……2）

i

=

100

;3）

……4）printf(

“A:

i

=

%d.”,

i)56…………√两个并发进程的运行：结果可能出错且不可再现i是内存全局可见变量问题：如何使并发的结果正确呢？程序B

1）

……2）

i

=

200

;……printf(“B:i=%d。”,i)…………答案：设定程序的特定区域不可中断。结果

：A:

i

=

100. B:

i

=

200.82临界资源和临界区临界资源[Critical

Resource]一次只允许一个进程独占

（使用）的资源例：前面例子中的共享变量i临界区[Critical

Section]进程中

临界资源的程序段。83临界资源和临界区的示意程序段A程序段B程序段C临界区临界区临界区进程1进程2进程3全局变量：i临界资源84临界资源和临界区的例子i是全局变量：临界资源程序A程序B1）

……1）

……2）

……2）

……3）

i

=

100

;i3）

i

=

200

;4）

……4）

……5）

…...5）

…...6）Printf(

“i

=

%d”,i)6）Printf(

“i

=

%d”,i)7)

……7)

……8)

……8)

……85临界资源和临界区临界区和临界资源的共享特点临界资源的 具有排他性；并发进程不能同时进入“临界区”；临界区作为“整体”被 ，不能被其它进程中断。86设计临界区机制的四个原则空闲让进当无进程处于临界区时，任何

进程可以进入临界区。忙则等待当临界区忙时（某个进程已处于其内)，其他进程必须在临界区外等待。有限等待进程进入临界区的请求应在有限时间内得到满足让权等待等待进程应该放弃CPU。（让其它进程有机会得到CPU）。87）临界区的方法问题如何标识临界区能否进入或临界资源可用？如何改变临界区或临界资源的可用标识/状态？临界区的方法硬件方法方法（锁信号量88硬件方法中断

方法进入临界区前执行“关中断”指令离开临界区后执行“开中断”指令测试并设置指令(

Test and

Set)TS(boolean

*lock)交换指令SWAP(int

*a,

int

*b)89方法设置一个“标志”表明临界资源“可用”还是“不可用”？在进入临界区之前检查标志是否为“可用”状态？若为“不可用”状态：进程在临界区之外等待若为“可用”状态：进程进入临界区，并将标识立即改为“不可用”状态退出临界区之后修改标志为“可用”状态锁是实现临界区

的 方法之一。90锁表示临界资源（临界区）是否可用的标志。可使用的状态：0不可使用的状态：1锁的操作【修改锁的状态】上锁（置1，不可用）开锁（置0，可用）019192上锁[原语]1.检测锁的值（0或1）2.如果为1，则返回第1步3.如果为0，则置其为1进入临界区，用上锁原语。LOCK(S)

//上锁操作{test: if

(S

=

=

1

)goto

test;

//测试锁位else //

S

=

=

0S=1;

//上锁}开锁【原语】1.把锁的状态置0UnLock(S)

//开锁操作{S=0;

//开锁}退出临界区，用开锁原语。93上锁操作临界区开锁操作上锁操作临界区开锁操作用锁机制 临界区目标：确保并发进程最多只有1个处于在临界区中。1.初始化锁的状态S=0(可用)2.进入临界区之前执行上锁操作；3.

离开临界区之后执行开锁操作。进程A

进程B目标：当一个进程在临界区中的时候，另外一个进程如果试图进入，则被阻塞。只有其中一个进程退出临界区后，另外一个进程才能进入。94用锁机制 临界区程序A

1）

……2）

Lock(

S

)；3）

i

=

100

;程序B

1）

……2）

Lock(

S)；3）

i

=

200

;………...Printf(

“i

=

%d”,i)UnLock(

S

)；……………...Printf(

“i

=

%d”,i)UnLock(

S

)；……5

2次课956.同步和互斥96进程的互斥关系进程的互斥关系的例子程序A程序B1）

……1）

……2）

……2）

……3）

i

=

100

;i3）

i

=

200

;4）

……4）

……5）

…...5）

…...6）Printf(

“i

=

%d”,i)6）Printf(

“i

=

%d”,i)7)

……7)

……8)

……8)

……97进程的互斥关系多个进程由于共享具有独占性的资源，必须协调各进程对资源的存取顺序：确保没有任何两个或以上的进程同时进行资源的存取操作。资源：临界资源资源的存取操作：临界区互斥和资源共享相关98进程的同步关系若干合作进程为了共同完成同一个任务，需要相互协调运行步伐：一个进程的某个操作开始之前必须要求另一个进程的某个操作已经完成，否则前一个进程只能等待。99进程的同步关系的例子和售票员之间的操作属于同步关系：起步，行驶，停车售票员：关门，售票，开门同步关系：起步前先关门，否则等待；开门前先停车，否则等待。100中进程的同步关系若干合作进程为了共同完成同一个任务，需要相互协调运行步伐：一个进程的某个操作开始之前必须要求另一个进程的某个操作已经完成，否则前一个进程只能等待。合作进程 先后关系或某个操作能否 则只能等待。互斥关系进

否属1017.信号灯和P-V操作102103信号灯的概念P-V操作的定义P-V操作实现进程同步经典同步问题信号灯的概念信号灯是一种卓有成效的进程同步机制。1965年荷兰学者Dijkstra(迪

彻)提出。1930.5-2002.8红绿灯控制各向车流有序通过交叉路口。104信号灯机制信号灯数据结构信号灯的操作信号灯的应用105信号灯机制信号灯数据结构信号灯变量定义为一个二元矢量（S,q），其中：S是整数，q是队列(进程PCB集合)。S：初值非负（S又称信号量）q：初值为空集struct

SEMAPHORE{int

S;

//整数，初值非负pointer_PCB

q;

//队列：进程PCB指针,初值空集}106信号灯机制信号灯的操作进程在运行过程受信号灯控制，并能改变信号灯。受控制：信号灯可以阻塞或唤醒进程。改变：信号灯的状态可以被进程改变。两个操作P操作（函数或过程，P(S,q)）V操作（函数或过程，V(S,q)）P，V是荷兰语：Passeren通过，Vrijgeven。107信号灯的操作P操作，P(S,q)

，简记P(S)S值减1；若差大于或等于零，该进程继续；若差小于零，则该进程阻塞并加入到q中，并转调度函数。P(S,q){S=S-1;

关键：S初值设置要合理。if

(S

<0

){Insert(

Caller

,

q

);Block(

Caller

);转调度函数();}}108信号灯的操作V操作，V(S,q)

，简记V(S)s值加1；若和大于零，该进程继续；若和小于或等于零，该进程继续同时从q中删除并唤醒一个进程。V(S,q){s

=

s+

1;if

(

s

≤

0

){Remove(

q, pid);//pid：进程IDWakeup(

pid

);}}109信号灯机制信号灯的应用实现进程互斥实质是实现对临界区的互斥1个临界资源：允许最多1个进程处于临界区M个临界资源：允许最多M个进程同时处于临界区应用过程进入临界区之前先执行P操作；（可能阻塞当前进程）离开临界区之后再执行V操作；（可能唤醒某个进程）S的初值设置要合理。实现进程同步110实现进程互斥1个临界资源的情况：允许最多1个进程处于临界区当已有1个进程在临界区时，其它进程如果试图进入则被阻塞。只有当临界区没有任何进程时，另外一个进程才能进入。S初值

=

1

S初值

=

0

？ S初值

=

2

？ S初值

=

3

,4,…

？P（S

,

q）V（S

,

q）P（S

,

q）临界区V（S

,

q）临界区进程1P（S

,

q）临界区V（S

,

q）进程2

进程N……思考：在N个进程并发的过程中，S可能的取值范围是多少？111实现进程互斥，假定M=2）M个临界资源的情况：允许最多M个进程处于临界区

（为方便当M个进程处于临界区时，其它进程如果试图进入则被阻塞。只有当其中某个进程退出临界区后，另外一个进程才能进入。S初值

=

M2 S初值

=

1

？ S初值

=

3

？ S初值

=

0,

4

,5,…

？P（S

,

q）V（S

,

q）P（S

,

q）临界区V（S

,

q）临界区进程1P（S

,

q）临界区V（S

,

q）进程2

进程N……思考：在N个进程并发的过程中，S可能的取值范围是多少？112实现进程互斥的例子例子：3个进程Pa,Pb,Pc

。临界资源数量为1，CSa,b,c是临界区。Pa(

){p(mutex

);CSav(mutex);}Pc(

){p(mutex

);思考：在并发过程中，mutex的取值范围是多少?main(

){/*

信号量mutex

*/int

mutex

=

1;cobegin//并发Pa(

);Pb(

);Pc(

);coend//并发结束}}CScv(mutex);Pb(

){p(mutex

);}CSbv(mutex);113信号灯机制信号灯的应用实现进程互斥实现进程同步实质：关键操作之前能使进程暂停和关键操作之后能唤醒某进程继续。一个操作只有满足条件才能继续进行，否则只能等待。应用过程某个关键操作之前执行P操作；某个关键操作之后执行V操作；关键：定义合适且有意义的信号量S并注意初值设置。114实现进程同步：例子——vs售票员起步；行驶停车；售票员关门；售票；开门；要求只有售票员关门后，才能起步；只有 停车后，售票员才能开门。115int

S1=0; /*

门是否关好？0：没有，1：关好*/int

S2=0;

/*

车是否停稳？0：没有，1：停稳*/售票员进程：while

(true){关门；进程：while

(true){P(S1)；起步；行驶；停车售票；}

开门;}P(S2)；V(S2)；V(S1)；116同步例子——进程流图P1，P2，P3是协作进程。int

S2

=

0;int

S3

=

0;/*

P2进程能否执行，1能，0不能*//*

P3进程能否执行，1能，0不能*/P2(

)P1(

){…功能1…}P3(

){}P2P3P1{P(S2);…功能2…}P(S3);…功能3…V(S2);V(S3);117同步例子——进程流图计算：(

a+b)*(c+d)–

e/f

=

？int t1,

t2,

t3,

t4,

t5;t1

=

a

+

b;t2

=

c

+

d;t3

=

e

/

f;t2=c+dt1=a+bt3=e/ft4

=

t1

*

t2;t5

=

t4

-

t3;t4=t1×t2t5=t4-t36

1次课118同步例子——共享缓冲区个缓冲区Buffer共享缓冲区的输入和输出进程INPUT和进程OUTPUT共INPUT把数据输入Buffer；OUTPUT从Buffer中读出数据同步要求BufferINPUTOUTPUT只有INPUT把数据输入Buffer后，OUTPUT才能读出。仅当buffer有数据,OUTPUT才能被读出，否则必须等待。只有OUTPUT把数据读出后，INPUT才能输入新数据。仅当Buffer为空时，INPUT才能输入，否则必须等待。119同步例子——共享缓冲区int

S1＝

0;int

S2＝

1;/*缓冲区中有无数据？0：没数据，1：有数据*//*缓冲区中有无空位？0：没空位，1：有空位

*/OUTPUT(

){while(还有数据待读出){从缓冲区读出数据；}}INPUT(

){While(还有数据待输入){输入新数据到缓冲区；}}120同步问题的本质进程的某个操作只有满足某条件才能继续运行，否则只能阻塞。进程的某个关键操作完成之后可能需要去唤醒另外一个受其影响的进程。同步实质：进程的有条件地暂停或继续。121122Windows进程同步机制临界区（锁）CRITICAL_SECTION互斥量(Mutex)

（锁）HANDLE信号量（Semaphore）HANDLE事件（Event）HANDLE等待操作WaitForSingleObject和WaitForMultipleObjects7