一.操作系统引论。

操作系统的定义：

一个系统软件，控制程序执行，防止错误和计算机的不当使用，执行用户程序给用户程序提供各种服务，方便用户使用计算机系统。

操作系统的4个目标：

方便性，有效性，开放性，可扩展性。

操作系统的4个特性：

并发，共享，虚拟，异步。

操作系统的作用：

作为用户和计算机硬件系统间的接口。

实现了对计算机资源的抽象。

为计算机系统资源的管理者。（1.处理及管理功能，2.存储器管理功能，3设备管理功能，4.文件管理功能）

单批道处理操作系统：

定义：内存中只能保持一道作业，系统资源利用率低。

多批道处理操作系统:

定义：内存中同时处理多个作业，利用某个作业的IO操作的空档时间去执行其他作业。

优点:资源利用率高，系统吞吐量大。缺点:平均周转时间长，无交互能力，提交作业后到作业完成都不能交互。

分时系统：

定义：按分时原则为每个用户服务彼此不干扰。 特征:多路性，独立性，及时性，交互性

实时系统：

定义：能及时响应外部事件的请求，并能在规定时间内完成该事件，并控制所有实时任务协调一致的运行。 特征：多路线，独立性，及时性，交互性，可靠性。

二、进程的描述与控制。

前驱图：

定义：有效无循环图(DAG)，用于描述进程间执行的先后顺序，每个节点表示一个程序段或进程或语句，有向边表示前驱关系。

进程。

定义:程序的一次运行，引入进程概念后，进程是系统进行资源分配和调度的独立单位。进程实体：由程序段，相关数据段，进程控制块PCB构成，进程实体简称进程。三种基本状态及转换。五种基本状态及转换。

进程控制快（PCB)。

定义：PCB是进程实体的一部分，是一种记录型数据结构，PC b中记录了操作系统所需的，用于描述进程的当前情况以及控制进程运行的全部信息。

作用:使一个在多道程序环境中不能独立运行的程序成为一个人独立运行的基本单位,或与其他进程并发执行的进程，系统利用PC b描述进程的基本情况和活动过程,进而控制和管理进程。

具体作用:

作为独立运行的基本单位的标志.能实现间断性运行方式.提供进程管理所需的信息.提供进程调度所需要的信息.实现与其他进程的同步与通信.

包含信息:

进程标识信息.处理器信息.进程调度信息.进程控制信息.

进程控制块的组织方式:

线性方式.链接方式.索引方式.

进程控制.

功能:进程控制是进程管理中最基本的功能，包括创建新的进程，终止已完成的进程，将因发生异常情况而无法继续运行的进程置于阻塞状态，负责进程运行中的状态转换等功能。o s内核：将一些与硬件相关模块，常用设备驱动模块和一些使用频率较高的模块安排在仅靠硬件的软件层次中，将他们常驻内存，即通常被称为os内核，作用是保护这些软件和提高os运行的效率。支撑功能（支撑os及其他模块所需的基本功能)。 中断处理.时钟管理.源于操作（源于操作是由若干条指令组成，不可分割，要么全执行，要么不执行）

进程创建。

相关知识: 进程可以创建另一个进程,子进程可继承父进城所有的资源，获得了句柄的进程就拥有了控制其他进程的权力。

引起进程创建的事件：

用户登录.作业调度.提供服务.应用请求.

进程创建步骤:

申请空白PCB。为新进程分配其运行所需要的资源.初始化进程控制块.若进程就绪对列能接纳新的进程，则将新的进程插入就绪对列.

进程同步。

概念:进程同步机制的主要任务是对多个相关进程在执行次序上进行协调，使并发执行的各进程间能按一定规则或次序共享系统资源，并能很好的和合作，从而使进程程序的执行具有可再现性。

两种形式的制约关系:

间接相互制约关系:像打印机这样的临界资源，必须保证多个进程对他只能互斥的访问，进程间就形成了间接相互制约关系。直接相互制约关系:如两进程合作完成某项任务，如a通过缓冲区向b提供数据时，若缓冲区无数据，则b因不能执行而阻塞，进程间就形成了直接相互制约关系。

同步机制遵循的规则.

空闲让进.忙则等待.有限等待.让权等待.

信号量机制

