考完就不看の操作系统笔记!

Review

  • 中断:特定事件发生后,先跳去执行中断处理程序,执行结束后返回断点
  • 中断分类:机器断电是机器故障中断;敲键盘是IO中断;printf是访管中断
  • linux中断分上下部
  • unix:层次结构;
  • 用户接口分类:系统功能调用,操作命令接口
  • Windows 启动方式:滚雪球式
  • (第四章开始每章必考)第四章至少两道,一道简单一道难(?)
  • 进程程序的最大区别:有无生命周期
  • 独占资源(互斥)一定有一个mutex信号灯
  • 死锁产生原因:系统资源不足,进程推进顺序非法
  • 写pv题:最后手动拿一个样例跑一炮
  • 移臂调度和电梯算法:同一个方向先做完再管另一个方向
  • 死锁4个必要条件:互斥、不剥夺、占有并等待、有环路
  • 死锁的避免:有序资源分配、银行家算法
  • 考试会挖的坑:\(p155,figure\; 5.9\)弯道问题,\(5.10, 5.14\),银行家算法中加各种奇怪条件(比如加入资源到达时间的限制)
  • 上下界寄存器:针对的是物理地址;基址限长寄存器:针对逻辑地址
  • 缓冲调度重点看第一次有没有命中
  • 页面大小和块大小是一一对应的(一页里,装且只装一个块)
  • 设备无关性:用户使用的设备与物理设备无关(逻辑设备)
  • 缓冲:在两种不同速度的设之间平滑传输信息的技术
  • linux和unix对设备的管理:当作文件
  • 三种文件:普通文件、目录文件、特殊文件(设备文件)
  • 第九章两道或以上答题
  • 文件后缀:标明文件属性
  • 文件的组织结构:逻辑结构、物理结构
  • 文件物理结构:连续(查找快,增加慢)、串联(查找慢,增加快)、索引(二者兼得)
  • systemV索引结构:前十个是一级索引,一个二级索引,一个三级索引
  • 考试10道大题,两道pv,一道自己写一道填空。存储有缓冲区队列题(一定要画图)。文件系统有。考定义的简答题只有一道很简单。
  • 快表。

Cp1.概论

  • 单道程序设计技术:完全串行,无法分别处理不同任务。一个程序阻塞,其他程序也被阻塞。
  • 多道程序设计技术:多个程序之间(宏观上)并行,微观上串行。不同的程序使用不同的“道”,多道之间穿插地运行,一个程序阻塞,可以马上运行其他程序。
  • 多道运行特点:多道、微观并行、宏观串行
  • 分时技术:cpu时间划分为时间片,大家轮流用。
  • 实时处理:对外来信息能在其允许的deadline内做出反应。(反应快速)
  • 操作系统:一个大型的系统,负责软硬件资源分配,控制并发活动,提供用户接口。
  • 操作系统特征:并发、共享、不确定性(可以处理不确定的事件序列)
  • 总览:操作系统资源管理:
    • 管cpu(先给谁用、谁用多久):进程调度,处理机分派
    • 存储器管理(谁的东西该放在哪、占多少):存储分配、存储无关性、存储保护、存储扩充(虚拟存储)
    • 设备管理:设备无关性、设备分配、设备传输控制
    • 文件系统:存取方法、文件共享、安全性、完整性、分配磁盘空间
  • 操作系统分类:
    • 批量操作系统:将程序组织为作业,批量处理。
    • 分时操作系统:使用时间片轮转法。特点:并行性、独占性、交互性
    • 实时系统:可以进行实时处理。特点:可靠性、安全性、及时响应
    • 多处理机系统:并行系统,单机->集群(例如多核cpu)
    • 分布式系统:多个资源部件是分布的,经过通信网络相互作用。系统对资源进行全局的管理。

