操作系统基础知识

2024-11-12 12:07 · 72 分钟阅读 ·

author:moyigeek os

操作系统的定义

操作系统是一个大型系统程序
- 操作系统是一个大型的程序系统，它负责计算机系统软件/硬件资源的分配；控制和协调并发活动；提供用户接口，使用户获得良好的工作环境。
管理并调度资源；
为用户提供接口。

操作系统的特性

并发性
- 同时处理多个任务的能力
共享性
- 为多个并发任务提供资源共享
不确定性
- 具有处理随机事件的能力
  - 中断处理的能力
  - 自动化能力

操作系统的功能

进程管理

处理机分配
处理机管理
CPU管理
具体功能
- 进程控制：创建，暂停，唤醒，撤销
- 进程调度：调度策略，优先级
- 进程通信：进程间通信

存储管理/内存管理

为应用程序运行分配和管理所需的内存
支持多道程序设计
具体功能
- 内存分配
- 内存共享
- 内存保护
- 内存扩充
- 虚拟内存

设备管理

设备的分配和回收
设备的驱动机制/传输控制
为应用提供统一接口访问设备
- 设备无关性
高效存取/设备缓冲机制

文件管理文件系统

为用户提供统一的文件存取接口，高效组织存储空间，提高存取效率，实现信息共享和存取控制。
文件用户接口
存储空间管理
文件的操作
目录的操作
存取权限管理

操作系统的性能/评价指标

吞吐率
- 在单位时间内处理信息的能力。
资源利用率
- 设备(CPU)使用的频度
响应能力
- 从接收数据到输出结果的时间间隔。
可移植性
- 改变硬件环境仍能正常工作的能力
可靠性
- 发现、诊断和恢复系统故障的能力。

操作系统的发展和演变

手工操作(无操作系统)（40年代-50年代初）

结构特点
- 硬件：电子管、接线面板
- 程序：二进制（卡片/纸带，打孔）
使用特点
- 上机：编程（打孔），预约，操作机器（开关/接线）
- 程序启动与结束：手工处理
缺点
- 效率低：CPU利用率低
- 用户独占
- 缺少交互

单道批处理系统（ 50年代）

工作过程
- 管理员将多个作业输入到磁盘形成作业队列；
- 监控程序（操作系统）依次自动处理磁盘中每个作业
  - 装入—运行—撤出—装入—运行—撤出…….
- 运行完毕，通知用户取结果
工作特点
- 一批：作业队列
- 自动：识别作业
- 单道：串行
实现
- 联机批处理
  - 特点：主机负责运算，同时控制输入/输出
  - 缺点：系统效率低
- 脱机批处理
  - 特点：主机负责运算；卫星机负责输入/输出。
  - 优点：系统效率高
  - 缺点：调度不灵活；保护问题
CPU
- 现象：外设工作时CPU空闲， CPU工作时外设空闲。
- 结论：CPU和外设效率低。

多道批处理系统（60年代初）

多道程序设计技术
- 内存中存放多道程序,当某道程序因为某种原因（例如请求I/O时）不能继续运行时，监控程序/OS便调度另一道程序投入运行，这样使CPU尽量处于忙碌状态，提高系统效率。
多道批处理系统
- 采用多道程序设计技术实现的处理系统称为多道批处理系统。
目的：
- 提高资源的利用率（或吞吐量）
- CPU与外设并行
- 外设之间也并行
实现资源共享
- 时分：分成多个时段：不同进程错开时段使用。
- 空分：分成多个单元：不同进程使用不同单元。
多个程序同时在计算机/虚拟机上运行
特点：
- 多道
  - 内存同时存放多道程序
- 并行
  - 宏观上
- 串行
  - 微观上
缺点
- 作业处理时间长
- 运行过程不确定
- 交互能力差

分时操作系统（60年代中-至今）

技术前置

中断技术
- CPU收到外部信号（中断信号）后，转去处理外部事件，处理完毕后回到中断处（断点）继续原来工作。
通道技术
- 专门处理外设与内存之间数据传输的处理机

背景

事务性任务和程序的涌现
- 交互性高
- 响应快速
- 多任务/多用户
硬件
- 中断技术
- 大规模集成电路
- 多终端计算机
  - 用户通过终端连接主机，通过终端与主机交互。
  - 主机采用分时技术轮流为每个终端服务。
分时技术概念
- 主机以很短的“时间片”为单位，把CPU轮流地分配给每个作业（终端/用户）使用，直到全部作业被运行完
- 时间片：较短时间间隔
- 循环/轮流：响应及时
  - 独占主机

特点

多路调制性
- 多用户联机使用同一台计算机
独占性
- 用户感觉独占计算机
交互性
- 及时响应用户的请求

分时操作系统演化

实时操作系统
- 实时要求
  - 实时事务：军用电子、工业控制，智能仪器等
  - 某些任务要优先紧急地处理
    - 强调作业完成的时限(dead-line)
    - 完成时间的可预测性
- 分类
  - 硬实时系统
    - 火炮控制系统
    - 航空航天
    - 工业控制
  - 软实时系统
    - 尽可能快完成
    - 网络视频
    - 广播
微机操作系统（PC机操作系统）
多处理机操作系统
- 包含两个或多个功能相当的处理器（CPU）
- 共享：内存，I/O通道、外设
- 单一操作系统控制
- 特点
  - 具有一定的并行处理能力
  - Linux支持SMP
网络操作系统
- 计算机网络：通过协议将多台计算机互连实现资源共享和信息传递的计算机系统。
- 网络操作系统=普通操作系统+网络通信+网络服务
- 特点：
  - 主机独立自治
  - 通信协议
  - IP/端口的标识
分布式操作系统
- 通过网络将多个通用资源部件互联，并能对资源进行全局统一管理和调度的计算机系统。
- 特点：
  - 可运行分布式程序
  - 主机自治又相互协调
  - 可扩展性| 高可靠性
- 与计算机网络的区别
  - 支持单点登录（虚拟为“单台”计算机）
  - 支持资源透明存取（计算机网络：通过IP指明主机）
  - 支持合作运算（计算机网络：不支持）
嵌入式操作系统
- 嵌入式系统使用的操作系统
- 实时操作系统∈ 嵌入式操作系统

操作系统的逻辑结构

OS的设计和实现思路

整体式结构(单体式结构，宏内核结构)

以模块为基本单位构建
- 每个模块具有特定的功能
定义
- 模块化结构/单体内核结构/宏内核结构
- 操作系统由大量过程构成。每个过程都有明确参数列表、返回值类型。大多数过程是可以相互间调用。
优点：
- 模块的设计、编码和调试独立。
- 模块之间可以自由调用。
缺点：
- 错误容易扩散
- 开发和维护困难
- 可伸缩性差

层次式结构

定义
- 功能模块按调用次序排若干层，各层单向依赖或单向调用
分层原则
- 最底层：硬件相关
- 最顶层：用户策略/用户交互
- 中间层：按调用次序/消息传递顺序
- 较低层：共性的、活跃的服务
优点：
- 结构清晰，避免循环调用。
- 整体问题局部化，系统的正确性容易保证。
- 有利于操作系统的移植、维护、扩充。

微内核结构

操作系统= 微内核+ 核外服务器
客户：应用程序
服务器：操作系统=微内核+核外服务器
微内核
- 足够小，提供OS最基本的核心功能和服务
  - 实现与硬件紧密相关的处理
  - 实现一些较基本的功能；
  - 负责客户和服务器间的通信。
核外服务器
- 完成OS绝大部分功能，等待客户提出请求。
- 由若干服务器或进程共同构成
  - 例如：进程/线程服务器，虚存服务器，设备管理服务器等，以进程形式运行在用户态。
微内核和单体内核（宏内核）比较

CPU的态

CPU的工作模式
对资源和指令使用权限的描述
用户态
- 有限的指令
核态
- 全部指令

特权指令

类别
- 涉及外部设备的输入/输出指令
- 修改特殊寄存器的指令
- 改变机器状态的指令
例子
- LGDT/LIDT/CLTS：装载特殊寄存器
- STI/CTI：允许和禁止中断
- HALT：停止CPU的工作
- IN/OUT：执行I/O操作
最高权限
用户态向核态
- 用户请求os提供服务
- 用户态企图执行特权指令
- 发生错误（内部中断）
- 发生中断
核态->用户态
- 一般是中断返回：IRET

存储体系

实际体系
- 寄存器
- 高速缓存
- 主存
- 磁盘

中断机制

定义
- 指CPU对突发的外部信号的反应过程或机制
- CPU收到外部信号后，停止当前操作，处理外部事件，处理完回到原来工作的中断处。
中断源
- 引发中断的事件
中断类型
- 强迫中断和自愿中断
  - 强迫：程序没预期，（外部中断
  - 自愿：程序有预期。（int 21h 访管指令)
外中断，内中断
- 外：外部事件引起，I/O
  - 不可屏蔽中断：中断原因很紧要，CPU必须相应
  - 可屏蔽中断：CPU可以选择响应
- 内：内部事件引起
断点
- 程序中断的地方
  - 将要执行的下一条指令位置(CS:IP)
