doovvv
0%

操作系统

Posted on Edited on Valine:

Operating System Lecture Notes # Operating-system Structure ## 操作系统结构分类 * 分层法： * 便于调试和验证（+） * 易扩展和维护（+）只要不改变接口，可修改或替换某层 * 合理定义各层比较困难（-） * 效率较差（-）层间通信增加额外开销 * 模块化： * 提高了操作系统设计的正确性、可理解性和可维护性（+） * 增强了操作系统的可适应性（+） * 加速了操作系统开发过程（+） * 模块间的接口规定很难满足对接口的实际需求（-） * 各模块设计者齐头并进，无法找到一个可靠的决定顺序（-） * 宏内核：是指将系统的主要功能模块都作为一个紧密联系的整体运行在核心态
* 微内核：机制与策略分离，C/S模式（客户和服务器之间借助微内核提供的消息传递机制来通信） * 通常包含的功能： * 进程（线程管理） * 低级存储器管理（地址转换->硬件） * 中断和陷入处理 * 可扩展性和灵活性 * 可靠性和安全性 * 可移植性 * 分布式计算 * 开销更大，因为需要频繁的切换用户态和核心态（-） * 外核 ## 两个接口：
* users:
* CLI 通过终端向操作系统发布指令->联机命令接口 * GUI 图形化 * Batch 批处理->脱机命令接口 * apps:
* API -> system call(OS level code -> kernel mode) * trap mechamism -> dual mode(user mode / kernel mode)

dual mode（用一个硬件模式位来表示当前模式位）：

  • user mode：用户级的代码
  • kernel mode：操作系统级的代码

系统调用实现机制：

系统调用：应用程序主动向操作系统发出请求

## Process Concept
## 进程的定义：
* 进程时一个程序的一次执行过程：
* 能完成具体的功能（一系列指令） * 是在某个数据集合上完成的（data，堆栈） * 执行过程是可并发的 * 进程是资源分配、保护和调度的基本单位

  • 程序：被动的，一个包含指令的存在磁盘上的可执行文件
  • 进程：活动的，当程序被加载进内存，就是进程（包含一个PC）

Process in Memory:

回忆在计组课程中写MIPS代码时，就区分了data区和text区
text区域存放指令（read only）
data区域直到程序结束才会回收

并发和并行：

并发Concurrency：多个事件同时发生或存在（单核CPU） 并行：同时运行

