操作系统原理（进程管理）

一、进程

1、前驱图

有向无环图

结点表示一条语句、一个程序段或进程

有向边表示两结点之间的偏序关系或前驱关系&＃xff08;p1->p2表示p1一定要发生在p2的前边&＃xff0c;换句话说&＃xff0c;只有p1发生了&＃xff0c;p2才能发生。&＃xff09;

特点&＃xff1a;前驱图不存在循环。

2、程序的顺序执行

按先后顺序执行语句操作。

是单道批处理系统的执行方式。

特点&＃xff1a;

顺序性、

封闭性&＃xff08;程序执行时独占全机资源&＃xff0c;各资源状态只有本程序才能改变&＃xff09;、

可在现性&＃xff08;只要程序执行环境和初始条件相同&＃xff0c;无论以何种方式&＃xff08;连续&＃xff0c;走停&＃xff09;运行&＃xff0c;其结果都相同&＃xff09;

3、程序的并发执行

逻辑上相互独立的程序或程序段在执行过程中执行时间在客观上互相重叠。即一个程序还未结束&＃xff0c;另一程序可以开始。

目的&＃xff1a;提高资源利用率

特点&＃xff1a;

间断&＃xff08;异步&＃xff09;性&＃xff1a;一个程序可能走到中途停下来&＃xff0c;失去原有的时序关系&＃xff08;意思就是执行不是连续的&＃xff0c;但会停止一下又继续&＃xff09;

失去封闭性&＃xff1a;共享资源&＃xff0c;即一个程序写到存储器内的数据可能会被另一个程序修改&＃xff0c;失去原有的不变特征。、

失去可再现性&＃xff1a;外界环境在程序的两次执行期间发生变化&＃xff0c;失去原有的可重复特征。&＃xff08;例&＃xff1a;两个程序都有输出&＃xff0c;两次执行可能执行顺序不同导致输出结果不同&＃xff09;

问题&＃xff1a;资源共享

{cpu如何调度可使得每个用户公平得到cpu、资源使用的冲突与竞争、并行程序间如何正确传递信息&＃xff08;&＃xff1f;&＃xff09;&＃xff08;个人理解&＃xff1a;我如何确定你传给我的信息是没有失真的&＃xff1f;&＃xff09;}

4、进程

描述程序执行的动态特征。

目的&＃xff1a;解决程序并发执行时的系统资源共享的问题。

定义&＃xff1a;

1&＃xff09;进程是程序的一次执行过程

2&＃xff09;进程是一个程序及其数据在处理机上顺序执行所发生的活动

3&＃xff09;进程是程序在一个数据集合上运行的过程&＃xff0c;是系统进行资源分配和调度的一个独立单位。

补充&＃xff1a;进程包括程序段、数据段、和一个称为进程控制块&＃xff08;PCB&＃xff09;的数据结构。

进程控制块

{

进程标识符、进程状态、程序计数器、cpu寄存器、cpu调度信息、内存管理信息、记账信息、I/O状态信息。

}

进程控制块是由OS维护的用来记录进程相关信息的一块内存。

是OS感知进程存在的唯一依据。

是操作系统中最重要的记录型数据结构。

#创建进程时应先创建相应的PCB&＃xff0c;然后操作系统才能根据PCB中的信息对进程进行管理和控制&＃xff0c;当进程完成时&＃xff0c;系统释放PCB&＃xff0c;释放后进程随之消亡。

#进程控制块处在核心段&＃xff0c;通常不能通过程序自身的代码直接访问&＃xff0c;而要通过系统调用&＃xff0c;或OS来访问。

特征&＃xff1a;

动态性&＃xff1a;具有动态的地址空间

并发性&＃xff1a;多个进程实体&＃xff0c;同存于内存中&＃xff0c;能同一时间段内同时运行。

独立性&＃xff1a;各进程的地址空间相互独立&＃xff0c;除非采用进程间通信手段。即系统中独立获得资源&＃xff0c;独立调度的基本单位。

异步性&＃xff1a;进程按各自独立&＃xff0c;不可预知的速度进行。

进程与程序的区别&＃xff1a;

1&＃xff09;主动&＃xff0c;动态与被动&＃xff0c;静态之分

2&＃xff09;暂时和永久之分

3&＃xff09;组成不同

4&＃xff09;进程与程序的对应关系&＃xff1a;通过多次执行&＃xff0c;一个程序可对应多个进程。通过调用关系&＃xff0c;一个进程可包含多个程序。

//进程并非一直处于执行状态&＃xff0c;由“执行-暂停-执行”的活动规律。

//进程的生命周期可以划分为一组状态。

