操作系统

操作系统概述

操作系统是管理计算机硬件的软件。
计算机系统由以下4个部分组成：

• 硬件： 为计算机提供基本的计算资源，如CPU、内存、I/O设备等；
• 操作系统： 控制硬件，并协调各个用户应用程序的硬件使用
• 应用程序： 确定了用户为解决计算问题而使用这些资源的方式；
• 用户

I/O结构：

• 同步I/O：I/O 启动后，在 I/O 完成之前，控制权不会返回给用户程序。
• 异步I/O：I/O 启动后，控制权将返回给用户程序，而无需等待 I/O 完成
• DMA（直接内存访问）：设备控制器将数据块从缓冲区存储直接传输到主内存，无需 CPU 干预；每个块只生成一个中断，而不是每个字节生成一个中断

操作系统特征

• 并发：并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。
• 共享：互斥共享和同步共享。
• 虚拟：虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术
• 异步：进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

操作系统的分类

• 图形用户界面（GUI）操作系统
  特点：提供图形化的用户界面，易于使用，适合普通用户。

• 命令行界面（CLI）操作系统
  特点：通过命令行输入命令，适合高级用户和系统管理员。

• 单内核（Monolithic Kernel）
  特点：所有操作系统服务都运行在同一个内核空间，效率高，但可扩展性差。

• 微内核（Microkernel）
  特点：核心服务运行在用户空间，内核只提供最基本的服务，可扩展性强，但效率较低。

• 混合内核（Hybrid Kernel）
  特点：结合了单内核和微内核的优点，部分服务运行在内核空间，部分运行在用户空间。

几种操作系统：

• 实时操作系统
• 分布式操作系统：分布式系统是物理上独立的、可能是异构的、通过网络相连的一组计算机系统。网络是两个或多个系统之间的通信路径

内核态和用户态

内核态能使用更高级的指令
内核态到用户态是操作系统主动让出CPU使用权
用户态到内核态是中断引起的

中断与异常

中断：是操作系统和硬件交互的关键部分，硬件可以通过系统总线随时发送信号到CPU触发中断，当CPU被中断时，它停止正在做的事情，并立即转到固定位置执行中断处理程序，中断处理程序是操作系统的一部分，它负责处理中断，并恢复CPU到中断前的状态
中断分为内中断(异常)和外中断。
异常：陷阱、陷入；故障；终止
外中断：时钟中断；I/O中断请求

系统调用

系统调用是用户程序与操作系统内核之间的一种通信机制。当用户程序需要操作系统提供的服务时（如文件操作、进程控制等），它会通过系统调用向操作系统内核发出请求。
系统调用的类型：

• 进程控制：
  • 创建和终止进程
  • 加载、执行
  • 获取进程属性，设置进程属性
  • 等待事件，信号事件
  • 分配和释放内存
• 文件管理
  • 创建文件，删除文件
  • 打开、关闭文件
  • 读、写、重定位
  • 获取文件属性，设置文件属性
• 设备管理
  • 请求设备，释放设备
  • 读、写、重定位
  • 获取设备属性，设置设备属性
  • 逻辑增加或移除设备
• 信息维护
  • 获取时间和日期，设置时间和日期
  • 获取系统数据，设置系统数据
  • 获取进程、文件或设备属性
  • 设置进程、文件或设备属性
• 通信
  • 创建、删除通信连接
  • 发送、接收消息
  • 传输状态信息
  • 增加或移除远程设备
• 保护
  • 获取文件权限
  • 设置文件权限

进程

程序：是静态的，就是个存放在磁盘里的可执行文件，一系列的指令集合。
进程：是动态的，是程序的一次执行过程。
特点：

• 独立性：每个进程都有自己的独立地址空间和资源。
• 并发性：多个进程可以同时运行，操作系统通过时间片轮转等方式调度进程。
• 隔离性：进程之间的地址空间是隔离的，一个进程的崩溃不会影响其他进程。
  优点：
