抄书

Processes & CPU

1. 进程的地址空间（逻辑空间布局）：代码区 code / .text、数据段（常量区 .rodata、全局数据区）、堆区 .heap、栈区 .stack、命令行参数区。x86 中的堆地址向上生长（低地址→高地址）、栈地址向下生长（高地址→低地址）。

   进程的运行时布局：只读部分和可读/写部分，只读段包含 code、.text 与 .rodata，读写段包含 .rwdata、.bss、堆栈区。

   进程的进程实体包括：程序段、数据段、PCB、堆栈、寄存器。

   （即使每次代码段相同，处理的数据段也相同，但OS为其分配PCB、进程号、堆、栈等系统分配资源肯定不同，故一个程序不能多次属于同一个进程）

2. 操作系统的三个要求：

   • Multiplexing：多个程序可并发执行，多处理器环境下多个程序可并行执行，共享CPU、内存、I/O设备软件资源与硬件资源。
   • Isolation：一个程序的运行不能影响OS，以及其他程序的运行。每个进程有独立的内存运行空间、CPU、I/O 设备，”感觉整个系统只有自己在运行，自己拥有一台私有的计算机系统”。
   • Interaction：共享终端（显示器、键盘等）。

3. ELF 由由4部分组成：ELF 头、程序头表、节、节头表。ELF 头描述文件的类型、程序头表与节区头表在文件中的位置和大小等信息。软件在运行时使用程序头表，在链接时使用节头表。

4. 进程五个基本特征：动态性、独立性、并发性、异步性、结构特征。

   动态性：由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡，具有一定的生命期。

   独立性：是系统中独立获得资源和独立调度的基本单位。支持线程的系统中，进程 是 独立获得资源 的基本单位，线程 是 独立调度 的基本单位。

5. 进程的状态：新建、就绪、执行、阻塞、结束。

   fork()：新建→就绪；yield()：执行→就绪；sleep()：执行→阻塞；finish()：执行→结束。

   在 xv6 中新建被分为 UNUSED（PCB 尚未使用）与 USED（正在初始化），其中结束状态为 ZOMBIE（父进程没有调用 wait() 来回收，调用后转为 UNUSED）。

   

6. PCB：系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。系统利用 PCB 来控制和管理进程，故 PCB 是系统感知进程存在的唯一标志，PCB 和进程一一对应，例如进程队列实际上是 PCB 队列。

   系统启动时，初始化一个进程表，其大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。

   fork 的功能：父进程调用fork创建一个子进程（在进程表中找一个空项分配、分配 PCB、赋予 PID、将子进程的状态设置为新建）、系统复制父进程的上下文到子进程的地址空间、子进程在它自己独立的地址空间中运行、父子进程并发执行。对父进程返回子进程的进程号，对子进程返回 0。

7. 进程间通讯：

   • 共享内存：拿出一块虚拟地址空间来，映射到相同的物理内存中。但当多个进程向同一个共享内存中写入数据时可能会产生覆盖。
   • 消息队列：保存在内核中的消息链表。但通信过程中，存在用户态与内核态之间的数据拷贝开销。
   • 管道：实现简单，但是是单向的、通信方式效率较低。

8. Job：批处理系统中，计算机操作员提供给操作系统执行任务的工作单元。提交给系统的 Job 形成 Job 队列，系统根据一定作业调度算法来进行执行。

   调度算法：短线调度（CPU 的调度）、中线调度（Swapping）、长线调度（Job 调度）。

9. 调度的评价标准：CPU 利用率、系统吞吐量、响应时间与周转时间（平均周转时间、带权周转时间、平均带权周转时间）。

10. 常见调度算法：（无特殊标注都为任务调度、进程调度都可）

    • 先来先服务（FCFS）：不利于短进程。
    • 短作业优先调度算法（SJF）：优先分配最快完成的作业。所有作业同时到达时，SJF 是最佳算法，平均周转时间最短，但对长作业不利。当有短作业不断进入就绪队列时，长作业会产生饥饿现象。
    • 优先级调度算法：分配给优先级最高。动态优先级：占用时间长短、等待时间长短；静态优先级：进程类、作业资源要求（内存大小、IO 类型与数量）、用户类型。分为抢占式和非抢占式，区别在于更高优先级的进程加入时是否停止当前进程。在优先级相同的情况下，通常按照 FCFS 和 SJF 的顺序执行。
    • 时间片轮转调度算法（进程调度）：将所有的就绪进程按先后顺序排成队列，总是选择第一个进程执行，执行一个时间片后将进程置于队尾。
    • 多级反馈队列调度算法（进程调度）：多个就绪队列，每个队列中进程执行时间片的大小不相同，优先级越高，对应时间片越短；在一个时间片结束时未执行完毕则转入下一个队列末尾。同时会有抢占。