Cp2.结构

  • 操作系统虚拟机:裸机+操作系统程序
  • 指令系统:
    • 裸机的指令系统只有机器指令;
    • 操作系统虚拟机的指令系统有操作命令(作业控制语言、键盘命令、图形化界面)和系统功能调用
  • 操作系统结构:
    • 单体结构:一整块
    • 模块化结构
    • 可扩展结构
    • 层次结构
  • unix结构:一层一层壳
  • linux:一块块不同的模块
  • windows:不同组件
  • 处理机の特权级:
    • 管态:操作系统管理程序的特权级。可以使用全部指令、全部资源
    • 用户态:用户程序执行时的状态,不能使用特权指令,只允许访问自己的存储区域。
  • 中断:某个事件发生,系统暂停工作处理该事件,处理完毕后又继续回到断点执行。
    • IO中断
    • 外中断:例如命令行Ctrl-C
    • 故障中断:例如电源故障
    • 程序性中断:例如程序溢出、非法操作(0/1)
    • 访管中断:对操作系统提出某种需求发出的中断。
    • 按来源分类:中断(cpu外部中断)&俘获(cpu内部中断)
  • 程序状态字(psw):反映程序执行时机器所处的现行状态的代码。包括指令地址(pc),指令执行情况,cpu状态等。例如x86汇编中,psw包括CS, IP, flag.
  • 响应中断需要的硬件支持:指令计数器(pc),cpu状态寄存器,堆栈,中断矢量表
  • 中断响应的实质:pc,ps入栈,保存现场。

Cp3.用户接口

  • 操作系统的初启动:系统引导:将必要部分装入主存。
  • 引导方式分为:现场独立引导方式(滚雪球,例如Linux),下载方式(从别的机器下载主要文件)
  • 滚雪球步骤:加电/复位,bios启动,启动引导程序,内核初始化。
  • 应用程序的处理:编辑,编译,链接,运行
  • 链接类型:
    • 静态(如果多个不同程序调用同一个库文件,会连接多次):在编译时就把需要的额外代码直接一起放入可执行程序中,在发布时就不再需要依赖库。
    • 动态(只会链接一次):编译时只向可执行文件放入库地址,在运行时才链接
  • 操作系统提供的用户界面:命令接口,程序接口
  • 不同的操作命令:
    • 作业控制语言(JCL):提供系统的作业控制
    • 键盘命令:命令行
    • 图形界面:ui
  • 系统功能调用:通过访管指令和访管中断实现。

Cp4. 进程管理

  • 顺序程序:程序顺序执行。在单道系统中,无法实现并行。结果可再现。具有封闭性(即一旦开始运行,就不受外界影响)
  • 并发程序:可以实现宏观上的并行。一个程序尚未结束,也可以开始执行另一个程序。失去了封闭性和可再现性。
  • 进程和程序的区别:一静一动;进程是独立运行的活动单位;进程是竞争系统资源的基本单位;一个程序可以对应多进程,一个进程至少包含一个程序。
  • 进程的状态:运行;等待(被阻塞);就绪(只待cpu)
  • 大量进程的组织:处于不同的状态的进程们分别属于不同的队列(例如运行队列,等待队列,就绪队列)
  • 进程的组成:程序+数据+PCB
  • 进程控制块(PCB):包含pid,进程当前的状态,next指针(指向当前队列的下一个进程),进程优先级,cpu现场保护区,和别的进程的通信信息,家族关系,占有资源清单。
  • 资源争用:
    • 互斥(临界)资源:同时仅允许一个进程使用。
    • 临界区:指的是某个进程中的一段代码,在该段代码中,该进程对临界变量进行了审查、修改操作。
    • 进程同步:不同进程之间传递消息。
    • 锁:0表示未🔒(可用),1表示已上🔒。
    • 信号灯:一个信号灯由二元组<s, q>组成。s是该灯当前的值,q值为试图获取该灯被阻塞的队列(没p到该信号灯的进程)。在pv操作中,若信号灯值>0,表示可用的资源个数,<0则其绝对值表示等待使用该资源的进程个数。

