一. 操作系统引论
操作系统是一组能有效阻止和管理计算机硬件和软件资源,合理地把对各类作用进行调度,以及方便用户使用的程序的集合。
1. 操作系统的目标与作用
- 在计算机系统上配置操作系统,其主要目标就是:方便性、有效性、可扩充性和开放性。
- 方便性:一个未配置的计算机系统是极难使用的。配置了操作系统之后,系统便可使用编译命令将用户采用高级语言编写的程序翻译成机器代码,或直接通过OS所提供的各种命令操纵计算机,极大地方便了用户。
- 有效性:提高系统资源利用率以及洗脱嫩肉吞吐量。
- 可扩充性:能方便的添加新的功能和模块,以及对原有的功能进行添加和修改。
- 开放性:指系统能遵循世界标准规范。
- 操作系统的作用
- 作为用户与计算机硬件操作系统之间的接口。用户可以通过OS来使用计算机硬件。
- 作为计算机系统资源的管理者。这些资源主要分为:处理机、存储器、I/O设备以及文件(数据和程序)。
- 实现了对计算机资源的抽象。
2. 操作系统的发展过程
- 人工操作方式:人工的输入输出,用户独占全机。
- 脱机输入/输出方式:引入了高速的磁带。减少了CPU的空闲时间,提高了I/O速度。
- 单道批处理系统:实现对作业的连续处理,系统中的资源得不到充分利用。
- 多道批处理系统:多道作业存放于外存的后备队列,有作业调度选择若干个作业调入内存,资源利用率高,系统吞吐量大,但是平均周转时间长,无交互能力。
- 分时系统:满足用户对人-机交互的需求。是指在一台主机连接了多个配有显示器和键盘的终端并由此所组成的系统,该系统允许多个用户同时通过自己的终端,以交互的方式使用计算机,共享主机中的资源。
- 实时系统:是指系统能及时响应外部事件的请求,在规定时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。
3. 操作系统的基本特性
上面介绍的多道批处理系统、分时系统和实时系统各自有各自的特点,但同时,他们还共同具有并发、共享、虚拟和异步四个基本特征。
- 并发:系统中的程序能够并发的执行,使得OS能有效地提高系统的资源利用率,增加系统的吞吐量。
- 并发性:是指两个或多个事件在同一时间间隔内发生。
- 并行性:指两个或多个事件在同一时刻发生。倘若在计算系统中有多个处理机,这些可以并发执行的程序便可分配到多个处理机上实现并行执行。
- 在未引入进程时,对于同属于一个应用程序中的两个程序只能顺序执行。引入进程,对内存中的多个程序分别建立一个进程,他们就可以并发的执行,极大地提高了系统资源利用率和系统吞吐量。
- 共享性:是指系统中的资源可供内存中 多个并发执行的进程共同使用。主要实现方式:
- 互斥共享:在一段时间内,只允许一个进程访问该资源,我们成该种资源为临界资源。
- 同时访问
- 并发和共享是多用户OS的两个最基本的特征。
- 虚拟性:采用时分复用技术和空分复用技术实现。
- 时分复用技术是通过利用处理机的空闲时间运行其他程序,提高了处理机的利用率。
- 空分复用技术则是利用存储器的空闲时间分区域存放和运行其他的多道程序,以此来提高内存的利用率。
- 异步性:进程以人们不可预知的速度向前推进,也就是用户不知道进程在何时获得CPU。
4. 操作系统的主要功能
引入OS的目的是为多道程序的运行提供良好的运行环境,以保证多道程序能有条不紊的运行,并能最大程度的提高系统中各种资源的利用率,方便用户的使用。OS具有处理机管理、存储器管理、设备管理、文件管理以及用户接口五大功能。
- 处理机管理的主要功能:进程控制,进程同步,进程通信以及进程调度。
- 存储器管理的主要功能:内存分配,内存保护,地址映射,内存扩充。
- 设备管理的主要功能:缓冲管理,设备分配,设备处理。
- 文件管理的主要功能:文件存储空间的管理,目录管理,文件的读写管理和保护。
- 接口的主要功能:提供用户接口和程序接口。
二. 进程的描述与控制
1. 进程与线程
为了能使程序并发的执行,并且可以对并发执行的程序加以控制,引入进程。为了使参与并发执行的每个程序都能独立运行,为每个进程配置一个进程控制块PCB,用PCB来描述进程的基本情况和活动过程,进而控制和管理进程。这样由程序段、相关的数据段和PCB三部分构成了进程实体。
- 进程的定义
- 进程是程序的一次执行。
- 进程是一个程序及其数据在处理上顺序执行时所发生的的活动。
- 进程是具有独立功能的程序在一个数据集合上运行的过程它是系统进行资源分配的独立单位。
引入线程的目的是减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。
- 进程创建,系统为它分配其所必需的、除处理机以外的所有资源,以及创建相应的PCB。
- 进程撤销,必须对其所占有的资源执行回收操作,然后撤销PCB。
- 进程切换,对进城进行上文切换时,需要保留当前进程的CPU,设置新选进程的CPU环境,因此需要花费不少的处理机时间。
进程是一个资源的拥有者,如果频繁的进行创建撤销切换会造成很大的时空开销。所以,引入线程,将线程作为调度和分派的基本单位,进程作为资源分配的独立单位。
2. 程序、进程、线程的比较
首先程序与进程的区别:
- 进程具有程序所没有的PCB,进程是程序的一次执行。
- 动态性:
- 进程的实质是进程实体的执行过程,动态性表现在:进程由创建而产生,由调度而执行,由撤销而消亡。可见进程具有一定的生命周期。
- 程序是一组有序指令的集合,并存放于某种介质智商,其本身并不具有活动的意义,是静态的。
- 并发性:
- 多个进程同存在于内存中,且能在一段时间内同时运行。
- 程序没有建立PCB不能参与并发执行。
- 独立性:
- 进程实体是一个能独立运行、独立获得资源的基本单位。
- 凡未建立PCB的程序都不能作为一个独立运行的单位参与运行。
- 异步性:
- 进程是按异步的方式运行的,即按各自独立的、不可预知的速度向前推进。
- 程序若参与并发执行,会产生其结果的不可再现性。
其次是进程与线程的区别:
- 调度的基本单位:
- 进程是资源分配的基本单位。
- 线程是调度和分派的基本单位。线程切换仅需要保存和设置少量的寄存器。在同一进程中线程的切换不会引起进程的切换,不同进程中线程的切换则会引起进程的切换。
- 并发性:
- 不仅进程与进程之间可以并发执行,而且在一个进程中的多个线程之间也可以并发执行。
- 拥有资源:
- 进程是系统中拥有资源的基本单位。
- 线程并不拥有系统资源,而是仅有一点必不可少的、能保证独立运行的资源,比如TCB、用于PC、保留局部变量、少数状态参数和返回地址等的一组寄存器和栈。
- 独立性:
- 每个进程都拥有独立的地址空间和其他资源。除了共享全局变量以外,不允许其他进程访问。
- 线程除了拥有少量资源外,还可以属于同一个进程的所有线程都具有相同的地址空间。并且可以访问所属进程的所有资源。
- 系统开销:
- 进程的创建、撤销所付出的开销远比线程大。
- 同一进程里的线程具有相同的地址空间,线程的切换比进程的切换代价小。
- 支持多处理机系统:
- 在多处理机系统上,对于传统的进程,不管有多少处理机,该进程只能运行在一个处理机上。
- 但对于多线程进程,就可以将一个进程中的线程分配到多个处理机上,使他们并行执行,可以加速进程的完成。
3. 进程的状态
1) 进程的三种基本状态:
- 就绪状态:进程已经分到除CPU以外的所有必要的资源,只要在获得CPU,便可立即执行。
- 执行状态:指进程已经获得CPU,其程序正在执行。
- 阻塞状态:指正在执行的进程由于发生某件事(如I/O请求、申请缓冲区失败等)暂时无法继续执行时的状态。
进程的三种基本状态及其转换如下图:
2) 为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性,引入了创建状态和终止状态。
- 创建状态:保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。获得所需要的资源以及对PCB的初始化工作完成之后,便可由创建状态进入就绪状态。
- 终止状态:等待操作系统进行善后处理,最后将PCB清零,并将PCB空间返还系统。
进程的五种基本状态以及转换如下图:
3) 挂起状态的引入:增加内存容量,实现虚拟内存。挂起是将进程调至内存外,从而保证内存充足。
引入挂起状态之后的状态装换图如下:
4. 进程同步
进程同步机制的主要任务,是对多个相关进程在执行次序上进行协调,使并发执行的诸进程之间能按照一定的规则共享系统资源,并能很好地相互合作,从而是程序的执行具有可再现性。
1) 两种形式的制约关系
- 间接相互制约关系:多个程序在并发执行时,由于共享系统资源,只是这些并发执行的程序之间形成相互制约的关系,多个进程互斥的访问这些资源。
- 直接相互制约关系:多个进程一同合作为了完成某个任务,这些进程在完成任务上有一定的时间顺序。有些进程要在其他进程的后才能开始。
2)同步机制应遵循的规则:
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
3) 硬件同步机制
- 关中断
- 利用Test-and-Set指令实现互斥
- 利用Swap指令实现进程互斥
4) 信号量机制
- 整型信号量:执行时不可中断。描述如下:
wait(S){
while(S<=0);
S--;
}
signal(S){
S++;
}
wait(S)和signal(S)是两个原子操作,不符合“让权等待”原则。
- 记录型信号量:采用记录型数据结构。描述如下:
typedef struct{
int value;
struct process_control_block *list;
}semaphore;
wait(semaphore * S){
S->value --;
if(S-value < 0) block(S->list);
}
signal(semaphore * S){
S->value ++;
if(S->value <= 0) wakeup(S->list);
}
- AND型信号量:江金城在整个运行过程中所需要的所有资源,一次性全部地分给进程,带进程使用完后在一起释放。
- 信号量集
5) 信号量的应用
- 利用信号量实现进程互斥,使多个进程能互斥的访问某临界资源。
- 利用信号量实现前驱关系。
5. 进程经典同步问题
- 生产者-消费者问题
- 哲学家进餐问题
- 读者-写者问题
6. 进程通信
进程通信类型:
- 共享存储器系统
- 管道通信系统
- 消息传递系统
- 客户机-服务器系统
三. 处理机调度与死锁
1.处理机调度的层次与调度算法的目标
1) 处理机调度的层次
- 高级调
一. 操作系统引论
操作系统是一组能有效阻止和管理计算机硬件和软件资源,合理地把对各类作用进行调度,以及方便用户使用的程序的集合。
1. 操作系统的目标与作用
- 在计算机系统上配置操作系统,其主要目标就是:方便性、有效性、可扩充性和开放性。
- 方便性:一个未配置的计算机系统是极难使用的。配置了操作系统之后,系统便可使用编译命令将用户采用高级语言编写的程序翻译成机器代码,或直接通过OS所提供的各种命令操纵计算机,极大地方便了用户。
- 有效性:提高系统资源利用率以及洗脱嫩肉吞吐量。
- 可扩充性:能方便的添加新的功能和模块,以及对原有的功能进行添加和修改。
- 开放性:指系统能遵循世界标准规范。
- 操作系统的作用
- 作为用户与计算机硬件操作系统之间的接口。用户可以通过OS来使用计算机硬件。
- 作为计算机系统资源的管理者。这些资源主要分为:处理机、存储器、I/O设备以及文件(数据和程序)。
- 实现了对计算机资源的抽象。
2. 操作系统的发展过程
- 人工操作方式:人工的输入输出,用户独占全机。
- 脱机输入/输出方式:引入了高速的磁带。减少了CPU的空闲时间,提高了I/O速度。
- 单道批处理系统:实现对作业的连续处理,系统中的资源得不到充分利用。
- 多道批处理系统:多道作业存放于外存的后备队列,有作业调度选择若干个作业调入内存,资源利用率高,系统吞吐量大,但是平均周转时间长,无交互能力。
- 分时系统:满足用户对人-机交互的需求。是指在一台主机连接了多个配有显示器和键盘的终端并由此所组成的系统,该系统允许多个用户同时通过自己的终端,以交互的方式使用计算机,共享主机中的资源。
- 实时系统:是指系统能及时响应外部事件的请求,在规定时间内完成对该事件的处理,并控制所有实时任务协调一致地运行。
3. 操作系统的基本特性
上面介绍的多道批处理系统、分时系统和实时系统各自有各自的特点,但同时,他们还共同具有并发、共享、虚拟和异步四个基本特征。
- 并发:系统中的程序能够并发的执行,使得OS能有效地提高系统的资源利用率,增加系统的吞吐量。
- 并发性:是指两个或多个事件在同一时间间隔内发生。
- 并行性:指两个或多个事件在同一时刻发生。倘若在计算系统中有多个处理机,这些可以并发执行的程序便可分配到多个处理机上实现并行执行。
- 在未引入进程时,对于同属于一个应用程序中的两个程序只能顺序执行。引入进程,对内存中的多个程序分别建立一个进程,他们就可以并发的执行,极大地提高了系统资源利用率和系统吞吐量。
- 共享性:是指系统中的资源可供内存中 多个并发执行的进程共同使用。主要实现方式:
- 互斥共享:在一段时间内,只允许一个进程访问该资源,我们成该种资源为临界资源。
- 同时访问
- 并发和共享是多用户OS的两个最基本的特征。
- 虚拟性:采用时分复用技术和空分复用技术实现。
- 时分复用技术是通过利用处理机的空闲时间运行其他程序,提高了处理机的利用率。
- 空分复用技术则是利用存储器的空闲时间分区域存放和运行其他的多道程序,以此来提高内存的利用率。
- 异步性:进程以人们不可预知的速度向前推进,也就是用户不知道进程在何时获得CPU。
4. 操作系统的主要功能
引入OS的目的是为多道程序的运行提供良好的运行环境,以保证多道程序能有条不紊的运行,并能最大程度的提高系统中各种资源的利用率,方便用户的使用。OS具有处理机管理、存储器管理、设备管理、文件管理以及用户接口五大功能。
- 处理机管理的主要功能:进程控制,进程同步,进程通信以及进程调度。
- 存储器管理的主要功能:内存分配,内存保护,地址映射,内存扩充。
- 设备管理的主要功能:缓冲管理,设备分配,设备处理。
- 文件管理的主要功能:文件存储空间的管理,目录管理,文件的读写管理和保护。
- 接口的主要功能:提供用户接口和程序接口。
二. 进程的描述与控制
1. 进程与线程
为了能使程序并发的执行,并且可以对并发执行的程序加以控制,引入进程。为了使参与并发执行的每个程序都能独立运行,为每个进程配置一个进程控制块PCB,用PCB来描述进程的基本情况和活动过程,进而控制和管理进程。这样由程序段、相关的数据段和PCB三部分构成了进程实体。
- 进程的定义
- 进程是程序的一次执行。
- 进程是一个程序及其数据在处理上顺序执行时所发生的的活动。
- 进程是具有独立功能的程序在一个数据集合上运行的过程它是系统进行资源分配的独立单位。
引入线程的目的是减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。
- 进程创建,系统为它分配其所必需的、除处理机以外的所有资源,以及创建相应的PCB。
- 进程撤销,必须对其所占有的资源执行回收操作,然后撤销PCB。
- 进程切换,对进城进行上文切换时,需要保留当前进程的CPU,设置新选进程的CPU环境,因此需要花费不少的处理机时间。
进程是一个资源的拥有者,如果频繁的进行创建撤销切换会造成很大的时空开销。所以,引入线程,将线程作为调度和分派的基本单位,进程作为资源分配的独立单位。
2. 程序、进程、线程的比较
首先程序与进程的区别:
- 进程具有程序所没有的PCB,进程是程序的一次执行。
- 动态性:
- 进程的实质是进程实体的执行过程,动态性表现在:进程由创建而产生,由调度而执行,由撤销而消亡。可见进程具有一定的生命周期。
- 程序是一组有序指令的集合,并存放于某种介质智商,其本身并不具有活动的意义,是静态的。
- 并发性:
- 多个进程同存在于内存中,且能在一段时间内同时运行。
- 程序没有建立PCB不能参与并发执行。
- 独立性:
- 进程实体是一个能独立运行、独立获得资源的基本单位。
- 凡未建立PCB的程序都不能作为一个独立运行的单位参与运行。
- 异步性:
- 进程是按异步的方式运行的,即按各自独立的、不可预知的速度向前推进。
- 程序若参与并发执行,会产生其结果的不可再现性。
其次是进程与线程的区别:
- 调度的基本单位:
- 进程是资源分配的基本单位。
- 线程是调度和分派的基本单位。线程切换仅需要保存和设置少量的寄存器。在同一进程中线程的切换不会引起进程的切换,不同进程中线程的切换则会引起进程的切换。
- 并发性:
- 不仅进程与进程之间可以并发执行,而且在一个进程中的多个线程之间也可以并发执行。
- 拥有资源:
- 进程是系统中拥有资源的基本单位。
- 线程并不拥有系统资源,而是仅有一点必不可少的、能保证独立运行的资源,比如TCB、用于PC、保留局部变量、少数状态参数和返回地址等的一组寄存器和栈。
- 独立性:
- 每个进程都拥有独立的地址空间和其他资源。除了共享全局变量以外,不允许其他进程访问。
- 线程除了拥有少量资源外,还可以属于同一个进程的所有线程都具有相同的地址空间。并且可以访问所属进程的所有资源。
- 系统开销:
- 进程的创建、撤销所付出的开销远比线程大。
- 同一进程里的线程具有相同的地址空间,线程的切换比进程的切换代价小。
- 支持多处理机系统:
- 在多处理机系统上,对于传统的进程,不管有多少处理机,该进程只能运行在一个处理机上。
- 但对于多线程进程,就可以将一个进程中的线程分配到多个处理机上,使他们并行执行,可以加速进程的完成。
3. 进程的状态
1) 进程的三种基本状态:
- 就绪状态:进程已经分到除CPU以外的所有必要的资源,只要在获得CPU,便可立即执行。
- 执行状态:指进程已经获得CPU,其程序正在执行。
- 阻塞状态:指正在执行的进程由于发生某件事(如I/O请求、申请缓冲区失败等)暂时无法继续执行时的状态。
进程的三种基本状态及其转换如下图:
2) 为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性,引入了创建状态和终止状态。
- 创建状态:保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。获得所需要的资源以及对PCB的初始化工作完成之后,便可由创建状态进入就绪状态。
- 终止状态:等待操作系统进行善后处理,最后将PCB清零,并将PCB空间返还系统。
进程的五种基本状态以及转换如下图:
3) 挂起状态的引入:增加内存容量,实现虚拟内存。挂起是将进程调至内存外,从而保证内存充足。
引入挂起状态之后的状态装换图如下:
4. 进程同步
进程同步机制的主要任务,是对多个相关进程在执行次序上进行协调,使并发执行的诸进程之间能按照一定的规则共享系统资源,并能很好地相互合作,从而是程序的执行具有可再现性。
1) 两种形式的制约关系
- 间接相互制约关系:多个程序在并发执行时,由于共享系统资源,只是这些并发执行的程序之间形成相互制约的关系,多个进程互斥的访问这些资源。
- 直接相互制约关系:多个进程一同合作为了完成某个任务,这些进程在完成任务上有一定的时间顺序。有些进程要在其他进程的后才能开始。
2)同步机制应遵循的规则:
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
3) 硬件同步机制
- 关中断
- 利用Test-and-Set指令实现互斥
- 利用Swap指令实现进程互斥
4) 信号量机制
- 整型信号量:执行时不可中断。描述如下:
wait(S){
while(S<=0);
S--;
}
signal(S){
S++;
}
wait(S)和signal(S)是两个原子操作,不符合“让权等待”原则。
- 记录型信号量:采用记录型数据结构。描述如下:
typedef struct{
int value;
struct process_control_block *list;
}semaphore;
wait(semaphore * S){
S->value --;
if(S-value < 0) block(S->list);
}
signal(semaphore * S){
S->value ++;
if(S->value <= 0) wakeup(S->list);
}
- AND型信号量:江金城在整个运行过程中所需要的所有资源,一次性全部地分给进程,带进程使用完后在一起释放。
- 信号量集
5) 信号量的应用
- 利用信号量实现进程互斥,使多个进程能互斥的访问某临界资源。
- 利用信号量实现前驱关系。
5. 进程经典同步问题
- 生产者-消费者问题
- 哲学家进餐问题
- 读者-写者问题
6. 进程通信
进程通信类型:
- 共享存储器系统
- 管道通信系统
- 消息传递系统
- 客户机-服务器系统
三. 处理机调度与死锁
1.处理机调度的层次与调度算法的目标
1) 处理机调度的层次
- 高级调