操作系统

第一章 操作系统概论

wedge

操作系统的概念、特征和功能

• 操作系统的特征包括并发、共享、虚拟和异步。其中并发和共享是两个最基本的特征
• 操作系统为用户提供了用户接口，包括命令接口、程序接口。其中程序接口由一组系统调用命令组成

操作系统运行环境

• 操作系统包括两种状态：核心态（也称管态）和用户态（也称目态）。内核程序只能在内核态运行，应用程序只能在用户态运行。
• 指令中有一部分指令时特权指令，只允许操作系统使用，包括I/O指令、置中断指令、存取用于内存保护的寄存器、送程序状态字寄存器等指令等
• 仿管指令只能在用户态下使用（存疑）

中断与异常

• 中断即外中断，异常即内中断，两者本质上都是中断。中断是来自CPU执行指令外的事件，如某个设备发出的I/O结束中断。异常则是来自CPU内部的中断，也称陷入（trap），如地址越界、虚存缺页等
• 中断发生时，CPU会进入核心态，这是通过硬件实现的
• 中断与子程序调用的区别：

系统调用

• 凡是与资源相关的操作，都必须通过系统调用的方式向操作系统提出服务请求，并由操作系统代为完成。
• 系统调用按功能大致可分为：设备管理、文件管理、进程控制、进程通信、内存管理
• 显然，系统调用运行在核心态

第二章 进程管理

process management

进程与线程

• 进程与线程的比较

• 用户级线程和内核支持线程

进程状态与进程控制

• 进程状态包括：就绪状态、运行状态、阻塞状态、创建状态、结束状态。其中前三种是基本状态
• 进程的创建过程为：申请空白PCB->为新进程分配资源->初始化PCB->如果可能就插入就绪序列。
• 进程终止的过程为：根据被终止进程的标识符，检索PCB，从中读出该进程状态->若该进程在执行，则终止执行，将处理器资源分配给其他资源->若该进程有子进程，则将子进程终止->释放该进程所拥有的全部资源->将该PCB从所在队列移除

处理机调度

• 调度从作业提交到完成可分为作业调度、中级调度和进程调度三个层次
• 如下几种情况时不能进行处理机调度：在处理中断的过程中、进程在操作系统内核程序临界区中、其他需要完全屏蔽中断的原子操作过程中
• 多级反馈队列的思想如下：设置多个就绪队列，优先级越高的队列时间片越小。优先级按1~n递减。一个新进程进入内存后，先放入第一辑队列末尾，按FCFS原则等待调度。当某个进程时间片用完后，若进程执行完则撤离系统，否则进入下一级队列。仅当1~i-1级队列为空时才会执行i级队列，当i级队列前面的队列有新进程进入时，会把正在运行的进程挂到对应队列的末尾，转而把CPU分配给新进程

进程同步与互斥

• 临界资源是指一次仅允许一个进程使用的资源，访问临界资源的那段代码称为临界区
• 实现临界区互斥的软件实现方法包括：
  1. 单标志法：这个方法只能让两个程序交替进入临界区，容易造成资源利用不充分
  2. 双标志先检查法：进程不必交替进入，但两进程可能会同时进入临界区
  3. 双标志后检查法：可以确保两个进程互斥访问临界区，但会存在两个进程都进不了临界区的“饥饿现象”
  4. Peterson算法：确保进程互斥访问临界区，且不会出现饥饿
• PV操作中，S.value的初值表示系统中某类资源的总数。S.value<0表示当前系统中已经没有该类资源，其绝对值表示因等待该资源而阻塞的进程个数

管程

• 管程是由一组数据以及定义在这组数据之上的对这组的数据操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步过程
• 管程由以下三部分组成：局部于管程的共享结构数据说明、对该数据结构进行操作的一组过程、对局部于管程的共享数据设置初始值的语句
• 管程的特性包括：
  1. 局部于管程的数据只能被局部于管程内的过程做访问
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