所谓的[原语],其实指的是原子操作,即该操作不可被分割,不可被中断。

  • 生产者消费者问题:生产者生产资源(执行v操作,资源增加),p空位;消费者p资源,消费资源,取走资源后,v空位。
  • 因此需要两个信号灯,分别表示缓冲区中的空位数目和满位数目。
  • 同时需要设置锁,防止同读同写。
  • 对于多个生产者消费者的情况,上述模板仍然使用(只要没有啥奇奇怪怪的条件XD)
  • 进程通信(IPC):
    • 消息缓冲通信:使用约定的格式收发消息
    • 信箱:嗯这个大概不考8 我不复习了jojo!
  • 线程:共享分给父进程的内存,有自己私有的堆栈和cpu环境。
  • 用户线程&内核线程:在用户空间中调用的线程。无需内核干预。内核线程:完全由os管理
  • fork():为新进程分配pcb,pid,增加与该进程关联的文件表和索引节点(也就是说,父进程已经打开的文件子进程也可继续使用)
  • fork类型程序的打印顺序:考虑父子进程分别先后执行、以及穿插执行的情况。
  • exec():传入可执行文件名,执行该文件。实际上,是把当前进程的执行内容替换为了一个新进程。因此,exec()语句之后的语句不会被执行,执行完exec后直接返回。
  • 等待进程/线程终止:
    • wait(),挂起当前进程,直到任意一个子进程返回。
    • waitpid(pid, status),挂起直到特定的子进程返回。
  • 进程调度&分派:在众多就绪态的进程中,选择一个运行。
  • 调度是把一个新进程插入就绪队列的合适位置;分派是将程序从就绪队列移出并运行。
  • 调度策略:
    • 先来先服务
    • 优先数调度:为每个进程分配优先数,根据该数字大小来决定优先级。
    • 循环轮转调度

Cp5. 资源管理

  • 资源分配策略:资源选择请求者;请求者选择资源。
  • 常用策略:先到先请求;优先调度;移臂调度(电梯);旋转调度(直接找最近)
  • 死锁原因:资源不足,进程推进顺序非法。
  • 产生的必要条件:资源互斥,进程之间不剥夺,部分分配(不会一次申请完),环路条件(存在依赖链)
  • 资源请求矩阵:每一行表示某一个进程需要的各个编号的资源的个数。
  • 资源分配矩阵:每一行表示某一个进程当前占有的各个编号的资源的个数。
  • 预防死锁:
    • 静态分配;
    • 有序分配:为每个资源都编号,分配资源必须升序
    • 银行家算法:进程申报自己对各个资源的最大可能的需求量,系统看当前资源够不够,不够就拒绝。

Cp.6 cpu调度

  • 两级调度:宏观决定那些程序调入os,微观决定当前哪个进程占用cpu。
  • 批处理系统:有两层,以作业为调度单位,在决定了作业的基础上再调度进程
  • 分时操作系统:以进程为调度单位
  • 作业的状态:与进程类似,有提交状态(用户刚刚提交),后备状态(作业录入到后备存储设备),执行状态(调入内存),完成状态。
  • 作业调度使用的数据结构:作业控制块JCB,记录已经进入os的各个作业的状态。
  • 作业周转时间:作业的完成时间-提交时间。包含了排队时间。
  • 平均周转时间:各个作业的周转时间求平均。
  • 带权周转时间:周转时间/实际的运行时间。该值大于等于1。
  • 平均带权周转时间:各个带权周转时间求平均
  • 作业调度算法:先来先服务,短作业优先(总选当前耗时最短的来执行);响应比高者优先(响应比为1+等待时间/运行时间);优先数调度算法
  • 进程调度算法:
    • 循环轮转(RR):时间片q足够大时,等效为先到先服务调度。
  • linux进程调度:动态优先数,且为可抢占式。

