操作系统概述

操作系统是管理计算机硬件的软件。
计算机系统由以下4个部分组成：

硬件：为计算机提供基本的计算资源，如CPU、内存、I/O设备等；
操作系统：控制硬件，并协调各个用户应用程序的硬件使用
应用程序：确定了用户为解决计算问题而使用这些资源的方式；
用户

I/O结构：

同步I/O：I/O 启动后，在 I/O 完成之前，控制权不会返回给用户程序。
异步I/O：I/O 启动后，控制权将返回给用户程序，而无需等待 I/O 完成
DMA（直接内存访问）：设备控制器将数据块从缓冲区存储直接传输到主内存，无需 CPU 干预；每个块只生成一个中断，而不是每个字节生成一个中断

操作系统特征

并发：并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。
共享：互斥共享和同步共享。
虚拟：虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术
异步：进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

操作系统的分类

图形用户界面（GUI）操作系统
特点：提供图形化的用户界面，易于使用，适合普通用户。
命令行界面（CLI）操作系统
特点：通过命令行输入命令，适合高级用户和系统管理员。
单内核（Monolithic Kernel）
特点：所有操作系统服务都运行在同一个内核空间，效率高，但可扩展性差。
微内核（Microkernel）
特点：核心服务运行在用户空间，内核只提供最基本的服务，可扩展性强，但效率较低。
混合内核（Hybrid Kernel）
特点：结合了单内核和微内核的优点，部分服务运行在内核空间，部分运行在用户空间。

几种操作系统：

实时操作系统
分布式操作系统：分布式系统是物理上独立的、可能是异构的、通过网络相连的一组计算机系统。网络是两个或多个系统之间的通信路径

内核态和用户态

内核态能使用更高级的指令
内核态到用户态是操作系统主动让出CPU使用权
用户态到内核态是中断引起的

中断与异常

中断：是操作系统和硬件交互的关键部分，硬件可以通过系统总线随时发送信号到CPU触发中断，当CPU被中断时，它停止正在做的事情，并立即转到固定位置执行中断处理程序，中断处理程序是操作系统的一部分，它负责处理中断，并恢复CPU到中断前的状态
中断分为内中断(异常)和外中断。
异常：陷阱、陷入；故障；终止
外中断：时钟中断；I/O中断请求

系统调用

系统调用是用户程序与操作系统内核之间的一种通信机制。当用户程序需要操作系统提供的服务时（如文件操作、进程控制等），它会通过系统调用向操作系统内核发出请求。
系统调用的类型：

进程控制：
- 创建和终止进程
- 加载、执行
- 获取进程属性，设置进程属性
- 等待事件，信号事件
- 分配和释放内存
文件管理
- 创建文件，删除文件
- 打开、关闭文件
- 读、写、重定位
- 获取文件属性，设置文件属性
设备管理
- 请求设备，释放设备
- 读、写、重定位
- 获取设备属性，设置设备属性
- 逻辑增加或移除设备
信息维护
- 获取时间和日期，设置时间和日期
- 获取系统数据，设置系统数据
- 获取进程、文件或设备属性
- 设置进程、文件或设备属性
通信
- 创建、删除通信连接
- 发送、接收消息
- 传输状态信息
- 增加或移除远程设备
保护
- 获取文件权限
- 设置文件权限

进程

程序：是静态的，就是个存放在磁盘里的可执行文件，一系列的指令集合。
进程：是动态的，是程序的一次执行过程。
特点：

独立性：每个进程都有自己的独立地址空间和资源。
并发性：多个进程可以同时运行，操作系统通过时间片轮转等方式调度进程。
隔离性：进程之间的地址空间是隔离的，一个进程的崩溃不会影响其他进程。
优点：
资源隔离：进程之间的资源隔离可以防止一个进程的错误影响其他进程。
稳定性：进程的隔离性提高了系统的稳定性。
缺点：
上下文切换开销大：进程之间的上下文切换需要保存和恢复整个进程的状态，开销较大。
通信复杂：进程之间的通信需要通过进程间通信（IPC）机制，如管道、消息队列、共享内存等，通信开销较大。

线程

线程是进程中的一个执行单元，是操作系统调度的基本单位。一个进程可以包含多个线程，这些线程共享进程的资源，但每个线程有自己的执行栈和程序计数器。
特点：