经典同步问题

• 比较简单，都是送分题，把semaphore拼对就好了

死锁

• 死锁必须满足四个条件：互斥条件、不剥夺、请求和保持、循环等待
• 系统安全状态是指系统能以某种进程推进顺序，为每个进程Pi分配其所需资源，直到满足每个进曾对资源的最大需求，使每个进程可以顺利完成。完成进程的顺序称为安全序列
• 有安全状态一定可以避免死锁。并非所有不安全状态都是死锁状态，而死锁一定是不安全状态。
• 死锁的处理包括：
  1. 预防死锁：破坏死锁产生的四个条件。如采用预先静态分配方法破坏请求和保持条件、采用顺序资源分配法破坏循环等待条件
  2. 死锁避免：在资源的动态分配中防止系统进入不安全状态，以避免发生死锁。代表方法为银行家算法，银行家算法核心是安全性能算法
  3. 死锁检测和解除：系统分配资源时不采取任何措施，而是提供思索检测和解除的手段。死锁检测的方法主要可采用资源分配图进行分析。而死锁解除的方法主要有资源剥夺法、撤销进程法和进程回退法

第三章 内存管理

store management

内存管理概念

• 程序的运行包括如下几步：
  1. 编译：由编译程序将用户源代码编译成成若干个目标模块，每个模块有各自的逻辑地址空间
  2. 链接：由链接程序将上述目标模块，以及所需要的库函数链接，形成具有完整的逻辑地址空间的装入模块
  3. 装入：由装入程序装入模块装入内存
• 程序的链接包括以下三种：
  1. 静态链接：程序运行前，先将各目标模块及他们所需的库函数链接成一个完整的可执行程序，以后不再拆开
  2. 装入时动态链接：将用户程序编译后得到一组目标模块，再装入内存时边装入边链接
  3. 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接，其优点是便于修改和更新，便于对目标模块的共享
• 装入内存有以下三种方式：
  1. 绝对装入：在知道程序将驻留在内存的某个位置的情况下，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。这种方式只用于单道程序环境
  2. 可重定位装入：根据内存的当前情况将装入模块装入到内存的适当位置。装入时对目标程序 中的指令和数据的修改过程称为重定位。因地址变换通常是在装入时一次完成，故又称静态重定位
  3. 动态运行时装入：也称动态重定位，装入程序把装入模块装入程序装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。这种方式需要一个重定位寄存器的支持
• 程序执行时，CPU会不断进行逻辑地址到物理地址的转换，这个过程称为地址重定位
• 为保护操作系统不受用户进程影响，同时保护用户进程不受其他用户进程的影响，可采取如下两种方法进行内存保护：
  1. 在CPU中设置一对上、下限寄存器，用于存放用户作业在主存中的上下限地址。CPU访存时，分别和两个寄存器对比，判断有无越界
  2. 通过采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长寄存器）来实现保护。重定位寄存器包含最小物理地址，界地址寄存器含逻辑地址最大值。如果逻辑地址未超过界地址寄存器的值就代表没有越界，加上重定位寄存器的值后映射成物理地址，再送内存

连续分配管理方式

• 连续分配方式

• 外部碎片可用紧缩解决，但是这需要动态重定位寄存器的支持，且相对费时
• 动态分区分配算法主要包括首次适应算法、循环首次适应算法、最佳适应算法和最差适应算法。其中循环首次适应算法是从上次查找的结束位置开始继续查找。这其中首次适应算法平均性能最好，而最佳适应算法和最差适应算法需要对分区排序

非连续分配方式

• 非连续分配方式允许将一个程序分散地装入到不相邻的内存分区中，它主要包括基本分页存储管理方式、基本分段存储管理方式和段页式管理方式
• 需要注意的是，非连续分配方式还是需要把进程所有信息一次性装入主存，也就是说不会存在块的换入换出的情况

基本分页存储管理方式

