发布日期: 2023-04-19

更新日期: 2023-04-19

文章字数: 6.8k

阅读时长: 23 分

阅读次数:

OS期中复习笔记

操作系统引论

异常

异步异常

中断(interrupt)分为：

可屏蔽中断，例如：所有IRQ中断
不可屏蔽中断，例如：电源掉电和物理存储器奇偶校验

均是来自I/O设备的信号，返回到下一条指令

同步异常

陷阱(trap)

程序内部有意的设置，返回下一条指令，例如：系统调用，信号机制（通过中断指令实现）

故障(fault)

潜在的客回复的错误，返回到当前指令，例如：缺页异常，除0错误，段错误

终止

不可恢复的错误，不返回任何值，例如：硬件错误

操作系统的特征

操作系统的基本特征包括：并发，共享，虚拟和异步。

并发

两个或多个事件在同一时间间隔内发生。计算机系统中同时存在多个运行的程序。

共享

资源共享，分为两种

互斥共享方式
同时访问方式

虚拟

指把一个物理上的尸体变为若干逻辑上的对应物。使用户有在使用真正的东西的感觉

异步

多道程序并发执行，但是由于资源有限，进程的执行并不是一贯到底的，以不可预知的速度前进。

操作系统的目标和功能

作为计算机系统资源的管理者

主要有以下几种功能

处理机管理（处理机的分配和运行都以进程为基本单位美因茨队处理机的管理可以归结为对进程的管理）
存储器管理：包括内存分配与回收，地址映射内存保护与共享和内存扩充
文件管理
设备管理：主要是完成用户的I/O请求，方便用户使用各种设备。

作为用户与计算机硬件系统之间的接口

命令接口

分为两种：

联机命令接口：又称交互式命令接口，适用于分时或者实时系统的接口。
脱机命令接口：又称批处理命令接口，适用于批处理系统。

程序接口

由一系列系统调用（又称广义指令）组成系统调用时操作系统为应用程序内核功能提供的接口，是操作系统为编程人员提供的接口。

对计算机资源的扩充

操作系统将裸机改造成了功能功能强，使用更方便的机器，因此：覆盖率软件的及其称为扩充机器或者虚拟机。

操作系统发展史

批处理系统

内存中始终保持一道作业，对作业的处理时成批进行的。

分时操作系统

按照时间片轮流把处理器分配给各个练级总也使用，若莫耳骨作业在分配给他的时间片内无法完成起计算，咋改作业暂停运行，每个用户都感觉自己在独占一台计算机。主要特征如下：

同时性(多路性)，允许多个终端用户同时使用一台计算机
交互性，用户可以方便的与系统进行人机对话
独立性，系统中多个用户可以彼此独立德进行操作，互不干扰
及时性，用户可以在很短的时间内获得响应

在设计分时操作系统时，首先需要考虑系统的交互性与响应时间。
与批处理系统相比，由于系统切换，其开销很大

实时操作系统

及时性与可靠性，其响应时间非常快，而且对系统的安全性要求很高（时间比分时更短，而且交互性不如分时操作系统）

一些tips

用户只能通过系统调用间接使用资源，比如当用户想要直接管理内存时会通过一个trap指令进入内核态进行资源管理。
这些操作需要切换到内核态：
- 系统调用，执行IO指令，修改中断向量
这些操作不需要切换到内核态
- 通用寄存器清零
操作系统会被加载到RAM
操作系统的局部性：操作系统往往会倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。

操作系统的启动流程：

打开计算机
CPU跳转到BIOS的物理地址
BIOS上电自检
寻找需要启动的设备
从MBR上加载执行启动程序
加载OS

比较重要的有两点：BIOS主要完成硬件初始化的相关工作，磁盘上的MBR用来引导操作系统

注意哈，BIOS的执行过程和操作系统无关，bootloader可以支持不同的CPU架构，可以支持不同操作系统的启动

操作系统结构

分层法