Cp.7 主存管理

  • 主存管理的功能:地址映射(逻辑地址->物理地址);为不同用户分配主存;存储保护;扩充虚拟主存。
  • 逻辑结构:
    • 一维地址
    • 二维地址:段地址+偏移
  • 主存空间:物理地址的集合
  • 程序地址空间:逻辑地址的集合
  • 静态地址映射:程序装入主存时,即进行映射
  • 动态地址映射:运行时才映射(例如,通过给逻辑地址加上一个偏移量(段地址),该偏移量存储在重定位寄存器中)
  • 主存分配使用的数据结构:主存资源信息块(M_RIB)
  • 主存分配中涉及的策略:
    • 分配(主存块选请求者);
    • 放置(请求者选主存块);
    • 调入策略(决定信息什么时候装入主存);
    • 淘汰(主存满时,淘汰哪些信息)
  • 虚拟存储器:swap分区。需要提供地址变换机构(用来映射地址)
  • 存储保护:保证各个用户程序只能在给定的区域内活动。
    • 上下界保护:分别用上下界寄存器存储当前程序的上下界,越界会发生中断。
    • 基地址限长保护:使用基址寄存器+限长寄存器保护
  • 存储分区:使用主存资源信息块+分区描述器+空闲区队列来管理,负责分配当前程序使用哪一块主存。
  • 空闲区队列结构:一个链表,首指针是第一块空闲区首地址,之后每一个节点表示一块空闲区,有三个成员:flag(始终为0,表示空闲),分区大小,next指针
  • 放置策略:
    • 首次匹配:尽量选低地址的
    • 最佳匹配:尽量选最接近大小的
    • 最坏匹配:尽量选最大的(与程序大小差距最大的)
  • 碎片拼接:把多个零散的小空闲区拼起来。
  • 页面(虚页):程序地址空间->一个个大小相等的页面/虚页
  • 主存块(实页):主存等分得到。
  • 主存中的实页和程序空间中的虚页具有映射关系。该映射关系通过页面存储。每个程序有自己的页表。
  • 相联存储器(联想存储器):cache;
  • 快表:在cache中存放正在运行的进程使用到的页表,因为很快所以叫做快表。起名鬼才.jpg
  • 使用关联存储器时的映射过程:
    • 获得逻辑地址后,首先提取出页号、偏移
    • 使用页号去联想存储器中查询,如果命中则直接获得物理空间中该页对应的主存块;
    • 未命中时,再去主存中的页表查询。
  • 请求型页式机制:装入一个程序的一部分页面即可运行。
  • 扩充页表:再增设一个中断位(0表示该页在主存),一个辅存地址(表示该页在辅存中的位置)
  • 缺页处理:即查询页表时,发现要查的页中断位=1(不在主存),此时发生缺页中断。此时说明要访问的页不在主存,在辅存中,需要将其调入主存。如果主存有空闲位置,则直接调入,否则需要淘汰当前程序在主存中存在的其他页。
  • 再次扩充页表:增设引用位(表示该页最近是否有被访问过),和改变位(该页是否被修改)
  • 淘汰(置换)算法:
    • 最佳算法:淘汰在最长的时间之后才会用到的页(或者最好永远不会再用到)
    • 先进先出:选择最早进入主存的页(需要记录各个页进入主存的顺序)
    • LRU(最久未使用):就组原里那个,完 全 一 致。软件实现可以使用一个栈,每访问一页,则调整栈中各个页号的次序。

需要注意,页式存储地址仍然是一维的。

  • 段式存储:一个分段是一片连续区域(段大小未必都相等)。
  • 段式地址映射机构:每一项需要记录段号、段长和基址
  • 段页存储:地址是二维的,一个段中有多个页。
  • 段表:每一项存储段号、页表的长度和页表基址。

