操作系统—进程管理

进程与线程

进程的概念：

程序的并发执行会破坏程序的封闭性，并且具有间断性和不可再现性，为了程序的并发执行，并且对运行的程序加以控制和描述，引入了进程的概念； 进程是程序的一次运行过程（动态的），是系统进行资源分配和调度的一个独立单位（程序是指令+数据的集合，静态的）

进程的特征：

• 动态性：进程是一次执行过程，有生命周期，新建，就绪，运行，阻塞，终止（阻塞挂起，就绪挂起）
• 并发性：多个进程可以同时存在内存中，在一段时间内同时运行，引入进程的目的就是为了程序的并发性；
• 独立性：进程是一个独立运行，独立获得资源，独立接收调度的基本单位；
• 异步性：进程由于调度会按照各自独立的，不可预知的速度向前推进，导致了执行结果的不可再现性，为此操作系统必须配置相应的进程同步机制；
• 结构性：每个进程分配一个PCB对其描述和控制，从结构上看，进程有三部分：程序段，数据段，进程控制段（PCB）

进程状态：

进程的状态

PCB（Process Control Block）：

PCB是系统为进程专门分配的数据结构，系统利用PCB对进程的运行进行控制和管理；

PCB存储的信息：

PCB

• 进程标识符PID：标志各个进程，每个进程都有唯一的标识号；
• 进程当前状态：描述当前进程状态信息，作为处理机调度的依据；
• 进程优先级：进程抢占处理机的优先级；
• 资源分配清单：说明内存地址空间或虚拟地址空间的状况，所使用的IO设备信息；
• 处理机相关信息：指处理机中各寄存器的值，当进程被切换时，处理机状态信息都必须保存在PCB中，当线程被重新执行时，执行信息可以从PCB恢复到处理机；

进程通信：

1. 共享存储：在通信的进程之间存在一块可以直接访问的共享空间，通过对这片共享空间读写实现进程通信；
2. 消息传递：进程间通信的数据已Message为单位，利用操作系统提供的消息传递方式实现进程通信
3. 管道通信：通过对共享文件pipe文件的读写，写进程通过字符流将大量数据写入管道，读进程从管道接收数据，管道通信的条件:互斥，同步，确定对方存在

线程的概念：

线程是轻量级的进程，CPU调度的最小单元， 是进程中被调度和分派的基本单位，线程共享进程的全部资源；由线程ID，程序计数器，寄存器集合，堆栈组成；

引入线程的目的为了减小程序在并发执行时所付出的时空开销，提高操作系统并发性能

线程的五个状态

进程与线程的比较

角度	线程	进程
组成	线程id，程序计数器，寄存器集合，堆栈	PCB，程序，数据
资源	线程不拥有资源，只能访问进程的资源	进程是资源的分配单位
上下文切换	在同一进程进行线程切换不需要切换进程	进程切换比线程切换的开销大很多，引入线程为了高效并发
通信	线程可以通过共享进程资源通信	进程通信涉及内核空间和用户空间的拷贝

线程的实现：

• 内核级线程：操作系统内核支持的线程，内核通过Scheduler调度器对线程进行调度，程序一般使用内核线程的高级接口轻量级进程（通常意义上的线程）去使用内核线程；每一个轻量级进程都由一个内核线程支持，一对一线程模型
  特点：因为基于内核实现，所以涉及到系统调用，即用户态和内核态的切换，代价较高；

• 用户级线程：完全建立在用户空间的线程，内核不能感知用户级线程的存在，用户线程的调度完全在用户态实现；每一个进程对应多个用户级线程，一对多线程模型
  特点：操作系统只负责把资源分配给进程，进程内部的线程操作，创建，调度，切换都需要自己完成，这是一件很困难的事情，所以用户线程实现的程序比较复杂，java 1.2之前使用的是用户级线程

JAVA线程的实现：

在jdk1.2之前，使用绿色线程的用户级线程，而到了jdk1.2中，使用了基于操作系统原生线程模型来实现，操作系统支持怎样的线程模型，很大程度上决定了jvm上线程是怎样映射；

JAVA线程的调度：

• 协同式线程调度：线程执行的时间由自己控制，当线程把工作做完以后，通知系统切换到另一个线程，实现简单，没有同步问题，如果一个线程出问题，整个进程就会阻塞；

• 抢占式线程调度：线程的切换由系统控制，由系统为每个线程分配执行时间，我们可以通过优先级来建议系统为某些线程多分配时间，在java中，优先级可能会出问题，因为java线程的实现是基于操作系统原生线程实现的，java线程的优先级有十种，如果操作系统的优先级种类少于十种，那么某些优先级可能会相同；

JAVA线程的状态：

java线程的五种状态 （深入理解JVM）
Running：包括了操作系统线程的就绪和运行状态

处理机调度

处理机调度：

系统按照某种算法将处理机分配给就绪队列的一个进程，使之执行

调度的种类：

1.高级调度作业调度：

根据一定原则将处于外存后备队列的作业调入内存，为他创建进程，分配资源，使他们获得竞争处理机的权利，然后将进程排入就绪队列准备执行；

2.中级调度内存调度：

将不能运行的进程调入外存中，此时的进程状态是挂起状态，当他们再次具备运行条件时再调入内存的就绪队列，状态为就绪态；作用是提高内存利用率和系统吞吐量

