跳转至

操作系统

学习资源

OSTEP

【操作系统原理(合集)】

【【一周目导读】操作系统导论】

【操作系统 专题二 进程同步 PV操作】

前言

好难，不想听课，都快学期中了基本没学什么东西，现在是20260412 21:40，如果说我的操作系统在这学期能学到点什么的话，那就是从这一刻开始的。

这里大概是看科普小视频的简单认识

概论

对比了一下学校的操作系统课件和OSTEP的目录，大致了解了一下他们的学习路径

学校里：

1概述 2硬件环境 3操作系统结构 4进程基础 5线程 6CPU调度 8死锁 9内存管理系统 10虚拟内存 11文件系统 12设备管理 13磁盘结构

  • 先讲概述、结构 计算机体系与中断
  • 然后讲 CPU 怎么分给进程（进程、线程、调度） 进程与线程
  • 然后讲进程之间怎么打架、协作（同步、死锁） 并发与同步
  • 然后讲内存怎么管 这点和上面的联系有点不清楚 内存管理
  • 最后讲外设和文件系统

OSTEP：

  • Virtualization虚拟化
  • Concurrency并发
  • Persistence持久化

顺序差异：

OSTEP认为内存管理（分页、地址转换）本质上也是一种虚拟化，所以和进程调度一起讲完，这样当讲到并发是，已经完全理解什么是共享地址空间

学校则是先讲进程怎么跑，再讲跑起来这么协作、再看跑这些东西要占多少地方

Tip

建议学同步是去看OSTEP的Concurrency，会讲P/V原语背后最直观的代码实现逻辑

1. 计算机体系与中断

可能之后复习的时候再来填

2.进程与并发控制

进程与线程的基础

进程与线程的区别

进程(Process)是可执行程序(Program)的一个实例，已经重复了很多次了

每个进程被分了一块虚拟内存，每个进程都以为自己独占了整个内存

每个进程至少会有程序计数器，如果有多个线程，则会有多个程序计数器

线程间则会共享[地址空间、全局变量、打开的文件]

为什么要有线程

线程就是进程中更轻量级的进程

一个进程中可能会有多个事需要并行执行，他们需要修改访问同一个文档（即是在同一个进程中的）

“线程是并行的最小单位”

所以单核CPU要想执行多个线程，就要在他们之间轮转

这时对于线程来说，存在3种状态：

  • 就绪：等待 CPU 时
  • 运行：一旦 CPU 过来执行，就转变成运行状态；CPU 去执行其他线程，就转变会就绪状态
  • 阻塞：例如程序向硬盘发送访问请求，开始等待，这时 CPU 进入空转，线程就变成阻塞状态，等到等待收到回复，就变回就绪状态

CPU 会在内存中为每个线程提供各自的虚拟的CPU，每个线程认为自己是一直独占着CPU

进程间通信——互斥

计算机要执行的程序，需要从硬盘中读取到内存中，形成一个个进程，每个进程就是一个独立的资源单位，内部有独立的虚拟地址空间

Question

进程间如何访问通信？

Example

进程A 进程B都要打印文件，有一个负责打印的守护进程，有一个共享的打印目录

会发生访问冲突

两个进程中的部分代码同时读写共享的全局变量时，就会因为竞争产生问题，这部分代码就叫临界区

解决办法是读写互斥，如何实现？

A: 加个锁？

也就是一个值，值为1时...值为0时...

但这个锁的读写依旧会冲突，套娃了

B: 严格轮换法

进程0:

while (turn != 0);
critical_region();
turn = 1;

进程1:

while (turn != 1);
critical_region();
turn = 0;

缺点：进程只能交替进入临界区，如果一个进程一直不出来，其他进程只能等着

将锁变量于警告变量的思想结合起来(Peterson算法)

每个进程在进入前：

int other = 1 - proocess;
interested[process] = True;
turn = process;
while(true == process && interested[other] == True)

离开后：

interested[process] = False;

进入前和离开后很妙，这样就不会进入到临界区发生冲突了

进程间通信——同步

进程间需要传输数据是比进程间互斥更复杂的

这是一个同步问题

生产者消费者问题

诶好像老师这节课就在讲这个，好像跟上了