Process State：

  • Running运行态：此时进程的代码在CPU上运行（单核CPU系统中只能有一个进程处于运行态，但不一定会有一个进程处于运行态，当所有进程都发生死锁时，所有进程都会处于阻塞态）
  • Ready就绪态：进程具备运行条件，等待分配CPU
  • Waiting等待态(阻塞态）：进程在等待某些事件的发生（比如IO操作结束）

进程切换：


一些例子： 运行态->就绪态：时间片用完，被高优先级进程抢占 运行态->阻塞态：申请临界资源，从磁盘读数据

Process Scheduling

## 中断技术
系统调用时中断的一个特例

中断源：

  • 外中断（中断Interrupt）：
    • 处理器之外的信号
    • 外部中断均是异步中断
  • 内中断（异常Exception）：
    • 处理器内部的信号
    • 硬件异常：掉电，奇偶检验
    • 程序异常：越界，除0
    • 系统调用 ## 中断向量 每个中断源都有对应的处理程序，这个处理程序称为中断服务程序，其入口地址称为中断向量。所有中断的中断服务程序的入口地址构成一个表，称为中断向量表。 ## 指令
      特权指令：只能运行在内核模式下运行的指令 非特权指令：只能运行在用户模式下运行的指令

模式切换：

中断时用户态向核心态转换的唯一途径。由硬件完成。

进程切换：

  • 切换时机：
    • 主动进入等待状态
    • 被动进入就绪状态
  • 切换过程
    • 保存中断进程的上下文信息
    • 保存被中断进程的控制信息
    • 将被中断的进程加入相应的序列
    • 调度一个新的进程并恢复它的上下文信息

进程控制块（状态）PCB

被中断的进程的状态数据存在PCB

进程队列：

只把PCB放入队列，而不是整个进程上下文

进程的通信

高级通信： * 共享存储 * 消息传递 * 管道通信： * 管道是一个固定大小的缓冲区 * 管道为空时，read()操作默认被阻塞

Thread

线程的定义：

线程是CPU利用的基本单元，线程包含一个线程id，PC，寄存器，栈。它和其他属于统一进程的线程共享code，data和其他操作系统资源（它没有自己独立的地址空间）。

多线程模型：

在多处理器系统当中，多核编程机制让应用程序可以让并发的线程分散到不同的处理器运行，以实现并行计算。 * 用户线程ULT：ULT在user mode下运行，它的管理无需内核支持 * 内核线程KLT：KLT在kernel mode下运行，由操作系统支持与管理，只有内核级线程才是处理及分配的单位。操作系统感受不到用户线程的存在

M:1模型：

1：1模型（主流）：

M：M模型：

线程库：为程序员提供创建和管理线程的API

CPU Scheduleing

CPU调度程序

当CPU空闲时，操作系统选择一个在就绪队列的进程执行

抢占调度： * 非抢占调度：一旦进程得到CPU，就会一直用到终止或者等待状态（主动） * 抢占调度：除此之外，都是抢占调度

CPU调度准则

调度算法性能的衡量：

调度算法

先来先服务（FCFS/FIFO）：
* 非抢占式调度算法 * 简单易行（+） * 如果短作业处于长作业的后面将导致周转时间变长（-） * 有利于CPU繁忙型作业，不利于I/O繁忙型作业

时间片轮转(RR)： * 每个进程都可以得到相同的CPU时间，当时间片到达，进程被剥夺CPU并加入就绪队列的尾部 * 抢占式调度算法 * 时间片选取： * 取值太小：进程切换开销显著增大（不能小于进程切换的时间） * 取值太大：响应速度下降（时间片无穷大就退化成先来先服务） * 公平算法（+） * 对长作业带来额外开销（-） * 适合实现人机交互

最短作业优先（SJF）： * 下一次调度总是选择需要CPU时间最短的那个作业 * 饥饿现象：长进程长时间得不到CPU * 预测技术：预测一个进程的CPU时间并非易事 * 优化了响应时间（+） * 难以预测CPU时间（-） * 不公平算法（-）

优先级调度： * 下一次调度总是选择优先级高的调度 * 静态优先级：优先级保持不变，但是可能会出现饥饿现象 * 动态优先级： * 根据进程占用CPU时间：当进程占用CPU时间越长，优先级逐渐降低 * 根据进程等待CPU时间：当进程在就绪队列中的等待时间越长，优先级逐渐升高

多级反馈队列调度算法： * 是时间片轮转调度算法和优先级调度算法的综合与发展 * 算法思想： * 设置多个就绪队列，每个就绪队列的优先级逐渐降低 * 赋予各个队列的进程运行时间片的大小各不相同，优先级越高时间片越小 * 每个队列都采用FCFS * 按照优先级调度。只有第一级队列为空时，才会调度第二级队列 * 终端型用户：短作业优先 * 短批处理用户：周转时间较少 * 长批处理用户：经过前面几个队列

高响应比优先调度： * 同时考虑了等待时间和执行时间 > 没有最好最坏的策略，只有最合适的场景

Synchronization

并发

并发进程/线程之间是交替进行的。

并发进程之间的关系： * 独立关系 * 交互关系：并发进程执行过程中需要共享或交换数据 * 竞争 -> 互斥锁（互斥关系） * 协作 -> 信号量（同步关系）

异步引发的异常

会引发竞争条件：多个进程并发操作于同一个数据导致执行结果依赖于特定的执行顺序

同步

进程同步是一种用于维护共享在交互进程的数据一致性的机制

管程

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程有三部分组成：

  • 局部于管程的共享变量说明
  • 对数据结构进行操作的一组过程
  • 对局部于管程的数据设置初始值的语句。此外，还需为管程赋予一个名字。

管程的引入是为了解决临界区分散所带来的管理和控制问题。

Mutex Locks

临界区问题

并发进程中改变公共数据区域的代码被称作临界区。临界区中不允许有两个进程同时执行。
临界区问题就是设计协议使得进程之间能过协作。

临界区管理规则

  • 有空让进
  • 择一而入
  • 无空等待
  • 有限等待
  • 让权等待

软件解决临界区管理

两个进程的实现代码是不对称的，当进程数量超过两个时，编程变得复杂

互斥锁

锁的基本操作：

原子操作：
原子操作在运行时不能被操作

锁的实现： 使用了原语test_and_set

忙式等待： 占用CPU执行空循环实现等待（自旋锁） * 浪费CPU周期（-） * 进程在等待时没有上下文切换（+）

Semaphores

信号量是一种比互斥锁更强大的同步工具。
信号量是一个整形变量，除了初始化之外，信号量只能被P和V两种原子操作access。

信号量的实现：

  • P操作：信号量<=0则执行忙式等待;否则信号量减1.

  • V操作：将信号量减1.

整数型信号量

记录型信号量

38dfa717356a085b5eff1dcaf4bfe39
## 信号量的使用：
* 二值信号量：二值信号量值只能是0或1，通常初始化为1，用于实现互斥锁的功能（P、V操作都是原子操作）。
* 一般信号量的取值可以是任意值，用于控制并发进程对共享资源的访问。
* P、V操作必须同时出现。
* 信号量--》可用资源数量： * s = 1->竞争 * s > 1->可用资源 * s = 0->用于进程同步

信号量实现同步问题：

同步问题的实质是将异步的并发进程按照某种顺序执行。
解决同步问题的本质就是找到并发进程的交互点。

Deadlocks

定义

处于等待状态的进程所需的资源被另外的处于等待状态的进程占有，这种情况就叫死锁 ## 哲学家用餐死锁问题 解决办法： * 至多允许同时四个哲学家吃 * 奇数号哲学家先取左边筷子，偶数号哲学家先取右边筷子 * 每个哲学家必须拿到两个筷子，否则不拿

饥饿 vs 死锁

饥饿：进程长时间等待
死锁：循环等待资源
死锁=>饥饿（反之不亦然）：

  • 饥饿可能终止
  • 如果无外部干涉，死锁不会终止

产生死锁的必要条件

  • 互斥使用：同一时刻，一个资源仅能被一个进程使用
  • 不可剥夺：进程间不能剥夺彼此的资源
  • 占有和等待（请求并保持）：进程资源得不到满足时，不会释放资源
  • 循环等待：存在一个闭合的进程链，每个进程至少拥有链中下一个进程的一个资源

死锁的解决方案

  • 预防：破坏四个必要条件
    • 破坏互斥条件：通常不可行，并且需要保护互斥条件
    • 破坏不剥夺条件：常用于状态易保存和恢复的资源，如CPU内存资源和寄存器，一般不能用于打印机等资源
    • 破坏请求并保持条件：预先静态分配法，即在运行前就一次申请完它需要的全部资源。
      • 缺点：资源浪费，还可能导致饥饿现象
    • 破坏循环等待条件：顺序资源分配法
      • 缺点：限制了新设备的增加
  • 避免：属于预防策略
    • 系统安全状态：在进行资源分配时，应先计算此次分配的安全性，若此次分配不会导致不安全状态，则允许分配，否则让进程等待。
    • 银行家算法：进程运行前声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量，若没超过再进行系统安全状态的检测。

死锁的检测和接触

  • 死锁检测时机：
    • 当进程等待时检测死锁
    • 定时检测
    • 系统资源利用率下降时检测死锁
  • 死锁的检测：
    • 资源分配图
    • 死锁定理：S死锁的条件是当且仅当S的资源分配图是不可完全简化的
  • 死锁的解除：
    • 资源剥夺法
    • 撤销进程法
    • 进程回退法

Memory Mangement

程序的链接和装入

程序的链接：

  • 静态链接
  • 装入时动态链接：边装入边链接
  • 运行时动态链接：对某些模块的链接，在程序执行中需要该模块才进行链接。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块。

程序的装入：

  • 绝对装入：内存的装入方式只适用于单道程序设计环境。在编译时，编译程序将产生绝对地址的代码。
  • 可重定位装入：程序中的地址都为相对地址，装入程序根据内存情况将装入模块装入到合适位置。在装入时对目标程序中的地址变换是一次完成的，所以又称为静态重定位。
  • 动态运行时装入：不立即把装入模块的相对地址装换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。（适合程序要在内存中变化的程序）

内存管理目标

  • 速度：cache
  • 保护os：防止用户进程去读取os内存空间
  • 保护用户进程（内存保护）：用户进程不能随意访问其他进程的空间
  • 操作正确：地址转换、内存分配、内存回收 ## Main Memory CPU根据PC的值从内存中获取指令。
    指令执行周期：fetch->decoded->execute->memmory->back

保护操作系统和用户进程

用户进程不可访问操作系统的内存数据，以及用户进程之间不能相互影响。
通过硬件实现： * base register * limit register

两个寄存器的值只能由特权指令获得

逻辑地址和物理地址

  • 逻辑地址：面向程序的地址，总是从0开始编址，每一条指令的逻辑地址都是与第一条地址的相对偏移
  • 物理地址：内存单元看到的实际地址，也称为绝对地址

内存管理单元MMU

完成逻辑地址到物理地址（运行时）的转换工作： * 基址寄存器

Contiguous Memory Allocation

单一连续分配

内存分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分，在用户区中，仅有一道用户程序。 ### Fixed-Sized Partition 内存被分成几个固定大小的分区（每个分区的大小可能不同）

  • 许多碎片，造成资源浪费（-）
  • 内存回收：occupied修改为0

Variable Partition

操作系统维护两张表，表明哪部分内存是可用的和哪部分是被占用的 动态存储分配问题：

  • 首次适应：分配首个足够大的孔，不需要遍历整个表，但是最佳适应和最坏适应需要，效率最高，空间利用率较低。
  • 邻接适应：又称循环首次适应，分配内存时从上次查找结束的位置开始继续查找。
  • 最佳适应：分配最小的孔。以容量递增链接。最容易产生碎片（由于每次选用当前大小要求最接近的空闲分区，然而大多数情况下空闲分区都会略大一点，这会导致产生碎片）
  • 最坏适应：分配最大的孔，产生剩余孔，再次利用。空闲分区以容量递减链接，找到的第一个即为最大的。

碎片

很小的内存块，很难被利用 * 内部碎片（进程块内） * 外部碎片（就可变分区而言，孔变得很小时就很难被利用）：
* 紧凑技术： * 静态时地址转换不能使用紧凑技术（编译时） * 开销

Segmenting and Paging

动机

一种应对碎片的方法：允许进程的逻辑地址不连续 ## 分段（基本分段管理方式）

分段：

程序员认为程序是由若干大小不等的段构成的，如各种函数，数据结构，每个段都有专门的用途。这些段就可以存在内存中不连续的位置
### 分段硬件 逻辑地址：段号：段内偏移
段表：段标号：段基址：段限长

分页（基本分页管理方式）

分页：将主存空间划分大小相等且较小的块，作为主存的基本单位，进程也以这个块为单位划分，在运行过程以这个块为单位请求内存。

逻辑地址：页号：页内偏移 ### 分页硬件 ## 分段和分页的区别

Page Table

页面大小

若逻辑地址长度为m bits，页面大小为\(2^n\) Bytes: * 页内位移占n bits * 页号占m-n bits

获取Linux系统页大小的命令： 

1
getconf PAGESIZE
## 页表 操作系统会为每个进程都维护一个页表，该页表的作用是将逻辑地址转为物理地址，它会被CPU调度程序用来定义硬件页表当一个进程被分配到CPU的时候。当然，页表会增加上下文切换的开销。

多级页表

最高级页表项不能超过一页

HARDWARE PAGE TABLE

页表被保存在内存中，而且一个page table base register 指向页表。
切换页表只需要切换这个寄存器，减少了上下文切换的开销。

TLB(hardware)

  • TLB只包含一部分页表项
  • 当CPU生成一个逻辑地址时，它的页号被送到TLB
  • 如果页号被找到，则它的页框号可以马上找到，此时只需要访问一次内存。
  • 如果TLB未命中，则要访问页表，此时需要访问两次内存 ## 基于页的保护和共享 ### 保护 为了防止地址转换出现异常，可在页表条目设置一个“vaild-invaild”比特位，用于表示该项的有效性。
    这个方法可以被扩展以提供更好的保护级别，如“只读”“读写”“可执行”等。
    ### 共享 不同进程共享一样的页框，这个页框只能为pure code（read only） ## 多级页表 为减少页表的大小，采用多级页表的方式 ## 段页式管理 作业的地址空间被分成若干逻辑段，然后将每段分成固定大小的页。
    系统为每个进程建立一张段表，每个分段有一张页表。

逻辑结构地址：

段号+页号+页内偏移地址

Virtual Memory

局部性原理

  • 时间局部性：如果某个信息这次被访问，那它可能在不久的将来被多次访问
  • 空间局部性：如果某个位置的信息被访问，那和它相邻的信息也可能被访问到
  • 分支局部性：顺序指令和非顺序执行的的比例大致为5：1

修改缓存数据

  • write through：修改缓存数据的同时修改内存数据
  • write back：修改缓存数据的时候不修改内存数据，直到该数据要被清除出缓存的时候再修改内存中的数据

部分装入和部分对换

  • 部分装入：进程运行时仅加载部分内存，而不必全部装入，其余部分暂时装入swap space
  • 部分的兑换：可以将进程部分对换出内存，用以腾出内存空间，对换的部分暂时放在swap space swap space时磁盘的一部分
    磁盘带来容量，内存带来速度。

虚拟内存

虚拟内存的一个主要的好处是程序能够比物理内存

虚拟内存技术的实现基于非连续的内存管理

虚拟内存的空间大小

  • 虚存的实际容量 <= 内存容量+外村容量，这是硬件的硬性条件决定的
  • 虚存的最大容量 <= 计算机的地址位数能容纳的最大容量

请求调页管理方式

只需要加载一部分页面到内存中，就可以启动页面。

与基本分页管理方式的区别：所有的页面只有再被请求的时候才加载进入内存，如果一个页面从来不会被访问就不会加载进内存。

内存分配策略：

  • 固定分配局部置换
  • 可变分配全局置换
  • 可变分配局部置换

页面置换算法

FIFO

总是淘汰最先进入内存的页面

  • Belady异常：页帧数增加不一定能减少page fault。

OPTIMAL

总是淘汰最长时间不会使用的页面

  • 无法实现，无法预测未来

LRU

总是淘汰最近最少使用的页面

  • 需要排序，实现起来耗费高

OPT > LRU >FIFO

CLOCK（NRU）

每页设置一个访问位，当某页被创建或被访问时，设置为1。当选择一页淘汰时，若该页为1则修改为0，给予第二次留在内存的机会，若该页为0则淘汰出内存。若循环一次后未找到为0的页则继续循环。即最近未被访问页面被淘汰。

  • 优化后的CLOCK：增加修改位，每次淘汰需要考虑修改位（因为如果某页被修改，需要写回磁盘，增大了I/O负担），优先级小于访问位

系统抖动

请求调页此时，进程的所有页面都在被使用，所以当调页完成后，又会马上发生缺页中断，此时又需要调页。 如果一个进程的执行时间小于进程的调页时间，这个现象就叫抖动。

抖动的原因

  • 并发进程过多->进程页框不够
  • 进程页框分配不合理 ## PFF，缺页故障率 基于这个数据可以实施一个防止抖动的策略：动态调节分配给进程的数量。
    从实际的角度出发：最好的策略为加内存条

Mass Storage

磁盘结构

### 磁盘格式化 * 高级格式化：构建格式化，在磁盘初始化文件系统数据结构 * 低级格式化：为每个扇区使用特殊的数据结构进行填充，包括一个头部，数据区域，尾部。头部可能包含区域编号，尾部可能包含校验码 ### 磁盘性能指标 查找物理块的顺序；柱面号，磁头号，扇区号

\(T_r=\frac{1}{2r}\)，注意顺序访问时只有第一个磁道有旋转延迟时间

磁盘调度

DISK I/O REQUEST

无论什么时候一个进程需要去读写进程，会发出一个系统调用给操作系统，这个系统调用几个信息： * 这个操作是输入还是输出 * 磁盘传输数据的地址【柱面，磁头，扇区】虚拟成LBA * 内存传输数据的地址 * 传输数据的扇区数量 ### DISK SCHEDULING 对于并发进程系统，同一时刻会发出大量的磁盘I/O请求，操作系统会维护一个磁盘队列，当一个请求访问结束，操作系统就会在磁盘队列中选一个请求开始服务
* FCFS：先来先服务 对于SSD来说已经足够 * SSTF：最短寻道时间优先->磁臂粘连现象->饥饿 * SCAN：来回服务请求 * LOOK：不用到终点即可返回 * C-SCAN（循环扫描）：负载均衡，固定方向（直接快速回到起始端，SCAN（电梯调度算法）会偏向于处理那些接近最里或最外的磁道），最实用 * C-LOOK：based on C-SCAN 不用到终点再折返，只要到了最远的一个端点就可以返回了

SSD

固态硬盘的特性

固态硬盘是一种基于闪存技术的存储器，和U盘并无本质差别，只是容量更大，存取性能更好。

磨损均衡

闪存的擦写寿命有限。如果读写数据集中在SSD的一部分闪存，那这部分闪存的寿命会损耗得特别快。

为了弥补SSD得寿命缺陷，引入磨损均衡：

  • 动态磨损均衡。写入数据时，自动选择较新得闪存快
  • 静态磨损均衡：更为先进，SSD检测自动进行数据分配，让老的得闪存块无须承担数据的存储任务，同时让较新的闪存块腾出空间

File System

文件系统

对于大多数用户来说，文件系统是一个最显而易见的操作系统的一部分。
它提供了存储和访问操作系统和用户的数据和程序的机制。
文件系统包含两个部分： * 文件的集合，每个文件包含数据 * 目录（管理和提供关于文件系统所有文件的信息） ## 文件概念 ### 文件定义 在用户看来：文件是具有结构的信息集合
在操作系统看来：文件的本质是存储在外存当中的二进制集合
### 文件属性 文件是“按名存取”的
属性：
* 文件名:按名存取！ * 文件类型->后缀 * 位置 * 大小 * 时间、日期和用户标识 * 保护 ### 文件类型 文件类型可用于指示文件的内部结构，操作系统通过了解文件类型决定如何进行解释。 一般地，操作系统至少要解释两种文件类型： * 文本文件 * 二进制可执行文件 * Windows： .exe * Linux： ./

Unix认为每个文件由字节序列组成，解释这些序列的工作交给具体的应用程序来做。所以对于未知的文件类型，操作系统选择对应的应用程序去出来。

Unix把设备视作特殊文件

文件内部结构

### 访问方法 * 顺序访问：读取/写入当前文件后，将文件指针移向下一个邻接区域 * 直接访问：若文件的逻辑记录的长度固定，那么在访问文件可按任意顺序进行快速读写。（从文件开始位置的LN个L字节） ## 文件目录 目录可以被看作一个翻译文件名成对应entry的符号表。
一种保存文件控制信息的数据结构 作用： 列出所有文件 * 增加文件 * 删除文件 * 更名

目录结构

  • 单层目录结构：所有的文件都保存在同一个目录下
    • 容易实现和理解
    • 命名是个很大的问题
  • 两层目录结构：每个用户有一个自己目录（UFD）
  • 树形结构目录：一个树形结构有一个根目录，在这个系统中的每个文件都有一个独一无二的路径名

文件的操作

  • 创建文件
    • 为新文件分配必要的外存空间
    • 在目录中为其创建一个目录项
  • 读文件：执行系统调用然后在目录中搜索文件，维护一个读指针
  • 写文件：与读文件类似
  • 重新定位文件：将文件位置指针重新定位
  • 删除文件：
    • 搜索文件
    • 释放空间
    • 删除目录项
  • 截断文件：不改变文件属性，但是删除文件内容

文件的打开与关闭

打开：调用open根据文件名搜索目录，将文件的属性复制到内存打开文件表的一个表目中，并将表目的索引返回给用户（文件句柄，文件描述符）

关闭类似

共享与保护

  • User：即所有者（owner）
  • Group：用户集合，拥有相同的权限

文件保护通过口令保护，加密保护和访问控制等方式实现。

口令和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式

文件访问控制

每个文件/目录关联一个访问控制表ACL * 每个文件/目录有三种用户类型：Owner/Group/Other * 三种用户的访问控制权限均有rwx * 每个ACL有九个bit

对于文件的访问控制，由用户访问权限和文件属性共同限制

File-System Implementation

## common file system 当今有许多文件系统被使用，大多数操作系统都支持多种文件系统 ## 文件目录 文件系统通过文件控制块来维护文件结构，FCB包含有关文件的信息，包括所有者，权限，文件内容的位置等

FCB主要包含以下信息：

  • 文件基本信息
  • 存取控制信息
  • 使用信息

文件目录用于组织文件，每个目录项对于一个FCB 文件目录实现的关键：

  • FCB与文件内容的关联方法
  • 在目录种“按名”搜索的效率
    • 线性表
    • 哈希表

UFS（unix file system）：UFS的FCB被称作索引节点inode，每个inode都有唯一的一个编号。UFS的目录条目只包含了文件名和inode编号。创建文件数量上限=索引节点数量上限。
UFS根据文件名在目录中找到相应的inode编号，再根据inode编号找到文件的相关信息。

文件目录结构：

  • 一级目录
  • 二级目录
  • 树形结构：可以从当前目录下开始检索

访问方式

顺序访问

文件信息按顺序排序，读取/写入当前文件信息后，将文件指针移向下一区域

磁带模型

直接访问

若文件的逻辑记录的长度固定，那么允许在访问文件信息时可按任意顺序快速读取和写入

分配方法

连续分配：

每个文件在磁盘上占用连续的物理块 * 简单，地址转换很快（+）随机存取 * 碎片（-） * 文件的增加和修改不方便（-），可能需要移动整个文件才能得到更大的空间

磁带是一种顺序存储设备，用它存储文件时只能采用顺序存储结构。

采用连续分配能够提高访问速度。

链接分配

文件分散在磁盘的不同位置，通过指针将他们链接起来 * 没有碎片（+） * 空间浪费了一部分（-）用了一部分空间存储指针 * 来自断链的风险（-） * 访问文件必须从头顺序访问（-），即不可以随机存取 ### 簇 指一组物理块的集合。如果以簇为分配的单位，可以节省指针占用的空间比例 ### 文件分配表FAT（显示链接） 用一张表来记录文件占用物理块的号的顺序 * 仍然不能完成随机访问
### 索引分配 将文件占用的所有物理块号按逻辑顺序保存在一张索引表中，存有索引表的物理块称为索引块。 * 实现了随机访问（+） * 索引块占用空间（-） * 索引块占用多少空间不确定(-)

空闲空间管理

Bit Map

每一个扇区的空闲情况有一个比特来表示

盘块号 = 起始块号+floor（盘块号/（盘块大小*8））

Linked List

将所有的空闲空间链接起来，在一个特殊的地方存放头指针 ## 文件系统结构 ### layered file system ### virtual file system

四种对象：

  • 超级块对象
  • 索引节点对象
  • 目录项对象
  • 文件对象

I/O System

I/O硬件

  • Mother Board

  • 总线：一组线路和通过线路传输的协议

    • 并行：占的面积较大，并且容易发生干扰
    • 串行：例如PCIe，SATA，USB

  • ports：

    • PCIe
    • SATA
    • USB（Universal Serial Bus）
    • VGA
    • HDMI
    • DVI ### 设备类型

  • 块设备：存取单位为一个block，传输速率高，可寻址，可随机读写

  • 字符设备：存取单位为一个字符，传输速率低，不可寻址，时常采用中断I/O

  • 共享设备：一段时间内允许多个进程同时访问的设备

  • ### 控制器

  • I/O接口：

    de970afca866dea878ad543e12f58c4

    设备控制器的组成部分：

    • 设备控制器与CPU的接口
    • 设备控制器与设备的接口
    • I/O逻辑。设备控制器通过对CPU发送来的指令进行译码来控制设备。

I/O端口

控制器有一个或多个用于数据和控制信号的寄存器。CPU通过直接读写这些寄存器来控制通信。 * 控制寄存器 * 状态寄存器 * 数据寄存器 ### I/O地址 I/O地址：控制寄存器地址 编址方式： * I/O独立编址：为每个端口分配一个端口号，所有I/O端口形成一个端口空间，普通用户不能对其进行访问。使用独立的I/O指令，如IN，OUT * 内存映射编址（统一编址）：划出一块内存地址，将I/O端口的地址映射起来，这样就可以用访问内存指令对控制寄存器进行读写。每个端口被分配唯一的内存地址 内存映射编址：

I/O控制方式

  • 轮询：

    • 缺点：串行工作，极大浪费CPU资源

  • 中断：

  • DMA直接内存访问： ## 内核I/O结构 内核I/O结构包括硬件和软件两个部分，I/O软件的设计目标主要体现在：

  • 高效性

  • 通用性：屏蔽硬件细节，让用户使用统一的接口方便地使用不同硬件

内核I/O结构图： 设备驱动层来提供统一的接口，从而对I/O子系统隐藏了I/O设备的控制器

2ba0fe81d0d2031fac8d7306da71a39
  • 用户从I/O软件
  • 设备独立性软件
    • 在应用程序中使用逻辑设备名请求设备，在系统实际执行时需要把逻辑设备名映射为物理设备名
    • 执行所有设备的公有操作
    • 向用户层提供统一接口
  • 设备驱动程序
  • 中断处理程序

I/O请求周期

简答题

虚拟存储器的特点？

  1. 虚拟扩充，从逻辑上而不是物理上扩充了内存容量
  2. 部分装入，即每个作业并不是一次性全部装入内存
  3. 离散分配，即不必占用连续的地址空间
  4. 缺点：
    1. 缺页中断增加了系统开销
    2. 可能产生抖动
    3. 增加了硬件成本

分时操作系统和实时操作系统的区别？

  • 分时操作系统：一种利用分时技术的联机的多用户交互式的系统，每个用户都可以通过终端向系统发出各种操控命令。分时技术就是把处理机的运行时间分成很小的时间片，按时间片轮流把处理机分配给联机作业使用。
  • 实时操作系统：一种能在特定或确定的时间能完成系统功能以及对内部或外部事件按同步或异步的方式做出响应的系统。

简述多道程序设计技术？

多道程序设计技术是指把多个程序同时存放在内存中并启动交替计算，在宏观上是并行，微观上是串行，轮流占有CPU。

进程和线程的区别

  1. 进程是操作系统进行资源分配的最小单位，线程是CPU调度的最小单位
  2. 线程依赖于进程而存在，一个进程至少拥有一个线程
  3. 进程拥有独立的地址空间，而线程共享所属进程的资源，除了自身运行的必须资源外，线程没有其他资源，所以线程的切换创建等都比进程开销更小。
  4. 进程通信必须用进程间通信的方式，而线程通信比较方便。
  5. 线程崩溃可能导致所属进程都会崩溃，而进程崩溃不影响其他进程。

什么是进程，和程序的区别？

  • 定义：进程是拥有独立功能的程序在一些数据集合上的一次运行过程。是系统进行资源分配和调度的单位。
  • 区别：
    • 进程是一次运行过程，是暂时的，有创建有撤销。程序是永久的。
    • 进程是动态的，程序是静态的。

进程进入临界区的调度原则?

  • 空闲让进：如果临界区空闲则允许一个进程进入。
  • 忙则等待：任何时候，处于临界区内的进程不可多于一个。所以临界区不空闲的时候，外面的进程必须等待
  • 有限等待：等待的时间是有限的。
  • 让权等待：如果进程不能进入临界区，应该让出“CPU”，避免忙等

PCB?

PCB是进程实体的一部分，是操作系统中一个非常重要的记录型数据结构，包含了操作系统用于描述进程情况和控制进程允许所需的全部信息。

内存管理的功能？

  • 内存空间的回收与分配
  • 地址转换
  • 内存共享
  • 存储保护

页式存储管理和段式存储管理的区别？

  1. 页式存储管理的逻辑地址是连续的，而段式可以不连续（段号与段号之间无联系，而页号按顺序增加）
  2. 页式的逻辑地址是一维的，而段式是二维的
  3. 每一页的大小是固定的，而每一段的大小不一定相同

页式：

  • 优点：没有外部碎片，内部碎片不大
  • 缺点：地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。增加了机器成本和系统开销。页与页之间没有了逻辑联系，无法进行共享和保护。

段式：

  • 优点：可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享，包括通过动态链接进行代码共享。
  • 缺点：外部碎片

缓冲技术的目的？

  1. 缓和CPU和I/O之间速度不匹配的问题
  2. 提高CPU和I/O之间的并行性
  3. 解决数据颗粒度不匹配的问题
  4. 减少CPU中断的频率

什么是通道？

通道本质是一个简单的处理器，具有控制输入输出，执行I/O指令的功能，可以通过执行I/O通道程序控制I/O操作。

磁盘访问时间由哪三部分组成？

  1. 寻道时间：磁头移动到指定磁道的时间
  2. 旋转延迟时间：指定扇区旋转到磁头下的时间
  3. 数据传输时间：将从内存传输到磁盘或从磁盘传输到内存的时间

简述中断处理过程

  1. 保护被中断进程的现场，保存被中断进程的PCB
  2. 分析中断原因，执行相应的中断处理程序
  3. 恢复被中断进程的现场，继续执行被中断进程

用户级线程和系统级线程的优缺点

用户级线程：

  • 优点：

    • 线程切换不用切换到内核模式，节省了模式切换的开销

    • 调度算法可以是进程专用的，不同的进程可以按照需要给线程使用不同的调度算法

    • 用户级线程的实现与操作系统的平台无关，由用户程序自己管理线程代码，所以可以运行在任意操作系统上。

  • 缺点：

    • 一个线程被阻塞，该线程所属进程的所有线程都会被阻塞
    • 内核每次分给一个进程的就一个CPU，不能发挥多线程优势

内核级线程：

  • 优点：
    • 能同时调度同一进程中的多个线程并行执行，发挥多处理机的优势
    • 如果一个线程被阻塞，内核可以调度其他线程占用处理机
    • 内核本身也可以采用多线程技术，提高系统的执行速度和效率
  • 缺点：
    • 同一进程的线程切换也需要切换到内核模式，系统开销较大

mit操作系统课程6.S081
6.S081 labs answer
6.S081课程记录（中文）