操作系统原理笔记(一)

一、绪论

1.1 操作系统与计算机体系结构的关系

操作系统的地位
- 不解决具体问题，不负责生成解决应用问题的程序
- 所有硬件之上，所有软件之下，是各种软件的基础运行平台
计算机系统的体系结构
- 应用软件
- 编译器，数据库，网络等组件
- 操作系统
- 硬件
操作系统与各层之间的关系
- 操作系统对各层的管理和控制
  - 管理控制硬件：控制CPU的工作、访问存储器、设备驱动、中断处理
  - 管理控制应用软件：提供方便简单得用户接口
- 各层对OS的制约和影响
  - 下层硬件环境的制约：提供操作系统的运行环境、限制了操作系统的功能实现
  - 上层用户和软件的要求：操作系统需要满足不同的应用需求
操作系统的功能
- 进程管理
  - 进程控制：创建，暂停，唤醒，撤销；
  - 进程调度：调度策略，优先级；
  - 进程通信：进程间通信
- 内存管理
  - 内存分配
  - 内存共享
  - 内存保护
  - 虚拟内存
- 设备管理
  - 设备的分配和调度
  - 设备无关性
  - 设备传输控制
  - 设备驱动
- 文件管理
  - 存储空间管理
  - 文件的操作
  - 目录的操作
  - 文件和目录的存取权限管理

1.2 操作系统的形成与发展(★)

1.2.1 手工操作阶段

人工操作
作业独占计算机
作业串行执行

1.2.2 批处理阶段

联机批处理

作业的I/O操作由CPU来处理：慢速I/O设备严重浪费CPU处理时间

脱机批处理

作业的I/O操作由廉价的卫星机处理
主处理器只与高速存储设备交互
DMA的原型

单道批处理技术

批量：将多个程序打包形成作业队列
自动：常驻监督程序（可视为操作系统）依次自动处理队列中的每个作业
单道：作业只能按照顺序依次被执行，是串行的
利用效率低：当需要执行I/O操作时，CPU空闲，而不能被其他作业使用；当需要CPU工作时，外设空闲，而不能被其他作业使用

多道批处理技术

多道：内存中同时存放多道相互独立的程序，以脱机方式工作
提高CPU利用效率：当某道程序因某种原因（如进行I/O操作）不能继续运行下去时，操作系统便将另一道程序投入运行
宏观上并行：多个程序同时占用多个资源同时执行
微观上串行：在某个时间点，最多一个程序占用CPU；多个程序交替占用CPU
无法交互：平均周转时间长，无交互能力
辅助技术：中断、通道（DMA、达成脱机方式）

1.2.3 分时系统阶段

以联机方式使用计算机

分时技术

把处理机时间划分成很短的时间片（如几百毫秒）轮流地分配给各个应用程序使用
如果某个程序在分配的时间片用完之前计算还未完成，该程序就暂停执行，等待下一次获得时间片后再继续计算

实时技术

系统能及时响应外部事件的请求，在规定的时间（deadline）范围内完成对该事件的处理，并控制实时任务协调一致运行
- 强调可预测而非迅速
- 硬实时：若实时约束不被满足，则会导致灾难性后果
- 软实时：若实时约束不被满足，则会导致服务质量的降级

1.3 操作系统的定义与特征

定义
- 大型软件系统
- 负责计算机系统软、硬件资源的分配
- 控制和协调并发活动
- 提供用户接口，使用户获得良好的工作环境
特征
- 并发
  - 并行是指两个或者多个事件在同一时刻发生，而并发是指两个或多个事件在同一时间间隔发生
  - 并行是在不同实体上的多个事件，并发是在同一实体上的多个事件
- 共享：系统中的资源可供多个并发执行的进程共同使用
- 虚拟：把一个物理上的实体变为若干个逻辑上的对应物
- 不确定：为多个作业的执行顺序和每个作业的执行时间是不确定的

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

2.1 操作系统的物质基础(★)

2.1.1 CPU特权级

设立特权级的目的：保护操作系统
CPU的两种状态
- 管态（核态、特权态）
  - 操作系统的管理程序执行时机器所处的状态
  - 可使用全部指令（包括一组特权指令）
  - 可使用全部系统资源（包括整个存储区域）
- 用户态
  - 用户程序执行时机器所处的状态
  - 禁止使用特权指令，不能直接取用资源与改变机器状态
  - 只允许访问自己的存储区域
