操作系统

问题

• 文件操作的系统调用open/seek/read/write/delete;
• 操作系统怎么把文件逻辑结构转成物理结构的？

一、绪论

• 1、概念、特征和功能

  • 操作系统的4个特征：并行、并发、虚拟、异步。并行和并发是两个最基本的特征，他们互为存在条件；

  • 并行和并发的区别：

    • 并行是指多个事件在同一时刻发生，并发性是指多个两个或事件在同一时间间隔内发生；
    • 操作系统的并发性是通过分时交替执行执行实现的；

  • 操作系统提供3种的接口：

    • 命令接口(联机、脱机(shell))、
    • 程序接口(用户程序中使用系统调用)、
    • GUI(Windows/ios/安卓)

• 2、内核态(管态)与用户态(目态)

  • 设置两种态的原因是：为了保证内核程序不被应用程序破坏
  • OS运行机制：
    • 两种指令：特权指令和非特权指令
    • 两种处理状态：核心态和用户态(本质是两种程序对CPU控制权的切换)
    • 两种程序：内核程序(OS正在控制CPU)和应用程序(控制CPU)
  • 从用户态转向内核态的4种情况：
    • 系统调用命令(trap指令)
    • 发生中断
    • 用户程序中产生了一个错误状态
    • 用户程序企图执行特权指令

• 3、中断、异常

  • 两种中断：
    • 内中断(也称异常或陷入)，中断信号来自CPU内部，和当前执行的指令有关。
    • 外中断(也称为中断)，中断信号来自CPU外部，与当前执行指令有关；
  • 中断的本质作用是，将CPU的控制权交给操作系统；
  • 有中断请求时，先由中断隐指令完成程序的状态保存，主要工作有3个
    • 关中断
    • 保存PC、PSW
    • 根据中断向量找到对应的中断程序，通用寄存器由中断程序完成，中断程序运行结束后再关中断；
  • 中断处理与(OS)子程序调用的区别？
    • 中断程序入口地址：
      • 中断：通过中断向量得到，
      • 子程序调用：由调用程序根据寻址方式得到；
    • 保存环境：
      • 中断：保存PC(记录当前执行的指令，也是寄存器)、PSW、通用寄存器。Program Status Words是程序状态字(也叫程序状态寄存器)，用于OS在系统态和用户态之间的转换。
      • 子程序调用：保存PC、通用寄存器
    • 进程状态：
      • 中断：从用户态转换为核心态，
      • 子程序调用：无变化

• 4、系统调用

  • 什么时候需要进行系统调用？
    • 凡是与资源有关的操作都是通过系统调用方式向OS提出请求，由OS代为完成的；
    • 系统调用可分为5种：进程通信、进程控制、内存、文件、设备管理
    • 系统调用可以保证系统的稳定性和安全性；
  • 系统调用的过程
    • 执行陷入(trap)指令(程序主动将CPU控制权还给OS)->传递系统调用参数->执行相应的中断程序->返回用户态

• 5、操作系统引导

  • 开机经过的4个程序：CPU->ROM中的引导程序(BIOS)->磁盘引导程序(找分区表)->主分区引导块的程序->OS初始化程序(在根目录下面)；
  • CPU从一个特定地址开始取指令，执行ROM中的引导程序(扫描主板接入的设备)->
  • 将磁盘的第一块记录读入内存，执行磁盘引导程序检查分区情况->
  • 从主分区(C盘)读入分区引导块的程序(每一个盘都有一个分区引导块)->
  • 在(C盘)根目录下找到OS初始化程序并执行，完成开机动作；
  • 在开机之前磁盘中的文件系统已经做好了：物理格式化->对磁盘进行分区(创建磁盘分区表)->逻辑格式化(每个分区可以有自己的文件系统)->操作系统存入磁盘。每次开机，OS都需要在内存中准备中断向量表以及中断服务程序；

二、进程管理

• 1、进程与线程

  • 进程与线程比较
    • 进程
      • 资源分配：是资源分配和拥有的基本单位
      • 调度：没有线程之前，进程是独立调度和分派的基本单位；x
      • 组成：由程序段、相关数据段、PCB组成
      • 通信：PV(申请、释放)操作、共享存储、消息传递、管道通信；
      • 系统开销：进程切换需要保存当前CPU环境及新进程CPU环境的设置，开销较大
      • 地址空间：进程之间地址空间相互独立；x
    • 线程
      • 资源分配：不拥有资源，可以访问所属进程拥有的资源；
      • 调度：线程是独立调度和分派的基本单位；
      • 组成：共享其隶属的进程映像，仅拥有线程ID、寄存器集合、堆栈；
      • 通信：同一进程各线程直接读写进程数据段，不同进程间的线程通信属于进程间通信；x
      • 系统开销：线程切换只需保存少量寄存器内容，开销很小；
      • 地址空间：同一进程的各线程共享进程的地址空间；x
    • 用户级线程和内核级线程比较
      • 用户级线程：
        • 由应用程序线程库实现。所有的线程管理(创建、切换)工作都有应用程序负责。用户级线程切换在用户态下完成，无需操作系统干预，OS意识不到这种线程存在；
        • 优点：节省线程切换的开销，调度算法可以是进程专用的，用户级线程的实现与操作系统平台无关，线程的管理代码都属于应用程序；
        • 缺点：当一个线程被阻塞，同一进程内的所有线程都会被阻塞。多线程应用不能利用多处理器系统的优点；
      • 内核级线程：
        • 内核级线程的调度和切换等工作都有OS内核负责，切换在内核态下完成，内核根据线程控制块感知线程的存在，只有这种线程才是CPU分配的单位；
        • 优点：内核能够同时调度同一个进程中多个线程并行执行，线程阻塞，内核可以调度其它线程或进程运行；
        • 缺点：同一个进程中，线程切换需要从用户态到内核态，开销较大。这类线程是用户调用操作系统api进行创建的。例如C++的thread就是这类；
      • 用户级线程和协程的比较
        • Java、Ruby等语言都曾经使用过用户线程，最终又都放弃了使用它。Golang等以高并发为卖点又支持了用户线程，使得用户线程的使用率有所回升。
        • 所谓“协程”，就是“互相协作的用户级线程”；
        • 多用户线程到多内核线程的实现（N: M）中，存在两级调度：
          • 用户级线程到内核级线程的调度，由应用程序完成；
          • 内核级线程到CPU的调度，由OS完成；
        • 协程之于Go调度器好比内核线程之于OS调度器，GMP模型，
          • M与一个内核线程进行绑定，P表示逻辑处理器(它维护一个局部Goroutine可运行G队列)，G只有绑定到P上才能被调度；
          • 对M来说，P提供了相关的执行环境，如内存分配状态(mcache)，维护一个局部任务队列(G)；

• 2、进程状态与进程控制

  • 5种状态：创建态、就绪态(其它运行资源都准备好，就差CPU)、运行态、阻塞态(其它资源和CPU都没有)->终止态；
  • 进程创建过程：申请空白PCB，给新进程分配资源，初始化PCB，将进程插入到就绪队列；
  • 进程阻塞和唤醒：
    • 阻塞：等待某个事件发生而阻塞(有请求系统服务、等待新数据到达、无新工作可做等阻塞)，从运行态->阻塞态是进程自己调用阻塞原语block把自己阻塞的；
    • 唤醒：等待的事件发生时唤醒进程，是从阻塞态->就绪态，由完成相关事件的进程调用wakeup原语将阻塞进程唤醒；

