Hermethus
2021/03/27
0
来自 爱国神器华为
约 19986 字
原创
最近更新： 2021/11/03 23:51

操作系统学习笔记

系列目录

计算机通信网络学习笔记

操作系统学习笔记

数据库基础 - MySQL

分布式系统学习笔记

参考资料

CS-Notes-操作系统

王道考研-操作系统

1 操作系统概论

1.1 介绍

操作系统是最基本的系统软件，负责控制和管理计算机的软硬件资源，并合理地组织调度计算机的工作和资源，以提供给用户和其他软件方便的接口和环境。

功能

内存管理、进程管理、设备管理、文件管理、提供接口

接口

  • 命令接口：联机/交互式命令接口、脱机/批处理命令接口
  • 程序接口：系统调用，只能通过程序间接使用，又叫广义指令
  • GUI图形界面

操作系统特征

  • 并发：宏观上事件同时发生，微观上交替发生。
    • 并行：多个事件在同一时刻同时进行。
  • 共享：系统中的资源可供内存中多个并发进程使用。（互斥/同享）
  • 虚拟：讲一个物理实体映射成多个逻辑实体。（空分复用技术、时分复用技术）
  • 异步（不可预知性）：多道程序环境下，允许多个程序并发执行，但是由于资源有限，程序不是一贯到底的，而是走走停停，以不可预知的速度向前推进。

1.2 操作系统运行机制

处理器状态：用程序状态寄存器（PSW）标识

  • 用户态：应用程序，CPU只能执行非特权指令
  • 核心态：内核程序，CPU可以执行特权指令（较为危险的指令）

内核

是计算机上配置的底层软件，是操作系统最基本最核心的部分。

微内核操作系统

内核只包括最基本的功能：

  • 时钟管理（计时）
  • 中断处理
  • 原语（最底层、最接近硬件的程序，具有原子性，不可中断）

大内核操作系统

内核还包括：进程管理、存储器管理、设备管理等

微内核功能少，结构清晰，方便维护，但需要频繁在核心态和用户态之间切换，效率低。大内核反之。

中断和异常

中断机制的引入是为了实现多道程序并发执行。发生中断意味着需要操作系统接入进行管理（如进程切换、I/O等）。

  • 中断发生时，当前程序暂停运行，使操作系统获得计算机控制权
  • 中断发生后，CPU立即进入核心态，并由操作系统内核依据中断信号处理中断
  • 用户态到核心态的切换只能通过中断实现
  • 核心态到用户态的切换是执行一个特权指令，改变一个程序状态字。

中断的分类

  • 内中断：信号来源于CPU内部，与当前执行指令有关，又叫异常、例外、陷入
    • 自愿中断（指令造成的中断）
    • 强迫中断（硬件故障、软件中断）
  • 外中断：信号来源于CPU外部，与当前执行指令无关，是狭义的中断
    • 外设请求
    • 人工干预

外中断的处理

  1. 执行完每条指令后，CPU都会检查中断信号。
  2. 如果检测到外部中断，CPU会保护被中断进程的CPU环境，如各种寄存器等
  3. 根据中断信号转入相应的中断处理程序
  4. 中断处理完毕，恢复原有程序的CPU环境，返回原进程继续执行

系统调用

系统调用是操作系统提供给应用程序使用的接口/函数，应用程序可以通过系统调用来获得操作系统的服务。

当用户想要获取计算机资源（存储、I/O、文件管理）或影响到其他进程的时候，就需要通过系统调用向操作系统发出请求，由操作系统协调管理。系统调用的相关处理需要在核心态下进行。

系统调用过程

  1. 用户程序发出系统调用请求（用户态）
  2. 执行系统调用函数中的陷入指令，触发内中断（用户态）
    • 陷入指令是唯一一个只能在用户态执行，不能在核心态执行的指令
  3. 执行系统调用相应的服务程序（核心态）
  4. 返回用户程序（用户态）

2 进程管理

2.1 基本概念

进程是程序的一次执行过程，是系统进行资源分配和调度的独立单位。程序段、数据段、PCB构成了进程实体。

进程控制块(PCB)

进程控制块（Process Control Block）用来描述进程的各种信息，包括进程标识符、用户标识符、进程状态、进程优先级、代码段指针、数据段指针、打开文件信息、寄存器值（进程切换时保存环境）等。

PCB是进程存在的唯一标志，创建进程，实质上是创建PCB，撤销进程，实质上是撤销PCB。

进程映像

程序是保存在磁盘上的可执行文件，加载到内存中被操作系统调用执行的程序叫进程，所以说系统里只有进程没有程序，一个程序可以同时被执行多次形成身份不同的进程。

