842操作系统

操作系统

1. os概述

• 中断

  • 外中断，也称中断，即从CPU外部发出的中断，包括可屏蔽INTR和不可屏蔽NMI，不可屏蔽中断在关中断状态不受中断标志位的影响，即使关中断也会响应。
  • 内中断，也称异常，从CPU内部发出的中断，都是不可屏蔽的中断，包括
    • 故障：缺页、除数为0、运算溢出
    • 自陷：系统调用
    • 终止：硬件故障如控制器出错、存储器校验错。和外部中断合称硬件中断。

• 处理器运行模式

  • 用户态（目态）——非特权指令
  • 核心态（管态、内核态）——特权指令——管理资源、原语、时钟、中断（硬件完成从用户态到核心态的转换，自动保存断点。os执行中断服务程序、保存PSW、保存中断屏蔽字、通用寄存器的值）

• 系统调用过程

  • 首先要传递系统调用参数，因为之后会进入内核态，用户不能传参。再执行trap指令

• 用户态到核心态由硬件中断完成，核心态到用户态由os程序执行后完成

• 子程序调用与中断处理

  • 子程序调用只需要保存程序断点，即下一条指令的地址
  • 中断处理不仅要保存断点，还要保存PSW内容

• CPU检测到中断信号后，由硬件自动保存断点（PC）和PSW，之后硬件找到中断信号对应的中断向量，中断向量指明中断服务程序的入口地址序，保存中断屏蔽字、保存各通用寄存器值，提供中断服务。其中，中断向量表由os开机初始化。

• 系统调用和中断处理是两个过程，都有图

• 外设和主机之间数据传送通过软件完成（中断服务程序）

• 外设准备数据时间不能小于中断处理时间（写入速度不能比读出速度更快）

• 操作系统初始化时，要创建中断向量表，用于实现中断处理

• 中断请求的产生与当前指令无关，因为中断请求来自CPU外部

• 保护中断现场的时候关中断，执行中断处理程序时开中断

• I/O指令实现的数据传送发生在通用寄存器和I/O端口（暂存信息的寄存器）之间

2. 进程管理

• 进程是除了CPU以外的系统资源的分配单元，线程是处理机的分配单元

• 创建进程就是申请一个空白PCB，并且初始化一些信息

• 线程的实现方式（os只为内核级线程建立TCB）

  • 用户级线程：线程切换不需要转换到内核空间，进程管理由应用程序完成，每次只有一个线程执行
  • 内核级线程：线程切换需要到核心态执行，内核同时调度同一进程的多个线程

• 处理器的三级调度模型

• 进程在临界区时候可以进行处理机调度（王道原题），在内核临界区时不可以

• 带权周转时间是作业周转时间与作业实际运行时间的比值

• 先有资源调度（在队列里给进程排位置），后有进程切换，广义的进程调度包括选择进程和切换进程。

• 上下文切换与模式切换

  • 上下文切换只能发生在内核态（进程切换）
  • 模式切换：用户态和内核态之间的切换。进程运行在用户态，因中断或异常进入内核态，执行后返回原进程。

• 处理机调度算法中

  • 时间片和多级队列肯定是抢占式
  • 短作业优先会饥饿
  • 响应比：（等待时间+要求服务时间）/（要求服务时间）

• 让权等待：进程不能进入临界区时，应立即释放处理器。硬件方法和皮特森方法都不能实现，记录型信号量引入了阻塞，可以实现让权等待。

• 临界区互斥需要满足“忙则等待”、“空闲让进”、“有限等待”，不一定要实现“让权等待”，如皮特森。

• 软件实现互斥方法理解

  • 单标志法：turn=0意为P0可以进入，之后修改为1。如果P0不进入，则P1也不能进。违背“空闲让进”。
  • 双标志法（flag数组2）先检查：定义flag数组，flag[i]为false则Pi未进入。先检查对方未进入，再进入并设置标志。如果同时检查都通过，会同时进入，违背“忙则等待”。
  • 双标志法后检查：先设置标志为true，再检测。如果都设置为true，都进不去。出现“饥饿”现象。
  • 皮特森算法：算法一和三的结合。每个进程设置flag后再设置turn标志，同时检测对方的flag和turn。

• 硬件方法有TestAndSet和Swap

• 整型信号量wait里面是循环，会阻塞。记录型信号量，wait会把进程加到等待队列中，使用block原语阻塞单个进程。signal会唤醒。

• 关中断时，进程不会被中断

• PV问题解题思路

  • 生产者消费者问题

    • 把进程分类，一种进程对应一个函数，函数内中文描述动作
    • 考虑每个动作前P什么，如果P，找出V。缓冲区必须互斥访问。
    • 所有PV写完之后定义信号量
    • 检查多个P连续的时候，是否可能死锁，调整多个P的顺序。

  • 读者写者问题（同类不互斥，异类互斥）

    • 用count计数，同类进程第一个上锁，最后一个解锁
    • 读写公平：读和写再各加一个PV操作，这样写进程就不会一直不被访问，而是按顺序访问。

  • 哲学家问题（只有一类进程）

    • 只有能拿两双筷子才能就餐

  • 理发师问题

    • 当前等待服务顾客数量num，用Lock互斥访问
    • 客户和理发师都有一个信号量