分层法是将操作系统分成若干曾，最底层为硬件，最高层为用户接口，每层只能调用紧邻他的低层的功能和服务（单向依赖）
分层法的优点：
- 便于系统的调试与验证
- 易扩充易维护
分层法的缺点：
- 合理定义各层比较困难
- 效率差，各层之间的通信效率低，有额外开销

模块化

模块化：将操作系统按照功能划分称为若干具有一定独立性的模块，每个模块都具有某方面的管理功能，并规定好的模块间的接口，使各模块之间能够通过接口通信，还可以进一步细分各个模块。其独立性主要有两个标准：内聚性，耦合度
- 模块化的优点：1.提高了操作系统设计的正确性，可理解性和可维护性，2.增强了操作系统的可适应性。3.加速了操作系统的开发过程
- 模块化的缺点：1.模块间的接口规定很难满足对接口的实际需求。2.各模块设计者齐头并进，每个决定无法解决在上一个已验证的正确决定的基础上，因此无法找到一个可靠的决定顺序。

宏内核&微内核

宏内核是指将系统的主要功能模块都作为一个紧密联系的整体运行的核心态，从而为用户程序提供高性能系统服务。
微内核是指将内核中的最基本功能保存在内核，而将那些不需要在核心态执行的功能移动到用户态执行，从而降低内核的设计复杂性。微内核的基本功能有：
- 进程管理
- 低级存储器管理
- 中断与陷入处理
微内核的特点
- 扩展性和灵活性
- 可靠性与安全性
- 可移植性
- 分布式计算
- 不断切换用户态与内核态，开销大，性能一般，很难说性能优越

外核

略

内存管理

存储管理基础

ELF目标代码文件是由section组成的，而可执行文件的内容是由segment组成
链接器将相同类型的section合并成segment
ELF文件中
- .text保存可执行文件的指令操作（由系统从可执行文件中加载）
- .data保存已经初始化的全局变量和静态变量
- .bss保存未初始化的全局变量和静态变量(static 型变量初始化为0的时候，它也会在.bss而非.data)
.data,.text均在可执行文件中加载，.bss由系统初始化
栈(stack)：存放交换临时数据的内存区
堆(heap)：存放进程运行中动态分配的内存段，他的大小并不固定，当进程调用malloc等函数分配内存，此乃分配的内存就被动态添加到堆上，利用free等桉树释放内存时，被释放的内存就从堆中被剔除
执行程序的过程：

shell调用fork()创建子进程
子进程调用execve()加载program

一个segment在文件中的大小是小于等于其在内存中的大小

基础内存管理

闲置空间管理：位图表示法，链表表示法

单道程序

单道程序：静态地址翻译（在程序运行之前就计算出所有的物理地址）

多道程序

方法：固定（静态）式分区分配，程序适应分区；可变（动态）式区分配，分区适应程序。
固定式分区：把内存分成若干个固定大小的连续分区
可变式分区：分区的边界可以移动，分区大小可以改变

基于顺序搜多的分配算法：适用于小型系统

First Fit：优先利用内存低地址的部分空闲分区，会出现很多外碎片，可能会导致程序沉积在内存的一端
Next Fit：存储空间的利用更加均衡，不会导致肖的坑先分区集中在存储器的一端，但是会导致缺乏大的空闲分区
Best Fit：保留了大的空闲分区，有很多小碎片
Worst Fit：大作业往往得不到妈祖

基于索引搜索的分配算法：适用于大中系统

快速适应算法：

优点：查找效率高，仅需要根据程序的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可，在该算法分配时，不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。
缺点：在分归还主存时算法复杂，系统开销很大，在分配空闲空间时是以进程为单位，一个分区只属于一个进程，存在一定的浪费，空间换时间。

伙伴系统：不停分割，每个碎片均为2的次幂，缺点是有很多内碎片

碎片：内存中无法被利用的存储空间

内碎片：分配给作业的存储空间中未被利用的部分，例如固定分区中存在的碎片
外碎片：系统中无法利用的小的空闲分区，如分区与分区之间的碎片。外碎片才是造成内存系统性能下降的主要原因，外碎片可以被紧凑技术清楚

分区保护：峰值一个作业破坏其他作业或者系统