进程在内存空间的分布情况叫进程映像，从低地址到高地址依次排列的是：

  1. .text 代码段：二进制指令

  2. .rodata 只读数据:、字符串字面值、具有const属性且被初始化过的全局、静态变量。也可以看作是代码段的一部分。

  3. .data 数据段：被初始化过的全局变量和静态变量

  4. .bss BSS段：没有初始化过的全局变量和静态变量，进程一旦加载成功就会把这段内存清理为零。也可以看作是数据段的一部分。

  5. 堆：动态的分配、管理，需要程序员手动操作，从低地址向高地址扩展

  6. 栈：由编译器自动分配，非静态的局部变量，包括函数的参数、返回值，从高地址向低地址使用。包含用户栈和内核栈。

    • 栈和堆内存之间存在一段空隙，为堆和栈的增长预留空间。

进程的状态切换

  • 运行态：占有CPU，在CPU上运行

  • 就绪态：已经具备运行条件，等待空闲的CPU

  • 阻塞态：由于某种资源的缺失不具备运行条件

  • 创建态：操作系统为进程初始化PCB，分配资源

  • 终止态：操作系统回收进程资源，撤销PCB

进程的5状态模型

  • 运行态->阻塞态是进程主动完成的
  • 阻塞态->就绪态是由外部资源控制的
  • 运行态->就绪态是进程被操作系统调度的

进程调度过程

进程的控制是通过原语完成的，原语的特点是必须一次性完成，不允许中断。原语采用关中断指令和开中断指令完成。原语要完成的任务有：

  1. 更新PCB中的信息：修改进程状态标志、保存/恢复运行环境

  2. 将PCB插入合适的（就绪/阻塞）队列

  3. 分配/回收资源

进程通信

进程是分配系统资源的单位 ，各进程拥有的内存地址空间相互独立。为保证安全，一个进程不能访问另一个进程的地址空间。

信号

linux系统提供了一种处理异步事件的方法。程序使用signal函数来等待信号并做出反应。

#include<signal.h>
#include<stdio.h>
#include <unistd.h>

void handler(int signum)//信号处理
{
    if(signum == SIGIO)
        printf("SIGIO   signal: %d\n", signum);
    else
        printf("error\n");
}

int main(void)
{
    signal(SIGIO, handler);//信号等待
	for(;;) sleep(10000);
    return 0;
}

共享存储

操作系统给两个进程分配一段共享内存空间，两个进程对共享空间的访问必须是互斥的。

管道通信

是在内存中开辟的一个缓冲区。单条管道只能采用半双工通信，某一段时间内只能实现单向传输。各个进程只能互斥地访问管道。

消息队列

数据以格式化的消息在进程间传递，进程通过操作系统提供的“发送/接收消息”两个原语进行数据交换。

套接字

IP地址和端口唯一标识了一台主机的某个进程，套接字通信可以用于和本地进程通信，也可以和远程进程通信。

2.2 进程、线程、协程

进程与线程

线程是一个基本的CPU执行单元，是程序执行的最小单位。引入线程之后，进程仅作为资源分配的基本单位，线程成了调度的基本单位。

一个进程内可以含有多个线程，进程内的各个线程可以并发执行，它们共享进程的代码段和数据段。在进程内进行线程通信只需要通过进程内部变量即可。

每个线程拥有自己的线程控制块，也有就绪、阻塞、运行三种基本状态。

线程拥有自己的堆栈。

由于线程不涉及资源的调度，不需要切换页表和内存等，所以在进程内部进行线程调度的开销要远小于进程调度的开销。

线程与协程

协程，又叫微线程，需要语言特性的支持，如Lua、Python、Go等语言。其优势在于将逻辑流和执行流统一在一起，避免一些异步带来的错误，并降低调度的资源损耗。

协程是一种可以暂停执行过程的函数，它可以中断当前的执行过程直到下一个yield指令达成。

yield相当于函数内部的断点，函数运行到此处，需要

线程间的切换依旧需要消耗系统资源，而协程可以在线程内部完成切换，不需要切换到核心态，其切换完全由程序/程序员控制。其在实现上更像是函数调用。

协程适合I/O密集型的程序，当程序被I/O请求阻塞时，可以通过协程调度直接切换到另一个协程。由于线程内部的协程本身是串行执行的，不能使用多核，所以不适合计算密集型场景。

2.3 处理机调度

概念

高级调度/作业调度

按一定原则从后备队列中选择一个作业，建立进程，使其获得竞争处理机的权限。调入时建立PCB，调出时撤销PCB。频率最低，每个作业只调度一次。

中级调度/内存调度

内存中的进程可能在短时间内不具备运行条件，于是将其调至外存等待，等到它重新具备运行条件且内存有空闲时再调回内存。

目的是提高内存利用率和系统吞吐量。被调度到外存的进程会处于挂起状态，又可以细分为就绪挂起、阻塞挂起。

初级调度/进程调度

按照某种策略从就绪队列中选取一个进程送入CPU。是操作系统中最基本的一种调度，频率很高。

