2022SPR《操作系统》笔记

由
内容纲要

第一章 引论

操作系统的功能和基本类型

操作系统的功能是：为用户提供一个更简单清晰的计算机模型，管理计算机系统的其他设备。即在相互竞争资源的程序之间，提供对处理器、存储器、IO设备等资源有序的控制、管理与分配。

操作系统是硬件和用户之间的接口，为计算机用户提供一个方便、高效地在计算机硬件上执行程序的环境。
操作系统管理硬件和软件资源。按需要分配计算机的独立资源，以解决所给的问题。分配过程应尽可能公平和有效。
操作系统作为一个控制程序的两个主要功能:

  • 监督用户程序的执行，防止错误和不当使用计算机
  • 管理I/O设备的操作和控制。

对资源：

  • 资源分配
  • 资源保护
  • 资源回收
  • 虚拟

对服务：

  • 抽象
  • 简化
  • 方便
  • 标准化

OS使计算机使用更加简单，功能更强。

操作系统的基本类型：

  • 大型机操作系统
  • 服务器操作系统
  • 多处理器操作系统
  • 个人计算机操作系统
  • 掌上计算机操作系统
  • 嵌入式操作系统
  • 传感器节点操作系统
  • 实时操作系统
  • 智能卡操作系统

操作系统的基本特征

并发：计算机系统中同时存在多个可运行的程序，需要OS管理和调度。
并行：计算机系统同时运行多个程序。
共享：同时访问或互斥共享。
虚拟：利用多道程序设计技术，让每一个用户都觉得有一个计算机专门为他服务。
异步：程序的执行不是一步到底的，而是走走停停，向前推进的速度不可预知，但只要运行环境相同，OS要保证程序运行的结果也相同。

中断和调用

中断：外部硬件设备所产生的信号，以通知操作系统处理事件。
调用：用户程序请求操作系统提供服务。

第二章 进程与线程

进程的特征

进程: 一个运行中的程序，也指一个程序的执行过程。

多道程序环境下，程序不能反映其运行的过程。

  • 多个用户可以运行同一个程序
  • 一个用户可以运行同一个程序的多个实例

进程三要素：程序、数据和进程控制块(PCB)

一个程序可以有多个进程实例，比如一个Excel程序可以同时处理两个表。

可以把程序理解为类，进程是由程序创建的实例对象。

进程管理的系统调用

pid = fork()
pid = waitpid(pid, &statloc, options)
s = execve(name, argv, encironp)
exit(status)

# 创建子进程，返回pid
# 子进程结束后，父进程继续执行
# 替换核心映像
# 退出

一个父进程可以创建它的子进程，子进程也可以创建自己的子进程。在Windows中没有进程家族概念。

进程的状态

  • 运行态（Running，占有CPU）
  • 阻塞态（Blocked，因为I/O操作）
  • 就绪态（Ready，不占有CPU）
  • 其他状态：挂起，终止

进程的并发

并发：计算机系统中同时存在多个可运行的程序，需要OS管理和调度。
并行：计算机系统同时运行多个程序。

进程的内容

  • 进程状态：就绪、运行、阻塞；
  • 程序指针；
  • 寄存器信息；
  • 调度信息：进程优先级，进程指针等；
  • 存储管理信息：基址/限长等信息；
  • 账户信息：进程ID、进程运行时间、用户ID；
  • I/O状态信息；

进程控制块（PCB）

上下文切换

具体包括:
– 保存老进程的相关状态信息到其PCB中;
– 调入新进程的PCB恢复现场;
– 刷新相应的缓存;

上下文切换的开销很大，且需要硬件支持。

线程

线程是进程中的一个顺序执行流。
线程可以独立调度，每个线程需要一个TCB。

#include ''csapp.h'' 
void *thread1(void *vargp); 
void *thread2(void *vargp); 

// 主线程
int main() {
    phtread_t tid1, tid2; 

    // 线程1，2
    Pthread_create(&tid1, NULL, thread1, NULL);
    Pthread_create(&tid2, NULL, thread2, NULL);
    Pthread_join(tid1, NULL);
    Pthread_join(tid2, NULL);
    exit(0);
}

上述代码共三个线程。

线程模型

在不支持线程的系统中，进程是资源分配和调度的基本单位；而在支持线程的系统中，进程是资源分配的基本单位，线程是调度的独立单位，进程中的线程共享该进程的所有资源。

共享信息（存于进程的PCB中）
– 处理器信息: 进程执行时间等
– 内存: 进程地址空间、页表等
– 已分配的I/O设备和打开的文件（已获得的软硬件资源）