整形信号量:用于表示资源数目的整形量s. 原子操作:执行时不可中断的. p,v操作:对应wait（s）,signal（s）都是原子操作.记录型信号量:整型信号量未遵循让权等待，所以引入记录性信号量，但因为出现让权等待后，可能多个进程等待同一临界资源，所以除资源数目value外，还需要增加一个进程链表指针list。and型信号量：当一个进程需要多个共享资源才能执行时，易和其他进程各握着一个共享资源，从而导致死锁。解决方案:将进程运行所需要的资源一次性全部分配给进程(要么全分配，要么一个也不分配)。信号量集:and信号量每次都是加1或减1，效率低且易发生死锁，所以为资源的分配设置下限值，即si大于等于t才允许分配，如某进程需求值为d，则直接进行减d而不是减1。信号量的应用: 利用信号量实现进程互斥.利用信号量实现前驱关系.

线程。

定义及引入线程的目的:线程是一种轻型进程,为减少程序在并发执行时所付出的时空开销，提高程序并发执行的速度。

特点:

进程在创建,撤销,切换时,时空开销较大，而线程仅需保存和设置少量寄存器内容，切换代价远低于进程.一个进程的多个线程也可并发执行.进程的多个线程可在不同处理机运并行执行.

线程的三个状态:

执行状态就绪状态.阻塞状态.

线程控制块tcb包含:

线程标识符.一组寄存器.线程运行状态.优先级.线程专有存储区.信号屏蔽.堆栈指针.

线程实现方式:

内核支持线程KST（直接取得内核支持,简单).用户级线程（ULT）（间接取得内核支持，复杂）.组合方式.

处理机调度与死锁。

三级调度（一个作业提交，执行，完毕，往往需要多级调度)。

高级调度:决定将外存上处于后备队列中哪几个作业调入内存（频率低).低级调度:决定就绪队列中哪几个进程获得处理机（频率高)。中级调度:内外存信息对换（决定是否挂起)。便于内存管理，提高内存利用率和系统吞吐量。

处理器调度算法的目标.

对批处理系统.

平均周转时间短.系统吞吐量高.处理机利用率高.

对分时系统.

响应时间快.均衡性.

对实时系统.

截止时间保证.可预测性.

作业.

包含:程序,数据和作业说明书（作业控制快jcb).

三个阶段（三个状态）。 1. 收容阶段（后备状态)。 2. 运行阶段（运行状态)。 3. 完成阶段（完成状态)。

作业调度算法.

先来先服务算法fcfs.短作业优先算法sjf.优先级调度算法psa.高响应比优先调度算法hrrn 优先权=（等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间。

进程调度.

主要任务.

保存处理机的现场信息.按某种算法选取进程.把处理器分配给进程.

两种进程调度方式.

非抢占式:一旦分配给某个进程，则一直运行至结束。抢占式:（遵循下面三个原则) 优先权原则.短作业优先原则.时间片原则.

三种进程调度算法.

轮转调度算法RR.（就绪队列上的每个进程每次运行一个时间片)。 完成时间:从开始的时间到该进程结束的时间. 周转时间:完成时间-到达时间. 带权周转时间=周转时间/服务时间.

优先级调度算法.（在轮转调度算法基础上引入优先级)。

类型:抢占式优先级调度算法，非抢占式优先级调度算法。优先级的类型: 静态优先级:一开始就确定优先级动态优先级:先设置一个优先级，随进程推进或等待时间的增加而改变优先级。

多队列调度算法.（多个进程的就绪队列)。 特点:不同类型进程可分配在不同的就绪对列，不同队列可用不同调度算法，不同队列也可设置不同优先级。

实时调度。

（在实时系统中，必须满足实时任务对截止时间的要求)。

实现实时调度基本条件:

提供必要的条件.（就绪时间，开始截止时间和完成截止时间，处理时间，资源要求，优先级)。系统处理能力强.采用抢占式调度机制.具有快速切换机制.

实时调度算法。

最早截止时间优先算法EDF.（可用于抢占式和非抢占式):根据任务截止时间确定优先级，优先级最高的放在队首，每次选择就绪队列中的第1个任务。最低松弛度优先算法LLF:根据松弛度确定优先级（主要用于抢占式)。 松弛度=必须完成时间-本身运行时间-当前时间.

死锁。

定义:如果一组进程中，每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的.

产生死锁的必要条件:

互斥条件.请求和保持条件.不可抢占条件.循环等待条件.

处理死锁的方法。

预防死锁（破除4个必要条件之一)避免死锁.（防止系统进入不安全状态.）检测死锁. （简化资源分配图使进程成为孤立点即无死锁）解除死锁.（撤销进程或剥夺资源至某个进程解除死锁）