• 3、处理机调度

  • 调度从作业提交到完成分为三个层次：作业调度、中级调度、进程调度；
    • 作业调度：创建进程、分配资源
    • 中级调度：本质是从磁盘调入内存中。挂起、激活进程
    • 进程调度：给进程就绪队列分配处理器。作业调度和中级调度感觉就是进程状态的前3种，进程调度就是第4种；
  • 进程调度的优先级：
    • 根据进程创建后其优先级是否可以改变，将进程优先级分为这两种：
      • 静态优先级(会出现饥饿问题)：短作业优先调度算法可以看做是静态优先级，后面不断出现高优先级就会饥饿前面低优先级的进程；
      • 动态优先级；
      • 把静态优先级改造成动态优先级需要三个变量：
        • priority=f(nice,cpuTime,waitTime)
        • 初始值nice(进程初始时都一样)、运行时间(处于cpu执行态时+1)、等待时间(进程处于就绪态时+1)；
        • 高响应比优先就是用这种方式(四则远算构造优先数中用到了乘除)，把等待时间用作分子(2016_46)；
    • 通常系统进程优先级高于用户进程，前台进程优先级高于后台进程，I/O型进程优先级高于计算型进程；
  • 不能进行处理机调度的3种情况：
    • 在处理中断的过程中；
    • 进程在操作系统内核程序临界区中，理论上必须加锁，防止其它并行进程进入；
    • 原子操作(如加锁、解锁、中断现场保护、恢复)中，连中断都要进行屏蔽，更不能进行进程调度与切换了；
    • 上述过程结束后才进行相应的调度与切换；
  • 5种调度算法
    • 先来先服务：从就绪队列中选择最先进入队列的进程。这种方式效率低，有利于长作业不利于短作业，有利于CPU繁忙型不利于I/O繁忙型进程；
    • 短进程优先：从就绪队列中选择一个估计运算时间最短的进程运行，这种方式估计的运行时间可能不准确，对长作业不利，平均等待时间、平均周转时间最少；
    • 高响应比优先：
      • 从就绪队列中选择响应比最高的作业运行，响应比=(等待时间+要求服务时间)/要求服务时间；
      • 综合考虑了作业的等待时间和估计运行时间，有利于长作业，等待时间越长优先级越高；
    • 优先级调度算法：从就绪队列中选择优先级高的运行，有静态优先级和动态优先级；
    • 时间片轮转算法：
      • 先从就绪队列中选择最先进入队列的进程，运行一个时间片后回到就绪队列的末尾排队，然后释放CPU给下一个就绪进程。时间片越短每次进程调度的时间就越小；
      • 影响时间片大小的因素有：响应时间、系统开销时间、进程数量等；
    • 多级反馈队列：
      • 适用于分时系统进程调度，每个队列可以设置不同的调度算法，比如第一个设置分时调度，第二个用短进程优先调度；
      • 设置多个就绪队列，优先级越高的队列设置的时间片越小，进程在执行完高优先级的时间片之后，会按优先级1-n级递减到对应就绪队列。调度过程也用到了先来先服务和时间片轮转算法的有点；
      • 如果多级反馈队列就绪队列只设置一个，就退化成了时间片轮转算法，就绪队列也不能设置太多；
    • 调度的指标
      • CPU利用率：运行时间/总时间。CPU忙的时间所占的比例；
      • I/O设备利用率：I/O设备忙的时间所占的比例；
      • 系统吞吐量：完成作业总道数/花费的总时间。单位时间内CPU完成作业的数量；
      • 系统开销：除了处理作业之外，系统在进程、内存等管理上消耗的时间。多道程序系统开销变大；
      • 周转时间：作业提交->作业完成的时间间隔
      • 平均周转时间：各作业周转时间之和/作业数量，周转时间越小用户满意度越高；
      • 带权周转时间：周转时间/实际执行时间
      • 平均带权周转时间：各作业带权周转时间之和/作业数量
      • 等待时间：作业/进程等待CPU的时间之和，时间越长满意度越低；
      • 响应时间：用户提交请求到首次响应所用时间
      • 总结：带权算出的是比例，其它都是毫秒或秒

• 4、进程同步与互斥

  • 实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循一下4个原则：
    • (1) 空闲让进：临界区空闲时，允许一个请求进程进入临界区；
    • (2) 忙则等待：已有进程进入临界区，其他请求临界区的进程等待，while一直循环检测是否可以进入；
    • (3) 有限等待：对请求访问临界区的进程，应该保证能在有限的时间内进入临界区；
    • (4) 让权等待：当进程不能进入临界区时，应立即释放CPU，防止进程忙等待(P、V操作和管程实现了让权等待)。这个是互斥机制非必须遵循的，皮特森就没遵循这个机制；
    • 管程中的条件变量就类似于PV操作中的信号量，由编译器负责实现各进程互斥的进入管程的过程，P操作=wait，V操作=signal(2018_28)；
    • 在管程出现之前：进程间的同步用信号量机制(P、V)来实现的，来解决信号量易出错的问题。管程是由编程语言支持的进程同步机制。管程可以实现互斥和同步两种操作；
    • 同步机制中：只有信号量的方法实现让权等待。皮特森、swap指令、TestAndSet(TSL硬件实现的原子操作)指令这三个都是忙等；
  • 互斥的四种软件(代码)实现方式
    • 单标志法：
      • p0、p1两个进程访问临界区，用一个整型变量turn标记允许进入临界区的进程，trun=0表示允许p0进程进入临界区；
      • 特点
        • 两个进程必须交替进入临界区，确保进程互斥访问临界区；
        • 违背“空闲让进”原则；
    • 双标志先检查法：
      • 设置一个数组flag[2]，表示进程是否进入临界区，若flag[i]=FALSE，表示Pi进程未进入临界区，值为true表示进程进入临界区；
      • 初始时p0和p1都是FALSE，p0和p1在进入临界区之前先检查对方是否想进入临界区，若对方想进入自己就循环等待；
      • 特点
        • 两个进程不必交替进入，两个进程可能同时进入临界区，无法实现互斥访问；
        • 违背“忙则等待”原则；
    • 双标志后检查法
      • 同样设置flag[2]，采用先设置自己标志后，再检查对方状态标志，若对方标志为TRUE，则进程等待；
      • 特点
        • 确保进程互斥访问临界区；
        • 存在两个进程都进不了临界区的现象；
        • 违背“空闲让进”、“有限等待”原则；
    • 皮特森算法(Peterson)：用上了单标志法、双标志法的思想；
      • 变量turn指示不允许进入临界区的进程编号，turn表示优先让哪个进程进入临界区，类似于“孔融让梨”。每个进程在先设置自己的flag标志后再设置trun标志；
      • 不允许另一个进程进入时，检查另一个进程flag标志和不允许进入标志turn。若对方flag标志位为TRUE且turn显示不允许对方进入临界区，则进程进入临界区；
      • 若对方也想进入，且最后是自己做出了谦让动作，则自己等待；
      • 特点
        • 确保进程互斥访问临界区；
        • 不会出现两个进程都进不了临界区的现象；
        • 不满足“让权等待”原则，暂时不能进入临界区的进程还会占用CPU；
  • 信号量机制
    • pre：信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，wait和signal原语；
    • 整型信号量
      • S表示资源个数，当进程占用资源后S--，使用完之后S++，当进程发现S小于等于0时会不断测试S值是否大于0；
      • 特点：进程处于忙等待状态，未遵循“让权等待”原则；
    • 记录型信号量
      • 结构体semaphore有两个字段，整型value和等待该资源的进程指针。S.value的初始值表示这类资源总数，绝对值表示等待资源而阻塞的进程个数；
      • 特点：记录型信号量遵循“让权等待”原则；
    • 信号量的P、V操作的实质是“加减”操作，P操作是对信号量进行减1操作，然后判断是否等于0就阻塞等待。V操作是加1操作，然后判断是否小于等于0，是就唤醒进程；