• 死锁与循环等待：死锁的进程互相占有对方需要的资源，循环等待中的进程可以从别的地方获取资源从而打破等待的循环链。

• 死锁预防：破坏死锁的四个条件 死锁避免：银行家算法 死锁检测与解除（分配资源的时候不会做任何事）

  • 破坏互斥：资源共享
  • 破坏不剥夺：得不到满足的话释放所有资源
  • 破坏请求并保持（占有且等待）：预先静态分配法，运行前一次性申请完所有资源
  • 破坏循环等待：顺序资源分配法，进程只能按照编号递增申请资源，不存在申请对方的资源。

• 管程：同一时刻只能由一个进程在执行，进程使用wait阻塞后，管程使用权释放，可以有另一个进程进入管程

• 银行家算法：当系统处于安全状态时，系统中一定没有死锁进程

• 死锁定理：从资源出去的边意思是已经分配的资源

• PCB不包含进程地址空间大小

3. 内存管理

• 链接的时候，把相对地址构成逻辑地址
• 装入的时候，把逻辑地址改为物理地址（地址重定位）
• 高级语言源程序转换为可执行目标文件过程：预处理☞编译☞汇编☞链接
• 进程的内存映像：当程序调入内存运行，就形成了进程的内存映像。包括代码段（只读，多个进程可共享）、数据段、PCB、堆栈
• 进程映像：程序、数据、栈和属性的集合
• 内存保护中，cpu先把逻辑地址和界地址寄存器（逻辑地址最大值）比，再加上基地址寄存器（重定位寄存器物理地址值）的值
• 分段为什么方便进程的只读内存区域共享：若共享40页的代码区，每个进程都要建立40个页表项，而分段的话，每个进程只需要一个段表项（始址+段长）
• 覆盖用于同一个程序或进程，交换用于不同作业进程之间。
• 紧凑技术：内存时不时对进程进行移动和整理，用于克服外部碎片。
• 首次适应算法性能最好，最佳适应算法最容易产生内存碎片
• 连续分配管理和非连续例子：1GB的作业，需要连续的1GB空间，非连续的话，可以分散。
• 分页不会有外部碎片，有很少的内部碎片，分段有外部碎片
• 进程未执行的时候，页表始址和页表长度存放在进程PCB中，进程调度执行时，放入页表寄存器中。
• 地址变换过程由硬件自动完成
• 分级页表：例如1024个页表，每次查页表都需要调入这么多页面，如果分级，只需要调入一级页表，然后调入一个二级页表，总共两个页表，不用浪费空间存储无关页表。
• 段的保护
• 请求分页的地址变换机构图
• 请求分页置换算法
  • OPT：以后最长不被使用
  • LRU：最近最久未使用
  • 改进时钟clock：替换指针：访问位，修改位 0,0 0,1 1,0 1,1
  • FIFO：先进先出
  • 第二次机会算法：FIFO和普通CLOCK算法结合
• 不同进程共享一个段，各自的逻辑段号可能不同
• 计算地址的时候，要注意高位补零

4. 文件管理

• 文件的逻辑结构（理解）
  • 顺序结构：记录定长，读写大批记录时效率高
  • 索引文件：可以根据位序计算地址，有定长和变长（需要索引表）
  • 索引顺序文件：索引+顺序，索引间有序，索引内顺序查找，类似分块排序。eg：字典
  • 直接文件或散列文件：就是通过哈希算物理地址
• 文件分配方式☞非空闲块；文件存储空间管理☞空闲块管理
• 文件物理结构
  • 分配方式
    • 连续分配（数组）
    • 链接分配（链表）：隐式链接（链表，顺序查找）；显式链接（FAT表就是静态链表数组，也显示空闲块）
    • 索引分配：每个文件有个索引块，包括所有盘号。
    • UNIX混合索引分配（重点计算题！）：10个直接地址，一级间址，二级间址，三级间址。
  • 空闲管理
    • 空闲表法（内存动态分配）空闲链表法
    • 位示图
    • 成组链接法UNIX：空闲表+空闲链表法：顺序n个空闲盘块号存在第一个成组链块中，成组链块的最后一个空闲盘块号指的那个块，作为成组链块，保存第二组空闲盘块。
• 目录：FCB的有限集合，一个FCB就是一个文件目录项
• Linux操作系统中，”/dev/hda”就是绝对路径，”./ls”是相对路径，”.”表示当前工作目录
• 建立硬链接（索引结点）和软链接（符号链）的流程图
  • 建立符号链接，引用计数值直接复制，删除操作对符号链接不可见
  • 建立硬链接，引用计数值加1，删除文件在引用计数值减1，值不为0则不能删除文件
