计算机操作系统——进程管理
一、进程与线程
(一)进程与线程的基本概念
1. 进程
(1) 进程的定义
从不同的角度可以有不同的定义,较典型的有:
- 进程是程序段一次执行。
- 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
- 进程是具有独立功能的程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位。
引入进程实体的概念后,我们可以把传统OS中的进程定义为: “进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。”
进程实体: 由程序段、相关的数据段和PCB三部分便构成了进程实体(又称进程映像)。
PCB: 进程控制块(Process Control Block),用来描述进程的基本情况与活动过程,是操作系统为程序执行分配的一个专门的数据结构。
(2)进程的特征
- 动态性: 进程的实质是进程实体的执行过程,因此,动态性就是进程最基本的特征。动态性还表现在: “它由创建而产生,由调度而执行,由撤消而消亡。”可见,进程实体有一定的生命期,而程序则只是一组有序指令的集合,并存放于某种介质上,其本身并不具有活动的含义,因而是静态的。
- 并发性,是指多个进程实体同存于内存中,且能在一段时间内同时运行。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行。因此,并发性是进程的另一重要特征,同时也成为OS的重要特征。而程序(没有建立 PCB)是不能参与并发执行的。
- 独立性。在传统的OS中,独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
- 异步性,是指进程是按异步方式运行的,即按各自独立的、不可预知的速度向前推进。正是源于此因,才导致了传统意义上的程序若参与并发执行,会产生其结果的不可再现性。为使进程在并发运行时虽具有异步性,但仍能保证进程并发执行的结果是可再现的,在OS中引进了进程的概念,并且配置相应的进程同步机制。
2. 线程
p81
(二)进程的状态与转换
p40
(三)线程的实现
p85
1. 内核支持的线程
2. 线程库支持的线程
(四)进程与线程的组织与控制
(五) 进程间通信
1. 共享内存
2. 消息传递
3. 管道
二、CPU 调度与上下文切换
(一)调度的基本概念
(二)调度的目标
(三)调度的实现
1. 调度器/调度程序(scheduler)
2. 调度的时机与调度方式
(抢占式/非抢占式)
3. 闲逛进程
4. 内核级线程与用户级线程调度
(四)典型调度算法
1. 先来先服务调度算法
2. 短作业(短进程、短线程)优先调度算法
3. 时间片轮转调度算法
4. 优先级调度算法
5. 高响应比优先调度算法
6. 多级队列调度算法
7. 多级反馈队列调度算法
(五)上下文及其切换机制
三、同步与互斥
(一)同步与互斥的基本概念
(二)基本的实现方法
1. 软件方法
2. 硬件方法
(三)锁
(四)信号量
(五)条件变量
(六)经典同步问题
1. 生产者-消费者问题
2. 读者-写者问题
3. 哲学家进餐问题
四、死锁
(一)死锁的基本概念
多个进程在执行过程中因竞争系统资源或相互通信而处于永久阻塞状态,若无外力作用,这些进程都将无法向前推进。这些进程中的每一个进程都在无限期地等待此组进程中某个其他进程占有的、自己永远无法得到的资源,这种现象称为死锁。系统资源不足是死锁发生的根本原因,进程推进顺序不当也会导致死锁发生。
根据资源是否可被剥夺,资源可分为两种:
- 不可剥夺资源:打印机等不可强行中断与剥夺使用权的资源,如果强制剥夺会导致双方均无法完成任务。
- 可剥夺资源:如主存和CPU等资源。
1. 死锁产生的必要条件
要产生死锁,下面四个条件缺一不可。
- 互斥条件:一段时间内某种资源仅被一个进程所占有。
- 不剥夺条件:进程所获得的资源在未使用完毕之前,不可被其他进程强行夺走,只能等待自己使用完成后释放。
- 请求与保持条件:进程每次申请它所需的一部分资源。在等待分配新资源的同时,进程继续占有已分配到的资源。请求与保持条件也称为部分分配条件。
- 环路等待条件:存在一种进程资源的循环等待链,而链中的每一个进程已经获得的资源同时被链中的下一个进程所请求。
(二)死锁预防
想要防止死锁的产生,只需要破坏上面的四个死锁产生的必要条件即可。
1. 互斥条件
由于资源的互斥性来自资源本身固有属性的限制,因此破坏互斥条件来防止死锁几乎是不可能的。
2. 不剥夺条件
为了破坏不剥夺条件,可以制定这样的策略:对于一个已经获得了某些资源的进程,若新的资源请求不能立即得到满足,则它必须释放所有已获得的资源,以后需要资源时再重新申请。
该策略实现起来比较复杂,并且释放已获得的资源可能导致前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统吞吐量。该方法通常不会用于剥夺资源造成的代价较大的场合。
3. 请求与保持条件
为了破坏请求与保持条件,可以采用预先静态分配方法。预先静态分配法要求进程在其运行之前一次性申请所需要的全部资源,在他的资源未满足之前,不投入运行。一旦投入运行,这些资源就一直归他所有,也不再提出其他资源请求,这样就可以保证系统不会发生死锁。
这种方法既简单又安全,但是降低了资源利用率,因为这种方法必须知道进程所需要的全部资源,一旦分配即使某资源未立即被使用,一直到运行末期才会被使用,也会导致该资源被占用,因此造成了系统资源不能被充分使用。
4. 环路等待条件
为了破坏环路等待条件,可以采用有序资源分配法。该方法将系统中的所有资源按类型编号,要求每个进程申请资源的时候必须按照编号递增的顺序来请求资源,同类请求一次性申请完。
这种方法的缺点在于,对各种资源编号后不易修改,因此限制了新设备的增加;不同作业对资源的使用的顺序也不会完全相同,从而造成资源浪费;进程对资源按序申请也会增加程序编写的复杂性。