操作系统面试题
线程调度
进程间的通信方式
- 管道/匿名管道(Pipes) ：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
- 有名管道(Named Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
- 信号(Signal) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
- 消息队列(Message Queuing) ：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显式地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺点。
- 信号量(Semaphores) ：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
- 共享内存(Shared memory) ：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
- 套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。
线程间的同步的方式
线程同步是俩个或多个共享关键资源的线程并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步方式
互斥量（Mutex）采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如java scynchronized关键字和各种lock都是这种机制
信号量（Semaphore）它云溪同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
事件（Event）wait、notify通过通知操作的方式来保持多线程同步，还可以方便多线程优先级的比较操作
进程调度算法
为了确定首先执行哪个进程以及最后执行哪个进程实现最大CPU使用率
先到先服务FCFS调度算法：从就绪队列选择一个最先进队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用CPU时再重新调度
短作业优先SJF调度算法：从就绪队列汇总选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或者发生某件事二倍阻塞放弃占用cpu时再重新调度
时间片轮转调度算法：时间片轮转调度是一种最古老，最简单，且最公平使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
多级反馈队列调度算法前面介绍的几种进程调度的算法都有一定的局限性，如短进程优先的调度算法，仅照顾了短进程而忽略了长进程。多级反馈队列调度算法技能使优先级搞的作业得到响应又能断使短作业迅速完成，因此它是目前被公认的一种较好的进程调度算法，unix操作系统采用的便是这种调度算法
实施如下：设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二队列次之，在各个队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也可不相同，在优先权越高的队列中，为每个进程所规定的执行时间片越小。例如第二个队列的时间片要比第一个队列的时间片长一倍。低i+1队列的时间片要比第i个队列的时间片长一倍
当一个新进程进入内存后，首先将它放入第一队列的末尾，再同样地按FCFS原则等待调度执行；如果第二队列中运行一个时间片后未完成，再次将它放入第三队列，如此下去。当一个长作业，从第一队列依次讲到底第n队列后，在第n队列便采取时间片轮转的方式进行
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，如果处理正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列，则新进程将抢占正在运行进程的处理机。
优先级调度为每个流程分配优先级，首先执行具有最高优先级的进程，以此类推。具有相同优先级的进程以FCFS方式执行。可以根据内存需求，时间要求或其他资源要求来确定优先级，即第i队列中某个正在运行的进程的时间片用完后，由程序选择优先权较高的队列中的那一个进程，把处理机分给它
unix，linux，windows进程调度策略比较
无论是在批处理系统还是分时系统中，用户进程数一般都多余处理器机数，这导致它们互相争夺处理器。系统进程也同样要用到处理器
进程调度的实质是资源分配，如何使系统能够保持较短的响应时间和较高的吞吐量，如何在多个可运行的进程中选取一个最值得运行的进程并投入运行是调度器的主要任务。进程调度包括俩个方面内容：何时分配CPU时间片（调度时机）即调度器什么时候启动；如何选择进程（调度算法）调度器该怎么做。进程的调度主要可以分为非剥夺方式与剥夺方式。
非剥夺方式：调度程序一旦把处理机分配给某个进程后便让它一直运行下去，知道进程完成或发声某件事而阻塞时，才把处理器 分配给另一个进程
剥夺方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理器机，将之分配给其他进程，剥夺原则有：优先权原则，段金成原则，时间片原则
linux从整体上区分实时进程和普通进程，因为实时进程和普通进程调度是不同的，它们俩者之间，实时进程应该优先于普通进程而运行，然后对于同一类型的不同进程，采用俩种不同的标准看来选择进程。对普通进程的动态策略是动态有限调度，对于实时进程采用了俩种调度策略FIFO（先来先服务）和RR（时间片轮转调度）
Unix系统是单纯的分时系统，所以没用设置作业调度，unix系统的进程调度采用的算法是多级反馈队列调度。但它还是在某些地方存在不足，当不断有新进程到来时，则长进程可能饥饿
windows系统调度方式比较复杂，它的处理器调度的单位是线程而不是进程，是基于优先级的抢占式多处理器调度，依据优先级和分配时间来调度。windows操作系统的调度系统总是运行优先级最高的就绪线程。在同一优先级的各个线程按时间片轮转算法进行调度。如果一个高优先级的线程进入就绪状态，当前的运行线程能在用完它的时间片之前就被抢占处理机
操作系统的内存管理主要是什么
操作系统的内存管理主要负责内存的分配回收（malloc函数：申请内存，free函数，释放内存），另外地址转换也就是将逻辑地址转换成物理等功能也是操作系统内存管理做的事情
常见的几种内存管理方式
简单分为连续分配管理方式和非连续分配管理方式这俩种。连续分配管理方式是指一个用户分配一个连续的内存空间，，常见的如块式管理
同样的，分连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理和段式管理
块式管理
远古时代的计算机操作系统的内存管理方式。将内存分为几个固定的大小块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就给他分配一块，如果程序运行只需要很小的空间的话，分配的组合内存很大一块就几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
页式管理
把储存分为大小相等且固定的一页一页的形式，页较小，相对于块式管理的划分粒度更小，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址
段式管理
页式管理虽然提高了内存占用率，但是页式管理其中的页并无任何实际意义。段式管理把主存分为一段一段的，段是有实际意义的，每个段 定了一组逻辑信息，例如，有主程序段，main，子程序段X，数据段D即栈段S等。段式管理通过对段表对应逻辑地址和物理地址
页式管理是物理单位，段式管理是逻辑单位。分页可以有效提高内存利用率，分段可以更好满足用户需求
回答的还不错！不过漏掉了一个很重要的 段页式管理机制 。段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说段页式管理机制 中段与段之间以及段的内部的都是离散的。
块表和多级页表
页表
OS会给每一份进程都分配一个页表；
页表的主要作用就是翻译逻辑地址位物理地址的；
并且页表是只有在进程被CPU调度时候，才会被使用，如果该进程没有被调度，那么对应得页表只会留在内存中，不会被使用；
CPU是通过一个寄存器来保存页表得信息的；
并且页表带来一个新的问题，会增加上下文切换的开销，因为进程切换时候，不仅要保存进程的相关信息，它对应的页表信息也需要被保存起来；
我们要清楚知道，页表也是需要存储在内存中的，但是页表会增加上下文切换的负担，一直让页表留在内存中，我们切换上下文就会缓慢，所以在CPU中专门有一个为页表服务的寄存器，那就是PTBR，它存放的是页表的地址；
有了它，就不用上下文切换时候，要把这页表搬来搬去，只需要修改PTBR的值即可，哪个进程被CPU调度，那么就往PTBR添加哪个进程的页表；极大缩短上下文切换的时间；
快表
我们知道有了这个寄存器后，我们访问页表，就需要有两次的内存访问了咯，当我们调度进程时候，第一次，访问的是页表的位置在哪，把它放入到PTBR寄存器中，第二次访问就是内存中页表的逻辑地址到物理地址的具体位置数据在哪咯；
认识快表前，我们要知道为什么需要快表？肯定是页表的访问速度太慢了，才导致快表的产生，是的，确实是，因为页表是存储在内存中的，还是那样CPU去内存读取页表，对于CPU来说太慢了，所以为了加快读取页表速度，那么OS设计者搞出一个快表；
他们如何搞快表的呢？我们知道软件设计有一个大原则：任何问题都可以通过增加中间层来解决问题；
是的，我们OS设计者，搞了一个硬件，是TLB，就是一缓存，它是专用缓存，专门用来存取页表的条目信息的，因为cahe比较小嘛。。不可以存储全部的页表，只能存储部分的页表条目；
所以当访地址空间时候，我们首先去TLBcahe查找是否有你要页表信息，如果有直接返回给CPU就可以处理，没有那么就再去内存访问剩余其他的页表条目即可；
这里会有两次内存访问，一次是访问 cache 一次是内存访问。是不是说这样变慢了/
不是的，只要我们保证一个原则，我们TLB cache中存放的页表信息，都是进程中需要寻找的地址那么就可以加快速度，只要再TLB cahce的信息，命中率高即可！
至于愈合提高TLB cache的命中率，是缓存那边的话题，这先不讨论，我们只要知道；有一个TLB硬件，他是cache，并且他存放的是页表的部分条目信息，他可以加快页表的访问速度，快表的体现也就是体现在这里；
多级页表
基于32位系统下，我们一个进程最多可以分配到1m个页面（每个页面大小为64kb）
用具体数字说，就是100w个左右的页面，那么一个进程的页表就是存放页面和页框的信息，也就是说，一个进程的页表就要存放1m左右的页表项（页面和页框的映射），也就是要一个进程的页表存放100w个左右的页表信息
我们再假设一个页表项大小为4字节，那么，一个页表就要存放4M字节的信息，也就是400w个左右的页表项信息；
这是什么概念？这个概念是，每当你创建出一个进程，OS都需要为你这个进程维护一个页表，这个页表占用的实际空间是4M;
这样可能觉得不大，假如我的OS搞出100个进程呢？那么你OS就要帮你维护400M的页表信息；
这样说可能觉得还没什么，你知道一个进程维护一个4M字节的页表什么概念嘛？也就是你的物理内存，需要有
4M / 4KB = 1K个页框存放你的页表哦，意思是你的物理内存有1024个左右的页框，并且还是连续的1024个页框，为什么是连续的？因为你的页表不可以被打散存放在页框中，如果打算存放你怎么找到？
基于上面页表的信息过于大，且需要连续的物理空间，存放页表信息，所以我们认为这种方式不合理。
所以多级页表的方式就诞生的。
多级页表的意思是将页表也拆分一个一个的，然后放入到物理内存的页框中，此时我们就需要多了一个数据结构，保存，页表号，和页框号的信息，因为我们需要找到也标号，才能找到页面号，进而找到对应的物理地址；
这个数据保存页表号的数据结构我们叫页表页；
所以一个逻辑地址：就被表示为了页表页号+页号+页内位移了；
总结
引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。
多级页表属于时间换空间的典型场景。
虚拟地址空间
现代处理器使用的是一种称为 虚拟寻址(Virtual Addressing) 的寻址方式。使用虚拟寻址，CPU 需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。 实际上完成虚拟地址转换为物理地址转换的硬件是 CPU 中含有一个被称为 内存管理单元（Memory Management Unit, MMU） 的硬件。
因为如果每个进程都访问物理内存的话,造成不可控性.如果进程有访问内存的权力,他就会把自己的数据存到内存上,但是他并不知道哪片内存被使用,那一片未被使用.所以在多个进程的情况下,数据会混乱,所以物理内存由操作系统管理,进程没有权限访问.
2,操作系统并不能预先知道这个进程有多大,这个进程运行多少时间,应该给他分配多少空间(如果分配的少了,不够进程的运行,如果分配的大了,则会导致内存空闲).所以进程给每个进程都虚拟出来一个4G的内存(32位操作系统上),如果进程需要保存数据或者开辟内存,操作系统通过虚拟地址就能知道,并在物理内存上进行操作.这样操作系统就能知道一个进程到底需要多少内存空间.
通过虚拟地址访问内存有以下优势：
- 程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
- 程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动。
- 不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。
局部性原理
局部性原理表现在以下两个方面：
- 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
- 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。
页面置换算法
在地址映射过程中，若在页面中发现所需要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统中没有空闲的页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而来淘汰哪一页的规则叫做页面置换算法
OPT页面置换算法
最佳置换算法，锁选择的淘汰页面将是以后用不是用的，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。但由于人们目前无法阈值进程在内存下的若干页面中哪个是未来组慈航时间内不再被访问的，因而该算法无法实现
FIFO
先进先出置换算法：总是淘汰最先进入内存的页面，即选择在内存中驻留时间醉酒的页面进行淘汰。
LRU
最近最久未使用的页面置换算法：LRU算法赋予每隔页面一个访问字段我，用来记录一个页面自上次被访问以来锁经历的时间T，淘汰掉一个页面时，选择现有页面中T最大的，即最久未使用的页面予以淘汰
LFU
最少使用页面置换算法，该置换算法选择在之前使用最少的页面最为淘汰页