-
1. 什么是操作系统？
操作系统是用于管理计算机资源，合理组织安排计算机工作流程，方便用户使用的计算机程序的集合 -
2. 操作系统分类？
批处理操作系统：计算机成批的，自动的，依次处理用户的作业，用户提交后只能等待这批作业全部处理完之后才能得到输出结果
分时系统：操作系统将时间分为若干时间片，依次轮流的为每个作业处理
实时系统:
个人计算机操作系统
网络操作系统
分布式操作系统
嵌入式操作系统
... -
3. 用户态与内核态？
用户态：执行用户程序
内核态：运行操作系统程序，与硬件相关的操作都必须陷入内核态执行
特权指令：只能操作系统使用，用户程序不能使用的指令
非特权指令：用户程序可以使用的指令
用户态 -> 内核态：中断 / 异常 / 陷入
内核心 -> 用户态：设置程序状态字PSW -
4. 中断与异常？
相同点：
CPU对系统发生的某件事件做出的一种反应，CPU暂停正在执行的程序，保留现场，转而自动执行相应事件的处理程序，处理完毕后，回到断点处恢复现场，继续处理之前被打断的程序
不同点：
中断是被外部时间所引发的，引入中断是为了支持CPU与设备之间的并行操作
异常是由正在执行的指令所引发的，引入异常是为了处理CPU执行指令时本身可能会出现的问题，如除零 -
5. 系统调用？
系统调用是用户在编程时可以调用的操作系统功能
是操作系统提供给编程人员的唯一接口
使CPU从用户态陷入内核态
系统调用主要包括进程控制，进程通信，文件使用，目录控制，设备管理等等 -
6. 并发与并行？
并发：一段时间内，多个进程同时运行，如多道程序设计，允许多个进程同时存在内存，允许多个进程处于已经开始执行但是尚未执行完毕的状态
并行：某一时刻，有多个进程在同时运行，实现并行只能是多个处理器，因为一个CPU某时刻只能一个进程正在运行 -
7. 进程？
定义：进程是具有独立功能的程序，关于某个特定数据集的一次运行活动，是系统进行资源分配和调度的基本单位。
进程的三状态模型：
就绪态（ready）：进程准备好了，随时可以被系统调度进CPU执行
运行态（running）：进程正在CPU中执行时的状态
阻塞态（waiting）：进程被中断，比如等待IO时间输入，处于阻塞状态，除非某种事件发生，否则进程不能运行
进程的其他状态：
创建（new）：已完成创建，但是因为资源有限，系统尚未打算执行该进程
终止（terminated）：进程执行完毕后，进入该状态，完成一些数据统计与资源回收
挂起（suspend）：用于调节负载，进程被放入磁盘，不占用内存空间
进程控制操作完成进程各状态之间的转换，由具有特定功能的原语完成
主要有进程创建原语，进程撤销原语，阻塞原语，唤醒原语，挂起原语，激活原语，改变进程优先级等等
进程的创建：unix（fork/exec），windows（CreateProcess）
给新进程分配唯一标识PID与进程控制块PCB
为进程分配地址空间
初始化进程控制块
设置相应的队列指针（把新进程加入到进程就绪队列链表中）
进程的撤销：unix（exit），windows（TerminateProcess）
收回进程所占用的资源（收回分配的内存，关闭打开的文件等）
撤销该进程的PCB
进程阻塞
处于运行状态的进程，由于期待某事件的发生（如IO输入，等待其他进程发送的消息等），当此事件尚未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态
UNIX中几个基本的进程控制操作
fork()：通过复制调用进程来建立新的进程，是最基本的进程建立操作，对父进程返回子进程的pid，对子进程返回0
exec()：包括一系列的系统调用，通过用一段新的程序代码，覆盖原来的空间，实现进程执行代码的转换
wait()：提供初级进程同步操作，使一个进程等待另外一个进程的结束
exit()：终止一个进程的运行
-
8. 进程控制块PCB？
PCB：Process Control Block，进程控制块，又称为进程描述符
操作系统用于管理进程的一个专门的数据结构
记录进程的各种属性，描述进程的动态变化过程
PCB是系统感知进程存在的唯一标志，PCB与进程为一一对应的
进程表：是所有进程的PCB集合
PCB里面应该包括进程的那些信息呢？
进程描述信息（进程标识符PID，进程名，用户标识符，进程组关系）
进程控制信息（当前状态，优先级，代码执行入口，程序磁盘地址等等）
所拥有的资源和使用情况（虚拟地址空间，打开文件列表）
CPU现场（寄存器值，指向该进程页表的指针） -
9. 原语，原子操作？
原语：系统提供的完成某种特定功能的一段程序，由机器指令编写，执行过程不可中断
原子操作：在多线程操作系统中不能被其他线程打断的操作叫做原子操作。当该次操作无法完成时，必须回到操作之前的状态，原子操作不可分割。 -
10. 进程与程序的区别？
进程是程序在特定数据集上的一次执行过程，是动态的；程序是存储在某个空间的静态文件
进程是有生命周期的；而程序是相对持久的
进程能更准确的刻画并发；程序不能
一个程序可对应多个进程
进程具有创建其他进程的功能 -
11. 线程？
为什么有了进程还需要引入线程？
应用程序的需要：某些应用程序需要同时发生多种活动，比如字符处理软件，当输入文字时，排版也在同时进行，自动保存也在进行。如果用线程来描述这样的活动的话，编程模型就会变得更简单，因为同一进程的所有线程都处于同一地址空间，拥有相同的资源
开销上考虑：线程更加轻量级，相对进程而言，线程的相关信息较少，它更容易创建，也更容易撤销。当有大量线程需要创建和修改时，这会节省大量的开销；线程之间的切换比进程之间的切换要快的多，因为切换线程不需要考虑地址空间，只需要保存维护程序计数器，寄存器，堆栈等少量信息；线程之间的通信也比进程之间的通信要简单，无需调用内核，直接通过共享变量即可
线程的概念
线程是进程中的一个运行实体，是CPU的调度单位
进程有两个属性，一个是资源的拥有者，另一个是CPU的调度单位
引入线程之后，进程还是资源的拥有者，而线程继承了CPU的调度单位这一属性，而同一进程的所有线程共享进程的所有资源
线程的属性
线程标识符ID
有状态及状态转换，即线程切换
切换线程时需要保存上下文：包括程序计数器，寄存器，堆栈等
线程有自己的堆栈
同一进程的所有线程共享进程的地址空间和其他资源
一个线程可以创建也撤销另一个线程
线程机制的实现
用户级线程
在用户空间建立线程库，提供一组管理线程的过程
由运行时系统来完成线程的管理工作
内核管理的还是进程，内核不知道线程的存在
线程切换不需要陷入内核
典型如Linux，Unix
优点：
切换速度快
调度算法可以由应用程序设定
用户级线程可以运行在任何操作系统，包括不支持线程操作系统
缺点：
同一进程的所有线程只能运行在一个处理器上
若一个进程的某个线程调用了阻塞的系统调用，那么该进程的所有线程也将会被阻塞，页面失效也会有同样的问题
内核级线程
内核管理所有的线程管理，创建，撤销与调度，并向应用程序提供API
内核维护进程和线程上下文
线程的切换需要内核支持
以线程为基础进行调度
优点：
由内核调度，当有多个处理器时，一个进程的多个线程可以在多个处理器上同时执行
一个进程的某个线程阻塞不会引起其他线程的阻塞，页面失效同理
缺点：
由内核进行创建，撤销，调度，系统开销更大
典型如Windows
混合实现
线程创建在用户空间
线程调度在内核 -
12. 进程与线程的区别与联系
定义的角度
进程是具有特定功能的程序关于某个数据集的一次运行活动
线程是进程的一个一个运行实体
角色的角度
进程是CPU资源分配的基本单位，线程是CPU调度的基本单位
资源共享的角度
进程之间一般不能共享资源，两个进程间通信需要进行系统调用；
而同一进程的所有线程共享该进程的地址空间和其他资源，线程之间的通信可直接通过共享内存来进行
独立性角度
进程与进程之间一般是独立的，每个进程都有自己独立的地址空间
而线程没有自己的地址空间，它是依赖于进程而存在的 -
13. 进程间通信
竞争条件
两个或多个进程读写某些共享数据，其最终的运行结果取决于进程间的精确运行时序
临界区
共享内存进行访问的片段
进程互斥
当一个进程正在访问临界区时，其他进程不能对临界区进行访问
互斥的原则
两个进程不能同时处于临界区
当没有进程处于临界区的时候，想进入临界区的进程可以进入
临界区外的进程不得阻塞其他进程进入临界区
不能使想进入临界区的进程无限等待
进程同步
系统中多个进程完成某些任务存在某种时序关系，需要相互合作，共同完成 -
14. 互斥锁mutex
适用于管理一小段代码或共享资源
一般有两种状态lock, unlock
当某个进程向进入临界区时，调用 mutex_lock，这样其他想进入临界区的进程就无法进入
离开临界区时，调用 mutex_unlock，离开之后，其他想进入临界区的进程就可以进入了
值得注意的是，lock与unlock只能是同一进程调用
mutex的底层实现
mutex_lock:
TSL, REGISTER, MUTEX（将互斥信号复制到寄存器，并将内存中的互斥信号置为１）
CMP REGISTER, #0（比较刚才复制进来的那个信号等于０吗？）
JZE ok（如果是０，那么表示可以进入）
CALL thread_yield（如果不是０，表示不能进入，此时线程调用yield，放弃CPU，稍后再试。避免一直循环等待，一直占有CPU，而正在临界区线程没有机会运行，肯定也就没有机会退出临界区，释放锁，而线程就会一直等待下去）
JMP mutex_lock（稍后再试）
ok: RET（如果是0，即ok，返回调用者，并进入临界区）
mutex_unlock
MOVE MUTEX, #0（将互斥信号置为０）
RET（返回调用者）
mutex为什么能锁住临界区？
因为TSL或者XCHG是原子性的，即不可打断的。
如果用另外一个共享变量ｘ而不是mutex来锁住临界区的话，那么共享变量也是一个临界区。如果进程１读取ｘ后被打断，另一个进程也读入ｘ后发现能进，并改变ｘ，后切换回进程１，则进程１发现先前读入的ｘ值也能进取，所有最后有两个进程进入临界区了。
mutex的关键之处就在于，用TSL或XCHG指令可以原子性的将mutex的值读入寄存器，并将值置为１，不可打断。所以当执行了这条语句之后，即使被打断，其他进程来判断mutex的值，也是１，所以不会进入，所以绝对不会出现两个进程在统一临界区的情况。 -
15. 信号量semaphore
一个特殊的变量，用于进程间传递信息的一个整数值
主要用于临界区互斥与进程间同步（进程的运行保持某种特定的时序）
mutex有时也称为二元信号量
定义：
struct semaphore
{
int value;
struct process * list; // 当value<0时，将进程阻塞至此队列
};
对信号量可以实施的操作：wait(), signal()或者P, V PV操作均为原语操作
wait(semaphore s)
{
s->value--; // 将value的值减一
if (s->value < 0) //若value的值小于０
{
add this process to s->list; //则将此进程的信息加入list队列
block(); // 并将此进程阻塞
}
}
signal(semaphore s)
{
s->value++; // 将value值加一
if (s->value <= 0) // 如果value的值小于等于０时，说明在value值加一之前，value的值是负数，即有进程阻塞在list中，此时应该将其中一个进程唤醒
{
remove a process p from s->list; // 将进程p从list移除
wakeup(p); // 并将进程p唤醒
}
// 如果value的值是正数的话，就说明之前的值至少是大于等于０的，即在list中没有进程阻塞，所以只需将value的值加一，表示可用的资源又多了一个，而不需要其他操作
}
- 16. 生产者消费者问题
一个生产者的进程与一个消费者的进程，两个进程共享一段缓存区
生产者生产了一个产品，就往缓存区里放，当缓存区满了，则进入睡眠，当消费者取出了一个产品后再将生产者唤醒
消费者消费了一个产品，就从缓存区中取出，当缓存区空了，即进入睡眠，当生产者生产了一个产品后，再将其唤醒
// 存在严重竞争条件的生产者消费者模型
#define N 100 // 缓存区的最大值
int count = 0; // 定义的共享变量，用于记录缓存区中产品的个数
int item;
void producer()
{
item = produce_iter(); // 生产一个产品
if (count == N) sleep(); // 如果缓存区满了，则生产者sleep
count++; // 如果没满或者被唤醒了，则继续执行，先count加一
insert_item(item); // 将产品放入缓存区
if (count == 1) wakeup(consumer); // 如果此时count等于１，就说明之前缓存区空的，即此时消费者应该在sleep，因为此时缓存区有产品了，应该将其唤醒
}
void consumer()
{
if (count == 0) sleep(); // 如果缓存区为空，则消费者进入sleep
count--; // 如果缓存区不为空或者被唤醒了，则继续执行，先count减一
item = remove_item(); // 然后再从缓存区中移除一个产品
if (count == N-1) wakeup(producer); // 如果此时count 等于N-1，说明刚才count 等于N，即生产者此时正在睡眠，因为此时缓存区空了一个位置了，故应该将其唤醒
consume_item(item); // 消费这个产品
}
这个模型存在的严重问题是，若此时缓存区为N，当生产者执行判断count是否为N的语句，如果CPU将count值复制进寄存器，但是还没来得及判断，就被中断了，CPU调度消费者上去，此时count仍然为N，而消费者消费了一个产品，此时count为N-1，消费者向生产者发送了一个wakeup()信号，但是此时生产者并未进入sleep，故此信号丢失，当CPU再次切换到生产者，操作系统恢复中断之前的状态，此时寄存器中count的值为N，继续往下执行，执行sleep，而wakeup信号丢失了，再也没有进程将他唤醒，而消费者随着一个一个的产品消费完，缓存区为空，也进入sleep，两个进程就一直睡眠下去了。
用信号量机制解决互斥与同步问题
#include N 100
typedef int semaphore // 将semaphore定义为int类型，可正可负
semaphore mutex = 1; // mutex为二元信号量，用于互斥对缓存区的操作
semaphore full = 0; // 信号量full, empty用于同步生产者消费者进行
semaphore empty = N;
int item;
void producer()
{
item = produce_iter();
wait(&empty); // 先判断缓存区是否为满，若为满，empty为０,对其执行wait操作，会把empty减为小于０，则系统会将生产者阻塞
wait(&mutex); // mutex用于控制进程对缓存区的操作，保证某个进程在临界区操作时，其他进程无法进入
insert_item(item);
signal(&mutex); // 将临界区解锁，两个signal操作其实可以交换位置，原则上不会有错误，但是临界区越小越好
signal(&full); // 对full执行signal操作，表示空的位置有增加了一个
}
void consumer()
{
wait(&full); // 对full执行wait操作，如果此时缓存区为空，则消费者应该被阻塞；full当缓存区为空时等于０，对其wait操作，会把full降为小于０，则系统会将其阻塞
wait(&mutex);
item = remove_item();
signal(&mutex);
signal(&empty); // 对empty执行signal操作，即把empty的值加一，表示缓存区空的位置又多了一个
consume_item(item);
}
当同一个信号量由同一个进程来执行wait, signal操作时，一般是临界区互斥
当同一个信号量由不同的进程来执行wait, signal操作时，一般是用于两个进程的同步问题
- 17. 第一类读者写者问题
两个进程，读者进程只读，写者进程只写
允许两个或以上读者同时读
不允许两个以上写者同时写
只有当没有读者读的时候，写者才能写
只有当没有写者写的时候，读者才能读
当有读者在读时，其他读者可随时进入
semaphore mutex = 1; // 用于互斥rc共享变量的二元信号量mutex
semaphore w = 1; // 用于同步读者与写者操作的信号量w
int rc = 0; // read_count
void reader()
{
wait(&mutex); // 用于互斥对临界区rc的操作，避免两个读者进程同时修改rc
if (rc == 0) wait(&w); // 如果rc等于０，说明它是第一个读者，此时应该锁住w，避免写者进行写操作，此后的第二个第三个读者没有必要再进行加锁
rc++;
signal(&mutex); // 解锁rc
read();
wait(&mutex); // 对rc加锁
rc--;
if (rc == 0) signal(&w); // 如果此时rc等于０，说明这是最后一个读者，此时应该解锁w，在这之后，如果有写者进行写操作才能进行下去
signal(&mutex); //解锁rc
}
void writer()
{
wait(&w); // 判断信号量w,如果有读者在读或者有写者在写，那么都无法进行下一步，将被阻塞
writer();
signal(&w); // 写完之后，解锁w，让其他读者或者写者可以进行读写操作
}
此例中，mutex主要用于共享变量rc的互斥，不允许两个以上的进程同时对rc进行操作，否则可能会永远阻塞写者；信号量w主要用于同步读者与写者进程的特定执行次序问题
-
18. 条件变量？
pthread提供了另一种同步机制，称为条件变量
条件变量允许线程由于未达到某个条件而阻塞，直到另一个线程向他发信号
条件变量允许这种阻塞和等待原子性的进行
当有多个线程被阻塞了，可以使用broadcast广播全部唤醒
条件变量经常与mutex一起使用
条件变量与信号量不同的地方：
信号量是可以保存状态的，wait和signal操作一般不会丢失，可以体现在值上
条件变量是不保存状态的，即条件变量不会存在内存中，如果在wait之前signal到了，那么没有线程在等待这个signal信号，也就丢失了，而执行wait的线程需要等到下一个signal -
19. 管程？
管程是一种特殊的抽象数据类型，内部定义有数据与特定的操作的集合
并且只能通过管程内部的操作才能操纵该数据类型的实例
只有通过管程的某个过程才能访问资源
管程是互斥的，即管程保证在某个时刻只能有一个进程或线程调用管程中的过程
管程应用数据类型本身的机制提供互斥操作
如果还需要同步，可再定义条件变量 -
20. 进程间基本的通信方式？
消息传递：send(destination, &message), receive(source, &message)，原语，系统调用
共享内存：需要解决互斥与同步问题，也就是互斥量，信号量，条件变量，管程等去解决的问题
管道：利用一个缓冲介质－内存或文件（内核缓存区）连接两个相互通信的进程
套接字：网络编程，一般用于不同主机上的不不同进程通信
远程过程调用：RPC是指主机A上的一个进程，调用另外一台主机B上的进程，其中A上的进程被暂时挂起，而B上的进程被调用开始运行，当值返回A时，A进程继续运行。调用方可以将信息以参数的形式传递给被调用方，这一过程，对开发人员来说是透明的。 -
21. 管道pipe？
管道是一种基本的IPC机制，用于有血缘关系的进程间半双工通信
其本质是一个伪文件（实为内核缓冲区），管道实为内核使用环形队列机制，借助内核缓冲区（4K）实现
由两个字符串引用，一个表示读端，一个表示写端
数据以字节流的方式单向传输
数据只能从写端写入，由读端读取
有无名管道与有名管道之分
管道队列机制，先进先出，字节流顺序
管道机制必须提供协调读写双方进程的能力，如果写进程不在了，那么读进程也就没必要等待了。反之同理
管道的局限：
数据自己读不能自己写，自己写不能自己读
数据一旦被取走，则在管道内不复存在，不能反复读取
管道采用半双工通信方式，数据只能单向流动
只能在有公共祖先的进程间使用管道 -
22. 屏障？
屏障机制用于进程组，即在某处设置一个屏障，只有当这一进程组的所有进程都执行到这里了，进程组的这些进程才统一往后继续执行
如果有进程先到达了屏障，那么必须等待其他进程 -
23. 进程调度算法？
CPU调度概念：当有多个进程在就绪队列，竞争一个CPU资源，那么操作系统必须按照一定的调度算法和规则选择一个就绪进程去CPU运行
调度发生的时机
创建，唤醒，退出等进程控制操作
进程等待IO，IO中断，时钟中断，进程执行过程出现异常等
进程切换的代价
假设进程A下CPU，进程B上CPU
１）保存进程A的上下文环境（包括程序计数器，程序状态字，寄存器等），用新状态和相关信息更新进程A的PCB
２）将进程A移到合适的队列（就绪队列，阻塞队列，或者移出内存等。。）
３）将进程B的状态设为运行态
４）从进程B的PCB中恢复上下文（程序计数器，程序状态字，寄存器等）（每个进程自创建起就有自己的PCB）
直接开销：内核完成切换所需要的CPU时间
间接开销：高速缓存，缓存区缓存失效
调度算法衡量指标：
吞吐量：每单位时间完成的进程的数目
周转时间：每个进程从提出要求到完成的时间
响应时间：进程熊提出要求到第一次回应的时间
CPU利用率：CPU做有效工作的时间比例
等待时间：进程在就绪队列中的等待时间
抢占式与非抢占式
抢占式：当有比正在运行的进程优先级更高的进程已就绪，那么系统可强行剥夺正在运行的进程的CPU，提供给优先级更高的进程
非抢占式：某一进程被调度运行后，除非由于它自身原因不能运行了，否则不能被强行剥夺CPU，可一直运行下去
批处理系统的调度算法
先来先服务（FCFS）：按照进程就绪的先后顺序来使用CPU
优点：实现简单，公平
缺点：在长进程后面的短进程需要等待很长的时间，不利于用户体验
最短作业优先（SJF）：若运行时间可预知，那么运行时间最短的进程优先，非抢占式
优点：最短的平均周转时间
缺点：长进程可能会因为源源不断的短进程而饥饿
最短剩余时间优先（SRTN）：最短作业优先的抢占式版本，即当就绪队列有剩余时间更短的进程，那么可以直接把正在CPU上运行的进程挤下来 优缺点与最短作业优先大致相同
交互式系统常用的调度算法
轮转调度（RR）：周期性切换，为每个进程分配一个时间片，利用时钟中断来轮换
时间片的选择不能太长，否则就成了先来先服务了，影响响应时间；
也不能太短，否则太多的消耗花在进程切换上面，CPU利用率低。
优点：公平，响应时间快
缺点：进程切换增加系统开销
最高优先级调度（HPF）：选择优先级最高的进程运行
通常系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好于IO型进程
优先级可以是静态的，也可以是动态的，比如正在CPU上运行的进程随着运行时间的增加降低优先级，而处于就绪队列的进程随着等待时间的增加而增加优先级
优点：实现简答，灵活度高，各方面表现都不错
缺点：但是不公平，可能优先级低的进程会产生饥饿现象
（题外话）对于抢占式的优先级调度，存在优先级反转的问题：即两个进程，优先级高的A，优先级低进程B，共享一段临界资源，B进程先运行，进入前加锁，如果正在临界区时，被A进程挤下去了，然而A进程无法进入临界区无法工作，而B由于无法得到运行时间而释放不了临界区，所以导致两个进程都无法运行
解决方案：设置优先级上限，动态优先级，使用中断禁止
多级反馈队列（MFQ）：是一个比较折中的综合调度算法
设置多个就绪队列，第一级优先级最高，依次递减
给不同就绪队列的进程分配长度不同的时间片，第一队列时间片最小，随着优先级降低，时间片增大。（这一策略体现了当进程为CPU密集型，如果轮转过快，反而会增加大量的系统消耗，所以对于优先级较低的CPU密集型进程，时间片设置的更大一些，减少轮转）
第一级队列为空时，在第二级队列轮转，以此类推
各级队列按时间片轮转的方式进行调度
新创建的进程，都进入第一级队列
如果进程是用完了CPU时间，被时钟中断，那么进入下一级队列（这体现了操作系统对IO密集型的进程的偏好，IO密集型进程需要更短的时间片以提高响应速度，而对于CPU密集型进程，时间片应该更大一些。所以当进程由于用完了时间片而中断，说明进程是偏向于CPU密集型进程的，应该降级）
如果进程因为阻塞而放弃了CPU，那么它的等待时间发生后，仍然回到这个就绪队列
系统如何预测进程的运行时间呢？
一种方法是根据过去的行为进行预测
假设某进程的估计时间是T0，上一次的运行时间是T1
则：T0 = a×T0 + (1-a)×T1
其中a为０－１的数，调整a的大小，可以觉得预估时间是应该以平均时间为重，还是应该以实时时间为重
PS：这个方法在计算机网络的估计RTT，确定丢包的时间，设置定时器的时候用到过。
-
24. 地址空间？
**概念：**地址空间是一种抽象的内存，是一个进程可以用于寻址内存的一套地址的集合。每个进程都有自己的独立的地址空间。
为什么要引入地址空间？
保护：避免用户进程直接访问内存的物理地址，避免对操作系统的破坏
多道程序设计：使用地址空间的概念，多道程序设计会变得简单的多。在没有地址空间的系统，实现并发只能用多线程编程，而很难实现多进程编程，而系统又需要有不同类型的进程的并发能力
**逻辑地址（相对地址，虚拟地址）：**用户程序经过编译汇编之后形成的目标代码，目标代码采用相对地址的形式，首地址为０，其余地址相对首地址编址，不能直接用逻辑地址在内存中寻址
**物理地址（绝对地址，实际地址）：**内存中存储单元的实际地址，可以直接寻址
地址重定位：为了CPU执行指令时可以正确访问内存单元，需要将用户程序中的逻辑地址转换为在内存中的物理地址，这一过程称为地址重定位，一般通过内存管理单元MMU来转换
**内存管理单元MMU：**负责管理内存
主要功能有两个：
１是保护权限，进程A不能访问进程B的地址空间；
２是负责地址重定位，CPU发出的寻址指令被MMU截获，CPU发出的是虚拟地址，MMU将其转换为物理地址，再到内存中实际寻址
空闲内存管理：
数据结构：
位图：每一个分配单元对应位图中的一位，０表示空闲，１表示占用；优点是实现简单，回收释放内存时简单，合并空闲块简单；缺点是寻找连续的空闲块是一个比较费时的操作
空闲区链表与已分配链表：维护两个链表，一个是空闲区的链表，一个是已分配的链表，表中记录区块的起始地址，长度，标志等；优点是寻找合适的区块很方便；缺点是内存释放与回收时比较复杂，因为需要与旁边的空闲块合并，不然的话会内存碎片化
内存碎片化：
物理内存碎片化：内存管理方面存在的问题．内存在经常多次分配与回收之后，可能会产生很多不连续的小的空闲区块，这样就会产生本来内存还有很多空闲空间，但是申请分配一段较长的连续空间却分配失败的情况，导致内存利用率下降．
内存碎片分内部碎片与外部碎片，内部碎片是比如申请３k内存，系统直接给了你一页４k，多余的那１k没有被使用，属于内部碎片；外部碎片是两个非空闲区中间夹着一小块空闲区，这一小块空闲区属于外部碎片
解决办法，内存紧缩，即把碎片化的小区块合并成大区块，需要考虑系统开销，以及合并的时机
内存分配算法
首次适配法：每次从头开始找，在空闲区表中找到第一个满足进程要求的区块
下次适配法：从上一次找到的空闲区接着往后找
最佳适配法：遍历整个空闲区表，寻找大小最合适的
最差适配法：总是分配最大的空闲区，将空闲区分为两部分，一部分分配给它，另一部分称为新的空闲区 -
25. 基本内存管理方案（６种）：
１单一连续区：一段时间只有一个进程在内存，简单，但是内存利用率低
２固定分区：将内存空间分割成若干区域，大小可相同也可不同，大小固定不变，每个分区只能装一个合适的进程
３可变分区：根据进程的需求，把内存空闲区分割处一个空闲区，分配给该进程，剩余部分称为新的空闲区，缺点导致内存外碎片化，内存利用率降低
４ 分页（paging）：
用户进程地址空间被划分为若干个大小相等的页面，每个页面从０开始编址
内存空间也按同样的大小划分为若干个页框，也从０开始编号
内存以页为单位，按进程的需求进行分配，虚拟地址相邻，物理地址不一定相邻
典型页面尺寸为4K或4M
虚拟地址：页号 ＋ 页内地址
通过MMU将虚拟地址的页号转换为物理地址的页框号，加上页内地址偏移，就得到了实际的物理内存地址
但是MMU是怎么把虚拟地址的页号转换为物理地址的页框号呢？
答案是通过页表：每个进程都分配有一个页表，页表中存有若干个页表项，每个页表项中存有一个虚拟页面号与实际物理地址页框号的对应关系，MMU通过访问页表，寻找虚拟页面号对应的物理页框号，来完成转换
页表存在哪里？：系统存在一个页表寄存器，存储页表起始地址与页表长度，因为每个进程都存在一个页表，所以实际的页表肯定存在内存中，进程的页表相关信息存储在进程的PCB中，当程序运行时，页表寄存器从PCB中读取页表起始地址与长度，之后的查询就寻址到页表中查询
当页面的数量变多时，常采用多级页表，第一级表示页表目录，第二级或更多级之后才是真正的页表项
因为地址转换要求特别快，而页表实际上存在内存中，如果每次都需要访问内存多次才能转换一个地址，这样就存在一些性能问题，速度过慢．解决办法为TLB
TLB转换检车缓冲区，快表：TLB为一个小型硬件设备，当中存储了少量常被访问的页表项，TLB具有并行查找能力，即可以同时查询所有的页表项，如果查询的虚拟地址在TLB中，TLB可以快速转换
当在TLB中没有找到的页表项，才进入到内存中的页表中查询，提高了系统的性能
TLB软失效：页表项不在TLB中，需要进入内存查找
TLB硬失效：页面不在内存中，需要从磁盘上置换上来
倒排页表：当系统是６４位时，那么一个进程页面的数量将会太多太多．．需要占用极大的空间，此时继续采用多级页表是不明智的．所以就出现了倒排页表，倒排页表是按内存中物理页框来存储的，存储的是实际物理内存页框中装的是哪一个虚拟页面，这样空间是节省了，但是查询某一虚拟地址对应的实际物理地址却非常困难，需要搜索整个页表．
解决办法有两个：第一是使用TLB来查询频繁访问的页表；第二是使用hash表来实现对整个页表的搜索，提高效率
５ 分段：
背景：如果一个进程有很多个过程，每个过程都紧挨着，如果其中一个过程需要增加空间，那么将会影响整个进程的其他过程，需要修改它们的起始地址，可能还需要修改页表等，这个开销是很大的．鉴于分页技术的提出只是考虑物理存储上的问题，使得一个进程不必连续的物理空间，但是没有考虑程序本身的结构，所以提出分段，每个段是一个逻辑实体
思想：用户进程地址空间按程序自身的逻辑实体划分为若干个程序段，长度可不同，每个段有一个段名，每个段都是独立的空间；物理内存空间被动态划分为若干个长度不同的区段，以段单位分配，每个段地址连续，段与段之间地址可不连续
地址表示：段号 ＋ 段内地址
优点是考虑了程序本身的逻辑结构，某一过程的改变不会影响其他过程，系统开销小
缺点是按段分配，会产生外部碎片问题
６ 段页结合：将分段与分页的优点结合到一起了．
分页的优点是一个进程的内存物理地址空间不必连续，内存利用率高，缺点一个进程的所有过程都紧凑的挨着，若一个过程需要改变，可能会影响所有的其他过程，系统开销大；
分段的优点是按进程的逻辑结构来分段，每个段是独立的地址空间，每个段连续，不同段不会相互影响；缺点是在内存中按段分配，会产生严重的外部碎片问题，内存利用率低
如果能把分页和分段的优点结合到一起，那最好不过了
思想：进程按照程序的逻辑结构划分为若干段，每个段为独立的地址空间；每个段再分页，每个页面固定大小；实际物理内存分配按页分配，不必连续空间
逻辑地址：段号 ＋ 段内地址（页号 ＋ 页内地址）
段页式存储管理：每个进程有一个段表，记录了所有的段，每个段有一个页表，记录了段内的所有的页；即每个进程有多个页表 -
26. 虚拟内存技术？
提出背景：软件的越来越大，内存无法同时容纳那么多的需要大内存的软件
基本思想：当进程运行的时候，先将其一部分装入内存，当要执行的指令或访问的数据在内存时，则立刻执行相应的映射，如果要执行的指令或访问的数据不在内存中，则执行缺页中断，由操作系统负责将需要的内容从磁盘装入内存，然后重新执行失败的指令
虚拟地址空间：分配给进程的虚拟内存，虚拟内存可以比物理内存还大
虚拟地址：在虚拟内存中的地址，当访问虚拟地址时，系统将虚拟地址送到MMU，映射为实际的物理地址，再执行访问
虚拟＋页式存储管理
即把虚拟内存与页式存储结合起来
进程的虚拟内存进行分页管理
进程开始执行之前，不是装入所有的页面，而是只装入０个或１个页面
之后随着进程运行的需要，动态装入其所需的页面
当内存空间满了，则需要使用某种算法置换出某个旧的页面，以装入新的页面
如果旧页面被修改过，则需要将修改先写回磁盘，如果没有被修改过，则不需要回写
-
27. 页面置换算法
最佳页面置换算法
置换出以后不再需要的，或者在最远的将来才需要的页面
无法实现，因为无法预测哪些页面什么时候会被需要
一般作为一种标准来衡量其他算法的优劣
先进先出算法：最老页面
选择最先进入的页面，即已在内存中存留时间最长的页面，置换出去
缺点：很多时候，很多常用的页面在内存中存留时间很长，但却不适合被置换出去，因为常用，可能马上就会又被用到
第二次机会算法：最老未被使用页面
为避免先进先出将常用的页面置换出去，第二次机会算法将在内存中存留时间最长，但是却没有被访问的页面置换出去
通过设置一个R位，一开始置为０，并且按进入内存的时间顺序把页面排成一个链表，如果页面被访问过，则将Ｒ置为１．
当需要置换页面出去时，按时间顺序从链表头部开始寻找，如果Ｒ位为１，说明页面被访问过，则将其置为０，并修改进入内存时间，放入链表末尾，仿佛刚进入内存的页面一样；如果Ｒ位为０，则表示未被访问过，则将找到的第一个的Ｒ为０的页面置换出去
时钟页面置换算法：最老未被使用页面
是第二次算法的优化，因为第二次算法每次需要在链表中移动页面，效率不高
将所有的页面都保存在环链表中，指针指向最老的页面
如果Ｒ为０，则置换这个页面，将新页面插入这个位置
如果Ｒ为１，则将其置为０，并向前移动一个位置，直到找到Ｒ为０的页面
最近最少使用LRU(Least Recently Used)：最近一段时间最少被使用的页面
置换最近使用出次数最少的页面，性能最接近最佳页面置换算法
实现方式
第一种硬件实现：为每个页面设置一个计数器，如果被访问就＋１，发生缺页中断时就选择计数器值最小的置换出去．缺点内存开销大，每个页表项都需要增加一个计数器，而且系统开销大，每访问一个页面，就要更新一次页表项
第二种硬件实现：假设有ｎ个页面，则使用一个ｎ＊ｎ的矩阵，当第ｉ个页面被访问时，先将第ｉ行全部置为１，再将第ｉ列全部置为０．发送缺页中断时，选择二进制数值最小的行，就是最近最少被访问的页面
最不常用算法NFU：置换访问页数最少的页面置换，LRU的软件解决方案
软件计数器，一页一个，初值为０，Ｒ位被访问为１，不被访问为０
每次时钟中断，计数器加Ｒ
发送缺页中断时，选择计数器最小的置换
缺点：会记录前面所有的访问，导致之前很久的访问对后面置换策略影响过大
NFU与LRU的区别：都是选择访问次数最少的，LRU是每次访问都被记录，NFU是每个时钟中断才记录一次
老化算法aging：优化NFU的缺点
NFU的问题是之前很久的访问对后面的置换算法影响过大
老化算法：
也是一个计数器，一页一个，初值为０，Ｒ位１被访问，０未被访问
发生时钟中断才记录一次
不同的是：老化算法记录时是将所有的计数器值右移一位，然后这次的Ｒ位加在左边，这样就淡化了过去访问页面对置换算法影响过大的缺点，因为每记录一次都会右移一位，这样过去的页面访问的影响就会越来越小，而当前和最近的访问影响更大，这也就是老化的含义
当发送页面中断时，也是选择计数值最小的置换出去
工作集算法：选择不在工作集的页面置换出去
引入一个工作集的概念：根据程序的局部性原理，一段时间内总是集中的访问某些页面，因此，设置一个时间Ｔ，把在过去Ｔ时间内访问的页面集合称为工作集
实现：
设置一个时间Ｔ，表示在过去时间Ｔ内访问到的页面称为工作集
记录每个页面的最后访问时间，与Ｒ位
当发生缺页中断时，搜索页表
如果Ｒ位为１，则将该页面最后访问时间设置为当前时间，并把Ｒ置为０
如果Ｒ位为０，则比较其当前时间－最后访问时间是否大于Ｔ
如果是，则表示可置换
如果不是，则记录当前时间－最后访问时间的最大值，扫描下一个页面
页面置换算法小结
最佳页面置换算法（OPT）：性能最优但不可实现，作为衡量标准
先进先出算法（FIFO）：可能置换出经常使用的页面
第二次机会算法（SC）：比FIFO有很大改进
时钟算法（Clock）：基于第二次机会算法的改进，链表改为循环链表
最近最少使用算法（LRU）：最接近OPT，但是很难实现，有硬件实现方案
最不常用算法（NFU）：LRU相似的软件实现，但是过去很久的页面访问对现在的页面置换影响过大
老化算法（Aging）：非常相似LRU的有效算法，优化了NFU的缺点
工作集算法（Working Set）：实现起来开销大
工作集时钟算法：好的优秀的算法 -
28. 概念：颠簸
虚拟内存中，页面频繁的在内存和磁盘中调度，如果缺页中断频繁发生，花在页面调度的时间比进程运行时间还长，就会使性能急剧下降，这种现象称为颠簸 -
29. 写时复制
这是在内存或磁盘上复制页面时提高效率的一种技巧，当复制时，只是增加一个指针指向这个页面，如果需要修改页面时，才真正执行复制这个动作，把这个页面复制到另外一页
-
30. 文件系统？
进程是对CPU的抽象
地址空间是对物理内存的抽象
文件是对磁盘的抽象
文件系统以名存取文件
文件类型：
普通文件（主要讨论的），字符特殊文件（用于IO设备），块特殊文件（用于磁盘设备） -
31. 文件一般有哪些属性？
文件名
文件大小
创建的时间日期
最后修改时间
最后访问时间
创建者
保护：谁可以存取文件，以什么方式存取
口令：存取文件时需要的口令
各类标志（只读，隐藏，系统，存档，随机存取/顺序存取，临时文件等） -
32. 文件操作？
creat : 创建不包含任何数据的文件
delete : 删除不需要的文件
open : 使用文件之前，必须打开文件；open调用把文件的ｉ节点装入内存，以便后续的快速存取
close : 存取结束之后，关闭文件，系统限制打开文件的最大数量，所以用完的文件需要关闭
read : 从文件读取数据，必须指定读取多少数据，存放在哪个缓存区
write : 向当前位置写数据．如果是末尾，则增加数据，如果在文件中间，则覆盖后面的数据
append : 往文件末尾增加数据
seek : 对于随机存取文件，seek调用可以调整当前指针指向的位置，当seek将指针调到特定的位置，读写操作可从该位置开始读写
get attribute : 读取文件属性
set attribute : 设置文件属性
rename : 重命名 -
33. 文件目录？
一级文件目录：实现简单，但是如果文件很多的话，就不好找了
层次文件目录：目录树的形式实现
绝对路径名：从根目录开始，全部写出来
相对路径名：从当前目录开始，./表示当前目录，../表示当前目录的父目录
目录的相关操作：
creat：创建目录(mkdir)
delete：删除目录
opendir：打开目录，为列出目录内容，需先打开目录
closedir：关闭目录
readdir：读取目录
rename：目录重命名
link：连接技术允许多个目录中出现同一个文件，共享
unlink：删除目录项 -
34. 文件系统的实现
将磁盘空间分成若干个块
１．连续分配：实现简单，随机存取，但是不可扩展，磁盘易碎片化
２．链表分配：磁盘利用率高，但是不可随机存取，存取速度慢
３．在内存中链表分配：在内存中存一张表，记录所有的磁盘块的信息，哪一个文件是从那一块开始的，下一块等信息．缺点是太占内存了
４．i节点分配：用一个i节点记录文件的基本属性，及文件所占的磁盘块的地址，存放在磁盘，当进程打开文件时，才将i节点读入内存，以便存取文件．如果文件太大，占用的磁盘块太多，导致i节点也很大，那么就是用多级i节点，即i节点存放磁盘块地址的最后一块，存放另一个存放了磁盘块地址的磁盘块，以此类推 -
35. 目录的实现
在linux中一切皆文件，包括目录也是文件
系统有一个根目录
每一个目录下面有一系列的目录项，一般目录项都是固定长度的，目录项记录的是文件名与i节点号，普通文件和子目录都算是文件，所以文件名也可能是子目录名，那么它的i节点号自然就是保存子目录的属性和磁盘块地址
所以这样一层一层的构成了一颗目录树 -
36. 文件共享，硬链接与软连接
每个文件都有配有一个i节点，i节点中存有这个文件的属性与磁盘块地址
每一个目录项中存有一个文件名和一个i节点号
所以，linux中，如果需要文件共享，可以把不同目录项，设置不同的文件名，但是i节点号还是用的同一个i节点号，这就是硬链接，i节点会记录连接在这个i节点的数量，当从某个目录项删除这个文件时，连接数减一，只有当连接数量为０，才真正删除这个文件．
硬链接的缺点是会受系统的限制，不允许对目录创建硬链接，不允许在不同的文件系统的文件间创建硬链接，因为i节点本来就是相对于某个文件系统内部而建立的，如果跨越文件系统了，会产生混乱
硬链接命令：ln fileA fileB
软连接命令：ln -s fileA fileB
软连接是创建一个新的链接文件，这个新的链接文件有自己的i节点号，系统知道这是一个链接文件，链接文件保存了指向另一个所连接的文件的路径，当打开这个连接文件时，系统会根据文件中的路径取指向另一个文件
软连接的优点是不受系统的限制，可以随意链接
缺点是它仅仅是保存了路径，而被链接的文件并不知情，因此i节点的链接数没有＋１，所以当被连接文件被删除或者被转移路径之后，软连接就失效了． -
37 IO控制方式
程序控制IO：当发生IO时，CPU采用轮询的方式不断查询IO是否完成．所以又称为忙等
中断控制IO：当发生IO时，CPU去做其他事情，IO操作完成之后，IO设备给CPU发出一个中断请求．这就是中断控制IO，主要是为了避免轮询，提高CPU利用率
但是，由于大量的中断操作，仍旧影响CPU的性能
DMA控制IO：
首先先搞清楚DMA是什么．．
DMA(Direct Memory Access)：直接存储器是一个特殊的硬件设备，它可以独立于CPU而访问系统总线．当系统需要IO操作时，CPU就把总线控制权交给DMA，由DMA直接控制IO操作的进行，当IO操作完成了之后，再有IO设备给CPU一个中断，告知其IO操作已完成
因此，使用DMA控制IO，CPU不需要大量的中断，只需要把IO需求交给DMA就行了．比中断控制IO性能更高
-
38. 死锁的四个基本条件？
死锁：如果一个进程集合里面的进程都在等待集合中其他进程发生的时间，呢么就是死锁．都在等待，没有进程能够继续运行
四个基本条件
互斥：每个资源只能分配给一个进程
占有并等待：已经得到了某个资源的同时可以再请求其他的资源
非抢占式：进程不能强行把资源从其他进程那里抢过来，只能等它主动释放
环路等待：系统中有两个或两个以上的进程形成了一个环路，环路中的每个进程都在等待下一个进程释放资源 -
39. 处理死锁的方式？
处理死锁的方式主要有四种：忽略，检测死锁并恢复，动态分配资源，破坏四个基本条件
下面一个一个来讲
忽略（鸵鸟算法）：忽略死锁的存在，如果死锁发生的频率非常低，甚至比机器出现其他故障的频率还低，那么在工程上来说，忽略它是可取的
检测死锁并恢复：检测死锁到底有没有发生，发生了的话就恢复．让死锁发生
那么如何检测死锁到底有没有发生呢？一种方法是判断资源有向图是否成环
死锁了如何恢复呢？比如可以利用抢占恢复，或者kill进程等
动态分配资源：在分配资源时避免死锁
安全状态：即使所有进程突然请求最大的资源量，仍然存在某种次序使得每一个进程都能运行完成，这种状态称为安全状态
动态分配资源就是要保证系统一直处于安全状态．
对每一个请求进行检查
如果分配了资源，系统仍然处于安全状态，就分配资源
如果某个进程的资源请求会使得系统处于不安全状态，那么系统拒绝这个请求
代表：银行家算法（dijkstra）
想法是很好的，实用性不强，但是很多时候并不能预先知道所有的资源需求量
破坏四个基本条件
互斥条件：如果让两个进程同时占有一个资源，造成混乱，pass
占有并等待：如果让进程一次性请求所有的资源，如果有一个不满足，则拒绝这个请求．确实可以避免死锁，但是既然能预先知道所有的资源需求，为何不用银行家算法呢？
非抢占式：如果变成抢占式，造成混乱，pass
环路等待：只剩下一个环路等待了．破坏环路等待可以将资源编排序号，所有的进程都必须按资源排序来申请资源，不允许申请比自己拥有的资源序号低的资源．这个方法很不错，确实可以预防死锁．但是由于资源众多，一直找不到一个所有人都满意的资源序号，所以．．． -
40. 通信死锁？
进程Ａ给进程Ｂ发消息，发完之后就阻塞了，等待进程Ｂ的回复，而进程Ａ一直都在阻塞着等待进程Ｂ的消息
但是不幸的是，消息丢失了．．．
所以这两个进程就一直阻塞在这里了．．
解决办法就是：超时重传机制（计算机网络，可靠数据传输原理） -
40. 饥饿？
有时候没有发生死锁，也有进程一直得不到资源
比如一个打印机，每次优先处理最短的文件
那么，如果有源源不断的短文件到来的话，长文件就永远得不到打印机资源了
解决办法：动态优先级，随着等待时间的增长，优先级不断增加