CPU特权指令
- I/O指令
- 停机halt指令
- 从核态转回用户态
- 改变状态寄存器（MSR）的指令
CPU特权级

2.1.2 中断技术

中断分类

	IRQ	Exception	Syscall
产生原因	CPU以外的外部设备产生的异步事件	当前程序的执行所导致的同步事件	当前执行的程序需调用操作系统的功能
处理时机	指令执行的间隙	发生异常的指令执行过程中	访管指令
返回地址	下一条指令	发生异常的指令	下一条指令
举例	敲击键盘、磁盘数据传输完成	除零、非法内存访问	ecall指令

中断响应

中断响应的过程
- 识别中断源
- 保护断点和现场：保存断点地址、程序状态字PSW
- 装入中断服务程序的入口地址
- 进入中断服务程序
- 恢复现场和断点
- 中断返回
中断响应的实质
- 交换CPU的态
- 交换指令执行地址

2.1.3 时钟

2.2 操作系统的组织结构

操作系统的组件
- 核心组件：中断管理、进程管理、内存管理
- 外围组件：文件管理、设备管理
操作系统的内核结构

	单内核	微内核	伴生内核
特点	所有组件均运行在内核态	核心组件运行在内核态，外围组件运行在用户态	同一台机器运行多个OS，包括主OS和伴生OS
优点	结构简单，执行效率高	内核小，稳定	伴生OS结构简单
缺点	内核庞大，难以维护	采用IPC通讯，效率低	完整系统结构复杂
例子	UNIX、Linux	Windows	PKE、Docker容器

IPC通讯：内核把用户请求服务的消息传给服务进程；服务进程接受并执行用户服务请求；内核用消息把结果返回给用户

2.3 程序的链接(★)

2.4 用户接口(★)

批处理操作系统：作业控制语言
分时操作系统、个人计算机操作系统：作业控制语言、键盘命令、图形用户界面
操作系统如何提供服务（系统调用）：
- 操作系统提供实现各种功能的例行子程序，每个功能对应一个功能号；
- CPU提供访管指令：svc n，其中svc表示访管指令的记忆符，n为功能号；
- 应用程序通过访管指令调用操作系统例程；
- 处理机执行到访管指令时发生中断，该中断称为访管中断。
系统调用与一般库函数的区别
- 系统调用代码驻留在内存中，属于操作系统，其执行回引起CPU状态由用户态转到核态，如getchar()函数
- 一般库函数由开发软件提供，不会引起CPU状态的变化，如max()函数
系统调用的实现
- 每个系统调用对应一个系统调用号；
- 每个系统调用对应一个执行程序段；
- 每个系统调用要求一定数量的输入参数和返回值

UNIX/Linux	Win32	Usage
fork	CreatProcess	创建进程
waitpid	WaitForSingleObject	等待进程终止
open/close	CreatFile/CloseHandle	创建或打开/关闭文件
read/write	ReadFile/WriteFile	读/写文件
lseek	SetFilePointer	移动文件指针
mkdir/rmdir	Creat/Remove Directory	建立/删除目录
stat	GetFileAttributesEx	获得文件属性

Linux的内核陷入指令为int 80h中断指令

三、进程管理

3.1 进程引入

顺序程序（单道系统）
- 程序的一次执行过程称为一次计算，它由许多简单的操作组成
- 一个计算的若干操作必须按照严格的先后次序顺序地执行，这个计算过程就是程序的顺序执行过程
- 特点
  - 顺序性：处理机的操作严格按照程序所规定的顺序依次执行
  - 封闭性：程序一旦开始执行，就不会受到外界因素的影响
  - 可再现性：程序执行的结果与它的执行速度无关 (即与时间无关)，而只与初始条件有关；初始条件相同，程序执行的结果一定相同
并发程序
- 若干个程序段同时在系统中运行，这些程序段的执行在时间上重叠
- 一个程序段的执行尚未结束，另一个程序段的执行已经开始，称这几个程序段是并发执行的
- 并发语句记号
  1
  2
  3
  cobegin
  S1,S2,S3,...,Sn
  coend
- 特点
  - 失去封闭性和可再现性：两个并发程序若干操作的先后顺序
    - 程序并发执行时的结果与各并发程序的相对速度有关
    - 即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误
  - 一个程序可以对应多个计算
  - 多个计算之间会有并发执行的相互制约
    - 直接制约：共享变量
    - 间接制约：资源共享

3.2 进程概念

3.2.1 进程定义