Synchronization

1. 互斥应该遵循：空闲让进、忙则等待、有限等待、让权等待。

2. 经典同步问题：

   • 生产者-消费者：

     full=0
     empty=n
     mutex=1
     producer():
      while(true):
          P(empty)
          P(mutex)
          // ...
          V(mutex)
          V(full)
     consumer():
     while(true):
          P(full)
          P(mutex)
          // ...
          V(mutex)
          V(empty)

     P 的顺序不能颠倒，可能会导致死锁；V 的顺序没有要求。

     多生产者或多消费者时 mutex 不能取消，保证对缓冲池的互斥访问（互斥信号量是给同类访问的）。

   • 读者-写者：

     读者优先：

     rmutex=1
     mutex=1
     reader():
      while(true):
          P(rmutex)
          if(readercount==0):
              P(mutex)
          readercount++
          V(rmutex)
          // ...
          P(rmutex)
          readercount--
          if(readercount==0):
              V(mutex)
          V(rmutex)
     writer():
      while(true):
          P(mutex)
          // ...
          V(mutex)

     公平情况：对上面读者有限增设信号量 wmutex=1，表示是否存在正在写或等待的读者，若存在则禁止新读者进入。

     wmutex=1
     rmutex=1
     mutex=1
     reader():
      while(true):
          P(wmutex)
          P(rmutex)
          if(readercount==0):
              P(mutex)
          readercount++
          V(rmutex)
          V(wmutex)
          // ...
          P(rmutex)
          readercount--
          if(readercount==0):
              V(mutex)
          V(rmutex)
     writer():
      while(true):
          P(wmutex)
          P(mutex)
          // ...
          V(mutex)
          V(wmutex)

     写者优先：

     wmutex=1
     rmutex=1
     mutex=1
     readable=1
     reader():
      while(true):
          P(readable)
          P(rmutex)
          if(readercount==0):
              P(mutex)
          readercount++
          V(rmutex)
          V(readable)
          // ...
          P(rmutex)
          readercount--
          if(readercount==0):
              V(mutex)
          V(rmutex)
     writer():
      while(true):
          P(wmutex)
          if(writercount==0):
               P(readable)
          writercount++
          V(wmutex)
          P(mutex)
          // ...
          V(mutex)
          P(wmutex)
          writercount--
          if(writercount==0):
               P(readable)
          V(wmutex)

   • 哲学家进餐：…

   • 理发师：…

3. 死锁：

   死锁产生的必要条件：互斥条件、不剥夺条件、请求和保持条件、环路等待条件。

   处理死锁：不处理、死锁预防（调度方式上破坏条件）、死锁避免（预知是否会死锁）、检测及解除死锁。

   （死锁预防对系统限制条件严格；死锁避免需要提前计算分配后系统是否安全）

   银行家算法。

Memory

1. 内存保护：

   • 界限寄存器方法：上下界寄存器法（分别存放作业的结束地址和开始地址，访问时比较超出则中断）、基址和限长寄存器方法（限长寄存器和相对地址比较超出则中断）。
   • 存储保护键方法：给储存块分配单独的保护键，每个作业赋予一个键，访问时不匹配则中断。

2. 覆盖与交换：

   • 覆盖：早期系统中把程序分为程序段来操作覆盖段，覆盖段可重用。
   • 交换：把暂时不用的某个程序及数据部分从内存移到外存中，腾出空间（处理器中的中级调度）。

3. 连续分配管理方式。

   内碎片：已经分配给作业但不能被利用的内存空间；外碎片：还没有分配给作业但不能被利用的空间。

   • 单一连续分配：只用于单用户、单任务的操作系统，各类资源利用率低，会产生内部碎片。

   • 固定分区分配：系统建立分区说明表，程序通过静态重定位的方式装入内存。不能实现多进程共享一个主存区，会产生内部碎片。

   • 动态分区分配：使用空闲分区表（记录分区号、起始地址、大小和状态）、空闲分区链。

     分区分配算法：

     • 首次适应（FF）：空闲分区按照地址递增的顺序串成队列，每次进程分配内存时都从队首开始找，顺着链表找到足够大的空闲分区。缺点：低地址外部碎片多、查找开销大。
     • 下次适应（NF）：如上，改为循环队列，从上次找到的分区的下一个分区开始找。缺点：缺乏大的空闲分区。
     • 最佳适应（BF）：空闲分区按照容量递增的顺序，分配空间时将满足大小的最小空闲分区分配给作业。缺点：产生很多难以利用的碎片空间。
     • 最差适应（WF）：如上，将满足大小的最大空闲分区分配给作业。缺点：大作业空间得不到满足。

     分区的动态管理：

     • 拼接技术（紧缩）：将所有已分配分区移动到主存的一端。
     • 回收时立即拼接 / 找不到空闲时拼接。

     缺点：存在外部碎片、无法实现多进程共享储存器（多进程共享主存段）、无法实现主存的扩充。

