操作系统常见练习题
1. 进程的常见状态？以及各种状态之间的转换条件？
- 就绪态：进程已处于准备好运行的状态，即进程已分配到除CPU外的所有必要资源后，只要在获得CPU，即可立即执行。
- 执行态：进程已经获得CPU，程序正在执行状态
- 阻塞态：正在执行的进程由于发生事件，暂时无法继续执行的状态
三者的转换图如下：
挂起状态：
在不少系统中进程只有上述三种状态，但在一些系统中又新增了一些新状态，最重要的是挂起状态。引入挂起状态的原因有：
- 终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。
- 父进程请求。有时父进程希望挂起自己的某个子进程，一边修改子进程或者协调各子进程间的活动
- 负荷调节的需要
-
操作系统的需要
16314381460840.jpg
2. 进程同步
进程同步的主要任务：是对多个相关进程在执行次序上进行协调，使并发执行的多个进程之间能有效共享资源和相互合作，从而使程序的执行具有可再现性
同步机制遵循的原则：
- 空闲让进：当临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入临界区
- 忙则等待：进程正在访问临界资源，则不允许其它进程再进入进阶区访问这些临界资源，而是让它等待
- 有限等待：进程在等待进入临界区访问临界资源时，应该限制这个等待的时间
- 让权等待：权是指处理机的使用权
3. 进程的通信方式
进程通信，是指进程之间的信息交换。
对于用信号量进行的进程间的互斥和同步，由于其所交换的信息量少而被归结为低级通信。
高级进程通信指：用户可以利用操作系统所提供的一组通信命令传送大量数据的一种通信方式。
- 管道：是单向的、先进先出的、无结构的、固定大小的字节流。它吧进程的标准输出和另一个进程的标准输入连接在一起。
- 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。主要作为进程间以及统一进程间不同线程之间的同步手段
- 消息队列：是一个在系统内核中用来保存消息的队列，它在系统内核中是以消息链表的形式出现的。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 共享内存：共享内存允许两个或多个进程访问同一个逻辑内存。这一段内存可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取读出，从而实现了进程间的通信。如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量）配合使用，来实现进程间的同步和通信。
- 套接字：套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信
4.上下文切换
上下文切换是一种将CPU资源从一个进程分配给另一个进程的机制。在切换的过程中，操作系统需要先保存当前进程的状态（包括内存空间的指针，当前执行完的指令等），在读取下一个进程的状态，然后执行此进程。
5.进程与线程的区别与联系
- 进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位
- 线程是进程的一个实体，是CPU调度和分配的基本单位，它是比进程更小的能独立运行的基本单位
进程和线程的关系
- 一个线程只能属于一个进程，而一个进程可以有多个线程，至少有一个线程。线程是操作系统可识别的最小执行和调度单位
- 资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程的多个线程共享代码段（代码和变量），数据段（全局变量和静态变量），拓展段（堆存储）。但是每个线程有自己的栈，用来存放所有的局部变量和临时变量
- 处理机分给线程，即真正在处理机上运行的是线程
- 线程再执行过程中，需要协作同步。不同进程的线程间要实现同步
进程和线程的区别
- 进程有自己的独立空间，线程没有
- 进程是资源分配的最小单位，线程是CPU调度的最小单位
- 进程和线程通信方式不同(线程之间的通信比较方便。同一进程下的线程共享数据（比如全局变量，静态变量），通过这些数据来通信不仅快捷而且方便，当然如何处理好这些访问的同步与互斥正是编写多线程程序的难点。而进程之间的通信只能通过进程通信的方式进行。)
- 进程上下文切换开销大，线程开销小
- 一个进程挂掉不会影响其它进程，而线程挂掉会影响其它线程
进程上下文切换开销大，线程开销小
进程切换分两步
- 切换页目录使用新的地址空间
- 切换内核栈和硬件上下文
线程上下文切换和进程上下文切换一个最主要的区别是线程的切换虚拟内存空间依然是相同的，但是进程切换是不同的。这两种上下文切换的处理都是通过操作系统内核来完成的。内核的这种切换过程伴随的最显著的性能损耗是将寄存器中的内容切换出。
另外一个隐藏的损耗是上下文的切换会扰乱处理器的缓存机制。简单的说，一旦去切换上下文，处理器中所有已经缓存的内存地址一瞬间都作废了。还有一个显著的区别是当你改变虚拟内存空间的时候，处理的页表缓冲（processor's Translation Lookaside Buffer (TLB)）会被全部刷新，这将导致内存的访问在一段时间内相当的低效。但是在线程的切换中，不会出现这个问题。
总结
进程和线程都是一个时间段的描述，是CPU工作时间段的描述，不过是颗粒大小不同。
进程(process)与线程(thread)最大的区别是进程拥有自己的地址空间，某进程内的线程对于其他进程不可见，即进程A不能通过传地址的方式直接读写进程B的存储区域。进程之间的通信需要通过进程间通信(Inter-process communication，IPC)。与之相对的，同一进程的各线程间之间可以直接通过传递地址或全局变量的方式传递信息。
进程作为操作系统中拥有资源和独立调度的基本单位，可以拥有多个线程。通常操作系统中运行的一个程序就对应一个进程。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，如从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。相比进程切换，线程切换的开销要小很多。线程于进程相互结合能够提高系统的运行效率。
线程可以分为两类：
用户级线程(user level thread)：对于这类线程，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。在应用程序启动后，操作系统分配给该程序一个进程号，以及其对应的内存空间等资源。应用程序通常先在一个线程中运行，该线程被成为主线程。在其运行的某个时刻，可以通过调用线程库中的函数创建一个在相同进程中运行的新线程。用户级线程的好处是非常高效，不需要进入内核空间，但并发效率不高。
内核级线程(kernel level thread)：对于这类线程，有关线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只能调用内核线程的接口。内核维护进程及其内部的每个线程，调度也由内核基于线程架构完成。内核级线程的好处是，内核可以将不同线程更好地分配到不同的CPU，以实现真正的并行计算。
事实上，在现代操作系统中，往往使用组合方式实现多线程，即线程创建完全在用户空间中完成，并且一个应用程序中的多个用户级线程被映射到一些内核级线程上，相当于是一种折中方案。
6. 进程调度
调度种类
- 高级调度：（High-Level-Scheduling）又称为作业调度，它决定把后备作业调入内存运行
- 中级调度：（Intermediate-Level-Scheduling）又称为在虚拟存储器中引入，在内外存对换区进行进程对换
- 低级调度：（Low-Level-Scheduling）又称为进程调度，它决定把就绪队列的某进程获得CPU
非抢占式调度与抢占式调度
- 非抢占式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程调度而阻塞时，才把处理机分配给另一个进程
- 抢占式：操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其它就绪进程的调度方式
7. 死锁的条件？如何处理死锁问题
定义：
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件
多个进程被无限期的阻塞、相互等待的一种状态
产生死锁的必要条件
- 互斥（Mutual exclusion）:资源不能被共享，只能由一个进程使用
- 占有与保持（Hold and wait）:已经得到资源的进程可以再次申请新的资源
- 非抢占（No pre-emption）:已经分配的资源不能从响应的进程中被强制的剥夺
- 循环等待（Circular wait）:系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正在占用的资源
如何处理死锁问题
- 忽略该问题
- 检测死锁并回复
- 破除死锁的四个必要条件之一来防止死锁产生
8. 临界资源
- 在操作系统中，进程是资源占有的最小单位，线程是CPU调度的最小单位。但对于一些资源来说，其在同一时间只能被一个进程所占有。这就是临界资源
- 对于临界资源的访问，必须是互斥进行的。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，知道其所申请的临界资源被释放，而进程内访问临界资源的代码被称为临界区
操作系统提供的两种原子操作指令，保证可实现进入临界区的同步操作
-
Test-and-Set 测试和置位
- 从内存中读取值
- 测试该值是否为1，然后返回真假
- 内存值设置为1
-
交换
- 交换内存中的两个值
boolean TestAndSet(boolean *target) { boolean rv = *target; *target = TRUE; return rv; } void Exchange(boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp; } -
TestAndSet实现自旋锁：
class Lock { int value = 0; } Lock::Acquire() { while(test-and-set(value)) ; // spin //如果锁被使用，那么test-and-set读取0并将值设置为1 -> 锁被设置为忙并且需要等待完成 //如果锁处于忙状态，那么test-and-set读取1并将值设置为1 -> 不改变所得状态并且需要循环（自旋锁 spin） } Lock::Release { value = 0; }当临界区较长时，忙等消耗的CPU较多，可使用无忙等待的锁，等待的时候将进程移到等待队列中，release时候唤醒该进程。
Exchange实现共享数据
int lock = 0;
//线程Ti
int key;
do {
key = 1;
while (key == 1) exchange(lock,key);
critical section
lock = 0;
remainder section
}
缺点：
- 忙等待消耗处理器时间
- 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
- 死锁，如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并等待临界区
9. 一个程序从开始运行到结束的完整过程
- 预处理：条件编译，头文件包含，宏替换的处理，生成.i文件
- 编译：将预处理后的文件转换成汇编语言，生成.s文件
- 汇编：汇编变成目标代码（机器代码）生成.o文件
- 链接：连接目标代码，生成可执行程序
10.虚拟内存是什么，他们的优缺点是什么
定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存和外存决定
与传统存储器比较虚拟存储器有如下特征：
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存运行
- 对换性，无需在作业运行时一直常驻在内存中，而是允许在作业的运行过程中，进行换进和换出
- 虚拟性：从逻辑上扩充内存的容量，使用者所看到的内存容量，远大于实际的内存容量
11.页面置换算法
操作系统将内存按照页面机型管理，在需要的时候才把进程相应的部分调入内存。当产生缺页中断时，需要选择一个页面写入。如果要换出的页面在内存中被修改过，就需要先将页面写回磁盘。页面置换算法，就是要选出最合适的一个页面使置换的效率最高。
- 最优页面置换算法
最理想的状态下，我们给页面做一个标记，挑选一个最远才会被再次用到的页面调用。当然，这样的算法不可能实现，因为不确定一个页面在何时会被用到。 - 先进先出页面置换算法（FIFO）
这种算法的思想和队列是一样的，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面淘汰。 - 最近最少使用页面置换算法LRU(Least Recently Used)
12. 中断与系统调用
定义：中断指在计算机执行程序的过程中，由于出现一些特殊事情，使CPU暂停对程序的执行，转而去执行这一事件的程序，等这个事件处理完成后再回去执行之前的程序。
- 内部异常中断：由计算机硬件异常或故障引发的中断
- 软中断：程序执行中断的指令引发的中断
- 外部中断：外部设备请求引起的中断
13.用户态与内核态
进程的执行在系统上有两个级别：用户级和核心级,也称为用户态和系统态
用户空间是用户进程所在的内存空间，系统空间是操作系统占据的内存空间。用户进程和系统进程的所有数据都在内存中。处于用户态的程序只能访问用户空间，处于内核态的程序可以访问用户空间和内核空间
用户态切换到内核态的方式如下：
- 系统调用：程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，需要向操作系统发出调用服务的请求（如打开设备、创建文件、读写文件）
- 异常：当CPU在执行运行在用户态的程序时，发生了事先不可知的异常，会触发当前运行进程切换到处理此异常的内核相关程序中，也就切换到了内核态（如缺页异常）
- 外部设备的中断：当外部设备收到用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的转换。比如硬盘读写操作，系统会切换到硬盘读写的中断程序中执行后续操作
用户态和内核态的区别：
权限不一样
- 用户态的进程能存取自己的指令和数据，但不能存取内核指令和数据
- 内核态的进程能存取内核和用户指令和数据
14.多线程同步和互斥的实现方法
线程间的同步方法分两类：用户模式和内核模式
- 用户模式：不需要切换到内核态，只在用户态完成同步操作。常用如原子操作（单一的全局变量），临界区
- 内核模式：指利用系统内核对象的单一性进行同步，使用时需要切换内核态与用户态。常用的如信号量、互斥量
临界区： 通过对多线程的串行化来访问公共资源，速度快，适合控制数据访问
互斥量： 为协调共同对一个共享资源的单独访问而设计
信号量： 为控制一个具有有限数量用户资源而设计
15.逻辑地址、物理地址、虚拟内存
- 物理地址：加载到内存地址寄存器中的地址，内存单元的真正地址。在前端总线上传输的内存地址，编号从0开始一直到可用物理内存的最高端
- 逻辑地址：CPU生成的地址。逻辑地址是内部和编程使用的并不唯一。如：在进行C语言指针编程中，可以读取指针变量本身值（&），实际上取得是逻辑地址，它是相对于当前进程数据段的地址（偏移地址），与绝对物理地址不相干
为什么会有这两种地址?
逻辑地址分配相对灵活，可以允许不唯一，看起来也比较只管，如：一段代码中分配数组，逻辑地址上是连续的，然而在物理地址上，这个数组所占用的页可能分散开，物理地址上就是不连续的。另外有了逻辑地址这个概念，才能使用虚拟内存技术
Paging 分页内存管理方案
分页的最大作用是，使进程的物理地址控件可以是非连续的
物理内存被划分为一块一块，每块被称为帧（Frame）。分配内存时，帧是分配是的最小单位，最小也要给一阵。
逻辑地址的表示方式是：前部分是页码，后部分是页偏移
采用分页技术不会产生外部碎片（内存都被划分为帧），但可能产生内部碎片（帧是最小单元，因此帧内部可能有空间没有用到）
16 Semaphore(信号量)
信号量：
- 一个整形（sem）,两个原子操作
- P操作：sem--，如果sem<0等待，否则继续
- V操作：sem++，如果sem>=0，通知唤醒挂在信号量上一个等待的进程
Attention:
- 信号量是整数
- 信号量是被保护的变量
- 初始化完成后，唯一改变一个信号量的办法是通过P操作和V操作
- 操作必须是原子的
- P操作能够阻塞，V操作不会阻塞
- 我们假定信号量是“公平的”
- 如果没有线程被阻塞，P操作仍然会被阻塞如果V操作被无线频繁调用
- 在实践中，FIFO经常被使用，以确定由哪一个线程继续执行P操作
用二进制信号量实现互斥
mutex = new Semaphore(1);
//////
mutex->P();
...
Critical Section;
...
mutex->V();
用二进制信号量实现同步操作，P()等待，V()发出信号
condition = new Semaphore(0);
//Thread A
condition->P();
//Thread B
condition->V();
