操作系统笔记

红太狼 2022-12-04 01:09 176阅读 0赞

## 一 连续内存分配 ##

1，内存碎片  
内部碎片：进程内部碎片  
外部碎片：进程外部碎片

2，内存分配  
首次匹配：第一次找到的足够大小的内存空间分配给进程  
优点：简单，易于产生更大的空闲块  
缺点：外部碎片，不确定性  
最优匹配：与进程需要的内存空间最合适的内存空间  
优点：小尺寸进程合适  
缺点：慢，微小碎片  
最差匹配：最大的内存空间  
优点：中等尺寸合适  
缺点：慢，大进程无法分配

## 二 非连续内存分配 ##

1，分段  
2，分页，每页大小相等  
由页表完成逻辑地址和真实地址的映射，即页号和帧号  
页内偏移  
多级页表：减少存储占用，即没有真实地址对应的逻辑页  
反向页表

## 三 虚拟内存 ##

1，覆盖技术，同一程序内没有调用关系的代码可以共用一块内存区域  
2，交换技术，用于多进程，闲置进程可以全部放入虚拟内存中  
3，虚存技术，一个进程的内存可以部分放到虚拟内存中，依赖程序的局部性，依赖分页或分段技术  
时间局部性：一段代码的当前执行和下一次执行，一个数据的访问和下一次访问都在较短的时间内  
空间局部性：当前指令和临近指令，当前访问的数据和临近数据在较小的区域内

## 四 页面置换算法 ##

**1，最优页面置换算法**  
产生缺页中断最少的算法

**2，先入先出算法 FIFO**  
产生缺页中断时将最先进入内存的页放入虚拟内存，性能差，调出的页面可能时经常访问的页面，并由Belady现象，很少单独使用。

Beladay现象：当使用FIFO算法时，有时会出现分配的物理页面增加，缺页率反而提高的异常现象。

**3，最近最久未使用 Least Recently Used LRU**  
选择最久未被使用的页面，开销比较大。  
系统维护一个链表，最近刚刚使用过的页面作为首节点，最久未使用的页面作为尾节点，每一次访问页面时都将这个页面移动到首节点，缺页中断时淘汰尾节点。  
**4，时钟页面置换算法**  
LRU的近似，FIFO的改进，淘汰的是比较久未被使用的  
–需要用到页表项的访问位，当一个页面被装入内存时，把该位初始化为0，然后如果这个页面被访问（读/写），则把该位置置为1（硬件完成）  
–把各个页面组织成循环链表（类似钟表面），把指针指向最老的页面（最先进来）  
–当缺页中断时，考察指针指向的最老页面。若它的访问位为0，立即淘汰；若为1，将其置为0，然后指针往下移动一格，直到找到被淘汰的页面。

**5，二次机会法**  
时钟法的改进，同时同脏位（写位）和使用位来指导置换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center]  
**6，最不常用法 LFU**  
当产生缺页中断时，选择访问次数最少的页面淘汰。

**7，工作集页面置换算法**  
工作集：在当前时刻t之前的一定的时间窗口当中所有页面组成的集合  
常驻集：当前时刻，进程实际驻留在内存中的页面集合。  
随着时间的进行，不在工作集内的页面被淘汰，并将新的页面加入内存

**8，缺页率页面置换算法**  
当缺页率高时增加工作集，当缺页率低时减少工作集  
当缺页发生时，记录上次却也到这次的时间，如果这个时间“大”，减少工作集，淘汰这两个时刻之外的页面；如果这个时间“小”，将缺失页加入工作集。

## 五 进程 ##

进程包括程序、数据、进程控制块（PCB）

**1，进程控制块**  
同一状态的进程PCB成一链表，多个状态对应多个不同的链表  
进程存在唯一的标志，包含三大类信息：  
1）进程标识信息，本进程标识，父进程标识；用户标识  
2）处理机状态信息保存区。保存进程的运行现场信息：  
用户可见寄存器，用户程序可以使用的数据，地址等寄存器。  
控制和状态寄存器，如程序计数器，程序状态字。  
栈指针，过程调用/系统调用/中断处理和返回时需要用到它。  
3）进程控制信息：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
**2，进程的生命周期**  
创建：系统初始化；用户请求；正在运行的进程执行了创建现成的系统调用  
就绪（唤醒）：被阻塞的进程需要的资源可被满足；被阻塞的进程等待的事件到达；将该进程的PCB插入到就绪队列，只能别别的进程或操作系统唤醒  
运行：  
阻塞（等待）：请求并等待系统服务，无法马上完成；启动某种操作，无法马上完成；需要的数据没有到达（等待IO操作）  
结束：正常退出（自愿）；错误退出（自愿）；致命错误（强制）；被其他进程杀死（强制）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
**3，线程**  
线程是进程中的一条执行流程  
–进程是资源分配单位，线程是CPU调度的单位  
–进程拥有一个完整的资源平台，而线程之独享必不可少的资源，如寄数器和栈  
–线程同样具有就绪、阻塞、运行等状态，同样具有状态间的转换  
–线程能减少并发执行的时间和空间开销：  
线程的创建和结束时间比进程短  
同一进程内的线程切换时间比进程短  
同一进程内的线程共享内存和文件资源，可以不通过内核通信

**4，线程的实现**  
1）用户线程：由用户级的线程库函数完成线程的管理及调度。内核无法感知，每个进程都有自己私有的线程控制块（TCB），且拥有自定义的线程调度算法。  
\-缺点：  
1，如果一个线程发起系统调用而阻塞，整个进程都会阻塞。  
2，当一个线程开始运行后，除非它主动交出CPU的使用权，否则它所在的进程的其他线程无法运行  
3，时间片分配给进程，多线程执行时得到的时间比较少。

2）内核线程：由操作系统的内核完成现成的管理及调度，线程的创建、状态切换、销毁都有内核完成，系统开销较大，一个内核线程发起系统调用被阻塞，不影响其他线程

3）轻量级进程：内核支持的用户线程，一个进程可以有多个轻量级进程。

**5，进程的创建、销毁**  
fork()函数：  
对子进程内存分配  
复制父进程的内存和CPU寄存器到子进程  
开销昂贵  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 4]

## 六 CPU调度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 5]  
多级反馈队列：优先级高的队列执行时间短，执行不完可以降级  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 6]  
实时调度  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 7]  
优先级反转  
T1需要的共享资源被T3占用，所以T2会比T1先执行  
解决办法：共享资源优先级继承  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 8]

## 七 互斥和同步 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 9]

1，禁用硬件中断  
线程无法停止  
2，基于软件的解决方案  
3，使用原子机器指令  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 12]

**读写锁：读者优先**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 13]  
**读写锁：写者优先**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 15]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9545256daf5d4228900c5279c00a223b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/7ebdcf588e3a47d68705729d30fe668b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/8065b86104354c2dae75ffa49decd8f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/c43bf9fb61c54f3b993110b16e7bb58c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/65887fb32f8349b3862896b8a7fa7a95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/fe4a3f825518485d916b8936179cbdd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/f8ca103bdcbf4b05b65af5d25af9581a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/1a1787e7eb1f43eb9c5cd67ad24a1af5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/0cbff1d870fa4e8f81dbf22f7a3ba479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/c0dca4f226314f86b041538c87d8db12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/1f50ddd086754153a53031c972c7a3c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/d8a0983a91c646fbb5bf090d093658b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/a32cc7221add42ba84c1676c90fb769a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221123/4d702921f48c48a783846ed1297243f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221123/50bcd1d43f694c51ba8e00caa774c9af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk2Mzc0MQ_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221123/9db03d6b613746469e77fea7ecd942a7.png