操作系统学习笔记

2019-08-09

字数统计: 5.7k字 | 阅读时长: 20分

参加秋招前，复习的操作系统笔记。

中断和异常

概念

中断发生时，CPU进入核心态，当前执行的进程暂停，内核对中断进行处理
中断是让CPU从用户态切换到核心态的唯一方法，使操作系统获得计算机的控制权
用户态就是应用程序的活动区间，当它们需要使用I/O资源、CPU资源时，需要进行系统调用
内核从本质上来说就是控制计算机各类资源的软件，为应用程序提供运行环境

分类

内中断：来自CPU内部，跟当前执行指令有关（指令错误，缺页处理、trap）
外中断，来自CPU外部，跟当前执行指令无关（I/O反馈等）

进程和线程

进程

进程 = 程序段（程序代码）+ 数据段 + PCB（进程控制块）
PCB：进程ID；用户ID；进程状态和执行优先级；资源指针；寄存器，如记录当前程序执行到了哪句指令。

进程状态：运行态（占有CPU并运行）、就绪态（万事俱备，只欠CPU）、阻塞态（等待某一事件）

创建进程：分配独立资源，创建PCB
销毁进程：回收资源，撤销PCB

就绪->运行进程调度
运行->就绪时间片轮转，或者被高优先级进程抢占
运行->阻塞请求资源分配，或等待事件发生
阻塞->就绪资源到手，只差CPU

进程通信

共享存储，消息传递，管道等
进程是资源分配的基本单位，各个进程之间资源相对独立

共享空间

共享空间的访问是互斥的，基于数据结构的分享和基于存储区的分享

管道通信

管道其实就是一个用于连接读写进程的共享文件，在内存中开辟一个固定大小的缓冲区

半双工通信（某个时间段只能实现单向传输，如需双向同时传输，可以设两个管道）
进程访问管道是互斥的
没写完不能读，没读完不能写
最多只能有一个读进程

消息传递

以格式化消息为单位，消息包括：消息头，消息体

消息头包括发送进程ID，接收进程ID，消息类型、长度等内容（类似于报头）

每个进程都有一个消息缓冲队列，可以直接放到接收方的队列
（还可以一个信箱作为中间载体，管理进程间的消息收发）

线程

有的进程可能需要同时做很多事，但传统进程只能串行执行某一程序段，引入线程，增加并发度

引入线程后，提高了并发度，减少了系统开销，切换线程时不需要切换进程环境，所以开销小

属性

是CPU调度的基本单位
有线程ID和线程控制块TCB
同一进程的不同线程共享进程资源
同一进程的不同线程通信无需系统干预
同一进程的线程切换不引起进程切换
切换同一进程的线程，开销小

进程和线程的区别

进程拥有独立的内存空间，当进程崩溃时不会影响其他进程，而同一进程的线程之间内存共享，当线程崩溃时会导致进程崩溃，所以多进程程序相较于多线程程序有更好的健壮性；
多线程程序的并发效率更高，对于一些需要同时进行又要共享数据的并发操作，只能用线程。

处理机调度

资源数量并不能满足为多进程同时服务的需求，因此处理机需要确定某种规则来合理决定进程执行的顺序。

先来先服务
根据作业到达的时间先后顺序进行服务
非抢占式
算法简单、但容易让短作业体验极差
不会饥饿
短作业优先
最少平均带权周转时间
导致饥饿
高响应比优先
折合考虑等待时间和运行时间
不会饥饿
时间片轮转
若未能在时间片内运行完，被抢占
时间片太大：先来先服务
时间片太小：进程切换频繁，系统花费大量时间处理进程切换
优先级调度
有抢占式和非抢占式
动态优先级和静态优先级
多级反馈队列

管程解决生产者消费者问题

1.定义共享数据（比如生产者消费者中的缓冲区）
2.设定一些访问共享数据的入口，并保证只有通过入口才能访问到共享数据
3.每次只能有一个入口被访问，这些互斥特性是编译器实现的，不需程序员关心
4.访问完数据后，记得归还入口。

通过函数封装的方法，让程序员不用关心复杂的细节，就能很方便的实现进程同步/互斥了。

进程同步

异步性：并发执行的进程各自独立，速度未知

进程同步机制，来实现进程并发时的限定顺序，保证正常执行
eg：管道通信的读写进程，并发异步，但需要保证写进程->读进程，所以需要引入同步制约关系

互斥

系统中某些资源在一个时间段内只能提供给一个进程访问
一个时间段内只能提供给一个进程访问的资源，叫做临界资源