4. 非连续分配管理：

   • 分页存储：作业的地址空间划分为若干个大小相等的区域，称为页，将主存的储存空间也分为与页大小相等的区域，称为块。为作业分配空间时，以块为单位来分配。

     分页储存管理的逻辑地址包含：页号 P 与页内位移 W。为了将连续的页号映射到多个块，需要设立页表存放对应关系（页表寄存器会存放页表起始地址与页表长度）。具体访问步骤：计算页号与页内位移、比较长度超出则产生越界中断、页号与页表起始地址相加并在页表中找到对应块号、拼接得到物理地址。通过设置快表放置在高速缓冲存储器中可以加速寻找块号的过程。

     多级页表：由于系统逻辑地址位数较多，页表会很大，故可将逻辑地址划分为外层页号、外层页内地址、页内地址等。先用外层页号再外部页表上查找，找出的单元内容是二级页表的首地址，页表首地址加上外层页内地址就是页表项的地址，内容是块号。

     页的共享与保护：共享的方法为使页指向相同的物理块。有两种保护：地址越界保护、访问控制保护（设置控制存取字段，根据页面使用情况定义为读写执行等权限，访问时将操作与权限匹配）。

     优点：内存利用率高、实现离散分配、便于储存访问控制、无外部碎片；缺点：需要硬件支持、内存访问效率下降、共享困难、有内部碎片。

   • 分段存储：按照逻辑关系将作业分段。作业地址空间由若干个逻辑分段组成，每个分段从 0 编址、采用连续的地址空间（所以称段是二维的、分类与段内位移）。

     逻辑地址由段号 S 和段内位移 W 组成。设立段表，系统为每个进程建立段表，每个段表描述段号、段长、内存起始地址等。寻址过程与分页类似。

     段的共享与保护：共享通过多个作业的段表中相应表项指向被共享段的同一个物理副本来实现。

     优点：满足用户需要、便于动态链接和共享、无内部碎片；缺点：需要硬件支持、需要拼接技术来满足分段的动态增长和减少外部碎片、受主存可用空间的限制、有外部碎片。

   • 段页式存储：

     逻辑地址由段号 S、段内页号 P 和页内位移 D 组成。系统中同时设立段表与页表：每个进程建立段表、每个分段有一张页表。段表项包括段号、页表起始地址、页表长度。页表项包括页号和块号。

     段页式结合段式和页式的优点、但段页式的内部碎片比页式要多。