现场
- 程序正确运行所依赖的信息集合
- PSW（程序状态字），相关寄存器，断点
现场处理
- 保护：状态->栈
- 恢复：栈->状态
中断响应过程
1. 中断信号
2. 断电入栈
3. 现场入栈
4. 进入中断服务
5. 现场出栈
6. 中断返回
中断的目的
- 实现并发活动
- 实现实时处理
- 故障自动处理
中断程序
- 填写中断向量表
- 填写中断描述符表
中断嵌套处理
- 高优先级打断低优先级中断服务
中断响应的实质
- 交换指令执行的地址
- 交换CPU的态
工作
- 现场保护和恢复
- 参数传递
引入中断的目的
- 实现并发
- 实现实时处理
- 故障自动处理

BIOS

系统BIOS
- 固件
- 地址范围：F0000- FFFFF
功能
- 加电自检(POST)
  - 初始化基本硬件
  - 自检错误通过喇叭鸣叫
  - 按下PowerON开始执行POST
  - 计算首条指令在FFFF0单元
  - JMP POST
- 设置CMOS
  - 交互式设置系统参数
- 基本I/O功能
  - BIOS中断
- post之后
  - 依次查找其他设备并初始化
  - 查找显卡，执行显卡BIOS（C0000-C7FFF）
  - 查找IDE控制器（C8000-CBFFF）
  - 显示启动信息
    - 各组件版权信息
  - 查找/设置其他外设
    - 配置寄存器
    - 启动设备BIOS
- 系统自举/加载OS
  - 现场引导方式
  - 下载引导方式

mode

实模式
- 按照8086访问1MB空间
- 寻址方式：物理地址（20）=段地址：偏移地址
- CPU单任务运行
- 实模式的1M空间
  - 前面640K 【00000 — 9FFFF】：基本内存
  - 中间128K 【A0000 — BFFFF】：显卡显存
  - 末尾256K 【C0000 — FFFFF】：BIOS
保护模式
- 寻址方式：段（16bit）和偏移量（32bit），寻址4gb
- CPU支持多任务

启动过程

从加电到用户工作环境准备好的过程

初始引导
- 把OS内核装入内存并使之接管计算机系统
- 引导程序：MBR
  - GRUB
  - bootmgr|NTLDR|LILO
核心初始化
- OS内核准备数据.
- 典型工作
  - 各种寄存器的初始化
  - 存储系统和页表初始化
  - 核心进程构建
系统初始化
- 为用户使用系统作准备
- 主要工作
  - 初始化文件系统
  - 初始化网络系统
  - 初始化控制台
  - 初始化图形界面

MBR

主启动扇区
存放引导代码
- 启动相关的数据和代码
512B=510字节+AA55h
PBR：分区/次引导记录
提供BootLoader或启动管理
- 直接指向引导代码加载OS
- 提供启动选项菜单
- 跳转到PBR以加载特定OS BootLoader
安装过程
- 把OS映像拷贝到存储空间
- 写启动相关代码和数据
  - MBR扇区
  - PBR扇区
  - 512字节
多操作系统安装
- MBR重写vs. MBR追加
- 安装顺序

windos启动过程

POST
- 加电后IOS启动主机自检程序
初始引导
- BIOS从MBR读入引导程序，装入内存的特定位置
- 引导程序启动DOS7.0，调入操作系统核心
- WINDOWS开始接管系统
核心初始化
- 资源状态、核心数据等初始化
系统初始化
- GUI界面生成，系统处于待命/消息接受状态

linux启动过程

POST → MBR → KERNEL映像→ KERNEL映像边自解压并边执行→ 内核初始化→ 内核启动→ init进程→

用户环境

用户工作的软件
- 桌面环境
- 命令行环境

用户环境构造

按照用户要求和硬件特性安装和配置操作系统。
- 提供操作命令和界面
- 提供系统用户手册

用户界面

定义

操作系统提供给用户控制计算机的机制(用户接口)

类型

操作界面
系统调用(System Call，系统功能调用,程序界面)

操作界面

类型

图形用户接口
操作命令（普通命令）
批处理与脚本程序

批处理与脚本程序

在控制台环境下自动处理一批命令
- Windows：批处理程序（bat/PowerShell）
  - 特点
    - 普通命令的集合，按批执行，由command解释执行
    - 支持变量替换、条件、转移、循环、注释等语法
    - 文件后缀*.BAT，解释执行
- Linux： Shell脚本程序
  - 特点：
    - 脚本程序是有一定逻辑顺序和语法结构的命令序列，能完成较复杂的功能和人机交互。
    - 所有命令按逻辑逐行执行
    - 脚本程序是文本文件（具有可执行属性X）
shell是操作系统与用户的交互机制（操作界面）
- 通过Shell(/控制台)执行用户命令
- 组织和管理用户命令的执行和结果展示

dos命令

文件管理
- COPY、COMP、TYPE、DEL、REN
磁盘管理
- FORMAT、CHKDSK、DISKCOPY、DISKCOMP
目录管理
- DIR、CD、MD、RD、TREE
设备工作模式
- CLS、MODE
日期、时间、系统设置
- DATE、TIME、VER、VOL
运行用户程序
- MASM、LINK、DEBUG

Linux典型命令

ls	列举子目录和文件	find	查找文件
ps	列举进程	whereis	查找文件目录
top	列举进程	man	查看命令帮助信息
echo	输出字符串	cp	拷贝
cat	读取内容	inode	查看文件节点
cd	改变目录	tar	压缩和解压
chmod	改变文件属性	rm	删除文件和文件夹
mount	挂载文件系统	umount	卸载文件系统
insmod	安装模块	rmmod	卸载模块

系统调用

操作系统内核为应用程序提供的服务/函数。
特点
- 内核实现
- 存取核心资源或硬件
- 调用过程产生中断
  - 用户态↔ 核态
  - 自愿中断
系统调用表
- 全部系统调用的入口列表
  - 有序排列
- 系统调用号：系统调用的唯一编号
系统调用的一般调用形式
- 访管指令： SVC X
  - SVC = SuperVisor Call
  - X = 系统调用的编号
具体OS中系统调用的调用形式
- DOS： INT 21H + AH
- Linux：INT 80H + EAX
  - INT XXH = SVC指令
  - AH/EAX = 系统调用的编号：N

进程概念

定义

进程是程序在某个数据集合上的一次运行活动
数据集合：软硬件环境，多个进程共存/共享的环境

进程特征

动态性
- 进程是程序的一次执行过程，动态产生/消亡
并发性
- 进程可以同其他进程一起向前推进
异步性
- 进程按各自速度向前推进
独立性
- 进程是系统分配资源和调度CPU的单位

进程与程序的区别

动态与静态
- 进程是动态的：程序的一次执行过程
- 程序是静态的：一组指令的有序集合
暂存与长存
- 进程是暂存的：在内存驻留
- 程序是长存的：在介质上长期保存。
程序和进程的对应
- 一个程序可能有多个进程

进程的状态

运行状态
- 进程已经占有CPU，在CPU上运行
就绪状态
- 具备运行条件但由于无CPU，暂时不能运行
阻塞状态
- 因为等待某项服务完成或信号来到而不能运行的状态
- 例如等待：系统调用，I/O操作，合作进程的服务或信号
进程状态的变迁
- 进程的状态可以依据一定的条件相互转化
- 服务：系统调用/ I/O
  - 就绪->运行：进程调度
  - 运行->就绪：时间片到；被抢占
  - 运行->阻塞：服务请求；等待信号
  - 阻塞->就绪：服务完成；信号来到
具有新建(new)和终止(terminate)状态的进程状态
- 状态机
支持挂起(suspend)和解挂(resume)操作的进程状态
- 阻塞
  - 活动阻塞（正常阻塞）
  - 静止阻塞（阻塞时挂起）
- 就绪
  - 活动就绪（正常就绪）
  - 静止就绪（就绪时挂起）
- 与挂起相关的迁移
  - 运行—>静止就绪：挂起
  - 活动就绪->静止就绪：挂起
  - 活动阻塞->静止阻塞：挂起
  - 静止就绪->活动就绪：解挂
  - 静止阻塞->活动阻塞：解挂
  - 静止阻塞->静止就绪：期待的事件/信号发生

进程控制块PCB

描述进程的状态、资源、和相关进程的关系。
PCB是进程的标志
创建进程时创建PCB；进程撤销后PCB同时撤销。
进程＝程序＋ PCB
基本成员
- name（ID）：进程名称（标识符）
- state：状态/status
- priority：优先级
- start_addr：程序入口地址
- next：指向下一个PCB的指针
- cpu_status：现场保留区(堆栈)
- comm_info：进程通信机制/信号机制
- process_family：家族关系
- own_resource：资源清单

linux实现

struct  task_struct{
/* these are hardcoded  - don't touch*/
long stat;  //进程的运行状态  （-1 unrunnable  ,1 runnable , 0 stopped）

long counter;  //进程的执行时间片，表示当前进程能够占用CPU资源的时间

long signal;  //信号量位图32bit每一个bit来表示一个信号

struct sigaction sigaction[32];  //信号量
long blocked;  //信号掩码  

/* various fields*/
int exit_code; //退出码

unsigned long start_code,end_code,end_data,brk,start_stack; //当前进程的内存使用信息

long pid,father,pgrp,session,leader; //pid 

unsigned short uid,euid,suid; //进程的用户ID，进程的有效ID，进程的超级ID

unsigned short gid,egid,sgid;  //进程组ID，进程的有效组ID，进程的超级组ID

long alarm; //进程的警告标志

long utime,stime,cutime,cstime,start_time;  //有关进程的用户时间，系统时间当前用户时间等

unsigned short used_math;  //是否使用协处理器

/*file  system info*/
int tty;  //当前进程是否占用控制台

unsigned short umask; //用户的掩码

struct m_inode * pwd;  //路径

struct m_inode * root;  //根目录

struct m_inode * excutable; // 执行位图

unsigned long close_on_exec; // 执行结束后关闭位图

struct file * fds[NUMFD];  //当前进程的文件列表FD在这个数组中找到一个file结构体

struct desc_struct ldt[3];

struct tss_struct tss;

}