安全状态:是指系统能按照某种进程推进顺序，为每个进程分配其所需要资源，直到满足每个进程对资源的最大需求，使每个进程都能顺利完成.

利用银行家算法避免死锁。

银行家算法4种数据结构:

available向量:系统可利用的资源数目.max矩阵:各个进程中对每种资源的最大需求.allocation矩阵:每个进程已分配的各类资源数目.need矩阵:每个进程尚需的各类资源数目.

算法步骤: 如某进程p一发出请求资源，请求向量为request，利用银行家算法，判断是否将资源分配给p。

判断request≤need？是则执行下一步，否则错误。判断request≤available？是的话进行下一步，否则等待。系统试探将资源分配给p,且更新状态: available=available-request，allocation=allocation+request, need=need-request，系统执行安全性算法检测此次分配后系统是否处于安全状态，若安全则正式分配给p，若不安全则恢复资源分配前的状态，让p继续等待。（安全性算法:看系统是否能按某种性进程顺序执行所有进程)

资源分配图简化方法:如图R2有空闲,分配p1,p1完成释放p1,相关边r1有空闲,分配给P2,P2完成,孤立.所以无死锁。 解除死锁常用方法：

撤销进程:撤销全部进程或者按某种顺序撤销，逐个撤销。剥夺资源:剥夺足够资源，使某个进程解除死锁。

存储器的管理

存储器的多层结构

寄存器 高速缓存 主存储器 磁盘缓存 固定磁盘 可移动存储介质

程序的运行。

程序在系统中运行的步骤:

编译:原程序编译成若干目标模块.链接:将一组目标模块和所需的库函数链接形成装入模块.装入:由装入程序将装入模块装入内存.

程序装入的三种方式.

绝对装入方式:当计算机系统小且进行运行单道程序时，就可能知道程序将注入在内存的位置，所以在程序中采用符号地址,编译后转为绝对地址逻辑地址与内存实际地址完全相同.可重定位装入方式:在多道程序环境中，不可能知道程序驻留内存的位置，所以编译形成的目标模块地址一般从0开始，程序中其他地址也都是相对起始地址计算的，指令地址也要修改，它可以根据内存具体情况，将装入模块装入到内存合适位置。动态运行时的装入方式:把装入模块装入内存后，并不立即把装入模块中的逻辑地址转为物理地址，而是把这种转换推迟到程序真正执行时再转换。

程序链接的三种方式。

静态链接方式:在程序运行前先将各目标模块及所需的库函数链接成一个完整的装入模块，以后不再拆开.

装入时动态链接:边装入边链接，即在装入一个模块时，若发生一个外部模块调用事件,再装入外部目标模块，再进行链接（修改目标模块中的相对地址)。 装入时动态链接的优点:一是便于修改和更新，二是便于实现对目标模块的共享。

运行时动态链接:对于某些程序每次运行模块可能不同，所以事先只有将所有相关模块都装入内存，但这效率很低，所以采用运行时动态链接，在程序执行过程中，发现被调用模块未被装入内存，再将此模块输入内存，链接到调用模块上。

连续分配存储管理方式.

连续分配方式可分为4类。 单一连续分配.固定分区分配.动态分区分配.动态可从定位分区分配. 基于顺序搜索的动态分区分配算法. 首次适应算法ff:从链首开始顺序查找，直到找到一个能满足要求的空闲分区为止，然后根据作业大小从该分区中划出一块内存空间分配给请求者. 缺点:低址部分不断划分会留下许多难以利用的，很小的空闲分区碎片，且每次从低址查找，增加了查找空闲分区的开销。 优点:为以后到达的大作业创造了条件.循环首次适应算法nf:与首次适应算法类似，区别就是不再每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。 优点:内存空间分区分布均匀，减少了查找空闲分区时间开消。 缺点:缺乏大的空闲分区。最佳适应算法bf，总把能满足要求，且又是最小的空闲分区分配给作业. 缺点:会留下很多难以利用的碎片。最坏适应算法wf:扫描整个空闲分区表或链表时，总挑选最大的空闲分区从中分割一部分存储空间给作业使用。 缺点:缺乏大的空闲分区. 优点:产生碎片可能性小，查找效率高。

离散分配存储管理。