• 资源隔离：进程之间的资源隔离可以防止一个进程的错误影响其他进程。
• 稳定性：进程的隔离性提高了系统的稳定性。
  缺点：
• 上下文切换开销大：进程之间的上下文切换需要保存和恢复整个进程的状态，开销较大。
• 通信复杂：进程之间的通信需要通过进程间通信（IPC）机制，如管道、消息队列、共享内存等，通信开销较大。

线程

线程是进程中的一个执行单元，是操作系统调度的基本单位。一个进程可以包含多个线程，这些线程共享进程的资源，但每个线程有自己的执行栈和程序计数器。
特点：

• 轻量级：线程是轻量级的，创建和切换线程的开销较小。(同一进程下线程切换比进程小，从一个进程的线程切换到另一个进程的线程就不一样了)
• 并发性：多个线程可以并发执行，共享进程的资源。
• 共享性：线程共享进程的地址空间和资源，线程之间的通信开销较小。
  一对一模型
  在一对一模型中，每个用户级线程直接映射到一个内核级线程。这意味着每个用户级线程都有一个对应的内核级线程。这种模型的优点是线程的调度由操作系统内核直接管理，可以充分利用多核处理器的并行性
  一对多模型
  在一对多模型中，多个用户级线程映射到一个内核级线程。这意味着多个用户级线程共享一个内核级线程。这种模型的优点是线程的创建和切换开销较小，适合需要大量线程的应用。
  多对多模型
  混合模型结合了一对一和一对多模型的优点。在这种模型中，多个用户级线程映射到多个内核级线程。这种模型既保留了用户级线程的高效性，又利用了内核级线程的并行性。

调度算法

FCFS先到先服务调度

• 算法思想：先到达的进程先服务
• 非抢占式
• 公平、实现简单
• 等待时间长，对长作业有利，对短作业不利
  SJF最短作业优先调度
• 算法思想：短进程优先
• 非抢占式或抢占式
• 等待时间短
• 会长进程饥饿
  RR时间片轮转调度
• 轮流让就绪队列的进程依次执行一个时间片，时间片时间应大于80%进程时间
• 抢占式
• 公平，响应快，适用于分时操作系统
• 高频率的进程切换会有一定开销
  优先级调度
• 优先级高的先运行
• 非抢占式或抢占式
• 用优先级区分任务的重要程度，适用于实时操作系统
• 可能会饥饿
  多级反馈队列调度
• 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大，新进程到达时先进入第1级队列，按FCFS原则等待时间片，若用完进程没结束，进入下一级队列队尾，只有第k级队列为空时才会为k+1级队头的进程分配时间片
• 抢占式
• 对各类型进程相对公平，每个新到达的进程都可以很快得到响应，不必估计进程的运行时间
• 一般不说缺点，可能饥饿

进程同步

do{
    entry section;//进入区
    critical section;//临界区
    exit section;//退出区
    remainder section;//剩余区
}while(true)

当一个进程在临界区时，其他进程不允许在它们的临界区内执行
临界区问题解决方案应满足的要求

• 互斥
• 进步，有空让进
• 有限等待，发出请求后等待时间有限
  Peterson解决方案

P_i进程

flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = false;
remainder section;

P_j进程

flag[j] = true;
turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = false;
remainder section;

缺点：只能在2个进程时使用
硬件指令

• 中断屏蔽方法
  开关中断
• TestAndSet指令

bool TestAndSet(bool *lock){
  bool old;
  old = *lock;
  *lock = true;
  return old;
}
while(TestAndSet(&lock));
critical section;
lock = false;
remainder section;

• CAS指令

Swap(bool *a, bool *b){
  bool temp;
  temp = *a;
  *a = *b;
  *b = temp;
}
bool old = true;
while(old == true)
  Swap(&lock, &old);
critical section;
lock = flase;
remainder section;

互斥锁

acquire(){
  while(!available);
  available = false;
}
release(){
  available = true;
}

主要缺点：忙等待
信号量

• wait(S)，P(S)