轻量级：线程是轻量级的，创建和切换线程的开销较小。(同一进程下线程切换比进程小，从一个进程的线程切换到另一个进程的线程就不一样了)
并发性：多个线程可以并发执行，共享进程的资源。
共享性：线程共享进程的地址空间和资源，线程之间的通信开销较小。
一对一模型
在一对一模型中，每个用户级线程直接映射到一个内核级线程。这意味着每个用户级线程都有一个对应的内核级线程。这种模型的优点是线程的调度由操作系统内核直接管理，可以充分利用多核处理器的并行性
一对多模型
在一对多模型中，多个用户级线程映射到一个内核级线程。这意味着多个用户级线程共享一个内核级线程。这种模型的优点是线程的创建和切换开销较小，适合需要大量线程的应用。
多对多模型
混合模型结合了一对一和一对多模型的优点。在这种模型中，多个用户级线程映射到多个内核级线程。这种模型既保留了用户级线程的高效性，又利用了内核级线程的并行性。

调度算法

FCFS先到先服务调度

算法思想：先到达的进程先服务
非抢占式
公平、实现简单
等待时间长，对长作业有利，对短作业不利
SJF最短作业优先调度
算法思想：短进程优先
非抢占式或抢占式
等待时间短
会长进程饥饿
RR时间片轮转调度
轮流让就绪队列的进程依次执行一个时间片，时间片时间应大于80%进程时间
抢占式
公平，响应快，适用于分时操作系统
高频率的进程切换会有一定开销
优先级调度
优先级高的先运行
非抢占式或抢占式
用优先级区分任务的重要程度，适用于实时操作系统
可能会饥饿
多级反馈队列调度
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大，新进程到达时先进入第1级队列，按FCFS原则等待时间片，若用完进程没结束，进入下一级队列队尾，只有第k级队列为空时才会为k+1级队头的进程分配时间片
抢占式
对各类型进程相对公平，每个新到达的进程都可以很快得到响应，不必估计进程的运行时间
一般不说缺点，可能饥饿

进程同步

do{
    entry section;//进入区
    critical section;//临界区
    exit section;//退出区
    remainder section;//剩余区
}while(true)

当一个进程在临界区时，其他进程不允许在它们的临界区内执行
临界区问题解决方案应满足的要求

互斥
进步，有空让进
有限等待，发出请求后等待时间有限
Peterson解决方案

P_i进程

flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = false;
remainder section;

P_j进程

flag[j] = true;
turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = false;
remainder section;

缺点：只能在2个进程时使用
硬件指令

中断屏蔽方法
开关中断
TestAndSet指令

bool TestAndSet(bool *lock){
  bool old;
  old = *lock;
  *lock = true;
  return old;
}
while(TestAndSet(&lock));
critical section;
lock = false;
remainder section;

CAS指令

Swap(bool *a, bool *b){
  bool temp;
  temp = *a;
  *a = *b;
  *b = temp;
}
bool old = true;
while(old == true)
  Swap(&lock, &old);
critical section;
lock = flase;
remainder section;

互斥锁

acquire(){
  while(!available);
  available = false;
}
release(){
  available = true;
}

主要缺点：忙等待
信号量

wait(S)，P(S)

void wait(int S){
    while(S<=0);
    S = S - 1;
}

- signal(S)，V(S)
void signal(int S){
    S = S + 1;
}

缺点：可能产生死锁

管程

类似一个类，基本特征如下：

局部于管程的数据只能被局部于管程的过程访问
一个进程只能通过调用管程中的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程


monitor ProducerConsumer
  condition full, empty;
  int count = 0;
  void insert(Item item){
    if(count == N){
      wait(full);
    }
    count++;
    insert_item(item);
    if(count == 1){
      signal(empty);
    }
  }
  Item remove(){
    if(count == 0){
      wait(empty);
    }
    count--;
    if(count == N - 1){
      signal(full);
    }
    return remove_item();
  }


producer(){
  while(1){
    item = product;
    ProducerConsumer.insert(item);
  }
}


consumer(){
  while(1){
    item = ProducerConsumer.remove();
    consume_item();
  }
}

死锁

死锁的四个基本条件：

互斥条件
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
请求和保持条件
循环等待条件

死锁的处理

预防死锁

破坏互斥条件：
将只能互斥使用的资源改造为允许共享使用，则系统不会陷入死锁。
缺点：并不是所有资源都可以改造成可共享的资源。
破坏不剥夺条件：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，等之后重新申请。
方案二：当某个进程需要的资源被其他进程所占有时，可以由操作系统协助将想要的资源强行剥夺。(这种方法一般考虑各进程的优先级)
缺点：
- 实现复杂。
- 释放已获得资源可能造成前一阶段工作的失效，只适用易保存和恢复的资源。
- 反复申请和释放增加系统开销，减低系统吞吐量。
- 采用方案一，只要暂时得不到某个资源，之前的资源就会放弃，重新申请。如果已知发生就会导致进程饥饿。
破坏请求和保持条件：
采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源。
缺点：有些资源可能只需要很短时间，因此如果整个运行期间都一直保持着所有资源，就会导致严重浪费，资源利用率极低。还有可能导致某些进程饥饿。
破坏循环等待条件
采用顺序资源分配法，先给系统中的资源编号，每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。
缺点：
- 不方便增加新的设备，需要重新编号。
- 进程实际使用资源的顺序可能和编号递增顺序不一致。
- 必须按规定次序申请资源，用户编程麻烦。

