操作系统概论

静态分配内存

动态分配内存

一是使操作系统内核的空间不会被用户随意访问，以保证系统的安全和稳定

二是确保每到用户程序都在自己的内存空间中运行，互不干扰

将逻辑地址转换为物理地址

顺序性

封闭性

可再现性

程序并发执行是指在同一时间间隔内运行多个程序。<br>一个程序执行结束之前，可以运行其他程序。

程序并发执行有以下特点

<b>进程是允许并发执行的程序在某个程序集合上的运行过程</b>

<b>进程是由正文段、用户数据段及进程控制块共同组成的执行环境</b>

（1）并发性<br>

（2）动态性

（3）独立性

（4）异步性

（5）结构特征

<b>进程与程序的区别</b><br>

<b>进程与程序的联系</b>

<b>每个进程有唯一的进程控制块，进程控制块是操作系统感知进程存在的唯一标志</b>

进程标识符信息

处理机状态信息

进程调度信息

进程控制信息

（1）就绪态

（2）执行态

（3）阻塞态

<b>进程开始在CPU上运行，进程的状态就由就绪态变为执行态。执行态进程可能变为就绪态，也可能变为阻塞态</b>

<b>进程状态不能由阻塞态直接变为执行态</b>，进程状态转换阻塞态变为就绪态的过程称为<b>唤醒过程</b>，由执行态变为阻塞态的过程称为<b>阻塞过程</b>

<br>

把系统中具有相同状态的进程控制块（PCB）用其中的链接字链接成一个队列

系统根据所有进程的状态，建立几张索引表，索引表的每一个表项指向一个PCB的物理块

当系统中有很多进程时，可以把进程控制块用队列组织起来，形成<b>进程队列</b>。<br>处于就绪态的进程构成的进程队列被称为<b>就绪队列</b> <br>处于阻塞态的进程构成的进程队列被称为<b>阻塞队列</b> <br>

同步中断是当指令执行时由CPU单元控制产生的<br>之所以称为同步，是因为只有在一条指令终止执行后才会发出中断，如<b>除法出错、调试、溢出和浮点出错</b>

异步中断是由其他硬件设备随机产生的

<b>外部中断又可以分为外部可屏蔽中断和外部不可屏蔽中断</b>

中断向量是对于不同中断源到来的信号编号，该编号是一个无符号整数（0-255），成为中端向量

不可屏蔽中断的向量和异常的向量是固定的，而可屏蔽中断的向量可以通过对中断控制器的编程来改变

可编程中断控制器的IRQ线是从0开始顺序编号的

用户空间是指用户进程所处的地址空间，一个用户进程不能访问其他进程的用户空间，只有系统

系统调用运行在核心态，而一般函数运行在用户态

系统调用与一般函数调用的执行过程不同

系统调用一般要经过中断处理，比一般函数调用多了一些系统开销

用整型变量值来标记资源的使用情况。<br><b>若整型量>0，说明有可用资源；若整型量<=0，说明资源忙，进程必须等待。</b><br>对于一次只允许一个进程访问的临界资源，可定义一个用户互斥的整型信号量，并将其初始化为1，<br><b>整型信号量的值只能通过两个特定的原子操作wait和signal来改变。 </b><br>

整型信号量的互斥：初始变量为1 整型信号量的协调：初始变量为0

总结

记录型信号量的优点是不存在「忙等」，采取了「让权等待」的策略 

基本思想是将进程在整个运行过程中所需要的所有资源一次性的全部分配给进程，待进程使用完之后再一起释放。只要还有一个资源不能分配给该进程，其他所有可能为之分配的资源也不分配给它。

周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔

包括四部分时间：

如果系统中有n个作业，<b>系统的平均周转时间</b>等于n个作业的周转时间之和除以n

作业的周转时间T与系统为它提供的服务时间Ts之比为W，W称为<b>带权周转时间</b>

<b>服务时间</b>Ts是一个作业在CPU上执行的的总时间

响应时间是指从用户提交一个请求开始直至系统首次产生相应的时间为止的一段时间

截止时间是指某个任务必须开始的最迟时间，或必须完成的最迟时间

在选择和设计进程调度算法应考虑使得CPU的利用率尽可能高

