操作系统

什么是操作系统

1. 操作系统是管理计算机软件硬件的程序，是计算机系统的内核和基石。
2. 操作系统实质上是运行在计算机上的软件。
3. 操作系统还给用户提供了一个与系统进行交互的界面。
4. 操作系统分内核和外核，外核是围绕着内核的应用程序，内核是操作硬件的程序，负责管理系统的内存，进程，设备，文件和网络系统等，是黑盒，是核心。、

系统调用

• 用户态：用户态运行的进程可以获取用户的程序和数据。
• 系统态：系统态的进程几乎可以反问所有的计算机资源。

但是我们的程序 一般都是运行在用户态，所以凡事有关系统态级别的资源的相关操作时候，比如文件，进程，内存，设备的管理和控制时候，就要通过系统调用的方式向系统发送服务请求，并交由系统代为完成。

进程状态转换图

进程和线程的区别

• 进程是资源管理的基本单位，线程是调度的基本单位
• 线程并发性，独立性比较高。
• 线程除自己栈空间和基本的寄存器，共用进程的资源。
• 一个进程执行过程，系统分配资源，也就是上下文，然后执行a小段，b小段，c小段等等，然后保存上下文，退出。
• 而内部粒度较小的a b c就是进程的内部线程，共享同个进程的资源。
• 资源具体就包括堆，静态变量，全局变量，文件等共用资源。
• 从JVM来说，多个线程共享进程的堆，方法区，而线程拥有自己的栈空间和程序计数器。
• 从操作系统来说，一个进程面对的是磁盘，因为每个进程拥有自己的虚拟内存。而线程更像是面对CPU去执行。

进程间的通信方式

通信相关：jianshu.com/p/c1015f5ffa74

• 管道：半双工的方式。其实就是共享文件或者缓冲区的方式，严格限制先进先出。
• 信号：信号是一种复杂的通信方式。通过将消息直接或者间接用原语的方式发送给另外一个进程。
• 消息队列：是具有特定格式消息的链表，也是先进先出。但是它是放在内核里面，除非重启内核或者显式删除，不然不会消失。
• 信号量：是一个计数器，用于控制多进程对于资源的访问。信号量在于控制进程的同步。
• 共享内存：多个进程共享同一部分内存，可以看到内存中数据的更新。
• 套接字：主要用于客户端喝服务器之间的通信。主要是通过TCP/IP对两个不同主机进程之间的通信。

进程调度

• 先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
• 多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
• 优先级调度 ： 为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。
• 高响应比优先调度：考虑两个因素，包括等待时间和运行时间。运行时间越短，优先级越高，等待时间越长，优先级越高。

死锁

当资源是不可剥夺的，有两个或者两个以上的进程占有自己的资源，然后请求对方的资源，会导致进程无法向后推进。

条件：

• 互斥条件。进程要求分配的资源是排他的，最多可以给一个进程去使用。
• 不可剥夺。资源在被一个进程使用的时候，不可以被强行多走。
• 请求与保持。进程占有自己的资源并请求其他资源。
• 循环等待。存在一种进程资源的循环等待链。

避免死锁：

• 破坏互斥条件。占有的资源先复制一份，当别的进程占用的时候就不会被阻塞。
• 破坏不可剥夺。可以抢占，当进程需要一个资源，并且此资源被其他进程占有，可以抢占它的资源来使用。
• 破坏请求与保持。在自己请求的资源缺少时，自动放弃自己持有的资源。
• 破坏循环等待。资源指定获取顺序，所有进程都要按照一定顺序去获取资源，就不会造成环。

动态内存分配

• 首次适应算法：
  • 优点： 该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件
  • 缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销
• 最坏适应算法：
  • 优点：给文件分配分区后剩下的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利。
  • 缺点：使存储器中缺乏大的空闲区，对大型文件的分区分配不利。
• 最佳适应算法：
  • 优点：每次分配给文件的都是最合适该文件大小的分区。
  • 缺点：内存中留下许多难以利用的小的空闲区。

内存管理机制

简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间，常见的如 块式管理 。同样地，非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理 和 段式管理

1. 块式管理 ： 远古时代的计算机操系统的内存管理方式。将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
2. 页式管理 ：把主存分为大小相等且固定的一页一页的形式，页较小，相对相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。
3. 段式管理 ： 页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义。 段式管理把主存分为一段段的，每一段的空间又要比一页的空间小很多 。但是，最重要的是段是有实际意义的，每个段定义了一组逻辑信息，例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。 段式管理通过段表对应逻辑地址和物理地址。
4. 段页式管理机制 ：段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。

分页和分段有什么共同点和不同点

1. 共同点：
   • 分页机制和分段机制都是为了提高内存利用率，较少内存碎片。
   • 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。
2. 区别：
   • 页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
   • 分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户的需要。

快表和多级页表

快表

为了解决虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了 快表 来加速虚拟地址到物理地址的转换。我们可以把块表理解为一种特殊的高速缓冲存储器（Cache），其中的内容是页表的一部分或者全部内容。作为页表的 Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

使用快表之后的地址转换流程是这样的：

1. 根据虚拟地址中的页号查快表；
2. 如果该页在快表中，直接从快表中读取相应的物理地址；
3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
4. 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

多级页表

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景。

虚拟内存

虚拟内存是一种内存的管理技术。它定义了一个连续的内存空间，并把内存扩展到了硬盘空间。它使得应用程序以为它拥有的是一大片连续的内存资源，但其实是分散的内存碎片，并且把部分暂时存储在外部的硬盘中。

作用

• 虚拟内存作为缓存的工具。
• 虚拟内存作为管理内存的工具。
• 虚拟内存作为内存保护的工具。

实现

1. 请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
2. 请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
3. 请求段页式存储管理

虚拟存储器

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样，计算机好像为用户提供了一个比实际内存大的多的存储器——虚拟存储器

局部性原理

我们的程序在执行的时候往往呈现局部性规律，也就是说在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域。

1. 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
2. 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

页面置换算法

• OPT 页面置换算法（最佳页面置换算法） ：最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。一般作为衡量其他置换算法的方法。
• FIFO（First In First Out） 页面置换算法（先进先出页面置换算法） : 总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。
• LRU （Least Currently Used）页面置换算法（最近最久未使用页面置换算法） ：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 T，当须淘汰一个页面时，选择现有页面中其 T 值最大的，即最近最久未使用的页面予以淘汰。
• LFU （Least Frequently Used）页面置换算法（最少使用页面置换算法） : 该置换算法选择在之前时期使用最少的页面作为淘汰页。