• os维护一个包含所有打开文件信息的表（打开文件表）。每个进程的打开文件表存储对文件的使用信息，系统表包含文件相关信息如位置，进程调用open时，在进程打开表中增加条目指向系统表。系统表对每个文件有一个计数器，计数为0，可以删去。
• 文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区有一个独立的文件系统。MBR主引导记录负责引导计算机，确定活动分区，读入引导块。引导块程序负责启动分区中的操作系统。
• Linux系统的FCB 中的文件名和其他管理信息分开，其他信息单独组成一个数据结构，称为索引节点inode，此索引节点在磁盘上的位置由 inode 号标识
• 磁盘格式化
  • 物理格式化：把空白版分成扇区，包括确定扇区校验码。
  • 把操作系统记录在磁盘上，第一步磁盘分成多个柱面，即磁盘分区。
  • 第二步是逻辑格式化（创建文件系统），将文件系统数据结构存储到磁盘上，包括目录、空闲或已分配的
• 可以提高文件访问速度
  • 延迟写：先将数据存入缓冲区，以备不久后访问，减少了访问磁盘次数
  • 提前读、分配连续簇、磁盘高速缓存
• 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是设备驱动程序，因为该功能和设备类型有关，设备驱动程序由厂家提供
• 树形目录解决了多用户之间文件命名问题，不同目录下可以由相同文件名
• open将文件属性从外存复制到内存打开文件表的一个表目中，将表目索引返回给用户

5. I/O管理

• I/O设备：磁盘、打印机、鼠标、键盘、光盘等
• I/O接口（设备控制器）：位于CPU与设备之间，与CPU和设备通信。结构图！
• I/O端口：设备控制器中可以被CPU直接访问的寄存器（数据、状态、控制寄存器）
• I/O控制方式（理解）
  • 直接控制（轮询）和中断驱动方式都是一次一个字，且都经过CPU存入主存。前者CPU发出读命令之后要等待I/O设备准备好，后者发命令之后不需要等待，只需要在指令周期末尾检查中断，若I/O设备发出中断，则接受一个字。
  • DMA在设备和内存间开辟一条数据通路，传输的是数据块，只需要在开始和结束传输前请求CPU。
  • 通道是一个处理机，与DMA区别：DMA需要CPU来控制数据块大小和内存位置，通道方式由通道控制；DMA对应一台设备和内存，通道可以控制多台设备与内存。
  • 通道与一般处理机区别：通道指令类型单一，没有自己的内存，与CPU共享内存。
• DMA传送前由设备驱动程序设置传送参数
• I/O软件的层次记忆（软件☞软件☞程序☞程序）
  • 用户层I/O软件（使用read命令）
  • 设备独立性软件（设备无关性：逻辑设备和物理设备，每个设备都能执行的共有操作）
  • 设备驱动程序（I/O进程与设备控制器之间的通信程序，每个设备接受命令之后行为不同，解析read指令）
  • 中断处理程序（中断当前进程，执行命令）
• 硬盘格式化时，要对硬盘进行分区，创建硬盘分区表。分区完成后，每个分区初始化文件系统，创建文件系统根目录，如果使用UNIX文件系统，还要创建索引结点表。
• 磁盘高速缓存不同于介于CPU与内存之间的小容量存储器，而是指利用内存中的存储空间暂存磁盘中读的信息。
• 高速缓存与缓冲区的区别：（都是内存空间一部分）
  • 高速缓存有的，低速设备必有。缓冲区存放的是低速设备给高速设备的数据，不一定有备份。
  • 如果高速缓存没有，会访问低速设备。但有缓冲区的话，不会直接访问低速设备。
• 缓冲区处理数据时间（处理机C，输出到处理机M，输入到缓冲区T）
  • 单缓冲max(c, t) + m
  • 双缓冲max(c, m) + t
• SPOOLING假脱机技术（理解）
  • 输入输出井（磁盘）、输入输出缓冲区（内存）、输入输出进程
  • 因为向磁盘输出数据速度快于向打印机输出数据，所以当有用户进程请求打印输出，SPOOLING系统同意打印，但不会给进程分配打印机。由假脱机管理进程把打印数据送给缓冲区暂存，送入输出井。对用户进程而言，打印已经完成。
  • 要打印的作业在输出井排队，等到设备空闲，按顺序打印。（SPOOLING就是多了输入井和输出井这两个排队环节）
  • 图（预输入程序、井管理程序、缓输出程序）
• 设备分配方式
  • 静态分配：一次性分配所有设备，不会出现死锁
  • 动态分配
• 磁盘驱动调度算法
  • 扫描算法scan：最后一道；循环扫描：最后一道然后从头开始
  • 电梯算法：最后一个请求