3.低级调度进程调度：

用来决定就绪队列中哪个进程获得处理机；进程调度时，首先会保存处理机的数据到PCB，然后根据某个调度算法在就绪队列中选出一个进程，将此进程的PCB数据恢复到处理机，处理机执行此程序；

处理机的三种调度

低级调度的种类：

• 非抢占式：一旦将处理机分配给某个进程，只有进程执行结束或者发生某个事件被阻塞，处理机才会分配给其他进程
• 抢占式：允许调度程序根据某个原则将已经分配处理机的进程暂停，把处理机分配给其他进程；优先权原则，短作业优先原则，时间片原则

调度算法：

算法	思路	作用对象	特点
先来先服务调度算法	从后备队列/就绪队列中选择最先进入队列的作业/进程，	高级调度，低级调度	简单，效率低；属于非抢占式；对短作业不利
短作业优先调度算法	从后备队列/就绪队列选择一个运行时间最短的作业/进程	高级调度，低级调度	对长作业不利，可能会导致长作业进程的饥饿现象；没有考虑到作业的紧迫程度；由于作业时间的长短是由用户提供的估计执行时间，可能不准确导致该算法无法真正做到短作业优先；平均等待时间和平均周转时间最短；
优先级调度算法	从后备队列/就绪队列选择一个优先级最高的作业/进程	高级调度，低级调度	优先级参照准则：系统进程>用户进程；交互型进程>非交互型进程；IO型进程>计算型进程
高响应比优先调度算法	选出后备队列中响应比最高的作业，响应比：1+等待时间/要求服务时间	高级调度	综合了先来先服务调度算法和短作业优先调度算法；等待时间相同，要求服务时间越短，相应比越高，有利于短作业；要求服务时间相同，等待时间越长，相应比越大，先来先服务思想；作业的相应比可以随着等待时间的增加而提高，克服了长作业的饥饿问题；
时间片轮转调度算法	按照先来先服务思想，选择就绪队列中的第一个进程，但只能运行一个时间片，在时间片用完后，当前进程必须释放处理机给下一个进程，被剥夺的进程返回就绪队列等待；	低级调度	时间片的大小对系统性能的影响很大；时间片大小的影响因素：系统的相应时间，就绪队列中的进程数，系统的处理能力；
多级反馈队列调度算法	设置多个有优先级的就绪队列，第一就绪队列的优先级大于第二就绪队列；各个队列中进程执行时时间片不同，优先级高的队列中的进程分得的时间片少；新进程进入内存后，先将其放入第一就绪队列按照FCFS原则服务，如果时间片用完还未结束则进入第二队列同样按照FCFS原则，如此下去； 只有当第一就绪队列为空时，才会调度第二就绪队列中的进程。如果处理机正在执行第i队列中的进程，此时有一个进程进入优先级较高的队列，则新进程抢占处理机；	低级调度	综合了时间片轮转调度算法和优先级调度算法，可以动态的调整进程优先级和时间片大小，兼顾多方面系统目标

调度算法的评价准则：

• 系统吞吐量：单位时间类CPU完成的作用数量
• 周转时间：作业提交到作业完成的时间，包括作业等待，就绪队列排队，处理机运行；
• 等待时间：进程处于等待处理机状态的时间总和，处理机调度算法只影响作业在就绪队列中等待的时间；
• 响应时间：用户提交到系统首次响应的时间

进程同步

信号量机制：

信号量机制可以用来解决同步与互斥问题，它的实现由两个标准原语实现，P操作，V操作

• S信号量的意义：当S>0时表示可以使用的资源数，当S<0 时其绝对值表示正在等待资源的进程数

• P操作：表示申请资源，S = S - 1，当S>=0时，当前进程继续执行；否则阻塞(小于0表示资源少)

• V操作：表示释放资源，S = S + 1，当S<=0,则唤醒一个进程，使其进入就绪队列，自己继续执行，否则直接继续执行，不影响其他进程；

死锁

死锁的概念：两个进程相互竞争对方的资源，又不释放自己的资源，若无外力作用，他们都无法向前推进

死锁的必要条件：

• 互斥：至少有一种非共享资源
• 占有等待：一个进程必须占有一种资源，并且等待一个被其他进程占有的资源
• 非抢占：进程占有的资源不能被抢占，只能主动释放
• 循环等待：形成一个进程———资源的环形链

死锁产生的原因：

• 竞争资源： 进程数>资源数
• 进程推进顺序非法：请求资源&释放资源的顺序不合理

预防死锁：

思路：破坏死锁的四个必要条件之一

• 资源一次性分配：一次性分配所有的资源，破坏占有等待
• 可剥夺资源：允许进程剥夺使用其他进程占有的资源，破坏非抢占
• 资源有序分配：系统给每个资源设置一个编号，每个进程按编号递增的顺序请求资源，编号递减的顺序释放资源，破坏循环等待

避免死锁：

银行家算法：当进程首次申请资源时，测试该进程对资源的最大需求量，若系统现有的资源满足它的最大需求量，按当前的申请资源分配，否则，推迟分配；

解除死锁：

• 剥夺资源：当系统检测到发生死锁时，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
• 撤销进程：将一个或多个思索进程终止（撤销），直至打破循环环路，使系统从死锁状态解脱。