应届生面试要点总结（10）操作系统相关

骑猪看日落 2022-03-25 16:42 205阅读 0赞

批处理（多道）系统：系统效率和吞吐量；分时系统：交互性和响应时间；实时系统：实时性和可靠性；

生产者消费者

public class Producer implements Runnable {
    
    BlockingQueue<String> queue;
    
    public Producer(BlockingQueue<String> queue) {
    
    this.queue = queue;
    
    }
    
    @Override
    
    public void run() {
    
    try {
    
    String temp = "A Product, 生产线程：" + Thread.currentThread().getName();
    
    System.out.println("I have made a product: " + Thread.currentThread().getName());
    
    queue.put(temp);
    
    } catch (InterruptedException e) {
    
    e.printStackTrace();
    
    }
    
    }
    
    }
    
    public class Consumer implements Runnable {
    
    BlockingQueue<String> queue;
    
    public Consumer(BlockingQueue<String> queue) {
    
    this.queue = queue;
    
    }
    
    @Override
    
    public void run() {
    
    try {
    
    String temp = queue.take();
    
    Systemo.out.println(temp);
    
    } catch (InterruptedException e) {
    
    e.printStackTrace();
    
    }
    
    }
    
    }
    
    BlockingQueue<String> queue = new LinkedBlockingQueue<String>(2);
    
    Consumer consumer = new Consumer(queue);
    
    Producer producer = new Produce(queue);
    
    for (int i = 0; i < 5; i++) {
    
    new Thread(producer, "Producer" + (i + 1)).start();
    
    new Thread(consumer, "Consumer" + (i + 1)).start();
    
    }

进程、程序：程序是一段代码，一组指令的有序集合。进程：程序的一次动态运行，通过进程控制块唯一标识这个进程。进程动态，有资源，有唯一标识，有并发性；程序：静态，无资源，无唯一标识，无并发性。进程是cpu分配资源的基本单位，线程是cpu调度的基本单位。

进程与线程

进程：我们电脑的应用程序，都是进程，假设我们用的电脑是单核的，cpu同时只能执行一个进程。当程序处于I/O阻塞的时候，CPU如果和程序一起等待，那就太浪费了，cpu会去执行其他的程序，此时就涉及到切换，切换前要保存上一个程序运行的状态，才能恢复，所以就需要有个东西来记录这个东西，就可以引出进程的概念了。进程就是一个程序在一个数据集上的一次动态执行过程。进程由程序，数据集，进程控制块三部分组成。程序用来描述进程哪些功能以及如何完成；数据集是程序执行过程中所使用的资源；进程控制块用来保存程序运行的状态。

线程：一个进程中可以开多个线程，为什么要有进程，而不做成线程呢？因为一个程序中，线程共享一套数据，如果都做成进程，每个进程独占一块内存，那这套数据就要复制好几份给每个程序，不合理，所以有了线程。线程又叫轻量级进程，是一个基本的cpu执行单元，也是程序执行过程中的最小单元。一个进程最少也会有一个主线程，在主线程中通过threading模块，开子线程。

进程线程的关系

一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。

资源分配给进程，进程是程序的主体，同一进程的所有线程共享该进程的所有资源。

cpu分配给线程，即真正在cpu上运行的是线程。

线程是最小的执行单元，进程是最小的资源管理单元。

进程的状态

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70][]

创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态。

就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行。

执行状态：进程处于就绪状态被调度后，进程进入执行状态。

阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用。

终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行。

进程调度算法：先来先服务，短作业优先，时间片轮转，最高优先权-抢占式和非抢占式。

间接相互制约可以称为互斥，直接相互制约可以称为同步，对于互斥可以这样理解，线程A和线程B互斥访问某个资源则它们之间就会产个顺序问题——要么线程A等待线程B操作完毕，要么线程B等待线程操作完毕，这其实就是线程的同步了。因此同步包括互斥，互斥其实是一种特殊的同步。

在linux32位操作系统下，一个应用程序最多分配和访问的内存大小3g，32位可映射4g，用户空间最大3g，内核1g。