指一个具有一定独立功能的程序关于某个数据集合的一次运行活动，即程序的一次执行
进程与程序的区别
- 程序是静态的（存储在内存/外存中的代码），进程是动态的（程序在处理机运行的过程，是运行中的程序）；
- 进程是一个独立运行的活动单位，是竞争系统资源的基本单位；
- 一个程序可以对应多个进程，一个进程至少包含一个程序

3.2.2 进程状态(★)

三种基本状态
- 运行态：该进程已获得运行所必需的资源，它的程序正在处理机上执行；
- 等待态：进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行；
- 就绪态：进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行
进程的变迁原因
- 就绪->执行：进程调度即可就绪状态转为运行状态
- 等待->就绪：处于等待状态的进程中相关服务完成或者相关资源获得完成
- 运行->等待：进程提出某种服务请求，比如说I/O
- 运行->就绪：在分时系统中，时间片到，才会发生这种变迁
进程基本状态的拓展
- 拓展1：程序执行完了，进程还可以被回收；
- 拓展2：添加挂起操作，添加静止状态，静止表示当前进程不在主存里面，在虚存里面；
- Unix进程，运行态分成用户态运行和核心态运行

3.2.3 进程描述

进程的组成
- 进程内部的程序和数据：描述进程本身所应完成的功能
- 进程控制块PCB：描述进程与其他进程、系统资源的关系，以及进程所处的状态
进程控制块的内容
- 进程标志符：进程符号名或ID
- 进程当前状态
- 进程队列的指针next：处于同一状态的下一个进程的PCB地址
- 进程优先级
- CPU现场保护区
- 通信信息、家族联系、占有资源清单
Linux中的PCB结构称为task_struct，所有进程均以task_struct链表的形式存储在内存中
PCB队列的组织
- 就绪队列：所有处于就绪状态的队列
- 等待队列：有多个等待队列，每个队列表示所有因为同个某种原因而等待的进程
- 运行指针：当前是什么进程正在运行

3.3 进程控制原语(★)

3.3.1 进程创建

进程创建原语：create(name，priority)
- 其中name为标识符，priority是优先级
- 创建一个具有指定标识符的进程，建立进程的PCB结构
实现方法
- 查找PCB池，是否出现同名现象
- 向系统申请一个空闲PCB，没有空闲PCB则出错退出
- 将入口信息填入PCB
- PCB入就绪队列
- 返回进程PID
进程创建：Linux中的fork()
- 创建一个子进程，它从父进程继承整个进程的地址空间，包括：进程上下文、进程堆栈、内存信息、打开的文件描述符、信号控制设置、进程优先级、进程组号、当前工作目录、根目录、资源限制、控制终端等。
- 创建过程
  - 为新进程分配一个新的PCB结构；
  - 为子进程赋一个唯一的进程标识号 (PID)；
  - 为子进程复制一个父进程上下文的逻辑副本——父子进程将执行完全相同的代码；
  - 增加与该进程相关联的文件表和索引节点表的引用数——父进程打开的文
    件子进程可以继续使用；
  - 对父进程返回子进程的进程号，对子进程返回零
进程更换：Linux中的exec()
- 更换进程执行代码，更换正文段，数据段
- 格式：exec(文件名，参数表，环境变量表)
- 例如：execlp(“max”,15,18,10,0)；execvp(“max”,argp)

3.3.2 进程撤销

进程撤销原语：kill()，exit()
- 撤消当前运行的进程并转进程调度程序
实现方法
- 由运行指针获得当前进程pid
- 释放本进程占用的资源给父进程
- 从总链队列中删除该进程
- 释放PCB结构
- 转进程调度
进程撤销：Linux中的exit()
- 撤销一个进程，它停止当前进程的运行，清除其使用的内存空间，销毁其在内核中的各种数据结构；
- 进程状态变为zombie僵尸态：仍保留其PCB结构，等待父进程回收
- 若其父进程正在等待该进程的终止，则父进程可立即得到其返回的整数status
- 僵尸进程：若子进程调用exit()，而父进程并没有调用wait()或waitpid()获取子进程的状态信息，那么子进程的PCB仍然保存在系统中，此时该子进程称为僵尸进程；
- 孤儿进程：当一个父进程由于正常完成工作而退出或由于其他情况被终止，它的一个或多个子进程却还在运行，这些子进程将成为孤儿进程；
- 孤儿进程将被1号进程接管，且1号进程定期清除僵尸进程

3.3.3 进程等待

