进程与线程

2.1.1进程的概念和特征

1.进程的概念 进程，更好的描述和控制程序的并发执行，实现操作系统的并发性和共享性 进程程序块：PCB，用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。唯一标识 进程映像：程序段，相关数据，PCB构成，静态

• 进程是程序的一次执行过程
• 进程是一个程序及其数据在处理机上顺序执行所发生的活动
• 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

2.进程的特征 动态性：进程是程序的一次执行，有创建，活动，暂停，终止等过程，具有一定的生命周期，基本特征 并发性：重要特征 独立性：独立运行 异步性：进程相互制约，进程具有执行的间断性，异步性导致进程结果不可再现，因此需要配置相应的进程同步机制 结构性：程序段，相关数据，进程控制段构成

2.1.2进程的状态与转换

运行状态：进程正在处理机上运行，在单处理机环境下，每一时刻最多只有一个进程处于运行状态 就绪状态：进程已处于准备运行的状态，即进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行 阻塞状态：等待状态，进程正在等待某一事件而暂停运行 创建状态:进程正在被创建，尚未进入到就绪状态 结束状态：进程正在系统中消失，可能是正常结束也可能是中断 运行状态----就绪状态：处于运行状态的进程在时间片用完后，不得不让出处理机；优先级高的先执行的情况下

2.1.3进程控制

1.进程的创建 允许一个进程创建另一个进程，父进程创建子进程，子进程可以继承父进程所拥有的资源，子进程被撤销，将归还资源。 创建原语：

• 为新进程分配一个唯一的进程标识号，并申请一个空白的PCB（有限）
• 为进程分配资源，为新进程的程序和数据，及用户栈分配必要的内存空间
• 初始化PCB，包括初始化标志信号，初始化处理机状态信息和初始化处理机控制信息，设置进程的优先级

2.进程终止：正常结束，异常结束    操作系统终止进程的过程（撤销原语）：

• 根据被终止进程的标识符，检索PCB，从中读出该进程块的状态
• 若被终止进程处于执行状态立即终止该进程的执行，将处理机资源分配给其他进程
• 若该进程还有子进程，则终止所有子进程
• 将该进程所拥有的资源还给父进程或系统
• 将该PCB从所在的队列（链表）删除

3.进程的阻塞和唤醒 正在执行的进程由于期待的某些事件未发生，系统自动执行阻塞原语（Block），使自己状态变为阻塞状态 Block的执行过程：

• 找到将要被阻塞进程的标识号对应的PCB
• 若该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
• 把该PCB插入到相应事件的等待队列中

Wakeup唤醒原语：

• 在该事件的等待队列中找到相应的PCB
• 将其从等待队列中移出，并置其状态为就绪状态
• 把该PCB插入就绪队列中，等待调度程序调度

4.进程切换 过程：

• 保存处理机上下文，包括程序计数器和其他寄存器
• 更新PCB信息
• 把进程的PCB移入相应的队列
• 选择另一个进程执行，并更新PCB
• 更新内存管理的数据结构
• 恢复处理机上下文

模式切换：处理机逻辑上可能还在同一进程中运行

2.1.4进程的组织

进程是操作系统的资源分配和独立运行的基本单元 1.进程控制块     创建时，新建一个PCB结构，之后就常驻内存，任意时刻可以存取，进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标识 2.程序段 能被进程调度程序调度到CPU执行的程序代码段。多个进程可以运行在同一个程序 3.数据段 可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果

2.1.5进程的通信

进程之间的信息交换， 1.共享存储         2.消息传递 在消息传递系统中，进程间的数据交换是以格式化的消息为单位的。 3.管道通信   指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件（pipe）管道机制存在互斥，同步和确定对方的存在。 引入进程，为了更好的使用多道程序并发执行，以提高资源利用率和系统吞吐量，增加并发程度

2.1.6线程概念和多线程模型

1.线程的基本概念   引入线程，为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能 是一个基本的CPU执行单元，也是程序执行流的最小单位，由线程ID，程序计数器，寄存器集合和堆栈组成 2.线程与进程的比较

• 调度。拥有资源和独立调度的基本单位都是进程，在引入线程 的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。在同一进程中，线程的切换不会引起进程切换；
• 拥有资源。进程是拥有资源的基本单位，线程可以访问其隶属进程的系统资源
• 并发性。都可以并发
• 系统开销。线程开销小
• 地址空间和其他资源。进程的地址空间相互独立，同一进程的各线程间共享进程的资源，抹进程内的线程对其他进程不可见
• 通信方式。进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以直接读写进程数据段来进行通信

３.线程的属性

• 轻型实体：每个线程都有一个唯一标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态
• 不同的线程可以执行相同的程序，即同一个服务程序被不同用户调用时，操作系统为他们创建不同的线程
• 同一进程中的各个线程共享该进程所拥有的资源
• 线程是处理机的独立调度单位，可以并发执行
• 线程被创建开始生命周期