进程调度时机

  • 主动放弃：进程正常终止、发生错误、主动请求阻塞
  • 被动放弃：时间片用完、发生中断、高优先级进程抢占CPU
  • 不能进行进程调度：中断处理过程中、在操作系统内核程序临界区中、在原子操作过程中

批处理系统的进程调度算法

先来先服务(FCFS)

按照作业/进程到达的先后顺序进行服务。等待时间越久的越先获得服务。

  • 优点：公平、实现简单，不会导致饥饿
  • 缺点：对长作业有利，对短作业不利，排在长作业后面的短作业需要等待很长时间。

短作业优先(SJF)

最短的作业/进程最先得到服务。

  • 优点：最短的平均等待时间和平均周转时间
  • 缺点：不公平，对短作业有利，对长作业不利，可能会导致长作业的饥饿。

最短剩余时间优先(SRTN)

短作业优先算法的抢占式版本。

每当有进程加入就绪队列时，如果新进程的剩余时间比当前进程的的剩余时间更短，则由新进程抢占处理机。

高响应比优先(HRRN)

响应比 = (等待时间 + 要求服务时间) / 要求服务时间

选择响应比最高的进程为其服务。非抢占式。

优点：综合考虑了等待时间和运行时间，等待时间相同时，要求服务时间短的优先；要求服务时间相同时，等待时间长的优先。不会导致饥饿。

交互式系统的进程调度算法

时间片轮转算法

公平、轮流地为各个进程服务。按照各个进程到达的顺序，轮流让各个进程执行一段时间片。进程用完时间片之后，剥夺处理机，使其排到队尾。是抢占式的算法。

如果时间片设置得太大，会退化为先来先服务算法；设置太小，会导致进程切换过于频繁，消耗性能。

不会造成饥饿。

优先级调度算法

实时操作系统的出现，越来越多的场景需要根据任务的紧急程度来决定处理顺序。每个作业/进程有各自的优先级，调度时选择优先级最高的。既可以抢占式，也可以非抢占式。

静态优先级：优先级不变；动态优先级：优先级可以动态调整。通常系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好I/O型进程。

可能会导致饥饿。

多级反馈队列调度算法

是对其他算法的折中权衡。设置多个队列，按照优先级从高到低、时间片从小到大分配。

  • 新进程进入第一个队列，按照先来先服务原则排队，若用完时间片后还未完成，进入下一级队列队尾。
  • 只有当上级队列的进程全部结束后，才会为下级的进程分配时间片。
  • 如果再下级进程运行过程中，有新的进程来到并进入第一级队列，那么新进程会抢占CPU，被抢占的进程会回到本级队列的队尾。

可以灵活调整对各类进程的偏好，如可以让I/O密集型进程用完时间片后回到原队列而不是下一级队列。可能会导致饥饿。

2.4 进程同步与互斥

  • 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
  • 互斥：一个时间段内只允许一个进程访问的资源叫临界资源，多个进程只能互斥地访问临界资源。当一个进程在访问某临界资源时，另一个想要访问该临界资源的进程必须等待，直到该临界资源的访问结束。

临界区

访问临界资源的代码被称作临界区，为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

一般而言，临界区前后用于实现互斥的代码被称作进入区和退出区。进入区用于检查临界区是否可以进入以及进入后对临界区上锁，退出区负责解除临界区的锁。

互斥锁与自旋锁

互斥锁

最常使用于线程同步的锁。

标记用来保证在任一时刻，只能有一个线程访问该对象，同一线程多次加锁操作会造成死锁；临界区和互斥量都可用来实现此锁。

被阻塞时，会让该线程睡眠，等待锁释放时被唤醒。

自旋锁

用处和互斥锁类似。

同互斥锁不同的是，在锁操作需要等待的时候并不是睡眠等待唤醒，而是循环检测保持者已经释放了锁，自旋锁阻塞后不会让出cpu，会一直忙等待，直到得到锁。

这样做的好处是节省了线程从睡眠状态到唤醒之间内核会产生的消耗，在加锁时间短暂的环境下这点会提高很大效率。坏处是消耗大量cpu资源。

条件变量与锁

锁是用来实现资源的互斥访问的，然而在进程的异步运行中，竞争资源的进程不知道何时锁是打开的，只能不停地轮询锁或者sleep等待，效率较低。

条件变量是操作系统实现的信号机制之一。

  • 当进程发现资源被锁，触发wait操作，等待信号
  • 另一进程使用完资源解锁，触发signal操作，告诉等待的进程可以继续运行。

信号量(Semaphore)

PV操作

  • P(wait)：表示占用一个资源
  • V(signal)：表示释放一个资源

PV操作要被设计成不可分割的原语，要通过硬件方法，譬如锁总线来实现。

整型信号量