调度算法

性能分析

调度算法

算法优点

算法缺陷

调度算法

优先权调度算法的类型

优先权的类型

优先权调度算法存在的问题和解决方案

时间片轮转调度算法

时间片大小的确定

时间片轮转调度算法的性能评价

引入时间片轮转调度算法的目的是：多个终端都能得到系统的及时响应

将每个进程分配到不同的队列，每个队列都有自己的调度算法

多级反馈队列可以解决多级队列调度中存在的无穷阻塞（饥饿）的问题

提供必要的调度信息

系统处理能力强

采用抢占式调度机制

<b>具有快速切换机制</b>

最早截止时间EDF算法

最低松弛度优先LLF算法

静态分配

动态分配

采用主——从式操作系统，操作系统的核心部分驻留在一台主机上，而从机上只运行用户应用程序，只有主机执行调度程序，而所有从机的进程都是由主机分配的

自调度

成组调度

指一个进程在访问资源的过程中，其他进程不能访问该资源<br>

进程已经保持了至少一个资源，又提出了新的资源要求，而新请求的资源已经被其他进程占有，此时进程阻塞，但又对已经获得的资源保持不放<br>

进程已经获得的资源不能被剥夺，只能由进程自己释放

进程死锁时，必然有个一进程申请资源的环形链

<b>摒弃请求和保持条件</b>

摒弃不剥夺条件

摒弃环路等待

当系统能找到一个进程执行序列，使系统只要按此序列为每个进程分配资源，就可以保证进程的资源分配和执行顺利完成，不会发生死锁时，称系统处于安全状态。<br>若不存在这样的安全序列，则称系统处于不安全状态。

<b>不安全状态不一定是死锁状态，但当系统处于不安全状态之后，便可能进入死锁状态，反之，只要系统处于安全状态，系统可避免进入死锁状态</b>

因此，避免进程思索的实质在于<b>使系统处于安全状态</b>

available[ ]是一个一维数组。标识系统中某种资源的可用数量，也就是这种资源可分配的数量，available[j]=k表示j类资源的可用数量为k，系统可以为进程分配的j类资源为k个

max[ ]是一个n行m列的二维数组。表示各进程需要各类资源的最大数量。max[i,j]=k表示进程pi需要j类资源的最大数量为k个

allocation[ ]是二维数组。表示某时刻已分配给进程的某类资源数。allocation[i,j]=k表示进程pi已经占有j类资源k个

need[ ]是二维数组，表示某个进程还需要某类资源的数量，need[i,j]，表示进程pi还需要j类资源k个

把用户区划分成大小相等的若干个分区

缺点是内存利用率比较低

当程序太小时，改程序所占用的分区有很大一部分是空闲的<br>当程序太大时，可能找不到一个分区足以装下改程序

为用户进程分配空间时，把大小最接近进程大小的空闲分区分配给申请内存空间的进程。<br>使小进程占小分区，大进程占大分区，减少内存浪费

系统在空闲分区表中<b>为每一个空闲分区建立一个表项</b>，每个表项中包含分区编号、大小和起始地址

使用空闲分区表的缺点是，若设置太多表项，会浪费内存空间；设置太少的表项，当空闲分区较多时，无法记录所有空闲分区的情况。在实现时，结构体的大小不容易确定

可以动态的为每一个空闲分区建立一个结点。每一个结点包过分区大小、分区起始地址、指向前一个分区结点的指针，以及指向后一个结点的指针

空闲分区链中的每个节点占用的内存可以动态分配，动态回收。

要求空闲分区链以地址递增的顺序连接<br>

在进行内存分配时，从链首开始顺序查找，直到找到一个能满足进程大小要求的空闲分区为止。然后在按照进程请求内存的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。

该算法先分配低地址部分的内存空间，容易使低地址部分留下小分区，而高地址部分大空闲分区较多。当进程请求大空间时，要找到合适的空闲分区时，时间开销大<br>

<b>而低地址部分的空闲分区反复被划分</b>，可能留下许多难以利用的很小的空闲分区，这种小空闲区被称为<b>外部碎片或外碎片</b><br>

分配给进程的的分区若大于进程请求的分区，分区内存在一部分人不被利用的空间，这部分被浪费的空间称为<b>内部碎片或内碎片</b>