首先需要一个共享的固定大小的缓冲区，进程1往缓冲区存放数据（生产者），进程2从缓冲区读取数据（消费者）

缓冲区满，生产者就要阻塞，缓冲区空，消费者就要阻塞

有界缓冲区问题

Question

如何让两个进程同步？

信号量

down/up 进程对共享的信号量的操作-1/+1

int full = 0, empty = 7;
int mutex = 1;
// 生产者
item = produce_item(); // 生产item等待插入
down(&empty); // 空位-1
// 当缓冲区满时，empty=0，对empty的down操作会让自己睡眠
down(&mutex); // 代表要读写缓冲区了 mutex-1
insert_item(item); // 把数据插入缓冲区
up(&mutex); // 结束访问缓冲区
up(&full); // full ++

// 消费者(和生产者的full和empty换了个顺序)
down(&full);
down(&mutex);
item = remove_item();
up(&mutex);
up(&empty);
// 如果把empty从0变成1，就会把睡眠的生产者进程唤醒
consume_item(item);

CPU 调度算法

进程有两种

  • 计算密集型：长时间占用CPU
  • I/O密集型：CPU计算时间短，但访问外接设备时间长

由于cpu速度增长很快，所以现在更多考虑优化I/O密集型进程

不同场景需要不同调度策略，调度策略可以大致分为3类环境：

  1. 批处理

A: FCFS(First Come First Serve)

缺点：遇上一个计算密集型的就会卡着，明明计算快的可以先运行然后早点进入I/O的

B: 最短作业优先

C: 最短剩余时间优先

  1. 交互式

用户与电脑交互时，需要多个进程同时执行

A: 轮转调度：

cpu 在进程间轮转，一次执行一个进程的时间称为时间片，时间片不能太短，因为进程的切换需要从用户态到内核态进行处理，再回到用户态

B: 优先级调度

根据优先级进行调度，但优先级也不是死的，不能一直只让优先级最高的运行。使用多级队列反馈算法，运行过一次后，优先级-1，优先级的定义是相对的，这样可以一直减下去

  1. 实时系统

视频流的播放，要求准时，轻正确运行

内存管理

内存管理 地址空间

内存管理多进程：

  1. 多个进程独立，程序内部使用相对地址
  2. 进程保护，有进程访问不是自己范围内的地址时，操作系统要进行干预保护

因此，我们需要一种存储器抽象：地址空间

在cpu配备两个专门的寄存器：基址寄存器、界限寄存器

  • 基址寄存器会存下当前进程的起始地址
  • 界限寄存器会存下当前进程占据的长度

这种方法的前提是程序在内存中是连续的

有了进程的地址空间，下一个问题：

内存大小有限，而进程数量通常很多，放不下的话只能将一部分暂时放到磁盘中，称为交换(swapping)技术

这样会使内存碎片化，可以使用内存紧缩技术来去除碎片，但会消耗大量CPU时间，后续再讲解虚拟内存技术

内存是如何具体管理的？

  • 位图：将内存划分成单位小区域每个区域标记为0/1，当一个进程需要加载内存时，就扫描寻找连续的0

  • 链表：每一块连续的区域都用链表表示，链表维护区域的头和尾的地址，此时查找有两种算法：

  • 首次适配算法

  • 最佳适配算法

顾名思义

内存管理 虚拟内存

上文讲的地址管理方式的缺点
  • 基址寄存器和界限寄存器的方法已不再使用，进程大小超过内存无法解决
  • 使用swap技术时，大块内存的转移会耗费大量时间

更好的做法！

把进程的内存切碎，每一小部分称为1页，只会有几页的内容存储在内存中，当cpu访问到不在内存中的页，则会把那一页从磁盘读取到内存中

这就是虚拟内存

会有一个地址转换器(MMU, Memory Management Unit)，负责把虚拟地址转换为物理地址，如何实现这个转换？

维护一个用来记录虚拟地址到物理地址页框的映射关系，页表

地址计算

举例，指令中虚拟地址为20500(B)，每个页面大小为4KB

即在页面5往后20B

\[20500B = 20B + 20480B = 20B + 20KB\]

20KB为起始地址，20B为偏移地址

这个地址转换后续再细搞，和位运算也有一腿，和缓存的计算也有点相似之处

还有什么多级页表

输入输出