CPU特权级#

• CPU特权级的意义：保护操作系统
• 分类
  • 管理态(supervisor mode， 内核态): 操作系统的管理程序执行时机器所处的状态，又称处理机的特权态。在此状态下处理机可以使用全部指令（包括一组特权指令）、使用全部系统资源（包括整个存储区域）
  • 用户态(user mode): 用户程序执行时机器所处的状态成为用户态。在此状态下禁止使用特权指令，不能直接取用资源与改变机器状态，并且只允许用户程序访问自己的存储区域
• CPU特权指令
  • I/O指令(如x86的in/out指令)
  • MMIO地址空间访问指令
  • 改变机器状态寄存器(MSR)的指令

中断#

• 定义：某个事件（电源掉电、运算溢出、IO）发生时，系统中止现行程序的运行、引出处理事件程序对该事件进行处理，处理完毕后返回断点继续执行的过程
• 发现中断信号
  • 发现中断源并向CPU发出中断信号的硬件称为中断装置，IRR是中断装置中的一个寄存器，称中断请求寄存器
  • IRR中的每一位对应一个中断源，当某个中断源产生中断请求时相应的位被置1.中断装置可以接收多个外部中断源的中断请求，并进行优先级判断，将当前优先级最高的中断请求送到CPU的INTR端
  • CPU执行完一条指令后检查INTR端，如果发现有中断请求，再从中断装置获取该中断的中断号
• 中断响应
  • 定义: 中止先行程序执行，自动引出中断处理程序，也称中断进入
  • 中断响应是由硬件完成的
  • 过程：
    • 保留程序断点及处理机有关信息
    • 自动转入相应的中断处理程序执行
  • 中断进入的实质: 交换指令地址及处理机的状态信息(PSW)
• 程序状态字PSW
  • 反应程序执行时机器所处的现行状态的代码，包括: 指令地址、指令执行情况、处理机状态、应屏蔽的中断等。
  • PSW的主要作用是实现程序状态的保护和恢复，每个程序都有一个与其执行相关的PSW，每个处理机都有一个PSW寄存器
  • 由于寄存器组织方式不同，大多数计算机的处理器中可能找不到一个称为PSW的寄存器，但总有一组控制与状态寄存器实际上起到这个作用
• 如何保证将来还能回到当前程序被中断的点继续执行: 保护现场和恢复现场
  • 现场: 在中断的那一时刻能确保程序继续运行的有关信息
    • 后继指令所在的主存的单元号
    • 程序运行所处的状态
    • 指令执行情况
    • 程序执行的中间结果
  • 保护现场: 当中断发生时，必须立即把现场信息保存在主存中
  • 恢复现场: 程序重新运行之前，把保留的该程序的现场信息从主存中送至相应的指令计数器、通用寄存器或一些特殊的寄存器中
• 中断响应的一般过程
  • 中断进入(硬件实现)
    • 切换指令地址，改变处理器状态
  • 中断保护
    • 保护应用程序的执行现场到特定内存区域
    • 在高优先级实现中断的处理
    • 调用特定中断返回指令
  • 中断返回
    • 从特定内存区域恢复执行现场
    • 回到中断发生前的优先级
• 向量中断
  • 定义: 当中断发生时，由中断源自己引导处理机进入中断服务程序的中断过程称为向量中断
  • 中断向量: 每类中断类型都有自己的中断向量，包含：中断服务例程的入口地址和程序状态字
  • 中断向量表: 主存中用于存放中断向量服务地址的一组存储单元组成的表
• 中断分类
  • 中断请求(Interrupt ReQuest, IRQ)
    • IRQ是Intel术语体系中的对应概念，RISCV术语中称为interrupt
    • 由处理机外部事件引起的中断，称为外部中断
    • e.g. I/O中断、时钟中断、机器故障中断
  • 异常(exception)
    • 由处理机内部异常状态事件引起的中断
    • e.g. 除零错误、用户态下用内核态指令、地址访问异常
  • 系统调用(syscall)
    • 程序为了使用操作系统的服务自愿执行访管指令产生中断
    • e.g. x86机器中的int指令，RISCV中的ecall指令

时钟#

• 三种常见的时钟硬件
  • 可编程间隔定时器(Programmable Interval Itmer, PIT)
    • 晶体振荡器产生精确周期信号，被送到计数器，数值递减，0的时候产生时钟中断。如果希望周期产生，那么会从一个存储器中复制初值，然后循环。
    • 周期性的中断被称为时钟滴答(clock tick)
  • 实时时钟(Real Time Clock, RTC)
    • 在PC断电后仍保存事件
    • 通过主板上的电池供电，与CMOS RAM集成到一块芯片上，称为CMOS Timer
    • 可在系统初启时读入并转换位相对于某一基准事件的事件滴答数
  • 时间戳计数器(Time Stamp Counter, TSC)
    • 某系处理器包含的64位寄存器
    • 在每一个振荡信号到时，计数器递增
    • 可为操作系统提供更精确的时间度量

DMA#

• 特点
  • 传输过程中无需CPU参与控制
  • 需要中断支持
  • 用于DMA的内存地址必须连续
  • 传输过程占用总线资源

内核#

• 定义: 为了处理多道程序系统中的并发性、共享性和随机性，使用户程序能协调的工作，必须由一个软件能对硬件处理器及有关资源进行改造，以便为程序的运行提供良好的运行环境，这个部分就是操作系统内核kernel
• 基本功能：
  • 中断处理
  • 进程调度
  • 原语管理
• 特征
  • 内核是由中断驱动的
  • 内核的执行是连续的
  • 内核在屏蔽中断状态下执行
  • 内核可以使用特权指令
• 结构分类
  • 单内核结构
    • 所有操作系统组件全部放在内核中，全部运行在内核态
    • 优点: 系统结构简单，代码执行效率高; 缺点: 内核庞大，难以维护、调试
    • UNIX, Linux
  • 微内核结构
    • 只将操作系统核心组件放在内核中，将外围组件放在用户态运行
    • 优点: OS内核非常小，容易保证稳定; 缺点: 采用IPC通讯，效率偏低
    • Windows NT, 鸿蒙
  • 伴生内核结构
    • 在同一台机器上运行多个OS,一个主，其它伴生
    • docker容器，云端虚拟机

操作系统的启动#

• 将操作系统的必要部分装入主存并对系统进行初始化工作，最终使系统处于命令接收状态
• 独立引导方式(滚雪球方式)
  • OS核心文件存储在系统本身的存储设备中，由系统自己将OS核心程序读入主存并运行，建立一个操作环境
  • 适用于微机和大多数系统
• 辅助下装方式
  • OS主要文件不放在系统本身的存储设备中，在系统启动后执行下装操作，从另外的计算机系统中将操作系统常驻部分传送到计算机中，使它形成一个操作环境
  • 用于多计算机系统、由主控机与前端机构成的系统以及分布式系统

x86机器上的Linux的启动流程#

• 系统加电或复位
• BIOS启动
  • ROM中的引导程序放在固定位置: FFFF: 0000, CPU从这里开始执行
  • 硬件自检
  • 从硬盘读入零柱面零磁道1扇区(Master Boot Record, MBR)到固定位置，jmp到0000: 7C00，将控制权交给MBR中的Boot Loader程序(如GRUB)
• Boot Loader(引导程序)
  • 将Linux内核读入内存，jmp到内核的入口地址，将控制权交给OS的初始化程序
• 系统核心初始化
  • Setup.s的工作
    • 检查调入内存中的代码
    • 获取内存容量信息，设置设备模式
    • 屏蔽中断，准备进入保护模式
    • 设置中断描述符表(IDT)，全局描述符表(GDT)；控制交给Heads
  • Heads的工作
    • 调用Setup_IDT做准备工作
    • 检查CPU类型
    • 调用Setup_pageing进行页表初始化
    • 调用main.c中的Start_kernel()
  • Start_kernel()的工作
    • 对与CPU、内存等最基本硬件相关部分进行初始化
    • 对IDT进行初始化
    • 为进程调度程序做准备
    • 设置基准时钟
    • 内核的内存分配
    • 对文件系统进行初始化
    • 建立init进程
  • init进程对每一个联机终端建立”getty”进程，getty 在终端上现实login, 等待用户登录

操作系统的生成#