void wait(int S){
    while(S<=0);
    S = S - 1;
}

- signal(S)，V(S)
void signal(int S){
    S = S + 1;
}

缺点：可能产生死锁

管程

类似一个类，基本特征如下：

• 局部于管程的数据只能被局部于管程的过程访问
• 一个进程只能通过调用管程中的过程才能进入管程访问共享数据
• 每次仅允许一个进程在管程内执行某个内部过程

monitor ProducerConsumer
  condition full, empty;
  int count = 0;
  void insert(Item item){
    if(count == N){
      wait(full);
    }
    count++;
    insert_item(item);
    if(count == 1){
      signal(empty);
    }
  }
  Item remove(){
    if(count == 0){
      wait(empty);
    }
    count--;
    if(count == N - 1){
      signal(full);
    }
    return remove_item();
  }
    

producer(){
  while(1){
    item = product;
    ProducerConsumer.insert(item);
  }
}
      

consumer(){
  while(1){
    item = ProducerConsumer.remove();
    consume_item();
  }
}
      

死锁

死锁的四个基本条件：

• 互斥条件
• 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
• 请求和保持条件
• 循环等待条件

死锁的处理

预防死锁

• 破坏互斥条件：
  将只能互斥使用的资源改造为允许共享使用，则系统不会陷入死锁。
  缺点：并不是所有资源都可以改造成可共享的资源。
• 破坏不剥夺条件：
  方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，等之后重新申请。
  方案二：当某个进程需要的资源被其他进程所占有时，可以由操作系统协助将想要的资源强行剥夺。(这种方法一般考虑各进程的优先级)
  缺点：
  • 实现复杂。
  • 释放已获得资源可能造成前一阶段工作的失效，只适用易保存和恢复的资源。
  • 反复申请和释放增加系统开销，减低系统吞吐量。
  • 采用方案一，只要暂时得不到某个资源，之前的资源就会放弃，重新申请。如果已知发生就会导致进程饥饿。
• 破坏请求和保持条件：
  采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源。
  缺点：有些资源可能只需要很短时间，因此如果整个运行期间都一直保持着所有资源，就会导致严重浪费，资源利用率极低。还有可能导致某些进程饥饿。
• 破坏循环等待条件
  采用顺序资源分配法，先给系统中的资源编号，每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。
  缺点：
  • 不方便增加新的设备，需要重新编号。
  • 进程实际使用资源的顺序可能和编号递增顺序不一致。
  • 必须按规定次序申请资源，用户编程麻烦。

避免死锁

处于安全状态一定不死锁，处于非安全状态，不一定死锁。
银行家算法：
1 if $request_i$ ≤ $need_i$ go to step 2
2 if $request_i$ ≤ available go to step 3
3 available = available - $request_i$
4 $allocation_i$ = $allocation_i$ + $request_i$
5 $need_i$ = $need_i$ - $request_i$
6 调用安全算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。

死锁检测和解除

检测有无死锁，有就立即解除。
检测死锁的算法：找出既不阻塞又不是孤点的进程，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。消去它所有的请求边和分配边，使之成为孤点，若能消去所有边就没有死锁。
解除死锁的方法有：

• 资源剥夺法：挂起(暂时放到外存上)某些死锁进程，并抢占它的资源。
• 撤销进程法：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。
• 进程回退法：让一个或多个死锁进程回退到避免死锁的地步。

内存管理

物理地址：是内存单元的实际位置
逻辑地址：程序在运行时使用的代码，也叫虚拟地址

覆盖技术
将内存分为固定区和覆盖区，将程序分为多个模块，经常使用的放在固定区，不经常使用的部分当需要使用的时候再放到覆盖区中

必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加用户编程负担。已成为历史。

交换技术

设计思想：内存紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

内存空间的分配

连续分配管理方式

连续分配：用户进程分配的必须是一个连续的内存空间

单一连续分配

