操作系统

1 简单说下你对并发和并行的理解？

• 并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。

• 并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。

• 并发是两个队列交替使用一台咖啡机。

• 并行是两个队列同时使用两台咖啡机。

2 同步、异步、阻塞、非阻塞的概念

• 同步：当一个同步调用发出后，调用者要一直等待返回结果。通知后，才能进行后续的执行。

• 异步：当一个异步过程调用发出后，调用者不能立刻得到返回结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

• 阻塞：是指调用结果返回前，当前线程会被挂起，即阻塞。

• 非阻塞：是指即使调用结果没返回，也不会阻塞当前线程。

3 线程与进程区别

• 进程是 CPU 分配资源的最小单位，线程是操作系统调度执行的最小单位
• 进程间的信息难以共享。由于除去只读代码段外，父子进程并未共享内存，因此必须采用一些进程间通信方式，在进程间进行信息交换。
• 调用 fork() 来创建进程的代价相对较高，即便利用写时复制技术，仍然需要复制诸如内存页表和文件描述符表之类的多种进程属性，这意味着 fork() 调用在时间上的开销依然不菲。
• 线程之间能够方便、快速地共享信息。只需将数据复制到共享（全局或堆）变量中即可。
• 创建线程比创建进程通常要快 10 倍甚至更多。线程间是共享虚拟地址空间的，无需采用写时复制来复制内存，也无需复制页表。

4 为什么有了进程，还要有线程呢？

进程属于在CPU和系统资源等方面提供的抽象，能够有效提高CPU的利用率。

线程是在进程这个层次上提供的一层并发的抽象：

（1）能够使系统在同一时间能够做多件事情；

（2）当进程遇到阻塞时，例如等待输入，线程能够使不依赖输入数据的工作继续执行

（3）可以有效地利用多处理器和多核计算机，在没有线程之前，多核并不能让一个进程的执行速度提高

5 进程的状态转换

进程状态反映进程执行过程的变化。这些状态随着进程的执行和外界条件的变化而转换。在三态模型中，进程状态分为三个基本状态，即就绪态，运行态，阻塞态。在五态模型中，进程分为新建态、就绪态，运行态，阻塞态，终止态。

• 运行态：进程占有处理器正在运行
• 就绪态：进程具备运行条件，等待系统分配处理器以便运行。当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列
• 阻塞态：又称为等待(wait)态或睡眠(sleep)态，指进程不具备运行条件，正在等待某个事件的完成

• 新建态：进程刚被创建时的状态，尚未进入就绪队列
• 终止态：进程完成任务到达正常结束点，或出现无法克服的错误而异常终止，或被操作系统及有终止权的进程所终止时所处的状态。进入终止态的进程以后不再执行，但依然保留在操作系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后，操作系统将删除该进程。

6 进程间的通信方式有哪些？

进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。IPC 的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams 等。其中 Socket 和 Streams 支持不同主机上的两个进程 IPC。

• 管道PIPE
  • 是半双工的，具有固定的读端和写端；
  • 只能用于父子进程或者兄弟进程之间的进程的通信；
  • 可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
• 命名管道
  FIFO 可以在无关的进程之间交换数据，与无名管道不同；
  FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
• 信号量semophere
  信号量（semaphore）是一个计数器。用于实现进程间的互斥与同步，而不是用于存储进程间通信数据；
  信号量用于进程间同步，若要在进程间传递数据需要结合共享内存；

信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作；

每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数；

支持信号量组。

• 共享内存shared memory
  共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区；
  共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
• 消息队列message queue
  消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符 ID 来标识；
  消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；

消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；

消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。

• 套接字socket
  可用于不同主机间的进程通信；
• 信号signal
  比较复杂的通信方式，用于通知进程某个事件已经发生。

7 进程的调度算法有哪些？

调度算法是指：根据系统的资源分配策略所规定的资源分配算法。常用的调度算法有：先来先服务调度算法、时间片轮转调度法、短作业优先调度算法、最短剩余时间优先、高响应比优先调度算法、优先级调度算法等等。