******

有一个小的分派程序&＃xff1a;能使处理器从一个进程切换到另一个进程

处理机分派器是操作系统中的一段代码

功能&＃xff1a;

把处理机从一个进程切换到另一个进程。

防止某进程独占处理机。

*******

五个基本的进程状态&＃xff1a;

新建状态&＃xff1a;刚被建立

终止状态&＃xff1a;进程执行刚结束&＃xff0c;还未撤销

就绪态&＃xff1a;进程已获得除cpu以外的其他资源。

执行态&＃xff1a;获得了cpu

阻塞态&＃xff1a;进程因等待某事件而暂时不能运行的状态

#就绪态不能转换到阻塞态&＃xff08;应执行态&＃xff09;&＃xff0c;阻塞态不能转换到执行态&＃xff08;应就绪态&＃xff09;。

补充&＃xff1a;进程由内存调到外存——进入挂起状态

PCB的组织方式&＃xff1a;

链表加索引

各不同状态的PCB(进程)以链表的形式存储和调用。用与状态相对应的指针对各状态链表遍历。

各不同状态的PCB(进程)以索引表的形式存储和调用。用与状态相对应的index对各状态链表遍历。

二、进程控制

系统使用一些具有特有功能的程序段控制进程。

目的&＃xff1a;达到多进程高效并发执行协调&＃xff0c;实现资源共享。

是由OS内核通过原语操作实现的

原语&＃xff1a;由若干指令构成的“原子操作”过程。作为一个整体不可分割&＃xff08;要么全部完成&＃xff0c;要么全部不做&＃xff09;

即&＃xff1a;原语是系统态下执行的某些具有特定功能的程序段。

许多系统调用的就是原语。

进程控制的原语&＃xff1a;{创建原语、撤销原语、阻塞原语、唤醒原语……}

父进程与子进程

关系构成&＃xff1a;树

继承&＃xff1a;子进程可以从父进程中继承用户标识符、环境变量、打开文件、文件系统的当前目录、控制终端、已经连接的共享存储区、信息处理例程入口表等。

撤销&＃xff1a;子进程撤销时&＃xff0c;归还从父进程继承的资源&＃xff1b;父进程撤销时&＃xff0c;同时撤销其所有子进程。

引起创建进程的事件&＃xff1a;

1. 交互登录&＃xff1a;终端用户登录到系统&＃xff08;进程代表终端用户&＃xff09;
2. 作业调度&＃xff1a;作业被调度程序选中成为执行态&＃xff08;进程担负作业执行的任务&＃xff09;
3. OS因为提供一项服务而创建&＃xff1a;OS为用户程序创建一个新进程&＃xff0c;代表用户程序执行一个功能。
4. 由现有进程生成&＃xff1a;为了程序的并行性创建新进程。

前三个是系统内核创建。

进程的创建实质上是生成一个PCB

【申请空白PCB】->【为新进程分配资源】->【初始化进程控制块】->【将新进程插入就绪队列】

终止程序&＃xff1a;

也称为“退出”或主程序返回&＃xff1a;调用exit&＃xff08;&＃xff09;可终止程序

引起进程终止的事件&＃xff1a;

• 正常结束
• 异常结束
• 外界干预

释放资源&＃xff1a;【释放内外存空间】、【关闭所有打开文件】、【释放共享内存段】

进程的阻塞和唤醒&＃xff1a;

引起进程阻塞和唤醒的事件&＃xff1a;

• 请求系统服务
• 启动某种操作
• 新数据尚未到达
• 无新工作可做

#发生条件尚不具备时&＃xff0c;进程自己调用阻塞原语阻塞自己

#一个处于阻塞状态的进程不可能自己唤醒自己

#当等待队列中的进程所等待的事件发生时&＃xff0c;等待该事件的所有进程都将被唤醒。

//阻塞是进程自身的一种主动行为。

//唤醒&＃xff1a;将进程状态转换成就绪态

进程的挂起与激活&＃xff1a;

用户请求或父进程请求将自己的某个子进程挂起时&＃xff0c;系统调用suspend&＃xff08;&＃xff09;将指定进程或阻塞状态的进程挂起。

#当发生激活进程的事件时&＃xff0c;若进程驻留在外存而内存中已有足够的空间&＃xff0c;则调用active&＃xff08;&＃xff09;激活。

********************************************************************************

进程间存在两种关系&＃xff1a;

相互合作&＃xff08;操作顺序冲突&＃xff09;&＃xff08;个人理解&＃xff1a;职能相干&＃xff09;

竞争资源&＃xff1a;&＃xff08;共享外设、内存&＃xff08;变量&＃xff09;等资源&＃xff09;