若系统有5台绘图仪，有多个进程均需要使用2台，规定每个进程一次仅允许申请1台，则至多有多少个进程参与竞争而不发生死锁。4个，哲学家问题，最多4个哲学家同时进餐，以保证至少一个哲学家能够进餐，最终会释放出2支筷子，从而使更多的哲学家进餐。

win32环境中，线程有3种线程模式，单线程，单元线程（所有线程都在主应用程序内存种各自的子段范围内运行，并且不能帮助在其他房间工作的人），自由线程（多个线程可以同时调用相同的组件和方法，与单元线程不同，自由线程不会被限制在独立的内存空间，找朋友搬房子，所有朋友都可以在任何一个房间工作）。

中断方式一般用于处理随机出现的服务请求。DMA方式数据传输不需要cpu控制。DMA和cpu必须同时使用总线。

中断并不会真正中断一个正在运行的线程，而只是发出中断请求，然后由线程在下一个合适的时候中断自己。比如，wait、sleep、join等方法，当他们收到中断请求或开始执行时，发现某个已经被设置好的中断状态，则抛出interruptedException。

每个线程都有一个boolean中断状态，当中断线程时，这个中断状态将被设置为true。interrupt方法：中断目标线程。isinterrupted：返回目标的中断状态。静态的interrupted方法：清除当前线程的中断状态，并返回他之前的值。大多数可中断的阻塞方法会在入口处检查中断状态。会自动重置中断状态为false，第二次调用总是返回false。

linux常用的进程间的通讯方式

管道(pipe)：管道可用于具有亲缘关系的进程间的通信，是一种半双工的方式，数据只能单向流动，允许一个进程和另一个与它有共同祖先的进程之间进行通信。

命名管道(named pipe)：命名管道克服了管道没有名字的限制，同时除了具有管道的功能外（也是半双工），它还允许无亲缘关系进程间的通信。命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建。

信号（signal）：信号是比较复杂的通信方式，用于通知接收进程有某种事件发生了，除了进程间通信外，进程还可以发送信号给进程本身。

消息队列：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。但是这种方式也有明显的缺点，它只适合点对点的通信，如果要多个进程间通信，内存区的数量会呈线性增长，会造成数据的冗余。

内存映射：内存映射允许任何多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它。

信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。

套接字（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。

死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

产生原因：因竞争资源发生死锁，现象：系统中供多个进程共享的资源的数目不足以满足全部进程的需要时，就会引起对诸资源的竞争而发生死锁现象。进程推进顺序不当发生死锁。

必要条件：互斥条件；请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此事请求阻塞，但又对自己获得的资源保持不放；不可剥夺条件；环路等待条件。

预防死锁（破坏四个必要条件）：资源一次性分配：（破坏请求和保持条件）；可剥夺资源：即当某进程新的资源未满足时，释放已占有的资源（破坏不可剥夺条件）；资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）。

避免死锁（银行家算法）：预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得较满意的系统性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。（即若能在分配资源时找到一个安全序列），则将资源分配给它，否则等待。

死锁的检测及解除：系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除手段。

死锁的检测：用死锁定理：具体表现为通过在资源分配图上进行简化，如果资源分配图是不可完全简化的，就是死锁。

死锁的解除：资源剥夺法，挂起某些死锁进程，并抢占他的资源，把这些资源分配给其他死锁进程。撤销进程法：强制撤销部分或者全部死锁进程并且剥夺这些进程的资源。进程回退法：让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是剥夺。要求系统保持进程历史信息，设置还原点。

缓存算法（页面置换算法）FIFO、LFU、LRU

FIFO先进先出：如果一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。

实现：利用一个双向链表保存数据，当来了新的数据之后便添加到链表末尾，如果Cache存满数据，则把链表头部数据删除，然后把新的数据添加到链表末尾。在访问数据的时候，如果在Cache中存在该数据的话，则返回对应的value值；否则返回-1。如果想提高访问效率，可以利用hashmap来保存每个key在链表中对应的位置。

LFU最近最少使用：基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。LFU是基于访问次数的。

实现：为了能够淘汰最少使用的数据，LFU算法最简单的一种设计思路就是利用一个数组存储数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。另外还有一种实现思路就是利用小顶堆+hashmap，小顶堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。

LRU最近最久未使用：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