• 先来先服务调度算法
  先来先服务调度算法是一种最简单的调度算法，也称为先进先出或严格排队方案。当每个进程就绪后，它加入就绪队列。当前正运行的进程停止执行，选择在就绪队列中存在时间最长的进程运行。该算法既可以用于作业调度，也可以用于进程调度。先来先服务比较适合于常作业（进程），而不利于段作业（进程）。

• 时间片轮转调度算法
  时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片。

• 短作业优先调度算法
  短作业优先调度算法是指对短作业优先调度的算法，从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短作业优先调度算法是一个非抢占策略，他的原则是下一次选择预计处理时间最短的进程，因此短进程将会越过长作业，跳至队列头。

• 最短剩余时间优先调度算法
  最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。

• 高响应比优先调度算法
  高响应比优先调度算法主要用于作业调度，该算法是对 先来先服务调度算法和短作业优先调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

• 优先级调度算法
  优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

8 什么是死锁

两个或两个以上的进程在执行过程中，因争夺共享资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。

9 死锁的几种场景

• 忘记释放锁
• 重复加锁
• 多线程多锁，抢占锁资源

10 分段和分页的区别

分页：用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
分段：将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

• 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要
• 页的大小固定，且由系统决定；而段的长度却不固定，决定于用户所编写的程序
• 分页的地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址

11 物理地址、逻辑地址、虚拟内存的概念

1.逻辑地址
是上层程序员可以操作的地址,和段相关的偏移地址部分，也就是变址寄存器中存储的32位偏移地址,而其他寄存器上的地址往往对于上层程序员来说是不可更改甚至是不可见的. 只有在实模式下,逻辑地址才和物理地址一致(因为实模式没有分段或分页机制,Cpu不进行自动地址转换);逻辑地址也就是在保护模式下程序执行代码段限长内的偏移地址(假定代码段、数据段如果完全一样).应用程序员仅需与逻辑地址打交道,而分段和分页机制对您来说是完全透明的,仅由系统编程人员涉及.应用程序员虽然自己可以直接操作内存,那也只能在操作系统给你分配的内存段操作。

2.物理地址
用于内存芯片级的单元寻址，与处理器和CPU连接的地址总线相对应。在实地址模式(因为实模式没有分段或分页机制,Cpu不进行自动地址转换)下,程序员操作的就是物理地址,所谓的物理地址就是物理内存上的32位地址,即物理地址可以直接定位到物理内存上的位置,无论任何操作,最终都必须要得到物理地址才能在物理内存上进行操作。

3.虚拟地址
cpu要访问虚拟内存地址时，需要经过地址翻译成物理地址才能访问。比如cpu要访问虚拟地址4100，需要通过专用的硬件内存管理单元（memory management unit）MMU来翻译成对应的内存物理地址4，然后cpu在内存地址4的位置上取到数据返回。

4.虚拟内存
在运行一个进程的时候，它所需要的内存空间可能大于系统的物理内存容量。通常一个进程会有4G的空间，但是物理内存并没有这么大，所以这些空间都是虚拟内存，它的地址都是逻辑地址，每次在访问的时候都需要映射成物理地址。

当进程访问某个逻辑地址的时候，会去查看页表，如果页表中没有相应的物理地址，说明内存中没有这页的数据，发生缺页异常，这时候进程需要把数据从磁盘拷贝到物理内存中。如果物理内存已经满了，就需要覆盖已有的页，如果这个页曾经被修改过，那么还要把它写回磁盘。

虚拟内存被分为一块块固定的大小，成为虚拟页（Virtual Page）简称VP，对应的物理内存也被分成一块块同样的大小，成为物理页（Physical Page）简称PP。磁盘和内存之间是以页为单位进行数据交换的。

12 什么是缓冲区溢出？有什么危害？

缓冲区为暂时置放输出或输入资料的内存。缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入是否合理。计算机中，缓冲区溢出会造成的危害主要有以下两点：程序崩溃导致拒绝服务和跳转并且执行一段恶意代码。

13 页面置换算法有哪些？

