NumPy's Blog

操作系统笔记(10)-并发简介 操作系统除了支持多进程之外，对单个运行的进程也提供了多任务运行的支持，即 线程，每个 线程 类似于独立的进程，与多进程不同的是，它们之间 共享地址空间，从而能够访问相同的数据。另一个不同的地方在于 栈，单线程中只有一个栈而多线程中每个线程都有一个栈 每个线程都有自己的一组用于计算的寄存器，因此，如果在单核机器上运行两个线程，从一个线程切换到另一个线程时，必定发生 上下文切换 线程的 上下文切换 类似于进程的 上下文切换，需要一个或多个 线程控制块（TCB） 来保存每个线程的状态 共享数据的难点 使用 多线程 访问共享数据时，很容易产生一个问题就是当多个线程访问同一个地址空间时会出现 竞态，到底谁先访问谁后访问，很多时候可能会产生不同的结果，也因此有了一些并发术语： 临界区（critical section） : 是访问共享资源的一段代码，资源通常是一个变量或数据结构 竞态条件（race condition） : 出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致了令人惊讶的结果 不确定性（indeterminate） ...

操作系统笔记(9)-超越物理内存:机制与策略简介 如果我们需要支持许多同时运行的巨大地址空间，仅仅靠 多级页表 是不够的，我们还需要在内存层级上再加一层 为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来，硬盘 通常能够满足这个需求，多道程序的出现，强烈要求能够换出一些页，因为早期的机器显然不能将所有进程需要的所有页同时放在内存中 我们要做的第一件事情就是在硬盘上开辟一部分空间用于 物理页 的移入和移出，一般在操作系统中，这样的空间称为 交换空间，因为我们将内存中的页交换到其中，并在需要的时候又交换回去 存在位 通过之前的机制，我们知道页表项 PTE 中含有一些位，其中的 存在位 的作用就是标识此页是在物理内存还是硬盘中，访问不在物理内存中的页，这种行为通常被称为 页错误（page fault） 页错误 不论在哪种系统中，如果页不存在，都由操作系统负责处理 页错误，操作系统的 页错误处理程序 确定要做什么 如果一个页不存在，它已被交换到磁盘，在处理 页错误 的时候，操作系统需要将该页交换到内存中，而要找到其在硬盘中的哪个位置，就需要用到 PT ...

操作系统笔记(8)-多级页表简介 假设一个 32 位地址空间（2^32 字节），4KB （2^12 字节）的页大小和 4B 的页表项大小，那么每个进程需要用来维护页表的内存就是 4 * 2^20B 也就是 4MB，当多个进程运行时，页表占用的空间就会非常大！ 为了解决这个问题，提出了 多级页表 ，它的思想是将页表分成 页大小 的 单元，如果一整块 单元 的页表项无效，就完全不分配该页的页表，为了追踪页表的页是否有效，引入了一个新的数据结构叫 页目录（PD），它可以告诉你页表的页在哪里或者页表的整个页不包含有效页 可以看到，多级页表 的工作方式就是让线性页表的一部分消失（因为实际运行的程序中可能会有很多单元无效），就相当于将原来的一大张页表拆分成很多小的，用一个 页目录 来映射这些 小页表，如果某个小页表中的所有项都是无效的，就不分配这页的内存，如下图所示： 上图就是 二级页表 结构，每一个 有效 的 页目录项（PDE） 都对应这一张含 有效 页表项的页表，可以大大节省空间，但是这样会产生额外的内存引用开销，因此 多级页表 是一个时间——空间折中 详细示例 设想一个大小为 ...

操作系统笔记(7)-快速地址转换简介 使用分页作为核心来实现虚拟内存，可能会带来较高的性能开销：额外的 内存引用 为了改善这个问题，我们需要硬件的帮助，它的名字叫 地址转换旁路缓冲存储器（translation-lookaside buffer），简称 TLB，也可以叫它 地址转换缓存 TLB 在处理器核心附近，设计的访问速度很快 TLB 的工作原理 对每次内存访问，硬件先检查 TLB ，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表。因此 TLB 带来了巨大的性能提升 算法流程如下： 从虚拟地址中 提取页号（VPN） 检查 TLB 中是否有该 VPN 对应的物理帧号 PFN 如果有，TLB 命中，转换成功 如果没有，TLB 未命中，硬件就访问 页表 来寻找地址映射 用找到的映射来更新 TLB 谁来处理 TLB 未命中 早期的硬件有复杂指令集，可以全权处理 TLB 未命中，然后去遍历 页表 找到对应的地址映射（如 x86 架构） 更现代的体系结构都是精简指令集计算机，通过软件管理 TLB，发生 TLB 未命中时，硬件系统会抛出一个异 ...

操作系统笔记(6)-分页简介 将空间切成不同长度的分片以后，空间本身会 碎片化（fragmented），随着时间推移，分配内存会变得比较困难 因此，出现了另一种叫作 分页 思想: 将空间分割成 固定 长度的分片，每个单元称为一页 相应地，把物理内存看成是定长槽块的阵列，叫做 页帧（page frame），每个这样的 页帧 包含一个虚拟内存页 如何映射到真实的物理地址 接下来，我们关心如何将虚拟页映射到物理页，首先为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存了一个数据结构，称为 页表（page table） 页表 的主要作用是为地址空间的每个虚拟页面保存 地址转换，从而让我们知道每个页在物理内存中的位置 假设单页的大小为 16B ，以一个 64B 的虚拟地址和一个 128B 的物理地址为例，它们的 页表 和 页帧 分布如下图: 我们可以用一个 6 位的二进制数来表示虚拟地址(2^6 = 64)，由于分为了 4 页，我们可以用高两位来表示地址属于哪一页，也叫 虚拟页面号，然后用剩余四位来表示当先页的 偏移量（offset） 如图 ...