用一个整型变量作为信号量，用来表示系统中某种资源的数量。

  • P：如果信号量大于0，执行-1操作；如果信号量小于等于0，进程睡眠，等待信号量大于0；在某些实现中这里是死循环等待。
  • V：对信号量执行+1操作，唤醒睡眠的进程让其完成wait操作。

记录型信号量

typedef struct {
    int value;//记录资源数
    struct process *queue;//等待队列，用于记录排队等待访问临界区的进程
    //用于记录资源数的整型变量为负数时，其绝对值表示正在等待队列中的进程数。
} semaphore;
  • P：value--，当value小于0时，进程调用block原语进行自我阻塞并进入等待队列，等待唤醒。
  • V：value++，若value小于等于0，说明还有进程在排队等待，此时调用wakeup原语唤醒等待队列中的队头进程。

使用信号量实现进程互斥

typedef int semaphore;
semaphore mutex = 1;
//数值为1的信号量都在某种程度上可以实现互斥
//一组数值之和最多为1的信号量也可以实现某个临界资源的互斥
P1(){
    ...
    P(mutex);//上锁
    //临界区
    V(mutex);//解锁
    ...
}
P2(){
    ...
    P(mutex);
    //临界区
    V(mutex);
    ...
}

使用信号量实现进程同步

即保证某些代码的执行顺序，前V后P。

typedef int semaphore;
semaphore mutex = 0;
P1(){
    ...
    要先进行的操作;
    V(mutex);//解锁，mutex++
    ...
}
P2(){
    ...
    P(mutex);//mutex--, mutex<0时阻塞
    要后进行的操作;
    ...
}

生产者消费者问题

系统中有一组生产者和一组消费者，生产者每次生产一个产品放入缓冲区，消费者每次从缓冲区取走一个产品。

假设缓冲区大小为n，只有缓冲区非空，消费者才能进行消费；缓冲区非满，生产者才能生产。

#define N 100
typedef int semaphore;
semaphore mutex = 1;//互斥信号量，实现互斥访问
semaphore empty = N;//同步信号量，表示空闲缓冲区数量
semaphore full = 0;//同步信号量，表示非空缓冲区/产品数量

void producer() {
    while(1) {
        生产产品;//将生产和消费放在临界区外，可以提升并发效率
        P(&empty);//减少空闲缓冲区
        P(&mutex);//互斥
        把产品放入缓冲区;
        V(&mutex);//互斥解除
        V(&full);//增加非空缓冲区
    }
}
/*
应当注意的是，互斥操作应当被同步操作包裹，即先同步后互斥
否则，当empty=0, full=N时，producer进程触发，先进行互斥上锁，又因为同步锁导致阻塞，此时consumer进程会因为互斥锁同样被阻塞，导致死锁。
*/
void consumer() {
    while(1) {
        P(&full);//减少非空缓冲区
        P(&mutex);//互斥
        取出产品;
        V(&mutex);//互斥解除
        V(&empty);//增加空闲缓冲区
        消耗产品;
    }
}

读者写者问题

有读者写者两组并发进程共享一个文件，多个读进程可以同时访问数据，但写进程与其他进程只能互斥访问数据，写进程要在其他进程退出后才能进行写操作。

typedef int semaphore;
semaphore data_mutex = 1;//实现写进程和其他进程的互斥访问
int count = 0;//记录有几个读进程在访问文件
//count数据也需要互斥访问，防止多个读进程同时访问，导致data_mutex被多加锁
semaphore count_mutex = 1;

void reader() {
    while(1) {
        P(&count_mutex);
        // 第一个读者需要检查写者的存在，并对数据进行加锁，防止写进程访问
        if(count == 0) 
            P(&data_mutex); 
        count++;
        V(&count_mutex);

        //读文件;

        P(&count_mutex);
        count--;
        // 最后一个读者需要对数据进行解锁，允许写进程访问
        if(count == 0) 
            V(&data_mutex);
        V(&count_mutex);
    }
}

void writer() {
    while(1) {
        //写进程是简单的互斥逻辑
        P(&data_mutex);
        //写文件;
        V(&data_mutex);
    }
}

上面的方法在读进程不断触发时，可能会导致写进程的饥饿，以下是优化

//实现了写进程与读进程的先来先服务
typedef int semaphore;
semaphore data_mutex = 1;
int count = 0;
semaphore count_mutex = 1;
semaphore resource_mutex = 1;//实现先到者对资源的优先访问

void reader() {
    while(1) {
        P(&resource_mutex);//当有写进程将此互斥量上锁，读进程就无法插队
        P(&count_mutex);
        if(count == 0) P(&data_mutex); 
        count++;
        V(&count_mutex);
        V(&resource_mutex);//读进程会在读文件之前将锁解开，不影响读进程的并发

        //读文件;

        P(&count_mutex);
        count--;
        if(count == 0) V(&data_mutex);
        V(&count_mutex);
    }
}