• 分页思想是：把主存空间划分为大小相等且固定的块，作为主存的基本单位，每个进程也已块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。这其中，进程中的块称为页，内存中的块称为页框（页帧）。外存也以同样的单位进行划分，称为块
• 分页逻辑地址结构包括页号P和页内偏移量W。系统为每个进程都建立一张页表，记录页面在内存中对应的物理块号。页表一般存放在内存中
• 地址变换由硬件完成，硬件支持由页表寄存器（PTR）完成，它用于存放页表的内存气质地址和页表长度
• 变换过程比较简单，不再赘述
• 由于映射关系的引入，页表的大小也成为了一个问题，倘若只使用一级页表，那么为了表达所有地址空间，这个页表势必就会很大，查找起来需要耗费相当的时间，因此我们引入多级页表的概念。思想是：将页表再进行映射，建立上一级页表，用于存储页表的映射关系。这样页表可以进一步缩小，一般来说，页表的大小应保持在一页以内。当然，实际上由于总页数的增多，实际上页表耗费的空间还是变得更大，但是毕竟查起来还是方便了很多，快了不少

基本分段存储管理方式和段页式管理方式

• 分段思想是：按用户进程中的自然段划分逻辑空间。其他思想和分页差不多：逻辑地址由段号S和段内偏移量W构成；段表由段号、段长和段的起始地址构成。它的硬件支持是段表寄存器，用于存放段表起始地址和段表长度TL
• 段页式管理方式作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每一段分成若干个长度大小固定的页。对空间管理仍然和分页存储管理一样，将其分成若干个页面大小相同的存储块。

分段和分页的比较

虚拟页式存储管理

• 根据局部性原理，可将程序中的一部分装入内存，在运行时再将做需要的部分调入内存。这样操作系统好像提供了一个比实际内存大得多的存储器，称为虚拟存储器
• 虚拟存储器的大小由计算机的地址结构决定，但不能大于内外存的容量和
• 虚拟存储器的实现方式包括：请求分页、请求分段、请求段页式，但不管哪一种都需要硬件支 持
• 硬件支持包括：页表机制、缺页中断机构和地址变换机构
• 当需要访问外存上的代码或数据时，就会产生缺页中断。缺页中断是为了将外存的代码或数据装入内存，它与普通的中断有以下两个明显区别：
  1. 在指令期间产生和处理中断信号，而非一次指令执行完之后
  2. 一条指令在执行期间，可能产生多次缺页中断
• 在地址变换过程中为了加快查找速度，便设置了一个具有并行查找能力的高速缓冲存储器——快表，又称联想存储器(TLB)。它是页表的一个子集，TLB有的内容页表一定有，反之则不然

页面置换算法

• 页面置换算法主要有最佳置换算法(OPT)、先进先出算法(FIFO)、最近最久未使用(LRU)算法、简单CLOCK置换算法（又称最近未用算法，NRU）和改进型CLOCK算法
• OPT算法可以保证最低的缺页率，可以用来评价其他算法。它什么都好，就只有一个缺点：他没法实现
• 只有FIFO才会产生Belady异常
• 简单CLOCk算法只考虑使用位，当某一页被替换时，该指针指向缓冲区的下一帧
• 改进型CLOCK算法考虑使用位和修改位，步骤如下：
  1. 指针从当前位置开始，扫描帧缓冲区，选择遇到的第一个使用位=0，修改位=0的帧用于替换
  2. 如果第1步失败，重新扫描，查找第一个使用位=0，修改位=1的帧用于替换，这一轮扫描中，把所有扫描到的帧的使用位改为0
  3. 如果2步失败，指针指向它最初的位置，再次查找使用位=0，修改位=0的帧
  4. 如果3步失败，指针指向它最初的位置，再次查找使用位=0，修改位=1的帧
• 工作集（驻留集）指某段时间间隔内，进程要访问的页面集合。如工作集大小为n，就往前数n个，把所有碰到的页面都收进来
• 抖动（颠簸）是指频繁的换入换出，通常造成抖动的因素有信息量过大、内存容量不足、置换算法不当。