5. 虚拟内存：

   特征：离散型、多次性（作业可分成多次调入内存）、交换性（在运行过程中换入、换出）、虚拟性（逻辑上扩充内存容量）。

   储存管理方式：

   • 请求分页储存管理方式：请求分页 = 基本分页 + 请求调页功能 + 页面置换功能。

     扩充后的页表项有：页号、物理块号、状态位（是否在主存）、访问字段（被访问的次数、由置换算法参考）、修改位（调入内存后是否被修改）、外存地址（在外存的存放地址，调入页面时使用）。

     缺页中断：若发现访问的页面不在内存，产生缺页中断。缺页中断处理程序根据此页在外存中的处理位置将其调入内存。调页过程中若有空闲则直接装入，若无空闲需要先淘汰一些页面：

     

     缺页中断是特殊的中断：在指令的执行期间产生和处理缺页中断、一条指令可以产生多个缺页中断。

     缺点：有些情况下系统产生抖动现象、最后一页仍然存在未被利用的部分。

     页面置换：页面置换算法优劣直接影响系统效率。常见页面置换算法：

     • 最佳置换（OPT）：预知页面号引用串时，每次都淘汰以后不再使用或以后最迟被再使用的页面。无法实现，用作标准衡量其他算法优劣。
     • 先进先出（FIFO）：淘汰最先进入内存的页面。会产生 Belady 异常，且忽略了最早调入的页面往往是使用最频繁的页面。
     • 最近最少使用（LRU）：淘汰最近最长时间未被使用的页面。使用寄存器组和栈实现，最接近最佳置换算法。
     • 时钟置换（CLOCK）：设置访问位，维护所有页面的循环链表，当程序访问链表中有的页面时，页面访问位置 1，否则需要淘汰一个内存中的页面，当指向页面访问位为 1 时，访问位清零并下移，访问位为 0 时，淘汰这一页面并将访问位置为 1、指针下移。是 LRU 和 FIFO 的折中。
     • 改进时钟置换：增加修改位，优先淘汰没有修改过的界面。步骤如下：首先从当前位置循环扫描链表，遇到的第一个访问位和修改位都等于 0 的页面用于替换；若无法找到，重新扫描，寻找访问位为 0 的页面用于替换，这次扫描时将访问位置 0；若仍未找到，重新执行一遍前两步即可。

     抖动现象与缺页率：

     • Belady 异常：FIFO 置换算法的缺页率可能岁分配物理块数增加而增加。原因是 FIFO 的置换特征与进程访问内存的动态特征矛盾。LRU、OPT 与归类为堆栈算法的页面置换算法不会出现。
     • 抖动现象：可能会有页面不断被调入调出的情况，系统大部分时间花在调入调出上。原因是请求分页系统每个进程只能分配到所需全部内存空间的一部分。
     • 缺页率：作业在运行中共需访问 A 次页面，页面需要调入内存的次数为 F，则缺页率 f=F/A，命中率为 1-f。

   • 请求分段储存管理系统：在运行前将当前需要的若干段装入主存，运行过程中若访问的分段不在主存，则通过调段功能调入主存。将段表扩充为：段号、段长、内存始址、访问字段、修改位、状态位、外存地址。

     当访问的段不在主存中，则会产生缺段中断信号。操作系统处理时先在主存中查找是否有足够大的分区存放此段，若没有这样的分区，则检查空闲分区容量综合来进行拼接，或调出一个或几个段后再装入。

File-System

1. FCB：文件控制块。文件由文件控制块与文件体两部分组成，FCB 包含的内容至少有：文件名、文件的结构（记录式还是流式、物理结构）、文件物理位置（储存地址与文件长度等）、存取控制信息、管理信息（建立日期、上次存取日期、当前使用状态）。UNIX 称 FCB 为索引节点（i-node）。

2. 文件打开：

   内核对所有打开的文件维护一个系统级的表格，也就是打开文件表，各个条目称为打开文件的句柄，句柄中给出了打开文件相关的所有信息，如：读写偏移量（调用 read 和 write 时更新）、文件访问模式、对该文件 i-node 对象的引用、文件类型和访问权限。

   open 的过程为：

   1. 解析 open 系统调用给出的文件路径，确定文件名所在的文件目录表。根据文件名查找文件目录表，找到该文件所在的目录项；如果不存在文件，返回错误。
   2. 根据目录项找到要打开文件的 FCB，读入到全局的 FCB 表中，并设置相关信息。
   3. 在全局“文件表”中为该文件分配一个表项，建立指向 FCB 表中对应的 FCB 项的指针，并设置其它相关信息。
   4. 在进程的局部打开文件表中（U-area，PCB 的一部分）建立指向全局文件表中的相应项的指针，open 返回该文件在局部打开文件表中的偏移，即File Descriptor。

3. 文件共享方式：

   • 硬链接：基于索引结点的共享方式。传统树形文件目录的共享式不同用户通过将各自文件的 FCB 设置成相同的物理地址来实现的，而索引结点将 FCB 中的文件描述系统单独构成一个数据结构，并加入计数值来统计指向该索引结点的目录项的个数。

     能够实现文件的异名共享，但当文件被多个用户共享时拥有者无法删除。

   • 软链接：利用符号链实现文件共享。创建一个称为链接的新目录项，包含被共享文件的路径。

     能够让拥有者删除共享文件、可以通过网络链接所有文件，但是访问时需要逐层查找目录、开销较大。

4. 文件访问控制：读、写、执行。三类用户：拥有者、拥有者同组用户、其他用户。

5. 文件的实现：

   • 外存分配通常以块为单位，方式分为连续分配、链接分配、索引分配等。

     索引分配方式中，系统为每个文件分配了一个索引块，索引块中存放索引表，每个表项对应分配给该文件的一个物理块。索引分配方式支持直接访问、不会产生外部碎片、文件长度受限制，但索引块的分配增加系统存储空间的开销。

     当文件很大时，索引表也会很大。若索引表的大小超过物理块，可以将索引表本身作为一个文件为其建立索引表构成二级索引，以此类推。

   • 文件储存管理方式为空闲文件表法、空闲块列表法、位示图法（建立表示分配情况的二进制串，请求时，系统顺序扫描找出一组值为 0 的二进制位并分配）、成组链接法。

     成组链接法适用于大型文件系统，将所有空闲块按每组 N 块分为若干组，将每一组的盘块数量和该组的所有盘块号记入到超级块中，这样每组的第一个盘块就链接成了一个链表，而组内的多个盘块形成了堆栈（是临界资源，会有互斥访问锁）。