void writer() {
    while(1) {
        //在写进程外圈添加一个互斥量，实现针对其他读写进程的互斥
        P(&resource_mutex);
        P(&data_mutex);
        //写文件;
        V(&data_mutex);
        V(&resource_mutex);
    }
}

哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物，哲学家之间的五个间隙分别放着一根筷子。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

一个思路是，将筷子看做临界变量，让哲学家依次分别拿起左边和右边的筷子并上锁。这样会导致一个问题，当所有哲学家同时决定拿起左手的筷子时，五个进程分别给一支筷子上锁，而无法获取第二根筷子，又不会主动放下自己手上的筷子，导致死锁。

解决办法有很多，譬如

  • 限制同时进餐的哲学家个数
  • 奇数哲学家先拿右手的筷子
  • 对取筷子的同步操作加互斥锁

管程

管程是一种由编译器实现的高级同步机制，用于解决信号量编写程序困难，容易出错的问题。

管程的特性：在一个时刻只能有一个线程使用管程所声明的区域。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

Java语言中的synchronized关键字就实现了类似管程的机制。

2.5 死锁

在并发环境下，各个进程因为竞争资源而造成的一种互相等待对方手中的资源，导致各进程都阻塞，无法向前推进的现象。

死锁产生的四个必要条件

  • 互斥：只有对临界资源的争抢才会导致死锁，因为进程需要阻塞等待。
  • 不可剥夺：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
  • 占有和等待：已经得到了某个资源的进程再请求新的资源。当新资源被其他进程占有，请求进程不放弃已获得的资源。
  • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

解决死锁问题：破坏四个必要条件中的若干个。

  • 互斥条件：将只能互斥使用的资源改造为同时共享的资源。如打印机假脱机技术。

  • 不可剥夺：当进程请求新资源而得不到满足时，立即释放所有资源；或者让进程能够强行剥夺别人占有的目标资源

  • 占有和等待：在进程运行之前一次性分配它所需的所有资源，直到使用结束。

  • 环路等待：给资源进行编号，规定进程按照编号顺序来请求资源。

  • 鸵鸟方法：不处理死锁。因为处理死锁的代价比不处理更大。

避免死锁——银行家算法

在资源分配之前先判断是否会进入不安全状态。

  1. 检查一次申请是否超过声明的最大需求

  2. 检查系统剩余资源是否满足这次需求

  3. 模拟分配，修改各个数据结构

  4. 用安全性算法检查是否导致系统进入不安全状态

安全性算法

  1. 检查当前剩余可用资源能够满足某个进程最大需求，能则将其加入安全序列，并“回收”该进程所有资源。

  2. 不断重复上一步，如果最终所有进程都进入安全序列，则处于安全状态。

死锁的检测和解除

允许死锁发生，但操作系统会检测死锁发生并采取措施解除死锁。

资源分配图

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

解除方法：剥夺资源、回滚进程、杀死进程

3 内存管理

操作系统内存管理的职责：

  • 负责内存空间的分配与回收
  • 需要提供某种技术从逻辑上对内存空间进行扩充
  • 需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换（地址重定位）
  • 内存保护功能：进程之间不能随意访问别人的内存空间。

地址重定位

  • 绝对地址：编译时产生物理地址，单道程序阶段使用。
  • 静态重定位：装入时将逻辑地址转换为物理地址，不允许进程在内存中的移动，用于早期多道批处理系统。
  • 动态重定位：运行时将逻辑地址转换为物理地址，允许进程在内存中的移动。

交换技术

  • 内存紧张时，会将不太被访问的进程换出外存，把外存中的某些具备运行条件的进程换入内存。
  • PCB会常驻内存，只换代码段和数据段。

3.1 动态分区分配算法

给进程分配内存地址的算法。

内部碎片：分配给进程的内存存在没有被利用的部分。 外部碎片：未分配给进程的内存因为容量太小等原因没有被利用的部分。

连续分配算法

首次适应算法

  • 每次都从低地址开始按顺序查找，找到第一个满足大小的空闲分区。
  • 优点：可以充分利用低地址区域的空间，在高地址区域留下大的连续空闲区。
  • 缺点：每次都从低地址开始查找，会导致低地址附近有大量小碎片，会增加查找开销。

临近适应算法

  • 每次分配内存时都从上次查找结束的位置开始依次查找。
  • 优点：避免低地址附近产生大量小碎片。
  • 缺点：可能导致缺少足够的连续内存空间给“大进程”。

最佳适应算法

  • 尽可能使用小的空闲区，以保证“大进程”到来时能有连续的大片空间
  • 实现方法：将空闲分区按照容量递增连接，分配时按顺序查找空闲分区链。
  • 缺点：可能会产生大量难以利用的外部小碎片。由于需要排序，开销大。