进程的上下文和进程切换

进程的上下文
- Context，进程运行环境
分时系统的进程切换过程
- 进程的上下文在CPU中交换
- 换入进程上下文进入CPU(从栈+PCB上来)
- 换出进程上下文离开CPU(到栈+PCB上去)

进程控制

在进程生存全期间，对其全部行为的控制
四个典型的进程控制

进程创建

功能
- 创建一个具有指定标识（ID）的进程
参数
- 进程标识、优先级、进程起始地址、CPU初始状态、资源清单等
创建进程的过程
- 创建一个空白PCB
- 赋予进程标识符ID
- 为进程分配空间
- 初始化PCB
  - 默认值
- 插入相应的进程队列
  - 新进程插入就绪队列

进程撤销

功能
- 撤销一个指定的进程
- 收回进程所占有的资源，撤销该进程的PCB
进程撤销的时机/事件
- 正常结束
- 异常结束
- 外界干预
参数
- 撤销进程的ID
进程撤销的实现
- 在PCB队列中检索出该PCB
- 获取该进程的状态。
- 若该进程处在运行态，立即终止该进程>
  - 先撤销子进程【递归/可选】
  - 或将字进程挂接到init进程下
- 释放进程占用的资源
- 将进程从PCB队列中移除

阻塞进程

功能
- 停止进程执行，变为阻塞。
阻塞的时机/事件
- 请求系统服务
  - （由于某种原因，OS不能立即满足进程的要求）
- 启动某种操作
  - （进程启动某操作，阻塞等待该操作完成）
- 新数据尚未到达
  - （A进程要获得B进程的中间结果，A进程等待）