进程等待原语：susp(chan)
- 其中chan为进程等待的原因
- 中止调用susp的进程的执行，并将其加入到等待chan的等待队列中，转进程调度
实现方法
- 保护当前进程的CPU现场到其PCB结构中
- 设置该进程为等待态
- 将该进程的PCB结构插入到chan对应的等待队列中
- 转进程调度
进程等待：Linux中的wait()
- 父进程通过调用wait(int* status)函数使其暂停执行，直到它的一个子进程结束为止；
- 其返回值是终止运行的子进程的PID；
- 参数status所指向的变量存放子进程的退出码，即从子进程的main函数返回的值或子进程中exit()函数的参数
进程等待：Linux中的waitpid()
- 父进程通过调用wait(pid_t pid, int * status, int options)函数使其暂停执行，直到特定子进程结束为止

3.3.4 进程唤醒

wakeup(chan)
- 其中chan为被唤醒进程等待的原因
- 当进程等待的事件发生时，由发现者进程唤醒等待该事件的进程
实现方法
- 找到chan对应的等待队列
- 将该队列的首个进程移出等待队列
- 设置该进程为就绪态
- 将该进程插入到就绪队列
- 进程调度

3.4 进程的相互制约关系

临界资源：一次只允许一个进程使用的资源
- 硬件：输入机，打印机，磁带机
- 软件：公共变量，队列
当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完成后，另一个进程才能访问修改该变量
临界区：对于公共变量或公共存储区进行访问和修改的程序段
临界区访问规则
- 空闲则入：没有进程在临界区时，任何进程都可以进入临界区；
- 忙则等待：有进程在临界区时，其他进程均不能进入临界区；
- 有限等待：等待进入临界区的进程不能无限等待；
- 让权等待：不能进入临界区的进程应释放CPU
进程互斥
- 当某一进程正在访问某一存储区时，不允许其他进程访问或者修改该存储区的内容，这种制约关系称为进程互斥
- 同一临界资源的临界区才需要互斥进入
进程同步
- 并发进程在一些关键点上可能需要互相等待与互通消息，这种制约关系称为进程同步
- 在病人看病过程中，看病活动需要等待化验活动作出的化验结果，而化验活动需要等待来自看病活动的化验请求
同步反映的是合作关系；互斥反映的是竞争关系

3.5 进程同步机构(★)

3.5.1 锁

用一个变量w代表某种资源的状态：w=1表示资源被占用，否则表示资源没有被占用
上锁原语：lock(w)
- 执行到lock的时候判断w是多少
- 如果w=1，就被阻塞，进程无法往下继续运行，直到什么时候w=0
- 如果w=0，不会被阻塞，进程可以继续执行，并且会把w赋值为1
开锁原语：unlock(w)
- 执行到unlock的时候，把w赋值为0即可

3.5.2 信号灯