最坏/大适应算法

  • 为避免产生大量小碎片，尽可能使用大的连续空闲区。
  • 实现方法：将空闲分区按照容量递减连接，分配时按顺序查找空闲分区链。
  • 缺点：可能导致缺少足够的连续内存空间给“大进程”。由于需要排序，开销大。

非连续分配——分页存储管理

将内存分为一个个大小相等的分区，每个分区是一个“页框”，并有一个编号。将用户进程的地址空间也分割成与页框大小相等的区域，叫“页”，并有一个编号。

操作系统会以页框为单位为各个进程分配内存空间，将每个页面分别装入一个页框。装入时，既不需要装入连续的框，也不需要按顺序装入，只需要记录装入的页与页框号的对应关系即可。

当页的大小取2的幂时，地址结构可以用页号+页内偏移量来表示。

页表

每个进程都对应一张页表，进程的每一页对应一条页表项，页表项记录进程的页号与物理内存的页框号的一一对应关系。

由于页表项长度是固定的，页号是连续的，所以页号信息可以隐含在连续地址中。

逻辑地址到物理地址的变换方法

  1. 根据逻辑地址计算出页号和页内偏移量
  2. 如果页号没有越界，则查询页表，找到页号对应的页框
  3. 根据页框和页内偏移量，找到并访问对应的物理地址

局部性原理

  • 时间局部性：如果执行了程序的某条指令，那么不久后该指令可能会被再次执行；如果某个数据被访问过，那么不久后该数据很可能再次被访问。（由于循环的存在）
  • 空间局部性：一旦程序访问了某段内存，则不久后其附近的内存也很有可能被访问。

快表

  • 基于局部性。存放在高速缓存中，访问速度比页表快得多。存储页号和页框号的一一对应。
  • 在访问一个页后，会将其存放在快表中，当下一次再访问相同的页面，会先查询快表，如果命中，则可以快速定位物理地址，没有命中则再去查页表。

两级页表 页表必须连续存放，当页表很大时，要占用很多连续的页框；同时也没必要让整个页表常驻内存。可以将页表再进行按页分组，再组织一个“页目录表”，这样页表也能离散地存放在内存中。

于是，逻辑地址的结构又可以被细分为一级页号、二级页号、页内偏移量。

  • 一级页号用于查询页目录表，获取对应页表的物理地址。
  • 二级页号用于查询页表，获取对应页面的物理地址。二级页号可以认为是页表的“页内偏移量”。

分段存储管理

进程按照自身的逻辑关系（功能）划分为若干个长度不定的段，每个段有一个段名。操作系统在分配内存时按照段为单位分配，每个段占据连续空间。

分段存储管理中，地址由段号和段内地址/偏移量组成的。

每个程序要建立一张“段表”，包括（隐含的段号、）段长、段起始地址。

段页式管理方式

分页和分段管理方式的结合。 段页式管理方式中，地址由段号、页号、页内偏移量构成。（页号、页内偏移量构成段内地址）

分页管理优点：空间利用率高，不会产生外部碎片，内部碎片少。 分页管理缺点：不方便按照逻辑模块实现信息的共享和保护。 分段管理优点：方便按照逻辑模块实现信息的共享和保护。 分段管理缺点：段过长时要分配很长的连续空间，且会产生外部碎片。

3.2 虚拟内存

基于局部性原理，在程序装入时，可以将很快用到的部分装入内存，暂时用不到的留在外存，然后开始执行程序。

执行过程中，当要访问不再内存的信息时，操作系统要先将所需信息从外存调入内存，然后继续执行。若此时内存空间不够，就先将内存中暂时用不到的信息换到外存。

这样，用户看来就会有一个比物理内存大得多的内存，就是虚拟内存。

虚拟内存是基于离散内存管理之上的。

虚拟内存存储在外存的“对换区”，有别于存储文件的区域，对换区采用连续分配的方式，I/O更快。

虚拟内存特征

  • 多次性：程序可以分多次装入内存
  • 对换性：作业可以在运行过程中换入换出
  • 虚拟性：在逻辑上扩充了内存的容量

请求分页管理方式

请求分页管理是分页存储管理在虚拟内存上的扩展。当程序在执行过程中要访问内存中缺失的页面时，由操作系统将缺失的页面从外存调入；操作系统还会将暂时用不到的页面换出。

页表机制 增加了一些字段：

  • 状态位：记录某一页是否在内存中
  • 访问字段：记录最近被访问的频率
  • 修改位：记录某一页是否被修改，如果未被修改，则不需要浪费时间写回外存。
  • 外存地址：页面在外存中的存放位置

缺页中断机构

  1. 在请求分页系统中，每当要访问的页面不在内存，便产生一个缺页中断，然后由中断处理程序处理。
  2. 缺页的进程被阻塞，页面换入后将其唤醒，放回就绪队列。
  3. 如果内存中有空闲的页框，则将所缺页面装入，并修改相应页表项。
  4. 如果没有空闲页框，则由页面置换算法将一个页面换出。若换出的页面被修改过，则写回外存。
  5. 换入和换出的页面也要修改相应的快表项。