将内存分为系统区和用户区。系统区用于存放操作系统，用户区用于存放用户进程相关数据。但内存只能有一道用户程序。
优点：实现简单；无外部碎片；不一定需要采取内存保护。
缺点：只能用于单用户、单任务的操作系统；有内部碎片；存储器利用率低。

固定分区分配

将整个用户区分为若干个固定大小的分区。
分区大小相等：缺乏灵活性，但很适用于用一台计算机控制多个相同对象的场合
分区大小不等：增加了灵活性。
操作系统需要建立一个数据结构————分区说明表，来实现各个分区的分配和回收。

优点：实现简单；无外部碎片
缺点：当用户程序过大，所有分区都不能符合要求，就不得不采用覆盖技术，但这会降低性能；会产生内部碎片，内存利用率低。

动态分区分配

在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。
用空闲分区表或空闲分区链来记录内存的使用情况。
动态分区分配算法
首次适应算法：每次从低地址开始查找，找到第一个能满足大小的空闲分区。
空闲分区按地址递增次序连接。
最佳适应算法：优先使用更小的空闲区。
空闲分区按容量递增次序连接。
最坏适应算法：优先使用最大的连续空闲区。
空闲分区按容量递减次序连接。
邻近适应算法：从上次查找结束的位置开始检索。
空闲分区以地址递增的顺序排列(可排成一个循环链表)。

非连续分配管理方式

分页存储

将内存分为一个个大小相等的分区，每个分区就是一帧/块；将进程的逻辑地址空间也分为与帧大小相等的一个个部分，每个部分就是一个页。
一个进程对应一张页表；进程的每个页对应一个页表项，每个页表项由页号和块号组成；页表记录进程页和实际存放的内存块之间的映射关系。
将逻辑地址拆分为页号和页内偏移量，就可以通过页号查询页表得到起始位置，再通过偏移量知道实际地址。
地址计算
设页面大小为L。

1. 计算页号P和页内偏移量W，(十进制就得算：P=A/L，W=A%L；二进制可以得到P和W)
2. 比较P和页表长度M，P ≥ M，则产生越界中断，否则继续执行。
3. P * L + W即为实际地址(设从0开始)

TLB(联想寄存器)
TLB是用来存放最近访问的页表项的副本的，也叫快表。
访问逻辑地址时，TLB有就直接访问，没有命中就按之前的方法访问物理地址，并将其存入快表中。

两级页表

单级页表的问题：

1. 页表必须；连续存放，因此当页表很大时，需要哦占用很多个连续的页框
2. 没必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问几个特定的页面

按地址结构将逻辑地址拆分为三部分：一级页表，二级页表，页内偏移量，解决问题一
需要内存时才把页面调入内存，在页表项中添加一个标志位，用于表示是否已经调入内存，解决问题二

分段存储

将逻辑地址分为段号和段内地址。需要为每个进程建立一张段映射表，简称段表。段表有段号(隐含的，不占存储空间)、段长、基址。
段长长度=段内块号长度。
段内地址不能大于等于段长。

虚拟内存

传统存储管理有2个问题：

1. 一次性：作业必须一次性全部装入内存后才能开始运行。这导致作业很大时，不能全部装入内存，导致大作业无法运行；当大作业需要运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
2. 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的，暂时用不到的数据，浪费了宝贵的内存资源。

局部性原理：时间局部性 & 空间局部性
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存。当程序执行时，当被访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
虚拟内存的主要特征：

• 多次性：允许被分为多次调入内存
• 对唤性：允许将作业换入、换出
• 虚拟性：从逻辑上扩充了内存的容量

虚拟内存技术，允许一个作业分多次调入内存，采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

复制读写

fork()允许父子进程共享内存中的同一个页面，这些共享进程会被标记为复制读写页面，只要有一个进程要改变共享页面，就会创建一个共享进程的副本。
vfork()创建子进程时，子进程与父进程共享同一内存空间。这意味着子进程对内存的修改会直接影响父进程。

请求页式