Cp.8 设备管理

  • 分类:存储设备,io设备,通信设备
  • 设备管理目标:提高利用率,方便用户使用。
  • 统一性:为各种不同设备提供一致的界面
  • 独立性:逻辑设备与物理设备无关
  • 设备管理的功能:状态跟踪,设备分配与回收,设备控制
  • 设备独立性实现:使用高级语言中的软通道实现;批处理系统中联接语句实现;指派命令实现
  • 总之,实现方法就是把一个变量/逻辑结构和实际的设备关联
  • 设备独立性优点:方便用户,提高利用率,提高可扩展性。
  • 管理设备使用的数据结构:设备控制块DCB。
  • 缓冲:用来暂时存放io数据的区域。
  • 引入缓冲的原因:生产、消费者速度有差异;传输数据速度不一致;可以用来实现应用程序的拷贝
  • 进程请求读取键盘输入的过程:
    • 进程从os获得一个空buffer
    • 键盘输入的内容->buffer
    • 用户请求时,os将buffer内容提出,发送到用户进程存储区
    • 若buffer空,进程还在请求,这该进程挂起,等待输入。
  • 进程请求写内容到输出设备:
    • 进程获得空buffer
    • 进程向buffer写入
    • 缓冲区满时,os才将其内容写入输出设备
    • 若缓冲区已满,且进程仍想继续输出,则进程挂起。
  • 常用缓冲:
    • 双缓冲:生产者先向buf1填满内容,然后消费者取buf1的时候,生产者填buf2,如此循环。
  • 设备分配:
    • 独享分配:一个作业执行时独占该设备
    • 共享分配:多个作业、进程共同使用
    • 虚拟分配:在一类物理设备上模拟另一类物理设备,可以把独占设备转换为共享设备。
  • spoooling系统:一种把独占物理设备变成多个虚拟设备的手段,提供外围设备同时联机操作。
    • 例如用户请求使用正在被占用的打印机,spooling系统仍会同意打印请求,然后再输出井中为其创建buffer,并将待打印内容填入其中,排队等待打印(缓输出) -对于输入设备,spooling系统则将其输入内容放入输入井,使其可被多个程序共享。
  • io控制方式:
    • 循环测试io方式
    • io中断方式
    • 通道方式
    • dma方式
  • io子系统:用来实施对设备的控制和操作,通过设备处理程序直接控制设备
  • 控制io核心模块的方式:
    • 为每个设备设置设备处理进程,io请求到来时该进程启动,无请求则睡眠。
    • 把设备作为文件
  • 执行io过程的步骤:
    • 逻辑设备名->物理设备名
    • 检查io合法性
    • 形成io请求块,并将其加入对应的设备请求队列

Cp.9

  • 文件:逻辑上具有完整意义的信息的集合。由信息项和记录组成。
  • 文件系统:负责管理、存取文件的软件机构
  • 功能:实现了按名存取。
  • 特点:使用简单,安全,既共享又保密
  • 文件的结构:
    • 逻辑记录:按照逻辑含义划分的信息单位
    • 物理记录:在存储介质上的存放。
  • 逻辑结构(文件组织):
    • 流式文件:无结构的,按照特殊字符为界或者按照信息个数存取。unix中所有文件都是流式文件。
    • 记录式:结构化的。一个文件有若干记录组成。
      • 定长记录:每个记录长度相等
      • 变长记录:不定长。
  • 存取方式:顺序方式,随机存取
  • 物理结构:
    • 连续文件:连续存储。目录项需要:文件名、文件大小、首地址。连续存取快,不易增删。
    • 串联文件:存在若干分散的块中,每块最末是下一块指针。目录项需要:文件名、首地址。易于增删。
    • 索引文件:仍然分散存储,但是这次建立索引表来指示每一块的地址(类比页表)。目录项只需要文件名和索引表地址。易于增删,可以读写任意记录。索引表中的表项存放逻辑块号和磁盘块号。
  • 多级索引:上一级索引表中不存实际数据的磁盘块地址,而是下一级索引表地址。
  • 文件目录:存放文件名、文件逻辑结构、文件物理结构(上面提到的内容)、权限、文件类型等。
  • 文件目录分类:
    • 一级文件目录:将所有文件都放到一张表。不允许文件同名。
    • 树形文件目录:目录内容可以是另一个目录,或者一个文件。
  • 文件链接🔗:一个文件目录中的文件指针直接指向源文件的目录表项(注意是指向它对应的目录表现,不是指向文件对应的磁盘块)
    • 硬链接:一个文件的多个硬链接共享一个inode号(相当于都是一个文件的不同别名)。删除一个硬链接不影响对应磁盘块中的内容,因为还有别的硬链接指向它。
    • 软链接:是一个另外的文件(inode号与指向的文件不同),只不过是在对其进行操作时,os自动将其路径修改为源文件的路径。
  • unix文件分类:普通文件、目录文件、特殊文件(设备)
  • 第七版unix索引结构:一共8个指针:
    • 小文件全是直接索引
    • 大文件全是一级索引
    • 超大文件最后一个指针是二级索引,其他还都是一级索引。
  • systemv文件索引结构:设磁盘块大小为\(a\),则0~9指针直接指向磁盘块(\(10a\)),10号指针是一级索引(\(256\times a\)),11号是二级索引(\(256^2\times a\)),12号是三级索引(\(256^3\times a\)

要看的0w0

  • 进程状态图(等待、就绪啥的),或者问其中的因果变迁;pv题;银行家算法题目;作业调度算法;