页面分配策略

1. 固定分配局部置换：为每个进程分配一定数量的物理块，在整个运行期间都不改变。当需要换入换出时，只能从该进程在内存中的页面中选出一个换出
2. 可变分配全局置换：为每个进程分配一定数量的物理块，操作系统自身也保持一个空闲物理块队列，当发现某进程缺页时，系统从物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中
3. 可变分配全局置换：为每个进程分配一定数目的物理块，当发生缺页时，只允许该进程在内存的页面中选出一页换出。如果进程频繁缺页，系统再为该进程分配若干物理块；反之，若该进程缺页率较低，则可适当减少分配给该进程的物理块

第四章 文件管理

file management

文件系统基础

• 文件的所有属性都保存在目录结构中，目录结构一般保存在外存上
• 文件的创建分为两步：先要找到空间，二是在目录中为新文件创造条目
  文件的删除也包括两步：先在目录中找到删除文件的目录项，使之成为空项，二是回收该文件占用的存储空间
• 首次打开文件时，使用系统调用的open，将指明文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开目录文件表的一个表目中，并将该表目的编号返回给用户
• 文件的逻辑结构与存储介质特性无关，但文件的物理结构与存储介质的特性有很大关系

目录结构

• 与文件管理系统和文件集合相关联的是文件目录，它包含有关文件信息，包括属性、位置和所有权等，这些信息主要由操作系统管理
• 为了实现目录管理，引入了文件控制块(FCB)的数据结构。FCB是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
• FCB主要包含如下信息：基本信息、存取控制信息和使用信息
• 文件的访问是从当前目录开始检索的
• 目录结构包括单级目录结构，两级目录结构、多级目录结构（树形目录结构）和无环图目录结构。其中树形目录结构可以方便文件分类，有效进行文件的管理和保护，但不利于文件共享，也会使查询速度变慢。无环图目录结构方便了文件的共享，却使系统管理变得复杂

文件共享和文件保护

• 文件共享包括硬链接和软链接。硬链接是直接指向索引结点，软链接是创建一个包含共享文件路径的LINK类型新文件
• 硬链接实现了异名共享，但是文件的拥有者不能删除与他人共享的文件
  软链接可以让拥有者删除被他人共享的文件，但是其他用户每次打开共享文件都要查找，访问开销大
• 文件保护的方法有口令保护、加密保护和访问控制等。其中口令保护和加密保护是问了防止用户文件被他人存取和窃取，而访问控制则用于控制用户对文件的访问方式
• 口令保护不是很安全，访问控制可通过访问控制列表实现

文件系统实现

• 文件系统一般包括层次结构如下：0.用户接口 1.文件目录系统 2.存取控制模块 3.逻辑文件系统与文件信息缓冲区 4.物理文件系统
• 文件分配方式包括如下几种：
  1. 连续分配：每个文件在磁盘上占有一组连续的块。其文件FCB包含第一块的磁盘地址和连续块的数量。优点包括：实现简单，访问时速度快。缺点有：文件长度不宜动态增加，反复增删文件后会产生外部碎片
  2. 隐式链接分配：每个盘块有一个向后一个盘块的指针，目录包括文件的第一块指针和最后一块指针。优点包括：消除了外部碎片，提高了外存空间的利用率、可动态按需分配磁盘块，对文件的增删改很方便。缺点有：只能顺序访问文件、一旦断链将导致文件数据的丢失
  3. 显式连接分配：给整个磁盘设置一张文件分配表(FAT)，每个表项代表某个盘块，其内容是该盘块的下一盘块号。这张表存放在内存中，故大大提高了检索速度减少了访盘次数
  4. 索引分配：把每个文件的所有盘块号都集中放在一起构成一张索引表。优点是支持直接访问，没有外部碎片。缺点是增加了存储空间的开销

