文件系统和文件

一种持久性存储的系统抽象。

文件头

储存文件信息，保存文件属性，跟踪那一块储存块属于逻辑上文件结构的哪一个偏移。

需要哪些元数据来管理打开的文件

文件指针，文件打开计数，文件储存位置，访问权限

访问2-12字节的空间

读一个或者多个扇区，然后返回

访问方式

基于顺序一次读取，随机访问，基于内容查找的访问

资源分配图

有两个集合，一个是进程集合，另一个是资源集合，如果进程i需要某资源j的一部分，则连边$i\to j$, 如果一个资源j的一部分被分配给了进程i，则连边$j\to i$,
资源分配图出现了有向环是发生了死锁的必要不充分条件。因为边只表示一部分资源的分配，而不是全部资源

死锁的必要条件

互斥、持有并等待、无抢占、循环等待

信号量

就是一个整型加上一个队列

1
2
3
4

class Semaphore{
  int sem;
  WaitQueue q;
}

P操作

让信号量减少1，如果<0，把自己挂起

1
2
3
4
5
6
7
8

// 有原子性
P(){
  sem--;
  if(sem<0){
    Add this thread to q;
    block(t);
  }
}

n个进程互斥，留坑

禁用中断

进入临界区以后禁用中断，离开临界区以后开启中断
一但禁用了中断，整个系统都停止，可能导致饥饿，要是临界区有个死循环就完蛋，多个CPU无法解决问题。

线程管理

线程控制块 TCB

类似PCB

线程优点

一个进程可以同时存在多个线程，各个线程之间可以并发执行，各个线程之间可以恭喜那个地址空间和文件资源。

线程缺点

一个线程崩溃会导致所属进程的所有线程崩溃。

进程与线程

进程是资源分配单位，线程是CPU调度单位
进程拥有完整的资源平台，线程只独享其中的寄存器和栈
线程也有就绪阻塞执行三种状态和状态转化关系
线程能减少并发执行的时间和空间开销,线程创建终止块，切换快，共享资源可直接进行不依赖内核通信。

用户线程和内核线程

用户线程操作系统看不到，内核线程操作系统看得到

用户线程

线程的创建终止同步和调度都是线程库实现的。TCB在进程内部

用户线程的缺点

当一个线程阻塞以后，整个进程都阻塞了，因为操作系统看不到用户心线程，只能看到进程。

进程管理

进程的组成

代码+数据+程序计数器中的值，堆和栈，一组资源(打开的文件)

进程的特点

动态创建，并发或者并行，独立(执行的正确性不受其他进程影响)

进程控制块(PCB)

操作系统为每个进程维护了一个进程控制块，用来保存与该进程有关的各种状态信息。是进程存在的唯一标示。
包含了进程标识信息(父进程，用户标识)， 处理器状态信息保存区(用户可见寄存器，PC寄存器，程序状态字，栈指针)， 进程控制信息(调度和状态信息、进程键通讯信息，储存管理信息，进程所用资源信息，数据结构连接信息)
PCB的组织方式： 链表或者索引表

进程的创建的时机

系统初始化, 用户的请求，进程的请求

页面置换算法

当缺页中断发生的时候，需要做交换，我们需要尽量减少交换的次数。

最优页面置换算法

将等待下一层的访问时间最长的那个页面置换出去，这个算法不可能实现，但是可作为评价其他算法的标准

先进先出页面置换算法

维护一个队列，FIFO即可
性能很差，被调出的页面可能是要经常访问的页面

最近最久未使用算法 LRU

这个算法基于空间局部性
维护一个页面链表，将刚刚使用过的页面作为首节点，那么缺页中断的时候淘汰链表尾部即可