OE.Heart's Blog

I/O 硬件 PC 总线结构 轮询（Polling） 中断 直接内存访问（DMA） 对于需要进行大量IO的设备，为了避免程序控制IO 即PIO，将一部分任务西方给了DMA控制器，在DMA开始传输时，主机向内存中写入DMA命令块。然后CPU在写入后继续干别的，DMA去自己操作内存总线，然后就可以向内存进行传输。 应用程序 I/O 接口 实现统一的 IO 接口，设备驱动提供了 API 来操控 IO 设备 I/O 设备在许多方面有很大差异： 字符流或块 顺序访问或随机访问 同步或异步 共享或专享 操作速度 读写、只读、只写 块与字符设备 块设备：包括硬盘，一般有读写seek的命令，对其进行raw原始IO或者文件系统访问。内存映射文件访问也OK 字符设备：键盘鼠标串口，命令是get put。库函数提供具有缓冲和编辑功能的按行访问。 网络设备 时钟与定时器 非阻塞与异步 I/O 阻塞IO：进程挂起直到IO完成，很容易使用和理解，但是不能满足某些需求 非阻塞IO：IO调用立刻返回。用户接口就是，接收鼠标键盘输入，还要在屏幕上输出，放视频也是，从磁盘读帧然后显示。 ...

大容量存储结构概述 磁盘 磁盘或硬盘（magnetic disk 或 hard disk）为现代计算机系统提供大量外存 移动磁头的磁盘装置 A: Track (磁道) B: Geometrical sector C: Track sector (扇区) D: Cluster (簇) 传输速率（transfer rate）是在驱动器和计算机之间的数据流的速率 定位时间（positioning time）或随机访问时间（random access time）包括两部分： 寻道时间（seek time）：移动磁臂到所要柱面的所需时间 旋转延迟（rotational latency）：旋转磁臂到所要扇区的所需时间 磁盘结构 磁盘驱动器可以看做逻辑块（logical block）的一维数组 逻辑块是最小的传输单位，大小通常为 512B 磁盘调度 对于磁盘，访问时间包括寻道时间和旋转延迟两个主要部分 FCFS 调度 先来先服务（First-Come First-Serve, FCFS） SSTF 调度 最短寻道时间优先（Shortest-Seek-TIme-First ...

文件系统结构 文件控制块（File Control Block, FCB）包含有关文件的信息，包括所有者、权限、文件内容的位置等 分层设计的文件系统 逻辑文件系统（logical file syste）管理元数据信息，也负责保护 文件组织模块（file-organization module）可以将逻辑块地址转成物理块地址，还包括可用空间管理器，以跟踪未分配的块并根据要求提供的文件模块 基本文件系统（basic file system）向适当设备驱动程序发送通用命令，以读取和写入磁盘的物理块 I/O 控制（I/O control）包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息 文件系统实现 概述 文件控制块 文件控制块中不包含文件名，而是交给目录项管理 磁盘上的数据结构： （每个卷的）引导控制块（boot control block）可以包含从该卷引导操作系统的所需信息 （每个卷的）卷控制块（volume control block）包括卷（或分区）的详细信息，在 Unix 中称为 superblock （每个系统的）目录结构用于组织文件 每个文件的 ...

文件概念 文件是存储某种介质上的（如磁盘、光盘、SSD等）并具有文件名的一组相关信息的集合 文件系统提供机制，以便对计算机操作系统与所有用户的数据与程序进行在线存储和访问 连续的逻辑地址空间 位、字节、行或记录的序列，其含义由文件的创建者和用户定义 文件属性 名称：符号文件名是以人类可读形式来保存的唯一信息 标识符：标识文件系统的文件的唯一标记（通常为数字） 类型：支持不同类型文件的系统需要这个信息 位置：指向设备与设备上文件位置的指针 尺寸：文件的当前大小（以字节、字或块为单位）以及可能允许的最大尺寸 保护：访问控制信息确定谁能进行读取、写入、执行等 时间、日期和用户标识：文件创建、最后修改和最后使用的相关信息可以保存，用于保护、安全和使用监控 所有文件的信息保存在目录结构中，目录结构保存在外存上 通常目录条目由文件名和唯一标识符组成，根据标识符可以定位其他文件属性 文件操作 创建、写入、读取、重新定位、删除、截断 打开文件表（open-file table）：用于维护所有打开文件的信息 系统调用open()返回一个指向打开文件表中的项的指针 每个打开文件具有如下关联信息： ...

背景 虚拟内存（virtual memory）将用户逻辑内存与物理内存分开 不需要将整个程序置于内存中 在现有物理内存有限的情况下，为程序员提供了更大的虚拟内存 虚拟内存大于物理内存 虚拟地址空间 随着动态内存分配，允许堆向上生长，也允许栈向下生长，只有在堆与栈生长时才需要实际的物理页 包括空白的虚拟地址空间称为稀疏（sparse）地址空间 虚拟内存允许文件和内存通过共享页为多个进程所共享 通过将共享对象映射到虚拟地址空间中，系统库可以为多个进程所共享 虚拟内存允许进程共享内存 当通过系统调用fork()创建进程时，可以共享页面，从而加快进程创建 虚拟内存可以通过两种方式实现： 请求调页（Demand Paging） 请求调段（Demand Segmentation） 请求调页（Demand Paging） 仅在需要时才加载页面 当进程需要执行时，它被交换到内存中，但不是整个进程交换到内存中，而是采用惰性交换器（lazy swapper） 惰性交换器除非需要某个页面，否则从不将它交换到内存中 调页程序（pager）只涉及进程的页面 基本概念 有效-无效位可用于 ...