文件存储空间管理

• 文件存储空间管理实质上是对空闲块的组织和管理，它包括如下几种方式：
  1. 空闲表法：建一张系统空闲盘快表，每个表项代表一片空闲盘块区域，其内容包括序号、第一个空闲盘块号和空闲盘块数
  2. 空闲链表法：把所有空闲盘区拉成一条空闲链，要用时从链首摘，释放出新的空闲盘块时往链尾挂
  3. 位示图：利用二进制的一位表示一个盘块是否被使用
  4. 成组链接法：适合大型系统。思想是这样的。有若干个索引块，每个索引块包含指向下一索引块的指针。每个索引块除了该指针外，其它还有若干项，这些表项指向空闲扇区

磁盘组织与管理

• 磁盘由若干个扇面，一个扇面上由若干个磁道，一个磁道上由若干个扇区。磁盘的存储能力受限于最内道的最大密度记录
• 一次磁盘读写操作的时间包括：寻道时间、延迟时间和传输时间。其中延迟时间是指磁头定位到某一磁道扇区所需要的时间，一般取半个自转周期
• 磁盘调度算法包括如下几种：先来先服务(FCFS)、最短寻找时间优先(SSTF)、扫描(SCAN)算法（电梯算法）、循环扫描算法(C-SCAN)。
• 最短寻找时间优先能提供比FCFS更好的性能，但是会产生饥饿现象
• SCAN算法偏向处理接近最里或最外的磁道访问请求，C-SCAN则可以避免这个问题
• SCAN算法和C-SCAN算法扫描时要移动到最远端，它们的变种LOOK和C-LOOK则不需要
• 一个新的磁盘块必须分成扇区以便磁盘控制器能进行读和写操作，这个过程称为低级格式化
  为使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上：第一步将磁盘分区（C盘D盘这种）；第二步对物理分区进行逻辑格式化，将初始的文件系统数据结构存储到磁盘上

第五章 输入输出管理

I/O management

I/O软件的层次结构

• 层次结构从高层到底层为：
  1. 用户层I/O软件：实现与用户交互的接口
  2. 设备独立性软件：实现用户程序与设备驱动器的统一接口、设备命令、设备保护，以及设备分配和释放等，同时为设管理和数据传送提供必要的存储空间。其功能有：执行所有设备的公有操作、向用户层软件提供统一接口
  3. 设备驱动层：实现系统对设备发出的操作指令，驱动I/O设备工作，为I/O内核子系统隐藏设备控制器之间的差异
  4. 中断处理程序：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被中断进程的现场后，返回被中断的进程
     中断处理层的主要工作有：进行进程上下文切换、对处理中断信号员进行测试、读取设备状态和修改进程状态等
  5. 硬件：引入控制器后，系统可以通过几个简单的参数完成对控制器的操作，而具体的硬件操作则由控制器用相应的设备接口完成，使CPU从繁重的设备控制器中解放出来

缓冲区

• 在块设备输入时，假定读入一块到缓冲区的时间为T，将数据从缓冲区传到用户区的时间为M，把CPU的处理时间设为C，则有：
  单缓冲对每一块的处理时间为max(C,T) + M
  双缓冲对每一块的处理时间为max(C + M,T)

设备分配与回收

• 设备分配的安全性是指设备分配中应防止发生进程死锁
• 设备的独立性是指应用程序独立于具体的物理设备
• 为了实现设备独立性，引入了逻辑设备和物理设备两个概念。在应用程序中使用逻辑设备名称来使用某类设备，而系统在实际执行中则使用物理设备名称

SPOOLing技术（假脱机技术）

• 思想主要是把要输出的数据挂到磁盘上，待到设备空闲时则输出
• SPOOLing技术主要特点：将独占设备改造为共享项设备、实现了虚拟设备功能。它的本质是时间换空间

• Previous
  数据结构复习
• Next
  如何在博客中加入音乐