页表中添加有效位，表示是否有效无效就是发生了缺页中断，缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的。
处理缺页中断的步骤：请求调页，获取被放入的位置，将要执行的页面调入内存，更改有效位，重新执行引起缺页中断的指令。
给页表项添加一个修改位，表示是否被修改过，没有就是放入空页表，有就是要发生置换。

页面置换算法

先进先出置换算法(FIFO)：
把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面页面即可。
最佳置换算法(OPT)：
每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再访问的页面。
最近最久未使用置换算法(LRU)：
每次淘汰的页面是最近最久未使用的页面。赋予每个页面对应的页表项一个LRU位，来访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中t值最大的。
第二次机会置换算法(CLOCK)：
给页表项加一个访问位用来记录访问次数，再将内存中的页面连成一个循环队列，当被访问时，0的时候就可以置换它，1的时候将它设置为0，再给它一次机会。
改进的第二次机会算法：
给页表项添加两位，一位是访问位，一位是修改位，还是循环队列。(0,0)表示替换的最佳位置(0,1)表示不是很好的替换位置(1,0)表示不久可能要用(1,1)表示最坏的置换位置。
第一轮扫描扫到第一个(0,0)的页面进行替换，本轮不修改任何标记位。
第一轮失败，则进行第二轮，找第一个(0,1)的页面，扫描过的页面访问位设为0。
第二轮失败，则进行第三轮，找第一个(0,0)的页面进行置换，不修改任何标记位。
第三轮失败，则进行第四轮，找第一个(0,1)的页面进行置换。
基于计数的页面置换算法：
为每个页面的引用次数保存一个计数器，接下来有2个方案：

• 最不经常使用页面置换算法(LFU)：选择具有最小计数的页面置换。但计数大的会保留在内存中，可以定期将计数右移一位，形成以指数衰减的平均使用计数。
• 最经常使用页面置换算法(MFU)：具有最小计数的页面可能刚被引入并且尚未使用

页面缓冲算法
固定分配：每个进程分配一组固定数目的物理块，进程运行期间不再改变。
可变分配：先为每个进程分配一定数目的物理块，进程运行期间，可根据情况做适当的增加或减少。
全局分配：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
局部分配：发生缺页时只能选进程之间的物理块进行置换。
抖动
抖动是指系统中页面调入和调出的频率非常高，导致 CPU 处理时间主要用于处理页面调度，而很少有时间用于执行用户程序指令的现象。
产生原因：运行的程序所需的页面数量超过了操作系统为它们分配的内存帧数量。

内存映射文件

内存映射文件(Memory-Mapped Files)是一种将文件内容映射到进程的内存空间的技术，它允许程序像访问内存一样访问文件数据，而不需要传统的文件读写操作。

• 方便程序员访问文件数据。
• 方便多个进程共享同一个文件。

传统的文件访问方式：
open系统调用–打开文件
seek系统调用–将读写指针移到某个位置
read系统调用–从读写指针所指位置读入若干数据(从磁盘读入内存)
内存映射文件的访问方式：
open系统调用–打开文件
mmap系统调用–将文件映射到进程的虚拟地址空间
以访问内存的方式访问文件数据，文件数据的读入、写入由操作系统自动完成，进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘。
多个进程可以映射同一个文件，实现共享。

文件系统

文件概念

文件属性

• 名称
• 标识符
• 类型
• 位置
• 尺寸
• 保护
• 时间、日期和用户标识

文件操作

• 创建文件
• 写文件
• 读文件
• 重新定位文件
• 删除文件
• 截断文件

文件类型

文件结构

Windows只分可执行文件和其他文件。操作系统支持太多文件结构会带来一个缺点：操作系统太复杂。如果操作系统定义了5个不同的文件结构，则它需要包含代码，以便支持这些文件结构。此外，可能需要将每个文件定义为操作系统支持的文件类型之一。如果新应用程序需要按操作系统不支持的方式来组织信息，则可能导致严重的问题。

内部文件结构