４.线程的实现方式 用户级线程（ULT）：有关线程管理的所有工作由应用程序完成 内核级线程（KLT）：有关线程管理的所有工作由内核完成，

---

处理机调度

1.调度的基本概念   对处理机进行分配。 2.调度的层次   

• 作业调度：又称高级调度，主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个或多个作业，给它们分配内存，输入输出设备等必要的资源，并建立相应的进程，获得竞争处理机的权利，内存与辅存之间的调度，对于每个作业只调入一次，调出一次
• 中级调度：又称内存调度，为了提高内存利用率和系统吞吐量；那些暂时不能运行的进程，调至外存等待，把此时的进程状态成为挂起状态，当它们具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程，再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待
• 进程调度：又称低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给他们

3.三级调度的联系

• 作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进行的进程挂起，中级调度处于作业调度和进程之间
• 作业调度次数少，中级调度次数略多，进程调度频率最高
• 进程调度是最基本的，不可或缺。

4.调度的时机，切换与过程    进程调度和切换程序是操作系统内核程序。请求调度的事件发生后，运行进程调度，调度了新的就绪进程后，才会去进行进程间的切换。   不能进行进程调度和切换的情况：

• 在处理中断的过程中：中断处理过程复杂，在实现上难做到进程切换，中断处理是系统工作的一部分，逻辑上不属于某一进程，不应该被剥夺处理机资源
• 进程在操作系统内核程序临界区中：进入临界区后，需要独占式的访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放
• 其他需要屏蔽中断的原子操作过程中：如加索，解锁，中断现场保护，恢复等原子操作，在原子过程中，连中断都需要频闭更不应该进行进程调度与切换

     如果发生了上述中的引起进程调度的条件，不能马上进行调度和切换，应置系统的请求调度标志，知道上述过程结束后才进行相应的调度与切换 应进行调度与切换的情况是：

• 当发生引起调度条件，且当前进程无法继续运行下去，马上进行调度与切换
• 当中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行调度与切换。（剥夺方式的调度）

5.进程调度方式     进程调度方式是指当某一个进程正在处理机上执行时，若有某个更为重要的或紧迫的进程需要处理，即优先权更高的进入就绪队列，此时应该如何分配处理机

• 非剥夺调度方式，又称非抢占方式。一个进程正在处理机上执行，即使有其他的优先级高的，也会继续执行；适用于批处理系统，不能用于分时系统和实时系统
• 剥夺调度方式，抢占式。一个进程正在处理机上执行，有其他的优先级高的，会先让优先级高的处理

6.调度的基本准则 CPU利用率，系统吞吐量，周转时间 周转时间：作业完成时间-作业提交时间 平均周转时间 带权周转时间=作业周转时间/作业实际运行时间 处理机调度算法实际上不影响作业执行或输入/输出操作时间，只影响作业在就绪队列中等待所花的时间 7.调度算法 1）先来先服务（FCFS）调度算法     既可以用于作业调度，也可以用作进程调度。不可剥夺算法。 特点：简单，效率低，对长作业有利，有利于CPU繁忙型作业，不利于I/O繁忙型作业 2）短作业优先（SJF）     优先选择运行时间短的进程 3）优先级调度算法     既可以用于作业调度，也可以用作进程调度。

• 非剥夺式优先级调度算法。
• 剥夺式优先级调度算法

    进程优先级分为两种：静态优先级：优先级是创建进程时确定的，运行期间保持不变，根据进程类型，进程对资源的要求，用户要求。动态优先级：根据进程的情况变化动态调整优先级。 4）高响应比优先调度算法      响应比Rp=等待时间+要求服务时间/要求服务时间 5）时间片轮转调度算法         适用于分时系统，按到达时间一次排序，规定时间片，即使进程未完成运行，也要必须释放处理机给下一个就绪进程，被剥夺的返回就绪队列的末尾重新排队。 6)多级反馈队列调度算法 是时间片轮转和优先级调度的综合和发展，

---

进程同步

2.3.1进程同步的基本概念

    多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系，为了协调进程之间的相互制约关系，引入进程同步。 1.临界资源     一次仅允许一个进程使用的资源称为临界资源。临界资源访问过程：

•  进入区：检查是否能进入临界区，可以，设置临界区标志，防止其他进入
• 临界区：进程访问临界资源的那段代码，（临界段）
• 退出区：将正在访问的临界区的标志清除
• 剩余区：代码中其余部分

2.同步 直接制约关系，为完成某种任务而建立的两个或多个进程，相互合作 3.互斥     为禁止两个进程同时进入的准则：

• 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入
• 忙则等待
• 有限等待
• 让权等待

2.3.2 实现临界区互斥的基本方法

