操作系统原理与Linux实例设计--第二章

第二章进程的并发控制2.1程序、进程与并发2.1.1并发概述并发和并行是不同的概念。并行是指在微观上看都可以看作是同时发生的两件或多件事。而并发是指在宏观上可近似看作同时发生的两件或多件事。并行可看作是一种特殊的并发。严格意义上的并行处理只有在多处理器的情况下才有可能发生。而并发是现代处理系统中常有的事。2.1.2程序的顺序执行和并发执行（介绍程序执行的过程）顺序执行：一个程序执行完以后才去执行下一个。优点：便于控制。缺点：浪费资源，不分轻重缓急。并发执行：两个或多个程序交替执行。优点：资源利用率高，更合理。缺点：控制复杂，可能产生死锁。２．１．３进程及其运行环境进程的定义：可并发执行的程序，在一个数据集合上运行的过程。进程与程序的关系：一个程序可以对应一个或多个进程；一个进程可以对应一个程序，或者对应程序的某一部分。（正解？）认为：进程首先是可执行的程序；进程是针对操作系统而言的；在编制进程程序时应合乎进程运行的规则。•进程运行的几个基本特征：动态性；并发性；独立性；异步性；进程的运行是并发的，也会带来一些问题：（１）增加了空间开销（２）额外的时间开销（３）难于控制（４）处理器竞争尤为突出２．２进程的状态转换进程是一个过程，从产生到灭亡，有若干个状态。２．２．１五状态进程模型执行状态阻塞状态就绪状态新建状态终止状态五状态间的相互转换：图２－５五状态进程模型新建终止就绪阻塞执行接纳事件发生事件等待完成时间片完分派／调度２．２．２进程的挂起状态对换技术的引入：进程较多，但都在等待同一Ｉ／Ｏ操作，将一些进程调到外存，而调入新进程。被调出的进程称为挂起进程。可能出现挂起的情形：进程全部阻塞；系统负荷过重；操作系统的需要；终端用户的请求；父进程的需求；挂起进程的特征：不能立即执行；不同于阻塞进程；能实施挂起的进程包括自身、父进程或操作系统；只有实施挂起操作的进程才能激活被挂起进程。２．２．３Linux的进程及其状态转换Linux进程分为三类：交互进程；批处理进程；守护进程。PCB：即数据结构task_struct,包含以下信息：进程状态；调度信息；标识符；进程通信相关信息；链接信息；时间信息；文件系统信息；虚拟内存信息；处理器信息。2.3操作系统对进程的控制2.3.1操作系统内核核心操作。包括资源管理和支撑功能。资源管理：进程管理；存储管理；Ｉ／Ｏ设备管理；支撑功能：中断处理；原语操作（由若干机器指令构成，能完成一定的较复杂的功能）；时钟管理；２．３．２进程的构成及组织进程由三部分构成：程序；数据集合；进程控制块；2.3.3进程控制块PCB1.进程标识符信息外部标识符；内部标识符。2.处理器状态信息：这些信息放在各个寄存器中，包括：通用寄存器；指令寄存器；程序状态字PSW；用户堆栈指针；3.进程调度信息进程状态；进程优先级；进程调度有关的其它信息（与算法有关）；事件。4.其它信息程序和数据的地址；进程同步和通信机制；资源清单；链接指针。2.3.4操作系统对进程的控制包括：1.进程的创建与撤销创建的过程：分配标识符；分配空间；初始化PCB；建立链接；建立或扩展其它数据结构。终止进程的步骤有：找到PCB，读状态；若为执行态，终止之，调度下一就绪进程执行；若有子孙进程，终止他们；归还该进程的全部资源到系统或父进程；将其PCB从所在队列移出。2.进程的阻塞与唤醒阻塞的原因：请求系统服务；启动某种操作；新数据尚未到达；无事可做，需等待。可自己阻塞自己，需要由操作系统或阻塞它的进程唤醒。3.进程的挂起与激活调用原语执行。4.进程切换分时系统中，分配时间片用完，转而执行另外的进程。2.3.5Ｌｉｎｕｘ对进程的控制创建；撤销。２．３．６Linux的内核机制机制的引入；机制的数据结构；任务队列：定时器队列；即时队列；进程调度队列。2.4线程—另一种并发实体２．４．１进程与线程进程包括申请资源，具体执行程序等（即调度）。将传统意义的进程分为两部分，新的进程作为资源申请与拥有的基本单位，线程作为调度的基本单位。要有专门的语言支持多进程、多线程。线程与进程的异同：调度；并发性；拥有资源；系统开销。２．４．２多线程并发线程从属于进程，一般拥有进程的状态，但一般不具有挂起状态。对线程的操作：派生；阻塞；解除阻塞；结束。2.4.3线程的类型1.用户级线程即由用户依据一定的平台而编制的线程。2.内核级线程用户无法直接对线程进行操作。2.4.4Linux的进程与线程管理该系统支持许多标准的内核级线程。2.5进程调度即采取什么原则让某一进程执行，即算法。２．５．１调度的目标、原则和方式目标：要公平合理；处理器利用率要高；系统吞吐量要大；尽量减少进程的响应时间。原则：（1）面向用户的原则响应时间；周转时间；截至时间。（2）面向系统的原则系统吞吐量；处理器利用率；各类资源的平衡使用；公平性；优先权。方式：非剥夺方式；剥夺方式。2.5.2调度的类型１．长程调度考虑的问题：选择多少作业进入内存；选择哪些进程。２．短程调度决定就绪队列里哪个进程获得处理器的使用权。３．中程调度它是对换功能的一部分。２．５．３进程调度算法1.先来先服务（FCFS）2.短进程优先（SPN）3.时间片轮转调度法（RR）4.基于优先级的调度算法5.剩余时间最短者优先（SRT）6.响应比高者优先（HRRN）(w/s+1)(w—等待，s—预期执行）7.反馈调度法（FB）（根据调度的情况动态改变进程的优先级别）•2.5.4实时系统与实时任务调度1.实时系统与实时任务实时系统：能及时响应外部请求，并作出反应的系统。是一个相对的概念。是否周期执行来划分：周期任务；非周期任务。据截至时间来划分：硬实时任务；软实时任务。•２．实时调度的目标及必要信息就绪时间；开始截至时间和完成截至时间；处理时间；资源需求；优先级；子任务结构。•３．实时调度算法最早截止时间优先调度算法；最低松弛度优先算法；速度单调调度算法。•２．６进程并发控制－－互斥与同步２．６．１并发控制包含的内容：１．竞争资源必须“互斥”，即不能同时使用，如打印机。这类资源又称为临界资源，访问临界资源的程序段称为临界区。临界区的使用原则：每次一个；短时停留；快速响应；不能限制进程的执行速度及处理器的数量；不能在临界区阻塞等待。２．共享协作多个进程共享某一些资源，包括修改，要使数据保持一致。３．通信协作多个进程之间应互通信息。２．６．２互斥与同步的解决策略１．软件方法Ｄｅｋｋｅｒ互斥算法；Ｐｅｔｅｒｓｏｎ互斥算法。２．硬件算法屏蔽中断；专用机器指令３．信号量方法预设一个或多个中间变量，通过改变这些变量通知其它的进程。４．管程一段程序，多个进程都须使用。包括三个方面：对局部于管程的共享数据结构的说明；对该数据结构进行操作的一组过程；对该数据结构初始化的语句。５．消息传递与信号量的区别：有先后顺序之分，及发送消息的进程和接收消息的进程。２．６．３互斥／同步问题：生产者／消费者问题１．用信号量方法解决该问题２．用消息传递解决该问题２．６．４互斥／同步问题：读者／写者问题多个读者、写者进程应满足以下条件：允许同时读；不能同时写，只能互斥写；若正在写，则不允许读。２．６．５Linux通信实例２．６．５Linux信号量分析2.7进程死锁死锁：多个进程因为竞争资源，或执行顺序不当，或相互通信而永久阻塞，如果没有外力将永远保持这种现象。２．７．１进程死锁的原因必要条件：互斥；占有且等待；非剥夺；循环等待。２．７．２解决死锁的方法预防死锁；避免死锁；检测并解除死锁。２．７．３预防死锁禁止产生死锁的必要条件。２．７．４避免死锁提前预测将来进程执行的情况。1.安全状态与不安全状态多个进程按特定顺序执行，则不会死锁，这种状态称为安全状态。由安全状态转为不安全状态：调用顺序不恰当，则可能出现该情况。2.银行家算法2.7.5检测并解除死锁１．死锁定理什么情况下肯定会出现死锁。２．死锁检测算法３．解除死锁2.8死锁举例：哲学家进餐问题