请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入。而内存中给页面留的位置是有限的，在内存中以帧为单位放置页面。为了防止请求调页的过程出现过多的内存页面错误（即需要的页面当前不在内存中，需要从硬盘中读数据，也即需要做页面的替换）而使得程序执行效率下降，我们需要设计一些页面置换算法，页面按照这些算法进行相互替换时，可以尽量达到较低的错误率。常用的页面置换算法如下：

• 先进先出置换算法（FIFO）
  先进先出，即淘汰最早调入的页面。

• 最佳置换算法（OPT）
  选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。

• 最近最久未使用（LRU）算法
  即选择最近最久未使用的页面予以淘汰

• 时钟（Clock）置换算法
  时钟置换算法也叫最近未用算法 NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。

14 谈谈你对动态链接库和静态链接库的理解？

静态链接就是在编译链接时直接将需要的执行代码拷贝到调用处，优点就是在程序发布的时候就不需要的依赖库，也就是不再需要带着库一块发布，程序可以独立执行，但是体积可能会相对大一些。

动态链接就是在编译的时候不直接拷贝可执行代码，而是通过记录一系列符号和参数，在程序运行或加载时将这些信息传递给操作系统，操作系统负责将需要的动态库加载到内存中，然后程序在运行到指定的代码时，去共享执行内存中已经加载的动态库可执行代码，最终达到运行时连接的目的。优点是多个程序可以共享同一段代码，而不需要在磁盘上存储多个拷贝，缺点是由于是运行时加载，可能会影响程序的前期执行性能

15 外中断和异常有什么区别？

外中断是指由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

而异常是由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。

16 程序执行过程简介

预处理：条件编译，头文件包含，宏替换的处理，生成.i文件。
编译：将预处理后的文件，进行词法分析、语法分析、语义分析及优化转换成汇编语言，生成.s文件
汇编：汇编变为目标代码(机器代码)生成.o的文件
链接：连接目标代码,生成可执行程序

17 进程终止的方式

• 正常退出(自愿的)：进程结束，正常退出
• 错误退出(自愿的)：进程程序出现错误，比如执行非法指令，引用不存在内存等，此时
• 严重错误退出(非自愿的)：比如编译了不存在的文件，此时会发出声明并退出，并且
• 被其他进程杀死(非自愿的)：通过其他进程kill -9 进行杀死

18 僵尸进程、孤儿进程和守护进程

• 孤儿进程
  如果父进程先退出，子进程还没退出，那么子进程的父进程将变为init进程。（注：任何一个进程都必须有父进程）。
  一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

• 孤儿进程并不会有什么危害。

• 僵尸进程

  • 每个进程结束之后, 都会释放自己地址空间中的用户区数据，内核区的 PCB 没有办法自己释放掉，需要父进程去释放。
  • 进程终止时，父进程尚未回收，子进程残留资源（PCB）存放于内核中，变成僵尸（Zombie）进程。
  • 僵尸进程不能被 kill -9 杀死，这样就会导致一个问题，如果父进程不调用 wait() 或 waitpid() 的话，那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程，此即为僵尸进程的危害，应当避免。

• 守护进程
  指在后台运行的，没有控制终端与之相连的进程。它独立于控制终端，周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的，如web服务器进程http等
  创建守护进程要点：
  （1）让程序在后台执行。方法是调用fork（）产生一个子进程，然后使父进程退出。
  （2）调用setsid（）创建一个新对话期。控制终端、登录会话和进程组通常是从父进程继承下来的，守护进程要摆脱它们，不受它们的影响，方法是调用setsid（）使进程成为一个会话组长。setsid（）调用成功后，进程成为新的会话组长和进程组长，并与原来的登录会话、进程组和控制终端脱离。
  （3）禁止进程重新打开控制终端。经过以上步骤，进程已经成为一个无终端的会话组长，但是它可以重新申请打开一个终端。为了避免这种情况发生，可以通过使进程不再是会话组长来实现。再一次通过fork（）创建新的子进程，使调用fork的进程退出。
  （4）关闭不再需要的文件描述符。子进程从父进程继承打开的文件描述符。如不关闭，将会浪费系统资源，造成进程所在的文件系统无法卸下以及引起无法预料的错误。首先获得最高文件描述符值，然后用一个循环程序，关闭0到最高文件描述符值的所有文件描述符。
  （5）将当前目录更改为根目录。
  （6）子进程从父进程继承的文件创建屏蔽字可能会拒绝某些许可权。为防止这一点，使用unmask（0）将屏蔽字清零。
  （7）处理SIGCHLD信号。对于服务器进程，在请求到来时往往生成子进程处理请求。如果子进程等待父进程捕获状态，则子进程将成为僵尸进程（zombie），从而占用系统资源。如果父进程等待子进程结束，将增加父进程的负担，影响服务器进程的并发性能。在Linux下可以简单地将SIGCHLD信号的操作设为SIG_IGN。这样，子进程结束时不会产生僵尸进程。