页面置换算法

最佳置换算法(OPT, optimal)

每次选择的页面是以后永不使用或最长时间不访问的页面。

只是理论上的最佳算法，无法实现。

先进先出置换算法(FIFO)

淘汰最早进入内存的页面。

可能出现为进程分配的物理块越多，缺页越严重的情况。算法的性能较差。

最近最久未使用(LRU)

用访问字段记录该页面自上次访问以来的时间，淘汰时间最长的那个。

性能好，但是实现困难，开销大。

时钟置换算法(CLOCK)

用访问位记录最近是否被访问过。

  1. 当某页被访问时，该位置1。
  2. 当要淘汰一个页面时，进行一轮扫描，检查访问位，如果是0则换出，如果是1则置0。
  3. 如果全是1，则全置0，再进行一轮扫描。

改进时钟置换算法

未修改的页换出不需要进行I/O写回，所以考虑修改位的情况。

  1. 换出扫描到的第一个访问位和修改位都为0的页，本轮不修改任何标志位。（既没有访问又没有修改的页优先换出）
  2. 若第一轮扫描没换出，则第二轮扫描访问位为0，修改位为1的页，本轮会将访问位置0。（换出没有访问的页）
  3. 重复1（访问过但没修改）
  4. 重复2（访问过且被修改）

页面分配策略

驻留集

给进程分配的物理块的集合。太大会导致程序的并发度下降，总体效率降低；太小会导致频繁的缺页，效率降低。

物理块分配方式

  • 固定分配：进程创建时，操作系统分配一定数目物理块，驻留集大小不变。
  • 可变分配：进程运行期间，驻留集大小可变。

物理块置换方式

  • 局部置换：发生缺页时进程只能在自己的物理块中进行置换。
  • 全局置换：操作系统会将自己的空闲物理块分配给缺页进程，也可以将别的进程的物理块换出，再分配给缺页进程。

组合策略

  • 固定分配局部置换：顾名思义。缺点是很难知道应当分配多少的物理块才合适。
  • 可变分配全局置换：当进程发生缺页，操作系统就会从空闲物理块中分一块给它，直到空闲块用完，才会将某个进程的物理块换出并分配。
  • 可变分配局部置换：进程缺页时只允许在自己的物理块中进行置换。但是系统会根据进程的缺页频率动态地分配物理块，频繁缺页时增加，不缺页时减少。

抖动现象

刚刚换出的页面又要换入内存，或刚刚换入的页面要换出。原因是进程频繁访问的页面数高于可用的物理块数（分配给进程的物理块不够）。

4 文件管理

4.1 文件系统

文件结构

  • 无结构文件：由二进制流或字符流组成，无明显逻辑结构。
  • 有结构文件：由记录组成，分为定长记录（可实现随机存储）、可变长记录（不可随机存储）

存储方式

  • 顺序存储：逻辑上相邻，物理上也相邻，类似数组的存储。
  • 链式存储：逻辑上相邻，物理上不一定相邻，类似链表。

排列方式

  • 串结构：不排序，一般按照时间顺序组织。
  • 顺序结构：按照关键字排序。可进行二分查找。

索引文件

对于可变长记录文件，必须进行顺序检索。为了提高文件检索速度，可以建立索引文件，记录索引号、文件长度、文件指针。

  • 文件不需要在物理空间连续存放。
  • 如果将关键字作为索引号，可以支持二分查找。
  • 可以用不同的数据项建立多个索引表。

索引顺序文件

并不是每一条记录（文件）都对应一个索引表项，而是一组记录对应一个索引表项。可以无须对关键字进行顺序排列，以方便增加新表项。

如果索引表尺寸过大，还可以创建多级索引文件。

文件控制块(FCB)

核心作用是实现文件名和文件物理地址之间的映射，使用户可以按名存取。

目录文件

本身是一种有结构文件，由一条条记录组成，每条记录对应一个该目录下的一个文件。

目录文件中的每一条记录就是一个“文件控制块”，包含了文件的基本信息，如文件名、文件物理地址、存取控制信息等。

索引节点

是FCB的改进，将FCB中除了文件名的部分构造成一个索引节点，FCB只记录文件名和索引节点的指针。

每个磁盘块所能够容纳的FCB增加，由于每次I/O只能读入一个磁盘块，查询多个磁盘块造成的额外I/O开销就减少。

链接文件

硬链接：不同的文件控制块指向同一个索引节点，索引节点的计数器+1。

软链接：以路径的形式存在，基本类似于Windows操作系统中的快捷方式。

文件的物理结构

磁盘中的存储单元会被分为一个个“磁盘块”，一般磁盘块和一个内存页的大小相同。 相应的，文件的逻辑地址也被分为一个个块，可以表示为(逻辑块号,块内地址)的形式