对临界资源访问过程：

do{
//进入区 检查是否还有临界资源，如果有，进入临界区，并且上锁
//临界区 访问临界资源
//退出区 解除锁
//剩余区 其他处理
}while(true)

为实现对临界资源的互斥访问，又要保证系统整体性能：

空闲让进，临界区空闲时让进程进入
忙则等待，已被占用时让进程有限等待
有限等待，应保证在有限时间内能进入临界区，不会饥饿
让权等待，当进程不能进入临界区时，释放CPU，避免忙等（不要占用处理机）

代码实现

单标识法
1
int turn = 0;//表示当前允许进入临界区的进程号
违背空闲让进原则，只有当turn指向的进程完成访问后才修改turn的值，这时候该进程如果占用了且不访问，就造成别的进程不能访问。
双标志前检查法
1
bool flag[2] 标记各进程是否想进入，并且检查其他进程是否进入
违背忙则等待原则，因为一开始都是false，然后同时检查，执行read还没来得及write，于是同时进入。
双标志后检查法
可能导致饥饿

其实互斥代码实现中，也存在一些问题，由于进程异步性导致一系列问题。

petersen算法

1.主动争取
2.主动谦让
3.检查对方是否也想要，且最近是不是自己谦让
可能忙等。

在双标志检查法中，检查和上锁操作无法一气呵成，导致两个进程可能同时进入临界区
所有方法都无法实现让权等待原则。

硬件实现

中断屏蔽

1
2
3

关中断//进程开始访问临界区到结束访问这段时间里不可被中断，也就不会发生进程切换
临界区
开中断

简单高效，但不适用于多处理机，不适用于用户进程，只适用于内核进程（内核态指令）

TestAndSet 指令

bool TestAndSet(bool *lock){
    bool old = *lock;
    *lock = true;
    return old;
}

while(TestAndSet(&lock));
//临界区
lock = false;
//剩余区

一开始是false，则返回false，进入临界区
一开始是true，则一直是true，直到访问临界区的进程执行lock=false的指令

TSL指令把上锁和解锁变成了一气呵成的原子操作，实现简单，使用于多处理机环境
不满足让权等待原则，当进入while循环后不会让出CPU，从而出现忙等。

swap指令

bool old = true
while(old == true)swap(lock , old);
//临界区
lock = false;
//剩余区

信号量机制

原语指的是一气呵成执行，不可被中断的程序段
信号量可以看作是一个变量，可以用来表示一种资源

wait 和 signal，简称为p v操作（一对原语）
1
2
3
4
5
6
7
8
9
//以打印机为例子
int s=1;
void wait(int s){//相当于进入区
while(s<=0);
s--;
}
void signal(int s){//相当于退出区
s++;
}
类似于双标志先检查法，但由于是原语操作，避免了并发异步导致的问题
不满足让权等待原则，会出现忙等

以上是整型信号量，如果采用记录型信号量，可避免忙等

typedef struct{
    int s;
    struct process *queue;
}semaphore;
void wait(semaphore s){
    --s.s;
    if(s.s<0)block(s.queue);
    //block原语可以让队首进程从运行态进入阻塞态
}
void signal(semaphore s){
    ++s.s;
    if(s.s<=0)wakeup(s.queue);
    //wakeup原语唤醒队列里等待的进程，从阻塞态进入就绪态
}

遵循了让权等待原则，不会出现忙等现象

信号量机制实现同步

初始化同步信号量为0

在前操作之后进行signal，在后操作之前进行wait

int s=0;
progress 1
//1
//2
wait(s)
//3

progress 2
//4
wait(s)
//5
//6

生产者-消费者问题

缓冲区没满，生产者才能把产品放入缓冲区，否则必须等待（同步问题）
缓冲区没空，消费者才能把产品拿出缓冲区，否则必须等待（同步问题）
缓冲区是临界资源，各进程必须互斥的访问，不然可能生产者产品覆盖（互斥问题）

问题转化为：
生产者每次消耗一个空闲缓冲区，释放一个产品；
消费者每次消耗一个产品，释放一个缓冲区；
消耗就是wait操作，释放就是signal操作；

semaphore mutex = 1;//实现临界区访问互斥
semaphore empty = n;//记录空闲缓冲区数量
semaphore full  = 0;//记录填满的缓冲区数量

生产者(){
    while(1){
        produce;
        wait(empty);
        wait(mutex);
        put produce;
        signal(mutex);
        signal(full);
    }
}