界限寄存器方法
存储保护键方法

覆盖与交换技术：多道程序环境下用来扩充内存的方法

可以解决小内存运行大足以的问题
覆盖是一个作业太大，得让后面装载的把前面装载的给覆盖掉，所以要程序员标记好哪些段是可以被后面的段覆盖掉的。
交换是把暂时不用的某个（或某些）程序及其数据的部分或全部从主存移到辅存中去，提高了并发的数量。
交换对程序员来说时透明的，覆盖段由程序员亲自划分

页式存储管理

作业包括程序，数据，操作说明
进程包括程序，数据集合
纯分页系统：不具备页面交换功能，不支持虚拟存储器功能
页：在分页存储管理系统中，把每个作业的地址空间分成一些大小相等的片，称之为页面（Page）或页，各页从0开始编号。
储存块：在分页存储管理系统中，把主存的存储空间也分成与页面相同大小的片，这些片称为存储块，或称为页框（Frame），同样从0开始编号。
为了便于在内存找到进程的每个页面所对应块，分页系统中为每个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。页表项中存的Valid若其为0，则它还没有被分配相应的物理页框，访问该页内容会发生缺页异常，该页的内容可能存储在磁盘上，还有外存地址和修改位等等。
分页储存管理有效解决了程序离散存放和存储器内碎片的问题，提高了储存器的利用率。

段式存储管理

段表：记录段与内存位置的对应关系
访问一个字节的数据需要访问两次内存（段表一次，内存一次）
逻辑地址由短号与段内地址组成
可重入代码：允许多个进程同时访问的代码，不允许任何进程对其进行修改

段页式存储管理

用分段方法分配和管理虚拟存储器，分页方法分配和管理实存储器

虚拟存储管理

虚拟存储技术的特征：离散性，多次性（多次调入内存），对换性（允许换入换出），虚拟性（从逻辑骄傲都访问存储器，不考虑你物理内存上的可用空间数量）
交换分区：一段连续按页划分的磁盘空间，在物理内存不够的情况下，操作系统先从把内存中暂时不用的数据存到交换分区
页面置换策略：
- 最优置换（OPT）：有一个页面申请串，此时又要换掉一个页面，要被换掉的页面是在串中最久要被用到的，即换掉最久不使用的页。
- FIFO：Belagy现象：分配的缺页增多，但是缺页率反而增高了
- 改进的FIFO：
  - Secong Chance：通过增加访问标志位，给予页面“二次机会”，A是FIFO队列中最旧的页面，且其放入队列后没有被再次访问，则A被立刻淘汰；否则如果放入队列后被访问过，则将A移到FIFO队列头，并且将访问标志位清除。如果所有的页面都被访问过，则经过一次循环后就会按照FIFO的原则淘汰。
  - Clock：做成一个循环队列，永远指向最久的页面。逻辑和二次机会一致
- LRU：类似于设置一个特殊的栈，保存当前使用的各个页面的页面号。重点是访问到了一个在缓存中的页时，要放到栈顶。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈底始终是最近最久未使用页面的页面号。
进程的工作集：当前正在使用的页面集合
进程的驻留集：虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分配的物理页框集合
关于缺页中断：在请求分页系统中，当要访问的页面不在内存中就会发生缺页中断，当查找页表发现valid位是0时页发生缺页中断，将该进程阻塞，如果有空闲块，则讲该页直接装入，并且修改对应的页表项，如果无空闲块，根据页面置换策略选择将某个内存块置换置换恢复CPU环境，继续执行。

分配模式：

页面分配策略

固定分配策略：为每个活跃的进程分配固定数量的页框，驻留集尺寸不变
可变分配策略

页面置换策略：

局部置换：系统在进程自身的驻留集中判断当前是否存在空闲页面，并在其中进行置换
全局置换策略：在整个内存空间中判断有无空闲页面，并允许从其他进程的驻留集中选择一个页面换出内存

分配模式与置换模式的搭配：固定分配策略只能采用局部置换策略，可变分配策略采用全局置换策略和局部置换策略

抖动问题：