19 共享内存和内存映射的区别

1. 共享内存可以直接创建，内存映射需要磁盘文件（匿名映射除外）
2. 共享内存效果更高
3. 内存
   所有的进程操作的是同一块共享内存。
   内存映射，每个进程在自己的虚拟地址空间中有一个独立的内存。
4. 数据安全
   • 进程突然退出
     共享内存还存在
     内存映射区消失
   • 运行进程的电脑死机，宕机了
     数据存在在共享内存中，没有了
     内存映射区的数据 ，由于磁盘文件中的数据还在，所以内存映射区的数据还存在。
5. 生命周期
   • 内存映射区：进程退出，内存映射区销毁
   • 共享内存：进程退出，共享内存还在，标记删除（所有的关联的进程数为0），或者关机
     如果一个进程退出，会自动和共享内存进行取消关联。

20 FIFO和pipe的区别

1. FIFO 在文件系统中作为一个特殊文件存在，但FIFO中的内容却存放在内存中。
2. 当使用FIFO的进程退出后，FIFO文件将继续保存在文件系统中以便以后使用。
3. FIFO 有名字，不相关的进程可以通过打开有名管道进行通信。

21 如何避免僵尸进程？

通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心，由内核回收。如果不想让父进程挂起，可以在父进程中加入一条语句：signal(SIGCHLD,SIG_IGN);表示父进程忽略SIGCHLD信号，该信号是子进程退出的时候向父进程发送的。
父进程调用wait/waitpid等函数等待子进程结束，如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。
如果父进程很忙可以用signal注册信号处理函数，在信号处理函数调用wait/waitpid等待子进程退出。
通过两次调用fork。父进程首先调用fork创建一个子进程然后waitpid等待子进程退出，子进程再fork一个孙进程后退出。这样子进程退出后会被父进程等待回收，而对于孙子进程其父进程已经退出所以孙进程成为一个孤儿进程，孤儿进程由init进程接管，孙进程结束后，init会等待回收。
第一种方法忽略SIGCHLD信号，这常用于并发服务器的性能的一个技巧因为并发服务器常常fork很多子进程，子进程终结之后需要服务器进程去wait清理资源。如果将此信号的处理方式设为忽略，可让内核把僵尸子进程转交给init进程去处理，省去了大量僵尸进程占用系统资源。

22 介绍一下几种典型的锁？

• 互斥锁

• 读写锁

• 条件变量

23 常见内存分配内存错误

• 内存分配未成功，却使用了它。

• 内存分配虽然成功，但是尚未初始化就引用它。

• 内存分配成功并且已经初始化，但操作越过了内存的边界。

• 忘记了释放内存，造成内存泄露。

• 释放了内存却继续使用它。常见于以下有三种情况：

  • 程序中的对象调用关系过于复杂，实在难以搞清楚某个对象究竟是否已经释放了内存，此时应该重新设计数据结构，从根本上解决对象管理的混乱局面。
  • 函数的return语句写错了，注意不要返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。
  • 使用free或delete释放了内存后，没有将指针设置为NULL。导致产生“野指针”。

24 原子操作的是如何实现的

处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。首先处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。Pentium 6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的，但是复杂的内存操作处理器是不能自动保证其原子性的，比如跨总线宽度、跨多个缓存行和跨页表的访问。但是，处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性