消费者(){
    while(1){
        consume;
        wait(full);
        wait(mutex);
        get produce;
        signal(mutex);
        signal(empty);
    }
}

实现互斥的P操作一定要放在实现同步的P操作之后，这样才能避免死锁

写者-读者问题

读者只读不修改缓冲区，而写者会修改缓冲区，因此读者与读者之间不存在互斥关系。

semaphore rw = 1;//表示当前是否有文件在进行访问
int count=0;//表示当前有几个读者
semaphore mutex = 1;//因为count计算不是原语，可能导致读者不能同时读，因此需要互斥访问count
// semaphore w = 1;//避免写进程饿死，写进程优先
writer(){
    while(1){
        //P(w);
        P(rw);
        write;
        V(rw);
        //V(w);
    }
}
reader(){
    while(1){
        //P(w);
        P(mutex);
        if(count==0)P(rw);
        count++;
        V(mutex);
        //V(w);
        read;
        P(mutex);
        count--;
        if(count==0)V(rw);
        V(mutex);
    }
}

写进程可能饿死，这时读进程是优先的，加上注释内容后，写进程一旦进入P(w)，就不会有其他新读者进入

所谓写优先，其实是公平的先来先服务，保证了写者不会饿死。

哲学家进餐问题

可以先选择一个人不吃饭，那么剩余的4个人一定能避免死锁并完成吃饭动作；
可以让奇数编号的哲学家拿左边的筷子，而偶数编号的哲学家拿右边的筷子，那么，只要相邻两个哲学家都想吃饭的时候，一定有一个被阻塞。

死锁

在哲学家进餐问题中就可能出现死锁，因为每个哲学家都因在等待资源而被阻塞，即发生死锁。

在并发环境下，各个进程因为竞争资源造成一种互相等待对方手里资源，从而无法向前推进的现象，发生死锁后如果没有外力干涉，这些进程永远无法推进。

死锁、饥饿和死循环的区别：
它们都是进程遇到某种故障导致无法向前推进的现象，但死锁至少有两个或以上的进程同时死锁，发生死锁的进程一定处于阻塞态；而饥饿是一个进程长期得不到资源或处理机，可以在阻塞，也可以是就绪态；死锁和饥饿是操作系统的问题，死循环是程序写出来的bug或者是程序员有意为之。

死锁条件

互斥条件，只有对互斥资源争抢才会导致死锁
不可剥夺，资源只能由进程主动释放，不能由其他进程强行夺走
请求和保持，进程请求当前资源被占用，而手里又保持资源，这就是保持并等待
循环等待，至少2个进程的请求资源占用并形成一个环

对不可剥夺资源的不合适分配，就会导致死锁。

处理策略

预防死锁//破环产生死锁的四个条件

互斥条件把互斥使用的设备改造成可以逻辑上共享的设备，应用并不广
不可剥夺当进程得不到请求的新资源时，马上释放手里所有资源
请求和保持静态分配，如果投入运行就能结束，就全部分配给它
循环等待顺序资源编号法，拥有小编号资源，才能申请大编号资源

避免死锁//银行家算法

熟，略。

死锁检测和解除//系统操作

对资源和进程建有向图

如果按照分析能够消除所有有向边，则不存在死锁，否则存在死锁（相当于能找到一个安全序列）

检测出死锁后：
1.资源剥夺法，挂起死锁进程，抢占它的资源（要考虑长时间挂起的饥饿）
2.撤销进程法，直接强制撤销进程，并剥夺资源，简单粗暴，但功亏一篑
3.进程回退法，选择进程进行回退到死锁前的版本，这就要求系统记录历史版本

那么要考虑：
1.进程优先级
2.进程执行时间
3.还要多久完成
4.用了多少资源
5.进程是批处理还是交互式的（别干交互式的，会让用户不爽）

内存管理

内存连续分配

单一连续分配
分为系统区和用户区，这种分配方式只支持单一程序运行，不支持多道程序运行
优点：简单，无外部碎片，不一定需要内存保护
缺点：只能用于单用户，单任务；有内部碎片（分配给进程的内存区域有没用到的部分），存储器利用率低
固定分区分配
为支持多道批处理系统，将用户空间划分成固定大小的区间，每个分区只装入一道作业
相等分区：缺乏灵活性，适用于作业对象相同的场合
不等分区：提高灵活性，可以满足不同大小进程需求
优点：实现简单，无外部碎片
缺点：产生内部碎片；如果超大程序进来，可能要使用覆盖技术解决，会降低性能
动态分区分配
根据进程大小动态地建立分区
没有内部碎片，但有外部碎片
内部碎片：分配给进程的内存区域有没用到的部分
外部碎片：内存中某些空闲分区由于太小，导致难以利用