• 定义
  • 所谓系统生成，就是为了满足物理设备的约束和需要的系统功能，通过组装一批模块来产生一个清晰的、使用方便的操作系统的过程
  • 简单地说就是系统的安装，即将OS安装到启动装置(可以是磁盘，也可以是tftp服务器的某个目录)
• 系统生成的内容
  • Bootloader
  • OS内核
  • 文件系统
  • 执行环境(如用户态lib等)

静态链接和动态链接#

Linux系统调用控制程序的功能#

1. 取系统调用号，检验合法性
2. 建立调用堆栈，保护现场信息
3. 根据系统调用号定位核心函数地址
4. 根据通用寄存器内容，从用户栈中取入口参数
5. 核心函数执行，把结果返回给应用程序
6. 执行退栈操作，判别调度程序scheduler是否要被执行

顺序程序#

• 程序的一次执行过程称为一个计算，由许多简单操作组成
• 一个计算的若干操作必须按照严格的先后次序顺序地执行，这个计算过程就是程序的顺序执行过程
• 特点
  • 顺序性
  • 封闭性
  • 可再现性

并发程序#

• 定义: 若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的
• 特点：
  • 程序与计算不再一一对应
  • 程序并发执行的相互制约
    • 间接的相互制约关系: 资源共享
    • 直接的相互制约关系: 公共变量
  • 失去程序的封闭性和可再现性: 若一个程序的执行可以改变另一个程序的变量，那么后者的输出就可能有赖于各程序执行的相对速度，即失去了程序的封闭性特点
    • 程序并发执行时的结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误

进程的定义#

• 进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动
• 进程与程序的区别
  • 程序是静态的概念，进程是动态的概念
  • 进程一个独立运行的活动单位
  • 进程是竞争系统资源的基本单位
  • 一个程序可以对应多个进程，一个进程至少包含一个程序

进程的状态#

• 运行状态(running)
  • 该进程已获得运行所必需的资源，它的程序正在处理机上执行
• 等待状态(waiting)
  • 进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行
• 就绪状态(ready)
  • 进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行

进程描述#

• 进程控制块
  • 描述进程与其它进程、系统资源的关系以及各进程在各不同时期所处的状态的数据结构，称为进程控制块(process control block, PCB)
  • 主要内容
    • 进程标识符: 进程符号名内部id
    • 进程当前状态: 本进程目前处于何种状态
    • 当前队列指针next: 该项等级了处于同一状态下的下一个进程的PCB地址
    • 进程优先级: 反应了进程要求CPU的紧迫程度
    • CPU现场保护区: 当进程由于某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中
    • 通信信息: 进程间进行通信时所记录的有关信息
    • 家族联系: 指明本进程与家族的联系
    • 占有资源清单
• 进程的组成(进程映像)
  • 程序与数据
    • 描述进程本身应完成的功能
  • 进程控制块PCB
    • 进程的动态特征，该进程与其它进程和系统资源的关系

进程控制的概念#

• 进程控制的职责: 对系统中的进程实时有效的管理，负责进程状态的改变
• 常用的进程控制原语
  • 创建原语、撤销原语、等待原语、唤醒原语
• 进程的状态变化

进程撤销#

• 进程撤销原语的形式
  • 进程完成任务或希望终止时使用进程撤销原语exit()
• 进程撤销原语的功能
  • 撤销当前运行的进程。将改进程的PCB结构归还到PCB资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序
• 进程撤销原语的实现
  • 入口->由运行指针得当前进程的pid->释放本进程所占用的资源给父进程->该进程从总队列中摘下->释放PCB结构->转进程调度
• 进程撤销的主要原因
  • 进程正常运行结束
  • 进程运行中处所，如执行了非法指令、在常态下执行了特权指令、运行时间超越了分给的最大时间段、申请的内存超过了系统能提供的最大量、越界错误等
  • 操作员或操作系统干预
  • 父进程撤销其子进程
  • 操作系统终止

进程等待#

• 进程等待原语的形式
  • 当进程需要等待某一事件完成时，它可以调用等待原语挂起自己
  • susp(chan)
  • 入口参数chan: 进程等待的原因
• 进程等待原语的功能
  • 中止调用进程的执行，并加入到等待chan的等待队列中；最后使控制转进程调度
  • 注意：并没有一个唯一特定的系统调用来将进程挂起，导致进程挂起的原因很多，所以很多系统调用例程都可能使用此原语讲当前进程挂起
• 进程等待原语的实现
  • 入口->保护进程的CPU现场到PCB结构中->置该进程为“等待”状态->将该进程PCB结构插入到等待队列中->转进程调度
• 进程等待的原因
  • 进程在执行过程中通过系统调用请求一些暂时得不到而必须等待的服务
    • 读写文件、访问共享内存等，这些服务操作系统可能无法立即提供
    • 进程在执行过程中发出了I/O请求，从而必须等待改I/O请求的完成才能继续执行
    • 因为进程间通讯的原因，一个进程在执行过程中必须等待另一个进程的消息才能继续往下执行

进程唤醒#

• 进程唤醒原语的形式
  • 当处于等待状态的进程所期待的事件到来时，由发现者进程使用唤醒原语唤醒它
  • wakeup(chan)
  • 入口参数chan: 进程等待的原因
• 进程唤醒原语的哦功能
  • 当进程等待的事件发生时，唤醒等待该事件的进程
• 进程唤醒原语的实现
  • 入口->找到该等待队列->将队列首进程移除此等待队列->将该进程置为“就绪”状态，并将其PCB结构插入到就绪队列中->返回
• 进程唤醒的时机
  • I/O完成时会产生一个中断，在该中断的中断处理函数中会唤醒等待该I/O的进程
  • 进程在等待某个被上锁的资源，当另一个进程通过系统调用来释放其施加在该资源上的锁的时候，系统调用服务例程会唤醒该进程
  • 进程在等待另一个进程的消息，当另一个进程通过系统调用向其发送消息时，系统调用服务例程会唤醒该进程

进程切换#

• 进程切换的时机
  • 操作系统必须先获取处理器的使用权

• 操作系统获得了处理器使用权后，一定会做进程切换吗？
  • 处理机状态切换(操作系统获得使用权的过程)
    • 设置程序计数器为中断处理例程的入口
    • 从用户态切换到内核态，开始中断处理例程(包含特权指令)的执行
  • 处理机状态切换的开销很小，大多数情况下不会导致进程切换；但是如果当前进程的状态需要变为等待态或就绪态，就必须做进程切换
• 进程切换要做哪些事情
  • 保存当前进程的上下文
  • 改变当前进程的进程控制块内容，包括其状态的改变、离开运行态的原因等
  • 将当前进程的控制块移到相应队列中，如就绪队列、事件等待队列等
  • 选则一个合适的进程开始执行
  • 更新被选则进程的控制块，将其状态置为运行态
  • 恢复被选则进程的上下文

进程互斥的概念#

• 临界资源
  • 特点: 当两个进程共用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量
  • 定义: 一次仅允许一个进程使用的资源称为临界资源
  • e.g. 硬件: 输入机、打印机、磁带机; 软件: 公用变量、数据、表格、队列等
