操作系统-进程和线程
进程和线程
进程线程的区别 1、进程是什么？ 是具有一定独立功能的程序、它是系统进行资源分配和调度的一个独立单位，重点在系统调度和单独的单位，也就是说进程是可以独立运行的一段程序。 当进程激活时，操作系统就将系统的资源包括内存、I/O和CPU等分配给它，使它执行。 2、线程又是什么？ 线程进程的一个实体，是CPU调度和分派的基本单位，他是比进程更小的能独立运行的基本单位，线程自己基本上不拥有系统资源。每一个线程对应于它在进程中的一个函数，也就是内存中的代码段，多个线程执行时CPU会根据它们的优先级分配时间，使它们完成自己的功能。 一般来说，进程中至少一个线程，一个主线程和其他线程组成一个进程。多个线程的目的在于分享CPU的时间片，从而完成并行任务。
在运行时，只是暂用一些计数器、寄存器和栈 。 二、他们之间的关系 1.线程是比进程更小的能独立运行的基本单位，通常一个进程都有若干个线程，至少也需要一个线程。 2.调度：线程是调度和分派的基本单位，进程是资源拥有的基本单位。 3.并发性：进程之间可以并发执行，在一个进程中的多个线程之间也可以并发执行。 4.拥有资源：进程是拥有资源的一个独立单元，线程自己不拥有系统资源（也有一点比不可少的资源）但它可以访问其隶属进程的资源。 5.系统开销：创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等，OS所付出的开销显著大于在创建或撤消线程时的开销；进程切换的开销也远大于线程切换的开销。
进程的生命周期
进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化（一个进程会经历若干种不同状态）。通常进程有以下五种状态，前三种是进程的基本状态。
- 运行状态：进程正在处理机上运行。在单处理机环境下，每一时刻最多只有一个进程处于运行状态。
- 就绪状态：进程已处于准备运行的状态，即进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。
- 阻塞状态，又称等待状态：进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。
- 创建状态：进程正在被创建，尚未转到就绪状态。创建进程通常需要多个步骤：首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息；然后由系统为该进程分配运行时所必需的资源；最后把该进程转入到就绪状态。
- 结束状态：进程正从系统中消失，这可能是进程正常结束或其他原因中断退出运行。当进程需要结束运行时，系统首先必须置该进程为结束状态，然后再进一步处理资源释放和回收等工作。
注意区别就绪状态和等待状态：就绪状态是指进程仅缺少处理机，只要获得处理机资源就立即执行；而等待状态是指进程需要其他资源（除了处理机）或等待某一事件。之所以把处理机和其他资源划分开，是因为在分时系统的时间片轮转机制中，每个进程分到的时间片是若干毫秒。也就是说，进程得到处理机的时间很短且非常频繁，进程在运行过程中实际上是频繁地转换到就绪状态的；而其他资源（如外设）的使用和分配或者某一事件的发生（如I/O操作的完成）对应的时间相对来说很长，进程转换到等待状态的次数也相对较少。这样来看，就绪状态和等待状态是进程生命周期中两个完全不同的状态，很显然需要加以区分。
进程状态转换
等待态—→挂起等待态：如果当前不存在就绪进程，那么至少有一个等待态进程将被对换出去成为挂起等待态；操作系统根据当前资源状况和性能要求，可以决定把等待态进程对换出去成为挂起等待态。 挂起等待态—→挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态。 挂起就绪态—→就绪态：当内存中没有就绪态进程，或者挂起就绪态进程具有比就绪态进程更高的优先级，系统将把挂起就绪态进程转换成就绪态。 就绪态—→挂起就绪态：操作系统根据当前资源状况和性能要求，也可以决定把就绪态进程对换出去成为挂起就绪态。 挂起等待态—→等待态：当一个进程等待一个事件时，原则上不需要把它调入内存。但是在下面一种情况下，这一状态变化是可能的。当一个进程退出后，主存已经有了一大块自由空间,而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化。 运行态—→挂起就绪态：当一个具有较高优先级的挂起等待态进程的等待事件结束后，它需要抢占 CPU，，而此时主存空间不够，从而可能导致正在运行的进程转化为挂起就绪态。另外处于运行态的进程也可以自己挂起自己。 新建态—→挂起就绪态：考虑到系统当前资源状况和性能要求，可以决定新建的进程将被对换出去成为挂起就绪态。
进程调度
- 先来先服务 （FCFS，first come first served） 在所有调度算法中，最简单的是非抢占式的FCFS算法。 算法原理：进程按照它们请求CPU的顺序使用CPU. 算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平 算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程 2.最短作业优先（SJF, Shortest Job First） 短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。 算法原理：对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。 算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。 算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。 3.最高响应比优先法(HRRN，Highest Response Ratio Next) 最高响应比优先法(HRRN，Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。 算法原理：响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。 算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。 算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。 4.时间片轮转算法（RR，Round-Robin） 该算法采用剥夺策略。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。 算法原理：让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。 算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。 算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当 怎样确定时间片的大小： 时间片大小的确定 1.系统对响应时间的要求 2.就绪队列中进程的数目 3.系统的处理能力 5.多级反馈队列(Multilevel Feedback Queue) 多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。 多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能够较好的满足各种类型用户的需要。
死锁
操作系统中有若干进程并发执行，它们不断申请、使用、释放系统资源，虽然系统的进程协调、通信机制会对它们进行控制，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况。此时，若不借助外界因素，谁也不能释放资源，谁也不能解除阻塞状态。根据这样的情况，操作系统中的死锁被定义为系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这就是死锁。 产生死锁的原因主要是： （1） 因为系统资源不足。 （2） 进程运行推进的顺序不合适。 （3） 资源分配不当等。 如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。 其次，进程运行推进顺序与速度不同，也可能产生死锁。 产生死锁的四个必要条件： （1） 互斥条件：一个资源每次只能被一个进程使用。 （2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。 （3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。 （4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。 这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。 死锁的解除与预防： 理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源。因此，对资源的分配要给予合理的规划。
死锁解决
处理死锁的策略 1、忽略该问题。例如鸵鸟算法。 2、检测死锁并且恢复。 3、仔细地对资源进行动态分配，以避免死锁。 4、通过破除死锁四个必要条件之一，来防止死锁产生。 鸵鸟算法： 该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。 银行家算法： 所谓银行家算法，是指在分配资源之前先看清楚，资源分配后是否会导致系统死锁。如果会死锁，则不分配，否则就分配。 按照银行家算法的思想，当进程请求资源时，系统将按如下原则分配系统资源： (1) 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。 (2) 进程可以分期请求资源，当请求的总数不能超过最大需求量。 (3) 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。 (4) 当系统现有的资源能满足进程尚需资源数时，必须测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足则按当前的申请量分配资源，否则也要推迟分配。 解决死锁的策略 对待死锁的策略主要有： (1) 死锁预防：破坏导致死锁必要条件中的任意一个就可以预防死锁。例如，要求用户申请资源时一次性申请所需要的全部资源，这就破坏了保持和等待条件；将资源分层，得到上一层资源后，才能够申请下一层资源，它破坏了环路等待条件。预防通常会降低系统的效率。 (2) 死锁避免：避免是指进程在每次申请资源时判断这些操作是否安全，例如，使用银行家算法。死锁避免算法的执行会增加系统的开销。 (3) 死锁检测：死锁预防和避免都是事前措施，而死锁的检测则是判断系统是否处于死锁状态，如果是，则执行死锁解除策略。 (4) 死锁解除：这是与死锁检测结合使用的，它使用的方式就是剥夺。即将某进程所拥有的资源强行收回，分配给其他的进程。
死锁的避免： 死锁的预防是通过破坏产生条件来阻止死锁的产生，但这种方法破坏了系统的并行性和并发性。 死锁产生的前三个条件是死锁产生的必要条件，也就是说要产生死锁必须具备的条件，而不是存在这3个条件就一定产生死锁，那么只要在逻辑上回避了第四个条件就可以避免死锁。 避免死锁采用的是允许前三个条件存在，但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链，从而避免死锁。该方法支持多个进程的并行执行，为了避免死锁，系统动态的确定是否分配一个资源给请求的进程。方法如下： 1.如果一个进程的当前请求的资源会导致死锁，系统拒绝启动该进程； 2.如果一个资源的分配会导致下一步的死锁，系统就拒绝本次的分配； 显然要避免死锁，必须事先知道系统拥有的资源数量及其属性
进程通信的方式
（1）管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。 （2）命名管道 (named pipe) ： 命名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。 （3）信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。 （4）消息队列( message queue ) ： 消息队列是消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。 （5）信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。 （6）共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。 （7）套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
线程生命周期
1)生命周期的五种状态 新建（new Thread） 当创建Thread类的一个实例（对象）时，此线程进入新建状态（未被启动）。 例如：Thread t1=new Thread(); 就绪（runnable） 线程已经被启动，正在等待被分配给CPU时间片，也就是说此时线程正在就绪队列中排队等候得到CPU资源。例如：t1.start(); 运行（running） 线程获得CPU资源正在执行任务（run()方法），此时除非此线程自动放弃CPU资源或者有优先级更高的线程进入，线程将一直运行到结束。 死亡（dead） 当线程执行完毕或被其它线程杀死，线程就进入死亡状态，这时线程不可能再进入就绪状态等待执行。 自然终止：正常运行run()方法后终止 异常终止：调用stop()方法让一个线程终止运行 堵塞（blocked） 由于某种原因导致正在运行的线程让出CPU并暂停自己的执行，即进入堵塞状态。 正在睡眠：用sleep(long t) 方法可使线程进入睡眠方式。一个睡眠着的线程在指定的时间过去可进入就绪状态。 正在等待：调用wait()方法。（调用motify()方法回到就绪状态） 被另一个线程所阻塞：调用suspend()方法。（调用resume()方法恢复）
线程调度
多数线程的调度是抢占式的（即我想中断程序运行就中断，不需要和将被中断的程序协商） a) 时间片方式（time slicing） b) 非时间片方式
- 下面几种情况下，当前线程会放弃CPU
a) 线程调用了yield()或sleep()方法主动放弃 b) 由于当前线程进行I/O访问，外存读写，等待用户输入等操作，导致线程阻塞 c) 为等候一个条件变量，线程调用wait()方法 d) 抢先式系统下，有高优先级的线程参与调度；时间片方式下，当前时间片用完，有同优先级的线程参与调度
- Java至少有两个线程：主线程、垃圾收集线程
多线程的运行模式有协作式和抢占式。 协作式：主动让出时间片，要加sleep提高CPU利用，否则一直占用CPU 抢占式：CPU分配时间片，不加sleep会提高分配到CPU资源的机会 一般在多线程中适当sleep，哪怕很短，因为如在协作式系统中，线程不会让出CPU，如有线程是高速设备的运行，而其它设备有IO等设备的操作运行。而线程执行机会是均等的，如不加sleep，及可能的情况是：高速设备的线程独占CPU。
线程通信
linux系统中的线程间通信方式主要以下几种:
- 锁机制：包括互斥锁、条件变量、读写锁 互斥锁提供了以排他方式防止数据结构被并发修改的方法。 读写锁允许多个线程同时读共享数据，而对写操作是互斥的。 条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
- 信号量机制(Semaphore)：包括无名线程信号量和命名线程信号量
- 信号机制(Signal)：类似进程间的信号处理