信号灯是一个确定的二元组(s,q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。
- 变量值s≥0时，表示绿灯，进程执行；
- 变量值s＜0 时，表示红灯，进程停止执行；
- 创建信号灯时应说明信号灯的意义和s的初值，且初值绝不能为负值
P操作
- 把信号灯变量s的值减一
- 操作后，如果s为负，调用P操作的进程阻塞，并插入到信号灯变量s对应的等待队列中，否则继续运行
V操作
- 把信号灯变量s的值加一
- 操作后，如果s非正，则从信号灯变量s对应的等待队列中取出一个进程放入就绪队列，否则继续运行

3.5.3 进程互斥的实现

对于每一个锁，进入临界区之前上锁，离开临界区的时候解锁
每个临界区都有有一个临界信号灯管理，进入临界区就P(s)，离开临界区就V(s)
基本原则
- 信号灯的初值为非负整数
- 除初始化外，只能使用P、V原语对信号灯进行操作
- P、V操作一定成对出现
  
  遗漏P操作则不能保证互斥访问，遗漏V操作则不能在使用临界资源之后将其释放（给其他等待的进程）

3.5.4 进程同步问题

进程流图
- 表示进程之间执行的先后次序，某些进程的完成代表某些进程可以开始执行的顺序
- 可以用多个信号灯表示，在每个进程前面加上若干个P操作，在每个进程后面加上若干个V操作
- 其中V操作用于通知其他进程本进程已经执行完毕（相当于消息发送者）
- P操作用于接受上一层V操作发送来的消息
- 假如说有一个关系p1->p2，p1执行完了才能执行p2，那么就有一个信号灯，初值为0，在p2的开始加上P操作，p1的末尾加上V操作，有多少对这样的关系就有多少个信号灯
共享缓冲区
- 问题概述：一个读进程，一个写进程，一个缓冲区
- 转化成进程流图：只有读完了，才能写，只能写完了，才能读
- 信号灯
  - sb代表缓冲区的空位置数，初值为1
  - sa代表缓冲区的数据数，初值为0
- 写进程
  - p（sb）
  - 数据放入buf
  - v（sa）
- 读进程
  - p（sa）
  - 取数据
  - v（sb）
生产者消费者
- 问题概述
  - 若干个生产者和若干个消费者共享一个可同时容纳多个产品的缓冲区
  - 生产者不断生产产品放入缓冲区，消费者不断从缓冲区取出产品并消耗
  - 任何时刻最多只能有一个生产者或消费者访问缓冲区
  - 禁止生产者向满缓冲区放入产品
  - 禁止消费者从空缓冲区取出产品
- 缓冲区有界
  - 同步问题分析
    - 互斥访问缓冲区
    - 由于缓冲区无界，生产者可以一直生产产品
    - 消费者需要根据满缓冲区的数量决定是否消费
  - 信号灯
    - 同步信号灯nfull：表示满缓冲区的数量，初值为0
    - 互斥信号灯mutex：表示缓冲区是否被占用，初值为1
- 缓冲区无界
  - 同步问题分析
    - 互斥访问缓冲区
    - 生产者需要根据空缓冲区的数量决定是否生产
    - 消费者需要根据满缓冲区的数量决定是否消费
  - 信号灯
    - 同步信号灯nfull：表示满缓冲区的数量，初值为0
    - 同步信号灯nempty：表示空缓冲区的数量，初值为n
    - 互斥信号灯mutex：表示缓冲区是否被占用，初值为1

3.6 线程

进程模型
- 进程是资源占用的基本单位：进程拥有主存、设备、文件等系统资源的使用权
- 进程是调度执行的基本单位：操作系统以进程为单位进行处理机的调度
- 不足：进程创建、切换、通信开销大
多线程模型
- 在进程内增加一类实体——线程作为调度的基本单位
- 同一进程内的线程共享相同的地址空间
- 对于共享的数据，线程使用的同步机制与进程一样
- 不足：一个线程崩溃，会导致其所属进程内的所有线程崩溃
多核处理器
- 设$f$为程序中能够并行的部分的运行时间在整个程序运行时间中的占比
- 加速比=在单处理器上执行程序的时间/在N个处理器上执行程序的时间=$\frac{1}{(1-f)+\frac{f}{N}}$
两种线程模型
Linux中的线程
- 线程创建：pthread_create(pthread_t *thread,pthread_attr_t *attr,void *(*start_routine)(void *),void *arg)
  - 其中thread为指向创建的线程标识符的指针；attr设置线程属性；start_routine为线程运行函数地址；arg为运行函数的参数
- 线程等待： pthread_join(pthread_t thread,void **thread_return)
  - 其中thread为被等待的线程标识符；thread_return为一个用户定义的指针，用来存储被等待线程的返回值
  - 调用该函数的线程将一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回

一、绪论

1.1 操作系统与计算机体系结构的关系

1.2 操作系统的形成与发展(★)

1.2.1 手工操作阶段

1.2.2 批处理阶段

联机批处理

脱机批处理

单道批处理技术

多道批处理技术

1.2.3 分时系统阶段

分时技术

实时技术

1.3 操作系统的定义与特征

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

2.1 操作系统的物质基础(★)

2.1.1 CPU特权级

2.1.2 中断技术

相关概念

中断分类

中断响应

2.1.3 时钟

2.2 操作系统的组织结构

2.3 程序的链接(★)

2.4 用户接口(★)

三、进程管理

3.1 进程引入

3.2 进程概念

3.2.1 进程定义

3.2.2 进程状态(★)

3.2.3 进程描述

3.3 进程控制原语(★)

3.3.1 进程创建

3.3.2 进程撤销

3.3.3 进程等待

3.3.4 进程唤醒

3.4 进程的相互制约关系

3.5 进程同步机构(★)

3.5.1 锁

3.5.2 信号灯

3.5.3 进程互斥的实现

3.5.4 进程同步问题

3.6 线程

主题设置

实验特性

播放设置

切换歌单

自定义歌单

默认背景

图片（PC端）

图片（移动端）

渐变色

纯色