程序、进程、线程的基本概念、信号量的PV操作、前趋图的PV操作

程序、进程、线程的基本概念

进程控制块PCB的组织方式：顺序方式、链接方式、索引方式、Hash。

在JVM 中进程与线程关系

进程：

• 拥有资源的独立单位。
• 可以被独立调度。
• 可以分配资源。

线程：

• 可以被独立调度。
• 同一进程中的多个线程，共享一些资源：内存地址空间、代码、数据、数据、文件等。
• 同一进程中的多个线程，每个线程私有：程序计数器、寄存器栈等。

进程的状态

此处先不考虑进程抢占式CPU调度的情况

• 进程的状态模型根据不同的场景有多种，例如：三态模型、五态模型、七态模型…。

三态模型：

• 进程状态划分依据：将CPU和其他资源进行归类，将资源分为两大类（CPU、非CPU），进程状态根据资源被占用的情况进行划分；
• 当CPU和其他资源都都具备的情况下，进程被调度，状态：运行。
• 当CPU资源不足，而其他资源具备，（除CPU以外，其他资源都做好了准备），进程状态：就绪。
• 就绪状态等到CPU调度进程，状态转为运行。
• 一个进程无法长期占用多个CPU资源，把CPU资源划分为多个小的时间片段进行分发给多个进程，一个进程的时间片用完，就会从运行转为就绪，等待CPU的下一次调度。
• 当CPU资源和非CPU资源都不足时，进程状态：阻塞（等待）。
• 运行的进程等待某个事件，转为阻塞状态，等待事件发生，从阻塞转为就绪状态。
• 不考虑特殊情况，CPU资源准备好，非CPU资源不足。
• 阻塞态不能直接转为运行态。
• 就绪态不能直接转为阻塞态。

五态模型：

• 在原三态模型基础上加入了挂起，从而有了静止状态和活跃状态。
• 挂起：当内存中进程过多，内存不足，将某些条件不足的进程挂起，放入磁盘对换区里，暂时不参与调度。
• 挂起的过程：进程从内存放入磁盘的过程。
• 静止的状态必须进行恢复或者激活才能转为活跃状态。
• 活跃的状态挂起转为静止状态。
• 静止的状态存在磁盘对换区中，活跃的状态存在内存中。
• 静止的状态无法被CPU直接调度，必须进行激活成活跃状态才能被调度转为运行态。
• 运行态挂起转为静止就绪态。
  运行中的进程等待某个事件的发生，从而转为活跃阻塞。

信号量的PV操作

进程间的同步关系与互斥关系

• 互斥模型（间接制约关系）：由于临界资源的限制，进程间相互排斥，这种关系也叫：间接制约关系。
• 同步模型（直接制约关系）：进程间存在互相依赖的关系，进程间存在顺序上的制约，这种关系也叫：直接制约关系。

• PV操作具有原子性。（原语）
• PV操作结合信号量进行操作。
• 信号量：资源数量（全局变量）。
• 对信号量-1（s-1）就是对资源数量-1，也就是对资源占据的过程。
• 对信号量+1 （s+1）就是对资源数量+1，也就是对资源释放的过程。
• P操作：申请并占用资源，加锁。
• V操作：释放占用的资源并通知排队进程，解锁。
• P操作，信号量<0（s<0），说明申请的资源没有占据到，资源不足。进程需要排队领资源，进入阻塞队列。
• V操作，信号量<=0（s+1），说明释放占用的资源，并通知排队进程进行下一个V操作，唤醒阻塞进程进入就绪态。无论信号量如何，进程继续进行后续动作。
• 信号量<0，可以表示资源数和排队的进程数。
• PV成对存在，只加锁不解锁（死锁），只解锁不加锁（无意义）。

前趋图的PV操作

• 前趋图是一种图的形式，一个图包含相应的节点，有向图中带有方向箭头连线各个节点，前趋图是有向图。
• 每一个节点代表一个进程。
• 箭头代表进程间的依赖关系。
• 如同所示：A是B的前趋，B是A的后继。
• 前趋图中，只有前趋完成，才能开始后继；后继开始前一定要确保前趋已完成。
• 存在多个进程并行的前趋图，进程间存在互相依赖的关系，是进程的同步关系，是直接制约关系。
• 前趋图体现的是：进程间存在互相依赖的关系，是进程的同步关系，是直接制约关系。
• A—>D可以表示为：（A,D）。

前趋图有时候可以不考虑信号量，主要关注节点间（进程间）的PV操作

死锁

系统有M个进程，每个进程都需要W个资源，系统需要多少个资源（N）才不可能发生死锁？
N>= M(W-1)+1*