协调好这些关系的过程——进程的同步

进程同步的主要工作&＃xff1a;

• 相互合作方面&＃xff08;间接相互制约&＃xff09;&＃xff1a;保证相互合作的诸进程在执行次序上的协调——同步
• 竞争资源方面&＃xff08;直接相互制约&＃xff09;&＃xff1a;保证诸进程能互斥地访问临界资源

临界资源&＃xff1a;计算机中的有些软硬件资源&＃xff0c;当多个进程对其进行访问时&＃xff08;关键是进行写入和修改&＃xff09;&＃xff0c;必须互斥地进行&＃xff0c;这些一次只允许一个进程使用的资源称为临界资源。

临界资源需要采用互斥方式&＃xff0c;实现对资源的共享。

--------------------------------------------------------------------------------------------------

一个访问临界资源的程序包含【进入区、临界区、退出区、剩余区】

进入区&＃xff1a;进入临界区之前&＃xff0c;检查可否进入临界区的一段代码。&＃xff08;如果可以进入&＃xff0c;则通常会设置“正在访问临界区”的标志&＃xff09;

临界区&＃xff1a;每个进程中访问临界资源的那段程序称为临界区。

退出区&＃xff1a;用于将“正在访问临界区”标志清除。

剩余区&＃xff1a;代码中的其他部分。

进入区作用&＃xff1a;{改变资源状态&＃xff0c;阻塞等待资源释放}

退出区作用&＃xff1a;{释放资源}

*******************************************************************************************

进程互斥&＃xff1a;若干共享临界资源的进程彼此交换信息以保证排他性的进入各自的临界区。

进程同步&＃xff1a;若干相互合作的进程彼此交换信息以保证在执行次序上的协调。

----------------------------------------------------------------------------------------------------------

同步和互斥的关系&＃xff1a;

1)进程同步是一般情况&＃xff0c;互斥是同步的一种特殊情况。

2)进程互斥可在具有一定逻辑关系的伙伴进程之间&＃xff0c;也可在非伙伴进程之间。而同步发生在相互有逻辑关系的伙伴进程之间。

同步机制应遵循的准则&＃xff1a;

• 空闲则入&＃xff1a;其他进程均不处于临界区
• 忙则等待&＃xff1a;已有进程处于其临界区
• 有限等待&＃xff1a;等待进入临界区的进程不能死等
• 让权等待&＃xff1a;不能进入临界区的进程&＃xff0c;应当释放CPU&＃xff08;如转换到阻塞状态&＃xff09;

解决互斥的方法有软件方法也有硬件方法。

两种方法原理上类似&＃xff1a;都是设置公共变量用来判断可否进入临界区和是否已经进入临界区&＃xff0c;再当进程使用临界资源结束后&＃xff0c;会通过修改那个公共变量来使临界资源被释放。

不同的是&＃xff1a;软件方法是用户自己设计的&＃xff0c;而硬件方法则是操作系统中自带的&＃xff08;个人理解&＃xff1a;是操作系统设计者设计的&＃xff09;

“饥饿”现象&＃xff1a;在一个可以预见的时间内&＃xff0c;一个或多个进程得不到满足&＃xff0c;如都不能访问临界资源。

产生原因&＃xff1a;动态系统中&＃xff0c;操作系统对每类系统资源需要确定分配策略&＃xff0c;有时分配策略是不公平的&＃xff0c;即不能保证等待时间上界的存在。当进程等待时间给进程推进和响应带明显影响时称发生了饥饿现象。

正确的算法是:先修改、后检查、后修改者等待

进入区&＃xff1a;flag[i] &＃61; true;turn&＃61;j;while(flag[j] and turn &＃61;&＃61; j)do no_op;

退出区&＃xff1a;flag[i] &＃61; flase;

软件方法具有局限性&＃xff1a;

{

不适用多进程

实现过于复杂

需要高编程技巧

}

可利用硬件指令&＃xff1a;读写操作由一条指令完成&＃xff0c;因而保证读操作和写操作不被打断。

硬件方法&＃xff1a;中断屏蔽方法、硬件指令方法。

硬件方法局限&＃xff1a;等待要耗费cpu时间&＃xff0c;不能实现“让权等待”。

优点&＃xff1a;适用任意数目的进程、简单、容易证明正确性、可以支持进程内存在多个临界区&＃xff0c;只需要为每个临界区设立一个布尔变量。

问题&＃xff1a;为啥硬件比软件好&＃xff0c;不应该一样吗&＃xff0c;都是同样的原理&＃xff1f;为啥软件方法的局限那么大&＃xff1f;