分页存储管理方式. 1.定义:用户将程序的地址空间分为若干个固定大小的区域.称为页或页面，典型页面大小为1kb，相应的吧，把内存空间分为若干个物理块或页框，页和块的大小相同，用户可将程序的任意一页放入任一物理块中，实现离散分配。

页内碎片:由于进程的最后一页装不满一块，而形成了不可利用的碎片，称之为页内碎片。

页面大小: 1.过小:1:减少内存碎片总空间,内存利用率提高.2.进程占用较多页面,进程页表过长，占用大量的内存.3.降低页面换进换出效率. 2.过大:1.减小页表长度，减少内存消耗。2.提高页面换进换出效率。3.页内碎片增大，

页表:实现了页号到物理快的映射。

快表:由于页表在内存中，使得CPU每存取一次数据时都要两次访问内存，第1次查找对应物理块号，再将物理快与偏移量w拼接形成物理地址，第2次通过获得的物理地址取得所需的数据。这样效率很低，所以在地址变换机构中增加一个高速缓冲寄存器，称之为快表，所以每次先在快表中查找是否存在相匹配的块号，若没有再去页表中查找。

内存的有效访问时间eat 。（t表示访问内存的时间，λ表示查找快表的时间，α表示查找快表命中率)。 使用快表:eat=t+t. 不使用快表:eat=t+αλ+(1-α)(t+λ).

两级和多级页表:由于现在计算机系统支持非常大的逻辑空间，这样环境下页表就非常大，所以要占用很大的内存空间。 采用两种方法解决：

对页表所需内存空间可采用离散分配方式，以解决难找到一块连续的大内存空间问题。可用两级和多几级页表解决，两级页表是将页表进行分页并编号，每个页面大小与内存物理块相同，然后将分页的页表离散的存放在不同物理块中，同样在为离散分配的页表再建立一张页表称为外层叶表，在里面记录页表页面的物理块号。

只将当前需要的部分页表调入内存，其余的页表仍驻留在磁盘。

分段存储管理方式。

引入目的:

方便编程.信息共享.信息保护.动态增长.动态链接.

缺点:

地址变换需要花费时间。需为段表提供附加的存储空间。有外部碎片.

分段:在分段存储管理系统中,作业的地址被划分为若干段，每个段定义了一组逻辑信息,如main,子程序段，数据段等，每段都有一个段号，且都从零开始编址，并采用一段连续的地址空间，各段长度不等。

断表:每个表项记录:段号，段长，基址（内存起始地址)。 作用:实现逻辑段到物理内存的映射。

虚拟存储器。

定义:

虚拟存储器指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

特征:

多次性:不用将程序一次性调入内存，可允许程序被分成多次调入内存。（只调用当前需求运行的部分)。对换性:在进程运行期间允许将暂时不用的代码和数据从内存调至外存.虚拟性:从逻辑上扩充内存容量.

虚拟存储器的实现方法.

请求分页存储管理方式:请求分页系统是建立在基本分页系统的基础上，为了能支持虚拟存储功能而增加了请求调页功能和页面置换功能。

6种页面置换算法:

最佳置换算法opt:拥有最好的性能，实际无法达到,可用于评价其他算法的优劣。具体实现是每次选择淘汰的页面都是在未来最长时间不在访问的页面。先进先出页面置换算法fIfo .最近最久未使用的页面置换算法lru,。最少使用置换算法lfu。clock置换算法（访问，访问位设为1，0淘汰1变为0,循环扫描）。页面缓冲算法.

请求分段存储管理方式:建立在分段式系统上，以分段为单位换进换出,增加请求调段功能和段置换功能。

IO

IO系统的基本功能:

隐藏物理设备的细节.与设备的无关性.提高处理机和IO设备的利用率.对IO设备进行控制.确保对设备的正常共享.错误处理.

数据项:

定义最低级的数据组织形式.分类: 基本数据项:数据组织中可以命名的最小逻辑数据单元.组合数据项:由若干个基本数据项组成的.

记录:

定义：一组相关数据项的集合，用于描述一个对象在某方面的属性。

文件:

定义：由创建者所定义的，具有文件名的一组相关元素的集合。

补充。

程序顺序执行时的特征:顺序性,封闭性，可再现性.程序并发执行时的特征:间断性,失去封闭性,不可再现性.进程的作用:为使程序并发执行，并且可对并发执行的程序加以描述和控制。进程的特征: 1.结构特征:由 PCB和程序段和相关数据段组成. 动态性，并发性，独立性，异步性。