避免死锁

处于安全状态一定不死锁，处于非安全状态，不一定死锁。
银行家算法：
1 if $request_i$ ≤ $need_i$ go to step 2
2 if $request_i$ ≤ available go to step 3
3 available = available - $request_i$
4 $allocation_i$ = $allocation_i$ + $request_i$
5 $need_i$ = $need_i$ - $request_i$
6 调用安全算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。

死锁检测和解除

检测有无死锁，有就立即解除。
检测死锁的算法：找出既不阻塞又不是孤点的进程，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。消去它所有的请求边和分配边，使之成为孤点，若能消去所有边就没有死锁。
解除死锁的方法有：

资源剥夺法：挂起(暂时放到外存上)某些死锁进程，并抢占它的资源。
撤销进程法：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。
进程回退法：让一个或多个死锁进程回退到避免死锁的地步。

内存管理

物理地址：是内存单元的实际位置
逻辑地址：程序在运行时使用的代码，也叫虚拟地址

覆盖技术
将内存分为固定区和覆盖区，将程序分为多个模块，经常使用的放在固定区，不经常使用的部分当需要使用的时候再放到覆盖区中

必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加用户编程负担。已成为历史。

交换技术

设计思想：内存紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

内存空间的分配

连续分配管理方式

连续分配：用户进程分配的必须是一个连续的内存空间

单一连续分配

将内存分为系统区和用户区。系统区用于存放操作系统，用户区用于存放用户进程相关数据。但内存只能有一道用户程序。
优点：实现简单；无外部碎片；不一定需要采取内存保护。
缺点：只能用于单用户、单任务的操作系统；有内部碎片；存储器利用率低。

固定分区分配

将整个用户区分为若干个固定大小的分区。
分区大小相等：缺乏灵活性，但很适用于用一台计算机控制多个相同对象的场合
分区大小不等：增加了灵活性。
操作系统需要建立一个数据结构————分区说明表，来实现各个分区的分配和回收。

优点：实现简单；无外部碎片
缺点：当用户程序过大，所有分区都不能符合要求，就不得不采用覆盖技术，但这会降低性能；会产生内部碎片，内存利用率低。

动态分区分配

在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。
用空闲分区表或空闲分区链来记录内存的使用情况。
动态分区分配算法
首次适应算法：每次从低地址开始查找，找到第一个能满足大小的空闲分区。
空闲分区按地址递增次序连接。
最佳适应算法：优先使用更小的空闲区。
空闲分区按容量递增次序连接。
最坏适应算法：优先使用最大的连续空闲区。
空闲分区按容量递减次序连接。
邻近适应算法：从上次查找结束的位置开始检索。
空闲分区以地址递增的顺序排列(可排成一个循环链表)。

非连续分配管理方式

分页存储

将内存分为一个个大小相等的分区，每个分区就是一帧/块；将进程的逻辑地址空间也分为与帧大小相等的一个个部分，每个部分就是一个页。
一个进程对应一张页表；进程的每个页对应一个页表项，每个页表项由页号和块号组成；页表记录进程页和实际存放的内存块之间的映射关系。
将逻辑地址拆分为页号和页内偏移量，就可以通过页号查询页表得到起始位置，再通过偏移量知道实际地址。
地址计算
设页面大小为L。

计算页号P和页内偏移量W，(十进制就得算：P=A/L，W=A%L；二进制可以得到P和W)
比较P和页表长度M，P ≥ M，则产生越界中断，否则继续执行。
P * L + W即为实际地址(设从0开始)

TLB(联想寄存器)
TLB是用来存放最近访问的页表项的副本的，也叫快表。
访问逻辑地址时，TLB有就直接访问，没有命中就按之前的方法访问物理地址，并将其存入快表中。

两级页表

单级页表的问题：

页表必须；连续存放，因此当页表很大时，需要哦占用很多个连续的页框
没必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问几个特定的页面

按地址结构将逻辑地址拆分为三部分：一级页表，二级页表，页内偏移量，解决问题一
需要内存时才把页面调入内存，在页表项中添加一个标志位，用于表示是否已经调入内存，解决问题二

分段存储

将逻辑地址分为段号和段内地址。需要为每个进程建立一张段映射表，简称段表。段表有段号(隐含的，不占存储空间)、段长、基址。
段长长度=段内块号长度。
段内地址不能大于等于段长。