• 5、经典同步问题

  • pre：绝大多数PV操作大题都可以用生产者-消费者解决，复杂的问题可以用读者-写者的思路来解决；

  • 生产者-消费者问题

    • 他们俩共享一个初始为空、大小为n的一个缓冲区，只有缓冲区没满时，生产者才能把数据放入缓冲区，否则等待。只有缓冲区不为空时消费者才能取出数据，否则等待。
    • 这是两个不同的“一前一后的问题”(即两个同步问题)，因此需要设置两个同步信号量。
    • 缓冲区是临界资源，各进程也必须互斥访问：
      • mutex=1 标记缓冲区的互斥访问，
      • empty=n 表示空闲缓冲区的数量，
      • full=0 表示缓冲区中产品的数量，
    • 生产一个产品过程：P(empty)、P(mutex)、V(mutex)、V(full)
    • 消耗一个产品过程：P(full)、P(mutex)、V(mutex)、V(empty)
    • 两个P操作顺序不能交换，实现互斥的P操作一定要在实现同步的P操作之后，否则会发生死锁。两个V操作顺序交换不会发生死锁；(见考点9)

  • 读者-写者问题

    • 有读、写两组并发进程，共享一个文件，有如下4个要求
      • 允许两个读进程同时以读操作访问文件；
      • 只允许一个写进程在某一时刻往文件中写信息；
      • 写进程未完成操作之前不允许读、写；
      • 写进程在执行写操作前，应该让已有的读、写进程全部退出占用文件；
    • 写、写互斥，写、读互斥，但读、读不互斥，解决这些问题的核心是设置一个计数器count用来记录当前正在访问共享文件的读进程数量，用count的值来做不同的处理；
    • 设置两个信号量和读进程的数量
      • rw=1 实现对文件的互斥访问，表示当前是否有进程在访问共享文件；
      • mutex=1 用户保证对count变量的互斥访问；
      • w=1 用于实现写优先;
      • count=0 记录当前读进程的数量；

  • 哲学家进餐问题

    • 一个进程需要同时持有多个临界资源的情况，可以参考哲学家问题的思路；拿一只筷子之前就需要考虑另一只筷子的情况，哲学家关键问题在于解决进程死锁；

• 6、死锁

  • 产生死锁必须同时满足以下4个条件：
    • 互斥条件：在一段时间内某资源仅为一个进程占有，此时若其他进程请求该资源，则进程请求进程只能等待；
    • 不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能由获得该资源的进程主动释放；
    • 请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求被阻塞，但对自己获得资源保持不放；
    • 循环等待条件：存在一种进程资源的循环等待链，链中的每个进程已获得资源同时被链中下一个进程请求资源；
  • 预防死锁：破坏死锁产生的四个必要条件中的一个或几个；
  • 避免死锁：用某种方法防止系统进入不安全的状态，例如银行家算法；
  • 死锁检测和解除：允许死锁发生，不过OS会负责检测死锁的发生，然后采取某种措施解除死锁；
  • 系统安全状态：
    • 安全状态：指系统能够按照某种顺序，为每个进程分配其所需要的资源，使每个进程都可顺序地完成工作；
    • 不安全状态：不是所有的不安全状态都是死锁状态，是系统进入不安全状态后，便有可能进入死锁状态。反之，系统只要处于安全状态就不会产生死锁；
  • 银行家算法
    • 银行家算法的数据结构
      • 可利用资源矢量 Available：含有m个元素的一维数组，每个元素代表一类可用资源数目，Available = (2,2,1)；
      • 最大需求矩阵 Max：表示各进程对资源最大需求数量，Max[i,j]=K，表示进程i需要Rj类资源的数目为K；
      • 分配矩阵 Allocation：Allocation[i,j]=K，表示进程i当前已分得Rj类资源的数目为K；
      • 需求矩阵 Need：Need[i,j]=K，表示进程i还需要Rj类资源的数目为K；
      • Max - Allocation = Need，用长度为m的一维数组Request表示进程此次申请的各种资源数量 Request = (2,1,1)；
    • 银行家算法步骤
      • ①检查此次申请是否超过了之前声明的最大需求数(需确角保Need[i]≥Request)
      • ②检查此时系统剩余的可用资源是否还能满足这次请求 (需确保Available≥Request)
      • ③试探着分配，更改各数据结构(Available-= Requesti; Allocation[i] += Requesti; Need=Max-Allocation)
      • ④用安全性算法检查此次分配是否会导致系统进入不安全全状态
    • 安全性算法步骤
      • 检查当前的剩余何用资源是否能满足某个进程的最大需习求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
      • 不断重复上述过程，看最终是否能让所有进程都加入安全全序列。
    • 银行家算法不能判断系统是否处于死锁状态，只能判断是否是否处于安全状态，不安全状态也可能会回到安全状态，所以不安全状态并不能说处于死锁了；

• PV做题方法总结

  • 做题方法
    • 先找到本题的类型
      • 生产者消费者
        • 对缓冲区的互斥mutex
        • 产品及空间的同步full、empty
      • 读者写着
        • 读者互斥read、write
        • 读操作计数int count
      • 叫号问题
        • 对取号机的互斥mutex
        • 客户、服务员同步costumer、server
        • 号码int number
      • 基本同步问题：只需要同步信号量，不存在互斥量。例如 a=0|1表示某个操作是否执行；
      • 哲学家
        • 筷子互斥数组chopsticks[n]
        • 需要对哲学家进行限制
    • 确定信号量
      • 同步信号线
      • 互斥信号量
    • 套对应类型的模板：2022_46题，process T1(){执行A;V(a)},process T2(){执行B;P(a)}
    • 检查是否满足题目要求、修改

三、内存管理

• 进程角度的内存：运行时由装入程序把一部分程序装入内存运行->缺代码或数据时->由OS的调页机制将页面调入内存给进程使用；
• OS角度的内存：选择一种内存分配方式(连续or非连续分配)->设置逻辑地址与物理地址转换规则(页、叶匡、快表、块)->设置给进程分配页面的策略->设置缺页中断时页面置换的算法；
• 1、内存管理的概念
  • 程序运行的基本过程
    • 编译：由编译程序将源代码编译成若干个目标模块，每个模块有各自的逻辑地址空间；
    • 链接：由链接程序将上述目标模块，以及需要的函数库链接，形成具有完整逻辑地址空间的装入模块；
    • 装入：由装入程序将“装入模块”装入内存，逻辑地址；
    • 在虚拟内存管理中，地址变换机构在链接阶段将各个模块各自的地址链接成完整的逻辑地址，在装载阶段将逻辑地址变换成物理地址；
    • 在程序运行过程中，在指令寻址和数据寻址时，CPU不断的进行逻辑地址到物理地址的转换。页表、快表就是地址变换机构；
