个人用操作系统重点（待补充）

一、操作系统基本概念

操作系统（系统软件）

控制和管理整个计算机的硬件与软件资源**（系统资源管理者，安全、高效）**
提供给用户和其他软件方便的接口与环境 （向上层提供方便易用的服务），用户无需关心底层实现原理，只需向操作系统发出命令即可。
一个程序需要被放到内存中才能被CPU处理（内存是CPU唯一可直接接触的区域。

操作系统功能

处理器管理
存储器管理
文件管理
设备管理

操作系统提供服务

用户直接使用：

1. GUI（图形化用户接口）
2. 联机命令接口/交互式命令接口(用户说一个，系统做一个)
   如:cmd
3. 脱机命令接口/批处理命令接口（用户说一堆，系统做一堆）
   如：运行.bat文件

用户不能直接使用：
4. 程序接口：用户无法直接调用，可以用过程序代码进行系统调用的方式来间接使用。

操作系统目标

实现对硬件机器的扩展（没有操作系统的只能叫裸机）

操作系统特征

并发：多个事情在同一时间间隔内发生。（宏观上同时发生，微观上交替发生）
并行：多个事情在同一时刻发生。
单核CPU只能并行一个程序，各个程序只能并发。
X核CPU表示可以并行执行X个程序。

互斥共享：一个时间段只允许一个进程访问。
同时共享：一个时间段多个进程并发使用。

并发性与共享性互为存在条件

虚拟：将物理上的实体（实际存在）变为若干逻辑上的对应物（用户感受到的）。
空分复用（虚拟存储技术）
时分复用（并发，虚拟存储器）

没有并发性就没有虚拟性

异步：在多个程序并发运行时，由于资源有限，进程执行并非一贯到底，而是阻塞（等待系统资源被分配）后继续运行，以不可预知的速度前进。

只有系统拥有并发性才有可能拥有异步性

操作系统历史

一：手工操作阶段（将操作写在纸带机上后（长时间），让机器运行（短时间），再用纸带机输出（长时间））
用户独占全机，人机速度矛盾，资源利用率低
二：批处理阶段

1. 单道批处理（多个程序员将纸带用外围机存到磁带里，计算机读取磁带，用监督程序来控制输入输出）
   内存同时只能有一个程序，CPU大量的时间在空闲等待I/O完成
2. 多道批处理（CPU计算时内存再读入，利用率提升）
   无法优先处理紧急任务，每个任务优先级相同。

三：实时操作系统（能优先响应紧急任务而无需排队）
硬实时系统：严格的在规定时间内完成处理
软实时系统：能偶尔接受违反时间规定
四： 络操作系统：实现各类资源共享与各种计算机之间的通信。
五：分布式操作系统：分布性、并行性，多台计算机协同完成。
六：个人计算机操作系统：eg:Windows XP等。

操作系统运行机制

指令：（二进制机器指令）：CPU能处理、识别的最基本的指令。
代码编译为机器指令（二进制）后由CPU执行。
内核程序：实现操作系统

CPU指令：

1. 特权指令（1，内核才能调用，内核态/核心态/管态）
2. 非特权指令（0，用户态/目态）

程序状态字寄存器存储CPU状态
改变CPU状态的指令是特权指令！
当CPU处于用户态出现非法指令时会产生中断。
CPU检测到中断后会变为核心态，停止当前运行的应用程序，并拒绝执行特权指令。然后执行处理中断的内核程序。
中断是操作系统夺回CPU使用权的唯一途径！

中断分类

1. 内中断（异常，与当前指令有关，源于CPU内部）
   故障（可能被内核程序修复）
   陷入指令/访管指令（应用程序请求系统调用，不是特权指令！）
   终止（致命错误无法修复）
2. 外中断（中断，与当前指令无关，源于CPU外部）
   时钟中断（定时器）
   I/O中断请求（输入输出结束）

中断原理

根据中断信 不同，在中断向量表中来找到对应进程在内存的位置

系统调用（获得内核提供的服务）

