冯·诺伊曼计算机模型

进程与线程

进程PCB

  • 进程PCB包含的内容
    1. 一个独立的进程空间，可装入进程映像；
    2. 一个独立的进程相关联的执行文件
    3. 进程所用的系统资源；
    4. 一个或多个线程。（进程在创建时一般同时创建好第一个线程， 其他线程按需要由用户程序请求创建）

进程的状态

  1. 进程有三大状态

    • running，正在使用CPU
    • ready，可以被运行，正在等待
    • blocked，不能运行直到外部事件发生

  2. 状态转换

进程间通信方式

管道

  1. 特点

    • 它是半双工的，具有固定的读端和写端
    • 它只能用于具有亲缘关系的进程之间通信（也是父子进程或者兄弟进程之间）
    • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write等函数，但是它不属于其他任何文件系统，并且只存在内存中

  2. 原型：当一个管道建立时，它会创建两个文件描述符：fd[0]为读而打开，fd[1]为写而打开
    图1

  3. 例子：单个进程中的管道几乎没有任何用处。所以调用pipe的进程调用fork，这样就创建了父进程与子进程之间的IPC通道。
    图2

FIFO（命名管道）

  1. 特点

    • 可以在无关的进程之间交换数据，与无名管道不同
    • FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统之中

  2. 例子：FIFO的通信方式类似于在进程中使用文件来传输数据，只不过FIFO类型文件同时具有管道的特性。在数据读出时，FIFO管道同时清除数据，并且“先进先出”
    图3

消息队列

是消息的链表，存放在内核中。一个消息队列由一个标识符（队列ID）来标识

  1. 特点
    • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级
    • 消息队列独立于发送与接受进程。进程终止时，消息队列及其内容不会被删除
    • 消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按照消息的类型读取

信号量

  1. 特点
    • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存
    • 信号量基于操作系统的PV操作，程序对信号量的操作都是原子操作
    • 每次对信号量的PV操作不仅限于对信号量值+1或者-1，而且可以加减任意正整数
    • 支持信号量组

共享内存

指多个进程共享一个给定的存储区

  1. 特点
    • 共享内存是最快的一种IPC，因为是进程直接读取内存
    • 因为是多个进程同时操作，所以需要同步
    • 信号量常和共享内存一同使用，信号量用来同步对共享内存的访问

Socket

  1. 特点：
    • 可以用于不同机器之间的进程通信

进程调度

  1. FCFS，先到先服务。缺点：护航效应

  2. JSF，最短作业优先。缺点：饿死

  3. Round-robin，时间片。缺点：频繁的上下文切换，没有考虑优先级

  4. Priority Scheduling，优先队列，每个任务分配一个优先级，每个优先级使用FCFS。缺点：也会饿死

  5. Multi-level Feedback Algorithm，循环遍历优先级队列，且时间片越来越长

  6. Guaranteed Scheduling，保证调度，保证每个进程都能分到1/n的CPU。缺点：其实不公平

  7. Lottery Scheduling，彩票调度

内存调度

存储层次

  1. 理想的内存：大、快、非易失性、便宜

  2. 实际的内存：小内存快速，昂贵，易失；大内存慢，便宜、非易失

地址空间

  1. 每个进程有自己的地址空间，独立于于其他进程的空间

  2. 动态定位：将进程的地址空间放在内存的不同部分

内存分配

内存管理的方法

  1. 外部碎片：进程被交换进物理内存和交换出物理内存，时间长了会形成很多空洞

  2. 使用bitmap进行内存管理

    1. 分配单元越小，bitmap越大
    2. 寻找一个连续的空块是很慢的

  3. 使用链表进行内存管理

    1. 使用链表记录内存分配情况

空闲块的选择

  1. First Fit：选择第一个可用的空洞。缺点：创建更多的空洞

  2. Next Fit：从上一个选择的空洞开始继续向下寻找。缺点：比First Fit的效果还差

  3. Best Fit。缺点：创建不可用的小空洞

  4. Worst Fit。缺点：减少了大型进程能够运行的空洞

  5. Quick Fit：为一些常见的请求大小维护单独的列表

overlaying

  • 可以将程序分割成小的片段，交换片段由操作系统完成，但程序员需要把程序手动分割成片段，这提高了编程的复杂度

虚拟内存

  1. 虚拟内存提供足够的内存给用户所需，所以一般虚拟内存地址空间大于物理内存地址空间

  2. 分页是用来实现虚拟内存的一种方式

    • pages:被分割的虚拟内存单元
    • page frames:对应的位于物理内存的单元

  3. page会轮流被装载到物理内存中，产生的映射存储在page table，page table需要装载到物理内存中，寻找一个没被映射到物理内存的page会产生一次page fault

  4. MMU（memory manangement unit）将虚拟地址翻译为物理地址

    • TLB是MMU中的一块高速缓存，在翻译过程中首先寻找TLB