操作系统笔记(5)-空闲空间管理简介 在堆上管理空闲空间的数据结构通常称为 空闲列表（free list)，该结构包含了管理内存区域中所有空闲块的引用 外部碎片 是指空闲列表中出现了很多小的内存块，导致无法分配一块较大的内存 内部碎片 是指分配了多余的内存，浪费发生在已分配单元的内部 底层机制分割与合并 假设有一段 0~30 字节的地址空间，其中 10~20 已经被使用了，那么剩余的就是空闲空间，用空闲列表表示如下： 如果要申请一块大小为 5 字节的空间，可以将第一个节点 分割 如果要释放原来的空间，也可以与空闲列表中的结点 合并 成一个更大的结点，以满足较大内存的需求 追踪已分配空间的大小 在 C 语言中，free() 函数可以释放空间，但是它只接受一个指针为参数，所以要知道待释放的空间的大小，需要在头块中保存一点额外的信息，这个头块通常就在返回的内存块之前 该头块至少包含所分配空间的大小，也可能包含一些额外的指针来加速空间释放，包含一个幻数来提供完整性检查，以及其它信息 typedef struct header_t { int size ...

操作系统笔记(4)-内存虚拟化概述 用户程序生成的每个地址都是 虚拟地址 操作系统只是为每个进程提供一个 假象，具体来说，就是它拥有自己的大量私有内存。在一些硬件的帮助下，操作系统会将这些假的 虚拟地址 变成真实的物理地址，从而能够找到想要的信息 地址空间 地址空间（address space）是运行中的程序看到的系统中的内存，假设只有 代码 、堆 和 栈 这三个部分： #include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { printf("location of code : %p\n", (void*)main); printf("location of heap : %p\n", (void*)malloc(1)); int x; printf("location of stack : %p\n", &x); return 0; } /* output: location of c ...

操作系统笔记(3)-进程调度简介 在操作系统获取 CPU 控制权之后, 可以选择调度执行的进程以提高工作效率 为了实现这个目的, 出现了许多种调度策略, 它们各有优势, 是操作系统发展中不可或缺的一部分 工作负载假设我们对操作系统中运行的进程（有时也叫工作任务）作出如下假设： 每一个工作运行相同的时间 所有工作 同时 到达 一旦开始, 每个工作保持运行 直到完成 所有工作只是用 CPU （即它们不执行 I/O 操作） 每个工作的运行时间是 已知 的 调度指标 周转时间（turnaround time） 定义为任务完成时间减去任务到达系统的时间，即 $T_{周转时间} = T_{完成时间} - T_{到达时间}$ 因为假设所有工作同时到达, 故 $T_{到达时间} = 0$ , $T_{周转时间} = T_{完成时间}$ 先进先出 (FIFO) 先进先出（First In First Out）也叫先进先服务, 意思就是任务按到达系统的先后执行, 假如有三个长度为 100 的任务, 则按照 FIFO 的方式, 其 $T_{平均周转时间} = (100 + ...

操作系统笔记(2)-受限直接执行概念 直接执行 ： 表示直接在 CPU 上运行程序 受限 : 为什么要 受限 呢 ? 是为了保证操作系统来管理资源, 防止其失去控制权, 操作系统必须以高性能的方式虚拟化 CPU , 同时保持对系统的控制, 因此程序的执行需要 受限 , 具体是受到硬件的限制 如何执行受限制的操作操作系统引入了两种模式: 用户模式：在此模式下运行的代码会受到限制。例如，在用户模式下运行时，进程不能发出 I/O 请求 内核模式：在此模式下，运行的代码可以做它喜欢的事，包括特权操作，如发出 I/O 请求和执行特权指令 用户如何执行特权操作 在 用户模式 下要执行特权操作，需要使用 系统调用 ，它允许内核小心地向用户程序暴露某些关键功能，例如访问文件系统、创建和销毁进程、与其他进程通信，以及分配更多内存 要执行 系统调用 ，程序必须执行特殊的陷阱(trap)指令, 该指令同时跳入内核并将特权级别提升到 内核模式，完成相应工作后，操作系统调用一个特殊的从陷阱返回(return-from-trap)指令，回到 用户模式 C 库中进行 系统调用 的部分是用汇编手工编 ...

Vim笔记(3)-选择操作简介 很多时候我们都需要批量选取文本并操作, 而 Vim 的 Virtual 模式提供了文本选取的功能 进入 Virtual 模式后我们可以配合各种移动操作快速选取文本 选择文本的三种 Virtual 模式 v : 进入字符选取模式, 从当前光标所指的字符进入 Virtual 模式并以字符为单位选取 V : 进入行选取模式, 选取当前行并进入 Virtal 模式, 以行为单位选取内容 <Ctrl-V> : 进入块选取模式, 以并行块的方式选取 练习 提供了两种模式下的参考答案 // 1. Remove "It is" // Normal mode: ldtb // Visual mode: lvtbd // 2. better => Better // Normal mode: ~ // Visual mode: v~ // 3. in one place, => in one place. // Normal mode: /,<ENTER>ncl.<ESC> // Visual mode: /,<ENTER>vc ...