逻辑记录是应用程序定义的数据单位，大小和内容由应用程序决定。(假设你有一本笔记本，用来记录每天的购物单。笔记本：就像磁盘，用来存储数据。笔记本的每一页：就像磁盘的“块”，是存储的基本单位。你写的每一行内容：比如“买苹果 3 个”、“买牛奶 1 瓶”，每一行就是一个“逻辑记录”。)
磁盘系统通常具有明确定义的块大小。所有磁盘 I/O 操作都以一个块为单位进行。因为磁盘是以块为单位操作的，而逻辑记录可能很小（比如 1 字节），所以为了提高效率，我们会把多个逻辑记录放在一起，组成一个块。比如，一个块有 512 字节，我们可以把 512 个字符（逻辑记录）打包到一个块里。

访问方式

文件存储信息。当使用时，必须访问这种信息，并将其读到计算机内存。

顺序访问

顺序访问是最简单的访问方法。文件信息按顺序加以处理。

直接访问

直接访问(相对访问)方法，文件由固定长度的逻辑记录组成，以允许程序按任意顺序进行快速读取和写入记录。

其他访问方法

其他访问方法可以建立在直接访问方法之上。这些访问通常涉及创建文件索引。为了在文件中查找记录，首先搜索索引，然后根据指针直接访问文件并且找到所需记录。这种结构允许仅仅通过少量I/O就能搜索巨大文件。
对于大文件，索引文件本身可能变得太大而无法保存在内存中。一种解决方法是为索引文件创建索引。

目录结构

一个磁盘可以划分为多个分区，包含文件系统的分区成为卷。假设你有一块硬盘，你将它分成了两个分区。第一个分区：格式化为 NTFS 文件系统，分配了驱动器号 C:。这个分区就是一个卷，我们通常称它为 C 盘。第二个分区：格式化为 NTFS 文件系统，分配了驱动器号 D:。这个分区也是一个卷，我们通常称它为 D 盘。

存储结构

计算机系统可能没有文件系统，也可能有多个文件系统，而且文件系统的类型可以不同。

目录概述

目录可视为符号表，可将文件名称转为目录条目。有如下操作：

• 搜索文件
• 创建文件
• 删除文件
• 遍历文件
• 重命名文件
• 遍历文件系统

单据目录

最简单的目录结构就是单机目录。

然而，当文件数量增加或系统有多个用户时，单机目录有重要的限制。因为所有文件位于同一目录中，它们必须具有唯一的名称。如果两个用户都命名数据文件为同一个名字，则违反唯一名称规则。不过，大多数文件系统支持长达255个字符的文件名。

两级目录

对于两级目录结构，每个用户都有自己的用户文件目录(UFD)，这种UFD具有类似的结构，但是只列出了单个用户的文件。当用户作业开始或用户登录时，搜索系统的主文件目录(MFD)。通过用户名或账户可索引MFD，每个条目指向该用户的UFD。

虽然两级目录结构解决了名称碰撞问题，但是它仍然有缺点。这种结构有效地将一个用户与另一个用户隔离。当用户需要完全独立时，隔离是个优点；然而当用户需要在某个任务上进行合作并且访问彼此的文件时，隔离却是个缺点。

树形目录

树是最常见的目录结构。

路径名可有两种形式：绝对路径名和相对路径名。绝对路径名从根开始，遵循一个路径到指定文件，并给出路径上的目录名。相对路径名从当前目录开始。

无环图目录

考虑两个程序员正在开展联合项目。与该项目相关的文件可以保存在一个子目录中，以区分两人的其他项目和文件。但是两个程序员都平等地负责项目，都希望该子目录在自己的目录中。这种情况下，公共子目录应该共享。一个共享的目录或文件可同时位于文件系统的两个(或多个)地方。

一个共享文件在多个目录中时，只有删除所有目录中的该文件才能彻底删除它。

通用图目录

文件系统安装

就像文件必须先打开才能使用一样，在访问文件系统之前，必须先安装文件系统。

文件共享

主要有三个问题：

