第一章 概述
1.1 定义操作系统
1.1.1 操作系统在计算机系统中的位置
操作系统位于计算机硬件和系统工具下的一层。
1.1.2 定义操作系统
控制和管理计算机的软硬件资源，合理组织计算机的工作流程，方便用户收集程序。
1.1.3 操作系统的功能：
管理系统资源是计算机系统的硬件资源和软件资源
资源管理功能：处理器管理；存储器管理；设备管理；文件管理；用户界面
1.1.4 两条红线:(两面)
面向系统-提高资源利用率
为用户提供良好的用户界面，方便用户使用
1.2 操作系统发展简史
随着计算机系统结构的发展，操作系统的发展大致经历了以下几代。
第一代计算机(1945—1955)：电子管和手工操作。
第二代计算机(1955-1965):晶体管和批处理系统。
第三代计算机(1965-1980):集成电路芯片和多程序设计技术。
第四代计算机(1980-1990):大型集成电路芯片和传统操作系统。
1.2.1 操作系统的发展阶段：四个阶段（P12）
SPOOLing技术：一般规律是，后一个操作系统阶段的出现是为了解决前一阶段的矛盾
第一阶段:无操作系统(电子管)-手动操作阶段
没有软件，人工干预，独家，串行
当CPU当速度提高时，会出现人机矛盾
- 专业计算机操作员
- 批处理，每批作业将有专门编制的监督程序依次自动处理
第二阶段：批处理系统（晶体管）-监督程序
批量处理对象，扩展称为bat。对用户提交的操作进行分类，将类似操作的操作分成一组，然后将一组操作放入系统中自动操作(由监督程序执行)
：指按作业执行时的特点划分作业的标准，如输入操作较多，或大部分作业在执行中进行计算操作
：(过渡与定序)
- 系统资源非常昂贵。
- 手动输入操作的速度和速度CPU速度不匹配
- 作业成批进入系统后备队
- 系统按照一定的策略自动调度操作
发展： 单道批处理系统
多道批处理系统
**·特点：**1)资源利用率高，吞吐量大。(资源可根据运行对系统资源的需求和系统当前状态进行充分调度)
2)周转时间长，无交互能力(操作进入系统后，系统自动调度，管理员或用户无法干预系统调度。
单道批处理阶段(作业):
作业运行期间，CPU单道作业仍执行一次。这里的批是指同时在主机上执行多个作业
**单道缺点：**系统资源利用率不高
**·早期/单道批处理：a.**联机批处理 **b.**脱机批处理
联机和脱机：相对于主机是联接或是断开（主机指内存 CPU）
联机批处理：主机直接完成慢速输入输出处理
**特点：**自动定序和自动过滤缩短了建立操作和人工操作的时间
**问题：**CPU与IO当输入输出时，串行操作，CPU处于空闲状态
脱机批处理:主机和慢速IO设备之间增加了——卫星机，使外设与主机并行工作，提高主机的利用
**特点：**增加卫星机，主机摆脱了 I/O操作与主机并行工作，通过卫星机提高主机的使用。
**问题：**磁带需要手动拆卸，系统保护不够。
卫星功能：输入设备将操作输入输入磁带，输出磁带将操作执行结果输出到输出设备。
第三阶段：执行系统阶段：
**·背景：**1)在批处理系统阶段，磁带需要人工装卸，操作麻烦，容易造成程序操作不安全。
2)在批处理操作过程中，没有监控程序，可能会导致用户程序篡改监控程序。
3)在批处理过程中，如果程序出错，用户无法干预程序，只能重新执行。
4）20 世纪 60 20世纪末，通道技术和中断技术的出现使操作系统进入了执行系统阶段。
第四阶段：多程序系统阶段（集成电路）
**·背景：**系统运行的处理仍是串行的，系统资源利用率不高。
**·特点：**1）多道
2)宏观并行(多个作业同时运行)
3)微观串行(某一时刻，单CPU仅运行）
**·意义：**引入多种程序设计技术可以改进 CPU 充分发挥计算机硬件的并行性。
**·解决问题：**1）存储保护与地址重定位
2)处理器的管理和分配
3)资源管理和调度。
**·技术问题：**共享系统资源，扩大内存，保护内存
**·多道缺点：**交互性差->产生分时系统
·单道：多个作业分批进入输入井，先来后到，依次高速执行
·多道:多道作业成批进入输入井，多道并发执行
·从执行时间上看：
在多种方式下，作业A的执行时间被拆分为：ta1 ta2=ta
单道方式下，作业A的执行时间为ta
·如果从时间范围的角度来看，即从操作进入系统到更改操作执行，则延长执行时间。即折衷问题：用户体验/用户感受到的响应时间和系统资源的利用率。
**：**在多个程序环境下，系统中的操作是共享系统资源->什么时候会释放占用的资源进行共享？
**答：**在执行过程中，暂时不需要使用资源时，暂时释放。
**解释：**从宏观上看，操作是并发的。然而，从微观（某一时刻、某一时间点）来看，操作仍然是串行的
**：**在多个批处理系统中，如果系统中同时执行三个操作，则在系统中交替执行三个操作。那么，如何穿插操作呢？或者什么时候操作会正在使用的资源？
**答：**在用户程序中使用外设时，单签使用CPU必须释放作业CPU其于其他作业。
**解释：**从宏观上看，从t1时刻到t2时刻，CPU一起忙碌，忽略作业间的过度时间，即监督程序的执行时间
1.3 操作系统分类（P14）
· 将处理器的运行时间分成非常短的时间片，根据时间片轮流将处理器分配给各种在线操作(各操作系统的时间片长度:Linux：5ms-8ms Windows95:20ms Win10:10ms）
**·技术：**一台主机连接多个终端，每个终端都有用户使用
**·特点：**同时性、交互性、独占性、及时性
同时正确实施响应时间有限，常用于军事方面
**·特点：**实时响应；高可靠性和安全性；实时操作系统的终端设备通常仅用作执行装置或咨询
⑥
- 个人计算机上的操作系统
- 嵌入式操作系统
- 网络操作系统：手机
- 分布式操作系统
- 智能操作系统
1.4 系统调用（P22）
1.4.1 系统调用概念
系统调用是操作系统及其他用户程序获得操作系统服务的途径，实现了用户与计算机硬件之间的一个接口，也是用户程序要求操作系统内核完成某一项工作时的过程调用。
1）从用户角度：方便用户使用计算机系统资源
2）从系统资源的角度：提高资源的利用，保护系统安
**·特点：**1）实现用户与计算机硬件资源之间的一个接口；
2）是对计算机机器指令的扩充；
3）是完成用户要求的特殊过程调用
·执行系统调用时，会引发——访管中断
(1) 运行状态不同。一般过程调用，其调用和被调用过程或者都是子程序，或者都是系统程序，运行在同一系统状态下：系统态或用户态。系统调用的调用过程是用户程序，它运行在用户态；其被调用过程是系统过程，运行在系统态下。
(2) 进入的方式不同。一般过程调用可以直接通过过程调用语句将控制转移到被调用的过程；而执行系统调用时，由于调用和被调用过程处于不同的系统状态，必须通过访管中断进入。
(3) 代码层次不同。一般过程调用中的被调用程序是用户级程序，而系统调用是操作系统中的代码程序，是系统级程序。
1）来源不同；
2）CPU态不同；
3）系统调用会引发访管中断，而子程序调用不会。
1.4.2 CPU的态
**·概念：**CPU的态即CPU的工作状态，分为核心态和用户态
**·意义：**CPU分态是为了对资源和指令的使用权限进行分类管理
·为区分CPU执行的是系统程序，还是用户程序，同时，也为保护操作系统，而将CPU分为两个状态：
**系统态/管态/核心态：**当前正在执行系统程序，可访问内存所有空间
内存空间通常包括两个部分：系统区，用户区
**用户态/目态：**当前正在执行用程序（用户程序），可访问内存中的用户空间
1.4.3 操作系统发展趋势：（P26）
微内核、嵌入式操作系统、分布式操作系统、多处理器并行操作系统、虚拟化操作系统
1.5 操作系统的特征（P24）
1.5.1 并发性
**·背景：**受到资源共享分配的影响，程序不可能从开始到结束不间断地被执行，执行中必然会出现间断。因此，多任务、多用户环境下程序是并发的方式被执行。
**·并发性：**指两个或多个事件在同一时间间隔内发生（逻辑上“同时”）
区分：并行性：指两个或多个事件在同一时刻发生（物理上“同时”）
·**作用：**为了改善系统资源的利用率并可提高系统的吞吐量，但同时也会使系统的管理更加复杂化
**操作系统的并发特性：**是指计算机系统中同时存在多个运行中的程序，因此，它应该具有处理和调度多个程序同时执行的能力。
**并发的体现：**内存中同时有多个用户的应用程序；多个操作系统程序被启动执行、暂停执行。
操作系统设计实现时必须具有控制和管理程序并发执行的能力。
1.5.2 虚拟性
**·概念：**虚拟性是操作系统中的一种管理技术，它是将物理设备虚拟成逻辑形式，通过某些软件和硬件技术，能够把资源虚拟成用户感官上独占的资源。
**·作用：**1）一方面为了提高系统资源的利用率
2）另一方面也为了方便用户的使用
**·采用的技术：**SPOOLing技术
**·包括：**1）虚拟CPU
2）虚拟存储
3）虚拟设备
1.5.3 共享性
**·背景：**在现代操作系统环境下，多任务及多用户的使用必然会使系统资源变得紧张。程序独占资源的执行方式虽然使得系统管理程序较为简单，但这种方式也会使其他等待相同资源的程序拉长等待时间，不利于提高用户程序的响应时间。同时，某资源被一个程序独占直到程序执行完毕，而该程序在执行中却不可能一直使用这种资源，所以独占方式的资源分配必然导致资源利用率的降低。
**·作用：**1）利于系统对于用户程序响应性能的提高
2）有利于提高资源的利用率
资源共享性分配相关的问题是分配策略、信息保护、存取控制等，必须妥善解决这些复杂问题。
1）共享性和并发性是操作系统的两个最基本特征，它们相互影响，相互依存。
2）资源的共享是因为程序并发执行导致的，若程序不是以并发的方式执行，资源也不必进行共享。
3）若系统中资源不能有效地共享使用，程序的并发也就无从说起，操作系统失去并发特性，整个系统性能将很难提升。
1.5.4 不确定性
**·不确定性：**是由操作系统的并发和共享性导致的。操作系统无法确定程序执行时间长短。操作系统的不确定性并不意味着无法控制资源的使用和程序的执行。
第二章 进程控制
2.1 进程的概念
2.1.1 进程的引入原因
的特点，不适应现代OS的需要（整个实体占用操作系统全部资源的方式不合时宜）
程序的结构也不具备并发处理的能力
及其特征：手工处理阶段以及单道批处理阶段，程序是按顺序化方式在系统中独占全机的去执行
**特征：**依靠监督程序处理，系统资源利用率不高
：
①顺序性：程序的执行严格按照顺序方式进行；
②封闭性：按顺序方式执行程序，该程序独占系统全部资源，不受外界因素的
③可再现性：一个程序在初始条件保持不变的情况下，无论在什么环境中运行、什么时间段内运行，都应该有相同的执行结果；（因此OS设计时必须保证，输入条件不变，不受环境及执行时间的限制，其输出结果保持不变）
2.1.2 程序并发执行特征
**并发的概念：**指两个或多个事件在同一时间间隔内发生
**①并发性：**程序的执行在时间上可以重叠，在单处理器系统中可以并发执行；在多处理器环境中可以并行执行；
**②共享性：**它们可以共享某些变量，通过引用这些共享变量就能互相交换信号，从而，程序的运行环境不再是封闭的；
**③制约性：**程序并发执行或协作完成同一任务时，会产生互相制约关系，必须对它们并发执行的次序（即相对执行速率）加以协调；
**④交互性：**由于程序在执行中共享某些变量，所以一个程序的执行可能影响其他程序的执行结果。因此，这种交互必须是有控制的，否则会出现不正确的结果。即使程序自身能正确运行，由于程序的运行环境不再是封闭的，程序结果仍可能是不确定的，计算过程具有不可再现性。
2.1.3 多道程序系统的执行环境特点
**①独立性：**每道程序都是逻辑上独立的，无逻辑的制约关系。即若有充分的资源，每道程序都可以独立执行，且执行速度与其他程序无关，且起止时间也是独立的
**②随机性：**在多用户的环境下，程序的数据的输入与执行开始时间都是随机的
**③资源共享性：**软、硬件资源的共享，会导致制约进程的执行速度
2.1.4 与时间有关的错误
**概念：**在多道程序并发执行的程序共享资源或者互相协作，因其执行速度的不确定性以及多道程序之间缺乏控制所带来的错误。
执行环境的非封闭性、共享资源未得到有效保护、或者是进程先后顺序执行中未执行完毕，有可能会发生时间上的错误。
有三种方式可以避免发生**“与时间有关的错误”**，但在操作系统中只能使用一种方法：在资源分配和使用的过程中通过采取有效的错误来避免。
2.1.5 进程的定义
有独立功能的程序在一个数据集上的一次执行过程。
进程是系统资源分配的基本单位。亦是资源分配的最小单位。
（程序执行的实体，例如一个工作由多人实行，一个人就是一个实体。从静态的角度观察，操作系统是一组程序和表格的集合；从动态的角度观察，操作系统是进程的动态、并发执行，有生存期。进程是执行中的程序。）
（进程是个动态的概念，可以关闭或者持续运行）
2.1.6 并发与并行的异同点
·并行：几道程序同时运行在不同的CPU上，宏观和微观上都是同时发生
·并发：几道程序分时运行在相同的CPU上，在宏观上通知，微观上不一定同时
·并发执行的两种方式：
①进程间的并发执行
②进程内部的并发执行
并行机上，多个CPU是同一时刻，同时运行多个程序。这个同时，是真正意义上的同时，是物理上的并行。
·并发需要解决的问题：
程序的并发执行：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的执行方式
·并发带来的问题：程序序的并发执行会破坏封闭性，同时潜在地破坏可再现性
2.1.7进程与程序的区别
①程序是静态的，存在外存中；进程是动态的，存在内存中，有生存期
②进程的特征是并发的，程序没有
③进程在执行过程中会占用系统资源，操作系统不会以程序为单位分配资源
④进程和程序之间是多对多的关系
i：程序与进程之间是一对多的关系
ii：进程与程序之间是一对多的关系——实验3
2.1.8 Bernstein条件
程序A和程序B，均对数据及Pi进行操作
程序A对数据及Pi读操作，Ra(Pi)
程序A对数据及Pi写操作，Wa(Pi)
程序B对数据及Pi读操作，Rb(Pi)
程序B对数据及Pi写操作，Wb(Pi)
程序A和程序B可以并发执行的条件：
1)Ra(Pi)与Wb(Pi)的交集为空
2)Rb(Pi)与Wa(Pi)的交集为空
3)Wa(Pi)与Wb(Pi)的交集为空
问题：
1)无法解决随机性；存在的程序个数未知，也无法判断哪些程序会使用到相同的共享数据
2)运行时只是部分程序或数据调入内存
基于上述原因，并发执行的程序，无法及时判断其共享的数据集，因此，
2.1.9 进程状态及转换（课本图+PPT图）
①进程状态的引入原因（方便操作系统管理系统中的进程）
新建状态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中，通常是还没有加载到主存中的新进程
运行状态：该进程正在被执行
阻塞状态：进程在等待某些事件，如I/O操作
就绪状态：进程做好了运行准备，只要获得CPU就可以开始执行
消亡状态：操作系统从可执行进程中中撤销了进程，或者自身停止，或者因为某种原因被撤销
②状态间的切换
2.1.10 Linux进程结构以及转换
运行/就绪—— TASK_RUNNING：通过进程是否占有CPU资源来区分
进程调度器：从各个CPU的可执行队列中分别选择一个进程在该CPU上运行
僵死——TASK_ZOMBIE：表示进程已经结束，但是没有从进程表中删除，仅剩task_struct结构这个空壳。task_struct中保存了进程的退出码，以及一些统计信息。用于在子进程在退出的过程中，内核向父进程发送一个信号，通知父进程来“收尸”。父进程可以通过wait系列的系统调用来等待某个或某些子进程的退出，并获取他们的退出信息，然后顺便将子进程的“尸体”（task_struct）也释放掉
可中断睡眠（浅度睡眠）——TASK_INTERRUPTIBLE：表示进程等待某个事件或某个资源。可以被信号唤醒而进入就绪状态等待调度
不可中断睡眠（）深度睡眠——TASK_UNINTERRUPTIBLE：因硬件资源无法满足，不能被信号唤醒，必须等到所等待的资源得到之后由特定的方式唤醒
暂停——TASK_STOPPED ：一般由运行状态转换而来，等待某种特殊处理
2.1.11 进程的实现PCB
·Process Control Block_进程 控制 块：是进程存在的唯一标识，是操作系统对进程进行控制、管理和调度的一句，它在创建进程时产生，在撤销进程时消亡
eg：PCB的作用？/存在的意义？
举例：OS管理进程——学校管理学生的学籍
OS:PCB = 学校:学籍卡
操作系统管理进程的一种静态信息
·PCB的主要内容：
进程标识符：进程符号名或内部id号
进程当前状态：本进程目前处于何种状态（运行、就绪、等待）
eg：当进程消亡到从系统中删除时，其对应的PCB是否还存在？
答：系统创建一个进程时，就为其创建一个PCB；进程被撤销删除时，相应的PCB也被删除。
2.1.12 进程的组成：code+data+stack+PCB
程序与数据：描述进程本身所应完成的功能
栈
PCB：进程的动态特征，该进程与其他进程和系统资源的关系
2.2 进程控制
2.2.1 四种进程控制的操作：PPT P.75
（创建、撤销）、（阻塞、唤醒）
进程创建：申请空白PCB->填PCB->置“就绪”状态
进程撤销：释放PCB->释放内存->释放所有资源
进程阻塞：置状态为“阻塞”->插入等待队列->停止程序运行->释放所有资源
进程唤醒：置状态为“就绪”->插入就绪队列
2.2.2 进程控制是否允许并发执行？
什么的并发：是为了提高系统吞吐量，实现资源共享的目的
潜在的问题：程序结果的不可再现性、打破程序结果的封闭性
不允许并发的可选择方法：系统调用、原语
2.2.3 原语
定义：把系统态下执行的某些具有特定功能的程序段称为原语（CPU处于关中断状态）
作用：用原语实现进程控制、保护操作系统内核
原语是原子操作(atomicoperation)，不可再分 ，要么全做，要么全不做。
地位：
进程控制均须用原语实现
操作系统内核的保护是通过原语 来实现
四种进程操作流程图
进程唤醒原语本身不涉及CPU资源的分配（非抢占式唤醒后即返回）
可抢占式内核中，新加入就绪队列的进程优先级是否高于目前使用CPU的进程优先级
2.2.4 Linux进程及进程控制
·终端管理进程与shell进程是init进程的子进程，而其它用户的进程则是由shell进程创建的。Linux系统中，除了0#进程以外的所有进程都是由init进程衍生出来的，故也称init进程是所有用户进程的祖先。
eg：父进程为什么要创建子进程？
答：Linux是一个多用户操作系统，在同一时间会有许多的用户在争夺系统的资源。有事进程为了早一点完成任务在争夺系统的资源。有时进程为了早一点完成任务就创建子进程来争夺资源。一旦子进程被创建，父子进程一起从forg处继续执行，相互竞争系统的资源。
★fork的使用：
fork创建新进程：
·为新进程生成task_struct结构
·为新进程赋予一个统一的标识(PID)【PPID父进程标识】
·为进程映像分配存储空间
·将新进程插入就绪队列
fork()：
pid=fork();
fork()返回值意义如下：
0：在子进程中，pid变量保存的fork()返回值为0，表示当前进程是子进程。
>0：在父进程中，pid变量保存的fork()返回 值为子进程的id值（进程唯一标识符）。
-1：创建失败。
fork系统调用的特点：一次调用两次返回
1)进程需要使用CPU
2)进程对应的程序+数据？（fork执行中是把父进程的PCB复制给子进程）
3)创建成功时，要区分是哪个进程在执行程序
进程占内存空间——一个进程其对应的代码和数据在内存中是分开存放的：
代码空间
数据空间
·实际上，新创建的进程，起初是和父进程共享代码空间，由PCB中存储地址；子进程会复制父进程的数据空间，但。当给子进程指定另外的程序执行时，子进程才会有自己的内存空间存放代码，
·进程撤销：
父进程想撤销时，有个先决条件是，其所有子进程全部。
当子进程执行完，准备退出时，由内核向其父进程发送一个信号，父进程不再继续“睡眠”，将转入就绪队列排队。之后，父进程接着将退出，即完成撤销操作。
2.3 进程间通信
2.3.1 进程之间的关系
进程互斥——进程间共享互斥资源
多个进程因不能同时访问而产生的制约关系称为进程的互斥
实现方法：PPT136
- 禁止中断
优点：简单有效
缺点：可能让系统无法正常相应紧急任务；且多CPU系统中该方法无效
- 软件方法：程序中设置标志位，进入临界区之前先测试该标志位，直到允许进入
优点：无需额外硬件，不增加成本。算法简单，易于实现
缺点：浪费CPU时间经常用于进行无效测试
进程同步——进程间执行顺序要求
系统中多个进程中发生的时间存在某种时序关系，需要相互合作，共同完成一项任务
进程通信——进程间交流的需要
互斥和同步的异同：
-
互斥进程各自单独执行时均可得到正确结果，仅在临界区交互时可能出现问题；同步进程间无法各自独立完成，需相互配合共同协调才能得到正确结果；
-
互斥进程进入临界区无顺序要求，同步进程间有严格的先后顺序要求；
-
互斥进程间不知对方的存在，而同步进程间不仅知道对方进程的存在，还需相互通信以达到相互协调。
2.3.2 临界资源
一次只允许一个进程使用的资源（扩展：如打印机，看起来是个共享的资源，实际上是个互斥的资源，表示了虚拟性）
临界区：访问临界资源的那段程序
临界区原则：有空让进、忙则等待、有限等待、让权等待
2.3.3 信号量机制（PV操作）：通过伪代码的方式
信号量：管理相应临界区的共有资源，它代表管理资源的使用权
信号量是一个整型变量：
>=0：可供并发进程使用的资源实体数
<=：正在等待使用临界区的进程数
用于互斥的信号量初值应该大于零
整数型信号量：仅通过两个标准的原子操作来访问，即P、V操作
记录型信号量：（常用，代码较复杂，但查询较为简单）除需要的一个用于代表资源数目的信号量外，还应增加一个进程链表，用于链接上述所有等待同一临界资源的进程
公用信号量和私用信号量：
信号量机制解决进程并发：用整型变量代表可用资源的实体数。（记录型信号量）
PV原语：信号量的初值只能由P，V原语操作（P：passeren V：verhoog）
PV操作：伪代码方式描述进程间共享资源的使用过程。
P操作：申请资源操作 PPT 150
①sem减1
②若sem减1后仍大于1或等于零，则P返回，进程继续
③若sem减1后小于零，则该进程阻塞转等待队列中
对于整数型信号量：申请共享资源时，首先，对信号量减一，表示将使用共享资源的进程多了一个，或者，可用的共享资源个数少了一个
当信号量减1后的值小于0，表示减1之前信号量的值至少是0了。此处表示减1之前信号量所管理的共享资源已无可用的了
eg：对于网络共享打印机，是同类资源，资源的使用不区分是某一个，共享资源的个数是多个
V操作：释放资源操作
①sem加1
②若sem加1后仍大于1，则V停止操作，进程返回调用处，继续执行
③若sem减1后小于或等于零，则该进程转就绪队列，同时进程调度选取一个等待队列中的进程转运行或就绪
若，信号量加1后的值大于1，表示该进程在释放资源之前，信号量所管理的共享资源个数至少为0，表示没有进程在等待使用共享资源。则当前进程V操作成功，或返回，继续执行后续操作。
若，信号量加1后的值等于0，表示该进程在释放资源之前，信号量的值为-1，也即有一个进程在等待；
若，信号量加1后的值小于0，表示该进程在释放资源之前，信号量的值必然小于0，有若干进程在等待；
因此，根据临界资源的使用原则：“有空让进”，则必须选中个等待中的进程，修改其状态有“等待”转“就绪”
如果，不管“有空让进”，pa进程继续使用CPU，而pb则仍处于“等待”状态，全局变量a一直处于“空闲”状态，这种情况是不被允许的！！
因此，pa进程不能继续“执行”状态，须转“就绪”状态。
eg：为什么？
原语的定义：系统态下执行的特殊程序段。（关中断状态）
PV操作涉及资源的分配。
PV操作时是否允许并发操作？原因？
·n个并发进程，互斥信号量mutex的初值为1：
mutex的取值范围为：1~-(n-1)
1：表示没有进程进入临界区。有一个资源，无进程等待；
0：表示有1个进程进入临界区。无资源，无进程等待；
-i：表示1个进程进入临界区。无资源，且有i(i<=n)个进程等待进入
·用P、V原语操作实现进程控制的方法与步骤：
①分析进程间关系
②为各并发进程设置信号量
③利用P、V原语和信号量规定各进程的执行顺序
2.3.4 Pc进程和Pp进程（这段不懂，保留原稿）
Pc进程：
借用wait和消息bufempty描述其执行过程；
signal通知对方进程
Pp进程：
借用wait和消息bufful描述执行过程
signal通知对方进程
思考：
该例中，为什么需要设两个消息名：bufempty和buffull？
只用一个消息是否可行？
由wait过程和消息bufempyt的使用决定某个进程是否可以开始执行，这与信号量机制中P操作的：申请资源–》信号量值减1；
由signal过程和消息buffull的使用，也可看作信号量机制中的V操作(即，释放资源)
目前分析来看，wait和signal和PV操作有一定的相通性。
Pc:
A: P(bufempty);
compute…
save–>bufffer…
V(buffull);
goto A
Pp:
B: P(buffull);
print…
delete…
V(bufempty);
goto B
PV操作是否能完成Pc和Pp进程执行的先后执行顺序
eg：如何设定bufempty和buffull的初值？
一般情况下，在初始情况时，buffer缓冲区是为空的，也即，对于初始情况下，应该能够保证Pc进程可以先于Pp进程运行！
因此，对于“P(bufempty);”，在初始情况下，应保证此P操作可以申请成功！
所以，bufempty的初值应该设为？
int bufempyt=1;//bufempty代表buffer初始情况下为空，未存放数据；
此处的1，还代表，Pc进程可执行一次的数据计算、存入buffer的操作！！
（信号量其它是管理的是共享资源的使用权！）
eg：对于buffull初值如何设定？
在初始情况时，buffer缓冲区是为空的，则对于Pp进程初始情况下，buffer未存放数据时，“P(buffull);”不能申请成功！
int buffull=0;//buffull代表buffer初始情况下为空，未存放数据，缓冲区为空不能执行Pp进程！
在buffer为空时，bufempty和buffull的初值决定了两个进程Pc和Pp的执行顺序！！
初值设定好了，再来判断PV操作是否可以实现进程同步的并发控制？？
思考：
Pc:
A: P(bufempty); //1–>0
compute…
save–>bufffer…
V(bufempty);//如果此处写的是这个V操作，会带来什么问题？？
//0–>1
//Pc进程循环不断地进行计算、存数据，而Pp进程并未取走数据！！
//V(buffull);
goto A
因此，Pc进程执行完一次数据的计算、存放后，不能V(bufempty)，不然会导致出现问题！
Pc:
A: P(bufempty); //bufempty : 1–>0
compute…
save–>bufffer…
V(buffull); //buffull : 0–>1，通知Pp进程”不必继续睡眠，要准备开始工作“
goto A
对于Pp进程：
Pp:
B: P(buffull); //1–>0
print…
delete…
V(bufempty); //0–>1
goto B
对于bufempty代表的缓冲区状态，什么时候会变会空？
将由Pp进程进行修改！
当buffer有数据时，由buffull和bufempty的值决定了Pc和Pp的执行顺序！
因此，在上述从初始情况到数据清空执行完毕后，Pc进程可继续运行！
2.3.5 进程通信IPC：进程间的信息交换
·低级进程通信：少量的信息交换，一般只传送一个和几个字节的信息，达到控制进程执行速度的作用。
·高级进程通信：大量的信息交换，有专门的同学机制，通信对用户透明
·直接通信方式（消息缓冲机制）：消息即进程之间相互传送的赖以发生交互作用的有结构的数据。两通信进程必须满足以下条件：
(1)在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对缓冲区消息队列的访问。同理，接收进程取消息时也禁止其他进程访问缓冲区消息队列。
(2)当缓冲区中没有信息存在时，接收进程不能接收到任何消息。
·间接通信方式（邮箱机制）：进程采用间接通信方式时，进程间发送或接收消息通过一个共享的数据结构一信箱进程采用间接通信方式时，进程间发送或接收消息通过一个共享的数据结构一信箱来进行，消息可以被理解为信件，每个信箱有一个唯一的标识符。
当两个以上的进程有一个共享的信箱时，它们就能进行通信。
进程间的通信要满足如下条件。
(1)发送进程发送消息时，邮箱中至少要有一个空格存放该消息。
(2)接收进程接收消息时，邮箱中至少要有一个消息存在。
邮箱包括两个部分:邮箱头和邮箱体。其中，邮箱头包括邮箱名称、邮箱大小、拥有该邮箱的进程名等;邮箱体用来存放消息。
2.3.6 管道通信
管道(pipe)通信是由UNIX首创的一种借助文件和文件系统形成的一一种通信方式。
消息缓冲通信机构是以内存缓冲区为基础的。
管道是以文件系统为基础的。
管道类型包括有名管道和无名管道。
管道按先进现出方式FIFO传送消息，且只能单向传送消息
相关命令：
2.3.7 软中断通信/信号机制
·信号（signal）机制是UNIX系统中最为古老的进程之间的通信机制，用于在一个或多个进程间传递异步信号。
·软中断是对硬件中断的一种，发送软中断就是向接受进程的task_struct结构中的相应项发送一个信号。接收进程在收到软中断信号后，将按照事先的规定去执行一个软中断处理程序。
·软中断和硬中断的区别：软中断处理程序必须等到接收进程执行时才生效，硬中断处理程序，收到中断信号后才被启动
·操作方式：忽略-ignore此信号；捕捉-catch信号；执行系统默认-default动作
·相关命令：
2.4 死锁
2.4.1 死锁的概念
在两个或多个并发进程中，如果每个进程持有某种资源而又都等待着别的进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。
2.4.2 死锁的起因
根本原因：系统资源不足->导致资源竞争使用->两种情况（资源的有效分配利用/死锁）
2.4.3 死锁产生的必要条件
(1)互斥。并发进程所请求的资源是互斥使用的资源，-次只能被一个进程使用。
(2)不可剥夺。进程所占有的资源在没使用完之前不能被其他进程抢占。
(3)部分分配。操作系统允许进程每次只请求自己所需资源的一部分。
(4)环路。系统中各并发进程对资源的占用和请求形成一个环路。
在上述4个条件中，互斥是资源的固有特性，是很难改变和破坏的。因此，要解决死锁，须从其他3个条件着手解决。
2.4.4 死锁的排除方法——死锁的预防
(1)破坏部分分配条件：将进程所需互斥资源一次性分配，不会因资源请求而被阻塞，从而预防了死锁；
(2)可剥夺资源：当某进程新的资源未申请成功时，释放已占有的资源，破坏了不可剥夺条件预防死锁；
(3)破坏环路等待条件：将资源编号，各进程申请资源按号的递增进行，从而破坏了环路等待条件预防死锁。
2.4.5 死锁的排除方法——死锁的避免（动态预防）
死锁的避免是指操作系统在动态分配过程中对每一次分配都要采取某种策略去判断一下当前的分配有无可能导致死锁，如果不可能则实施分配，否则拒绝此次分配。
死锁的避免也称为动态预防，因为系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免的方法。这是一种动态的排除死锁的方法。
状态划分：安全状态（处于此状态，可避免发生死锁）、不安全状态
安全状态：在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给
进程;否则进程等待。
当前系统中所有进程能够执行完毕的一种执行顺序，表示为<Pi,Pj,…,Pm>,称之为安全序列。
2.4.6 死锁的检测与恢复
最简单的办法：将产生死锁的进程全部撤销
逐个撤销死锁的进程，直至死锁解除为止
从发生死锁的进程中剥夺其占用的资源，破坏死锁的“不可剥夺条件”，剥夺的次序以花费最小为次序
2.5 线程
2.5.1 线程的引入原因
为了减少进程并发执行的开销，提高系统性能
将资源分配与调度分开
并发的进程因共享CPU时间片，则时间片满时，当前进程只能让出CPU，因此，系统中并发的进程不断进行切换。
进程在系统中是通过PCB。PCB信息很多，因此，进程切换，涉及系统资源的耗费是非常庞大的。
线程也可占用CPU，同进程下的不同线程间切换时，系统耗费非常小。
反之，不同进程下线程间的切换还是如进程间切换一样，系统资源耗费较大。
2.5.2 线程的基本概念
·线程是进程的一部分。
·线程是进程中的一个实体，是被系统独立调度和执行的基本单位。
·线程除运行必需的资源外，不拥有系统资源，但它可与同属一进程的其它线程共享进程所拥有的全部资源;
·一个线程可创建和撤消另一线程；同一进程中的线程间可并发执行; .
·线程有就绪、阻塞、执行三种基本状态
2.5.3 线程和进程的区别
系统开销：
创建——撤消的开销（PCB比TCB复杂）
调度开销：同一进程内的线程切换的开销小于进程切换开销，不会引起进程切换。
资源开销：线程一般不拥有资源，但可访问所属进程的资源。
通信开销：进程通信——具有独立的地址空间，通过共享文件等。线程通信一任务通信，开销小。
2.5.4 线程的分类
(1)用户级线程(user level threads)
用户级线程管理过程全部由用户程序完成，OS内核只对进程进行管理。OS提供一个在用户空间执行的线程库，包括创建、调度、撤销线程通信，线程的执行以及存储线程上下文的等功能。
(2)核心级线程(Kernel- level Threads)
即系统级线程，由OS内核进行管理。OS内核给应用程序提供相应的系统调用和应用程序接口API，使用户程序可以创建、执行、撤销线程。
2.5.5 线程的执行特性
产生(Spawn)：当产生一个新进程时，同时也为该进程产生-一个线程，随后，进程中的线程可以在同一个进程中产生另一个线程，并为新线程提供指令指针和参数。
阻塞(Block):当线程需要等待一个事件时，它将自己阻塞，此时处理器转而执行另一个就绪线程。
解除阻塞(Unlock):当阻塞一个线程的事件发生时，该线程被转移到就绪队列中。
结束(Finish):当一个线程完成时，其寄存器上下文和栈都被释放。
第三章 处理机调度
处理机调度关系到整个计算机系统性能，它是一个程序，一个安排进程先后执行顺序的算法。
3.1 作业的概念
3.2.1 作业的概念
定义：用户在一次解题过程中要求计算机所做工作的集合称为一个作业
作业与程序的区别
3.1.2 作业控制块JCB(PCB/TCB)
在作业建立到消亡的整个过程中，JCB一直存在，知道作业撤销时。（与PCB相同）
JCB是作业存在的标志。
JCB内容：作业名、作业类型、资源要求、资源使用情况、优先级（数）、当前状态、其他
引伸：
process control block 进程控制块
thread control block 线程控制块
JCB:job control block 作业控制块
DCB:device control block 设备控制块
3.1.3 作业与进程的区别
一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。而进程是对已提交完毕的程序所执行过程的描述，是资源分配的基本单位。其主要区别如下。
（1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。
（2）一个作业可由多个进程组成，且必须至少由一个进程组成，反过来则不成立。
（3）作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。
（1）进程更能真实地描述并发，而程序不能。
（2）进程由程序和数据两部分组成，进程是竞争计算机系统有限资源的基本单位，也是进程处理机调度的基本单位。
（3）程序是静态的概念；进程是程序在处理机上一次执行的过程，是动态的概念。
（4）进程有生存周期，有诞生有消亡。是短暂的；而程序是相对长久的。
（5）一个程序可以作为多个进程的运行程序；一个进程也可以运行多个程序。
（6）进程具有创建其他进程的功能；而程序没有。
一个作业通常包括程序、数据和操作说明书3部分。每一个进程由PCB、程序和数据集合组成。这说明程序是进程的一部分，是进程的实体。因此，一个作业可划分为若干个进程来完成，而每一个进程有其实体————程序和数据集合。
3.1.3 作业步的概念
作业步是在一个作业的处理过问程中，计算机所做的相对独立的工作。
每一个加工步骤称一个作业步 (Job Step)。 作业由不同的顺序相连的作业步组成。
3.1.4 作业的状态
(1) 提交状态。一个作业在其处于从输入设备进入外部存储设备的过程。
(2) 收容状态。作业内容全部进入外存输入井，但该作业还未被作业调度程序选中时
所处的状态。
(3) 执行状态。作业调度程序从后备作业队列中选择若干个作业投入运行，它为被选
中作业建立进程并分配必要资源，这些被选中的作业处于执行态。
(4) 完成状态。当作业运行完毕，但它所占有的资源还未全部释放时所处的状态。
作业与进程的关系
作业可被看作用户向计算机提交任务的实体，而进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。
一个作业由一个或多个进程组成：
(1)系统为一个作业创建一个根进程；
(2)在执行作业控制语句时，根据任务要求，系统或根进程为其建立相应的子进程；
(3)系统为子进程分配资源和调度各子进程完成作业要求的任务。
3.2 多级调度的概念
高+中+低+（线程调度）
3.2.1 高级调度
任务：决定将外存上后备队列中的哪些作业调入内存。
调度工作决定
接纳多少作业：取决于多道的程度，即内存允许放多少个作业。
接纳哪些作业：有调度算法决定。
适用于批处理系统
3.2.2 中级调度
又称进程调度、微观调度
任务：决定就绪队列中的哪些进程将获得处理机。
调度方式
非剥夺式
剥夺式
抢占原则
时间片
优先权
进程长短
适用于分时、实时、批处理系统
3.2.3 低级调度
又称对换程序
主要作用：内存和外存对换区之间进行进程对换，以解决内存紧张问题。
3.2.4 线程调度
现代操作系统为提高并行处理能力实现了线程技术,在此类操作系统中处理器的分派 与管理等调度均以线程为单位进行.对于线程调度(Thread Scheduling),一般采用优先调度策略
3.2.5 各级调度图
3.3调度性能衡量指标——作业调度算法
周转时间是指作业从提交时刻开始到完成时刻为止所经历的时间
或用等待时间加上执行时间，即
而平均周转时间就是将一段时间内系统执行完毕的所有进程的周转时间之和除以进程
的个数，如：
带权周转时间是指进程周转时间和进程执行时间的比值，即
而平均带权周转时间的计算公式为
3.3.1 先来先服务调度算法(First Come First Served, FCFS)
先来先服务调度算法按照作业进入就绪队列的先后次序选择作业投入运行。算法的优
点是易于理解且实现简单，只需要一个队列，对每道作业都相当公平。但是算法的缺点是
只考虑了作业进入就绪队列的先后，而没有考虑作业执行时间的长短，很可能出现短作业
等待的时间远超过其执行时间，因此该算法对短作业不利。
3.3.2 最短作业优先法(Shortest Job First, SJF)
为改进 FCFS 算法对短作业不利的调度方式，SJF 算法总是选取执行时间最短的作业
优先投入运行。
3.3.3 最高响应比优先法(Highest Response Ratio Next, HRN)
最高响应比优先法是对 FCFS 和 SJF 两种调度算法的一种综合运用。FCFS 方式只考
虑每个作业的等待时间而未考虑执行时间的长短，而 SJF 方式只考虑执行时间而未考虑等
待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN 调度策略
同时考虑每个作业的等待时间长短和估计需要的执行时间长短，当需要从就绪队列中选择
新的作业投入运行时，先计算这个作业的响应比，选择响应比最高的作业开始运行。
3.4调度性能衡量指标——进程调度算法
调度功能：PCB记录进程的有关情况、决定分配策略、实施处理机的分配和回收
3.4.1 优先数进程调度算法
作业在系统中创建时先确定其优先数。优先数的选择要综合考虑各种因素，如作业的
轻重缓急程度、作业的大小、等待时间的长短、外部设备的使用情况等，再结合系统性
能，最终确定其优先数，调度时按优先级高者先执行。
分为不可抢占CPU和可抢占CPU两种情况：
**可抢占式：**可剥夺方式也被称为抢占方式。在这种方式下，允许一个进程按照某种原则，抢占其它进程占有的处理机。抢占采用优先权原则的比较多，也就是说，如果一个进程比正在运行进程的优先级高，则它可以抢占处理机而运行
**不可抢占式：**不可剥夺方式也被称为非抢占方式。采用这种调度方式时，一旦把处理机分配给某个进程，该进程将一直执行下去，直到运行完毕或因某种原因不能运行，才把处理机分配给其它进程，决不允许其它进程强占正在运行进程占有的处理机。
进程被创建时，确定一个优先数，并在进程运行期间保持不变。
进程所需资源越多，运行时间将越长，其优先级越低。
无法反应进程执行特性。
进程被创建时，确定一个优先数，在以后任一时刻，进程被重新调度或耗尽时间片时，优先数被调整，以反映进程的动态变化。
例如，进程的优先级随着占用CPU而降低，随着等待时间增加而变高。
3.4.2 简单循环轮转法（RR=round robin）
让每个进程在就绪队列中的等待时间与享受服务的时间成比例。将CPU的处理时间分为固定大小的，若运行中的进程时间片到，但未完成操作时，则该进程放弃处理机，转到就绪队列尾部，等待下一次进程调度。
时间片：q=t/n;
q:时间片
t:用户可接受的响应时间
n:系统中进程个数
①当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为FCFS模式。
②当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。
4.例3－3
1>FCFS: 调度顺序： 1–>2–>3–>4
2>SJF: 调度顺序： 3–>2–>1–>4
3>RR:
时间片为1：
1->2->3->4->1->2->4->1->2->4->1->4->1->4->1->4->4
时间片为3：
1->2->3->4->1->4->4
5.改善简单循环轮转RR调度性能：
1>可变时间片
响应时间保持不变
2>多级反馈轮转法
时间片的设计：
S1>S2>S3>…>Sn
S1<S2<S3<…<Sn
3.5 LINUX进程调度
Linux系统采用动态优先数和可变时间片的调度算法，且采用可抢占式调度策略。
Linux系统调度目标是响应时间短，系统利用率高。
第四章 进程控制
4.1 存储管理概念
存储管理是操作系统主要的功能，存储管理主要对象是计算机中的内存，即主存储器。
存储管理的功能主要有： 主存储空间的分配和去配，地址转换，主存储空间的共享与保护，主存储空间的扩充
：由于用户程序中使用的地址是逻辑地址(也称相对地址)，而程序在内存被执行时(或程序在装入内存时)须将逻辑地址转换为机器可以识别的物理地址(也称绝对地址)。
(1) 逻辑地址是指用户程序经编译后，每个目标模块以 0 为基地址进行的顺序编址。逻辑地址又称相对地址。
(2) 物理地址是指内存中各物理存储单元的地址从统一的基地址进行的顺序编址。物理地址又称绝对地址，它是数据在内存中的实际存储地址
当一个进程装入到固定大小的分区块（比如页）时，假如进程所需空间小于分区块，则分区块的剩余的空间将无法被系统使用，称为内部碎片。
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。
单道连续分配只有内部碎片。多道固定连续分配既有内部碎片，又有外部碎片。