实现：（1）用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。思路简单，但是需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。（2）利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部；如果不存在，则新建一个节点，放到链表头部。若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

补码的作用：1、可以非歧义的表达数字0。2、补码方便计算机的二进制运算，直接用补码相加减（符号位参与运算），补码计算的结果就是最终的结果。

内存保护：内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响，内存保护可采取两种方法。

1、再cpu中设置一堆上下限寄存器，存放用户作业在主存中的下限和上限地址，每当cpu要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。

2、通过采用重定位寄存器（或基地址寄存器）和界地址寄存器来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。每个逻辑地址必须小于界地址寄存器，内存管理机构动态地将逻辑地址与界地址寄存器进行比较，如果未发生越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。因为逻辑地址是从0开始的，所以界地址寄存器只需保存最长逻辑地址的上界就行了。

连续分配管理方式：连续分配是为一个用户程序分配一个连续的内存空间，比如说某用户需要1GB的内存空间，它就在内存空间中分配一块连续的1GB的空间给用户。它主要包括单一连续分配、固定分区分配和动态分区分配。

单一连续分配：内存在此方式下分为系统区和用户区，系统区仅提供给操作系统使用，通常在低地址部分；用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。因为内存中永远只有一道程序。

固定分区分配：将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以从后备作业队列中选择适当大小的作业装入该分区。有两种分配方式：分区大小相等和分区大小不等；固定分区分配会产生内部碎片。

动态分区分配：不预先将内存划分，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。动态分配策略4种：首次适应，最佳适应，最坏适应，邻近适应。

非连续分配管理方式：内存的非连续分配管理方式根据分区的大小是否固定分为：分页存储管理方式和分段存储管理方式。分页存储管理方式中，根据运行时作业是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

基本分页存储管理方式：固定分区会产生内部碎片，动态分区会产生外部碎片，这两种方式内存使用率都比较低。我们希望内存使用尽量避免碎片的产生，引入了分页的思想：把主存空间划分为大小相等且固定的块，块相对小，作为主存的基本单位。每个进程也以块为单位进行划分，进程执行时，以块为单位逐个申请主存中的块空间。分页从形式上看像分区相等的固定分区技术，分页管理不会产生外部碎片，也会有内部碎片，但是非常小，而且是最后一块才会有内部碎片。每个进程平均只产生半个块大小的内部碎片。刚刚提到的块，在进程中叫页，在内存中叫页框，外存也以同样的方式划分直接称为：块。页面大小应该是2的整数幂。而且大小应该适中，太小会使进程中页面过多，页表就过长占用大量内存。页过大会产生页内碎片就比较大。地址结构：页号+页内偏移量。页表：页号+块号 。页表的作用是实现页号到物理块号的地址映射。

基本分页储存管理方式具有如下特征：

一次性：要求将作业全部装入内存后方能运行。许多作业在每次运行时，并非其全部程序和数据都要用到。如果一次性地装入其全部程序，造成内存空间的浪费。

驻留性：作业装入内存后，便一直驻留在内存中，直至作业运行结束。尽管运行中的进程会因I/O而长期等待，或有的程序模块在运行过一次后就不再需要(运行)了，但它们都仍将继续占用宝贵的内存资源。

请求分页储存管理是实现虚拟存储器的一种常用方式，它是在基本分页储存管理的基础上实现的。其基本思想是：在进程开始运行之前，仅装入当前要执行的部分页面即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面。为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。请求分页是基于基本分页的，不同的是不是一次性把作业全部装入内存，而是需要的时候向系统发出缺页中断请求，以获取页。

段页式管理方式：

页式管理能有效提高内存利用率，分段存储管理能反应程序的逻辑结构并有利段的共享。两种方式结合起来就是段页式存储管理方式。

段页式虚拟存储系统结合了分段式和分页式的全部优点，具体包括：1）便于用户模块化程序设计，因为程序是以段为单位分割的，每个段内是连续的，但是段间是可以不连续 ；2）能减少存储空间的浪费 ；3）有利于实现程序的动态连接 ；4）有利于程序的共享 。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70]: /images/20220325/e2ed62830eaf4e23b5666a94221293cb.png