背景 基本硬件 程序需要从磁盘中被移入内存，再分配一个进程来运行 CPU 可以直接访问的通用存储只有内存和处理器内置的寄存器 CPU 内置寄存器通常可以在一个 CPU 时钟周期内完成访问 完成内存的访问可能需要多个 CPU 时钟周期 在 CPU 寄存器和内存之间设置了高速缓存（cache） 为了系统操作的正确应保护内存 Memory Hierarchy 基地址寄存器和界限地址寄存器定义逻辑地址空间 基地址寄存器（base register）含有最小的合法的物理内存地址 界限地址寄存器（limit register）指定了范围的大小 地址绑定 符号地址（Symbolic Address）：源程序中的各种变量的名字。 可重定位地址（Relocatable Address）：地址在内存中相对某一位置的偏移量。编译器将符号地址转换为可重定位地址。 绝对地址（Absolute Address）：一个数值，地址在整个内存中的偏移量。链接器将可重定位地址转换为绝对地址。 指令和数据绑定到存储器地址可以发生在三个不同的阶段： 编译时（compile time）：如果在编译时就已知道进程 ...

系统模型 资源类型（Recourse types）包括 CPU 周期、文件、I/O 设备等 每个资源类型有一定数量的实例 每个进程只能按如下顺序使用资源： 申请（request） 使用（use） 释放（release） 死锁特征 必要条件 如果在一个系统中以下四个条件同时成立，就能引起死锁： 互斥（mutual exclusion）：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止 占有并等待（hold and wait）：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有 非抢占（no preemption）：资源不能被强占，即资源只能被进程在完成任务后自愿释放 循环等待（circular wait）：有一组等待进程 {P0,P1,⋯ ,Pn}\{P_0,P_1,\cdots,P_n\}{P0​,P1​,⋯,Pn​}，P0P_0P0​ 等待的资源为 P1P_1P1​ 占有，P1P_1P1​ 等待的资源为 P2P_2P2​ 占有，…， Pn−1P_{n-1}Pn−1​ 等待的资 ...

背景 临界资源：一次仅允许一个进程使用的资源 竞争条件（race condition）：多个进程并发访问和操作同一数据并且执行结果与特定访问顺序有关 临界区问题 每个进程有一段代码，称为临界区（critical section），进程在执行该区时可能修改公共变量、更新一个表、写一个文件等。 临界区问题：设计一个协议以便协作进程 在进入临界区前，每个进程应请求许可，实现这一请求的代码区称为进入区（entry section），临界区之后可以有退出区（exit section），其它代码为剩余区（remainder section）。 临界区问题的解决方案应满足三条要求： 互斥（mutual exclusion）：如果进程 PiP_iPi​ 在临界区内执行，那么其它进程不能在其临界区内执行 进步（progress）：如果没有进程在其临界区内执行，并且有进程需要进入临界区，那么只有那些不在剩余区内执行的进程可以参加选择，以便确定谁能下次进入临界区，而且这种选择不能无限延迟 有限等待（bounded waiting）：从一个进程做出进入临界区的请求直到这个请求允许为止，其它进程允许 ...

基本概念 CPU-I/O 执行周期 进程执行包括周期进行 CPU 执行和 I/O 等待 CPU 执行和 I/O 执行的交替序列 CPU 执行时间的直方图 I/O 密集型程序具有大量短 CPU 执行，CPU 密集型程序可能只有少量长 CPU 执行。 CPU 调度程序 进程选择采用短期调度程序（short-term scheduler）或 CPU 调度程序 抢占调度 需要进行 CPU 调度的情况可以分为四种： 当一个进程从运行状态切换到等待状态时 当一个进程从运行状态切换到就绪状态时 当一个进程从等待状态切换到就绪状态时 当一个进程终止时 1 和 4 必须要调度，2 和 3 还有其它选择。 如果调度只发生在 1、4 情况下，则调度方案时非抢占的（nonpreemptive）或协作的（cooperative），否则是抢占的（preemptive）。 Dispather Dispatcher 是一个模块，用来将 CPU 控制交给由短期调度程序选择的进程，这个功能包括： 切换上下文 切换到用户模式 跳转到用户程序的合适位置，以便重新启动程序 调度准则 CP ...

概述 每个线程是 CPU 使用的一个基本单元，与同一线程的其它线程共享代码段、数据段和其他操作系统资源。 多线程编程具有如下四大类的优点： 响应性：一个采用多线程的交互程序即使部分阻塞或者执行冗长操作，仍可以继续执行，从而增加对用户的相应程度 资源共享：线程默认共享它们所属进程的内存和资源 经济：进程创建所需的内存和资源更昂贵，创建和切换线程更加经济 可伸缩性：线程可在多处理器核上并行运行 多核编程 并发性（concurrency）：并发系统允许支持多个任务，允许所有任务都能取得进展（单核通过切换任务也能完成） 并行性（parallelism）：并行系统可以同时执行多个任务 并发不一定并行，并行一定并发 多线程模型 用户线程：通过用户层面的线程库实现线程管理，位于内核之上，无需内核支持，缺点是内核享受不到多线程带来的好处 内核线程：由操作系统来直接支持和管理 多对一模型 映射多个用户级线程到一个内核线程 一对一模型 映射每个用户线程到一个内核线程、 优点是在一个线程执行阻塞系统调用时，能够允许另一个线程继续执行，所以提供了比多对一模型更好的并发功能；也允许多个线 ...