与库函数的区别：系统调用是更为底层的东西，部分库函数需要系统调用
（如创建新文件）
凡是和**共享资源有关（存储分配，I/O操作，文件管理）**的操作都需要系统调用，防止用户非法操作，增加稳定性与安全性。
   设备管理
   文件管理
   进程控制
   进程通信
   内存管理
调用过程：
传参指令（调用参数）->陷入指令（用户态）->处理相关（核心态）->返回应用程序

大内核（操作系统最核心的部分）

1. 时钟管理（实现计时功能）
2. 中断处理（实现终端）
3. 原语（具有原子性，最底层部分，运行时间短，调用频繁，执行时不可被中断）
4. 对系统资源进行管理（进程、存储器、设备）
   1~3属于微内核
   微内核需要频繁被切换，消耗大

二、进程管理

进程概念

程序是静态的可执行文件
进程是动态的，程序的一次执行过程（系统进行资源分配调度的独立单位，每个进程内部内存空间独立）
进程在内存被创建时会分配一个唯一的PID，CPU再根据进程中的指令执行。
系统会记录进程被分配了哪些资源与运行情况，存入进程控制块（PCB）中

PCB是进程存在的唯一标志！

1. PCB
2. 程序段（程序代码）
3. 数据段（程序变量）

进程特征

1. 动态性（基本特征）：动态产生、变化、消亡
2. 并发性：内存中有多个进程实体并发运行
3. 独立性：独立运行、获得资源、调度的基本单位
4. 异步性：各进程异步执行，操作系统提供“进程同步机制”,但并发会导致结果的不确定性
5. 结构性：每个进程都有PCB

进程状态转换（用原语完成，否则会导致关键数据信息不统一）

两个进程对共享空间的存储必须是互斥的（不能互相影响，通过系统内部工具实现，操作系统只提供共享空间与同步互斥工具）
基于数据结构的共享（低级通信方式，速度慢限制多）
基于存储区的共享

管道存储（内存中开辟的大小固定的缓冲区）

进程调度的时机

1.当前进程主动放弃处理机（部分系统只允许程序主动放弃处理机）
如正常终止、异常终止、主动阻塞（如等待I/O）
2. 当前进程被动放弃处理机
如时间片用完、优先级更高的进程进入就绪队列、更紧急的时间需要处理（如I/O中断）
在处理中断、进程在内核临界区、执行原语时不可调度！
注意！内核程序临界区和临界区是有区别的！
进程在普通临界区中是可以进行调度、切换的。
前者：访问某种内核数据结构（如进程的就绪队列）
后者：访问临界资源（一个时间段只允许一个进程访问的，各进程需要互斥地访问）的代码

进程调度方式

非抢占式（只允许主动放弃处理机）

实现简单，开销小但无法及时处理紧急任务，适合早期批处理系统

抢占式（处理机会被分配给更重要紧急的进程）

调度算法（用于作业/进程）

调度算法评价指标

CPU利用率：忙碌时间/总时间
系统吞吐量：完成作业数量/花费时间
周转时间：从作业被提交开始，到被完成为止的时间
平均周转时间：所有作业周转时间之和/作业数
带权周转时间：作业周转时间/实际运行的时间（必然≥1，时间越小满意度越高）
平均带权周转时间：所有带权周转时间/作业数
等待时间：作业处于等待被服务状态的时间之和
（I/O完成的时间不算在内，但要考虑作业在外存后背队列的时间）
响应时间：用户提交请求到首次响应的时间

先来先服务（FCFS，非抢占，不会导致饥饿）

根据作业到达的先后顺序进行服务
优点：公平、实现简单
缺点：带权周转时间很大，对长作业有利，短作业不利

时间片轮转（RR，只用于进程调度，抢占式，常用与分时操作系统，不会饥饿）

每隔一段时间，轮流地为各个进程服务，强制获取控制权，利用时钟中断实现
如果时间片太大，会退化成FCFS，因此时间片不能太大。
如果时间片太小，进程切换过于频繁，开销大，因此时间片不能太小。
时间片要让切换进程的开销占比不超过1%

把已经到达的进程放入就绪队列、每次转移控制权时将前一个进程置于队尾
优点：公平、响应快、适用于分时系统
缺点：进程切换有开销、不区分任务的紧急程度。