多级page table

  1. 单极页表需要连续的内存空间存储页表项，并且大部分页表项是未使用的

  2. 多级页表使用一个额外的页表项作为目录，并且只需装载需要的部分page table进入内存中

反转页表（Inverted Page Tables）

  1. 每个页表项是哈希索引，哈希索引每一项指向虚拟内存到物理内存的映射，哈希索引的大小与物理内存页的数量相同。所以具有更小的体积，但是需要维护额外的哈希链开销

  2. 因为一个物理页不可能有多个共享虚拟地址。解决这个问题的方法是允许页表包含一个虚拟地址到物理地址的映射，这意味着对未被映射的虚拟地址的引用会导致页错误

页面置换算法

  1. Random page replacement：随机替换一个页面

  2. First in First Out：替换存在物理内存中最久的page

  3. Not Recently Used(NRU)：维护两个标记位，一个标记位R标识对象是否被使用过，另一个标记为M标记对象是否被修改过，当一个对象在缓存中被找到时，R置为1，当一个对象被修改，M置为1，优先级如下。该算法认为最近被使用过的对象比最近被修改过的对象更重要

      1. referenced, modified
      1. referenced, not modified
      1. not referenced, modified
      1. not referenced, not modified

        当缓存已满则按照从下到上的优先级替换page

  4. Least Recently Used(LRU)：替换掉页面中最久没被使用过的page

    1. 使用一个链表，如果一个page被访问且在链表中，则将其移到链表头部，如果不在链表中，则插入到链表头部，如果链表满了，则选择移除链表最尾的page
    2. 老化算法：越近使用权重越大

  5. Not Frequently Used(NFU)：最不常用算法，使用一个计数器来记录页面使用状况

  6. Working Set：保留最近的工作集页面

文件系统

文件系统布局

  1. MBR（(Master Boot Record）在第0个扇区，用于启动计算机

  2. partition table用于给出每个分区的开始与结束地址，并将其中一个分区标记为激活

  3. 每一个分区有自己的文件系统，并且开头为一个boot block

    这个boot block包含一个小程序，引导操作系统进入该分区

  4. 操作系统启动时，BIOS读取MBR，然后定位激活的分区，读取分区的boot block并执行

文件实现

  • 文件的实现指的是追踪每个文件位于哪一硬盘块中

连续分配

  1. 使用连续的块存储每一个文件

  2. 优点：实现简单，只需要记录文件起始位置与长度，读取性能很好

  3. 缺点：产生磁盘碎片，并且需要预先知道文件的最大大小，否则文件大小无法增长

  4. Good for CD-ROMs, DVDs and other write-once optical media

Linked List Allocation

  1. 用链表链接一串硬盘块来存储文件，块可能存储在硬盘的各个位置，每个块的第一个字指向下个文件块的位置

  2. 优点：没有外部碎片，只需要记录文件的开始块，文件可以无限增长，顺序读取快

  3. 缺点：随机访问慢，块中的数据量不是2的幂

  4. 改进：

    1. Linked List Allocation Using FAT：使用硬盘每个分区的第一个扇区来存储FAT（File Allocation Table），即把每个文件块的指针单独存放在一个文件用作索引

      1. FAT需要装载到内存中以减少硬盘寻道

      2. FAT的一个条目包含文件块所在的位置以及下一个文件块索引所在的位置

      3. 优点：整个磁盘块可以用来存储文件数据，只需要记录文件索引的开始块

      4. 缺点：需要把FAT加载到内存中

    2. Indexed Allocation (i-Node)：将文件的所有指针放在一个位置（i节点），所有文件都有自己的i节点

      1. 在打开文件的时候只需要把该文件的i节点加载进内存

      2. 所有的目录条目只需要存放i节点地址即可

      3. 优点：支持直接访问，没有外部碎片，只需要文件对应的i节点加载进内存

      4. 缺点：需要额外的空间开销存放index

I/O控制

  1. 每一个控制寄存器有特殊的I/O端口

  2. 特别的I/O指令用于读/写这些控制寄存器

Separate I/O and memory space

Memory-mapped I/O

  1. 优点：无需特别的指令来读写控制寄存器，无需特别的保护机制来保护控制寄存器不受用户的直接访问

  2. 缺点：如果控制寄存器的值是缓存的会导致问题。

I/O中断

  • 使用DMA来作为I/O设备与CPU的中转站，一次传输多个字符，以防CPU被频繁打断