随着驻留在内存中的进程数目增加，处理器利用率先上升后下降
消除与预防：局部置换策略，引入工作集算法，预留部分页面，挂起若干进程

进程与线程

一些概念

并发：若干个程序同时在系统中运行，这些程序的执行在时间上是重叠的
并行
竞争：多个进程在读写一个共享数据时结果依赖于他们执行的相对时间
竞争条件：多个进程并发访问和操作统一数据且执行结果与访问的特定顺序有关称为竞争条件
$Bernstein条件$
$$
进程S_1和进程S_2可并发当且仅当
$$
$$
R(S_1) \cap W(S_2) = \emptyset
$$
$$
R(S_2) \cap W(S_1) = \emptyset
$$
$$
W(S_1) \cap W(S_2) = \emptyset
$$
中断是进程并发的必要条件，没有中断的话操作系统不能获得系统的控制权，无法按照调度算法对处理机进行重新分配，一个程序将一直运行到结束

进程

进程的定义与特征：

进程是程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位
进程的组成包括程序、数据、进程控制块

进程的状态：

就绪态，执行态，阻塞态

转化关系：

执行态–(时间片到)–>就绪态
就绪态–(调度)–>执行态
阻塞态–(事件发生)–>就绪态
执行态–(等待某个事件)–>阻塞态

操作系统在进程管理方面的五项主要活动是：进程控制，进程同步，进程调度，进程通信，死锁

进程的互斥与同步

互斥：两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥。
同步：系统中各进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性的过程称为进程同步。作而相互等待、相互交换信息所产生的制约关系。

线程

线程包括了两个概念：资源拥有者和可执行单元

进程：资源拥有者
线程：可执行单元

引入线程的目的：

减小进程切换的开销
提高程序内的并发程度
共享资源

线程共享资源的同时，有自己的私有的栈

线程的实现方式

用户级线程：library模拟
内核级线程：kernel多个分身，支持内核线程的操作系统被称为多线程内核
两种线程的比较：
- 内核级线程是操作系统内核可感知的，而用户级线程是操作系统不可感知的
- 用户级线程的创建撤销和调度不需要操作系统内核的支持，是在语言或用户库这一级处理的，而内核支持线程的创建撤销和调度都需要操作系统内核提供支持
- 用户及线程执行系统调用的时候导致所属进程被中断，而内核级线程只导致该线程中断
用户级线程在用户空间通过库函数实现，无需内核支持也不参与内核的调度，由用户程序自行调用、调度和维护。用户级线程不受内核时钟中断的影响，但如果其所在的进程时间片用完，自然整个进程的所有线程都会让出CPU。
内核级线程由内核调度和维护，是可以被时钟中断单独剥夺CPU使用权的。
对于混合线程实现方式，用户级线程和内核级线程之间有映射关系，一个线程是否会被时钟剥夺CPU使用权取决于其由哪一方控制。不论是Many-to-One, One-to-One, 还是Many-to-Many，其映射中内核级线程是可以被时钟中断剥夺CPU使用权的，而用户级线程的情况取决于其所映射的内核级线程，一旦内核级线程被剥夺CPU使用权，其所映射的用户级线程都将让出CPU。
有些系统同时支持用户线程和内核线程，产生了不同的多线程模式Many-to-one,One-to-One,Many-to-Many

进程同步

临界资源：一次只允许一个进程访问的资源
临界区：每个进程中访问临界资源的那段代码
进程互斥：：两个及以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥
进程同步：系统中各进程之间能有效共享资源和相互合作，从而使程序的执行具有可再现性的过程称为进程同步

基于忙等待的互斥方法

软件方法：Dekker算法，Peterson算法，面包店算法
Dekker算法

P:
...
    pturn=true;
    while(qturn) {
        if(turn ==1) {
            pturn=false;
            while(turn==1);
            pturn=true;
        }       
    }
临界区
    turn = 1;
    pturn=false;
...

Q:
...
    qturn=true;
    while(pturn) {
        if(turn ==0) {
            qturn=false;
            while(turn==0);
            qturn=true;
        }
    }