• 2、连续分配管理方式
  • 连续分配方式
    • 单一连续分配：
      • 分为系统区(OS使用,在低地址)和用户区(除系统外的内存地址)，
      • 碎片：有内部碎片，
      • 作业道数：只能运行1道作业，
      • 空间不足时：“覆盖”之前的数据。
      • 硬件：界地址寄存器、越界检查机构；
    • 固定连续分配：
      • 将内存用户区划分成若干个固定大小的区域，每个区域只装入一道作业。当有空闲分区时，就可以从外存的作业队列中选择一个合适大小的作业装入该分区；
      • 碎片：有内部碎片，
      • 作业道数：根据用户空间划分为N块，能运行小于等于N个进程；
      • 空间不足时：覆盖、交换(换到外存)
      • 硬件：上下界寄存器、越界检查机构、基地址寄存器、长度寄存器、动态地址装换机构；
    • 动态分区分配
      • 不预先将内存划分，在进程装入内存时，根据进程的大小动态的建立分区，使分区的大小正好适合进程的需要。因此分区的大小和数目是可变的；
      • 碎片：有外部碎片，
      • 作业道数：能运行进程数量不确定；
      • 空间不足时：交换(换到外存)
      • 动态分区分配算法
        • 4种不同的算法有不同的分配策略，回收所有的算法都是相同的(与相邻的合并就是回收2017_26)；
        • 首次适应算法
          • 空闲分区以地址递增的次序链接。分配内存是从链表首部开始顺序查找，直到找到满足要求大小的第一个空闲分区；
          • 特点：实现方式简单、查找速度快、平均性能最好、碎片多出现在低地址空间；
        • 循环首次适应算法
          • 空闲分区以地址递增的次序链接。分配内存时，从上次查找结束的位置开始继续查找，直到找到满足要求大小的第一个空闲分区；
          • 特点：平均性能比首次适应算法差、碎片多出现在高地址空间；
        • 最佳适应算法
          • 空闲分区以容量递增的次序链接。分配内存是从链表首部开始顺序查找，直到找到满足要求大小的第一个空闲分区。有合适的空间优先分配小的连续块；
          • 特点：需要对分区排序，开销大。形成许多难以利用的小碎片；
        • 最坏(差)适应算法
          • 空闲分区以容量递减的次序链接。分配内存是从链表首部开始顺序查找，直到找到满足要求大小的第一个空闲分区，也就是找出最大的分区；
          • 特点：需要对分区排序，开销大。使系统缺少大的连续空闲地址空间；
        • 这几个动态分配算法里面最容易产生内存碎片的是：最佳适应算法(2019_32)；
• 3、非连续分配管理方式
  • 分页存储管理方式
    • 页、叶框、块
      • 把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位；
      • 每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间；
      • 进程中的块称为“页”，内存中的块称为叶框(页帧)，外存中的块就称为“块”，外存也以同样单位进行划分；
    • 页表、页表寄存器
      • 分页存储管理的逻辑地址结构包括两部分：页号P、页内偏移量W；
      • 系统为每个进程都建立一张页表，用于记录在内存中对应的物理块号，例如：页表项(页号->主存物理块号)
      • 硬件支持：页表寄存器(PTR)，用于存放页表在内存的起始地址F和页表长度M；
    • 逻辑地址与物理地址的转变过程
      • 1、查页表
        • (1)、先将页号P与页表长度M比较，若P>=M，则表示地址越界并中断；
        • (2)、若未越界P小于M，则将页表起始地址与页号和页表项长度的乘积相加，将得到该表项在页表中的位置，从而得到这页的物理块号；然后把他俩的对应关系放入物理地址寄存器缓存起来；
      • 2、根据页表项算出物理地址
        • 将有效地址中的页内偏移量传入物理地址寄存器的块内地址字段中，即可得到要访问的内存物理地址；相当于查页表的缓存；
  • 分段存储管理方式
    • 段表、段表寄存器
      • 分段存储的逻辑地址由两个字段组成：段号S、段内偏移量W。段号字段表示作业最大段数，段内偏移量字段表示最大段长；
      • 系统为每个进程都建立一张逻辑空间与主存空间映射的段表，每一个段表项对应进程的一个段，段表项记录该段在内存中的起始地址和段的长度，例如：段表项(段号->段长->本段在主存的起始地址)；
      • 硬件支持：段表寄存器、用于存放段表起始地址和段表长度TL；
      • 操作系统会维护一张共享段表，共享段表(多count字段)和每个进程自己的段表结构不同。一个程序启动多个进程时，内存中只有一份代码段，他们共享这个程序段；
    • 逻辑地址与物理地址的转变过程
      • 控制寄存器(段表起始地址M、段表最大段号)
      • 逻辑地址(段号、段内偏移量)
      • 第一步：通过当前访问的段号和段表的长度比较判断是否越界
      • 第二步：通过段表起始地址和段号找到对应的段表项(段表中的一行)
      • 第三步：根据段表项信息判断是否有越界异常、段缺失异常、越权异常，没有异常才会进行物理地址计算
      • 1、查段表
        • (1)、先将逻辑地址中的段号S与段表长度TL进行比较，若S>TL，则表示地址越界并中断；
        • (2)、若未越界，则根据段表起始地址和该段的段号，计算出该段表对应段表项的位置，从中读出该段在内存中的起始地址；
      • 2、根据段表项算出物理地址
        • (1)、检查段内地址W是否超过该段的段号SL，若超过即W>SL，则同样发出越界中断信号
        • (2)、若未越界，则将该段的基地址D与段内地址相加，就可以得到要访问的物理地址；
  • 分页存储与分段存储的对比
    • 分页：是从计算机的角度考虑设计的，以提高内存的利用率，提升计算机的性能为目标；分页通过硬件机制实现，逻辑地址是一维机构，会产生内部碎片，页面大小一致；
    • 分段：是从方便用户编程的角度考虑的，以信息保护和共享、动态增长及动态链接等方便的需要；段号和段内偏移量由用户(编译器)提供，逻辑地址是二维机构，会产生外部碎片，段长大小不相等；
  • 段页式管理(不考)
    • 分页和分段存储管理方法结合起来，就是段页式存储管理方式。对内存空间的管理仍然和分页存储管理一样；
    • 在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量。将每段分成若干大小固定的页；
    • 逻辑地址与物理地址的地址变换
      • 系统为每个进程建立一张段表，每个分段有一张页表。段表表项中包括(段号、页表长度、页表起始地址)
      • 进行一次访问实际需要三次访问主存：1、首先通过段表查到页表起始地址，2、然后通过页表找到页框号，3、最后形成物理地址。这里也可以通过快表来加速查找；
    • 在一个进程中，段表只有一个，页表可能有多个。段页式管理的地址空间是二维的；
