保研面试408复习 4——操作系统、计网

标记文字记忆，加粗文字注意，普通文字理解。

1、操作系统

一、文件系统中文件是如何组织的？

• 文件控制块（FCB）
  • FCB存储文件的基本信息，像进程的PCB一样。
  • FCB的有序集合称为文件目录。文件目录也被视为一个文件，即目录文件。
    • 文件的目录：FCB的有序集合；目录文件：这个文件的信息是目录
  • 一个FCB就是一个文件目录项。
  • 知道了一个文件的FCB，那么就可以找到这个文件在磁盘中是存放在哪以及如何存储的。
  • 文件控制块一般不直接存储文件内容，因为这样的话，由于文件是存储在磁盘中的，要进行文件查找需要将文件调入内存，导致文件查找开销变得很大。所以FCB一般存储的是文件的文件名 和 索引信息，相当于FCB分为次部和主部，次部用于文件查找比对存放文件名；而主部存放在固定位置存放的是FCB的其他信息，它可能进一步确定文件内存的存储位置。如存储该文件的头磁盘号。
• 文件的逻辑组织：
  • 无结构文件（流式文件）
    • 是由一组相关信息组成的有序字符流
  • 有结构文件（记录式文件）
    • 目录文件是一种记录式文件
• 文件的物理组织：如何存储就是物理组织，比如顺序存储，索引存储，链接存储，混合索引存储

  • 文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。

  • 文件的存储方式和文件的存储位置存储在FCB中，只有找到了FCB才能知道文件的物理组织。

  • 连续分配
    

  • 索引分配

    • 索引分配将每个文件所有的盘块号都集中放在一起构成索引块(表)
      

  • 链接分配
    

• 混合索引分配：UNIX系统的inode结构（UNIX的文件FCB）
  • 直接块直接指向数据块
  • 一级间址指向一个索引块，索引块对应n个数据块
  • 二级间址指向一个二级索引块，一个索引块指向n个一级索引块，一个一级索引块指向n个数据块。
    

二、文件的整体概述

• 用户打开文件表、系统打开文件表、文件打开流程、UNIX超级块
  • 文件整体知识理解。

三、UNIX外存空闲空间管理

用来存放一组空闲盘块号(空闲盘块的块号)的盘块称为成组链块。成组链接法的大致思想是:把顺序的n个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块(作为成组链块)则用于保存另一组空闲盘块号，如此继续，直至所有空闲盘块均予以链接。系统只需保存指向第一个成组链块的指针。

• 看到下面这个图就想起来了：成组链接法的细节。
  

2、计算机网络

一、CSMA/CD 协议（数据链路层协议）

• 广播（信道上的所有设备都能收到，共享广播信道）
• 半双工（只允许单点成功发送）

---

CSMA/CD：载波监听 多路访问 /碰撞检测（Carrier Sense Multiple Access with Collision Detection）
先听后发，边发边听，冲突停发，随机延迟后重发（截断二进制指数退避算法）

• 先监听信道是否空闲，信道空闲再发送（先听后发）
• 如果信道空闲则发送该帧，边发该帧时同时检测是否产生冲突（即信道上是否出现其他结点发送的帧）。争用期计算的最短帧长，保证了如果存在冲突必然能够在发送时被检测到。（边发边听）
• 检测到冲突，则停止发送该帧，转而发送拥塞信号。（冲突停发）
• 采用截断二进制指数退避算法随机等待一段时间（这些可选的时间集合是争用期的倍数）继续发送。（随机延迟后重发）

二、以太网MAC帧MTU

• MAC帧的首部+CRC是18B，数据部分最短是46B，所以MAC帧最短64B。
• MTU是MAC帧数据部分的最大载荷部分，是一个MAC帧最多能携带的最长上层协议的长度。
  • 如果上层协议是IP协议，由于一般情况下IP首部是20B，则IP数据报的数据部分是不大于$MTU-20B$的。又由于IP数据报的偏移量是一个整数，它是以8字节为单位的，所以在进行IP数据报分片时，要求前一个IP数据报的数据部分必须是8个倍数，并且会尽可能分得更大。因此有$$MTU-8<20+IP数据报第二个分片的偏移量\ast 8<=MTU$$
  • 可以理解为$$20+IP数据报第二个分片的偏移量\ast 8<=MTU<20+(IP数据报第二个分片的偏移量+1)\ast 8$$
    • MTU如果更大一点则会导致偏移量更大。