计算机操作系统大纲

[lightman]

<计算机操作系统>大纲和要点(以考试内容为主

第一章 绪论

操作系统的地位

• 存储程序式计算机(冯诺依曼):

  存储器, 运算器, 控制部件, io

  • 主存 MAR, MDR, CR
  • CPU ALU, 控制单元(PC, IR)
  • io

操作系统的形成发展

• 元器件

  • 电子管时代
  • 集成电路时代
  • 超大规模集成电路时代

• 操作系统阶段

  • 操作系统初级阶段

    监督程序

    • 早期批处理

      为了解决人机矛盾

    • 脱机批处理

      为了解决 CPU 高速与 io 低速的矛盾, 但是 cpu 在输入输出是会空闲

      由主机和卫星机组成

    • 执行系统

      通道和中断

      • 通道: 负责外部设备与主存之间的信息传递
      • 中断: 就是中断, interrupt

  • 操作系统的形成

    • 多道程序设计技术

      为了解决 cpu 空闲的问题, 多个独立程序相互穿插运行, 使得 cpu 和外部设备尽可能并行操作

      • 特征: 多道, 宏观上并行, 微观上还是串行

    • 分时技术

      为了解决用户不能直接控制程序运行的问题, 实现联机操作交互对话(用户使用计算机)

      分时技术使得每个终端用户在自己的终端设备上以联机方式使用计算机, 好像自己独占一样, 分时技术就是把时间分成片然后轮流分给用户

    出现了

    • 批量操作系统-->多道程序设计
    • 分时操作系统-->分时技术
    • 实时操作系统-->生产过程
      • "实时": 计算机对于外来信息能够在被控对象允许的截止期限内做出反应

  • 操作系统的进一步发展

    • 即, 现代操作系统

操作系统的概念

• <u>操作系统的特性</u>

  • 并发: 单机操作系统的并行性, 又叫并发性, 但是是逻辑上的并行, 物理上的串行
  • 共享
  • 不确定性(用户 xjer 操作)

• 操作系统的资源管理能力

  对系统资源实施管理和调度, 控制和协调并发活动, 对外提供用户界面

  • 处理机管理(cpu)
  • 存储器管理(主存)
    • 存储分配和存储无关性, 存储保护, 存储扩充
  • 设备管理
    • 设备无关性, 设备分配, 设备传输控制
  • 文件系统(file system)

• 操作系统应该解决的问题

  • 资源分配的方法和策略
    • 先来先服务
    • 显现调度
    • 时间片轮转
  • 协调并发活动
    • 锁, 上锁, 开锁
    • 信号灯, 信号灯上的 p 操作 v 操作
  • 保证数据一致性
  • 数据存取

☆操作系统基本类型

批量操作系统

• 多道程序设计, 将用户提交的作业成批输入计算机, 然后由作业调度程序自动选择作业运行
• 特点:
  • 吞吐率高
  • 作业周转时间长
  • 交互性差

分时操作系统

• 时间片轮转, 使一台机器同时为多个终端用户服务(联机方式)
• 特点
  • 并行性, 独占性, 交互性

实时操作系统

• 能够在 deadline 内处理完毕外部信息并作出反应

• 特点

  • 实时响应
  • 高可靠性, 安全性
  • 执行装置, 咨询装置

• 分类

  • 实时控制(工厂)
  • 实时信息处理(检索)

• 嵌入式操作系统(EOS)

  • 区别

    

个人计算机操作系统

都懂

网络操作系统

• 特点:

  1. 多个处理部件

  2. 无公共主存

  3. 消息通信机制

• 网络通信模块

分布式操作系统

• 与网络操作系统的区别
  • 计算机网络存取资源是不透明的, 分布式是透明的
  • 计算机网络合作计算需要用户分配, 分布式由系统分配
  • 分布式系统对用户完全透明

操作系统的关键技术

并行处理技术

虚拟技术

虚拟存储技术为主

UNIX, Linux

UNIX

• 特点
  • 核心层和使用层
  • shell
  • 层次式文件系统
  • 统一看待文件和设备
  • 可移植性

Linux

• 基础
  • UNIX
  • Minix
  • GNU
  • POSIX(portable operating system ix)
• 特点
  • 多用户, 多任务
• 系统组成
  • 内核: 多进程管理, 进程调度
  • shell
  • 实用工具

[gck]

这也太长了8 建议分p

[lightman]

第二章 操作系统的结构和硬件支持

操作系统虚拟机

在裸机上配置了操作系统后就构成了操作系统虚拟机

操作系统的核心在裸机上运行, 而用户程序则在扩充后的机器上运行

操作系统提供的全部命令的集合称为: 操作命令语言, 它分为

• 操作命令

  1. 键盘命令
  2. 作业控制语言
  3. 图形化用户界面

• 系统功能调用

  INT

操作系统的结构

操作系统由内核(核心层)和其他操作系统功能组成, 核心层包括处理器管理, 存储管理, 设备管理, 文件管理

四种设计方法

• 一体化结构

  过程间可以互相调用而不受约束

• 模块化结构

  功能是通过逻辑独立的模块来划分的

• 可扩展内核结构

  内核分为基础核心和其他核心功能两部分

• 层次化结构

运行时的组织结构

操作系统运行过程中调用一个给定的操作系统的内部例程有两种方式

• 系统功能调用方式 INT

• 客户/服务器方式

  将操作系统服务作为系统服务进程来提供, 服务请求和服务响应是通过消息传递方式来实现的

处理机的特权级

为了保护操作系统

☆处理机的态和分类

核态 > 管态 > 用户态

计算机系统中运行的程序可以分为两大类

• 操作系统的管理程序
• 用户程序

处理机的态, 又称处理机的特权级, 就是处理机当前处于何种状态, 正在执行哪类程序, 为了保护操作系统, 至少分为管态, 用户态两种状态

• 管态

  在此状态下中央处理机可以使用全部机器指令

• 用户态(目态)

  在此状态下禁止使用特权指令, 不能直接取用资源与改变机器状态, 并且只允许用户程序访问自己的存储区域

• 核态

  具有管态的所有权限. 此时管态的权限有所变化: 管态允许使用一些在用户态下所不能使用的资源, 但不能使用修改机器的状态指令

特权指令

FLAG: IOPL 位, IO 特权

这些特权指令设计如下方面

1. 改变机器状态的指令
2. 修改特殊寄存器的指令
3. 设计外部设备的输入输出指令

在下列情况下有用户态自动转向管态(中断发生, 中断返回)

1. 用户进程访问操作系统, 要求操作系统的某种服务, 这种访问称为<u>系统功能调用</u>
2. 在用户程序执行时, 发生一次中断
3. 在一个用户进程中产生一个错误状态, 这种状态被处理为程序性中断
4. 在用户态下企图执行一条特权指令, 作为一种特殊类型的错误, 按照情况三处理

中断及其处理

概念

指某个时间发生时, 系统终止现行程序的运行, 引出处理该事件的程序进行处理, 处理完毕后返回断点继续执行

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gk9jczvbcrj30rs0sx1cl.jpg" alt="image-20201101115909104" style="zoom:25%;" />

类型

按照功能分类

1. <u>输入输出中断</u>
2. <u>外中断: 如时钟中断, 操作员控制台中断</u>
3. <u>机器故障中断: 如电源故障</u>
4. <u>程序性中断: 程序性质的错误</u>
5. <u>访管中断: 对操作系统提出某种需求(INT)时所发出的中断</u>

按照中断方式分类

1. 强迫性中断: 由某种事故或外部请求信号引起的
2. 自愿中断(INT): 这种事件是由于运行程序请求操作系统服务引起的

按照中断来源分类

1. 外中断(中断): 由处理机外部事件引起的中断成为外中断, 在 x86 中称为异步中断. 包括 I/O中断, 外中断
2. 俘获: 由处理机内部时间引起的中断成为俘获, x86 中称为异常, 也成同步中断. 包括访管中断, 程序性中断, 机器故障中断

向量中断

向量中断: 硬件提供入口地址, 非向量中断: 只有一个入口地址, 软件通过标志位进行判断是哪个中断

由中断源自己引导处理机进入中断服务程序的中断过程称为向量中断

中断向量包含两个字: 第一个字含有中断服务例程的入口地址, 第二个字是服务程序所用的处理机状态字

所有中断向量放在一起组成中断向量表

中断进入

发现中断源而产生中断过程的设备称为中断装置(中断器)

1. 保护现场和恢复现场

2. 程序状态字: 主要包括: 程序当前应执行的指令, 当前指令执行情况, 处理机所在状态, 程序在执行时应屏蔽的中断, 寻址方法编址保护键, 响应中断的内容, 小型机(X86)包括 CS:IP 和 FLAGS

3. 中断响应: 中断响应的实质是交换 用户程序和处理该中断事件的中断程序的 指令执行地址和处理器状态

   <img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gk9jsya3zjj31i70rs4qp.jpg" alt="image-20201101121433659" style="zoom:50%;" />

硬件负责中断的发现, 响应中断请求, 把中断的原因和断点记下来供软件处理时查用;

软件的中断处理程序负责中断分析, 中断处理

☆软件中断处理过程

包括三步

1. 保护现场和传递参数
2. 执行响应的中断(自陷)服务例程
3. 恢复和退出中断

中断服务的主要内容

• 硬件故障的中断处理
• 程序性中断事件的处理
• 外部中断时间的处理
  • 时钟中断事件的处理
  • 控制台中断事件的处理
• 外部设备中断的处理
  • 传输结束中断的处理
  • 传输错误中断的处理
  • 故障中断的处理

UNIX Linux 系统结构

UNIX 系统的体系结构

UNIX 的系统核心层的功能包括文件管理, 设备管理, 存储管理, 处理机管理

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gk9k8exdzoj30yp0rs7u2.jpg" alt="image-20201101122924852" style="zoom:33%;" />

Linux 系统的内核结构

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gk9kb3ht5ej313t0rse58.jpg" alt="image-20201101123159716" style="zoom:33%;" />

Linux 系统的特权级与中断处理

Inter i386: 实模式, 保护模式

实模式: 只能使用实地址访问主存, 没有安全保护措施

保护模式: 处理机提供 4 个特权级, Linux 使用两个: 特权级 0(核模式), 特权级 3(用户模式)

中断处理的上半部和下半部

Linux 的中断处理有自己的特色: 分为上半部和下半部, 将中断响应后必须立即处理的工作即刻执行, 而将更多的处理工作向后推迟执行

上半部

中断处理程序的上半部是中断处理中又严格时间限制的工作, 是关键而紧迫的部分, 上半部的工作是不可打断的

下半部

下半部的执行时可以被打断的

实现机制主要有两种: tasklet 和工作队列

• tasklet

  软中断是利用硬件中断的概念，用软件方式进行模拟，实现宏观上的异步执行效果。很多情况下，软中断和"信号"有些类似，同时，软中断又是和硬中断相对应的，"硬中断是外部设备对CPU的中断"，"软中断通常是硬中断服务程序对内核的中断"，"信号则是由内核（或其他进程）对某个进程的中断"。

  百度百科

  通过软中断(信号机制)实现, 详情不列

• 工作队列

  工作队列机制将中断处理程序的下半部交给一个内核线程去执行

[lightman]

@gck 好的好的

[lightman]

第三章 操作系统的用户接口

用户工作环境

操作系统提供的环境:

1. 提供各种软硬件资源
2. 设计操作系统的命令集
3. 系统初启

☆操作系统的生成和系统初启

系统生成(计算机厂商)

系统生成程序: SYSGEN

系统生成必须确定以下信息:

1. 使用的 CPU 类型, 需要安装的选项(如扩展指令集, 浮点运算操作)
2. 可用主存空间
3. 可用设备
4. 操作系统选项和参数值(如支持进程的最大数量, 进程调度策略的类型, 需要的缓冲区的大小)

系统初始启动(系统引导), 如关机后

• 初始启动三个阶段

  1. 初始引导: 把系统核心装入主存中的指定位置, 并在指定地址启动
  2. 核心初始化: 执行系统核心的初始启动子程序, 初始化系统核心参数
  3. 系统初始化: 为用户使用系统做准备(如建立文件系统, 建立日历时钟)

  之后用户就可以使用计算机系统了

• 系统引导的方式

  • 独立引导(滚雪球)bootup

    操作系统的核心文件存储在系统本身的存储设备中, 由操作系统自己将操作系统核心程序读入主存并运行

    过程:

    1. 初始引导(自举)

       自举是操作系统通过滚雪球的方式将自己建立起来的过程

       主要任务就是把系统核心送入主存并启动它运行

       启动需要一个小程序: 引导程序

       在大多数机器的只读存储器(ROM只读存储器, PROM可编程只读存储器, EPROM可擦除可编程只读存储器)中有一段用于初始引导的代码, 当系统加电或者按下某个按钮时自动将这段程序读入主存

       初始引导的步骤:

       1. 系统加电
       2. 执行初始引导程序
       3. 从硬盘中读入操作系统引导程序

    2. 引导程序的执行

    3. 核心初始化

       1. 建立进程有关的数据结构
       2. 获得自由存储空间的容量
       3. 建立系统设备和文件系统的数据结构
       4. 初始化时钟

    4. 系统初始化

  • 辅助下装方式 download

    从另外的计算机系统中将操作系统常驻部分传到该计算机中

  • Linux 系统的引导

    linux 系统是滚雪球方式启动的

    过程:

    1. 系统加电或者复位
    2. BIOS(Basic Input Output System) 启动(在 ROM 中的引导程序放在固定位置:FFFF:0000)
       1. 上电自检
       2. 对硬件设备检测和链接
       3. 从盘中读入引导程序
    3. 引导程序执行
    4. 核心及系统初始化(过程略)

应用程序的处理

编辑, 编译, 连接, 运行

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gk9zjg7bbwj324s0rsb29.jpg" alt="image-20201101211858528" style="zoom: 25%;" />

连接类型:

静态连接

写进目标文件

动态链接

在调用外部函数的地方做记录, dll 动态链接库

用户接口

用户接口分类: 操作接口(操作命令)(用户通过此来组织自己的工作流程和控制程序的运行), 程序接口(系统功能调用)(用户程序可以调用的服务)

• 操作接口:

• 程序接口:

系统功能调用

定义: 用户程序对操作系统例行子程序的调用应以一种特殊的调用方式, 就是访管方式来实现(用户态和管态之间的转换) svc n

当处理机执行到访管指令时就发生访管中断

☆系统功能调用的实现

一个带有一定功能号的访管指令定义了一个系统调用, 系统调用是利用访管指令定义的命令

实现这种服务是由 SSR(系统服务请求)机构 来实现的

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka05sph7fj31g40rsx5f.jpg" alt="image-20201101214029068" style="zoom:25%;" />

UNIX 系统功能调用

分类: 进程管理, 文件和外设管理, 系统状态

UNIX 系统功能调用的实现

• 访管指令trap是俘获的一种

• 系统调用入口地址表

• 系统调用实现过程

  <img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka0d393okj31ge0rs1kt.jpg" alt="image-20201101214729668" style="zoom:25%;" />

Linux 系统功能调用

linux 中系统调用是通过异常实现的

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka0g52u4pj31kc0rs1kx.jpg" alt="image-20201101215025303" style="zoom:25%;" />

Linux 系统功能调用的实现机制

• 系统调用进入 int 0x80

• 系统调用号和系统调用表

  每个系统调用被赋予唯一的系统调用号, 定义在文件: include/asm-i386/unistd.h

  系统调用表记录了内核中所有已经注册过的系统调用, 保存在文件 arch/i386/kernel/entry.S

• 系统调用处理程序system_call()

  1. SAVE_ALL 保护现场
  2. 进行系统调用正确检查
  3. 调用服务例程
  4. RESRORE_ALL 恢复现场, iret 返回

Linux 增加新的系统调用

eg. 新增加的系统调用名为mysyscall, 系统调用编号名__NR_mysyscall, 服务例程名sys_mysysycall

步骤

1. 添加新的服务例程

   在/usr/src/linux/kernel/sys.c 文件中新增一个函数

   asmlinkage int sys_mysyscall(int number){
     return number;
   }
   

2. 增加新的系统调用号

   在 include/asm-i386/unistd.h 增加

   #define __NR_mysyscall XX
   

3. 修改系统调用表

   在文件 /arch/i386/kernel/entry.S 的 sys_call_table 中增加

   ENTRY(sys_call_table)
     .long sys_restart_syscall
     //...
     .long sys_mysyscall //新增
   

4. 重新编译内核并启动新内核

[lightman]

第四章 进程及进程管理

进程引入

顺序程序

程序是为解决某一问题而设计的一系列指令的集合, 是算法的形式化描述

特点: 顺序性, 封闭性, 可再现性

并发程序

定义: 程序的并发执行是指, 若干个程序同时在系统中运行 这些程序的执行在时间上是重叠的, 一个程序的执行尚未结束, 另一个程序的执行已经开始

cobegin
	S1; S2; S3...
coend

特点:

1. 失去程序的封闭性(公共变量)

2. 程序与计算不再一一对应

   当多个计算任务共享某个程序时, 他们都可以调用这个程序

3. 程序并发执行时的相互制约关系

与时间有关的错误

进程概念

定义

执行中的程序

1. 进程是这样的计算部分: 他是可以和其他计算并行的一个计算
2. 进程是一个程序与其数据一道通过处理机的执行所发生的活动
3. 进程是由一个程序以及与他相关的状态信息所组成的
4. 进程就是一个程序在给定活动空间和初始环境下, 在一个处理机上的执行过程
5. 进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动

进程和程序的区别:

1. 程序是指令的有序集合, 是一个静态概念, 进程是程序在处理机上的一次执行过程
2. 进程是一个能独立运行的单位
3. 进程是竞争计算机系统有限资源的基本单位, 也是进行处理机调度的基本单位

为了描述进程, 人们提出了一个数据结构: 进程控制块

进程的状态及变迁

进程的基本状态

• 就绪状态

  进程获得除了 cpu 以外的所有资源

• 运行状态

  得到了 cpu 的控制权限

• 等待状态(阻塞状态)

  若一进程正在等待某一时间发生而暂时停止执行, 这时, 即使给他 cpu 控制权, 他也无法执行

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka1uaxnjnj31jv0rskjl.jpg" alt="image-20201101223838478" style="zoom:25%;" />

进程控制块(PCB process control block)

内容:

1. 进程标识符

2. 进程的状态

3. 当前队列指针 next

   通常把具有相同转台的进程链在一起, 组成队列

4. 进程优先级

5. CPU 现场保护区

6. 通信信息

7. 家族联系(如子进程和父进程的标识符)

8. 占有资源清单

进程控制

包括: 创建进程, 撤销进程, 进程等待, 进程唤醒

通过原语(一种特殊的系统调用, 他可以完成一个特定功能, 一般为外层软件所调用, 其特点是原语执行时不可中断, 具有原子性)来实现控制和管理的目的

进程创建 fork()

进程撤销 kill()

进程等待 susp(chan)

chan: 进程等待的原因

将现行进程的 cpu现场保护到 PCB 结构中

进程唤醒 wakeup(chan)

chan: 进程等待的原因

进程之间的约束关系

进程竞争

进程协作

有以下两种情况需要合作

1. 信息共享
2. 并行处理

协调进程之间的协作需要进程同步, 进程同步需要进程通信

进程同步概念

进程同步可以分为: 进程互斥, 进程同步, 进程的直接通信

进程互斥

A 和 B 不能在同一时间执行

临界资源: 通常把一次仅允许一个进程使用的资源叫做临界资源

临界区: 一组进程共享某一临界资源, 这组进程中的每个进程对应的程序中都包含了一个访问该临界资源的程序段, 这段程序成为临界区或临界段

进程同步

保证进程之间操作的先后次序的约束, 所谓同步, 就是并发进程在一些关键点上可能需要互相等待与互通消息, 这种互相制约的等待与互通消息称为进程同步

同步机构

操作系统提供的同步机构有两种

1. 锁和上锁, 开锁操作
2. 信号灯(信号量)和 P, V 操作

锁和上锁, 开锁操作

对于每一个共享的临界资源都要有一个单独的锁位, 0 可用 1 已占用

进程使用共享资源之前必须进行一下操作, 称为关锁

1. 检测锁位的值
2. 是 0 则置为 1
3. 是 1 则返回 1.再考察

lock(){
  while(w==1){
    保护现场;
    将现行进程的 pcb 插入 w 的等待队列;
    将该进程置为等待;
    转进程调度;
  }
  w = 1;
}

unlock(){
  if (w 等待队列不为空){
 		移除等待队列首元素;
    将该进程的 pcb 插入就绪队列;
    置该进程为就绪;
  }
  w = 0;
}

信号灯(信号量)和 P, V 操作

信号灯

信号灯是一个确定的二元组(s, q)
s(信号灯) 是一个非负初值的整型变量, 代表资源的实体或并发进程的状态
q 是一个初始状态为空的队列

当 s>=0 时为绿灯, 进程可以继续推进, s<0 为红灯, 进程被阻, 信号灯的值通过 PV 操作改变

P(-1)

P(){
  s--;
  if(s<0){
    保留调用进程现场;
    将该进程的 pcb 插入 s 的等待队列;
    置该进程为等待;
    转进程调度;
  }
}

V(+1)

V(){
  s++;
  if(s<=0){
    移除 s 等待队列首元素;
    将该进程的 pcb 插入就绪队列;
    置该进程为就绪;
  }
}

进程互斥与同步的实现

上锁开锁实现进程互斥

main(){
  int w = 0;
  cobegin
    pp1();
  	pp2();
  coend
}

pp1(){
  ...
  lock(w);
  cs1;//临界区 1
  unlock(w);
  ...
}

pp2(){
  ...
  lock(w);
  cs2;//临界区 2
  unlock(w);
  ...
}

信号灯实现进程互斥

设互斥信号灯为 mutex(mutual exclusion), 赋初值为 1

进入临界区的操作置于 P(mutex)和 V(mutex)之间即可

对于两个并发进程, 互斥信号灯的取值仅为 1, 0, -1

mutext = 1 没有进程进入临界区

mutext = 0 一个进程进入临界区

mutext = -1 一个进程进入临界区, 另一个等待进入

信号灯实现进程同步

main(){
  int s1 = 0;//有无化验单
  int s2 = 0;//有无化验结果
  cobegin
    labora();//化验
    diagnosis();//看病
}

labora(){
  while(化验工作未完成){
  	p(s1);//询问有无化验单
    化验工作;
    v(s2);//送出化验结果
  }
}

diagnosis(){
  while(看病工作未完成){
    看病;
  	v(s1);//送出化验单
    p(s2);//等化验结果
    诊断;
  }
}

合作进程的执行次序

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka3jglo8jj30t10rsn8t.jpg" alt="image-20201101233724704" style="zoom:20%;" />

main(){
  int sb = 0;
  int sc = 0;
  cobegin
    pa();
  	pb();
  	pc();
  coend
}

pa(){
  ...
  v(sb);
  v(sc);
  ...
}

pb(){
  p(sb);
  ...
}

pc(){
  p(sc);
  ...
}

共享缓冲区的合作进程的同步

main(){
  int sa = 0;//buf 中有信息
  int sb = 1;//buf 中无空位置
  cobegin
    cp();//计算进程
  	iop();//打印进程
  coend
}

cp(){
  while(计算未完成){
  	得到一个计算结果;
    p(sb);
    将数据送到缓冲区中;
    v(sa);
  }
}

iop(){
  while(打印工作未完成){
    p(sa);
    从缓冲区取一个数;
    v(sb);
    在打印机上输出;
  }
}

生产者消费者问题

main(){
  int full = 0;//满缓冲区的数目
  int emtpy = n;//空缓冲区的数目
  int mutex = 1;//对有界缓冲区进行操作的互斥信号灯
  cobegin
    p1(),p2(),p3()...//生产者
    c1(),c2(),c3()...//消费者
  coend
}

producer(){
  while(生产未完成){
    ...
    生产一个产品;
    p(empty);
    p(mutex);
    送一个产品到有界缓冲区;
    v(mutex);
    v(full);
  }
}

consumer(){
  while(还要继续消费){
    p(full);
    p(mutex);
		从有界缓冲区中取产品;
    v(mutex);
    v(empty);
    ...
    消费一个产品
  }
}

进程通信(IPC interprocess communication)

进程通信方式

IPC 机制是消息(message)从一个进程的地址空间拷贝到另一个进程的地址空间的过程, 而不使用存储器的方法

1. 消息缓冲通信

   使用消息头

   包括消息缓冲, 发送原语和接受原语

2. 信箱通信

   包括信箱结构, 消息发送和接受

   分类: 信箱定义在用户空间和操作系统的空间

   <img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka4dnr7f1j31k10rs7wh.jpg" alt="image-20201102000626648" style="zoom: 25%;" />

   <img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka4envfg1j31f50rs4qc.jpg" alt="image-20201102000724924" style="zoom:25%;" />

线程的概念和特点

在传统操作系统中, 每个进程只存在一条控制线索和一个程序计数器, 现代操作系统中, 有些提供了对单个进程中多条控制线索的支持, 这些控制线索通常称为线程, 也叫轻量级进程

线程是进程的一个执行路径

对于线程的描述:

1. 线程是进程中的一条执行路径
2. 他有自己私用的堆栈和处理机执行环境
3. 他共享父进程的主存
4. 他是单个进程所创建的许多个同时存在的线程中的一个

进一步可以将进程的组成概括为以下:

1. 一个执行程序, 定义了初始代码和数据
2. 一个私用地址空间, 他是进程可以使用的一组虚拟主存地址
3. 进程执行时所需的系统资源是由操作系统分配给进程的
4. 若系统支持线程运行, 那么, 每个进程至少有一个执行线程

进程是任务调度的单位, 也是系统资源的分配单位;

线程是进程中的一条执行路径, 是任务调度的单位, 但不是系统资源的分配单位

线程完全继承父进程占有的资源, 当他活动时, 具有自己的运行现场, 有自己的堆栈

线程的特点

线程的状态变迁:

1. 创建
2. 就绪
3. 运行
4. 等待
5. 终止

用户线程和内核线程

• 用户线程: 是在内核的支持下, 用户层通过线程库实现的, 用户线程的创建和调度是在用户控件内形成的, 不需要内核干预
• 内核线程: 由操作系统直接支持, 对内核线程的管理是由操作系统完成的

操作系统的并发机制实例

创建进程

fork()

1. 为新锦成分配一个新的 PCB 结构
2. 为子进程赋一个惟一的进程标识号(PID)
3. 做一个父进程上下文的逻辑副本(增加引用数)
4. 增加与该进程相关联的文件表和索引节点表的引用数, 这意味着父进程打开的文件子进程可以继续使用
5. 对父进程返回子进程的进程号, 对子进程返回 0

创建线程

clone()

等待进程, 线程的终止及其应用

waitpid(pid_t pid, int *status, int options)

使得父进程暂停执行, 知道它的一个子进程结束为止

pid: 子进程的 PID

status: 子进程的退出码

信号量与使用方法

semget semop semctl

信号量的创建

int semget(key_t key, int num_sems, int sem_flags)

key: 用来允许多个进程访问相同信号量的整数值, 他们通过相同的 key 值来调用 semget()

num_sems: 所需要的信号量数目, semget()创建的是一个信号量数组, 数组元素个数为 num_sems

sem_flags: 标记集合

信号量控制

int semctl(int sem_id, int sem_num, int command, ...)

sem_id: semget()函数所获得的信号量标识符

sem_num: 信号量数组元素的下标, 即对第几个信号量进行控制

command: 要执行的动作, 常用的值有 SETVAL(用于为信号量赋初值), IPC_RMID(当信号量不再需要时用于删除一个信号量标识符)

信号量操作

int semop(int sem_id, struct sembuf *sem_ops, size_t num_sem_ops)

sem_id: 信号量标识符

sem_ops: 指向结构数组的指针

struct sembuf {
  short sem_num;//信号量数组下标
  short sem_op;//信号量的变化量值, -1 对应 p, 1 对应 v
  short sem_flg;//通常设置为 0
}

共享主存

共享主存允许两个或更多进程访问用一块主存, 但程序编制者必须提供自己的同步措施

• 共享主存的分配

  shmget

  参数 1: 表示共享主存快的键值(IPC_PRIVATE 可以保证系统建立一个全新的共享主存块)

  参数 2: 所申请的主存块的大小

  参数 3: 一组标识

• 共享主存的绑定

  shmat绑定

  参数 1: 共享主存标识符 SHMID

  参数 2: 指向希望用于映射该共享主存块的进程主存地址的指针

  参数 3: 一个标志位

  shmdt脱离

• 共享主存的释放

  shmctl

  参数 1: 共享主存标识符

  参数 2: IPC_RMID

  参数 3: null

  或用来 get 共享主存的相关信息

  参数 1: 共享主存标识符

  参数 2: IPC_STAT

  参数 3: 一个指向 struct shmid_ds 对象的指针

UNIX 进程管理

UNIX 进程及其映像

• 进程映像

  unix 中的进程实体称为映像(image), 包括

  • 进程基本控制块 proc结构

    unix 把进程控制块分为两部分, 把最常用的一部分信息常驻主存作为基本控制块, 称为 proc 结构

    另一部分存放不常用的信息称为扩充控制块, 称为 user 结构

  • 正文段

    纯过程, 只能读和执行

  • 数据段

    可读可写可执行

    分为三部分: 最高层用户栈, 中间用户数据区, 低端进程数据区(ppda per process data area), ppda 分为两部分, 上面是核心栈, 下面是 user 结构

• 共享正文段

  为了管理正文段, 设置正文表 text

  正文段平时放在磁盘上

• 进程基本控制块

  proc 型数据结构

• 进程扩充控制块

  user 型数据结构

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka7voph7cj313k0rse3i.jpg" alt="image-20201102020733676" style="zoom:25%;" />

UNIX 进程状态及变迁

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka7xkeuz1j31620rs1kx.jpg" alt="image-20201102020916842" style="zoom:25%;" />

状态:

1. 运行状态

2. 就绪状态

   在主存中就绪, 就绪切换出

3. 睡眠状态

   高优先睡眠, 低优先睡眠

4. 创建状态

5. 僵死状态

6. 进程转台变迁

UNIX 进程的创建

pid = fork()

fork(){
  newproc();
  判断从 newproc 返回的值;
  if(返回值为 0){
    //子进程
    子进程标识数送入栈内 r0 保护单元;
    栈内保护的返回地址加 2;
    return(r0);
  }
  else{
    //父进程
    父进程标识数送入栈内 r0 保护单元;
    子进程运行时间参数清零;
    return(r0);
  }
}

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka84vi0atj318t0rskd5.jpg" alt="image-20201102021616008" style="zoom:25%;" />

UNIX 进程的终止与等待

进程的自我终止

exit(status)

status 是终止进程向父进程传递的参数, 父进程用 wait 取得该参数

等待进程的终止

pid = wait(stat_addr)

wait(stat_addr){
  if(等待进程没有僵死进程)
    return(错误码);
  for(;;){
    if(等待进程有僵死子进程){
      取任一僵死子进程;
      将子进程的 cpu 使用量加到父进程;
     	释放子进程的 proc;
      return(子进程标识号, 子进程退出码);
    }
    睡眠在可中断的优先级上(事件:子进程退出)
  }
}

UNIX 进程的睡眠与唤醒

进程的睡眠

sleep(chan, pri)

pri 为唤醒后该进程的优先级, 若为负责进入高优先级睡眠状态, 否则进入低睡眠优先级状态

sleep(chan, pri){
	提高处理机执行级来屏蔽所有中断;
  置当前进程状态为睡眠;
	if(pri<0){
    p_wchan = chan;
    p_pri = pri;
    s_stat = SSLEEP;
    重置处理机优先级为进程进入睡眠时的值;
    switch();
  }
  else{
    p_wchan = chan;
    p_pri = pri;
    s_stat = SWAIT;
		if(0#因无进程换出而等待){
     	唤醒 0#进程;
    	重置处理机优先级为进程进入睡眠时的值;
      switch(); 
    }
  }
}

唤醒睡眠进程

wakeup(chan)

wakeup(chan){
  提高处理机执行级来屏蔽所有中断;
  查找睡眠原因;
  for(每个在该原因上睡眠的进程){
    将进程移出此等待队列;
    置进程状态为就绪;
    将进程加入就绪队列;
    清除 proc 表中的睡眠原因域;
    if(进程尚未装入主存)
      唤醒对换过程(进程 0);
    else
      if(被唤醒的进程比当前运行的进程的优先级高)
        设置调度标志
  }
  将处理机的执行级恢复为原来的级别;
}

Linux 系统的进程管理

进程描述符(process descriptor)及其主要内容

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka8qe9bzpj30tk0rsas6.jpg" alt="image-20201102023701946" style="zoom: 33%;" />

进程描述符的获得

current宏

thread_info 结构成为进程基本信息块, Linux 系统将内核态的进程堆栈和 thread_info 结构组织在一起, thread_info 放在堆栈的尾端, 可以直接用 esp 获取

linux 进程状态变迁

<img src="https://tva1.sinaimg.cn/large/0081Kckwgy1gka8t20qaxj31hm0rs1kx.jpg" alt="image-20201102023934918" style="zoom:25%;" />

linux 系统的进程创建

写时拷贝(copy-on-write), 当一方要写入时才进行拷贝

fork() clone()

linux 系统的进程终止

exit()

linux 系统的进程等待

linux 系统的进程唤醒

[lightman]

第五章 资源分配与调度

资源管理概述

静态分配与动态分配

静态: 作业被调度时根据用户给出的信息分配

动态: 进程运行中 根据运行状态动态分配使用释放

资源管理

虚拟资源

资源管理的机制与策略

资源分配机制

资源描述器rd

描述了资源的特性和管理方式, 一个资源分配单位(如主存的块, 磁盘的扇区)对应一个资源描述器

资源信息块rib

它描述了某类资源的请求者, 可利用的资源, 以及该类资源的分配程序地址

数据结构包括: 等待队列头指针(PCB), 可利用资源队列头指针(rd), 资源分配程序入口地址

资源分配策略

选择请求者, 选择资源两种策略, 分别针对两个队列

先请求先服务

如批处理系统在处理作业调度采用 FIFO

优先调度

对每一个进程指定优先级

针对设备特性的调度

死锁

定义: 进程之间相互等待不能向前推进

例子: 生产者消费者的 mutex 和 占用的顺序问题

死锁的原因

根本原因: 操作系统能够提供的资源个数比请求资源的进程数少

进程推进顺序违法

必要条件:

1. 互斥条件
2. 不剥夺条件: 资源被占有以后不能被剥夺
3. 占有并等待: 等待资源时继续占有已经有的资源
4. 环路条件: 存在一种进程的循环链, 链中的每一个进程已获得的资源被链中的下一个进程所请求

死锁的处理

思想: 进入系统的一组进程必须事先宣布他们所需要的各类资源数

资源分配图:

若图没有环, 则系统没有发生死锁, 若有环, 则可能发生死锁

如果环涉及一组资源类型, 且每个资源类型只有一个实例, 那么有环就意味着有死锁

解决死锁

破坏必要条件

1. 资源静态分配
2. 资源动态分配, 有控分配
3. 检测死锁并修复
4. 忽略死锁, 重启系统

死锁的预防

静态预防: 预先分配所有共享资源

动态避免: 有序分配

要求每个进程:

1. 对它锁必须使用而且属于某一类的所有资源必须一次性申请完
2. 在申请不同类资源时, 必须按各类的编号依次申请

银行家算法

进入系统的进程必须说明它对各类资源类型实例的最大需求量

当进程申请一组资源时, 该算法需要检查申请者对各类资源的最大需求量, 如果系统现存的资源数可以满足当前它对资源的最大需求量, 就满足该申请, 否则等待.

即仅当申请者可以再一定时间内无条件归还所申请的资源是, 才把资源分配给他

第六章 进程调度

处理机的多级调度

批处理系统: 作业调度+ 进程调度

多任务操作系统

多线程操作系统

作业调度

作业状态

后备状态, 执行状态, 完成状态

作业调度的功能

数据结构: 作业控制块 jcb

调度算法

平均周转时间: 周转时间 = 作业完成的时间 - 进入系统的时间

带权周转时间 = 周转时间/作业实际执行时间

FIFO

短作业优先调度

总是选取计算时间最短的作业作为下一个服务的对象

可以使平均周转时间最小

响应比高者优先调度算法

响应时间 = 进入系统后的等待时间 + 执行时间

响应比 = 响应时间/执行时间 = 1 + 等待时间/执行时间

每次调度作业, 计算响应比, 响应比最高执行

优先调度算法

分配资源

善后处理

进程调度

分为: 调度和分派

进程调度的功能:

1. 记录进程有关情况(PCB)
2. 决定分配策略
3. 实施处理机的分配和回收

调度方式

非剥夺调用

可剥夺调用

进程优先数调度算法

分两级

进程调度(低级调度, 短程调度)

高级调度(中程调度)

进程优先数调度算法

优先数:

静态优先数: 进程创建时确定

动态优先数: 进程被重新调度时或者耗尽时间定额时, 优先数被调整

循环轮转调度

FIFO 有缺陷

每个进程被调度时分得一个时间片, 时间片用完以后, 转为就绪并进入就绪队列末端

时间片 q = 用户所能接受的响应时间/进入系统的进程数目

改进:

1. 可变时间片

   每一轮开始时, 系统根据就绪队列中已有的进程数目计算一次 q

2. 多就绪队列

   某进程分到处理机时, 给它一个与就绪队列对应的时间片, 时间片用完后, 被迫释放处理机, 进入下一级就绪队列中, 每高一级就绪队列, 时间片就加倍

状态变迁

超时间片: 低优先就绪

阻塞: 高优先就绪

[lightman]

第七章 主存管理

概述

物理主存

​ 物理地址(实地址, 绝对地址): 处理机可以根据绝对地址任意存放信息

逻辑主存

​ 逻辑地址(虚地址)

分片:

1. 划分为大小不同的区域, 根据需求决定大小: 按区(按段)分配
2. 划分为大小相同的块: 按页分配

逻辑组织:

1. 一维地址
2. 二维地址: 例如分为代码段, 数据段, 堆栈段, 确定地址需要两个信息: 分段, 偏移量

主存管理的功能

虚拟存储器

定义: 只装入部分程序代码和数据就启动运行, 由操作系统和硬件相配合完成主存和辅存之间的信息动态调度, 这样的计算机好像为用户提供了一个比主存大得多的存储器

虚地址空间 V

实地址空间 R

地址映射

即逻辑地址和物理地址的转换

根据程序开发的不同阶段分类:

1. 编程或者编译时确定
   这样的程序模块必须放在主存的一个确定地址
2. 静态地址映射(静态重定位)
   虚实地址对应在程序装入主存时完成(转换由软件实现)
   要求被装入的程序本身是可以重定位的, 即对需要修改的地址具有某种标识
   但这种情况下, 一个已经开始执行的程序是无法在主存中移动的
3. 动态地址映射
   程序执行期间, 随着和每条指令和数据访问, 自动连续的进行映射
   当某个进程取得 CPU 时, 操作系统负责将该程序在主存中的起始地址送入重定位寄存器中(硬件实现转换)

主存分配

存储保护

上下界防护(上下界寄存器)

分区存储

分区分配机构

描述主存资源的数据结构: 主存资源信息块(m_rib), 分区描述器(pd)

m_rib: 等待队列指针, 空闲区队列指针, 主存分配程序入口地址

pd: 分区标志(已用1还是空闲0), 分区大小, 勾连字(next空区)

分区分配和放置策略

分区分配

分配主存块: 若找到的空闲区的大小小于请求大小, 就继续找, 否则找到

如果大小正好, 啧从空闲区移除, 否则一部分成为已分配区, 一部分成为空闲区并修改 pd

放置策略

即空闲队列的排序规则

1. 按照地址增加或减少排序
2. 按照区的大小排序

算法:

1. 首次适应算法
   按照地址排序, 尽可能利益存储器低地址的空闲区
2. 最佳适应算法
   按照大小递增的顺序排序, 能找到最适合的, 但会使得剩下的空闲区非常小以至于无法使用
3. 最坏适应算法
   放入最大的空闲区, 按照大小递减的顺序排列

碎片问题

1. 回收时立即拼接
2. 找不到足够大的的空闲区再拼接

页式存储

主存的块和页面大小相等且为 2 的幂次, 只要求把当前所需要的一部分页面装入主存即可

页式地址转换

页表(地址变换表, 地址映像表): 页号, 块号

页面尺寸一般为 1, 2, 4kb

页表放在快速存储器中, 放置页表的快速存储器叫做联想存储器, 其中的页表叫做块表

虚拟地址

按位分成页号和页内位移, 页内位移取决于页面尺寸

页式地址变换

作业访问主存->虚拟地址->分页机构->页号+页内位移->页表始址寄存器->页表->根据页号找到块号->块号+页内位移->物理地址

请调页面机制

即从辅存把页面装入主存

扩充页表

页号, 主存块号, 中段位(1 不在主存 0 在主存), 辅存地址

淘汰机制与策略

扩充页表

页号, 主存块号, 中断位, 改变位(1 修改过 0 未修改), 引用位(1 已被访问 0 未被访问), 辅存地址

几种置换算法

1. 最佳算法 opt(理论)

2. 先进先出 FIFO

将留存最老的一页淘汰

1. 利用: 页号表

P[k] = 新页号;//P 为页号表, 大小为程序可用的块的数量m
k = (k+1) mod m;//k 为替换指针

2. 在存储分块中建立先后次序

存储分块表: 以块号为序号, 依次登记各块的分配情况(分配给了哪个页)

组成: 块号, 页号, 指针(指向下一个已分配的块, 指示了块分配的次序, 用一个替换指针实现替换最先分配的块)

3. 最久未使用算法(LRU)

选择最长时间未被使用的页

1. 计数器
   计数器内容复制到对应页表项的时间域内, 反应最近是否使用
2. 页号堆栈
   栈底存放的就是最久未使用的

4. LRU 近似算法

存储块有一个引用位, 当页面被访问时置 1, 页面管理软件周期性将所有引用位置 0

段式和段页式存储

地址变换

同时提供段名和段内地址, 程序地址的形式为(s, w)

段表: 段号, 长度, 基址

基址+段内地址=主存地址

扩充段表

加入中断位, 引用位, 改变位

段页式存储

一个程序->一张段表->每个段一个页表

[lightman]

第八章 设备管理

概述

设备分类: 存储设备, io 设备, 通信设备

功能: 状态跟踪, 设备分配, 设备管理

设备独立性

定义: 用户在编制程序时所使用的设备与实际使用的设备无关, 也就是在用户程序中仅使用逻辑设备名

1. 程序独立于分配给他的某种类型的具体设备
2. 程序尽可能与它所使用的的 io 设备类型无关

独立性的实现

1. 软通道
   在用户一级仅进行逻辑指派, 操作系统的 io 管理模块需要建立逻辑设备与物理设备的链接
2. 指派命令
   assign 物理名: 逻辑名
3. 逻辑设备描述器 ldd

设备独立性的优点

方便用户, 提高设备利用率, 提高系统的可适应性和可扩展性

设备控制块dcb

记录硬件特性, 链接, 使用情况的数据结构, 每一个设备有一个设备控制块

内有命令转换表的指针

缓冲技术

定义: 缓冲是在两种不同速度设备之间平滑传输信息过程的常用手段

实现: 硬件: 缓冲器, 软件: 存储区

利用缓冲技术进行 io

• 读

  1. 用户要求在某个设备上进行读操作时, 先获得一个空缓存

  2. 将物理记录送到缓存区中

  3. 当用户要求使用这些数据的时候, 系统从缓冲区提取数据发给用户进程的存储区中

     当缓冲区空而进程有要求数据时, 进程被迫等待

• 写

  1. 用户要求写操作时, 先获得一个空缓存

  2. 将进程的逻辑记录送到缓存区中, 若为顺序写请求, 啧直到写满缓冲区为止

  3. 当缓冲区写满的时候, 系统从缓冲区提取数据写到设备上, 缓冲区再次为空

     系统来不及腾出缓冲区时, 进程被迫等待

缓冲技术解决的问题

1. 速度差异问题(双缓冲区)
2. 协调数据大小不一致的问题(网络)
3. 应用程序的拷贝语义问题(write 操作, 写入的是内核操作中在 write 调用时的拷贝数据, 而不是数据本身)

常用的缓存技术

双缓冲

交替使用

缓冲池

一组缓冲区组成, 避免在消费者多次访问相同数据时重复产生相同数据的问题

设备分配

静态分配: 对独占设备一般用静态分配, 一旦分配给一个应用程序, 就由其单独使用

动态分配: 共享设备

io 分配算法: FIFO, 优先级

独享分配

有些外部设备适用于一个应用程序独占使用

共享分配

当进程提出资源申请时, 由设备管理模块进行分配, 进程使用完毕以后立即归还

虚拟分配

虚拟设备

利益系统中便于共享的快速的存储设备来替代不适合共享的, 慢速的字符设备, 采用预先收存, 延迟发送的方式来改造独占设备

虚拟分配

方法: 将想要从独占设备输入(出)的信息先复制到辅存的存储设备中, 当进程需要从输入设备读入信息时, 系统将这一要求转换成从辅存读入的请求

通常把用来代替独占性设备的那部分外存空间称为虚拟设备

Spool 假脱机系统

该系统在应用程序执行前将应用程序的信息通过 独占设备预先输入到辅存上的一个特定的存储区域(叫做"井")存放好, 称为预输入

设备分配算法

FCFS

最短寻道时间 SSTF

扫描算法 类比电梯

循环扫描算法 磁头单向移动

输入输出控制

输入输出硬件

端口(硬件的端口又叫做接口), 总线, 控制器(用于操作端口, 总线或设备的电子器件)

处理器控制控制器:

1. 控制器拥有多个寄存器
2. 方式 1: 通过特殊 io 指令, 将信息传递给控制寄存器
3. 方式 2: 主存映射 io, 设备控制寄存器映射到处理器的地址空间
4. 处理器通过标准数据传输指令完成对设备控制器的读写

输入输出控制方式

1. 循环测试 io 方式: 反复检测控制寄存器的完成位
2. io 中断方式
   1. 将启动位和中断允许位送入控制器寄存器
   2. 请求数据输入的进程进入等待状态
   3. 输入完成后输入设备通过中断向 cpu 发中断请求信号
   4. 中断处理程序保护现场, 将输入寄存器的数据转送到特定单元, 唤醒请求的进程, 然后恢复中断现场继续执行
   5. 之后某一时刻请求进程开始执行, 从特定单元取出数据
3. 通道方式
4. DMA 方式
   DMA 控制器可以控制设备和主存之间的成批交换, 而且不需要 cpu 干预

输入输出子系统

io 子系统对不太设备按统一标准来处理

各类设备的接口

1. 块设备接口
   read, write, seek
2. 主存映射接口
3. 字符流设备接口
4. 网络套接字接口

输入输出子系统功能

解释用户的 io 系统调用, 设备驱动, 中断处理

调用 io 核心模块的方式

1. 设备处理进程方式
   io 控制模块有一个接口程序->负责解释进程的 io 系统调用
   对每类设备有一个设备处理程序(某类设备的驱动程序)->接受 接口程序的命令
2. 文件操作方式
   unix

输入输出例子

通用形式的系统调用

对一个 io 请求

1. 实现使用设备的转换
2. 合法性检查
3. 形成 io 请求块

设备处理进程

设备处理程序: 从 io 请求队列中取出一个 iorb, 启动相应 io 操作, 完成后进入中断处理程序

UNIX 系统的设备管理

[lightman]

第九章 文件系统

文件分类: 系统文件, 程序库文件, 用户文件

文件组织: 逻辑文件, 物理文件

对应: 逻辑记录, 块

文件的逻辑结构和存储方法

逻辑结构

流式文件

无结构

记录式文件

有结构, 可分定长变长

文件的物理结构

组织文件的方式

连续文件

文件目录项: 文件名, 块数量, 第一个逻辑记录所在的块

串联文件

文件目录项: 文件名, 第一个块

类比链表

文件映照结构(表实现)

索引文件

文件索引表

直接索引

文件目录项: 文件+索引表, 索引表每一个项对应一个块号

一级间接索引

文件目录项: 文件+索引表, 索引表每一个项对应一个一级间接索引表, 一级间接索引表每一个项对应一个块号

二级间接索引

文件目录项: 文件+索引表, 索引表每一个项对应一个二级间接索引表, 二级间接索引表每一个项对应一个一级间接索引表, 一级间接索引表每一个项对应一个块号

文件存储空间的管理

磁盘空闲空间

空闲文件目录

一个表, 每一个表项: 序号, 第一个空闲块号, 空闲块个数...

空闲块链

位示图

每个块是否空闲用一位表示, 1 已分配, 0 空闲

分配策略

静态分配

创建文件时宣布文件大小

动态分配

写文件时分配大小

文件目录

一级文件目录

表项: 文件名, 物理地址, 其他信息

不能解决重名问题

多级文件目录

目录对应目录文件

共享与安全

存取权限的类型和验证

访问控制矩阵

每一个用户对每一个文件的权限

存取控制表

用户分组

用户权限表

口令

密码

利用文件路径名加快查找

建立当前目录

链接技术

硬链接 软连接

文件操作与备份

UNIX 文件系统

UNIX 文件索引结构

目录项只包括文件名, 其他信息存到索引节点 inode 上

UNIX7 文件索引结构

i_addr[8]

小型文件: 直接索引表 8

大型文件: 一级间接索引 7

巨型文件: 一级间接索引 7 + 二级间接索引 1

UNIX systemV 索引结构

i_addr[13]

0-9 直接索引

10 一级间接索引

11 二级间接索引

12 三级间接索引

UNIX 文件目录结构

UNIX 打开文件机构

活动 i 节点表

打开文件->登记到活动 i 节点(主存索引节点)

系统打开文件表

不同进程打开同一个文件时要登记不同的表项

用户文件描述符表

每个用户打开的文件

每一项指向系统打开文件表的一个表项

文件存储器空闲块的管理

表链结合