• 4、虚拟页式存储管理

  • 虚拟存储器的定义和特征

    • 在程序装入时，可以先只装入程序的一部分到内存，其余部分留在外存，就可以启动程序执行。在执行过程中发现所访问的信息不在内存时，由OS将所需的部分调入内存；
    • 另一方面，操作系统也可以将内存中暂时不使用的内容换到外存，这样就好像比实际内存大得多，称为虚拟存储器，基于局部性原理实现；
    • 程序访问的局部性原理使得高速缓冲技术成为可能。高速缓冲技术利用程序访问的局部性原理，把程序中正在使用的部分存放在一个高速的、容量较小的Cache中；
    • 虚拟内存技术，用于实现在内存中保留更多的进程，从而提高系统效率；
    • 虚拟存储器
      • 有三个主要特征：多次性、对唤性、虚拟性；
      • 有三种实现方式：请求分页、请求分段、请求段页式；
      • 虚拟存储器的容量：取决于地址空间的大小，而不是由实际的内存容量决定；

  • 缺页中断机构

    • 在虚拟页式存储中，程序是部分装入的，当需要访问的代码或数据在外存上时，系统就产生缺页中断；进程因缺页产生中断时会阻塞，调页完成后唤醒进程；
    • 如果内存中没有空闲块，则需要淘汰某页。内存有空闲块时，将调入的页装入该块，并修改页表中相应的页表项；
    • 缺页中断与一般中断的区别
      • 在执行指令期间产生和处理中断信号，而不是一条指令执行完后；
      • 一条指令在执行期间，可能产生多次缺页中断；
      • 中断的过程：保存CPU环境->分析中断原因->转入缺页中断处理程序->恢复CPU环境等步骤；
    • 缺页处理过程
      • 发生缺页中断，判断是否有空闲叶匡
        • 有：将对应页从磁盘调入该叶匡(只要调入页，就需要更新页和页号的对应关系)，然后修改页表中的对应状态位；
        • 没有：淘汰页得到空闲叶匡(所以这一步不一定会发生)；

  • 快表

    • 是一个高速缓冲存储器，有并行查找能力，用于存放当前访问的若干页表项；
    • 快表的分页机制的地址变换过程：查找快表->判断页表项是否在快表中的两种情况
      • 页表项在快表中：直接找到物理地址并访问内存数据；
      • 页表项不在快表中：查找页表->判断该页是否在内存中(缺页中断将该页调入内存)->修改快表；

  • 基本分页与请求分页的区别：基本分页是一次加载全部页面，请求分页是先只装入程序的一部分到内存+请求调页机制；

  • 页表机制，在页表项增加了如下4个字段

    • 状态位P：指示该页是否已调入内存，
    • 访问字段A：记录本页在一段时间内被访问的情况。
    • 修改位M：标识该页在调入内存后是否被修改过。
    • 外存地址：用于指出该页在外存上的地址，通常是物理块号；

  • 二级页表

    • 二级页表在原有页表结构上再加上一层页表，用于建立索引，第一级被称为页目录表，第二级被称为页表；
    • 虚拟地址2050 1225H对应的页目录号、页号分别是多少？
      • 这个是16进制，转换成二进制就是，0010 0000 0100 0000 0001 0010 0010 0101(一位对应4个二进制位)
      • 页目录号(10位)、页号(10位)、页内偏移(12位)：0010 0000 01、00 0000 0001、0010 0010 0101，把这些二进制按位数分好后转成16进制就是对应目录号和页号；
      • 做题比较简单就两步，1、把16进制转成二进制，2、按对占用位数把前面转的二进制分好后，再转成二进制即可(2019_31)；

  • 页面置换算法

    • 页置换算法越差、工作集越小、进程数量越多，一般缺页率越高；页面缓冲区是在外存和内容中间的，页面缓冲队列的长度对缺页率没有影响，只影响内外存交换速度(缺页之后的代价)；
    • 1、最佳置换算法：淘汰最长时间不再被使用的页面。可以保证最低的缺页率，这个算法也可以用来评价其他算法；
    • 2、先进先出页面置换(FIFO)算法：优先淘汰最早进入内存的页面。会产生Belady异常(分配物理块数增大产品的页故障)
    • 3、最近最久未使用置换(LRU)算法：淘汰最近最长时间未访问过的页面；
    • 4、时钟(CLOCK)置换算法：增加了有一个使用位标识，将进程全部页面视作一个循环队列，当需要替换一个页面时，从指针位置开始查找使用位为0的页，0替换1不替换；
    • 改进型的时钟(CLOCK)置换算法：在使用位的基础上又增加了一个修改位标识，循环扫描时发现使用位=0、修改位=0的用于替换；都不为0时，扫描过程中会重置一些0再扫描，
    • *给进程分配物理块，并有N个页面号的引用，会计算检测缺页中断的情况；

  • 页面分配策略

    • 固定分配+局部置换：OS为每个进程也分配一定数量的物理块，之后都不改变数量，缺页时从该进程在内存的页面选择一个换出，然后再调入需要的页面；
    • 可变分配+全局置换：OS自己保留一个空闲物理块队列(全局)，每个进程也分配一定数量的物理块；
    • 可变分配+局部置换：OS为每个进程也分配一定数量的物理块，如果检测到频繁缺页，则给这个进程再增加一些物理块；

  • 举例：系统采用LRU页面置换算法+局部置换策略，页面置换的情况发生在进程的叶匡数被页面占满之后，比如进程有4个叶匡，需要访问1/2/3/4/3/5这6次页面，访问5页面时根据lru置换算法会用页面1替换页面5（2019_29）；

  • 工作集(驻留集)：进程经常使用的页面放在驻留集中，OS跟踪每个进程的驻留集，当全部进程的驻留集之和大于可用物理块总数时，选择一个进程暂停，将他的页面分配给其它进程；

  • 用高考举例：页置换算法就像复习方法，方法越好复习效率越高、工作集是复习的时长、进程数量是竞争的人数，人数越多竞争越激烈；

  • 抖动现象：

    • 进程在页面置换过程中页面频繁的调入调出就称为抖动，抖动发生时进程在换页上用的时间比进程执行任务的时间多；
    • 发生抖动的原因：置换算法选择不当(这是OS内置的改不了)，或者内存容量不足。解决办法是增大内存容量或者减少进程数量；

  • 在分页系统中，从逻辑地址到物理地址的过程：查页表(内存)->缺页(缺页处理程序->从磁盘调度页面到内存)；

四、文件管理

• 1、文件元数据和索引节点
  • 文件元数据：就是文件属性啊，FCB包括，文件名、文件大小、"硬链接"计数，物理存储位置信息(连续、显or隐链接、索引分配)等等；
  • 采用索引结点的文件系统，物理构成就是索引分配；
  • 索引结点(inode)
    • 不采用索引结点，每个目录项很大，用了索引结点后，每个目录项就只有文件名和索引结点指针了。所有索引结点连续存储(类似数组)在外存的特定区域；
    • 系统中索引结点总数也限制了文件总数的上限，比如索引结点占用4B，则文件数量的上限为2^32，4B只能表示这么大的inode范围(inode存储在外存一块连续内存区域，像数组一样按索引编号)；
    • 计算访问磁盘的次数
      • 未采用索引结点读文件需要：每个目录项64B，磁盘块大小为1KB，则目录下有100个文件需要访问100*64/1024=6.25次磁盘;
      • 采用索引结点读文件需要：每个目录项16B，磁盘块大小为1KB，则目录下有100个文件需要访问100*16/1024=2次磁盘，再加1次索引结点从外存读数据，共3次;
    • 混合索引分配：直接地址(直接块)和间接地址(一级索引地址、二级索引地址)，unix采用混合索引分配；