局部性原理

时间局部性，最近执行的某条指令或最近访问的某个数据，在接下来可能再次访问
空间局部性，如果程序访问了某个存储单元，那么接下来可能会访问附近的存储单元

快表

页表存放在内存中，快表存放在更加高速的存储器中
根据局部性原理，可以将最近使用过的页表项放入快表
在接下来先看快表，如果快表命中，就不需要再访问内存了，提高了效率
如果快表没命中，再查询内存中的页表

基本分段存储管理

进程的地址空间，是按照程序自身逻辑关系划分成若干个段的，每个段都有段名，每个段从0开始编址

内存分配原则：每个段在内存中占据连续空间，但段与段之间可以不相邻

比如
main函数 0号段放在 40k-42k
X函数 1号段放在 50k-51k
D段 2号段放在 60k-65k

由于按照逻辑功能模块划分，会使得用户编程更方便，程序可读性更高

分段地址结构：段号 + 段内地址（偏移量）
段号长度决定程序最多被分成多少段，段内地址长度决定每个段的最大长度

段表：建立了逻辑段到实际物理内存的一个映射关系

分段、分页的对比

页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存利用率，分页是系统管理的需要，对用户不可见

段是信息的逻辑单位，分段能够更好的满足用户需求，分段对用户是可见的，用户编程时需要显式给出段名

页的大小固定，由系统决定；
段的大小取决于用户编写的程序；

分页的用户进程地址空间是一维的，只需要给出一个记忆符就可以表示一个地址；
分段的用户进程地址空间是二维的，既要给出段名，也要给出段内地址，才能表示一个地址；

分段比分页更容易实现信息的共享和保护
比如生产者消费者问题中，对于临界资源的判断的代码（纯代码、可重入代码）可以作为一个可共享的段，所有生产者和消费者都可以“不修改”的共用这个段，这个段的信息是允许其他进程访问的；
但如果采用分页存储，就会造成难以实现共享。

段页式管理

一个进程，先按照逻辑进行分段，然后对于各个段再进行分页，再将内存划分为相同大小的物理块

逻辑地址结构：段号 + 页号 + 页内偏移量

虚拟内存

传统存储方式（连续分配、非连续分配）的缺点：
一次性全部装入内存后才能运行，导致大作业无法运行；
大量作业不能同时运行，导致并发度下降；
由于局部性原理，实际上装入的很多数据都是不会被访问的，这就导致内存中驻留了大量的暂时用不到的数据，浪费内存资源；

基于局部性原理，提出虚拟内存的概念

高速缓冲思想就是对局部性原理的利用，
1.将近期会频繁访问到的数据放到高速存储器，近期暂时用不到的数据放在低速存储器中。
2.如果要访问的数据不在内存，就要把数据从外存调入内存
3.如果内存不够了，要把暂时用不到的信息换出到外存

虚拟内存：在操作系统管理下，用户看来似乎有一个比实际内存大得多的内存，实际内存大小没有变

虚拟内存的特征：

多次性：无需将作业一次性装入内存，可以多次装入内存
对换性：作业运行时，允许将作业换入换出
虚拟性：逻辑上扩充了内存容量

虚拟内存的实现，建立在离散分配的内存管理方式基础上：

请求分页，请求分段，请求段页式（缺页中断）
操作系统负责调入调出：实现请求调页/调段功能，实现页面/段置换功能

缺页中断机制

每当要访问的页不在内存时，产生一个缺页中断，进程进入阻塞态，直到调页完成后恢复就绪态

如果内存中有空闲块，直接把页面放入空闲块便可；
否则需要调用页面置换算法选择一个页面进行淘汰，如果这个页面在内存期间被修改过，就要写回外存；

页面置换算法

最佳置换：找到最长时间内不会被访问的页面
（理论算法，因为无法提前得知下一次访问页面的时间）
先进先出：淘汰最早进入内存的页面
最近最久未使用：每次淘汰的是最近最久没使用过的页面

颠簸

颠簸本质上是指频繁的页调度行为，具体来讲，进程发生缺页中断，这时，必须置换某一页。
然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。
因此，会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸（抖动）。

如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
否则，还剩下两个办法：终止该进程或增加物理内存容量。