计算机操作系统
内存管理
内存管理干什么的？
内存的分配与回收：对进程所需的内存进行分配和释放，malloc 函数：申请内存，free 函数：释放内存。
地址转换：将程序中的虚拟地址转换成内存中的物理地址。
内存扩充：当系统没有足够的内存时，利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存。
内存映射：将一个文件直接映射到进程的进程空间中，这样可以通过内存指针用读写内存的办法直接存取文件内容，速度更快。
内存优化：通过调整内存分配策略和回收算法来优化内存使用效率。
内存安全：保证进程之间使用内存互不干扰，避免一些恶意程序通过修改内存来破坏系统的安全性。
虚拟内存
存在于硬件里面的地址叫物理内存地址
程序使用的内存地址叫虚拟内存地址
引入虚拟内存，进程持有的虚拟地址就会通过CPU的内存管理单元的映射关系，转变成物理地址，再通过物理地址访问内存。
为什么引入虚拟内存？
- 虚拟内存可以让进程对运行内存超过物理内存大小
- 每个进程都有自己的页表，所以就实现多线程之间地址冲突问题。
- 页表可以标记各个页的权限，内存访问有安全性
那很明显这里最核心的就是怎么个映射关系，有两种方法：内存分段和内存分页
内存分段
构成
分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量
1、段选择因子保存在段寄存器里，段选择因子有段号和标志位
2、段内偏移量位于 0 和段界限之间。
联系
虚拟地址通过段表和物理地址映射，分段机制会把虚拟地址分成 4 个段，通过段号找到这段的基地址，然后加上偏移量就是物理地址
内存碎片&问题
内部内存碎片：已经分配给进程使用但未被使用的内存。
分段不会出现，需要多少就分多少。
外部内存碎片：未分配的连续内存区域太小，产生了多个不连续的小物理内存。
分段会出现，每个段长度不固定
分段下解决内存碎片的方法是，内存交换，也就是先把中间占用的内存写到硬盘上，再从硬盘上读回内存里，读回的时候紧跟着连续的内存的后面。
但是这样效率非常低，硬盘的访问速度要比内存慢太多了。
内存分页
内存分页的出现就是为了解决内部内存碎片问题。
构成
把整个虚拟和物理内存空间切成一段段固定尺寸的大小，这样一个连续并且大小固定的空间就叫页。
分页机制下的虚拟地址由两部分组成，页号和页内偏移。
联系
虚拟地址与物理地址之间通过页表来映射
把虚拟内存地址，切分成页号和偏移量，根据页号，从页表里面查询对应的物理页号，然后加上偏移量得到物理内存地址。
当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，系统内核空间分配物理内存，更新页表，返回用户空间，恢复进程运行。
内存碎片&问题
分页机制下，没有外部内存碎片了，因为页和页之间紧密相连，但会出现内部内存碎片。
如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高。
这种分页方式还是有问题：
- 在一个 32 位系统中，单级页表需要占用 4MB 的连续内存空间
- 而且绝大多数应用只会使用到页表中的几项
- 而且在单级页表中，即使某个虚拟地址范围（比如 4KB）从未被使用，它在 4MB 页表中的对应页表项也必须存在，导致这部分 4MB 内存被白白分配和占用，以防万一。
所以引入多级页表
多级页表
核心就是按需分配页表。
用时间换空间。
100多万个页表可以分成1024个一级页表，每个一级页表再指向1024个二级页表。
举例：
实现了4G的虚拟地址映射到物理内存页表大小是：4KB一级页表+按需分配的二级列表。
假设有20%的一级页表被用到了，占用空间是4KB+0.2*4MB=0.8MB
快表
多级页表解决了空间大小的问题，但是转换的过程多了工序降了速度，所以引入快表，相当于 后端的缓存
页面置换算法
最佳页面置换算法：优先选择淘汰的页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
但由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现，只是理论最优的页面置换算法，可以作为衡量其他置换算法优劣的标准。
- 先进先出页面置换算法（FIFO） : 最简单的一种页面置换算法，总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。该算法易于实现和理解，一般只需要通过一个 FIFO 队列即可满足需求。不过，它的性能并不是很好。
- 最近最久未使用页面置换算法（LRU）：LRU 算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。LRU 算法是根据各页之前的访问情况来实现，因此是易于实现的。OPT 算法是根据各页未来的访问情况来实现，因此是不可实现的。
段页式内存管理
组合使用！
构成
先分段，每段分页，地址由三部分组成：段号，段内页号，页内偏移
联系
三次内存访问：
- 访问段表，得到页表起始地址
- 访问页表，得到物理页号
- 把物理页号和页内偏移结合，得到物理地址。
进程线程
进程相关
在内存中运行中的程序就叫进程，进程是工厂。
进程的状态
基本状态
状态变迁
有大量的阻塞状态的进程，那内存空间会浪费很多，所以通常把阻塞状态的进程的内存空间换到硬盘，要运行再换回来。
这个进程没实际占用到物理内存的状态就是挂起状态。
- 阻塞挂起状态：进程在硬盘并等待某个事件的出现
- 就绪挂起状态：进程在硬盘，但只要进入内存，即刻立刻运行
进程的控制
进程控制块PCB包含：
- 进程的描述信息，包括进程的名称、标识符等等；
- 进程的调度信息，包括进程阻塞原因、进程状态、进程优先级；
- 进程对资源的需求情况，包括 CPU 时间、内存空间、I/O 设备。
- 及其他
进程的通信方式
1、管道：用于具有亲缘关系的父子进程或兄弟进程的通信，数据流动是单向的
2、信号：异步的通信方式，用于通知
3、信号量：计数器，用来同步或者控制多个进程对于共享资源的访问
4、套接字：Sockets，就是TCP和UDP的接口，进程间的基于网络协议的通信
死锁
四个条件：
1、互斥：有资源互斥
2、循环等待：两个线程获取资源的顺序构成了环形链
3、非抢占：是非抢占的调度，必须用完才能放出来
4、请求保持：线程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他线程占有。此时请求线程阻塞，但对自己已获得的资源保持不放。
线程相关
线程是进程当中的一条执行流程，同一个进程内的线程之间可以共享各种资源，但是每个线程都有自己一套独立的寄存器和栈。线程是工人。
线程的作用
让一个进程内的各种模块可以并发运行，又因为共享资源，不需要额外通信。
线程和进程的区别
1、拥有资源：进程是资源分配的基本单位，有独立的地址空间；线程是CPU调度的基本单位，只有少量的私有数据（寄存器和栈）。
2、开销：创建或者销毁一个进程开销很大，线程开销很小。
3、隔离性：进程之间是隔离的，一个崩溃不影响其他工厂。一个线程操作失误（访问非法内存）会导致进程崩溃。
进程调度算法
非抢占类
先来先服务调度：如题
短作业优先调度：如题
抢占类
时间片轮转调度：每个进程被分配一个时间段，称为时间片，允许该进程在这个时间段中运行。
优先级调度：每个进程都有一个优先级，选择优先级最高的进程，具有相同优先级的进程以 FCFS 方式执行。
多级反馈队列调度：有多个队列，每个队列优先级从高到低，优先级越高时间片越短。
- 开局：新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度。
- 进程降级：如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
惩罚长作业 - 进程优先级：当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。
- 进程抢占：如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
移入到原队列末尾：是因为在被抢占之后它的运行周期就算结束了，为了公平