• 2、文件的操作
  • open系统调用的
    • 需要两个参数：文件名、打开方式(读、读&写)
    • 调用的处理过程
      • 1、根据路径，将各级目录数据读入内存，逐层查找并读入目标文件的FCB；
      • 2、检查打开方式，是否被允许(文件保护)；
      • 3、将文件FCB复制到“系统打开文件表”中，打开计数器加1；
      • 4、在“进程的打开文件表”中增加一个表项，并指向“系统打开文件表”对应的表项；
      • 5、返回文件描述符fd(类似于指针)；
    • 将文件的FCB读入内存后，根据文件系统的物理结构，即可找到文件所有数据块在外存中存放的位置；
    • 多个进程打开同一个文件，只需要在各个进程的“进程打开文件表”中指向“系统打开文件表”，并增加打开次数，每个进程的打开方式可以各不相同；
    • open系统调用，采用索引和不采用索引唯一的区别只有一个，目录项是否有完整的FCB；
  • seek系统调用
    • 需要三个参数：文件描述符fd、读取的字节数量、开始读取的位置(起始指针)
    • 调用的处理过程
      • 1、根据文件描述符fd找到“进程的打开文件表”中对应的表项；
      • 2、根据读写指针的位置，将文件数据从外存读入内存；
  • read系统调用
    • 需要三个参数：文件描述符fd、读取的字节数量、*p
    • 读取数据的过程，先将文件内容读入内核区，再将文件内容复制到用户区；
  • write系统调用
    • 需要三个参数：文件描述符fd、想要写入的字节数量、开始写入的位置(起始指针)；
    • 调用的处理过程：和read过程相反；写入的数据要先从用户区复制到内核区，再写回磁盘；
  • close系统调用
    • 需要三个参数：文件描述符fd
    • 调用的处理过程：
      • 1、根据文件描述符fd找到“进程的打开文件表”中对应的表项，并删除这个表项，
      • 2、“系统打开文件表”打开计数器减1，若为0，则删除“系统打开文件表”中对应的表项；
  • delete系统调用
    • 需要1个参数：路径+文件名
    • 调用的处理过程：
      • 1、根据路径，找到目标文件的FCB；
      • 2、检查删除是否被允许(文件保护)，或者有其它进程打开该文件，则不允许删除；
      • 3、删除目录项，释放分配给文件的磁盘块；
      • 若采用索引结点，删除后还要让索引结点硬链接计数count减1，如果count==0，才会释放分配给文件的磁盘块，并释放索引结点；
• 3、文件的逻辑结构和物理结构
  • 文件的逻辑结构(文件的存储位置信息)
    • 连续分配：
      • FCB中逻辑地址的表示：起始块号、总块号；
      • 支持随机读写，不方便扩展(可以移动位置来扩展文件长度，但总体来说没有索引分配方便)；
      • 在FCB已经读入内存的情况下，访问第i个逻辑块只需要读1次磁盘；
    • 隐式链接：
      • FCB中逻辑地址的表示：起始块号、结束块号；
      • 不支持随机读写(只能顺序访问)，方便扩展(扩展的意思是可以增加文件长度2020_24题)；
      • 在FCB已经读入内存的情况下，访问第i个逻辑块需要读i次磁盘；
    • 显示链接(FAT表)：
      • FCB中逻辑地址的表示：起始块号；
      • 支持随机读写，方便扩展；
      • 在FCB已经读入内存的情况下，访问第i个逻辑块只需要读1次磁盘。通过FCB可知文件第一块的块号，再查FAT表就可以知道第i块存储在哪里；
      • FAT在磁盘的固定位置，开机时读入并常驻内存；
    • 索引分配：
      • FCB中逻辑地址的表示：顶级索引表(一级/二级/多级)，这是混合索引分配，需要关注索引项是哪种类型；
      • 支持随机读写，方便扩展；
      • 在FCB已经读入内存的情况下，访问第i个逻辑块需要读几次磁盘，取决于i块属于哪一级索引
        • 从属直接索引：只需读1次磁盘；
        • 从属一级间接索引：需读2次磁盘；
        • 从属二级间接索引：需读3次磁盘；
        • 从属三级间接索引：需读4次磁盘；
      • 顶级索引表包含在inode中，open系统调用首先读入文件目录项、再读入inode；
  • 文件的物理结构(文件的分配方式)
    • 连续分配：要求每个文件在磁盘上占有一组连续的块，文件的FCB包含第一块的磁盘地址和连续块的数量。反复删文件会产生外部碎片；
    • 隐式链接：将每个文件对应一个磁盘块的链表，磁盘块离散分布，用链表把磁盘块连接起来，文件的FCB包含第一块磁盘的指针和最后一块的指针。消除了外部碎片，但稳定性存在问题；
    • 显示链接：把用于链接文件各物理块的指针显示的存放在一张链表中，每个表项中存放链接指针，文件FCB的物理地址字段中存的第一条链的链首地址对应的盘块号；
    • 索引分配：把每个文件的所以盘块号都放在一起构成索引表。每个文件都有其索引块，这是一个磁盘块地址的数组，数组的第i个位置就是文件的第i块，没有外部碎片；
• 4、文件共享和文件保护
  • 文件共享
    • 硬链接：实现了异名共享，硬链接共享采用索引结点方式，在树形结构的目录中只设置文件名及指向相应索引结点的指针，索引结点中有一个链接计数count，当count>1时文件不能删除；
    • 软连接(符号链接)：只有文件的拥有者才有指向其索引结点的指针，软连接共享只包含一个共享文件路径名的LINK类型的新文件。访问开销大，逐级根据路径名查找文件地址；
  • 文件保护
    • 访问控制信息，存放在FCB中的访问控制信息字段中，四种操作类型(读、写、执行、删除)，三种用户(管理员、文件主、其它人)；
    • 访问控制信息的位数 = 角色数量 * 文件的操作类型；
• 5、目录结构和操作
  • FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
  • 目录结构类型
    • 树形目录结构：树形目录结构能便于实现文件分类，但不便于实现文件共享；
    • 无环图目录结构：无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂；
  • 目录的实现
    • 目录的实现就是为了查找文件，线性列表实现对应线性查找，哈希表的实现对应散列查找。
• 6、磁盘的组织与管理
  • 一次磁盘读写操作的时间=寻找(寻道)时间+延迟时间(+传输时间)；
  • 磁盘寻找时间由磁盘调度算法决定
    • 先来先服务算法(FCFS)：根据进程请求访问磁盘的先后顺序进行调度；
    • 最短寻找时间优先算法(SSTF)：每次寻找的时间最短，选择调度处理当前磁头所在磁道距离最近的数据，会出现饥饿现象；
    • 扫描(电梯)算法(SCAN)：对最近扫描过的区域不公平，磁头当前移动方向只会顺序往前走；
    • 循环扫描算法(C-SCAN)：在SCAN之上增加了，返回时快速移动至起始端的功能；
  • 传输时间和延迟时间：都由磁盘转速决定；
  • 空闲磁盘块的管理：unix采用的是成组链接法（超级块）。位图、空闲磁盘块链、文件分配表(FAT)用标记位还兼职干者空闲磁盘块的管理；