6. 磁盘中的信息：引导控制块（有无操作系统）、分区控制块、目录结构、文件控制块。

   磁盘的访问时间 = 寻道时间 + 旋转延迟 + 传输时间

   调度算法：先来先服务（FCFS）、最短寻道时间有限（SSTF）、扫描算法（电梯调度算法、SCAN）、循环扫描（C-SCAN）。

RAID 技术：将数据按位级或者按块级分散写入到多个磁盘上，多个磁盘可以同时读写存取操作，实现数据的并行存取，提高了系统的性能；结合数据冗余技术及校验技术，提高系统的可靠性。

IO Systems

1. 设备在应用程序中使用逻辑设备名称来请求使用，操作系统将目前可用的物理设备分配给该进程（OS 需要借助逻辑设备表 LUT 完成从逻辑设备到物理设备的映射），这易于实现 IO 重定向。

   IO 控制方式：程序直接控制方式、中断控制方式、DMA 控制方式、通道控制方式。

   

   IO 软件的结构：用户层软件（IO 调用）、设备独立性软件（命名保护阻塞缓冲分配）、设备驱动程序（设备寄存器、检查状态）、中断处理程序（唤醒驱动程序）、硬件。IO 请求自左向右处理、IO 响应自右向左产生。设备独立性软件执行所有设备的公有操作，向用户层（文件层）提供统一接口，从而实现设备的独立性。

2. 缓冲区：缓和 CPU 与设备速度不匹配的矛盾，提高设备和 CPU 的并行操作程度，提高系统吞吐量和设备利用率。

   • 单缓冲：当用户进程发出一个 IO 请求时，操作系统便在内存中为它分配一个缓冲区。缓冲区是共享资源，设备与处理器对缓冲区的操作是串行的。
   • 双缓冲：缓冲对换。在双机通信时一般设置两个缓冲区用于发送和接受。
   • 多缓冲（循环缓冲）：设置环形缓冲区循环处理。
   • 缓冲池：设置多个缓冲区，可分为空缓冲队列、输入队列（装满输入数据）、输出队列（装满输出数据）。还有收容/提取 输入/输出数据的工作缓冲区。

3. SPOOLing：假脱机 IO，利用一台可共享的、高速大容量的块设备（例如硬盘）来模拟独享设备的操作，使一台独享设备变为多台可并行使用的虚拟设备，即把独享设备变为逻辑上的共享设备。

   脱机输入利用外围控制机将低速 I0 设备上的数据预先输入到磁盘上，然后从磁盘上直接读取输入数据; 脱机输出利用外围控制机将主机先将输出数据写到磁盘上的数据在低速 IO 设备上输出;

   可以理解为：基于 SPOOLing 技术，OS 将物理打印机虚拟为磁盘上的一个文件。

4. 流：用户级进程与设备之间的一个全双工的链接，能让应用程序动态地组合驱动程序代码流水线。流机制提供了一个框架，可以方便使用模块化的思想，在 UNIX 中得到广泛应用。

   流包括：与用户进程之间的接口（流头标）、与设备之间的接口（设备驱动程序尾部）、两个接口之间可以有若干个模块。

题目

请结合操作系统各部分的功能，说明在命令窗口中输入 a.out 及回车后，到屏幕输出 Hello World\n 为止，操作系统对程序 a.out 的处理与执行过程。

操作系统做了什么？

• 找到 a.out 程序的相关信息， 检查其类型是否是可执行文件；并通过程序首部信息，确定代码和数据在可执行文件中的位置并计算出对应的磁盘块地址；
• 创建 一个新 的进程，并将 a.out 可执行文件映射到该进程结构，表示由该进程执行 a.out 程序；
• 操作系统：为 a.out 程序设置 CPU 上下文环境，并跳到程序开始处执行 a.out 程序的第一条指令，由于此时代码数据还没有调入内存，发生缺页异常；
• 分配一页物理内存 ，并将代码从磁盘读入内存，然后继续执行 a.out 程序 a.out 程序执行 printf 函数，在显示器上写一字符串 Hello World\n；
• 遇到 \n 刷新缓冲区，找到要将字符串送往的显示设备；
• 控制设备的进程告诉设备的窗口系统它要显示字符串，窗口系统确定这是一个合法的操作，然后将字符串转换成像素，将像素写入设备的存储映像区；