• 允许多用户共享文件
• 将共享扩展到多个文件系统
• 共享文件的冲突操作

多用户

要实现共享和保护，系统必须维护更多的文件和目录属性。
所有者(或用户)：可以更改属性和授予访问权限
组：定义用户子集，允许用户加入组，从而获得组访问权限。
给定文件(或目录)的所有者ID和组ID，与其他文件属性一起存储。

远程文件系统

在分布式系统中，文件可通过网络共享。

• 通过ftp程序在机器之间手动传送文件。
• 通过分布式文件系统(DFS)，远程目录从本机上可直接访问。
• 通过万维网(WWW)，通过浏览器访问远程文件。

客户机-服务器模型

允许一台计算机从一台或多台远程计算机安装一个或多个文件系统。
服务器：包含文件的机器。
客户端：寻求访问文件的机器。
一个服务器可以为多个客户端提供服务。
服务器通常在卷或目录级别指定可用文件。识别客户更加困难。指定客户可以采用网络名称或其他标识符，例如IP地址，但是这些可以被欺骗或模仿。通过欺骗，未经授权的客户机可以允许访问服务器。
针对UNIX及其网络文件系统(NFS)，认证缺省通过客户网络信息来进行。客户端和服务器端的用户ID必须匹配，才能有权限访问文件。服务器必须相信客户端能提供正确的ID。

分布式信息系统

分布式信息系统也称为分布式命名服务。域名系统(DNS)为整个互联网提供主机名到网络地址的转换。

故障模式

故障模式是指系统在运行过程中可能出现的各种异常情况或错误状态。这些故障模式可以分为硬件故障和软件故障两大类。了解这些故障模式有助于开发人员设计更健壮的系统，同时也有助于系统管理员更好地进行故障排查和恢复。

一致性语义

一致性语义是指系统在多个操作或多个副本之间保持数据一致性的规则和约定。比如你们团队在用一个在线文档写报告，一致性语义要求无论谁在文档里做了修改，其他人都能看到最新的内容，不会出现你改了第一段，但别人看到的还是旧的第一段这种情况。

保护

当信息存储到计算机系统中时，需要保护它的安全，以便避免物理损坏(可靠性的问题)和非法访问(保护问题)。可靠性通常通过文件的重复副本来提供。许多计算机系统都有系统程序，自动地定期地把可能意外损坏的文件系统复制到磁带。

访问类型

访问的允许或拒绝取决于多个因素，其中之一就是请求访问的类型。

• 读
• 写
• 执行
• 附加
• 删除
• 列表

访问控制

保护问题的最常见方法是根据用户身份控制访问。为每个文件和目录关联一个访问控制列表，以指定每个用户的名称及其允许的访问类型。

其他保护方式

为每个文件加上一个密码。

文件系统实现

文件系统结构

磁盘的优势：

• 磁盘可以原地重写；可以从磁盘上读取一块，修改该块，并写回原位置。
• 磁盘可以直接访问它包含信息的任何块。因此，可以简单按顺序或随机访问文件；并且从一个文件切换到另一个文件只需移动读写磁头，并且等待磁盘旋转。

• 逻辑文件系统：管理元数据信息。元数据包括文件系统的所有结构，而不包括实际数据。逻辑文件系统管理目录结构，以便根据给定文件名称为文件组织模块提供所需信息。通过文件控制块(FCB，包含有关文件信息，包括所有者，权限，文件内容的位置等)来为维护文件结构。
• 文件组织模块：知道文件及其逻辑块以及物理块。可将逻辑块地址转成物理块地址。还包括可用空间管理器，以跟踪未分配的块。
• 基本文件系统：只需向适当设备驱动程序发送通用命令，以读取磁盘的物理块。还管理内存缓冲块和保存各种文件系统、目录和数据块的缓存。
• I/O控制：包括设备驱动程序和中断处理程序，以在主内存和磁盘系统之间传输信息。

文件系统实现

磁盘结构

• 引导控制块
• 分区控制块
• 目录结构

内存结构