操作系统 - YxY的小站

文章目录

1 计算机系统概述
2 进程和线程
3 内存管理
4 文件管理
5 输入输出管理

计算机系统概述

操作系统的基本概念

概念功能

操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件。

①操作系统是系统资源的管理者

②向上层提供方便易用的服务

③是最接近硬件的一层软件

操作系统的功能和目标——作为系统资源的管理者

处理机管理
存储器管理
文件管理
设备管理

操作系统的功能和目标——向上层提供方便易用的服务

直接给用户使用的（GUI、命令接口—（联机命令接口、脱机命令接口））
给软件/给程序员使用的（程序接口）即“系统调用”，用户通过程序间接使用

操作系统的功能和目标——作为最接近硬件的层次

需要实现对硬件机器的拓展

回顾

特征

并发、共享（两个最基本的特征，二者互为存在条件）、虚拟、异步

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。常考易混概念——并行：指两个或多个事件在同一时刻同时发生。

操作系统的并发性指计算机系统中“同时”运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。操作系统就是伴随着“多道程序技术”而出现的。因此，操作系统和程序并发是一起诞生的。

注意（重要考点）： 单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行 多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行

共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源

同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问

所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的（即分时共享）

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。

处理器的分时共享：虚拟技术中的“时分复用技术”。微观上处理机在各个微小的时间段内交替着为各个进程服务

虚拟存储器：虚拟技术中的“空分复用技术”

如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义了。因此，没有并发性，就谈不上虚拟性

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。

操作系统的发展与分类

手工操作阶段

主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低

批处理阶段——单道批处理系统

引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出

主要优点:缓解了一定程度的人机速度矛盾,资源利用率有所提升。

主要缺点:内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待l/o完成。资源利用率依然很低。

批处理阶段——多道批处理系统

主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大

主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。eg：无法调试程序/无法在程序运行过程中输入一些参数）

分时操作系统

分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。主要

优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/ 作业服务一个时间片，不区分任务的紧急性。

实时操作系统：

主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性

硬实时系统—-必须在绝对严格的规定时间内完成处理

软实时系统—-能接受偶尔违反时间规定

网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机之间的通信。（如：Windows NT 就是一种典型的网络操作系统，网站服务器就可以使用

分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务

个人计算机操作系统：如 Windows XP、MacOS，方便个人使用

操作系统运行环境

运行机制

中断

中断的分类

中断的基本原理

系统调用

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

陷入指令是非特权指令

操作系统体系结构

内核是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序。

操作系统内核需要运行在内核态 操作系统的非内核功能运行在用户态

操作系统引导

进入BIOS后再硬件自检

虚拟机

虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器（Virtual Machine, VM），每个虚拟机器都可以独立运行一个操作系统

进程和线程

进程与线程

进程概念

程序:就是一个指令序列

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”—— PID（Process ID，进程ID）

注意:PCB是进程存在的唯一标志!

程序段、数据段、PCB三部分组成了进程实体(进程映像)引入进程实体的概念后，可把进程定义为: 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的状态与转换

操作系统会将各个进程的PCB组织起来—-（链接方式、索引方式）

转换

就绪态->运行态

运行态->阻塞态

阻塞态->就绪态

运行态->就绪态

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

使用原语实现

进程间通信

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

共享存储

为避免出错，各个进程对共享空间的访问应该是互斥的。

消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

管道通信

线程概念

可以把线程理解为“轻量级进程”。线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件)

引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的)。 线程则作为处理机的分配单元。

用户级线程

内核级线程

多线程模型

一对一、多对一、多对多

线程的状态与转换

处理机调度

概念

七状态模型（408不考）

三层调度的联系对比

调度算法评价指标

进程调度的时机、切换与过程

调度算法

先来先服务

最短作业优先

最高响应比优先

响 应 比 等 待 时 间 服 务 时 间 服 务 时 间

时间片轮转

若时间片太大就变成了先来先服务

优先级调度

多级反馈队列

多级队列调度

同步与互斥

同步互斥概念

进程同步和进程互斥是操作系统中用于处理多个进程共享资源时的两个重要概念。

进程同步指的是多个进程之间按照一定的顺序和时间进行协调，以保证它们能够正确地共享和访问共享资源。在进程同步中，进程可能需要等待其他进程的某个事件或操作完成，才能继续执行自己的任务。常见的进程同步机制包括信号量、互斥锁、条件变量等。