• 问题汇总
  • 磁盘有300个盘片、每个磁道有200个扇区，每个柱面有10个磁道，文件系统的每个簇(簇是文件系统层面的容量单位)包含2个扇区，计算磁盘的容量大小。(300 200 10)/2 = 30万个簇。1个磁盘块就是1个扇区，通常一个扇区大小是512字节，也有1KB、2KB、4KB等；
  • 磁盘的物理结构包括:盘片->磁道(等于柱面)->扇区
    • 盘片：是由铝合金材料制成，表面覆盖着磁性材料。每个盘片被分成许多扇形的区域，盘片被划分成多个磁道，这些磁道按照固定大小的存储空间被划分成扇区。每个扇区通常为512字节，是磁盘进行物理读写的最小单位，理解成扇区就是用以存储数据的。
    • 磁头：位于盘面上方和下方，负责读取和写入数据。每个盘面都有两个磁头，分别位于正面和背面。
    • 悬臂：起到支撑和定位磁头的作用。
    • 柱面(等于柱面)：以盘片中心为圆心，用不同的半径，划分出不同的很窄的圆环形区域，称为磁道。上下一串盘片中，相同半径的磁道所组成的一个圆柱型的环壁，就称为柱面。
  • 簇/块：
    • 是操作系统层面限制的存储空间分配的基本单位，簇是windows的说法，块是unix的说法；
    • 例如以2kb作为簇/块的大小，在创建文件时以簇/块为单位划分，就算一个文件只有1B，也会占用2kb的大小；
  • 可以提高文件访问速度：提前读(把相邻的文件块一起读入内存)、延迟写(连续写和读最新)、为文件分配连续的簇/块、采用磁盘高速缓存

五、I/O管理

• 1、1/O控制方式：轮询方式、中断方式、DMA方式；
  • DMA方式的流程
    • CPU进行DMA控制器的初始化并启动I/O设备。CPU告诉DMA控制器从哪个地方存取 数据，存取多少，DMA控制器通过设备接口从设备中存取数据，然后放到指定的内存缓冲区中；
    • 当需要的数据放到内存缓冲区中后，DMA控制器会发送一个中断信号(2017_32)；
• 2、1/O软件的层次结构
  • 用户层I/O软件
    • 实现与用户交互的接口，用户直接调用与I/O操作有关的库函数，对设备进行操作。用户层软件通过一组系统调用来取得操作系统服务；
  • 设备独立性软件(OS实现)
    • 实现用户程序与设备驱动器的统一接口(设备命令)、设备的保护、设备的分配与释放等；
    • 同时为设备管理和数据传送提供必要的存储空间，功能如下
      • ①执行所有设备的公有操作。
      • ②向用户层(或文件层)提供统一接口。
  • 设备驱动程序(厂商实现)
    • pre：驱动程序中有许多I/O指令；
    • 当系统对设备发出操作指令时，驱动程序驱动I/O设备工作。它是I/O进程与设备控制器之间的通信程序，通常以进程的形式存在。驱动程序与1/O控制方式有关；
    • 接收：向上层用户程序提供一组标准接口，用于接收上层软件发来的抽象I/O要求(如read和 write命令)，转换为具体后发送给设备控制器，驱动I/O设备。
    • 返回：将由设备控制器发来的信号传送给上层软件；
  • 中断处理程序
    • 用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程。
    • 中断处理层的主要任务有：
      • 进行进程上下文的切换、
      • 对处理中断信号源进行测试、
      • 读取设备状态和修改进程状态等；
    • 中断处理过程(也是系统调用的过程，包括硬件和操作系统的处理)
      • 中断程序完成的工作
        • 保存现场和屏蔽字(通用寄存器就是现场的一部分)
        • 开中断
        • 执行中断服务程序
        • 关中断
        • 回复现场和屏蔽字
        • 开中断
        • 中断返回
      • 硬件完成的工作
        • 将CPU模式改为内核态，关中断之前就切换为内核态，开中断切换为内核态，都是硬件完成的
        • 关中断
        • 保存断点(pc)和程序状态(pcw)
        • 中断服务程序寻址
        • 保存被中断程序的中断点也是硬件自动完成的；
  • 硬件设备：引入控制器后，系统可以通过几个简单的参数完成对控制器的操作，而具体的硬件操作由控制器调用相应的设备接口完成，使CPU从设备控制操作中解放出来；
• 3、I/O调度与缓冲区
  • I/O调度的概念：确定I/O请求的执行顺序，是进程之间公平地访问贡献设备，减少I/O的平均等待时间；
  • 单缓冲与双缓冲
    • 单缓冲：
      • 在设备与处理器之间设置一个缓冲区，读、写数据对缓冲区进行操作；
      • OS对每一块数据的处理时间表示为：Max(C,T)+M
        • T: 从磁盘读一块数据到缓冲区的时间为;
        • M: OS将缓冲区的数据传到用户区的时间为;
        • C: CPU处理一块数据的时间为;
    • 双缓冲：
      • 在设备与处理器之间设置两个缓冲区，OS处理每一块数据的时间为：Max(C,T)。T段和M段分别占用两个缓冲区；
• 4、设备分配与回收
  • 设备独立性：为实现设备独立性而引入了逻辑设备和物理设备这两个概念，其实就是设备逻辑表LUT(包括逻辑设备名、物理设备名、驱动程序入口地址)
  • 逻辑设备与物理设备：应用程序使用逻辑设备名来请求使用设备，在系统实际执行时，逻辑设备名通过一张逻辑设备表(LUT)转换成物理设备名；
• 5、SPOOLing(假脱机技术) 技术
  • 由操系统将独占设备改造成共享设备的技术。
  • SPOOLing系统的组成：
    • 输入、输出设备->内存(输入、输出缓冲区+输入输出两个SPO进程)->磁盘(输入井、输出井)；
    • 在磁盘(外存)上开辟两个缓存区（输入井与输出井）；
    • 在内存中开辟的两个缓冲区。

磁盘与文件管理大题汇总

• 磁盘旋转速度每分钟6000转，一毫秒多少转？公式是(t/r)(1/2)，601000/6000=10*1/2=5ms，平均旋转时间就是5毫秒。例题在33题14分钟。

• 簇在文件系统中就等于2块，有些题目中会把块、扇区、簇当成同义词。

• 逻辑地址(簇)转为磁盘物理地址，n*2=磁盘块数，然后乘以1000或取余100算出磁道号和扇区号。

• 文件内容采用链接分配方式，从文件指定编号位置插入内容时，访问磁盘次数存和取各是1次。采用固定长度分配时，是移动次数，前或后的内容移动都可以。

• 启动磁盘的次数，当物理结构是顺序存储时，只需要启动一次就可以把相邻的数据都取到。块内位移指的是从所在块数0的位置到n号记录的编号。

• 每一个的文件分配都在一张全局的FAT中，FAT有多少个表项可以用磁盘大小/磁盘块大小，FAT占用的存储空间用表项总数*每个表项大小。

• 注意目录文件的每个目录项中包含的内容(文件名、文件的第一个簇号)，一个目录有一个目录文件。

