八股笔记
Day7.18 +7.19+7.20
进程间调度算法
思路：先介绍三种偏向长/短任务的一方的算法（先来先服务偏向长，最短任务偏向短，最短剩余时间中和了长任务可能存在的阻塞，但还是偏向短，同时可以提一下两种进程任务的长短分类），再说明这些算法的缺陷，为了规避于是想出三种综合考虑长短任务的方法：高响应比（综合考虑等待时间+执行时间），时间片轮转（平等均匀地看待长短任务但是时间片的长短设置很重要，过长有缺点（阻塞短），过短也有缺点（进程切换开销），优先级（举例鼠标>后台优先级）。结束。
先来先服务，最短作业有限，高响应比，时间片轮转，优先级
先来先服务：先来的进程先运行直到结束或者被阻塞。进程分为计算密集型，Io密集型，计算密集型算作长任务，Io密集型算短任务，当长短任务都存在的时候，这种算法可能导致cpu长时间被长任务占据，影响短任务效率。
最短作业优先：优先选择执行任务更短的进程（对比上一种方法），可能导致短任务插队，长任务难以被执行掉。
最短剩余时间优先：比较任务执行剩余的时间，如果长任务剩余时间较短，也可以被执行。
上述算法都偏向于长/短任务，而不偏向另一方/。
高响应比（优先级）调度：等待时间长+执行时间短的有优先级，这样长短任务都能在不同方面被赋予优先性。
时间片轮转：每个进程都被分配时间片，单个进程在这个时间片中运行。算法中的时间片设置比较重要，时间片过短，cpu需要进行频繁的任务切换，开销大，过长则短任务等待时间过长。好的时间片设置为20-50ms左右。
优先级区分：比如鼠标控制优先级》〉后台任务优先级，高优先级会被排在前面，但依旧是按照时间片切换执行的
进程间通信方式
思路：可以先讲两句进程通信机制，（由于不共享内存而需要机制来通信，是操作系统提供的一种balabala。。）从管道讲起，半双工+实现方式就是文件（cpu在内核中创建缓冲区通过文件读写实现通信）+两种管道特点（匿名限于父子，子进程fork父进程文件描述符，结束后cpu回收内存，命名可以在无亲缘关系的进程间通信，在文件系统中有持久的文件名），讲到由于半双工带来的不便，因此有消息队列方式，通过链表实现，全双工，允许多对多，支持消息优先级，但可能会由于消息重复造成内存资源浪费。讲到共享内存，进程类似线程间的通信方式，（一个进程建设一段内存，其他进程都可以读写访问，但可能会由于同时读写造成脏数据的现象，因此共享内存和信号量通常是在一起使用的，信号量通过计数的方式实现对进程访问一段内存资源的控制，结合起来可以控制同一时刻只能有一个进程访问对应的共享内存。）然后讲到上面都是进程在正常状态下的通信，当进程遇到突发的网络状况，可能来不及把进程进入阻塞队列，因此简单高效的方法是采用信号的方式，进程接收到后可以暂时中断转为处理信号，但这种方式信息量携带少。最后是socket套接字，计网中TCP/IP的通信最小单元，由操作系统内核实现，系统创建和管理，可以实现跨网络传输，但受网络环境影响大，实现和调试较为复杂。
进程通信是操作系统提供的一种让进程在彼此间传递消息的方式。
管道：内核提供的文件系统的接口创建的。
匿名管道：可以参考Linux中的/符号，将/前面指令的输出作为后面指令的输入，流动是单向的，效率低。临时传输机制，利用完管道后，对应内存会被及时释放掉，只支持父子进程消息传递。子进程fork父进程的文件描述符实现。
命名管道：内核在内存中创建的缓冲区，在文件系统中有持久的文件名。允许无亲缘关系的进程通信。
管道符合Linux中一切皆文件的理念，实现方式就是文件。但管道这种方式并不支持频繁通信。
消息队列：全双工，通过链表实现消息队列。给运行进程收发消息，允许多对多通信和消息优先级，但可能存在消息重复的问题导致资源浪费。
信号：可能会遇到突发的网络状况，来不及把进程进入阻塞队列，因此有一种异步通信机制，告知进程发现了某种事件或条件。可以中断进程正常执行，转为处理信号。简单高效，适用于需要时效高的操作，但可传递的信息量少。
信号量：使用不当可能导致死锁或优先级反转
共享内存：类似线程的通信方式，由一个进程设定一个
socket套接字：TCP/IP的基本通信单元。用于客户端服务器间通过网络进行通信，由操作系统内核实现，通过系统调用创建管理，基于流/数据报通信，可以跨网络通信，实现和调试比较复杂，受网络环境影响大。
进程同步互斥及实现
同步：多个进程并发执行，数据可能存在依赖关系，进程有执行顺序，因此协调，管理数据依赖的关系称为进程同步。
互斥：访问资源，某个时刻只允许一个进程操作，其他进程必须等待资源释放。
互斥实现：常用的是锁，互斥锁和读写锁。
互斥锁：只要有进程在访问资源，就上锁（不管读写），结束后释放，其他资源发现资源被上锁，只能等待。
读写锁：对读操作和写操作区分，写的时候不允许其他进程读+写，读可以多个进程同步读，读不会变化资源，因此不会互斥。
信号量：可以解决互斥+同步的问题。有两种操作，P和V
P操作：检查资源，判断资源是否可用，如果可用就减少信号量计数，使对应资源可以被访问。
V操作：归还资源，增加信号量的计数，根据增加完的状态判断，可能会唤醒一些正在等待的进程。
死锁以及避免
思路：
两个进程在执行过程中由于争夺资源进入等待状态。+加锁的原理（互斥条件）。
都在等待对方释放锁会进入死锁。
四个条件：
互斥条件：一个资源只能同时被一个进程访问并加锁，其他进程面对加锁的资源时只能等待，不能进行访问。
持有并等待条件：一个进程在等待其他资源的锁的过程中不会释放当前已有的资源。（举例子AB）
不可抢占：一个资源获取一个资源，其他不可强行占有已经上锁的等待。
循环等待，进程对资源获取形成环路，陷入互相等待的状态。
四个条件打破其一可以
互斥条件不是很好打破，主要是针对资源和业务逻辑的规定，为了防止资源同时被读写产生冲突或者脏数据的必要条件。
打破二：要求进程在一开始就获取所有所需资源
打破三：当进程等待时主动释放当前已经占有的资源。
打破四：资源的有序分配，对资源申请顺序规定，不同进程执行过程中都按照相同顺序访问资源避免环路的产生。
介绍一下几种典型的锁
有两种底层的锁的模式：
互斥锁+自旋锁
其他锁都可以根据折两个锁实现，
互斥锁：上下文切换的状态（两次）
自旋锁：一直占有cpu直到锁被释放。线程在尝试获取的时候会不断轮询直到
使用场景不同
被锁住的代码执行时间短，切换开销不划算，自旋锁合适。如果时间长，自旋锁一直占有cpu会造成资源浪费。
读写锁：读不会更改资源，非互斥操作。写锁未被持有，其他线程可以并发持有读锁。使用场景（大量读少量写）
悲观锁：认为多线程修改资源概率高，因此访问共享资源之前必须上锁。
乐观锁：对应悲观锁，直接修改不会预先上锁，修改后再验证是否有其他，如果没有就顺利修改，否则放弃。假定场景冲突概率低，但加锁消耗高的情况。
讲一讲你理解的虚拟内存
多进程的环境下，进程间为了处理内存地址不受影响，为了内存隔离 操作系统会为每个进程分配虚拟内存地址空间，每个进程只需要关注自己的虚拟内存的空间，好处是防止多个进程同时对物理内存的地址修改，可以防止造成冲突导致崩溃。
虚拟内存由操作系统映射到具体物理内存，内存隔离机制使进程处理简单安全。
第二个是实现内存扩展，让各内存以为自己都拥有完整物理内存，可以使内存运行超过自己实际持有物理内存的。因为cpu访问一些资源的操作是重复性高的，一些（不常用）的内容可能会移到硬盘上，可以释放内存给进程使用，虚拟内存可以保证这种操作的顺利进行。
第三个是使操作系统的物理内存不足的时候，会把一些页面动态加载硬盘对应的虚拟内存中，满足当前内存的需求。这个过程被称为页面交换。当需要这些页面，操作系统会再从硬盘对应的虚拟内存中读取。
线程同步的 方式有哪些
解决并发执行的线程中对同一块资源操作，进行资源竞争产生的问题。进行线程同步的 目的就是为了保证线程之间的操作不会影响彼此，如果线程之前操作互相干扰，会影响最终结果。+举例子（十个线程对一个0变量执行+1操作，竞争过程中可能还没有提交修改某个变量结果，另一个变量就开始读取内存了）
常见线程同步操作措施：
锁，锁原理描述，互斥锁+读写锁详细描述（读写是对互斥的优化，放宽读限制）（不恰当操作容易导致死锁）频繁加锁解锁可能会影响执行效率，增加开销。
条件变量：设置全局变量表示某种状态，访问变量监控状态，如果条件没有满足，线程阻塞等待。条件变量也需要通过互斥机制保护，因为希望同时只有一个线程对条件变量进行修改。
信号量：可以维护共享数据状态，通过信号量值判断，P操作-1，V操作+1，判断信号量是否大于0判断资源是否可以访问。
有哪些页面置换算法
当cpu对内存管理，想要载入新的物理页，需要在当前内存中选取一个页面置换，腾出空间
先进先出FIFO：选取当前停留时间最久的页面，缺点是可能循环状态访问页面，隔一段时间访问这个页面，先进入的页面可能停留一段时间被替换掉，但过一段时间还会被载入，这个场景下该算法效率不高。
LRU：基于页面的使用历史，选择最长时间没被访问的页面，缺点是 实现成本高，每次一选取被置换的页面的时候都需要遍历找出最长时间没被访问
LFU：统计每个页面的访问次数，最少次数被访问的页面，只考虑了次数没考虑时间，有些页面可能只是短时间高频访问，但下一次操作可能是很久以后，那这种页面会被留存在内存中。
时钟算法，空间换时间维护环形链表，定义时钟指针，当前页面访问位是否为0，为0表示当前是最久没被访问。（？）
最佳页面算法：预测未来该页面被访问的情况，但不可被实现，只能作为基准算法来评估当前算法。是一种理想状态下的算法。