进程互斥是指多个进程竞争同一个资源时，需要通过一定的机制来确保同时只有一个进程可以访问该资源，其他进程必须等待。进程互斥的目的是防止多个进程同时修改共享资源，导致数据不一致或冲突。常见的进程互斥机制包括互斥锁、临界区、信号量等。

进程同步和进程互斥通常是相互关联的，它们的目标都是确保多个进程之间的正确协作和共享资源的安全访问。进程同步用于协调进程之间的执行顺序，避免竞争条件和数据不一致问题。进程互斥用于限制对共享资源的独占访问，确保同时只有一个进程可以修改共享资源，从而避免冲突和数据损坏。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
1. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
1. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
1. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥的软件实现方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

int turn=0;//turn 表示当前允许进入的进程号

p0:
while(turn!=0);//进入区
critical section;//临界区
turn=1;//退出区
remainder section;//保留区

p1:
while(turn!=1);
critical section;
turn=0;
remainder section;

该算法可以实现“同一时刻最多只允许一个进程访问临界区”

只能按 P0 ->P1 -> P0 -> P1 ->……这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。因此，单标志法存在的主要问题是：违背“空闲让进”原则。

双标志先检查法

双标志后检查法

Peterson算法

硬件实现方法

中断屏蔽方法

硬件指令法（TestAndSet/Swap）

互斥锁

特性：

• 需忙等，进程时间片用完才下处理机，违反“让权等待”

• 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低 • 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区

• 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量

用信号量机制实现进程互斥、同步、前驱关系

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

生产者消费者问题

semaphore mutex=1;
semaphore full=0;
semaphore empty=n;
producer(){
    while(1){
        生产产品
        P(empty)；
        P(mutex)；
        将产品放入缓冲区
        V(mutex);
        V(full);
    }
}
consumper(){
    while(1){
        P(full);
        P(mutex);
        从缓冲区取出一个产品
        V(mytex);
        V(empty);
        消费产品
    }
}

多生产者多消费者

吸烟者问题

int num=0;
semaphore offer1;
semaphore offer2;
semaphore offer3;
semaphore finish;
provide(){
    while(1){
        num++;
        num=num%3;
        if(num==1)
            V(offer1);
        else if(num==2)
            V(offer2);
        else if(num==3)
            V(offer3);
        将材料放在桌子上
        P(finish);
    }
}
P1(){
    while(1){
        P(offer1);
        吸烟；
        V(finish);
    }
}
P2(){
    while(1){
        P(offer2);
        吸烟；
        V(finish);
    }
}
P3(){
    while(1){
        P(offer3);
        吸烟；
        V(finish);
    }
}

读者写者问题

int count=0;//当前读者数
semaphore rw=1;//读写互斥
semaphore mutex=1;对count互斥访问
writer(){
    while(1){
        P(rw);
        开始写；
        V(rw);
    }
}
reader(){
    while(1){
        P(mutex);
        if(count==0)
            P(rw)
        count++;
        V(mutex);
        开始读
        P(mutex)
        count--;
        if(count==0)
            V(rw);
        V(mutex);
    }
}

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。最后，还要认真体会我们是如何解决“写进程饥饿”问题的。

哲学家就餐问题

如何防止死锁的发生呢？

①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

③各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了

实现③

semaphore choptick[5]={1,1,1,1,1};
semaphore mutex=1;
pi{
    while(1){
        P(mutex);
        P(choptick[i]);
        P(choptick[(i+1)%5]);
        V(mutex);
        吃饭
        V(choptick[i]);
        V(choptick[(i+1)%5]);
        思考；
    }
}

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。

管程

管程（Monitor）是一种并发编程的概念，用于实现多线程之间的同步和互斥操作。它提供了一种高级抽象，用于管理共享资源的访问，并提供了一组操作用于线程的调度和通信。

管程由以下几个要素组成：

共享变量：管程中包含了一些共享变量，这些变量是多个线程需要访问和操作的共享资源。
进程/线程入口：管程提供了一些进程/线程可以调用的入口方法。这些方法定义了对共享资源的访问操作，例如获取资源、释放资源等。
条件变量：管程可以包含一个或多个条件变量，用于实现线程的等待和唤醒机制。线程可以在某个条件变量上等待，并在满足特定条件时被唤醒。