• 文件内容的第N(5000)个字节，可以根据簇的大小*簇号得到第N个字节的簇号。

• 文件系统支持的最大长度为可寻址空间，FAT的表项大小可以表示最大寻址空间。

• 文件物理结构中的索引组织方式

  • 512B包括两个部分：直接表示磁盘块的地址、索引地址，各自表示可存储的文件内容大小
  • 索引表结构<6,2>，前6个字节是起始块号(用6个字节表示块号范围)，后2两个字节表示总的块数范围2^16=64kb。这里用6B表示可寻址磁盘范围有点浪费，超过总盘块号了，4B就可以寻址到整个文件系统。
  • 索引地址：算出有多少个索引项，每个索引项指向多大的存储空间
  • 把这两个相加就可以表示文件最大的字节数。
  • 如果把索引表结构改成<4,4>，起始块号和块号都是4B，可以让单个文件达到最大，那可寻址范围就是2^32 * 1kb = 4TB，

• 文件的物理结构

  • 用多级索引组织方式才是最好表示大文件的方式
  • 假设1个盘块大小是4kb，
    • 一次间接地址文件中可存放1k个盘块，那一次间接索引就可以表示4MB的文件大小。
    • 二次间接地址就可以表示4GB大小的文件了。1024^2，三次是1024^3
    • 40kb为什么一定要用一次间接索引？4kb*10个直接索引也可以啊？
    • 注意区分不同文件大小因为索引组织方式不同，访问最后一个磁盘块(扇区)的时间是不同的。
  • C-SCAN调度默认是C-LOOK算法，不用走到顶部，也不用走到0处，直接到需要访问的扇区。ssd硬盘用先来先访问的算法最优，随机访问没有移动磁头的步骤。

内存管理大题

• 页式的表示，页号+偏移
• 段页式的表示，段号+页号+偏移，段号和页号用一个进制表示，前2位是段号。
• 多级页表的表示，页目录号(10位)+页号(10位)+偏移(12位)。可以通过16进制的虚拟地址结构-页面大小判断出=页号的位数。2364H，页面大小4k，那就是16-12=4位。可以看出2就是页号。
• 物理地址转逻辑地址获取页表的层级：TLB(快表)->页表->磁盘(加载不在内存中的页表)，不在快表也会计算访问快表的时间。
• 分页的逻辑地址到物理地址的映射：通过页表，页号+偏移，在页表中找到物理地址后用偏移量找到小组中的编号，相当于在教室中找座位号。
• 加载数据到内容中需要做的事情：先加载该进程对应的页表(通过页号找物理地址)，再将逻辑地址转换为物理地址。
• 虚拟地址转物理地址，(16进制数转二进制后)只需要按照虚拟地址的高位页号在页表中找到物理块号，将虚拟地址的高位替换为物理块号+虚拟地址地位的偏移就是实际的物理地址了，都是二进制表示的(分页地址隐射-案例2)。
• 32个页面可用5个bit表示(2^5可表示0-32)，每页的长度是1kb需要10bit表示(2^10=0-1024)，则用户空间的长度就是15位bit表示。
• 一个16进制数需要用4bit表示，例如0A5C是 000 1010 0100 1100(从地位开始写二进制，最高位可根据用户空间长度省略)。
• 给定逻辑地址和物理地址，可以找叶框号，页表中有页号(逻辑地址)和叶框号(物理地址未加偏移的编号)。给定一个物理地址和物理块大小也可以算相邻的物理地址编号。做题步骤，先确定页号位数(页表项范围0-N)和偏移位数(一般是物理块大小4k为12bit,2^12)，然后将16进制的逻辑地址转为二进制确定页号和偏移数。
• 单级页表在实际使用是不可取的，例如32位的系统页表项就有2^32/2^12=2^204个，每个页表项假如是4k，那页表就有4M大小。64位操作系统页表就有2^524=2^14G这么大。
• 一个进程一个页表
• 一个页面大小是4k，这个页面表示的是教室，在教室里面找人就是在4k大小的范围内找，这个4k就是偏移。
• 4k大小只需要三个16进制表示000-fff就是0-4096，偏移量位大于4096之后，就需要在地址位+1，这是为什么了？
• 16进制的虚拟地址，转成二进制之后，根据页号或目录号占用位数，截取二进制对应的位数，再转成16进制对应的二进制从左到右每四位是一个16进制数。
• 多维数组是用多级页表表示的，一维表示的是页目录号，二维表示页号。可以算数组元素的虚拟地址，例如a[1024][1024]已知起始地址1080 0000H，就可以知道数组中任意一个元素的虚拟地址如，a\[1]\[2]，

PV大题

• 生产者-消费者的同步关系：各自都需要检查和唤醒

  • 生产前先对empty--，小于0就睡眠等待消费者唤醒，生产一个之后就让full++，消费者检查empty<=0就唤醒一个生产者进程。
  • 消费者消费前先对full--，小于0就睡眠等待生产者唤醒，消费一个之后就让empty++，生产者检查full<=0就唤醒一个消费者进程。
  • 因资源而阻塞的就是互斥信号量，不允许两个生产者或两个消费者同时进行操作，mutex--，precess()，mutex++。
  • 同步和互斥中的P()是对信号量减1和检测是否需要堵塞的操作，V()是对信号量加1和检测是否需要唤醒一个相对进程的操作。
  • 同步指的是和对方保持某种互动操作。互斥指的是同时只允许一个操作，避免混乱。
  • 初始化时，empty=BUFFER_SIZE生产过后-- ,full=0生产数量++,mutex=1表示同时只允许1个进程进行操作,

• 多生产-多消费者

  • 两个生产者、两个消费者、缓冲区只能放一个数据，生产者放数据前都先P(empty)，消费者只消费自己的就行V(plate)，V(orange)。
  • 先按单消费者来处理-生产者p(empty)，消费者v(empty)，full没值消费者睡眠，empty没值生产者睡眠，
  • 生产者或消费者执行一个动作之后，想一下什么增加了，什么减少了(同步)。什么我能做别人不能做(互斥)
  • empty只等于1的时候，多个消费者本身就带有互斥行，但是当empty大于1时，同时只允许一个消费者操作empty就需要用上互斥信号量mutex.
  • 上面的这种缓冲区只能为1个的多生产-多消费者，最简单，不需要考虑互斥。

• 读者-写着

  • mysql的读锁和写锁，只允许多个进程同时读，不允许多个同时写。

• 大题汇总

  • 进程调度算法：短作业优先，先来先服务，高响应优先，时间片轮转
  • PV大题：PV的本质就是if和sleep或唤醒。单生产者-消费者的同步关系。多生产-多消费者的同步问题(简单)，需不需要互斥自己判断。
  • 内存管理：段页式内存管理、逻辑地址到物理地址的映射、页表置换算法(最佳置换是看新到来的访问不会访问现有内存中的谁就淘汰谁、LRU、FIFO、CLOCK)。
  • 磁盘与文件：逻辑地址(簇)转为磁盘物理地址有简单取余公式(磁盘块不会累加)、可以用FAT算磁盘总大小、多级索引组织方式才是表示大文件的方式、索引表结构<6,2>
  • 注意，FAT是链接分配，向数组一样的指向，假如100的下一个是106，知道100的编号就不用按顺序查，直接通过100获取106