为进程分配内存空间时，不再每次从链首开始查找，而是<b>从上次找到的空闲分区的下一个空闲分区开始查找</b>，知道找到第一个能满足要求的空闲分区，并从中划出一块玉请求的大小相等的内存空间分配给进程。

为实现该算法，应该设置一个<b>起始查找指针</b>，以指示下一次起始查找的空闲分区，并采用<b>循环查找方式</b><br>

循环首次适应算法的优点是：空间分布均匀，查找开销较小。缺点是容易使系统缺乏大空闲区

该算法每次作业分配内存，总是把<b>大小与进程所请求的内存空间大小最接近的空闲分区分配给进程</b>，避免了“大材小用”。为了加速寻找，该算法要求将所有的空闲<b>按分区大小递增顺序</b>形成一个空闲区链<br>

将一个进程的<b>逻辑地址空间</b>分成若干个大小相等的<b>片</b>，称为<b>页</b>

将<b>物理内存空间</b>分成与页大小相同的若干个存储块，称为<b>页框</b>或页帧

在为进程分配内存时，以<b>页框为单位</b>将进程中的若干页分别<b>装入可以不相邻的页框中</b>

<b>进程的最后一页一般装不满一个页框，是一种内部碎片</b>

<b>页表是系统为进程建立的数据结构，页表的作用是实现从页号到页框号的映射</b>

存放页所在的页框号

标识页是否在内存中

用于<b>记录页最近被访问的情况</b>。

标识页最近是否被修改过

标识页的访问权限

多道程序度太高，使运行进程的大部分时间都用于进行页的换入换出，而几乎不能完成任何有效工作的状态称为抖动

引起抖动的原因是系统中的进程数量太多，每个进程能分配到的页框太少，以至于进程运行过程中频繁请求调页

采取局部置换侧率。仅在进程自己的内存空间范围内换页

在CPU调度程序中引入工作集算法

挂起若干进程，腾出进程占用的空间

键盘鼠标

打印机

磁带机、磁盘机、光盘机

数据的存取以数据块为单位

如磁盘

传送字节流

如打印机、鼠标

必须作为临界资源互斥访问的设备

如打印机

允许多个进程共同访问的设备，如磁盘

但同一时刻，只能有一个进程对磁盘进行读写

通过某种技术将一台物理设备虚拟成若干台逻辑设备

数据线、控制线和地址线

设备与设备控制器的接口中的3类信号为数据、状态和控制信号

包括指令译码器和地址译码器，将CPU的命令和地址分别译码，控制指定设备进行IO操作

空缓冲区区R

已装满数据的缓冲区G

现行工作缓冲区C

Nextg

Nexti

Current

空缓冲区、装满输入数据的缓冲区和装满输出数据的缓冲区

空缓冲区队列、输入队列、输出队列

收容输入数据的缓冲区。收容完输入数据后，缓冲区被插入到输入队列中

提取输入数据的缓冲区、存在于输入队列中，进程需要输入数据时，先从输入队列中获取这些缓冲区

收容输出队列的缓冲区。收容完输出数据后，缓冲区被插入到输出队列中

提取输出数据的缓冲区。存在于输出队列中，进程需要输出数据时，先从输出队列中获取这种缓冲区。

系统为每个设备建立一张设备控制表

系统为每个控制器设置一张用于记录该设备控制器信息的控制器控制表

在一些主机系统中还有通道设备，系统会为每个通道设备设置一张通道控制表

记录了系统中全部设备的情况。每个设备占一个表目

缺点是得不到充分利用且容易引起死锁

可同时分配给多个进程使用。

一台设备采用虚拟技术后变为多台逻辑上的设备

把磁臂（磁头）移动到指定磁道上所经历的时间

将指定扇区移动到磁头下面所经历的时间

把数据从磁盘读出或向磁盘写入数据时所经历的时间

将磁盘请求队列分成若干个长度为N的子队列，按FCFS算法依次调度这些子队列，在队列按SCAN算法，对一个队列处理完以后，在处理其他队列

FSCAN算法是NStepSCAN算法的简化。只将磁盘请求队列分成两个子队列