管程的基本思想是，当一个线程进入管程并开始执行时，它会锁定管程，确保其他线程不能同时进入管程。这样，每个线程都能独立地访问共享变量并执行操作。如果某个线程需要等待某个条件满足，它可以在相应的条件变量上等待，并释放管程的锁，使其他线程有机会进入管程。当某个线程满足条件后，它可以通过条件变量将等待的线程唤醒，并重新获取管程的锁，继续执行。

管程提供了一种高级的同步机制，隐藏了底层的锁和条件变量的细节，使得并发编程更加方便和易于理解。它可以确保共享资源的互斥访问，避免竞争条件和数据不一致问题，并提供了线程之间的通信和协调机制，使得多线程程序可以按照特定的顺序和条件进行执行。

死锁

概念

死锁（Deadlock）是在并发计算中的一种情况，其中两个或多个进程（或线程）无限期地被阻塞，因为它们互相等待对方所持有的资源。这种情况下，被阻塞的进程无法继续执行，并且系统无法进一步前进。

死锁通常涉及以下几个必要条件：

互斥条件（Mutual Exclusion）：一个资源同时只能被一个进程持有，如果一个进程已经获取了某个资源，其他进程就无法再获取该资源。
请求与保持条件（Hold and Wait）：一个进程在持有至少一个资源的同时，可以请求获取其他进程持有的资源，同时保持自己所拥有的资源。
不可剥夺条件（No Preemption）：资源只能在进程使用完之后由进程自愿释放，其他进程无法强行剥夺其资源。
循环等待条件（Circular Wait）：存在一个进程链，每个进程都在等待下一个进程所持有的资源，使得最后一个进程等待第一个进程所持有的资源，形成了循环依赖。

当这些条件同时满足时，就可能导致死锁的发生。在死锁发生时，系统中的进程将无法继续执行下去，除非采取一些特定的解除死锁的措施，如资源剥夺、进程终止、资源预先分配等。

死锁是并发编程中的一个常见问题，因此需要仔细设计和管理资源的使用，以避免死锁的发生。各种死锁避免和死锁检测算法也被开发出来，用于识别和解决潜在的死锁情况。

死锁的处理策略

预防死锁

避免死锁

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

检测和解除

死锁解除（Deadlock Recovery）：死锁解除的目标是从已发生死锁的状态中解脱出来，使系统能够继续正常运行。常见的死锁解除方法包括资源剥夺、进程终止和回滚。

资源剥夺：选择一个或多个进程，并从它们中剥夺一部分或全部资源，将这些资源分配给其他进程，以解除死锁。资源剥夺可能导致进程的异常终止或回滚。
进程终止：选择一个或多个进程，将其终止，释放它们所占用的资源，从而解除死锁。终止进程可能会导致数据丢失或进程的重启。
回滚：选择一个或多个进程，将它们回滚到先前的检查点，撤销已执行的操作，使系统恢复到一个安全状态。回滚可能会导致一些进程的重复工作，但可以保证系统的一致性。

内存管理

内存的基础知识

内存可存放数据。程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾

绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。

静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。

动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。

链接的三种方式

内存管理

操作系统负责内存空间的分配与回收
操作系统需要提供某种技术从逻辑上对内存空间进行扩充
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

覆盖与交换

连续分配管理方式

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

动态分区分配算法

首次适应算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法

又称最大适应算法（Largest Fit）

算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

对比

基本分页存储管理的基本概念

页号 = 逻辑地址 / 页面长度（取除法的整数部分）

页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）

基本地址变换机构

快表TLB

快表，又称联想寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90% 以上。

两级页表

基本分段存储管理方式

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

段页式管理

虚拟内存的基本概念

请求分页管理方式

请求分页存储管理与基本分页存储管理的主要区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

页面置换算法

最佳置换算法（OPT）

最佳置换算法（OPT，Optimal）：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块

Belady 异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有 FIFO 算法会产生 Belady 异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

最近最久未使用置换算法（LRU）

最近最久未使用置换算法（LRU，least recently used）：每次淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。

时钟置换算法（CLOCK）

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）

简单的CLOCK 算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK 算法选择一个淘汰页面最多会经过两轮扫描

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过

各置换算法对比

页面分配策略

驻留集:指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）

可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

可变分配全局置换：只要缺页就给分配新物理块

可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块

内存映射文件

文件管理

文件的逻辑结构

文件目录

文件的物理结构

文件分配方式——连续分配

连续分配的文件在顺序读/写时速度最快
物理上采用连续分配的文件不方便拓展。
物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