进程同步

由于进程本身有异步性，同步即是制约多个进程的工作次序。

进程互斥

进程互斥：一个时间段里只能允许一个进程访问临界资源
临界区是访问临界资源的代码段
进入区与退出区是负责实现互斥的代码段
如果没有互斥，部分进程的内容会混淆在一起

互斥实现方法

单标志法（将进入临界区的权限只能由前一个进程赋予后一个）

用一个变量来表示当前允许进入临界区的进程
但有可能出现允许进入的编程却不进入的现象

双标志先检查（设置数组表示该进程是否想要进入临界区，先“检查”后“上手”）

每个人进程在进入临界区之前先检查其他进程是否需要进入临界区，如果无，则将自己设为true，之后开始访问
如果进程并发，可能会出现多个进程想同时使用临界区。
“检查”与“上锁”不是一气呵成的

双标志后检查（先“上锁”后“检查”，但可能产生饥饿现象）

PeterSon算法（结合双标志、单标志的，会产生忙等现象，不会产生饥饿）

如果多个进程想进入，优先让对方用，在彼此都“谦让”后（只会“谦让”一次），由第一个先“谦让”的进程再开始调度

硬件实现进程互斥

中断屏蔽（期间不可被中断）

简单高效，但不适用于多处理机，只适用于操作系统内核进程

TestAndSet（TS/TSL指令）

实现简单，但会产生“忙等”
old记录是否已被上锁，
再将lock设为True。
检查临界区是否已被上锁

Swap指令（Exchange/XCHG指令）

信 量（实现进程互斥、进程同步，用原语实现）

信 量表示系统中某种资源的数量（用变量实现）
wait(S) P操作 进入区、申请资源，S–
signal(S) V操作 退出区、释放资源，S++

整型信 量（存在“忙等”）

拥有三种操作：初始化、P操作、V操作
“检查”与“上锁”一气呵成，避免并发、异步导致的问题
但会发生 “忙等”

信 量实现进程互斥（互斥信 量mutex）

设置互斥信 量mutex，初值为1，表示进入临界区的名额
不同资源需要不同信 量
在进入区P(mutex)来申请资源
在退出去V(mutex)来释放资源

信 量实现进程同步（实现“一前一后”，同步信 量S）

设置同步信 量S，初始为0
在前操作后执行V操作
在后操作前执行P操作

生产者消费者问题（互斥&同步、两对同步关系）

管程（更方便地实现互斥与同步，封装）

管程组成

1. 局部于管程的共享数据结构说明：
2. 对该数据结构进行操作的函数/过程
3. 对共享数据设置初始化的语句
4. 管程有一个名字

管程基本特征

1. 局部于管程的数据只能被该管程访问
2. 一个进程只有通过调用管程内的函数才能进入管程访问共享数据
3. 每次只允许一个进程在管程内执行（管程每次只开放一个函数，且只有一个进程/线程可以进入，由编译器实现）
4. 可以在管程中设置条件变量与等待/唤醒操作来解决同步问题

死锁的检测与解除（允许死锁发生）

死锁检测（依次消除与不阻塞进程相连的边直到无边可消）

一：使用某种数据机构保存资源请求与分配信息
二：提供算法利用上述信息来检测是否进入死锁
将进程与资源试做节点，请求和分配看作边，可以建成资源分配图
找到既不阻塞又不是孤点的进程Pi （至少有一条边与其相连，且资源请求数量小于已有空闲资源数量），消去其所有请求边与资源分配边，使之成为孤点。
如果所有的边都能消除，这该图是可完全简化的，不会发生死锁，若不能消除，则该进程进入死锁
（出现死锁时，并非所有进程都是死锁状态）

死锁解除

资源剥夺：挂起（暂时放到外存）死锁进程并抢占其资源，分配给其他死锁进程（要保证被挂起的进程不会饥饿）
撤销/终止进程：强制撤销部分，甚至全部死锁进程，并剥夺其资源，实现简单，代价很大。
进程回退：让死锁进程回退到避免死锁的状态
死锁进程选择：

1. 优先级
2. 已执行时间
3. 完成还需要的时间
4. 是交互式还是批处理式