进程与线程
进程的概念：
程序的并发执行会破坏程序的封闭性，并且具有间断性和不可再现性，为了程序的并发执行，并且对运行的程序加以控制和描述，引入了进程的概念； 进程是程序的一次运行过程（动态的），是系统进行资源分配和调度的一个独立单位（程序是指令+数据的集合，静态的）
进程的特征：
-
动态性：进程是一次执行过程，有生命周期，新建，就绪，运行，阻塞，终止（阻塞挂起，就绪挂起） -
并发性：多个进程可以同时存在内存中，在一段时间内同时运行，引入进程的目的就是为了程序的并发性； -
独立性：进程是一个独立运行，独立获得资源，独立接收调度的基本单位； -
异步性：进程由于调度会按照各自独立的，不可预知的速度向前推进，导致了执行结果的不可再现性，为此操作系统必须配置相应的进程同步机制； -
结构性：每个进程分配一个PCB对其描述和控制，从结构上看，进程有三部分：程序段，数据段，进程控制段（PCB）
进程状态：
PCB（Process Control Block）：
PCB是系统为进程专门分配的数据结构，系统利用PCB对进程的运行进行控制和管理；
PCB存储的信息：
-
进程标识符PID：标志各个进程，每个进程都有唯一的标识号； -
进程当前状态：描述当前进程状态信息，作为处理机调度的依据； -
进程优先级：进程抢占处理机的优先级； -
资源分配清单：说明内存地址空间或虚拟地址空间的状况，所使用的IO设备信息； -
处理机相关信息：指处理机中各寄存器的值，当进程被切换时，处理机状态信息都必须保存在PCB中，当线程被重新执行时，执行信息可以从PCB恢复到处理机；
进程通信：
- 共享存储：在通信的进程之间存在一块可以直接访问的共享空间，通过对这片共享空间读写实现进程通信；
- 消息传递：进程间通信的数据已Message为单位，利用操作系统提供的消息传递方式实现进程通信
- 管道通信：通过对共享文件
pipe文件的读写，写进程通过字符流将大量数据写入管道，读进程从管道接收数据，管道通信的条件:互斥，同步，确定对方存在
线程的概念：
线程是轻量级的进程，CPU调度的最小单元， 是进程中被调度和分派的基本单位，线程共享进程的全部资源；由线程ID，程序计数器，寄存器集合，堆栈组成；
引入线程的目的为了减小程序在并发执行时所付出的时空开销，提高操作系统并发性能
进程与线程的比较
| 角度 | 线程 | 进程 |
|---|---|---|
| 组成 | 线程id，程序计数器，寄存器集合，堆栈 | PCB，程序，数据 |
| 资源 | 线程不拥有资源，只能访问进程的资源 | 进程是资源的分配单位 |
| 上下文切换 | 在同一进程进行线程切换不需要切换进程 | 进程切换比线程切换的开销大很多，引入线程为了高效并发 |
| 通信 | 线程可以通过共享进程资源通信 | 进程通信涉及内核空间和用户空间的拷贝 |
线程的实现：
-
内核级线程：操作系统内核支持的线程，内核通过Scheduler调度器对线程进行调度，程序一般使用内核线程的高级接口轻量级进程（通常意义上的线程）去使用内核线程；每一个轻量级进程都由一个内核线程支持，一对一线程模型
特点：因为基于内核实现，所以涉及到系统调用，即用户态和内核态的切换，代价较高；
-
用户级线程：完全建立在用户空间的线程，内核不能感知用户级线程的存在，用户线程的调度完全在用户态实现；每一个进程对应多个用户级线程，一对多线程模型
特点：操作系统只负责把资源分配给进程，进程内部的线程操作，创建，调度，切换都需要自己完成，这是一件很困难的事情，所以用户线程实现的程序比较复杂，java 1.2之前使用的是用户级线程
JAVA线程的实现：
在jdk1.2之前，使用绿色线程的用户级线程，而到了jdk1.2中，使用了基于操作系统原生线程模型来实现，操作系统支持怎样的线程模型，很大程度上决定了jvm上线程是怎样映射；
JAVA线程的调度：
协同式线程调度：线程执行的时间由自己控制，当线程把工作做完以后，通知系统切换到另一个线程，实现简单，没有同步问题，如果一个线程出问题，整个进程就会阻塞；抢占式线程调度：线程的切换由系统控制，由系统为每个线程分配执行时间，我们可以通过优先级来建议系统为某些线程多分配时间，在java中，优先级可能会出问题，因为java线程的实现是基于操作系统原生线程实现的，java线程的优先级有十种，如果操作系统的优先级种类少于十种，那么某些优先级可能会相同；
JAVA线程的状态：
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,则唤醒一个进程，使其进入就绪队列，自己继续执行，否则直接继续执行，不影响其他进程；
死锁
死锁的概念：两个进程相互竞争对方的资源，又不释放自己的资源，若无外力作用，他们都无法向前推进
死锁的必要条件：
- 互斥：至少有一种非共享资源
- 占有等待：一个进程必须占有一种资源，并且等待一个被其他进程占有的资源
- 非抢占：进程占有的资源不能被抢占，只能主动释放
- 循环等待：形成一个进程———资源的环形链
死锁产生的原因：
- 竞争资源： 进程数>资源数
- 进程推进顺序非法：请求资源&释放资源的顺序不合理
预防死锁：
思路：破坏死锁的四个必要条件之一
- 资源一次性分配：一次性分配所有的资源，破坏占有等待
- 可剥夺资源：允许进程剥夺使用其他进程占有的资源，破坏非抢占
- 资源有序分配：系统给每个资源设置一个编号，每个进程按编号递增的顺序请求资源，编号递减的顺序释放资源，破坏循环等待
避免死锁：
银行家算法：当进程首次申请资源时，测试该进程对资源的最大需求量，若系统现有的资源满足它的最大需求量，按当前的申请资源分配，否则，推迟分配；
解除死锁：
- 剥夺资源：当系统检测到发生死锁时，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
- 撤销进程：将一个或多个思索进程终止（撤销），直至打破循环环路，使系统从死锁状态解脱。