文件分配方式——链接分配

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高。

缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间

显示链接分配

显式链接——把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点：文件分配表的需要占用一定的存储空间。

文件分配方式——索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

如果一个文件的大小超过了256 块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？

①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放
②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块
③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。

总结

文件存储空间管理

对空闲磁盘块管理

空闲表法

空闲链表法

操作系统保存着链头、链尾指针。

如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

位示图法

成组链接法

如何分配？ Eg ：需要1个空闲块 ①检查第一个分组的块数是否足够。1<100，因此是足够的。 ②分配第一个分组中的1个空闲块，并修改相应数据

Eg ：需要100个空闲块 ①检查第一个分组的块数是否足够。100=100，是足够的。 ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此 300号块的数据需要复制到超级块中。

如何回收？ Eg ：假设每个分组最多为100 个空闲块，此时第一个分组已有99个块，还要再回收一块

如何回收？ Eg ：假设每个分组最多为100 个空闲块，此时第一个分组已有100个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

总结

文件的基本操作

文件共享

基于索引结点的共享方式（硬链接）

基于符号链的共享方式（软链接）

文件保护

口令保护、加密保护、访问控制

注意访问控制，最少需要描述文件位数为组数*访问权限数

如linux中三组ago为rworworwo

文件系统的层次结构

文件系统的全局结构(布局)

文件系统在外存中的结构

文件系统在内存中的结构与open系统调用打开文件的背后过程

注：近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速度

虚拟文件系统 & 文件系统挂载（安装）

虚拟文件系统的特点：

①向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异

②VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求

存在的问题：不同的文件系统，表示文件数据结构各不相同。打开文件后，其在内存中的表示就不同

输入输出管理

磁盘与固态硬盘

磁盘结构

柱面号->磁道盘面好->磁盘扇区号->扇区

磁盘调度算法

注意：若题目中无特别说明，则SCAN 就是 LOOK， C-SCAN 就是C-LOOK

一次磁盘读/写操作需要的时间

先来先服务调度算法(FCFS)

最短寻找时间优先（SSTF）

扫描算法（SCAN）

LOOK 调度算法

循环扫描算法（C-SCAN）

C-LOOK 调度算法

总结

减少延迟时间的方法

交替编号

思考：为什么？磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）

答：读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间

错位命名

磁盘的管理

磁盘初始化

Step 1：进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC 循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）
Step 2：将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的 C盘、D盘、E盘）
Step 3：进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表）

引导块

坏块的管理

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在 FAT 表上标明。（在这种方式中，坏块对操作系统不透明）

对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。

在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。

会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

固态硬盘

I/O设备的基本概念和分类

什么是I/O设备?

“I/O” 就是 “输入/输出”（Input/Output） I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件。

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

I/O设备的分类——按使用特性

人机交互类外部设备（数据传输速度慢）
存储设备（数据传输速度块）
网络通信设备（传输速度介于上述二者之间）

I/O设备的分类——按传输速率分类

低速设备（鼠标键盘）
中速设备（激光打印机）
高速设备（磁盘）

I/O设备的分类——按信息交换的单位分类

块设备（传输速率较高，可寻址，即对它可随机地读/写任一块）
字符设备（传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式）

I/O控制器

I/O设备由机械部件和电子部件组成

I/O控制器的功能

接受识别CPU发出的命令
- 如CPU发来的 read/write 命令，I/O 控制器中会有相应的控制寄存器来存放命令和参数
向CPU报告设备的状态
- I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如： 1表示空闲，0表示忙碌
数据交换
- I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据
地址识别
- 类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器

值得注意的小细节：

①一个I/O控制器可能会对应多个设备；

②数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址。

内存映像I/O v.s. 寄存器独立编址

I/O控制方式

程序直接控制方式

中断驱动方式

引入中断机制。由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O 完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。

注意：

①CPU会在每个指令周期的末尾检查中断

②中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能

DMA方式

与“中断驱动方式”相比，DMA方式（ Direct Memory Access，直接存储器存取。主要用于块设备的 I/O控制）有这样几个改进

①数据的传送单位是“块”。不再是一个字、一个字的传送；

②数据的流向是从设备直接放入内存，或者从内存直接到设备。不再需要CPU作为“快递小哥”。

③仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。

通道控制方式

通道：一种硬件，可以理解为是 “弱鸡版的CPU”。通道可以识别并执行一系列通道指令

