进程是程序中一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位,由程序块、进程控制块(PCB)和数据块三部分组成
程序和进程区别:进程是程序一次执行过程。程序是一个静态的概念,而进程是动态的概念。
进程的状态
进程的三态模型
-
等待又被称为阻塞
-
进程在就绪时,所有需要的资源都就绪,只需要等待CPU调度
-
运行状态可以回到就绪,也可以进入等待(阻塞)。当CPU时间片用完,不能再占用资源了,或者有更高优先级的进程调度时,低优先进程会回到就绪;运行完很有可能会等待某些事件(比如I/O),会进入等待(阻塞)状态
-
进入等待时,只有等待的事件发生才会进入就绪状态
五态模型
了解即可,主要考查三态
进程的互斥与同步
进程的互斥:合作进程的间接制约关系,因为需要争夺临界资源(比如图中独木桥)
进程的同步:合作进程之间的直接制约关系
PV操作
一些概念:
临界资源:诸进程间需要互斥方式对其进行共享的资源,如打印机
临界区:每个进程中访问临界资源的那段代码
信号量:一种特殊变量
除了起始与终止进程,PV操作在进程中只能有一次,并且需要成对出现
详情:
P操作:申请资源的操作
V操作:释放资源的操作
S:信号量
分析:
对于P操作,申请资源,使信号量-1,如果信号量(代表资源数)不够,那么就阻塞,直到资源足够,被V操作唤起,就继续P操作
对于V操作,释放资源,使信号量+1,如果信号量(资源数)<=0,说明有任务在阻塞,那么就唤起一个阻塞的任务
举个例子:
有两个某类资源,四个进程A、B、C、D要用该类资源,最开始S=2,当A进入,S=1,当B进入S=0,表明该类资源刚好用完, 当C进入时Sem=-1,表明有一个进程被阻塞了,D进入,S=-2。当A用完该类资源时,进行V操作,S=-1,释放该类资源,而这时S<0,表明有进程阻塞在该类资源上,于是唤醒一个。
互斥模型
多个进程共享一台打印机的问题
互斥模型初始信号量为1
P(S); 使用打印机; V(S); 后续代码;
同步模型
单缓冲区生产者、消费者问题
来一道例题
前驱图
如图所示的前驱图,每一个圆圈表示一个进程,被箭头指向的必须等待指向者完成
箭头尖是入度 根部是出度
死锁问题
如果一个进程在等待一件不可能的事情,那么会发生进程死锁
如果一个或多个进程死锁,就会导致系统死锁
例:
系统有五个进程: A、 B、 C、 D、 E,这五个进程都需要四个系统资源,系统至少有多少个资源,不可能发生死锁?
形成死锁的必要条件
四个必要条件:互斥、保持和等待、不剥夺、环路等待
如果要预防死锁,就要打破这四个必要条件
如果要避免死锁,需要有序资源分配法或者银行家算法
有序资源分配:逐进程分配资源,类似于排队
银行家算法:对资源合理分配,规则如下:
-
当一个进程对资源最大需求量不超过系统资源总数时可以接纳
-
进程可以分期请求资源,但总数不能超过最大需求数
-
系统现有资源不能拿满足进程需要时,对进程请求可以推迟分配,但总能使进程在有限时间得到资源
银行家算法例子:
进程资源图
主要考察节点的阻塞类型
资源出箭头代表分配,用完之前,不能给其它资源用;入箭头代表申请资源