- 无新工作可作(idle进程：pause( )
  - （进程完成任务后，自我阻塞，等待新任务到达）
参数
- 阻塞原因
- 不同原因构建有不同的阻塞队列。
进程阻塞的实现
- 停止运行
- 将PCB “运行态”改“阻塞态”
- 插入对应的阻塞队列
- 转调度程序

唤醒进程

功能：
- 唤醒处于阻塞队列当中的某个进程。
引起唤醒的时机/事件
- 系统服务由不满足到满足
- I/O完成
- 新数据到达
- 提出新请求
参数
- 进程的标识

进程控制原语

原语
- 由若干指令构成的具有特定功能的函数
- 具有原子性，其操作不可分割
进程控制原语
- 创建原语| 撤消原语| 阻塞原语| 唤醒原语

windos进程

CreateProcess
创建新进程
- 创建进程内核对象，创建虚拟地址空间
- 装载EXE和/或DLL的代码和数据到地址空间中
- 创建主线程和线程内核对象
- 启动主线程，进入主函数（main）
结束进程
- ExitProcess
  - VOID ExitProcess(UINT uExitCode)
- TerminateProcess
```
VOID TerminateProcess (
	HANDLE hProcess,
	UINT uExitCode )
```

linux进程控制

创建进程—fork
例子：pid_t pid=fork()
父进程和子进程
- 子进程：新建的进程
- 父进程：fork( )的调用者
- 子进程是父进程的复制
- 父进程和子进程并发运行。
关于fork 的返回值：pid
- pid = 0（在子进程中）
- pid > 0（在父进程中）（子进程ID）
- pid = -1 （出错）
fork( )执行流程
- 分配task_struct结构
- 拷贝父进程
  - 复制页表
    - 复制正文段、用户数据段及系统数据段
  - 复制task_struct
    - 修改task_struct小部分内容
- 把新进程加入进程列表。
- 置新进程为就绪状态
- fork ( ) → sys_fork ( ) → do_fork( )
进程的阻塞wait( )
- 检测有无子进程结束?
  - 没有:
    - 继续阻塞：等待子进程结束。
  - 有:
    - 收集该子进程信息并彻底销毁它，返回。
- Status接收子进程退出时的退出代码。
  - status：按位处理
  - 若忽略子进程的退出信息pid =wait(NULL)
进程的终结exit( )
- 调用void exit(int status)终结进程
- 进程终结时要释放资源并向父进程报告
  - 利用status向父进程报告结束时的退出代码
  - 变为僵尸状态，保留部分PCB信息供wait收集
    - 正常结束还是异常结束
    - 占用总系统cpu时间
    - 缺页中断次数
进程的休眠Sleep( )
- 进程暂停执行nSecond秒
- 系统暂停调度该进程
- 相当于windows挂起操作resume( )，挂起指定秒

线程

进程的并发性

进程与进程可以并发运行(共享CPU)
进程是系统中共享CPU的最小的并发单位
- 进程内部的指令和函数都是串行执行的
- 若多个任务要并发，则必须设计相应数量的程序。

定义

线程是进程内创建的可运行模块/指令序列，能执行指定的任务。
进程内可以定义多个线程
线程和线程可以并发运行。

意义

线程提高了系统的并发性能
- 线程的并发粒度比进程更细
- 更充分地发挥CPU的性能
线程的应用成本更低，更灵活
- 进程为线程提供资源和地址空间
  - 线程的创建，撤销和管理成本更低
  - 线程间通信更容易，更灵活
大多数操作系统都采用了线程技术

线程创建(windos)

功能：创建一个线程同时为其指定任务(TaskFunction)。
原型

HANDLE CreateThread (
LPSECURITY_ATTRIBUTES lpThreadAttributes,
DWORD dwStackSize,
LPTHREAD_ROUTINE ThreadFunction, //线程函数
LPVOID lpParameter //线程函数的参数
)

Linux线程和分类

内核线程

内核线程/Kernel Thread
创建函数：kthread_create( )
创建、运行和撤销都在内核完成，由内核驱动。
内核线程没有独立的地址空间mm=NULL
- 只在内核空间运行，不切换到用户空间；

用户线程

通过pthread线程库创建和管理
线程库提供同步和调度的方法。
用户线程不是真正的调度实体，内核对它们一无所知。
- 当一个进程被抢占时，它的所有用户线程都被抢占
- 当一个用户线程被阻塞时，它会阻塞其所属的进程

用pthread创建线程

int pthread_create( pthread_t * thread,
	pthread_attr_t * attr,
	void *(*ThreadFunc)(void *),
	void * arg);

创建函数：clone( )

同步/互斥

进程互斥的定义

多个进程共享具有独占性的资源时，必须确保各进程互斥地存取资源，即确保没有任何两个进程同时存取资源。
进程内设定特定区域，所有进程互斥地访问这些区域。

同步关系

若干合作进程为了共同完成一个任务，需要相互协调运行步伐：一个进程A开始某个操作之前要求另一个进程B必须已经完成另一个操作，否则进程A只能等待
合作进程中某些操作之间需要满足某种先后关系或某个操作能否进行需要某个前提条件满足，否则只能等待。
互斥关系属于特殊的同步关系。

同步机制

功能
1. 当进程的某个操作不能执行时（即运行条件不满足时）能让该进程立即暂停执行；
2. 当暂停的操作条件一旦满足时，能被立即唤醒继续运行。
3. 同步进制在实现上需要满足原子性。

临界资源

一次只允许一个进程独占访问（使用）的资源

临界区

进程中访问临界资源的程序段。

临界区和临界资源的共享特点

临界资源的访问具有排他性；
并发进程不能同时进入“临界区”

访问临界区的方法

硬件方法

中断屏蔽方法
- 进入临界区前
  - 执行“关中断”指令
- 离开临界区后
  - 执行“开中断”指令
测试并设置指令
交换指令

软件方法

锁
信号量

设计临界区访问机制的四个原则

忙则等待
- 当临界区忙时，其他进程必须在临界区外等待。
空闲让进
- 当无进程处于临界区时，任何有权进程可进入临界区。
有限等待
- 进程进入临界区的请求应在有限时间内得到满足
让权等待
- 等待进程放弃CPU。（让其它进程有机会得到CPU）。

锁

基本原理

设置一个“标志”S：
- 临界资源可用还是不可用？1:0
在进入临界区之前检查标志是否“可用”？
- 若为“不可用”状态
  - 进程在临界区之外等待
- 若为“可用”状态
  - 进入临界区,并将标志修改为“不可用”
  - 在临界区内访问临界资源……
- 退出临界区时
  - 将标志修改为“可用”状态

信号量和P-V操作

数据结构

信号灯定义为一个二元矢量（S, q）
S：整数，初值非负（S又称信号量）
q：队列(进程PCB集合)，初值为空集

操作

P操作（函数或过程）： P(S,q)
- Passeren通过
- 第1步：S值减1
- 第2步：判断S<0
  - 若S大于或等于零，该进程继续
  - 若S小于零，该进程阻塞并加入到q中，转调度函数
V操作（函数或过程）： V(S,q)
- Vrijgeven释放
- V操作可能会唤醒另一个正阻塞的进程。
- 第1步：S值加1
- 第2步：判断S <= 0
  - 若S大于零，该进程继续；
  - 若S小于或等于零，该进程继续同时从q中唤醒一个进程。

信号灯P-V操作的应用

实现进程互斥
- 实现对临界区的互斥访问
  - 1个临界资源：允许最多1个进程处于临界区
  - M个临界资源：允许最多M个进程同时处于临界区
- 应用过程
  - 进入临界区之前先执行P操作；
  - 离开临界区之后再执行V操作；
  - S的初值设置要合理
利用信号灯P-V操作实现同步
- 同步机制实质
  - 运行条件不满足时，能让进程暂停
  - 运行条件满足时，能让进程立即继续
- P-V操作应用于进程同步的基本思路
  - 在有条件执行的关键操作之前执行P操作
  - 在作执行条件的关键操作之后执行V操作
  - 定义有意义的信号量S，并设置合适的初值
    - 信号量S能明确地表示“运行条件”，
    - 不合理的初值不仅达不到同步的目的，还会发生死锁

经典同步问题

windos和linux同步实现

windos

临界区CRITICALSECTION

在进程内使用，保证仅一个线程可以申请到该对象
临界区是临界资源的访问
相关api
InitializeCriticalSection()初始化临界区
DeleteCriticalSection()删除临界区
EnterCriticalSection() 进入临界区
LeaveCriticalSection()退出临界区
等待函数
- 等待目标对象变成有信号的状态就返回
- WaitForMultipleObjects()
- WaitForSingleObject( )

互斥量mutex

保证只有一个线程或进程可以申请到该对象
可以跨进程使用
可以有名称
互斥量比临界区要消耗更多资源，速度慢

api

HANDLE CreateMutex( //创建互斥量
	LPSECURITY_ATTRIBUTES IpMutexAttributes,
	BOOL bInitialOwner,// 初始化互斥量的状态 : 真或假
	LPCTSTR IpName ）// 名字，可为NULL但不能跨进程用 
	);
HANDLE OpenMutex(//打开一个存在的互斥量
	DWORD dwDesiredAccess
	BOOL bInheritHandle
	LPCTSTR IpName// 名字 
);
BOOL ReleaseMutex( HANDLE hMutex):
BOOL CloseHandle(//关闭互斥量
HANDLE hObject // 句柄

信号量semaphore

允许指定数目的多个进程/线程访问临界区
一种资源计数器，用于限制并发线程的数量
初始值可以设置为N，则允许N个进程/线程并发访问资源

api

HANDLE CreateSemaphore( //创建信号量
	LPSECURITY ATTRIBUTES IpSemaphoreAttributes,// 安全属性
	LONG IInitialCount，// 初始值
	LONG IMaximumCount，// 最大值
	LPCTSTR lpName //名字 );
	HANDLE OpenSemaphore(//打打开信号量
	DWORD dwDesiredAccess，// 存取方式
	BOOL bInheritHandle， // 是否能被继承
	LPCTSTR IpName// 名字 
):
BOOL ReleaseSemaphore(//释放信号量
	HANDLE hSemaphore，// 句柄
	LONG IReleaseCount， // 释放数，让信号量的值增加的数量
	LPLONG IpPreviousCount // 得到释放前信号量的值，可为NULL
	);
BOOL CloseHandle(//关闭信号量
	HANDLE hObject
	);

事件event

用于通知一个或多个线程某事件出现或标识某操作已经完成
分类
- 自动重置的事件:使用WaitForSingleObiect等待到事件对象变为有信号状态后该事件对象自动变为无信号状态
- 人工重置的事件:使用WaitForSingleObiect等待到事件对象变为有信号状态后该事件对象的状态不变，除非人工重置事件。

api

HANDLE CreateEvent ( //创建事件对象
	LPSECURITY ATTRIBUTES pEventAttributes,// 安全属
	BOOL bManualReset，// 是否为人工重置
	BOOL bImitialState,// 初始状态是否为有信号状态
	LPCTSTR IpName //名字 
	):
HANDLE OpenEvent (//打开事件对象
	DWORD dwDesiredAccess，// 存取方式
	BOOL bInheritHandle， // 是否能够被继承
	LPCTSTR IpName// 名字 
	):
BOOL ResetEvent (//设置事件为无信号状态
	HANDLE hEvent // 句柄 ):
BOOL SetEvent (//设置事件有信号状态
	HANDLE hEvent // 句柄
	BOOL CloseHandle(//关闭事件对象
HANDLE hObiet //句柄

死锁

定义

两个或多个进程无限期地等待永远不会发生的条件的一种系统状态。
在两个或多个进程中，每个进程都已持有某种资源，但又继续申请其它进程已持有的某种资源。
- 每个进程都拥有其运行所需的部分资源，但又不足够运行，从而每个进程都不能向前推进，陷于阻塞状态。这种状态称死锁。

原因

系统资源有限
- 资源数目不足以满足所有进程的需要，引起进程对资源的竞争而产生死锁。
并发进程的推进顺序不当
- 进程在运行过程中，请求和释放资源的顺序不当，导致进程产生死锁。

关于死锁的一些结论

陷入死锁的进程至少是2个
参与死锁的进程至少有2个已经占有资源
参与死锁的所有进程都在等待资源
参与死锁的进程是当前系统中所有进程的子集
死锁会浪费大量系统资源，甚至导致系统崩溃

死锁的必要条件

互斥条件
- 资源具有独占性，进程互斥使用资源
不剥夺条件
- 资源被访问完之前(即在释放前)不能被其他进程剥夺
部分分配条件
- 进程所需资源逐步分配，需要时临时申请（等待分配）
- 占有一些资源，同时申请新资源
环路条件
- 多个进程构成环路：环中每个进程已占用的资源被前一进程申请，而自己所需新资源又被环中后一进程所占用。

预防死锁

通过设置某些限制条件，破坏死锁四个必要条件中的一个或多个，来防止死锁。
- 破坏互斥条件
- 破坏不剥夺条件
- 破坏部分分配条件(预先静态分配)
- 破坏环路条件(有序资源分配)

检测和恢复死锁

允许死锁发生，但可通过检测机制及时检测出死锁状态，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除，将进程从死锁状态解脱出来
检测方法
恢复方法
- 撤消或挂起一些进程，以回收一些资源
缺点
- 实现难度大

定义

调度定义

schedule队列
在队列中按某种策略选择最合适的对象(执行相应操作)。
分类
- 长程调度（宏观调度/作业调度）作业：磁盘→内存
- 中程调度（交换调度）进程：就绪(内存)→交换空间
- 短程调度（进程调度）进程：就绪(内存)→CPU
- I/O调度（设备调度）进程：阻塞(设备)→就绪

进程调度

在合适的时候以一定策略选择一个就绪进程运行.
目标
- 周转时间/平均周转时间
- 带权周转时间/平均带权周转时间
周转时间
- 进程(或作业)提交给计算机到完成所花费的时间
- 周转时间t = $完成时间t_c – 提交时间t_s$ $完成时间 t_{c} - 提交时间 t_{s}$
  - $t_s$ ——进程的提交时间（Start）
  - $t_c$ ——进程的完成时间（Complete ）
- 意义
  - 说明进程在系统中停留时间的长短。
平均周转时间
- $t = （t_1 + t_2 + … + t_n）/ n$
- 所有进程的周转时间的平均
- 平均周转时间越短意味着：平均停留时间越短，系统吞吐量越大，资源利用率越高。
带权周转时间w
- w = 周转时间t ÷ 进程运行时间(进程大小) r= $t / t_r$ $t / t_{r}$
  - t：进程的周转时间
  - $t_r$ ：进程的运行时间（run）
  - 意义：进程在系统中的相对停留时间。
平均带权周转时间
- $w = （w_1 + w_2 + … + w_n）÷ n$
- 所有进程的带权周转时间的平均

进程调度算法

先来先服务调度

算法
- 按照作业进入系统的时间先后次序来挑选作业。先进入系统的作业优先被运行。
特点
- 只考虑作业等候时间，不考虑作业大小(运行时间)
- 晚来的作业会等待较长时间
- 不利于晚来但是很短的作业

短作业优先调度算法

算法
- 参考运行时间，选取时间最短的作业投入运行。
特点/缺点
- 忽视了作业等待时间
- 早来的长作业会长时间等待(资源“饥饿”)

响应比高者优先调度算法

响应比定义
- 作业的响应时间（等待时间+运行时间）和与运行时间的比值
- $\begin{aligned} 响应比 &= 响应时间 / 运行时间 \\ &= 1 + 等待时间/运行时间 \\ &=加权周转时间(当前的) \end{aligned}$
算法
- 调度作业时计算作业列表中每个作业的响应比，选择响应比最高的作业优先投入运行。
特点
- 响应比= 1 + 等待时间/ 运行时间
- 有利于短作业
- 有利于等候已久的作业
- 兼顾长作业
应用
- 每次调度时重新计算和比较剩余作业的响应比

优先数调度算法

算法
- 根据进程优先数，把CPU分配给最高的进程。
- 进程优先数= 静态优先数+动态优先数
静态优先数
- 进程创建时确定，在整个进程运行期间不再改变
动态优先数
- 动态优先数在进程运行期间可以改变。
静态优先数的确定
- 基于进程所需的资源多少
- 基于程序运行时间的长短
- 基于进程的类型
动态优先数的确定
- 当进程使用CPU超过一定时长时；
- 当进程等待时间超过一定时长时
- 当进行I/O操作后

循环轮转调度法

算法
- 把所有就绪进程按先进先出的原则排成队列。新来进程加到队列末尾
- 进程以时间片q为单位轮流使用CPU。刚刚运行了一个时间片的进程排到队列末尾，等候下一轮调度。
- 队列逻辑上是环形的
优点
- 公平性：每个就绪进程有平等机会获得CPU
- 交互性：每个进程等待(N-1)* q的时间就可以重新获得CPU
时间片q的大小
- 如果q太大
  - 交互性差
    - 甚至退化为FCFS调度算法
- 如果q太小
  - 进程切换频繁，系统开销增加
改进
- 时间片的大小可变（可变时间片轮转调度法)
- 组织多个就绪队列（多重时间片循环轮转）

调度方式

定义

当一进程正在CPU上运行时，若有更高优先级的进程进入就绪，系统如何对待新进程（分配CPU）？

非抢占方式

让正在运行的进程继续运行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把CPU分配给新来的更高优先级的进程。

抢占方式

让正在运行的进程立即暂停，立即把CPU分配给新来的优先级更高的进程。

linux进程调度

基本特点

基于优先级调度；
支持普通进程，也支持实时进程
实时进程优先于普通进程
普通进程公平使用CPU时间

LINUX进程优先级（task_struct成员变量）

priority/静态优先数
priority = priority - #
[-20～19]
- 普通用户：自己进程，[ 0, 19 ]
- root用户：任何进程，[-20, 19 ]
counter/动态优先数
- 初值= priority
- 用于实际比较的优先数
- 进程在当前一轮调度中还能连续运行的时间片数量
- counter越大，优先级越高，可获得越多CPU时间
- 新一轮调度开始时
  - counter = priority
- 时钟中断服务程序
  - counter - -
- 特定情形
  - counter = counter + △
- 所有进程的counter都减到0后
  - 重新开始新一轮调度

内存管理的功能

存储器功能需求

容量足够大
速度足够快
信息永久保存
多道程序并行

三级存储体系

内存
辅存
cache
基本思想
- 用辅存支援内存，提高容量
- 用cahe支援内存，提高效率

换出与换出（辅存与内存）

放入原来位置
- 程序简单
- 地址冲突
任一位置
- 利用内存灵活
- 地址需要重定位
地址重映射
- 重新确定指令中目标数据的正确地址（更新地址）
- 新的值与目标程序块的实际放置位置有关

多道程序并行的问题

保护
- 禁止程序间越权访问
共享
- 代码和数据共享，节省内存

存储管理的功能

1.地址映射

定义
- 地址重定位，地址重映射
- 把程序中的地址（虚拟地址,虚地址,逻辑地址,相对地址）变换成真实的内存地址（实地址,物理地址,绝对地址）的过程
  - 虚拟地址/源程序地址：地址，变量，标号，函数名
- 逻辑地址
  - 多道程序环境
  - 目标模块/装入模块：使用内部的线性地址：[0~N)
- 物理地址
  - 内存单元的绝对地址
    - 数据实际存放位置
  - 单道程序环境中、
    - 程序装入的起始地址可以预知。
    - 程序中直接指明数据/指令的物理地址。
  - 多道程序环境中
    - 程序不能预知装入的地址
    - 程序中无法明确地使用物理地址。
固定地址映射
- 定义
  - 编程或编译时确定逻辑地址和物理地址映射关系。
- 特点
  - 程序加载时必须加载到指定的内存区域。
  - 容易产生地址冲突，运行失败。
  - 不能适应多道程序环境
静态地址映射
- 定义
  - 程序装入时由操作系统完成逻辑地址到物理地址的映射
  - 保证程序在运行之前所有地址都绑定到主存
- 映射方式
  - 物理地址MA = 装入基址BA + 虚拟地址VA
- 特点
  - 程序运行之前确定映射关系
  - 程序占用连续的内存空间
  - 程序装入后不能移动
    - 如果移动必须放回原来位置
动态地址映射
- 在程序执行过程中把逻辑地址转换为物理地址
- 映射方式
  - 物理地址MA = 装入基址BA + 虚拟地址VA
  - 装入基址：基址寄存器BAR
  - 切换进程的同时切换基址寄存器BAR
  - IR = 指令寄存器
    - 保存的是VA(虚拟地址)
- 程序可分配到不连续的多块内存中存放
  - 按段编译
    - 段内地址：线性地址
  - 按段装入，不同段放入不同内存块
    - 每段维护一个段寄存器
      - 段的重定位寄存器
  - 段式存储管理
  - 段的切换
- 特点
  - 程序占用的内存空间可动态变化
  - 程序不要求占用连续的内存空间
  - 便于多个进程共享代码
- 缺点：
  - 硬件支持（MMU：内存管理单元）
  - 软件复杂

2.存储扩充/虚拟存储

目的
- 程序过大或过多时，内存不够，不能运行
- 多个程序并发时地址冲突，不能运行
解决1
- 借助辅存在逻辑上扩充内存，解决内存不足
- 迁入：装入将要运行的部分到内存
- 迁出：把不运行部分暂存到辅存上
前提：
- 有适当容量的内存
- 有足够大的辅存
- 有地址变换机构
应用：
- 页式虚拟存储
- 段式虚拟存储

3.内存分配

为程序运行分配足够的内存空间
解决的问题
- 放置策略
  - 程序调入到内存哪个/哪些区域
- 调入策略
  - 何时把要运行的程序调入内存？
  - 预调策略| 请调策略
- 淘汰策略
  - 迁出（/淘汰）哪些程序以腾出内存空间。

4. 存储保护

保证内存中的多道程序只能在给定区域活动，并且互不干扰。
- 防止访问越界
- 防止访问越权
方法：
- 界址寄存器
  - 上限地址寄存器/下限地址寄存器
  - 基址寄存器和限长寄存器
  - 适于连续物理分区中的情形
- 存储键保护
  - 适于不连续物理分块的情形，也可用于共享中的权限。

物理内存管理

单一区存储管理

定义
- 用户区不分区，完全被一个程序占用。
优点
- 简单不需复杂硬件支持
缺点
- 程序占用整个内存
- 内存浪费，利用率低
场景
- 适于单用户单任务OS

分区存储管理

定义
- 把用户区分为若干大小不等的分区，供不同程序使用。
分类
- 固定分区
  - 系统初始化时分区
  - 特点
    - 运行时分区的大小和位置不变
    - 分区大小不同，适应不同程序需求
  - 分区表
    - 记录分区的位置、大小和占用标志
  - 缺点
    - 浪费内存
    - 大程序可能无法运行
    - 程序过多无法运行
  - 应用
    - 程序的装入数量和顺序要与分区的数量、大小顺序尽量保持一致。
- 动态分区
  - 程序装入时临时分区
  - 分区回收
    - 收回占用分区，以便重新分配
    - 回收时要考虑释放区和相邻区的合并
  - 分区再分配
  - 特点
    - 分区的个数和大小均可变
    - 存在内存碎片（外部碎片）
  - 放置策略(分区的选择)
    - 空闲区表
      - 描述内存空闲区的位置和大小的数据结构
    - 首次适应法
      - 空闲区表按首址递增排序
      - 尽可能先利用低地址空间
    - 最佳适应法
      - 空闲区表按大小递增排序
      - 尽量先选中满足要求的最小空闲区
    - 最坏适应法
      - 空闲区表按大小递减排序
      - 尽量先使用最大的空闲区
      - 仅作一次查找就可找到所要分区。
  - 分区的分配
    - 从用户选中的分区中分配/分割所需大小给用户
    - 剩余部分（若有）依然作为空闲区登记
    - 分割空闲区时一般把 (底部) 分割给用户(这样空闲区表就只需要修改大小)。
  - 缺点：
    - 容易产生内存碎片：内存反复分配和分割
内存碎片
- 过小的空闲区
- 难以实际利用
- 外部碎片
  - 所有分区之外的碎片(单独的分区)
- 内部碎片
  - 分区内部出现的碎片。
    - 固定分区的某分区剩下部分。
    - 分⻚系统引起的⻚内碎片
解决碎片的方法
- 规定门限值
  - 分割空闲区时，若剩余部分小于门限值，则此空闲区不进行分割，而是全部分配给用户。
- 内存拼接技术
  - 将所有空闲区集中一起构成一个大的空闲区。
  - 拼接的时机
    - 释放区回收的时候
    - 系统找不到足够大的空闲区时
    - 定期
  - 缺点
    - 消耗系统资源
    - 离线拼接
    - 重新定义作业

Overlay(覆盖)

在较小的内存空间中运行较大的程序
内存分区
- 常驻区：被某段单独且固定地占用的区域，可划分多个
- 覆盖区：能被多段共用（覆盖）的区域，可划分多个
工作原理
- 程序分成若干代码段或数据段
- 将程序常用的段装入常驻区；（核心段）
- 将程序不常用段装入覆盖区；
  - 正运行的段处于覆盖区；
  - 暂时不运行的段放在硬盘中(覆盖文件)；
  - 即将运行的段装入覆盖区（覆盖旧内容）；
缺点
- 编程复杂：程序员划分程序模块并确定覆盖关系。
- 程序执行时间长：从外存装入内存耗时

Swapping（对换技术）

原理：
- 内存不够时把进程写到磁盘（换出/Swap Out ）。
- 当进程要运行时重新写回内存（换入/Swap In ）。
优点：
- 增加进程并发数；
- 不考虑程序结构。
缺点
- 换入和换出增加CPU开销；
- 对换单位太大（整个进程）：
问题：
- 程序换入时的地址重定位
- 减少对换传送的信息量
- 外存对换空间的管理方法

虚拟内存管理

页式内存管理

概念

目的
- 小内存中运行大程序和多个程序
程序和内存的划分
- 程序和内存都划成等大小（例4KB）的小片：页面和页框
程序的装入方式
- 程序以页面为单位装入页框
- 内存以页框为单位使用

原理

程序运行的局部性
- 在任何有限时段内程序的运行活动一般局限在有限范围内。
仅把程序的局部装入内存中
- 仅把当前时段涉及的部分页面装入内存(可让程序短暂运行)
- 运行过程逐步装入新页面
  - 已运行过的旧页面可删除
确保有限时段内程序只占用了少量的内存。
进程装入和使用内存的原则
- 局部装入，不断更新
  - 只把程序部分页装入内存便可运行。
  - 页在内存中占用的页框不必相邻。
  - 需要新页时，按需从硬盘调入内存。
  - 不再运行的页及时删除，腾出空间

地址

虚拟地址VA是线性的，从0开始
VA分成页号P和页内偏移W
- P=VA/页大小
- W=VA%页大小
- 计算方法
页面映射表（页表）
- 记录页面与页框(块)之间的对应关系。也叫页表。
- 页号：登记程序地址的页号。
- 页框号：登记页所在的物理页号。
- 页面其他特性：登记含存取权限在内的其他特性。
- 建立
  - 操作系统为每个进程建立一个页表
    - 页表的基址存放在进程控制块中
    - 页表的内容由内核负责填充和更新
  - 当前进程的页表驻留在内存
    - 页表基址：页表基址寄存器
地址映射
- 虚拟地址(页式地址)->物理地址
- 步骤：
  1. 计算P，W
  2. 根据页表，得到页框号 $P'$
  3. 计算MA= $P'\times页大小+页内偏移W=P'<<n||页内偏移$

缺页中断

定义
- 当程序要访问的目标页面不在内存时，程序将被迫临时中断：缺页中断
处理
- 立即将所缺页面装入内存
- 页面从硬盘拷贝到内存
  - I/O操作，耗时较长
- 缺页中断降低了程序实时性
扩充有中断位I和辅存地址的页表
- 中断位I ——标识该页是否在内存?
  - 若I =１，不在内存
  - 若I =０，在内存q
- 辅存地址——该页在辅存上的位置
扩充有访问位（引用位）和修改位（Dirty）的页表
- 访问位——标识该页最近是否被访问？
  - ０——最近没有被访问
  - １——最近已被访问
- 修改位——标识该页的数据是否已被修改？
  - ０——该页未被修改
  - １——该页已被修改
缺页中断处理程序
- 中断处理程序把所缺的页从页表指出的辅存地址调入内存的某个页框中，并更新页表中该页对应的页框号以及修改中断位I为0。
缺页率
- 缺页率f = 缺页次数/ 访问页面总次数
- 命中率= 1 – f
访存指令流程

淘汰策略

选择淘汰哪一页的规则称淘汰策略。
页面抖动
- 页面在内存和辅存间频繁交换的现象
- “抖动”会导致系统效率下降。
好的淘汰策略
- 页面抖动较少
- 具有较低的缺页率（高命中率）
最佳算法（OPT算法）
- 淘汰不再需要或最远将来才会用到的页面。
- 特点
  - 理论上最佳，实践中该算法无法实现。
先进先出淘汰算法（FIFO算法）
- 淘汰在内存中停留时间最长的页面
- 优点：
  - 实现简单：页面按进入内存的时间排序，淘汰队头页面。
  - 进程按顺序访问地址空间时抖动较少，缺页率较低。
- 异常现象
  - 对于一些特定的访问序列，分配页框越多，缺页率越高
最久未使用淘汰算法（LRU算法）
- 淘汰最长时间未被使用的页面。
- 实现(硬件)
  - 页面设置一个移位寄存器R，页面被访问则重置为1
  - 周期性地(周期很短)将所有页面的R左移1位(右边为0)
  - 当需要淘汰页面时选择R值最大的页
  - R的位数越多且移位周期越小就越精确，但硬件成本也越高。
  - 若R的位数太少，可能同时出现多个为0页面情况，难以比较。
- 软件实现
  - 软件周期性（T）地将所有访问位置0
  - 当淘汰页面时根据该页访问位来判断是否淘汰
    - 访问位为1：不淘汰：在时间T内，该页被访问过。
    - 访问位为0：可以淘汰：在时间T内，该页未被访问过！
- 缺点
  - 周期T难定
最不经常使用（LFU）算法
- 选择到当前时间为止被访问次数最少的页面
- 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；
- 发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零

影响缺页次数的因素

淘汰算法
分配给进程的页框数
- 页框越少，越容易缺页
页本身大小
- 页面越小，容易缺页
页面的大小选择
- 常见大小：2的整数次幂：1KB，2KB, 4KB
- 页面太大
  - 页面增多，页表长度增加，浪费内存；
- 页面太小
  - 换页频繁，系统效率低

快表机制(cache)

分级存储体系
- CACHE + 内存+ 辅存
快表的特点
- 快表是普通页表（慢表）的部分内容的复制
- 地址映射时优先访问快表
  - 若在快表中找到所需数据，则称为“命中”
  - 没有命中时，需要访问慢表，同时更新快表
- 合理的页面调度策略能使快表具有较高命中率
地址映射过程

页面的共享

在页表中填上被共享代码（共享页框）的页框号。
- 共享代码/共享页框在内存只有一份存储。

二级页表

把页表(4MB)分拆成1K个小页表(4KB)且分散存放
为了对小页表进行管理和查找，另设置一个叫页目录的表，记录每个小页表的存放位置（即页框号）
- 页目录：1K条记录[小页表号: 页框号]，4KB
- 页目录：一级页表或外部页表
- 小页表：二级页表/页表

缺点

页面划分无逻辑含义
页的共享不灵活
页内碎片

段式内存管理

定义

进程分段
- 把进程按逻辑意义划分为多个段，每段有段名，长度不定。进程由多段组成
段式内存管理系统的内存分配
- 以段为单位装入，每段分配连续的内存；
- 段和段不要求相邻。
段表
- 记录每段在内存中映射的位置
- 段号S ：段的编号（唯一的）
- 段长L ：该段的长度
- 基地址B ：段在内存中的地址

映射机制

虚拟地址
- 段式虚拟地址VA包含段号S和段内偏移W
- VA:(S,W)
映射过程
1. 逻辑地址VA分离出(S, W);
2. 以S为索引查询段表
  - 检索段号S，查询该段基地址B和长度L
3. 物理地址MA＝ B+W
段表的扩充
- 基本字段：段号，长度，基址
- 扩展字段：中断位，访问位，修改位，R/W/X
段的共享
- 共享段在内存中只有一份存储
- 需要共享的模块都可以设置为单独的段
- 共享段写入相关进程的段表
缺点：
- 段需要连续的存储空间
- 段的最大尺寸受到内存大小的限制
- 在辅存中管理可变尺寸的段比较困难

段式系统vs 页式系统

地址空间的区别
- 页式系统：一维地址空间
- 段式系统：二维地址空间
段与页的区别
- 段长可变vs 页面大小固定
- 段的划分有意义vs 页面无意义
- 段方便共享vs 页面不方便共享（相对）
- 段用户可见vs 页面用户不可见
- 段偏移有溢出vs 页面偏移无溢出

段页式存储

在段式存储管理中结合页式存储管理技术
在段中划分页面

地址映射

段号S、页号P和页内位移W
段页式地址的映射机构
- 同时采用段表和页表实现地址映射
  - 系统为每个进程建立一个段表
  - 每个段建立一个页表
- 段表给出每段的页表基地址及页表长度
  - 页表给出段内每页对应的页框

LINUX存储管理

实模式（Real Mode）

实模式阶段
- 计算机加电前一段时间处于实模式
实模式寄存器
- IP，AX，BX，CX，DX，SP，BP，SI，DI，FLAGS，CS，DS，SS，ES，FS，GS
实模式内存空间
- 20位物理地址
- 1MB内存空间
- 分段机制：段地址(16位)：偏移地址(16位)
实模式寻址
- 逻辑地址：段地址(16位) ：偏移地址(16位)
- 物理地址= 段地址左移4位+ 偏移地址

保护模式

保护模式寻址
- 段基址=段基址( DS )
- 全局描述符表/GDT
  - Global Descriptor Table
  - 全局唯一一个，每个进程可见
- 局部描述符表/LDT
  - Local Descriptor Table
  - 每个进程/任务一个，表内含有进程的各种私有段的描述符。
  - LDT的描述符位于GDT中
    - LDT描述符
- 优化分段管理机制
- 支持分⻚管理机制
- 4GB内存空间（32位）
CPU特性
- 支持多任务
- 支持特权级机制
- 扩展寄存器和新增寄存器
  - EAX~EDX，EIP，ESP，ESI，EDI，EFLAGS
  - CR0~CR4，GDTR，LDTR，IDTR，TR
- 控制寄存器CR0
  - PE: 保护模式/实模式
  - MP: 有无数学协处理器
  - EM: 有无仿真协处理器
  - TS: 切换任务时自动设置
  - ET: 协处理器的类型
  - PG: 是否允许分页

描述符（Descriptor）

属性的描述
- DPL:描述符特权级别Descriptor Privilege Level
- P：Present，是否在内存中（1：在内存）
- G：段的粒度（段长计量单位）
  - G=0, 字节(段最长1M)
  - G=1 ,页面4KB（段最长4G）
- S |TYPE：描述符的类型和特性
  - S=1（存储段）| S=0（系统段）
  - TYPE=4位
    - 存取属性、特性类型
    - 读，写，访问标志等
- 例子：quad 0x 00C0 9A80 0000 001F
  - 结构
  - G=1，P=1,DPL=00,S=1
描述符表（Descriptor Table）
- 存放描述符的数组/线性表
- ⻓度：8字节的整数倍。
- 分类
  - 全局描述符表GDT
  - 局部描述符表LDT
  - 中断描述符表IDT
- 选择子(Selector) /16位/段寄存器
  - 用于选择GDT/LDT等表中的描述符
  - 索引域（INDEX）
    - 13位，描述符在描述符表中的序号3-15
  - 表标识域（TI，Table Indicator）
    - 1位：GDT(0)|LDT(1)2
  - 请求特权级域（RPL）
    - 2位，Request Privilege Level0-1
  - 选择子放在段寄存器中
GDTR（48位）
- GDT的基址（32位）
- GDT的限长（16位）
  - GDT中描述符数量≤ 8k
- lgdtr:更新GDTR
LDTR（16位）
- 选择子
  - 选择GDT中的描述符/LDT描述符
- lldtr:更新LDT/进程切换

保护模式内存寻址：段式地址转换

把逻辑地址转换到物理地址/线性地址

设备管理概述

类型和特征

按交互对象分类
- 人机交互：显示设备、键盘、鼠标、打印机
- 与CPU交互：磁盘、磁带、传感器、控制器
- 计算机间交互：网卡、调制解调器
按交互方向分类
- 输入设备：键盘、扫描仪
- 输出设备：显示设备、打印机
- 双向设备：输入/输出：硬盘、软盘、网卡
按外设特性分类
- 使用特征：存储设备、输入设备、输出设备
- 数据传输率：低速(键盘)、中速(打印机)、高速(网卡、磁盘)
按信息组织特征分类
- 字符设备
  - 传输的基本单位是字符。例：键盘、串口
- 块设备
  - 传输的基本单位是块。例：硬盘，磁盘
- 网络设备
  - 采用socket套接字接口访问
  - 在全局空间有唯一名字，如eth0、eth1

设备管理功能

目标：
- 1）提高设备读写效率
  - 设备缓冲机制
- （2）提高设备的利用率
  - 设备分配（设备调度）
- （3）为用户提供统一接口
  - 实现设备对用户透明

状态跟踪

记录设备的基本属性、状态、操作接口及进程访问信息
- 设备控制块（Device Control Block，DCB)
  设备名
  设备属性
  命令转换表
  在I/O总线上的设备地址
  设备状态
  当前用户进程指针
  I/O请求队列指针
- 设备名
  - 设备的物理名
- 设备属性
  - 设备当前状态（一组属性）
- 命令转换表
  - 设备操作接口

设备名
设备属性
命令转换表
在I/O总线上的设备地址
设备状态
当前用户进程指针
I/O请求队列指针

设备分配

按一定策略安全地分配和管理各种设备。
- 按相应算法把设备分配给请求该设备的进程，并把未分到设备的进程放入设备等待队列。

设备映射

设备逻辑名/友好名(Friendly Name)
- 用户编程时使用的名字（文件名/设备文件名）
- 例：Linux： /dev/test
设备独立性/设备无关性
- 用户程序中使用统一接口访问逻辑设备，而不用考虑对应物理设备的特殊结构和操作方式。

I/O缓冲区管理

开辟和管理I/O缓冲区
提高读写效率

设备控制/设备驱动

对物理设备进行I/O操作（IN/OUT指令）
把应用对设备的读/写请求转换为对设备I/O操作。
应用读写请求采用文件接口
- open/read/write/close
- 设备是文件
设备驱动程序的特点
- 设备驱动程序与硬件密切相关。
- 设备必须要配置驱动程序
- 动程序一般由设备厂商根据操作系统要求编写

缓冲技术

缓冲作用

连接不同数据传输速度的设备
- CPU（设备驱动）与设备（控制器）之间传输数据
- 内存中增加缓冲区
协调数据记录大小的不一致
- 进程之间或CPU与设备之间的数据记录大小不一致
- 进程（结构）：设备（字节）
正确执行应用程序的语义拷贝
- 利用write( Data, Len)向磁盘写入数据Data
- 方法1：应用等待内核写完磁盘再返回(实时性差)
- 方法2：应用仅等内核写完内存即返回
  - 事后由内核把缓冲区写到磁盘。(实时性好)
- 语义拷贝：确保事后拷贝的数据是正确版本

Linux缓冲机制应用

典型的块设备

硬盘、软盘、RAM DISK等
块(block)和扇区
- 硬盘读/写/寻址：扇区
- 文件读/写/寻址：块
  - 块= 2n ×扇区
  - Linux块= 1KB (n=1)

Linux缓冲机制

内存开辟高速缓冲区
提前读
- 进程读时，其所需数据已被提前读到了缓冲区中，不需要启动外设去执行读操作。
延后写
- 进程写时，数据先存在缓冲区，等到特定事件发生或足够时间后（已延迟），再启动外设完成写入。
目的：
- 提高进程与外设数据传输效
- 减少访问设备次数，提高设备访问的效率。
- 内存开辟高速缓冲区

高速缓冲区(内存区)

按块分为缓冲块(数据块)，与磁盘块对应
缓冲头（buffer_head）：描述缓冲块

struct buffer_head{
char* b_data//指向缓冲块对应的数据区
unsigned long b_blocknr//设备中的块号
unsigned short b_dev//设备号
unsigned char b_lock//表示该缓冲块是否已被锁定
unsigned char b_count//缓冲块被多少个进程引用
unsigned char b_dirt//延迟写字段，即脏位字段
unsigned char b_uptodate//数据有效位字段
struct task_struct* b_wait//指向访问缓冲块的等待队列
}

进程读写设备数据
- 进程read/write →文件访问请求→ 块读取bread( )
块读取函数bread(设备号,块号)
- 以(设备号, 块号)为索引搜索高速缓冲区，查找对应的缓冲块
  - 若找到，直接读回
  - 若没有找到
    - 分配一个新缓冲块
    - 调用ll_rw_block( )读相应磁盘块到新分配的缓冲块

组成

Cache
- 高速缓冲寄存器【CPU ↔ 内存】
设备内部缓冲区
- 外设或I/O接口的内部缓冲区【端口】
内存缓冲区
- 应用广泛，使用灵活【CPU ↔ 接口/外设】
- 应用开辟| 内核开辟
辅存缓冲区
- 开辟在辅存上【暂存内存数据，SWAP】

实现

单缓冲
- 缓冲区仅有1个单元
双缓冲
- 缓冲区有2个单元
环形缓冲
- 在双缓冲的基础上增加了更多的单元，并让首尾两个单元在逻辑上相连
- pStart起始指针
- pWrite输入指针
- pRead输出指针
缓冲池
- 多个缓冲区
- 可供若干个进程共享
- 可以支持输入，也可以支持输出
- 提高缓冲区利用率，减少内存浪费

设备驱动程序

定义设备操作接口与文件操作接口之间的映射
实现设备的注册函数和注销函数
设备注册
- 将用户定义的设备加入到系统的设备数组
设备注销
- 释放设备，将设备从系统的设备数组删除
编译驱动程序
安装/删除驱动程序
```
insmod RWDevState.ko
rmmod RWDevState
```
创建设备文件

驱动程序在系统中的地位

面向用户程序的接口

设备的打开与释放
设备的读写操作
设备的控制操作
设备的中断处理
设备的轮询处理

面向I/O管理器的接口

注册函数
- insmod(命令)
  - module_init() (API)
注销函数
- rmmod (命令)
  - module_exit() (API)
必需的数据结构

面向设备的接口

实现设备的端口操作
- 无条件传送
- 查询传送
- 中断传送
- DMA传送

驱动程序工作在核态

驱动程序工作在内核态
应用程序和驱动程序之间传送数据
- get_user( )
- put_user( )
- copy_from_user ( )
- copy_to_user ( )

设备文件

主设备号
- 标识该设备种类，标识驱动程序
- 主设备号的范围：1-255
- Linux内核支持动态分配主设备号
次设备号
- 标识同一设备驱动程序的不同硬件设备

设备分配

设备分类

独占设备

不可抢占设备（普通外设或资源）
- 使用时抢占，释放后才能被其他进程申请到
- 先申请，后使用（主动）

共享设备

可抢占设备（CPU，内存，硬盘）
- 允许多个作业或进程同时使用。
- 不申请，直接用（被动+ 主动）

虚拟设备

借助虚拟技术，在共享设备上模拟独占设备。

分配方法

独享分配

针对独占设备
流程：申请→占用→释放
- 指进程使用设备之前先申请，申请成功开始使用，直到使用完再释放。
若设备已经被占用，则进程会被阻塞，被挂入设备对应的等待队列等待设备可用之时被唤醒。

共享分配

针对共享设备
- 典型共享设备：硬盘
当进程申请使用共享设备时，操作系统能立即为其分配共享设备的一块空间（空分方式），不让进程产生阻塞。
共享分配随时申请，随时可得。

虚拟分配

虚拟技术
- 在一类物理设备上模拟另一类物理设备的技术
- 通常借助辅存部分区域模拟独占设备，将独占设备转化为共享设备。
虚拟设备
- 用来模拟独占设备的辅存区域称为虚拟设备
  - 具有独占设备的逻辑特点
- 输入井：模拟输入设备的辅存区域
- 输出井：模拟输出设备的辅存区域
当进程申请独占设备时将对应虚拟设备分配给它
- 首先，采用共享分配为进程分配虚拟设备
- 其次，将虚拟设备与对应的独占设备关联
- 进程运行中仅与虚拟设备交互，提高了运行效率

SPOOL技术

结构（硬件）

输入和输出井

磁盘上开辟出来的两个存储区域
- 输入井模拟脱机输入时的磁盘
- 输出井模拟脱机输出时的磁盘

输入缓冲区和输出缓冲区

内存中开辟的存储区域
- 输入缓冲区：暂存输入数据，以后再传送到输入井。
- 输出缓冲区：暂存输出数据，以后再传送到输出设备。

预输入程序

控制信息从独占设备输入到辅存，模拟脱机输入的卫星机

输入表

独占设备↔虚拟设备

缓输出程序

控制信息从辅存输出到独占设备，模拟脱机输出的卫星机；

输出表

独占设备↔虚拟设备

井管理程序

控制用户程序和辅存之间的信息交换

优点

“提高”了I/O速度
将独占设备改造为“共享”设备
- 实现了虚拟设备功能

文件和文件系统概念

文件

文件是计算机系统存放信息的一种形式，由若干信息项有序构成。
文件具有唯一的文件名。
用户通过读写指针来存取文件的信息项。

文件的分类

按文件的用途
- 系统文件
- 库文件
- 用户文件
按文件的操作权限
- 只读文件
- 只写文件
- 可执行文件
- 可读可写文件
- 不保护文件
按文件的存储时间
- 永久文件
- 临时文件
按文件的性质
- 普通文件
- 目录文件
- 设备文件

文件系统

管理文件的机构
- 实现文件的创建、撤消、读写、修改、复制和存取控制等
  - 方便用户以文件名存取文件
- 管理文件存储设备的空间和存取
  - 高效利用存储空间和高效存取文件

文件结构

文件的逻辑结构

记录式文件

信息项是记录，记录包含若干成员
特点：
- 文件头部保存记录长和记录数信息
- 浪费存储空间
分类
- 定长记录文件
- 不定长记录文件

流式文件

信息项是字节
特点
- 文件长度就是字节的数量
- 文件无需额外说明信息或控制信息
现代OS把文件当作流式文件，由应用解释

文件的存取方法

顺序存取
- 按从前往后的顺序对文件信息项进行读/写直到定位到目标信息项为止
随机存储/直接访问
- 直接定位到文件目标信息项进行读写
- 适合流式文件或定长记录文件

文件的物理结构

文件在存储设备上的存储结构
签掉合理利用储存空间，缩短I/O时间
类型
- 连续文件
  - 连续文件指文件存放在连续的存储块中。
- 串联文件
  - 串联文件存放在离散的存储块中，每个存储块包含一个链接指针记录下一个存储块位置。
  - 例子：FAT文件系统
    - File Allocation Table，FAT，文件分配表
    - 文件分配表是一维数组，与存储设备空间对应，元素与存储块一一有序对应，每个元素存放文件下一个逻辑块所在存储块的块号。
    - FAT16文件系统
    - 存储块（簇） = 64个扇区
    - FAT元素16位宽,存储块(簇)数 ≤ 216簇
    - 磁盘容量 $\le2^{16}簇* 64扇区* 512字节= 2GB$
- 索引文件
  - 读取索引文件时应先读取索引表
  - 索引表本身占据额外的存储区域/缺点
  - 支持顺序和随机存取
  - 支持文件动态增长、插入、删除等
  - 实例：ext系列文件系统(inode索引节点文件)

存储空间管理

磁盘存储空间管理

管理和记录磁盘空间使用情况。

空闲文件目录

空闲文件：连续的空闲存储块组成的特殊文件。
- 存储设备上所有的空闲文件就代表了存储设备上的全部空闲空间。
空闲文件目录：为所有空闲文件建立的目录
- 记录空闲文件的首块号和存储块数(或其他方式)

空闲块链

把所有空闲存储块用链表链接在一起。
- 当申请空闲块时，从链表头部摘取空闲块
- 当回收存储块时，把空闲块加在链表尾部。

位示图

一块特殊内存区域，每一位(bit)对应一个存储块，值1表示存储块空闲，0表示已占用。

文件目录

功能
- 实现“按名存取”：系统根据文件名能找到指定文件。
  - 文件目录记录文件的文件名、存放地址以及属性
目录文件
- 目录文件是文件目录的实现，由文件目录项构成
文件目录项
- 描述文件基本信息、使用信息和存取控制信息等。
  - 基本信息：文件名、存储位置(存储块号)等
  - 使用信息：属性、大小、建立时间、修改时间等
  - 存取控制信息：文件存取权限
目录结构
- 单级目录
  - 最简单的目录结构，全部文件都登记在同一目录中。
  - 简单、易于理解和实现
  - 缺点
    - 查找速度慢| 不允许重名| 不便于文件共享
- 二级目录
  - 第一级称为主目录(MFD)，第二级称为子目录或用户目(UFD)。
    - 每个用户有一个子目录(用户目录)
  - 解决文件重名的问题，不同用户可以使用相同名字。
- 树状目录
  - 多级目录结构，二级目录结构的扩充
  - 目录结构如同倒置的树，树根是主目录(根目录)，枝结点是子目录，树叶描述文件。

文件全名

从根目录到文件为止整个通路上所有目录、子目录和文件的名字用”/”顺序连接构成的字符串称为文件全名。
- 路径名：文件全名中由目录和子目录组成的部分。
  - 每个文件都有惟一的路径名。
- 路径名的表达形式
  - 绝对路径名：从根目录直到文件的路径
  - 相对路径名：从指定目录到文件的路径
文件属性
- 相对路径名：从指定目录到文件的路径
- 文件的属性一般存放在文件的（目录/文件）中。
文件操作
- 创建文件
- 写文件
- 读文件
- 文件定位
- 删除文件
- 截短文件
- 属性设置和读取
目录操作
- 创建目录
- 删除目录 1,鸿蒙OS的技术架构分为内核层、系统服务层、框架层、应用层(√) 2,鸿蒙OS的技术特点为分布式软总线、分布式设备虚拟化、分布式数据管理、分布式任务调度、一次开发，多终端部署、系统统一，弹性部署(×) 3、鸿蒙OS技术架构从上往下分别为（A ） A、应用层系统服务层框架层内核层 B、应用层框架层系统服务层应用层 C、系统服务层框架层应用层内核层 D、框架层内核层系统服务层应用层 4、鸿蒙OS具备（C）三大核心能力 A、分布式软总线、分布式设备虚拟化、分布式数据管理 B、分布式设备虚拟化、分布式数据管理、分布式任务调度 C、分布式软总线、分布式数据管理、分布式安全 D、分布式设备虚拟化、分布式数据管理、分布式安全 5、鸿蒙OS系统功能设计按照下列（C ）顺序从整体到局部逐级展开。 A.系统-> 功能-> 子系统-> 模块B.模块-> 功能-> 子系统-> 系统 C.系统-> 子系统-> 功能-> 模块D.模块-> 子系统-> 功能-> 系统 6，BUILD.gn文件中sources = [ “LED.c”, ] 表明编译生成静态库的源代码文件来源于LED.c （√ ） 7、vscode与Ubuntu通过命令（C）bossay@ip -A链接 A、scp B、vim C、ssh D、snp 8、程序编译完成后烧录到开发板中的文件存在于（B）文件中 A、device B、out C、build D、vendor 9、程序通过串口烧录到开发板中时，不需要选择auto burn选项（×） 10、烧录完成后、将Disconect切换成Connect就按下复位键运行程序的话、会导致程序重新烧录（√）

（1）已发群中“鸿蒙专题复习.pdf”要复习，是考试内容之一。（2）进程调度算法，尤其是Linux进程调度基本原理（优先数调度）要搞懂，这是典型的调度算法，也是课程设计的内容。（3）内存管理：理解分页存储管理和分段存储管理的地址映射的过程，这两种机制都不要求内存连续分配，理解这两种机制下程序装入，内存分配，地址映射的全过程。（4）有/无快表时页式地址的映射机制，快表命中率80%，90%的含义，看课堂上PPT上的习题。（5）P-V操作：同步问题：识别哪些是“关键操作”，“有条件执行的操作”，“影响其他操作的操作”，P-V操作添加的位置：关键操作之前还是之后；互斥问题：临界区/临界资源的访问（6）设备管理和文件管理二章：简答题会多些，主要是概念为主。

计算机通过硬件中断机制完成由用户态到核态的转换
程序设计中无法实现屏蔽中断
”访管“指令仅能在用户态下使用
广义指令即系统调用
trap指令负责由用户态转换成核态
内部中断类似整数除0，无法通过异常处理程序恢复，无法回到原来中断处
PC值由中断指令隐程序自动保存，通用寄存器由操作系统保存
区分核态与用户态是为了保护操作系统
用户通过内部中断进入内核态，
MBR大小是512B
段式系统共享比页式共享方便
在分区管理下，导致碎片的原因是作业连续存储
进程是资源分配的基本单位（不管有没有线程），没线程，进程是CPU调度的基本单位，有线程，线程是CPU调度的基本单位