I/O软件层次结构

用户层软件
设备独立性软件
- (设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。)
设备驱动程序
中断处理程序
硬件

输入/输出应用程序接口 & 设备驱动程序接口

阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待。 eg：字符设备接口——从键盘读一个字符 get

非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。 eg：块设备接口——往磁盘写数据 write

设备驱动程序接口

不同的操作系统，对设备驱动程序接口的标准各不相同。

设备厂商必须根据操作系统的接口要求，开发相应的设备驱动程序，设备才能被使用

I/O核心子系统

假脱机技术（SPOOLing技术）

SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

设备的分配与回收

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。

独占设备——一个时段只能分配给一个进程（如打印机）
共享设备——可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。
虚拟设备——采用 SPOOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用 SPOOLing 技术实现的共享打印机)

从进程运行的安全性上考虑，设备分配有两种方式：

安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。（eg：考虑进程请求打印机打印输出的例子）
- 一个时段内每个进程只能使用一个设备
- 优点：破坏了“请求和保持”条件，不会死锁
- 缺点：对于一个进程来说，CPU和I/O设备只能串行工作
不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。
- 一个进程可以同时使用多个设备
- 优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进
- 缺点：有可能发生死锁（死锁避免、死锁的检测和解除）

静态分配和动态分配

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏了“请求和保持”条件，不会发生死锁）

动态分配：进程运行过程中动态申请设备资源

设备分配管理中的数据结构

缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区

缓冲区的作用

缓和CPU与I/O设备之间的速度不匹配
减少对CPU的中断频率，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题
提高CPU与I/O设备之间的并行性

单缓冲

双缓冲

假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）

双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空

结论：采用双缓冲策略，处理一个数据块的平均耗时为 Max (T, C+M)

使用单/双缓冲在通信时的区别

若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。

若两个相互通信的机器设置双缓冲区，则同一时刻可以实现双向的数据传输。

循环缓冲区

缓冲池

用户进程

从空缓冲队列中取出一块作为收容输入数据的工作缓冲区（hin）。冲满数据后将缓冲区挂到输入队列队尾
从输入队列中取得一块冲满输入数据的缓冲区作为 “提取输入数据的工作缓冲区（sin）”。缓冲区读空后挂到空缓冲区队列
从空缓冲队列中取出一块作为“收容输出数据的工作缓冲区（hout）”。数据冲满后将缓冲区挂到输出队列队尾
从输出队列中取得一块冲满输出数据的缓冲区作为 “提取输出数据的工作缓冲区（sout）”。缓冲区读空后挂到空缓冲区队列

知识总览

Post Views: 2,059

赞赏

微信赞赏支付宝赞赏

计算机系统概述

操作系统的基本概念

概念功能

特征

操作系统的发展与分类

操作系统运行环境

运行机制

中断

中断的分类

中断的基本原理

系统调用

操作系统体系结构

操作系统引导

虚拟机

进程和线程

进程与线程

进程概念

进程的状态与转换

进程控制

进程间通信

线程概念

处理机调度

概念

调度算法评价指标

进程调度的时机、切换与过程

调度算法

先来先服务

最短作业优先

最高响应比优先

时间片轮转

优先级调度

多级反馈队列

多级队列调度

同步与互斥

同步互斥概念

进程互斥的软件实现方法

硬件实现方法

互斥锁

信号量

用信号量机制实现进程互斥、同 步、前驱关系

生产者消费者问题

多生产者多消费者

吸烟者问题

读者写者问题

哲学家就餐问题

管程

死锁

概念

死锁的处理策略

预防死锁

避免死锁

检测和解除

内存管理

内存的基础知识

内存管理

覆盖与交换

连续分配管理方式

动态分区分配算法

首次适应算法

最佳适应算法

最坏适应算法

邻近适应算法

对比

基本分页存储管理的基本概念

基本地址变换机构

快表TLB

两级页表

基本分段存储管理方式

段页式管理

虚拟内存的基本概念

请求分页管理方式

页面置换算法

最佳置换算法（OPT）

先进先出置换算法（FIFO）

最近最久未使用置换算法（LRU）

时钟置换算法（CLOCK）

改进型的时钟置换算法

各置换算法对比

页面分配策略

内存映射文件

用信号量机制实现进程互斥、同步、前驱关系

假脱机技术（SPOOLing技术）

发表回复取消回复