• 临界区
  • 临界区是进程中对公共变量(或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区
• 互斥
  • 操作系统中，当某进程正在访问某一存储区域时，就不允许其它进程来读出或者修改该存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。
  • 注意: 关于同一临界资源的临界区才需要互斥进入
• 进程同步的定义
  • 并发进程在一些关键点上可能需要互相等待以互通消息，这种相互制约的等待于互通消息称为进程同步
• 临界区的访问规则
  • 空闲则进入: 没有进程在临界区时，任何进程都可以进入临界区
  • 忙则等待: 有进程在临界区时，其它进程均不能进入临界区
  • 有限等待: 等待进入临界区的进程不能无限等待
  • 让权等待(可选): 不能进入临界区的进程应释放CPU

锁#

用变量w代表某种资源的状态，称为锁。

• 检测w的值(0或1)
• 如果w的值为1，继续检测
• 如果w的值为0，将锁位置1(表示占用资源)，进入临界区执行
• 临界资源使用完毕，将锁位置0

信号灯#

• 信号灯是一个确定的二元组(s, q)，s是一个具有非负数值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯对并发进程和共享资源进行控制和管理。
  • s >= 0，进程执行
  • s < 0，进程停止执行
  • 注意: 创建信号灯时应说明信号灯的意义和s的初值，且初值绝不能为负值
• P操作
  • 对信号灯s的P操作记为P(s)
  • P(s)是一个不可分隔的原语操作，即取信号灯值减1，若相减结果为负，则调用P(s)的进程被阻，并插入到该信号灯的等待队列中，否则该进程继续执行
• V操作
  • 对信号灯s的V操作记为V(s)
  • V(s)是一个不可分隔的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，唤醒在该信号灯等待队列上的第一个进程
• 注意事项
  • 信号灯的初值不能为负值
  • 必须成对使用P和V操作: 遗漏P操作则不能保证互斥访问，遗漏V操作则不能再使用临界资源之后将其释放(给其它等待的进程)
  • P、V操作不能次序错误、重复或遗漏

信箱的归属权: 进程vs操作系统#

• 信箱属于创建它的进程
  • 随着创建它的进程结束而结束
  • e.g. 端口
• 信箱属于操作系统
  • 与使用它的进程是否结束无关，必须通过明确的命令撤销
  • e.g. 消息队列

Linux: 共享内存#

共享内存是把同一片物理内存区域同时映射到多个进程的地址空间的通信机制

• 共享内存的创建
  • int shmget(key_t key, int size, int shmflg)
  • key: 键值，多个需要使用同一共享内存的进程用相同的key来创建或获取该共享内存
  • size: 共享内存的大小
  • shmflg: IPC_CREAT | 0666
• 共享内存的绑定
  • void *shmat(int shmid, char* shmaddr, int shmflg)
  • shmid: 共享内存句柄，shmget调用的返回值
  • shmaddr: 一般用NULL
  • shmflg: SHM_R | SHM_W
• 共享内存的释放
  • int shmctl(int shmid, int cmd, struct shmid_ds* buf)
  • shmid: 共享内存句柄，即shmget函数的返回值
  • cmd: 控制命令
  • buf: 一个结构指针，它指向共享内存模式和访问权限的结构

Linux: 信号量#

• 信号量的创建
  • int semget(key_t key, int num_sems, int sem_flags)
  • key: 用来允许多个进程访问相同信号量的整数值，它们通过相同的key值来调用semget
  • num_sems: 所需要的信号量数目。Semget创建的是一个信号量数组，数组元素的个数即为num_sems
  • sem_flags: 一个标记集合，与open函数的标记十分类似。低九位是信号的权限，其作用与文件权限类似。另外，这些标记可以与IPC_CREATE进行或操作来创建新的信号量，一般用IPC_CREATE | 0666
• 信号量的控制
  • int semctl(int sem_id, int sem_num, int command, ...)
  • sem_id: 是由semget所获得的信号量标识符
  • sem_num: 是信号量数组元素的下标，即指定对第几个信号量进行控制
  • command: 要执行的动作，有多个不同的command值可用于semctl，常用的两个command值为
    • SETVAL: 用于为信号量赋初值，其值通过第四个参数指定
    • IPC_RMID: 当信号量不再需要时用于删除一个信号量标识
  • 如果有第四个参数，则是union semun，该联合定义如下

1
union semun {
2
  int val;
3
  struct semid_ds* buf;
4
  unsigned short* array;
5
}

• 信号量的操作
  • int semop(int sem_id, struct sembuf* sem_ops, size_t num_sem_ops)
  • sem_id: 要操作的信号量的标识符
  • sem_ops: 一个指向结构数组的指针，该结构包含操作的参数

1
struct sembuf{
2
  short sem_num;  // 数组下标
3
  short sem_op;  // 操作，-1或1
4
  short sem_flg;  // 0
5
}

• num_sem_ops: 操作数量，一般为1

Linux: 信号#

• 信号机制是一种进程间的软件中断信号通知和异步处理机制
• 信号机制是在软件层次上对中断机制的一种模拟
• 进程在很多情况下会都接收到软中断信号
  • 用户在终端按下某些特殊键: e.g. ^C,终端进程会发送SIGINT信号给前台进程
  • 硬件异常: e.g. 除零，CPU产生异常，内核处理完该已成后会发送SIGFPE信号给进程
  • 内核检测到某种软件条件: 如闹钟超时，会发送SIGALRM信号给进程
  • 显式调用kill函数或kill命令发送信号给某个进程

信号机制的功能#

• 预制对信号的处理方式
  • 忽略: 忽略该信号不做处理，SIGKIL和SIGSTOP不能被忽略
  • 捕获: 通知内核在某种信号发生时，调用用户指定的函数进行处理
  • 执行默认动作: 编译器预置了各个信息的处理函数
• 信号发送: 发送进程把信号送到指定进程的信号域的某一位上，如果目标进程正在一个可被中断的优先级上睡眠，系统将其唤醒
• 信号处理: 收到信号的进程在由核态返回到用户态前，按预置的处理方式完成对相应事件的处理
• 不足: 传送的信息量小，只有一个信号类型

Linux: 管道#

• 管道是进程间基于文件的一种间接通信机制
• 管道是半双工的，数据只能单向流动
• 管道对于管道两端的进程而言就是一个文件，写管道时内容添加在文件末尾，读管道则从文件头部读出
• 无名管道
  • 无名管道没有名字，只有一组文件描述符
  • 子进程从父进程继承文件描述符
  • 只能用于具有亲缘关系的进程间的通信
• 命名管道
  • 管道有文件名，允许无亲缘关系的进程通过访问管道文件进行通信
• 与管道相关的系统调用
  • 创建无名管道: int pipefd[2]; int pipe(pipefd)
    • pipedf[0]只能用于读，接收进程应关闭写入端，即close(pipefd[1])
    • pipefd[1]只能用于写，发送进程应关闭读取端，即close(pipefd[0])
  • 将数据写入管道: write()
    • 管道长度受到限制，管道满时写操作将被阻塞，直到管道中的数据被读取
    • fcntl()可将管道写模式设置为非阻塞模式
  • 从管道读取数据: read()
    • 数据被读取后将自动从管道中清楚，若管道中没有数据则读操作将被阻塞
    • fcntl()可将管道读模式设置为非阻塞模式
  • 关闭管道: close()
    • 所有读端口都关闭时，在管道上进行写操作的进程将受到SIGPIPE信号
    • 所有写端口都关闭时，在管道上进行读操作的read()函数将返回0
  • 创建命名管道
    • int mknod(char* pathname, mode_t mod, dev_t dev);
    • int mkfifo(char* pathname, mode_t mode);
  • 命名管道的使用
    • 命名管道必须先调用open()将其打开，其它与无名管道相似
    • 以只读方式(O_RDONLY)打开时，进程将被阻塞直到有写方打开管道
    • 以只写方式(O_WRONLY)打开时，进程将被阻塞直到有读方打开管道
  • 命名管道的删除
    • int unlink(char* pathname)

Linux: 消息队列#

• 消息队列是消息的链接表，存放在内核中并由消息队列标识符表示
• 每一条消息都由自己的消息类型，每种类型的消息都被对应的链表所维护
• 消息队列的创建
  • int msgget(key_t key, int msgflg)
  • key: 键值，多个需要使用同一消息队列的进程用相同的key来创建或获取该消息队列
  • msgflg: flag | mode
    • flag: 可以是0或者IPC_CREATE(不存在就创建)
    • mode: 同文件权限一样
• 消息的发送
  • int msgsnd(int msqid, const void* msgp, size_t msgsz, int msgflg)
  • msqid: 消息队列ID
  • msgp: 存放消息的结构体

1
struct msgbuf {
2
  long mtype;  // 消息的类型，必须>0
3
  char mtext[1];  // 消息内容，长度可变
4
}

• msgsz: 要发送的消息的大小，不包括消息的类型占用的4个字节
• msgflg: 如果是0，当消息队列为满时msgsnd会阻塞；如果是IPC_NOWAIT，当消息队列为满时不阻塞，立即返回
• 消息的接收
  • int msgrcv(int msqid, void* msgp, size_t msgsz, long msgtype, int msgflg);
  • msqid: 消息队列ID
  • msgp: 存放消息的结构体
  • msgsz: 要接收的消息的大小，不包括消息的类型占用的4个字节
  • msgtyp: 要接收的消息类型
    • =0: 返回消息队列中的第一条消息

    • 0: 返回消息队列中类型等于msgtyp的第一条消息

    • <0: 返回其类型小于或等于msgtyp绝对值的最小的一个消息
  • msgflg: 如果是0，则没有指定类型的消息时会阻塞；如果是IPC_NOWAIT，则不阻塞，立即返回
• 消息队列的删除
  • int msgctl(int msqid, int cmd, struct msqid_ds* buf);
  • msqid: 消息队列ID
  • cmd: 控制命令，IPC_RMID表示删除

线程的定义#

• 线程是进程中的一条执行路径

• 单个进程可创建多个同时存在的线程

• 每个线程又自己私用的堆栈和处理机执行环境

• 同一进程中的多个线程共享分配给该进程的内存

• 线程的特点

  • 优点
    • 创建和撤销一个线程比创建一个进程的开销要小得多(10~100倍)
    • 因为共享地址空间和数据，线程间通信十分方便且高效
    • 同一个进程的线程间切换速度快(纳秒级)
    • 在进程内创建多线程，可以提高系统的并性处理能力，加快进程的处理速度
  • 缺点
    • 一个线程崩溃，会导致其所属进程内的所有线程崩溃

• 多核与多线程

  • 应用在多核处理器上所能取得的性能上的好处，实际上取决于它对多处理器资源的利用能力
  • 设f为程序中能并性的部分的运行事件在整个程序运行事件中的占比
  • 加速比 = 在单处理器上执行程序的时间 / 在N个处理器上执行程序的时间 = $\frac{1}{1-f+\frac{f}{N}}$

• 线程的状态

  • 创建
  • 就绪
  • 运行
  • 等待
  • 终止

虚拟资源#

• 操作系统对资源区分两种不同的概念
  • 物理资源(实资源)
  • 虚拟资源(逻辑资源): 某些物理资源有限，采用其它物理资源改造成该类资源使用
• 虚拟技术的目的
  • 方便用户使用
  • 资源可动态分配，提高资源利用率

计算机系统中的物理资源与虚拟资源分析

资源分配策略#

• 先请求先服务
  • 每一个新产生的请求均排在队尾
  • 当资源可用时，取队首元素，并满足其需要
  • 排序原则: 按请求的先后次序排序
• 优先调度
  • 对每一个进程指定一个优先级
  • 每一个新产生的请求，按其优先级的高低插到相应的为止
  • 当资源可用时，取对手元素，并满足其需要
  • 排序原则: 按优先级的高低排序
• 针对设备特性的调度
  • e.g. 磁盘调度算法
    • 最短寻道时间优先SSTF
    • 扫描算法SCAN
    • 循环扫描算法CSCAN

进程-资源分配图#

• 约定$P_i -> R_j$为请求边，表示进程$P_i$申请资源$R_j$中的一个资源得不到满足而处于等待$R_j$类资源的状态，该有向边从进程开始指向方框边缘，表示进程$P_i$申请$R_j$类中的一个资源。
• $R_j -> P_i$为分配边，表示$R_j$类中的一个资源已经倍进程$P_i$占用

产生死锁的必要条件#

1. 互斥条件: 涉及的资源是非共享的，即为临界资源
2. 不剥夺条件(非抢占): 进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走
3. 占有并等待(部分分配): 进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源
4. 环路条件(循环等待): 存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求

解决死锁问题的策略#

• 破坏产生死锁的四个必要条件之一
  • 预防死锁
  • 避免死锁
  • 死锁的检测与解除
• 死锁预防: 静态分配策略
  • 在作业调度时为选中的作业分配它所需要的所有资源，资源一旦分配给该作业后，在其整个运行期间这些资源为它独占
  • 缺点
    • 一个用户(进程)在程序运行之前很难提出将要使用的全部设备
    • 设备(资源)的浪费太大，有些资源在进程运行过程中可能只有很少的时间会用到，有的甚至根本不会用到，例如条件分支语句
• 死锁预防: 有序资源分配法
  • 系统中所有资源都给定一个唯一的编号
  • 所有分配请求必须以上升的次序进行
  • 当遵守上升次序的规则时，若有资源可用，则予以分配；否则，请求者等待
  • 优点: 相对于静态分配法，提高了资源使用效率
  • 缺点: 进程实际使用资源的顺序不一定与资源的编号相一致
• 死锁避免: 银行家算法
  • 对每个资源请求进行检查，看是否会导致不安全状态。若是，则拒绝该请求；否则便满足该请求
  • 检查状态是否安全的方法是看其是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全状态，最初的请求可以批准
  • 按某种顺序并发进程都能获得最大资源而顺序完成的序列称为安全序列

死锁的解除#

• 立即结束所有进程的执行，并重启操作系统
• 撤销陷于死锁的所有进程
• 逐个撤销陷于死锁的进程，回收其资源，直至死锁解除
• 剥夺陷入死锁的进程占用 资源，但并不撤销它，直至死锁解除
• 根据系统保存的checkpoint，让所有进程回退，直到足以解除死锁

作业控制块#

• 作业名
• 资源要求
  • 估计执行时间
  • 最迟完成时间
  • 要求的主存数量
  • 要求外设的类型及台数
  • 要求文件量和输出量
• 类型
  • 控制方式(联机/脱机)
  • 作业类型(计算型/IO型)
• 资源使用情况
  • 进入系统时间
  • 开始执行时间
  • 已执行时间
  • 主存地址
  • 外设台号
• 优先级
• 状态

作业调度的目标#

• 调度实质上式一个策略问题，设定的目标往往是相互冲突的
  • 单位时间内运行尽可能多的作业
  • 使处理机尽可能保持”忙碌”
  • 使各种I/O设备得以充分利用
  • 对所有的作业都是公平合理的
• 考虑因素
  • 调度算法应与系统设计目标保持一致
  • 注意系统资源均衡使用
  • 保证提交的作业在截至时间内完成
  • 设法缩短作业平均周转时间

作业调度算法性能的衡量指标#

• 周转时间
  • 定义: 一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间
  • $t_i = tc_i - ts_i$
    • $t_i$: 作业i的周转时间
    • $ts_i$: 作业i的提交时间
    • $tc_i$: 作业i的完成时间
  • 意义: 说明作业i在系统中停留时间的长短
  • 平均周转时间: $t=\frac{1}{n}\sum _{i=1}^n t_i$
• 带权周转时间
  • 定义: 一个作业的周转时间与其运行时间的比值
  • $w_i = \frac{t_i}{tr_i}$
    • $tr_i$为作业的实际运行时间
  • 意义: 说明作业i在系统中相对等待时间
  • 平均带权周转时间$w=\frac{1}{n}\sum _{i=1}^n w_i$

作业调度算法#

• 先来先服务调度算法(FCFS)
  • 策略: 按作业来到的先后次序进行调度
  • 特点
    • 优先考虑系统中等待时间最长的作业，不管运行特性
    • 简单，容易实现
    • 性能指标不稳定，波动大
• 短作业优先调度算法(SJF: Shortest Job First)
  • 策略: 按照作业请求运行的时间长短进行调度，优先选则短作业
  • 特点: 容易实现，系统吞吐量高
    • 只照顾短作业，而没有考虑长作业的利益；需要预知作业的运行时间
• 响应比高者优先调度算法(HRN: Highest Response Ratio Next)
  • 响应时间=开始执行时间-提交时间，可以反映作业等待了多久，等待时间长的就会更能够先执行
  • 在我们的版本中，响应时间=周转时间
  • 响应比=响应时间/运行时间
  • 策略: 优先选则响应比高者作业运行
  • 特点: 前两种算法的一种折衷，既照顾了短作业，又不使作业等待时间过长

进程调度/分派结构#

• 调度: 在众多处于就绪状态的进程中，按一定的原则选则一个进程
• 分派: 当处理机空闲时，移除就绪队列中第一个进程，并赋予它使用处理机的权力

进程调度的功能#

• 记录进程的有关情况和状态特征
• 决定调度策略
  • 优先调度原则: 进程就绪队列按进程优先级高低排序
  • 先来先服务原则: 进程就绪队列按进程来到的先后次序排序
• 实施处理机的分配和回收

进程调度方式#

• 进程调度方式是指当一个进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要运行，系统如何分配处理机
  • 非剥夺方式: 正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程
  • 剥夺方式: 当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程

进程调度算法#

Linux进程调度目标和特点#

• 调度策略
  • 基于动态优先级和可变时间片的调度
  • 调度方式为可抢占式调度
• 调度目标
  • 实现算法复杂度为O(1)级的调度
  • 提高交互性能
  • 保证公平
  • 实现SMP可扩展性
• 特点(多级反馈循环调度)
  • 基于进程过去行为的启发式算法
  • 选则优先级高的进程先运行，相同优先级的进程按循环方式调度
  • 动态优先级依进程占有CPU的情况、休眠时间的长短来增、减
  • 系统根据进程优先级调整分配给它的时间片
  • 实施可抢占调度方式
• 可变优先级
  • 基于优先级的调度: 优先级高的进程先运行，相同优先级的进程按轮转方式进行调度
  • 静态优先级
    • 静态优先级的确定: 在进程创建时，新创建的进程继承父进程的静态优先级
    • 静态优先级的取值范围: 0-99对应实时进程，100-139对应普通进程(取值越小，优先级越高)
    • 静态优先级的改变: 用户可以通过系统调用改变nice值，从而改变自己拥有的静态优先级
  • 动态优先级
    • 每个进程有一个动态优先级，它是进程调度程序选择可运行进程所使用的参数，其取值范围是100(最高优先级)~139(最低优先级)(实时进程优先级不变)
    • 动态优先级的计算 动态优先级=nax(100, min(静态优先级-bonus+5, 139))
      • bonus的取值范围是0~10
      • bonus值小于5，表示降低动态优先级以示惩罚
      • bonus值大于5，表示增加动态优先级以示奖励
      • bonux的值也与进程的平均休眠时间有关
• 可变时间片
  • Linux系统的进程的调度目标: 优先照顾交互式进程，为其提供较长的时间片
  • 时间片的计算
    • 基本时间片: 静态优先级本质上决定了进程的基本时间片
    • 静态优先级越高(值越小)，基本时间片越长
  • 时间片处理的时机
    • 创建新进程时的处理: 新创建的子进程和父进程均分父进程剩余的时间片
    • 进程用完时间片时的处理: 根据任务的静态优先级重新计算时间片
  • 时间片的使用
    • 一个进程拥有的时间片可分多次使用，放弃CPU时进入活动队列
    • 当一个进程的时间片耗尽时，认为是过期进程，进入过期队列
• 活动队列和过期队列
  • 每个处理器维护两个优先级数组: 活动数组和过期数组
  • 活动数组上的可执行队列中的进程都有剩余时间片
  • 过期数组上的可执行队列中的进程都已耗尽时间片
  • 当一个进程的时间片耗尽时，被移至过期队列中；当活动数组上的可执行队列中的所有进程都已耗尽时间片，在活动数组和过期数组之间切换指针

存储组织#

• 存储器的功能示保存数据，存储器的发展方向是告诉、大容量和小体积
• 存储组织是指在存储计数和CPU寻址计数许可的范围内组织合理的存储结构
  • 依据是访问速度匹配关系、容量要求和价格
  • 寄存器-内存-外存 结构
  • 寄存器-缓存-内存-外存 结构
  • 快速缓存
    • data cache
    • TLB(Translation Lookaside buffer)
  • 内存: DRAM, SDRAM等
  • 外存: 硬盘、光盘、软盘、磁带等

程序的逻辑组织#

• 一维地址结构
  • 一个程序是一个连续、线性的地址结构
  • 确定线性地址空间中断 指令地址或操作数地址只需要一个信息
• 二维地址结构
  • 一个程序由若干个分段组成，每个分段是一个连续的地址区
  • 确定线性地址空间中断指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量

主存共享方式#

• 大小不等的区域
  • 分区存储管理
  • 段式存储管理
• 大小相等的区域
  • 页式存储管理
• 结合
  • 段页式存储管理

概念#

• 物理地址(绝对地址、实地址): 物理地址式计算机主存单元的真实地址，又称为绝对地址或实地址
• 主存空间: 物理地址的集合所对应的空间组成了主存空间
• 逻辑地址(相对地址、虚地址): 用户的程序地址(指令地址或操作数地址)均为逻辑地址
• 程序地址空间: 用户程序所有的逻辑地址集合对应的空间

主存管理功能#

• 地址映射
• 主存分配
• 存储保护
• 主存扩充

固定分区#

• 操作系统在启动时将内存区域划分为若干个分区。分区总数和各分区的大小一旦确定，则整个系统运行阶段都保持不变。固态分区也称为静态分区
• 分区说明表: 记录分区信息的树结构。存储管理程序在内存分配、释放、存储保护以及地址转换时都要查询和修改分区说明表中的信息

动态分区#

动态分区式指处理程序的过程中依用户请求的大小建立并分配分区

分区存储管理的缺点#

• 程序必须整体装入
• 需要分配连续的内存空间
• 碎片问题

基本概念#

• 页面: 程序的地址空间被分成大小相等的片，称为页面(page),又称为虚页。
• 主存块: 主页被分成大小相等的片，称为主存块，又称为实页、页框(frame)
• 页面与主存块的关系
• 页表
  • 定义: 为了实现从地址空间到物理主存的映像，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表
  • 组成
    • 高速缓冲区: 旁路转换缓冲(Translation Lookaside Buffer, TLB)，或称为页表缓冲，CPU中用于存放页表项的告诉缓存。地址变换速度快，但成本较高
    • 主存区域: 地址变换速度比硬件慢，成本较低

页式地址变换#

• 页表: 记录页与块之间的对应关系
• 虚地址结构: 当CPU给出的虚地址长度为16位，页面大小位1KB时，在分页系统中地址结构的格式为
  • 页号P(1510) + 页内位移w(90)
• 页式地址变换
  • CPU给出操作数地址
  • 由页分页机构自动把逻辑地址分为两部分，得到页号P和页内相对位移w
  • 根据页表始址寄存器指示的页表始地址，以页号为索引，找到p对应的块号b
  • 将块号b和页内位移量w拼接在一起，就形成了访问主存的物理地址
• 缺点:
  • 每次取数据都需要访问两次内存
• 采用联想存储器加快查表速度
  • 在联想存储器中存放正在运行的进程当前用到的页号和对应的块号，又称为快表

缺页处理#

段式地址空间#

• 段: 分段式程序中自然划分的一组逻辑意义完整的信息集合，如代码段、数据段
• 程序地址空间: 由若干逻辑分段组成，每个分段有自己的名字，并且是一个连续的地址区
• 段式地址结构: 段号s + 段内位移w
• 段式地址变换
  • 取出程序地址(s, w)
  • 用s检索段表
  • 如w < 0 或 w >= L，则主存越界
  • (B+w)即为所需主存地址

分段和页面的区别

Linux系统的存储管理#

输入输出控制方式#

CPU通过I/O控制器与物理设备打交道。按照I/O控制器智能化程度的高低，I/O设备的控制方式分为四类

• 循环测试I/O方式
• I/O中断方式
• DMA方式
• 通道方式

I/O子系统#

• I/O控制的功能
  • 解释用户的I/O系统调用
  • 设备驱动
  • 中断处理
• 设备驱动程序
  • 设备驱动程序是能直接控制设备运转的程序，它根据各类设备的特点和性能来编写。每一类设备有一个相应的设备驱动程序，能控制同类中多台物理设备同时工作。设备I/O完成或出错时产生中断，由该类设备的中断处理程序处理
• I/O子系统的接口
  • 在应用层为用户提供I/O应用接口
    • 对设备的控制和操作则由内核I/O子系统来实施
  • 对每个通用设备类型都通过一组标准函数(及接口)来访问
    • 设备间的差异被设备驱动程序所封装，这些设备驱动程序一方面可以定制以适合各种设备，另一方面也提供了一组标准的设备访问接口
    • 设备驱动程序层的作用是隐藏设备控制器之间的差异，它将I/O子系统与硬件分离，简化了操作系统开发人员的任务，也有利于设备的设计与制造
• I/O控制模块的实现方式
  • 以设备处理进程的方式
    • 为每一类设备设置一个设备处理进程
    • 没有I/O请求时，该进程睡眠；当有I/O请求到来时，该进程被唤醒，进行设备驱动工作
  • 由I/O控制模块的接口程序负责解释用户的I/O系统调用，将其转换称I/O控制模块认识的命令形式后，将I/O请求发给对应的设备处理进程
  • 将设备与文件一样对待: 将设备与文件一样对待，使用文件系统的系统调用命令进行设备的读写

输入输出控制示例#

Linux设备驱动程序框架#

• 驱动程序的注册和注销
• 设备的打开和释放
• 设备的读写操作
• 设备的控制操作
• 设备的中断和查询处理

缓冲概念#

• 定义: 缓冲是两种不同速度的设备之间传输信息时平滑传输过程的常用手段
• 缓冲类别
  • 缓冲器: 缓冲器是用来暂时存放数据的一种存储装置，它容量较小，存取速度快
  • 软件缓冲: 在I/O操作期间用来临时存放I/O数据的一块存储区域
• 引入的意义
  • 处理数据流的生产者与消费者间的速度差异
  • 协调传输数据大小不一致的设备
  • 应用程序的拷贝语义
    • e.g. 操作系统为保证系统调用write的正确语义(应用程序要写入磁盘的数据就是write系统调用时发生时候的版本)
    • 方法: 在系统调用返回前将应用程序缓冲区复制到内核缓冲区

利用缓冲技术如何进行I/O操作#

• 进程活动期间，请求从某输入设备读入数据
  • 当用户要求在某个设备进行读操作时，首先从操作系统中获得一个空的缓冲区
  • 操作系统将一个物理记录送到缓冲区中
  • 用户请求这些数据时，操作系统将依据逻辑记录特性从缓冲区中提取数据并发送到用户进程存储区中
  • 当缓冲区空而进程又要从中取用数据时该进程被迫等待。此时操作系统需要重新送数据填满缓冲区，进程才能从中取数据继续运行
• 进程活动期间，请求从输出设备输出数据
  • 当用户要求进行写操作时，首先从操作系统中获得一个空的缓冲区
  • 将一个逻辑记录从进程存储区传送到缓冲区中
  • 当缓冲区写满时，操作系统将缓冲区的内容作为物理记录文件写到设备上，使缓冲区再次为空
  • 只有在系统还来不及腾空缓冲区之前，进程又企图输出信息时，它才需要等待

常用的缓冲技术#

• 双缓冲
  • 在双缓冲方案下，为输入或输出分配两个缓冲区buf1, buf2
• 环形缓冲
  • 在系统中设置若干缓冲区，并把这些缓冲区连接起来，这样若干个缓冲区就形成了一个环，故称环形缓冲区
• 缓冲池
  • 将系统内所有的缓冲区统一管理起来，就形成了能用于输入/输出的缓冲池。缓冲池通常由大小相同的缓冲区组成，是系统的公用资源，任何进程都可以申请使用这个缓冲池中的各个缓冲区

Unix系统的缓冲区管理#

• 目的
  • 加快系统相应、增强系统吞吐量
  • 减少对磁盘的I/O操作次数
• UNIX系统缓冲管理的思路
  • 当进程要从磁盘读数据时，首先考虑从缓冲区中读
  • 当进程要写数据到磁盘时，先写入缓冲区中
• 缓冲区数据结构
  • 缓存数组: 含有磁盘上的数据的存储器数组
  • 缓存首部: 描述缓冲区特性的数据结构
    • 设备号: 缓冲区所包含的信息所属设备的设备号
    • 快号: 由设备号指出的设备上相对于第0快的块号
    • 状态flag: 描述了缓冲区当前的状态
      • BUSY: 缓冲区当前正忙
      • AVE: 缓冲区包含的数据有效
      • DELWR: 内核在某缓冲区重新分配出去之前必须把缓冲区内容写到磁盘上
      • WRITE: 内核当前正把缓冲区的内容写到磁盘
      • READ: 内核当前正从磁盘往缓冲区写信息
      • WAIT: 一个进程当前正在等待缓冲区变为空闲
  • 缓冲区队列结构
    • 设备缓冲区队列: 与某类设备有关的所有缓冲区组成的队列称为设备缓冲区队列，简称b链
    • 空闲缓冲区队列: 可供重新分配使用的缓冲区组成的队列称为空闲缓冲区队列，简称av链
• UNIX缓冲管理算法
  • 一个buf被分配用于读/写某设备上的块时
    • 置B_BUSY=1，位于b链上，不在av链上
  • 当读写操作结束时
    • 释放该buf吗，置B_BUSY=0，仍留在b链上，并送入av链尾
  • 若进程需要的信息在buf中时
    • 在该设备的b链上找到，置B_BUSY=1，从av链上摘除，使用完后，送入av链队尾
  • 对空闲buf队列的处理
    • 当需要一个空闲buf时，总是取av链的首元素；一个使用过的buf释放时，插入到空闲buf队列(av链)的队尾。实现了精确的最久未使用淘汰算法(LRU算法)
  • 对延迟写的处理
    • 当一个具有延迟标写标记的buf移动到av链头，要用于分配时，立即进行写操作。从av链上摘除，使用完后又送入av头部

独享分配#

• 独享设备
  • 让一个作业在整个运行期间独占使用的设备
  • 特点
    • 临界资源
    • 费时的I/O操作或需要人工干预
• 独享分配
  • 在一个作业执行前，将它所要使用的设备分配给它；当它结束时，将分配给它的这类设备收回

共享分配#

• 共享设备
  • 由多个作业、进程共同使用的设备称为共享设备
  • 特点
    • 旋转设备，可直接或随机访问
    • 便于共享，转接简单，耗费较少
  • 共享分配
    • 进程提出资源申请时，将所要使用的设备分配给它；进程使用完毕后，立即将设备收回

虚拟分配#

• 虚拟技术
  • 在一类物理设备上模拟另一类物理设备的技术，将独占设备转化为共享设备的技术
• 虚拟分配
  • 当进程需要与独占型设备交换信息时，系统将分配磁盘空间，并建立相应的数据结构，这种分配方法称为设备的虚拟分配
• 虚拟设备
  • 通常把用来代替独占型设备的那部分外存空间(包括有关的控制表格)称为虚拟设备

SPOOLING系统#

Simultaneous Peripheral Operations On Line系统，也叫假脱机系统，为用户提供外围设备同时联机操作的功能

• 设计思想
  • 预输入
    • 在应用程序需要数据前，OS已将所需数据预先输入到辅存输入井存放。当应用程序(或进程)需要数据时，可直接从辅存中读入主存
  • 缓输出
    • 在应用程序执行时，将输出数据写入辅存输出井中。当应用程序(或进程)执行完毕(或需要数据时候)，由操作系统将数据输出
• SPOOLING
  • 利用通道和中断技术，在主机控制之下，由通道完成输入输出工作。
  • 系统提供一个软件系统(包括预输入程序、缓输出程序、井管理程序、预输入表、缓输出表)。
  • 它提供输入收存和输出发送的功能，使外部设备可以并性操作
• 优点
  • 提供虚拟设备
  • 外围设备同时联机操作
  • 加快作业处理速度
• 实现
  • 大容量的辅存空间
    • 在辅存上需要开辟两个较大的输入和输出井，用以存放大量应用程序的输入信息和输出信息
  • 硬件基础
    • 通道装置、中断系统
  • 数据结构
    • 预输入表、缓输出表: 描述辅存输入井和输出井的状态变化
  • 软件
    • 预输入软件: 控制信息从独占设备输入到辅存
    • 缓输出程序: 控制信息从辅存输出到独占设备
    • 井管理程序: 控制用户程序和辅存之间的信息交换

文件#

• 文件: 在逻辑上具有完整意义的信息集合，有一个名字以供标识，文件名是由若干约束的字符串
  • 特点: 可以长期保存、可以在进程间共享、具有内部结构
• 构成文件的基本单位: 信息项(单个字节或字符)、记录
• 文件的其它描述
  • 文件是就有符号名的信息(数据项)的集合
  • 文件是具有符号名的记录的集合
• 分类
  • 按文件的性质和用途分类: 系统文件、程序库文件、用户文件
  • 按文件保护级分类: 不保护文件、执行文件、只读文件、读写文件
  • 按文件刘翔分类: 输入文件、输出文件、输入输出文件
• 文件名与属性
  • 文件名: 每个文件有一个给定的名字，包括文件符号名和内部标识符
  • 文件扩展名: 表示文件的使用特征
  • 文件属性: 表示文件类别、保护级等信息

文件系统#

• 定义: 文件系统是操作系统中负责管理和存取文件信息的软件机构
• 组成
  • 管理文件所需的数据结构: 如目录表、文件控制块、存储分配表
  • 管理程序
  • 一组操作
• 文件系统的功能
  • 从用户角度看: 文件系统实现了“按名存取”的功能
  • 从系统角度看: 文件系统提供的功能包括: 辅存空间管理、构造文件结构、文件共享、存取文件的方法、文件保护、一组文件操作命令
• 特点
  • 使用简单: 使用文件名、一组文件操作命令
  • 安全可靠:
    • 提供防护措施，在文件遭受破坏时，能及时修复
    • 全量备份、增量备份、动态备份、远程备份
  • 既能共享，又能保密: 身份验证、存取权限验证

文件系统的两种结构#

• 逻辑结构
  • 从用户角度看到的文件面貌，即用户对信息进行逻辑组织的文件结构
  • 为用户提供一种逻辑结构清晰、使用简单的逻辑文件形式
  • 用户按文件的逻辑结构形式取存储、检索和加工文件中的信息
• 物理结构
  • 信息在物理存储器上的存储方式，是数据的物理表示和组织
  • 选则工作性能良好、设备利用率高的物理文件形式
  • 系统按照文件的蓄力结构形式和外部设备打交道，控制信息的传输
• 逻辑记录与物理记录(磁盘块)
  • 逻辑记录: 文件中按信息在逻辑上的独立含义来划分的信息单位，逻辑记录是对文件进行存取操作的基本单位
  • 物理记录: 在存储截至上，由连续信息所组成的一个区称为块，也叫物理记录
  • 逻辑记录与物理记录的区别与联系
    • 一个是逻辑的概念，一个是物理的概念
    • 逻辑记录最终要存放到物理记录上

文件的逻辑结构#

• 流式文件
  • 定义: 流式文件是相关的有序字符的集合，是无结构的
  • 存取方法: 流式文件是按信息的个数或以特殊字符为界进行存取的
• 记录式文件
  • 定义: 记录式文件是一种有结构的文件，这种文件在逻辑上总是被看成是一组连续顺序的记录的集合
  • 定长记录与变长记录

文件存取方法#

• 顺序存取
  • 后一次存取总是在前一次存取的基础上进行的
  • 顺序存取时不必给出具体的存取位置
• 随机存取
  • 用户以任意次序请求某个记录
  • 随机存取时要指出起始存取位置

基本概念#

• 块是存储介质上连续信息所组成的一个区域，也叫物理记录
• 间隙是块之间不记录用户代码信息的区域
• 块是主存和辅存间信息交换的物理单位，每次交换一块或整数块
• 不同类型的存介质，块的大小常常各不相同；同一类型的存储截至，块的大小也可以不同
• 块的大小要考虑到用户使用方式、数据传输效率和存储设备类型等多种因素

连续文件#

• 连续文件结构是由一组分配在磁盘连续区域的物理块组成的
• 特点:
  • 存取速度较快
  • 文件长度一经固定便不易改变
  • 文件的增生和扩容不易

串联文件#

• 由按属于内需串联的块组成，即文件的信息存于若干个物理块中，每个物理块的最末一个字作为链接字，指出后续块的物理地址。文件的最后一块的链接字为结束标记”^“，它表示文件至本块结束
• 特点
  • 能较好利用辅存空间
  • 易于对文件进行增生和扩容
  • 连续存取速度较快，随机存取速度慢

文件映照#

• 把串联文件中的链接字集中在一个结构中，既保持了串联文件的优点，也克服了其随机存取速度慢的缺点，就是FAT文件
• 文件分配表FAT是以链接方式存取文件的系统中记录磁盘分配和跟踪空白磁盘(蔟)的数据结构
• 该表在文件系统格式化后产生，共包含N个表项，每个表项对应一个蔟，编号从0开始直至N-14(N为磁盘中蔟的总数)
• 每个表项中的内容为存放文件数据的下一个蔟的蔟号
• 文件的首地址(第一个蔟号)存放在目录中。因此，从目录中找到文件的首地址后，就能找到文件在磁盘上的所有存放地址

索引文件#

• 系统为每个文件建立逻辑块号与物理块号的对照表，这张表称为该文件的索引表
• 索引文件由数据块和索引表构成
• 操作
  • 索引文件在存储区中占两个区
    • 索引区: 存放索引表
    • 数据区: 存放数据文件
  • 访问索引文件的操作
    • 查文件的索引表，由逻辑块号查得物理块号
    • 由物理块号而获得所要求的数据
• 特点
  • 易于文件的增删
  • 直接读写任意记录
• 组织
  • 直接索引: 文件目录项中有一组表项用于索引，登记逻辑记录所在的磁盘块号
  • 一级间接索引: 文件目录项中有一组表项，其内容等级的是第一季索引表块的块号。第一季索引表块号中的索引表项等级的是文件逻辑记录所在的磁盘块号
  • 二级间接索引: 文件目录项中有一组表项，其内容等级的是第二级索引表块的块号。第二季索引表块中的索引表项等级的是第一季索引表块的块号，第一季索引表项中等级的是文件逻辑记录所在的磁盘块号

几种文件物理结构的比较#

• 连续文件
  • 优点: 不需要额外空间开销，顺序访问和随机访问的效率都高
  • 缺点: 动态增长困难；要求用户创建时提供文件大小；存储空间浪费较大
  • 适合长度固定不变的只读文件的存储
• 串联文件
  • 克服了连续文件的不足；但随机访问的系统开销过大；适应于顺序访问的文件
  • DOS及WINDOWS系统中改造了串联文件结构，使其克服了串联文件的不足，但增加了系统的危险性
• 索引文件
  • 既适用于顺序访问，也适用于随机访问；但索引表需要存储开销和访问时间开销
  • UNIX系统是适用索引结构

位示图法#

• 磁盘空间由固定大小的块组成，可方便地适用位示图管理
• 每一位对应一个物理块，1表示被占用，0表示空闲
• 优点
  • 每个盘块仅需要1bit来标识
  • 若盘块长为1KB，则位视图开销位0.012%
• 缺点: 对于大容量磁盘，位示图的存储和查找考校较大，需要建立辅助存储统计表来提高访问速度

空闲文件目录#

• 将空闲区存储块的位置及其连续空闲的块数构成一张表
• 分配时，依次扫描空闲区表，寻找合适的空闲块并修改登记项
• 删除文件并释放空闲区时，把空闲位置及连续空闲区长度填入空闲区表，出现邻接的空闲区时，还需要执行合并操作
• 适用于连续文件结构
• 缺点: 碎片问题

空闲块链#

• 把所有空闲块连接在一起，系统保持指针指向第一个空闲块，每一个空闲块中包含指向下一个空闲块的指针
• 申请一个空闲块时，从链头取一块修改系统指针
• 释放占用块时，将其挂到空闲链的链头，并修改系统指针指向它
• 优点: 几乎不需要占用空间
• 缺点: 分配多块时效率低(需要I/O操作)
• UNIX文件系统对这种方法进行了改进，在一个空闲块中保存一组空闲块指针，称链成组链接法

文件控制块#

• 文件控制块(FCB)是文件系统位每个文件建立的位移的管理数据结构
  • 文件标识和控制信息: 文件名、用户名、文件存取权限、访问控制权限、文件类型等
  • 文件逻辑结构信息: 记录类型、记录个数、记录长度、成组银子等
  • 文件物理结构信息: 文件所在设备名、文件物理结构类型、记录存放在辅存中的块号或文件信息首块盘块号，文件索引的位置等
  • 文件适用信息: 共享文件的进程数，文件修改情况，文件最大长度和当前大小
  • 文件管理信息: 文件建立日期，最近修改日期，最近访问日期等

文件目录#

• 文件系统基于FCB来实现文件的按名存取
  • 创建文件时，为其建立FCB，用来记录文件的属性信息
  • 存取文件时，先找到其FCB，再来找到文件信息盘块号或首块物理位置
• 为了加快文件的查找速度，通常将FCB集中起来，组成文件目录
• 文件目录包含至少两种目录选项: 普通文件的FCB、子目录的目录文件的FCB
• 目录文件至少包含两个目录项
  • 当前目录项 .
  • 父目录项 ..
• 文件目录的基本功能
  • 将文件名转换成此文件信息在磁盘上的物理位置
  • 有效的组织和管理文件

文件共享与文件保护#

• 保护
  • 操作前先对用户的权限进行验证
  • 所谓存取权限的验证，是指用户存取文件之前，需要检查用户的存取权限是否符合规定，符合者允许适用，否则据绝
• 验证用户存取权限的方法
  • 访问控制矩阵
  • 存取控制表
  • 用户权限表
  • 口令
  • 密码
• 加快文件的查找
  • 当前目录(值班目录)
    • 当指定当前目录后，用户对文件的所有访问都是相对于当前目录进行的
  • 链接技术: 在相应目录表目之间进行连接，即个不路中的表目直接指向另一个目表所在的物理位置

Linux的链接文件#

文件操作#

• 常用的文件操作命令
  • create 创建一个新文件
  • delete 从系统目录中撤销一个文件
  • rename 在系统目录中改变文件的名字
  • open 打开文件，在用户和文件(或设备)之间建立一个逻辑通路
  • close 关闭文件，在用户和文件(或设备)之间撤销一个逻辑通路
  • write 写到一个文件(或设备)上
  • read 从一个文件(或设备)读入数据信息
• 打开文件和关闭文件操作
  • 打开文件操作: 把该文件的有关目录表目复制到主存中的约定区域，建立文件控制块，建立用户和这个文件的联系
  • 关闭文件操作: 用户宣布这个文件当前不再适用，系统将其在主存中的文件控制块山区，因而也就切断了用户同这个文件的联系
• 文件备份: 为了能在软、硬件实现的以外情况下恢复文件，保证文件的完整性、数据的连续可利用性，文件系统提供适当的机构，以便复制备份
  • 周期性转储: 按固定的时间周期把存储器中所有文件的内容转存到某种截至上，通常是磁带或磁盘。在系统失效时，使用这些转存磁盘或磁带，将所有文件重新建立并恢复到最后一次转存时的状态
  • 增量型转储: 只转储从上次转储以后已经改变过的信息，增量转储的信息量较小，故转储可在更短的时间周期内进行
  • 文件备份技术的发展: 动态备份，远程备份技术

概述#

• 特点
  • 树形文件目录结构
  • 可安装拆卸的文件系统
  • 文件是无结构的字节流式文件
  • 将外部设备与文件一样对待
• 类型
  • 普通文件: 用户程序、数据文件
  • 目录文件: 用于组织和形成树形目录结构中的一个单位，由若干目录项组成
  • 特别文件: 与硬件设备有关的文件称为特别文件。包括块设备文件、字符设备文件。与计算机链接每一种输入输出设备都有一个特别文件。它式操作系统核心用于存取输入输出设备的通道，是用户与硬件设备联系的桥梁
  • 命名管道: 管道是一种进程间通信机制。管道中缓存了从输入端接收的数据，这样从输入端读数据的进程就能以先进先出的方式来接收数据
  • 链接文件: 本质上，链接文件是一个已存在的文件的另一个文件名
  • 符号链接: 者是一个数据文件，文件中包含了其所链接的那个文件的名字

UNIX系统的索引文件结构#

• 文件索引节点
  • UNIX系统把文件目录项中除了名字以外的信息全部存放到一个磁盘的数据块上，这种数据块称为磁盘索引节点(index node)，简称i节点(inode)
  • 结构
    • 文件所有者标识: 定义对一个文件具有存取权的用户集合，分为文件所有者、文件所有者用户组
    • 文件类型: 分为正规文件、目录文件、字符特殊文件或块特殊文件等
    • 文件存取许可权: 按文件所有者、文件的用户组所有者及其它用户三个类别对文件实行保护，每类都具有读、写、执行该文件的存取全，并且能分别地设置
    • 文件链接数目: 表示在文件目录结构中，有多少个文件名指向该文件。每当增加一个名字时，i_ilink值+1，减少一个名字是其值-1.当其值减为0时，该文件才能真正删除
    • 地址索引表: 文件数据的磁盘地址信息，即地址索引表，

UNIX系统文件目录结构#

• 目录文件与目录项
  • 目录文件: 每个目录表为一个目录文件。目录文件由目录项组成
  • 目录项: 每个目录项包含16个字节(UNIX老版本)。在目录项中，低1，2字节为响应文件的辅存i节点号，后14个字节为文件名。一个辅存磁盘块(512B)包含32个目录项
• 树形目录结构
  • 每个文件系统都有一个根目录文件，它的辅存i节点是相应文件存储设备上辅存索引区中的第一个
  • 打开某个文件时，从根目录的i节点可以找到根目录文件的索引结构，得到根目录文件的每个数据块
  • 将待打开文件的路径信息与目录文件中的目录项逐一比较，可以得到下级目录的i节点号，并最终得到目标文件的i节点号。从i节点号中的索引表，得到数据文件的存储块号，实现对目标文件的随机存取
• 文件目录结构中的链接
  • Unix文件目录结构中带有交叉连接。用户可以用不同的文件路径名共享一个文件
  • 文件连接在用户看来是为一个已存在的文件另起一个路路径名
  • 文件连接的结果表现为一个文件由多个目录项所指向

Unix系统的打开文件机构#

• 为了提高系统效率，减少主存空间的占用，系统设置了打开文件和关闭文件操作。当打开一个文件时，建立用户与该文件的联系
• 文件系统中管理这一工作的结构称为打开文件机构。打开文件机构由活动i节点表、打开文件表和用户文件描述符表组成
• 活动i节点表
  • 当执行打开文件操作时，将文件辅存i节点的有关信息拷贝到主存，形成活动i节点(主存索引节点)，若干个活动i节点组成活动i节点
• 系统打开文件表
  • 一个文件可以被同一进程或不同进程，用同一或不同路径名，相同的或互异的操作要求(读、写)同时打开。为了记录打开文件所需的附加信息，文件系统设置了一个内核结构: 系统打开文件表
• 用户文件描述符表
  • 用户进程扩充块user中的一个数组u_ofile[NOFILE]称为用户文件描述符表，其中的每一项(指针)指向系统打开文件表的一个表项
  • 一个打开文件在用户文件描述表中所占的文职就是它的文件描述符(或称打开文件号)。进程可以打开不同的文件，也可以对统一文件以不同的操作方式打开

文件存储器空闲块的管理#

• 文件卷和卷管理块: 一个文件系统就是逻辑设备，每个逻辑设备占用一片连续的磁盘存储空间。文件卷上存放UNIX文件系统。 文件卷的结构 |引导块|管理块|索引节点区|数据区| |:—|:—|:—|:—| |大小为一个磁盘块，包含引导程序|记录文件系统各种数据，如文件系统大小、空闲块数目等|索引节点结构组成|数据文件占用的区域|
• 空闲磁盘块的管理
  • UNIX的空闲磁盘块管理采用成组连接法，即将空闲表和空闲连两种方法相结合
  • 系统初启动时，文件存储区是空闲的，将空闲块从尾倒向前，每100块分为一组(最后一组99块)，每一组的最后一块作为索引表，用来等级下一组100块的物理块号和块数
  • 最前面一组(可能不足100块)的物理块号和块数存放在管理块的s_free[100]和s_nfree中
• 空闲块的分配算法
  • 检查管理块的空闲块号栈是否已经上锁(邻接资源)，若已上锁则进程睡眠等待
  • 给空闲磁盘块号栈上锁后，将s_nfree减1，若s_nfree仍大于0，即栈中还剩布置一个空闲块，则将s_free[s_nfree]中等级的空闲盘块分配出去
  • 若s_nfree为0，即当前空闲盘块号栈中只剩下最后一个空闲盘块，必须先将该盘块的内容读入管理块的空闲盘块号栈中，然后再将该盘块分配湖区。若s_nfree为0，而且栈底等级的盘块号为0，则表示系统中无空闲盘块可分配
• 空闲块的回收
  • 再系统回收空闲盘块时，将回收盘块的盘块号计入空闲盘块号栈的顶部，并执行空闲盘块数加1操作
  • 当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记如新回收的盘块中，再将盘块号作为新栈底