私有状态(程序执行的现场信息，存于线程的TCB中）
– 线程状态(就绪、运行和阻塞)
– 寄存器
– 程序指针
– 执行堆栈（存放线程中的局部变量、参数以及返回地址等）

每个线程可以独立调度、执行。并且有一个私有的堆栈。

线程与函数的区别

多线程实例：

#include ''csapp.h'' 
void *thread1(void *vargp); 
void *thread2(void *vargp); 
int buffer[];
int main() {
FILE *fp = fopen("D:\\demo.txt","rb+");
phtread_t tid1, tid2; 
Pthread_create(&tid1, NULL, thread1, NULL);
Pthread_create(&tid2, NULL, thread2, NULL);
Pthread_join(tid1, NULL);
Pthread_join(tid2, NULL);
exit(0); }

同样的单线程实例：

int main() {
thread1(); 
thread2();
}

阻塞型系统调用

– 通常与I/O相关: read(), fread(), getc(), write()
– 系统调用完成前不返回调用进程/线程
– 进程/线程进入阻塞状态等待
– 当I/O完成, 进程/线程变成就绪状态，等待调度。
– 简单
– 现实生活例子: 去听讲座

非阻塞型系统调用

– 异步 I/O
– 复杂
– I/O初始化完成后马上返回调用进程/线程, 进程/线程继续运行。
– I/O 操作一旦完成, 通过中断通知调用进程/线程。
– 现实生活例子: 找工作

用户空间和内核空间的线程实现

用户空间的线程实现中，操作系统是不知道线程的存在的。线程包存放在用户层。
内核空间的线程实现中，线程包存放在内核层，操作系统知道线程的存在。

用户级线程之间切换开销小，而且可以在不支持线程的操作系
统实现；但是当一个用户级线程因为I/O阻塞时, 整个进程都会
阻塞。
内核级线程的实现是基于操作系统的，总体性能更加优越；但
内核级线程的上下文切换开销相对较大。

调度程序激活机制

模拟内核线程的功能，获得用户级线程的性能；避免在用户空间和内核空间之间的不必要切换。

内核给每个进程安排一定数量的虚拟处理器，让运行时系统分配处理器给线程。

问题：上行调用。

弹出式线程

进程间通信

进程通信：进程间相互传送信息，实现信息/数据交换。
进程互斥与同步：对临界资源（独享资源）的互斥访问；合作进程间的速度协调。
解决方案同样对线程适用。

临界区

Process {
    while (true) {
        Do other work;
        进入区(Enter Critical Section)
        Access shared variables; // Critical Section;
        (Access on critical I/O devices;)
        退出区(Leave Critical Section)
        Do other work ;
    }
}

进入区：如果没有其他进程访问临界资源，则进入临界区；否则等待。

退出区：与进入区对应，释放资源。

临界区访问控制要求

互斥条件：当有一个进程在临界区时，其他进程不能同时进入。
空则让进：如果没有进程在访问临界资源，那么有进程请求访问该临界资源的要求应该满足。
有限等待：如果有进程在访问临界资源，则其他进程必须等待，但应该是有限的等待。
没有假设：不应对进程的推进顺序、速度，以及CPU的速度和数量做任何假设。

以忙等方式实现互斥

占用CPU，循环直到可以访问临界资源。
性能一般，但是实现简单。

关中断

一个进程进入临界区后关闭所有中断，在离开临界区前再重新开中断。
关中断后，CPU就不能响应时钟以及其他中断请求，因而就不会有进程切换。

锁变量

设置lock变量，为0则说明没有进程访问；为1则说明有别的进程访问。

// EnterCriticalSection
While (lock);
lock = 1;
access shared variable;
// LeaveCriticalSection
Lock = 0;

锁变量方案无效。它假设了进程执行的顺序，假设了检测lock和设置lock的步骤是有先后顺序的。

严格轮换法

如果turn为0，进入a的临界区；如果turn为1，进入b的临界区。

使用flags
int flag[2]= {false, false};
Thread Me;
{
    while (true)
    {   
        flag[my_thread_id] = true;
        while (flag[other_thread_id] ) { };
        Access shared variables;
        flag[my_thread_id] = false;
        Do other work
    }
}

假设了检测flag和设置flag之间不会被中断。

Peterson解决方案

TSL指令

在锁变量的基础上，将检测和设置变为原子操作。

睡眠与唤醒

忙等方案浪费了CPU时间。并且会造成优先级反转，即在以优先级为实现方案的系统中，如果低优先级进程在访问临界区资源，但是高优先级进程不阻塞，则低优先级任务无法调度，无法离开临界区的情况。这会导致无论高低优先级，任务都无法继续进行的情形，称为永久等待。

解决方案：睡眠与唤醒。在进程无法进入临界区时阻塞，而不是忙等。

信号量

信号量是用来描述资源的分配情况的数据结构，其中两个成员变量表示可用的资源数量和指向该资源等待队列的指针。

定义如下：

typedef struct semaphore{
    int value;  // 可用资源数量
    PCB *p;     // 等待队列的指针
};

struct semaphore s;
void P(s){ // 申请资源
    s.value = s.value - 1; // 可用资源减一
    if(s.value < 0) // 如果无可用资源，阻塞进程
        block(s.p);
}

void V(s){ // 释放资源
    s.value = s.value + 1; // 可用资源加一
    if(s.value <= 0) // value小于0代表有进程在等待，此时有了可用资源，就要唤醒等待的队列
        wakeup(s.p);
}

进程互斥是由于各进程共享、竞争同一临界资源，从而造成这些进程之间的一种间接制约，这些进程之间并没有逻辑联系。

进程同步是相互合作的进程之间，为了保证结果的正确性，必须达成的速度上的协调，是有逻辑联系的直接制约。

进程互斥问题中，各个进程需要的是同一种资源；而进程同步问题，相互合作的两个进程需要的资源是不同的，但一个进程所需的资源由对方进程产生。

经典的IPC问题

生产者-消费者问题

中间的缓冲区可以存储数据。如果缓冲区满了，生产者部分就要sleep，直到缓冲区有空位（count == N-1）；如果缓冲区为空，消费者部分就要sleep，直到缓冲区有数据（count == 1）。

解决方案：

struct semaphore s1,s2,empty,full=1,1,n,0
message buffer[n]; int in,out=0,0;
cobegin void produceri( i=1,2,…k){ 
    message x;
    while(TRUE){
        x=produce_message( );
        P(empty);
        P(s1);
        buffer[in]=x; in=(in+1) mod n;
        V(s1);
        V(full);
    }
}
void consumerj( j=1,2,…m){
    message y;
    while(TRUE){
        P(full);
        P(s2);
        y=buffer[out]; 
        out=(out+1) mod n;
        V(s2);
        V(empty);
        consume_message(y);
    }
}
coend

互斥同步混合问题：多个生产者对应多个消费者，并且共享多个缓冲区。

哲学家就餐问题

吃面要两把叉子，但是每次只能拿一把叉子。如上图，如果有5个哲学家想要同时吃面，就会出现死锁。

struct semaphore forks[5]=(1, 1, 1, 1, 1);
struct semaphore count=4;
void phi(i)( i=0, 1, 2, 3, 4 )
int i;
{ while(TRUE){
think;
P(count);
P(forks[i]);
P(forks[i+1 mod 5]);
eat;
V(forks[i]);
V(forks[i+1 mod 5]);
V(count);}
}

进程通信方式

共享存储区系统

管道通信

消息传递系统

void send(receiver,a){
    getbuf(a.size, i);
    i.sender=a.sender;
    i.size=a.size;
    i.text=a.text;
    i.next=0;
    getid(pcbset, receiver, j);
    P(j.mutex);
    insert(j.mq,i);
    V(j.mutex);
    V(j.sm);
}

void receive(b){ 
    P(j.sm);
    P(j.mutex);
    remove(j.mq, i);
    V(j.mutex);
    b.sender= i.sender;
    b.size= i.size;
    b.text= i.text;
    releasebuf(i);
}

调度

决定哪个进程线程可以占有资源。
调度发生在：

  • 一个运行的进程完成时
  • 一个运行的进程阻塞时
  • 时钟中断发生时
  • 一个新进程进入系统时
  • 一个进程I/O操作完成时

非抢占式调度：运行的进程一直占有CPU，直到自愿释放，即进程完成时和进程阻塞时。

抢占式调度：运行的进程可以基于某种原则（时间片或者优先权）被强制中断执行，系统进而将CPU分配给其他进程。

批处理系统调度算法

FCFS先来先服务

性能标准：平均等待时间。

FCFS是一种非抢占式调度，没有最优平均等待时间。并且对短作业不公平，且不能并行使用各种资源。

比如计算密集型进程需要的等待时间远大于I/O密集型进程，但一般来说，I/O密集型进程数量远大于计算密集型进程。如果计算密集型进程先到，数量多时间短的I/O进程就会长时间阻塞。

护航效应：CPU和IO设备利用率低。
I/O密集型作业被调度后很快阻塞进行I/O操作。然后计算密集型作业被调度运行，一直到完成。
I/O操作完成时，被唤醒进入就绪队列，需要等待计算密集型作业完成，此时I/O设备是空闲的。
当计算密集型作业完成后，I/O作业抢夺I/O设备，再次阻塞，此时CPU空闲。

SJF最短作业优先

两种调度类型：抢占式&非抢占式。

非抢占式实例：

SJF并不总是最优的，因为进程的到达时间可能不一样。

抢占式SJF的应用前提是：作业的运行时间要预先可知。
思路是：优先调度剩余时间最短的进程。

抢占式SJF实例：

SJF会导致饥饿现象，在某些情况下，长作业等待时间会很长。
解决这一现象的方法是利用相应比，相应比高的进程优先。
R_p= 1 + \frac{t_w}{t_e}

交互式系统调度算法

通常是抢占式调度，性能标准是最短的响应时间和最佳的用户体验。

RR时间片轮转

就绪队列的进程轮流执行，一次执行一个时间片。
问题：

  • 忽略优先级
  • 上下文切换开销很大

算法效率依赖于时间片的选择，时间片过大则退化为FCFS算法，且系统响应时间不佳；时间片太小则会产生过多的上下文切换，CPU利用率低。

选择原则: 保证70-80%的作业在一个时间片内阻塞或者完成。

优先级调度

每次调度优先级最高的一个进程，相同优先级的进程采用FCFS方式调度。

优先级调度不能确保最佳的AWT，且可能会产生饥饿现象，没有给IO密集型进程更多的关注。

改进方法：

  • 每过一个时钟周期，增加等待CPU的进程的优先级，或者减小
    当前运行进程的优先级。
  • 每个进程指定一个允许运行的最大时间片。更加关注IO密集型进程，进程的优先级可以设置为\frac{1}{f}，其中f为上一个时间片该进程用掉的时间占时间片的比例。
多级队列调度

有多级就绪队列，每个就绪队列中的进程优先级不同。
每个进程根据其优先级进入不同就绪队列，进程每次运行
一个时间片。
优先调度优先级较高就绪队列中的进程，也可以根据其优先级的高低，分配给这些就绪队列不同的CPU运行时间比例。

多级反馈队列

与多级队列同样有多个优先级队列，每个优先级对应的对列的时间片长度不同。最高的优先级拥有最短的时间片，随着优先级的下降，时间片按照2倍顺次延长。
每个任务都先进入最高优先级队列，如果在一个时间片轮转中没有完成，则进入下一级优先级的队列。
运行时，先运行最高优先级队列的一个时间片轮转，然后不管此队列中的任务是否完成，都要运行下一个优先级的队列中的任务一个时间片。
优先级最低的队列中采取先入先出调度算法。

这么做是为了将IO操作集中在最高优先级，批处理作业集中在最低优先级。因此对每种类型的作业都有很好的调度性能。

第三章 存储管理

基本概念

地址重定位

分为静态重定位和动态重定位。
静态重定位的地址变换需要在程序运行前完成。在程序加载时完成程序中所有地址项的变换，因此不利于实现程序在内存中移动。
动态重定位的地址变换就在程序运行时进行，在程序加载不需要对程序中的地址项进行地址变换。因此可以很方便地实现程序在内存中的移动。

存储管理的目的和功能

存储分配，地址变换，“扩充”主存容量，存储保护。

存储管理方式

单一连续区存储管理

系统只能同时运行一道程序。

固定式分区存储管理

系统固定多个大小不同的分区，分区的大小和地址在系统启动后无法改变。将任务分配到比任务大的分区中即可实现管理。

但是内存分配存在“内零头”，即分区内存减去任务内存这块零头内存区域。因此内存利用率低。

可变式分区存储管理

按照每个作业的需要划分系统中合适的空闲区。但是在作业完成，系统进行多次内存的分配和回收后，内存就会形成分配区和未分配区相间的状态。这会产生“外零头”，即较小的，不能分配给任务的未分配区。

最佳适应算法：每次挑选能够分配的区域中最小的那个进行分配。缺陷在于每次分配几乎都会产生外零头。
最坏适应算法：每次挑选能够分配的区域中最大的那个进行分配。缺陷在于多次使用后，内存需求较大的作业无法被满足。
首次适应算法：每次从上至下顺次查找能够分配的区域。
循环首次适应算法：分配完成后查找范围不再回到起点，而是接着上次分配的地址继续向下查找，直到查找到地址终点。

解决外零头的方法：

  • 把程序分成好几部分装入不同分区
  • 将零头拼成一个大空闲区

虚拟存储系统

虚拟存储只需要把程序部分装入内存即可运行程序，程序需要的其他资源存放在外存对换区中，在程序需要的时候请求调入。
虚拟存储器的容量=内存容量+外存容量，同时受限于CPU寻址能力。（CPU地址长度）

局部性理论

空间局部性：大部分程序按照顺序执行，因此使用的内存附近的内存也大概率会被使用。
时间局部性：指若一条指令被执行，则在不久的将来，它可能再被执行。

分页式存储管理

分页式存储管理是一种离散式存储管理方法，作业不需要申请连续的内存，而是将程序按照某个大小（一般为4KB）分成若干块，利用页表结构，将程序的逻辑地址映射到物理地址中，从而实现程序在物理内存中的离散化。

若加入快表机制，则快表可以缓存最近使用过的页表项目，从而跳过查页表的步骤，直接经由快表访问物理内存。

请求分页式存储管理

适用于虚拟存储管理模式的分页系统称为请求分页式存储管理。在此模式下，只要调入进程的一部分页面，进程就可以运行，而其他的页面是在需要时请求操作系统从外存调入。

请求分页存储管理的页面置换算法

FIFO先入先出页面置换算法：字面意思。
最佳置换算法：适用于离线情况，已知未来页面的置换顺序，并且每次挑选目前主存中在最远将来会被使用的页面（极限情况是永远不被使用）进行替换。这种算法是最优的，但是是不实际的。一般用于比较其他算法的性能。
LRU最近最久未用页面置换算法：在先入先出置换的基础上，每次将最近使用的页面放到队列末尾。这样每次被淘汰的就是最近最久未用页面。

分页系统页面大小的选择:

  • 页面越小，内存利用率越高，但管理开销也越大。
  • 一般页面大小选择为4KB(或1KB、2KB)

分页系统的优点:

  • 能较好地支持虚拟存储技术。
  • 采用离散式的存储管理方式，能充分地利用内存空间。

分页系统的缺点：

  • 产生内零头。
  • 分页时完全是机械地划分，页面跟程序的逻辑结构没有直接关联，不便于程序和数据的共享。

分段式存储管理

按照程序自然逻辑结构分段。

分段式存储管理的优缺点：

  • 分段是根据程序的自然逻辑结构形成的，有利于程序和数据的共享。
  • 产生外零头。
  • 分段一般比较大，内存利用率不如分页。

段页式存储管理

在分段的基础上，对每一段分页。

段页式系统的优缺点：

  • 兼具分页系统和分段系统的优点。按程序的逻辑结构分段，能很好地支持程序以及数据的共享；段内分页，页面作为独立分配单位，具有分页系统的高内存利用率。
  • 没有外零头，但一个作业的每个分段的最后一个页面还是会产生内零头。
  • 系统管理开销较大。

使用位示图、链表管理存储空间

位示图是一串01数组，0代表当前存储单元未使用，1代表已使用。
链表管理：

转换检测缓冲区（快表TLB）

先从快表中查找地址映射，然后查询页表。以加速访问效率。
快表中的项目需要更换。

多级页表

一级页表在高位系统中占用内存大，因此不能全部放入主存，需要用二级（多级）页表管理一级（下一级）页表，以将低级的页表全部放入外存对换区。

因为每级页表都是以单独的页表保存在内存中，所以在二级页表分页系统中，对一个内存单元的访问需要3次。
仍然可采用快表来缓存“活动”的页表表项，以此提升多级页表的性能。

倒排页表

页表的排列顺序代表了实际的物理块页号。

用小页表管理大空间，但是搜索开销很大。
可以使用hash优化，将hash页号作为索引，使用顺序表、链表混合的存储方法管理表。

页面置换算法

缺页时如果没有空闲块，则要选择一个合适的页面置换。
已修改过的页面在被置换前应先保存到外存，而没有修改过的
页面只是简单地覆盖。
最好不要选择经常使用的页面，如果这样的话，刚被置换的页面有可能马上被访问，又要从外存调回来。

最佳置换算法

置换以后不再访问的页面或者离下次访问最远的页面。

NRU最近未用页面置换算法

每个页面都有访问位(Reference bit)和修改位(Modified bit)，一个页面被访问时，其访问位被置为1；一个页面被修改后其修改位被置为1。页面的访问位定期地(如每隔20ms)被清为0，所以如果一个页面的访问位为0，则表示该页面在最近一个时钟周期没有被访问过。

根据访问位和修改位的状态，页面被分为四类：

  • 第0类：未引用，未修改(R=0，M=0)
  • 第1类：未引用，有修改(R=0，M=1)
  • 第2类：有引用，未修改(R=1，M=0)
  • 第3类：有引用，有修改(R=1，M=1)
    NRU随机地从类编号最小的非空类中挑选一个页面淘汰之。
时钟页面置换算法


循环队列，每次碰到R位为0的就将其置换。如果碰到R为1的，R变为0并且搜索下一个。

FIFO先进先出页面置换算法

字面意思。
但是会出现Belady异常现象，分配的物理块多的情况下，缺页率反而提升。因为这是个不讲道理的算法。

第二次机会页面置换算法


按照FIFO排列页面，当要淘汰的页面的R为1时，将R设为0，并且将它移到队首。

LRU最近最久未用页面置换算法

保持一个页面链表，最近访问过的页面在链表的最后端，最久没有访问的页面在链表的最前端。每次页面访问都要重新更新页面链表。

每执行一条指令后计数器的值增1，故计数器的值为程序从开始运行以来已经执行的指令数。
当一个页面被引用时，当前计数器的值被保存在页面的页表项中。每次置换页表项中的计数值最小的页面。

NFU最不常用页面置换算法

每个页面有一个关联的软件计数器。
每个时钟中断时，操作系统扫描每个页面，将页面的R位的值累加于对应的计数器，所以计数器值最大的页面表示访问次数最多的页面。
置换计数器值最小的页面。

根据R位在某时钟期间的状态，在计数器最左边加入1或者0。计数器的其他位右移1位。

总结

第四章 文件系统

文件的逻辑结构

无结构的流文件，有结构的记录文件。

文件的物理结构

文件的物理结构有连续和离散两种存储方式。
常见的文件物理结构包括：

  • 连续文件
  • 链接文件
  • 索引文件
  • Unix文件

连续文件

支持随机存取，存取速度最快。但是不能支持文件的动态增长，不能充分利用磁盘空间。

链接文件

链接文件将文件按照物理块分开存放，每一个物理块都有编号和指针，指针指向下一个编号的物理块。
因为采用链式存储，所以具有链表的优点和缺点。

文件分配表

对于链接文件，引入文件分配表，可以更快地找到想要的物理块。

索引文件

在物理块内加入单级索引文件，将所有指向其他盘块的指针加入索引块。
假如物理块大小为4KB，索引指针为4B，则一个物理块能管理的最大文件为4MB。
利用索引读取文件需要的磁盘IO操作数为：1+1=2。

多级索引文件

单级索引文件能管理的文件太小，如果再加入1级索引，能管理的最大文件为4GB。读取文件需要的磁盘IO操作数为：2+1=3。

UNIX文件

UNIX文件包含10个直接寻址指针域，也可以引入多级索引。

文件的存取方法

共享文件

链接

硬链接

指令：ln src target
以不通的文件路径名共享同一个文件副本，在同一个分区内才可以创建。
删除文件的多个路径链接中的一个，不影响其他路径访问文件。文件本体只占用一次存储区。

软链接

指令：ln -s src target
快捷方式，可以对目录、不存在的文件名链接。

磁盘空间管理

磁盘的空间利用率跟盘块（物理块）大小的关系。
物理块过大会导致磁盘利用率骤降，原因是文件占不满物理块。

两种管理方案的开销在空闲块数量:总块数=1:32的时候一样。

内存中全满的空闲块表存入一半到磁盘中，可以避免空闲块表反复在内外存之间调换，减少系统开销。

空闲块目录表登记连续的空闲块信息。

空闲块链将100个空闲块作为一组，在组头加入个数、下一个空闲块组的指针，形成102个域。后100个为空闲块指针域。
最后一组不满100个空闲块的组作为专用块，放入内存中管理。

可靠性技术

文件系统备份

备份只需要备份部分文件，其中临时文件、设备文件等不需要或者不能备份。

物理备份比较简单、快速。但是不能对指定的目录进行转储和恢复，不能根据需要增量转储与恢复个别文件。

逻辑转储也需要备份已修改文件或目录的路径上的所有目录，这是基于以下两个方面的原因：
–可能需要恢复文件到相应的目录中。
–可能需要将被备份的文件或者目录恢复到另一个计算机的全新文件系统中。

文件一致性

– 如果在写文件时发生系统崩溃，可能会出现文件一致性问题。
– 问题主要出现于：文件目录块、 i-节点(i-nodes)块、索引块、包含空闲块表的盘块等。
– 文件一致性检测程序：fsck // scandisk
– 可以进行两种一致性检测：

    • 盘块级（块分配与否的一致性）
    • 文件级（文件链接数与实际访问路径数的一致性）

链接数大于路径数，路径全部删除，文件仍然占用内存。
链接数小于路径数，路径全部删除，文件直接释放，导致剩余的链接无法访问文件。

处理方法

丢失块：在空闲块登记块号。
矛盾块：空闲块置零。
空闲块重复：空闲块置一，在某个空闲块表中去掉这个空闲块即可。
数据块重复：数据损坏已经造成，将其中一个文件块分配到别的空闲块上可以缓解。

空闲块表损坏、文件删除都可恢复。
空闲块表的损坏，遍历所有文件，然后重构表。
文件删除的恢复，找到这个文件之前所在的数据块，数据没被覆盖前不会消失，因此可以恢复。
文件粉碎机即，不仅登记空闲块，还要将块的数据清零。

文件系统性能

高速缓存

在内存中开辟一块缓冲区，存放经常访问的数据盘块。
对于高速缓存中的盘块，需要采取LRU等方式置换。

– 盘块可根据其作用进行分类，如i节点(i-nodes)块、间接寻址块、索引块、文件目录块、全满数据块、部分满数据块等。
– 对于某些块，如i节点块(i-nodes)极少可能在短时间内被引用两次，而满数据块再次被访问的可能性也相对较少，可以考虑将它们放在LRU前端。
– 对于关系到文件系统一致性的关键块，一旦被修改，则需要立即更新到磁盘。

fclose的作用是，在退出文件后保存文件数据盘块到磁盘。
fopen的作用是，初始化数据盘块控制信息。

块提前读

仅适用于顺序访问。
在对应块在被访问前预先调入高速缓存，以此增加高速缓存的块命中率。可以通过跟踪每个打开文件的存取方式来确定是否需要块提前读。

减少磁臂运动

把有可能顺序存取的块放在一起，最好在同一个柱面上，从而减少磁臂移动的距离。
减少i节点(i-nodes)与其对应文件数据块之间的平均距离:

  • 将i节点(i-nodes)区放在磁盘的中间而不是开始处，这样i节点(i-nodes)与其对应文件数据块之间的平均距离减为原来的一半。
  • 将磁盘分成多个柱面组，每个柱面组都有自己的i节点(i-nodes)区、数据块和空闲块表。

第五章 设备管理

设备控制器

典型的I/O设备包括机械部分和电子部分，其中的电子部分就是设备控制器(或者叫适配器)，而机械部分就是设备本身。

磁盘控制器一般进行数据转换、检错纠错、数据预读缓存等工作。
设备控制器一般有寄存器用于数据的输入、输出和设备控制。

块设备、字符设备

块设备：以数据块为单位传送数据(如磁盘)
块设备系统调用: read, write, seek

字符设备：以字节为单位传送数据(如键盘、打印机等)
字符设备系统调用: get, put

IO操作方式

程序IO方式

又称为查询方式、忙等方式。
首先将输入的字符串存储在用户空间，然后将用户空间的字符串数据读入内核空间，内核向打印机发送指令，逐字打印字符。

cp_from_user(buffer, p, count);
for(i=0; i<count; i++){
    while(*priter_status_reg != READY);
    *printer_data_reg = p[i];
}

中断IO方式

引入中断控制器。给予每个设备对应的中断控制服务。

  • 首先设备就绪，对中断控制器发出请求。
  • 中断控制器令CPU当前进程进入中断。
  • 进程阻塞后可以调度别的进程继续占用CPU。
  • 中断控制器控制服务完成后，CPU结束中断，此时可以再次调度之前阻塞的进程。

中断IO方式采用了阻塞机制，取代忙等。使得CPU的效率提升。

使用DMA控制器

CPU设置好DMA控制器的参数，包括地址，字符串长度等信息。之后的IO操作完全交给DMA控制器完成，此时CPU可以处理别的任务。
在DMA控制器结束任务后，向CPU发送一个中断请求。

Spooling技术

脱机输入输出技术使得主机仅作为数据传输的工具，而不需要处理输入设备和输出设备的请求。
通过外部输入机，将数据从输入设备输入到输入井。这样主机的读取任务就是从输入井中读取数据，速度较快。
通过外部输出机，将数据从输出井读出并输出到输出设备。这样主机的输出任务就是将数据输出至输出井，速度较快。

Spooling技术则在没有外部机器的情况下，通过构建输入进程SPi和输出进程SPo负责与数据井交换数据。

它的实现思想是：
利用中央处理器和通道并行工作的能力，在多任务系统中分别以一个输入进程和一个输出进程代替脱机技术中的输入外围机和输出外围机。

这样用一台机器完成脱机外围设备操作技术中三台机器的工作。

SPOOLing系统在磁盘中划分出专门称为“井”的区域，它分为输入井和输出井。

输入进程把作业流中作业信息预输入到输入井保存，作业在执行时只要通过井管理程序从输入井中获取数据，而不去启动低速的外围设备。

作业执行时产生的结果也不直接输出到低速外设上，而是先通过井管理程序先输出到输出井，由输出进程将输出井中的数据缓输出到低速设备上。

磁盘概述

磁盘调度算法

寻道时间：T=m*n+s
旋转延迟时间：T=\frac{1}{2r}
数据传送时间：T=\frac{b}{rN}
其中n为磁头移动过的磁道数量，r为转速，N为每个磁道的数据字节数，b为要传输的数据字节数。

其中延时主要体现在寻道时间。

移臂调度

FCFS移臂调度算法

计算线段长之和。

SSTF最短寻道优先

SCAN电梯调度

磁臂粘着现象：如果一直存在在磁臂移动方向上的磁道号，则反方向的磁道难以被访问。

CSCAN循环扫描

但是如果存在很多给一样磁道号的调度，则其他“异类”磁道就很难被访问。
因此改进方法为N-Step-SCAN，将磁道序列分为N个1组，每次通过CSCAN完成1组，保证异类也能被访问。

FSCAN则采用前后台的方式，当前前台的所有访问序列在调度时，后续增加的访问序列放在后台，直到前台序列调度完毕，后台的序列不再增加，放到前台。

旋转调度

旋转调度的目标为：同一个柱面上的各个IO请求。
要特别关注那些不同磁道的相同扇区号上的访问请求。

电源管理

对CPU、内存和 I/O设备设置多级能耗状态：

  • 睡眠
  • 休眠
  • 关闭
    空闲一个设定时间后，切换到低一级的能耗状态，直到使用唤醒。

显示器是计算机中的最大电源能耗部件。
一段时间没有操作后，关闭显示器。或者分区域加背光。把屏幕分成若干个区域，只“点亮”程序窗口所在的区域。

硬盘要消耗相当一部分电能。
一段时间没有存取操作后，降低磁盘的旋转速度。 一旦需要，再“加速”。
内存的缓存可以节约能耗，如果需要的盘块在缓存，则“空闲”的磁盘不需要再次启动。
另一种可能是“告知”各应用程序当前磁盘的状态，这样程序就可以选择是否在当前存取磁盘。

CPU能耗和时钟频率与CPU的电压有关。
时钟频率与电压成正比，能耗与电压的平方成正比，因此可通过降低电压的方法降低CPU能耗。

对内存来说，有以下两个选择节省能耗：

  • 刷新高速缓存，并关闭。（睡眠）
  • 把主存的内容写入磁盘，关闭主存。（休眠）

当内存被关闭时（休眠）：

  • CPU 也被关闭，或者必须自ROM执行。
  • 当CPU被一个中断唤醒时，它可能需要自ROM执行，重新从磁盘加载内存。

如果无线接收器一直侦听是否有消息到达，这样耗能会很大。

  • 空闲一段时间后关闭接收器。
    使用基站缓存到达的消息，在系统缓冲区中存放要发出的消息。以此避免丢失信息。

关闭的时间点可以是空闲时间、用户、应用程序、系统决定。
打开的时间点同理。

第六章 死锁

死锁概念

如果一个进程在等待一个永远不会发生的事件，那么我们说这个进程进入了死锁状态。
死锁是一种永久等待或者无限等待，没有外力介入，这种等待不会结束。与饥饿不同。

死锁的必要条件

互斥：进程对临界资源的访问必须是互斥的。
请求保持：已经得到某些资源的进程继续请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性被抢占(剥夺)，它只能由占有它的进程释放。
环路等待：死锁发生时，系统中一定有由两个或者两个以上的进程组成的一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

解决死锁的基本方法

死锁预防

设置某些资源使用限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。

死锁避免

在资源动态分配过程中，用某种方法来防止系统进入不安全状态。

银行家算法

安全状态：即使各个进程同时提出各自的最大资源需求申请，系统也存在着一个资源分配序列(也叫安全序列)，按照此序列逐个为每个进程分配资源到其最大需求，各进程都能顺利推进直至完成，最后释放它们占有的资源，则我们称此时系统处于安全状态。如果系统处于安全状态，则一定不会出现死锁。
不安全状态: 找不到上述的安全序列。不安全状态可能会引起死锁。
银行家算法的实质是在资源动态分配中，避免系统进入不安全状态。

算法描述

def bank():
    # 当前请求大于最大需求，错误
    if Rei > Needi:
        Error(0)
    # 当前请求大于资源数，跳过后续步骤直接等待
    if Rei > Av:
        PiWait()
    # 否则，进行尝试性分配，修改Av项和进程的表项
    Av -= Rei
    Ali += Rei
    Needi -= Rei
    # 安全性测试
    if isSafe():
        # 安全则分配
        PiGet()
    else:
        # 不安全则等候
        PiWait()

def isSafe():
    Work = Av
    Finish = [F,F,...,F]
    findall(pi) that enable:
        if Finish(i)==F and Needi<=Work:
            Finish(i)=T,Work=Work+Ali
    if find(pj) that Finish(j) == F:
        return false
    return true

死锁检测

允许系统出现死锁，但能检测死锁的发生，也能确定与死锁相关的进程和资源。

死锁定理：系统中某个时刻S为死锁状态的充分必要条件是，S时刻系统的资源图是非完全可化简的。（注：不能化简的部分就是死锁相关的进程与资源）
利用该定理，可以通过某种算法来实现资源分配图的化简，并以此为依据检测系统中是否存在死锁以及哪些进程是死锁的。

死锁检测算法如化简图所示。

死锁恢复

在检测到死锁发生后，可通过撤销或挂起相关进程的方法，释放相应的资源，使系统回到非死锁状态。

  • 撤销所有死锁进程。
  • 每次撤销一个死锁进程，释放其资源。
  • 回滚进程到合适的检查点。

留下评论