1.软件实现方法     算法一：单标志法             turn=0时允许P0进程进入，该算法只允许一个进程进入，两个进程是交替进入，某个不再进入，另一个也不进入，违背空闲让进，造成资源利用不充分             算法二：双标志法先检查   ，先检查对方标志，再设置自己标志。临界资源正在被访问，等待，否则进入 优点：可以连续使用；缺点：Pi和Pj可能同时进入，违背忙则等待     算法三：双标志法后检查 先设置自己标志true，再检查对方标志 对方标志都为true，产生饥饿现象     算法四：Peterson's Algorithm 先设置自己的标志后，再设置true标志，同时检测另一个进程状态标志和不允许进入标志 2.硬件实现方法 硬件提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等 1）中断屏蔽法     关中断----临界区------开中断     限制了处理机交替执行程序的能力，效率降低， 2）硬件指令方法     TestAndSet指令：原子操作，读出指定标志后，把标志设置为真。     Swap指令：交换两个字的内容 硬件方法的优点：适用于任意数目进程，简单容易验证其正确性，可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。 缺点：进程等待进入临界区时要耗费处理时间，不能实现让权等待，饥饿现象

2.3.3信号量

可以解决互斥与同步的问题，只能被原语wait（S)和signal（S）来访问，记作P操作，V操作 1.整型信号量    S 表示资源数目的整型量

wait(S){               while(s<=0)测试        s=s-1;   } signal(s){        s=s+1; }

未遵循让权等待 2.记录型信号量

    int value;     struct process *L;

3.利用信号量实现同步      y需要用到x的运行结果     若P2先执行到P（S）时，S为0，执行P操作会把进程P2阻塞，放入阻塞队列中，当进程P1中的z执行完后，执行V操作，把P2从阻塞状态放回就绪队列，当得到处理机时就可以继续执行了 4.利用信号量实现进程互斥     

2.3.4管程

1.管程定义     系统中的各种硬件资源和软件资源，均可用数据结构抽象的描述其资源特性，即用少量的信息对资源执行 操作来表示该资源，而忽略了他们的内部结构和实现细节。管程是一组数据以及定义在  这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。 2.管程的组成

• 局部于管程的共享结构数据说明
• 对该数据结构进行操作的一组过程
• 对局部于管程的共享数据设置初始值的语句

3.管程的基本特征

• 局部于管程的数据只能被局部于管程内的过程所访问
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

2.3.5经典同步问题

1.生产者-消费者问题 问题描述：一组生产者进程和一组消费者进程共享一个初始为空，大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，只允许一个生产者放入消息，或者一个消费者从中取出消息。 信号量设置：信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量为初始值1；信号量full用于记录当前缓冲池为满，初始值为0.信号量empty用于记录当前缓冲池中空，初始值为n。 2.读者-写者问题     问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程同时访问共享数据时则可能导致数据不一致的错误。要求：允许多个读者 可以同时对文件执行读操作；只允许一个写者往文件中写信息；任意写者在完成写操作前不允许其他读者或写者工作 3.哲学家进餐问题     问题描述：一张圆桌坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭；哲学家思考时不影响其他人，哲学家饥饿时才试图拿起左右两根筷子，如果筷子已在他人手中，需等待。拿到两根筷子才能进餐。 4.吸烟者问题 问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它，但是要卷起并抽到烟，需要三种材料：烟草，纸胶水。每个人拥有一种材料，，供应者每次提供两种材料，拥有剩下那种材料的人卷烟并抽掉，并给供应者提供信号完成了，

---

死锁

2.4.1死锁的概念

1.死锁定义     指多个进程因竞争资源而造成的一种僵局（互相等待） 2.死锁产生的原因     1）系统资源的竞争          通常争夺不可剥夺的资源，会发生死锁     2）进程推进顺序非法          进程运行过程中，请求和释放资源的顺序不当，信号量使用不当也会发生死锁     3）必要原因

• 互斥条件：进程要求对所分配的资源进行排他性控制，
• 不剥夺条件：进程主动释放资源
• 请求和保持条件：已经占有资源，又提出新的资源请求，而该资源已被其他占用，此时请求被阻塞
• 循环等待条件：循环等待链

   2.4.2 死锁的处理策略

   1.预防死锁 设置某些限制条件，破坏产生死锁的条件    2.避免死锁  在资源的动态分配过程中，用方法防止系统进入不安全状态    3.死锁的检测及解除   检测发生的死锁，并解决

2.4.3死锁预防

破坏产生死锁的四个条件之一即可 1.破坏互斥条件 2.破坏不剥夺条件   3.请求和保持条件 4.循环等待条件

2.4.4死锁避免

1.银行家算法 思想：将操作系统看作银行家，操作系统管理的资源相当于银行家管理的资金，进程向系统请求分配资源相当于用户向银行家贷款。

2.4.5死锁检测和解除 

1.资源分配图 框中的一个点代表一类资源中的一个资源，从进程到资源的有向边叫请求边，资源到进程的边叫分配边。