临界区
turn = 0;
qturn=false;
...

Peterson算法

void enter_region (int process){
    int other;
    other = 1 - process;
    interested[process] = true;
    turn = process;
    while(turn == process && interested[other] == TURE);
}

void leave_region(int process) {
    interested[process] = FALSE;
}

进程i:
... ...
enter_region(i);
临界区
leave_region(i);
... ...

面包库算法

Entry Section (i) { // i  process i
while (true) {
    Choosing[i] = 1;
    Number[i] = 1 + max(Number[1],...,Number[N]);
    Choosing [i] = 0;
    for (j=1; j＜=N; ++j) {
        while (Choosing[j] != 0) { }
            // wait until process j receives its number
        while ((Number[j]!=0) && ((Number[j],j) ＜(Number[i],i))) { }
            // wait until processes with smaller numbers, or with the 
            // same number, but with higher priority, finish their work
    }
    // critical section...
    Number[i] = 0;
    // non-critical section...
    }
}

硬件方法：中断屏蔽，使用test and set指令，使用swap指令
- 中断屏蔽方法：使用“开关中断”指令，
  - 优点：简单。
  - 缺点：不适用于多CPU系统，往往会带来很大的性能损失
  - 的那处理器使用，适用于内核进程（少量使用）
- test and set指令：自锁，是不会被中断的原子指令
- swap指令：Swap（对换）指令与TSL指令一样，是不会被中断的原子指令，其功能是交换两个字的内容

共性问题：

忙等待：浪费CPU时间
优先级反转：优先级低的进程先进入临界区，高优先级进程一直忙等

基于信号量的同步方法

信号量的定义：一个确定的二元组$(s,p)$，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列
二元信号量：只能为0或1，主要实现互斥
一般信号量：处置为可用物理资源的总数，用于进程间的写作同步问题
强信号量：进曾从被阻塞队列释放时采取FIFO
弱信号量：没有规定从阻塞队列中移除顺序
信号量的物理意义：信号量的值为正时，表示系统中某类资源的数量；为负时，表示等待进程个数。

P(S):
while(S <= 0);
S--;

V(S):
S++;

优点：PV操作可以解决一切互斥与同步的问题。
缺点：PV操作不够安全，可能产生死锁，而且加重了编程的负担
信号量集机制：包括AND型信号量和一般信号量集
- AND型信号量集
  - 基本思想：将进程所需的全部共享资源一次全部分配给它，待改进昵称使用完后一起释放
- 一般信号量集
  - 基本思想：SP(S1,t1(测试值),d1(占用值))

进程间通信

低级通信：只能传递状态和整数值，包括进程互斥和同步采用的信号量和管程机制
高级通信：适用于分布式系统，基于共享内存的多处理机系统，单处理机系统，能够传递任意数量的数据，可以解决进程的同步问题和通信问题，主要包括：管道，共享内存，消息队列
无名管道只能用于具有亲缘关系的进程，有名管道克服了这一点
管道是半双工通信，要实现父子进程双方互动通信需要定义两个管道
一个进程要向另一个进程传送大量数据，如不考虑进程间的同步，效率最高的进程间通讯机制是共享内存。

管程

操作系统中的一种同步与互斥机制，由共享资源的数据及其在该数据上的一组操作组成，则该机制称为管程。
互斥：任一时刻，管程中只能有一个活跃进程
管程是一种语言概念，由编译器负责实现互斥

经典的进程同步与互斥问题

生产者-消费者问题

若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作

semaphore mutex = 1;//互斥
semaphore empty = N;//空闲数量
semaphore full = 0;//产品数量

main() {
    Cobegin
    producer();
    consumer();
    Coend
}

producer() {
    while(true){
        生产产品nextp;
        P(empty);
        P(mutex);
        buffer[in] = nextp;
        in = (in + 1) MOD n;
        V(mutex);
        V(full);
    }
}


consumer() {
    while(true){
        P(full);
        P(mutex);
        nextc = buffer[out];
        out = (out + 1) MOD n;
        V(mutex);
        V(empty);
        消费nextc中的产品
    }
}