文件分配方式

连续分配：文件在磁盘上占有一组连续的块。

  • 优点：支持文件的随机访问，且连续读写时速度快。
  • 缺点：不方便文件拓展，会产生大量小碎片。

链接分配：采取离散分配的方式。

  • 隐式链接：每个文件块记录下一个文件块的位置。
    • 优点：存储效率高，方便文件拓展。
    • 缺点：只能顺序访问。
  • 显示链接：把用于链接各个物理块的指针显示存储在一张表中，称为文件分配表(FAT)。每个磁盘仅设置一张FAT，在开机时装入内存，并常驻内存。
    • 优点：块号转换过程不需要读取磁盘，效率很高。

索引分配：为每个文件建立索引表，记录逻辑块对应的物理块。

  • 优点：用户可以随机访问文件的某个逻辑块，容易实现文件扩展。
  • 缺点：索引表占空间。当文件很大时，索引表也会很大，索引表的查询会耗费时间。解决方法：多级索引。

混合索引：多级索引的改进

在一个文件的顶级索引列表中，既包含直接地址索引，又包含一级间接索引、二级间接索引等。可以适应不同大小文件的需求。

磁盘存储空间管理

空闲表法：用列表方式列出空闲块以及连续的空闲块数。

空闲链表法：在空闲区尾部有链接下一个空闲区的指针。

位示图法：用一个表，每个单元格格中用一位表示该块是否空闲。可以适用于连续和离散分配。

成组链接法

在UNIX系统中，将空闲块分成若干组，每100个空闲块为一组，每组的第一空闲块登记了下一组空闲块的物理盘块号和空闲块总数，其他99个空闲块用于存放文件。如果一个组的第下一个空闲块号等于0，则意味着该组是最后一组，即无下一个空闲块。

在磁盘文件部分的目录区中有一个块会作为“超级块”记录磁盘信息，启动时将“超级块”读入内存，并要保证内外存中的“超级块”数据一致。超级块是第一个空闲块，类似于头指针。

分配空闲磁盘时，从前（超级块）往后分配，已分配的块则从组里消除（减少空闲块数）。如果超级块被完全分配，则将超级块移除，将下一个分组写入超级块（去除头部，将第二级作为头部）

回收空闲磁盘时，同样从前往后，直接插入超级块，如果超级块100个满了，则复制一个超级块，并将回收的空闲磁盘块写入超级块(插入头部，原头部作为第二级)

文件操作

创建文件：执行create系统调用

  1. 在外存中找到一片空间
  2. 在对应目录创建对应目录项
  3. 分配磁盘块

删除文件：执行delete系统调用

  1. 找到目录项
  2. 回收磁盘块
  3. 在对应目录删除对应目录项

打开文件：执行open系统调用

  1. 找到目录项
  2. 将目录项复制到内存的系统“打开文件”表中，若已经打开，则计数器+1，写入相应进程的“打开文件”表中。

关闭文件：执行close系统调用

  1. 删除进程对应的“打开文件”表项。
  2. 系统“打开文件”表对应项的打开计数器-1，为0时删除对应表项。

4.2 磁盘管理

磁盘结构

  • 盘面（Platter）：一个磁盘有多个盘面；
  • 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
  • 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
  • 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
  • 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
  • 主轴（Spindle）：由马达驱动，使整个盘面转动。

磁盘调度算法

先来先服务(FCFS)

按照磁盘请求顺序进行调度。

  • 优点是公平和简单。
  • 缺点：因为未对寻道做任何优化，使平均寻道时间可能较长。

最短寻道时间优先(SSTF)

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

电梯算法(SCAN)

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。但是各个磁道的响应不是很平均。

循环扫描算法(C-SCAN)

磁盘的扫描仅按朝一个方向走，到达一端后，会快速返回起点，重新开始扫描。

优点是各个磁道的响应很平均，但损失了效率。

5 设备管理

I/O控制方式

程序直接控制

  • CPU向控制器发出读指令，设备启动
  • CPU轮询检查控制器状态
  • 输入设备将数据传给控制器，并报告状态
  • 控制器将数据放入缓存，并报告就绪
  • 如果设备就绪，CPU从I/O模块读入数据并写入内存

中断驱动方式

用中断将请求I/O的进程阻塞，CPU去处理其他任务，等到I/O结束再恢复被阻塞的进程。

DMA直接存储器存取

用于块设备，数据的传送单位是块。数据流不再经过CPU，直接在内存和设备之间流动。仅在连续的块传送的起始和末尾需要CPU干预。如果数据传输是离散的，那么CPU需要多次干预。

通道控制方式

通道可以识别并执行一系列CPU发出的通道指令，只有在完成一组数据块的I/O后才需要发出中断信号。

八股文

评论区