一. 操作系统概述
1、 操作系统的主要功能
进程与处理机管理：作业和进程调度、进程控制和进程通信；
存储管理：内存分配、地址映射、内存保护和内存扩充；
设备管理：缓冲区管理.设备分配.设备驱动.设备无关性
文件管理：文件存储空间的管理、文件操作的一般管理、目录管理、文件的读写管理和存取控制；
作业管理：包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。
2、操作系统的基本特征
并发：两个或多个活动在同一给定的时间间隔进行；
共享：计算机系统中的资源被多个任务所共用。
异步：多道程序下，各程序的执行过程由程序执行时的现场决定。
3、操作系统的主要类型
多道批处理系统：用户作业成批的处理，作业建立、过渡、完成都自动有系统成批完成，且在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制下，相互穿插运行。
分时系统：系统内存在若干并发程序对CPU时间片共享使用。例子：UNIX
实时系统：计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。
个人机系统：用于个人机（PC机）的系统，包括单用户系统和多用户操作系统。
网络操作系统：将分布在各处的计算机和终端设备通过数据通信系统结合在一起构成的系统。
分布式操作系统：运行在不具有共享内存的多台计算机上，但在用户眼里却像是一台计算机。
二、进程管理
1、什么是进程，进程与程序的区别和关系：
进程：进程是可以和别的计算机并发执行的计算；进程是程序的一次执行，是在给定内存区域中的一组指令序列的执行过程；进程是一个程序在给定活动空间和初始条件下在一个处理机上的执行过程；进程可定义为一个数据结构和能在其上进行操作的一个程序；进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
进程与程序的区别：①程序是静态概念，而进程是程序的一次执行过程，是动态概念。②进程是一个能独立运行的单位，能与其它进程并发执行。进程是作为自愿申请和调度单位存在的；而通常的程序是不能作为一个独立运行的单位而并发执行的。③程序和进程无一一对称关系。④各个进程在并发执行过程中会产生相互制约关系，而程序本身是静态的，不存在这种异步特征。
2、进程的基本状态及其变化：
执行态：当前进程已分配到CPU，它的程序正在处理机上运行；
就绪态：进程已具备运行条件，但因为其它进程正占用CPU，所以暂时不能运行而等待分配CPU的状态；
阻塞态：因等待某件事件发生而暂时不能运行的状态。
就绪→执行：被调度程序选中，分配到CPU。
执行→阻塞：因缺乏某种条件而放弃对CPU的占用。
阻塞→就绪：阻塞态进程所等待的事件发生了。
执行→就绪：进程用完时间片。
3、进程由哪些部分组成，进程控制块的作用:
进程由PCB、程序部分和数据集合组成；进程控制块是进程组成中最关键的部分，进程控制块（PCB）是进程存在的唯一标志，每个进程有唯一的进程控制块，系统根据PCB对进程实施控制和管理，PCB是进程存在的唯一标志。
4、什么是进程的同步与互斥：进程的同步：
进程的同步：进程间共同完成一项任务时直接发生相互作用的关系；
进程的互斥：两个逻辑上本来完全独立的进程由于竞争同一个物理资源而相互制约。
5、多道程序设计概念：
多道程序设计是在一台计算机上同时运行两个或更多个程序，多道程序设计具有提高系统资源利用率和增加作业吞吐量的优点；
6、什么是临界资源、临界区：
临界资源：一次仅允许一个进程使用的资源；
临界区：每个进程访问临界资源的那段程序。
7、什么是信号量，PV操作的动作，进程间简单同步与互斥的实现：
信号量是一种特殊的变量,实际上就是用来控制进程状态的一个代表某一资源的存储单元。表现形式是一个整型S和一个队列.
PV操作:
P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P（S）时信号量S的值减1，若结果不为负则P（S）执行完毕，否则执行P操作的进程暂停以等待释放。执行V操作V（S）时，S的值加1，若结果不大于0则释放一个因执行P（S）而等待的进程.
P操作:也称为down()/wait()操作,使S=S-1,若S<0,进程暂停执行,放入信号量的等待队列.
V操作:也称为up()/signal()操作,使S=S+1,若S<=0,唤醒等待队列中的一个进程.
具体参考：操作系统 信号量与PV操作
8、什么是死锁；产生死锁的必要条件；死锁预防的基本思想和可行的解决办法；
死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。
产生死锁的四个必要条件：
（1） 互斥条件：一个资源每次只能被一个进程使用。
（2） 请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3） 不可抢占条件:进程已获得的资源，在末使用完之前，不能强行剥夺，只能在进程使用完时由自己释放。
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。因此可以写下如下的预防死锁的方法。
避免死锁的方法：
（1）破坏“互斥”条件:就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他三个必要条件，而不去涉及破坏“互斥”条件。
（2）破坏“请求和保持”条件:在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。
方法一：所有进程在运行之前，必须一次性地申请在整个运行过程中所需的全部资源。这样，该进程在整个运行期间，便不会再提出资源请求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件。
该方法优点：简单、易行且安全。
缺点：
a.资源被严重浪费，严重恶化了资源的利用率。
b.使进程经常会发生饥饿现象。
方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。这样，一个进程在需要资源S时，须先把它先前占有的资源R释放掉，然后才能提出对S的申请，即使它可能很快又要用到资源R。
（3）破坏“不可抢占”条件：允许对资源实行抢夺。
方法一：如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。
方法二：如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，该方法才能预防死锁。
（4）破坏“循环等待”条件：将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁。
利用银行家算法避免死锁：
设进程i提出请求Request[i,j] (i还需要资源j Request[i,j]个)，则银行家算法按如下规则进行判断。
(1) 如果Request[i,j]≤Need[i,j]，则转向（2），否则认为出错，因为它所需要的资源数已超过它所需要资源的最大值。
(2) 如果Request[i,j]≤Available[j]，则转向（3）；否则表示尚无足够资源，Pi需等待。
(3) 假设进程i的申请已获批准，于是修改系统状态：
Available[j]=Available[j]-Request[i,j]
Allocation[i,j]=Allocation[i,j]+Request[i,j]
Need[i,j]=Need[i,j]-Request[j]
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
死锁的解除：
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要两种方法：
（1） 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
（2） 终止（或撤销）进程。终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
安全性算法：
(1) 设置两个工作向量Work=Available；Finish[i]=False
(2) 从进程集合中找到一个满足下述条件的进程，
Finish [i]=False;
Need[i,j]≤Work[j];
如找到，执行(3)；否则，执行(4)(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work[j]=Work[j]+Allocation[i,j];
Finish[i]=True;
Go to step 2;(4) 如所有的进程Finish[i]=true，则表示安全；否则系统不安全。
三、处理机管理
1、作业调度和进程调度的联系：
进程调度是真正让某个就绪状态的进程到处理机上运行，而作业调度只是使作业具有了竞争处理机的机会。简单比喻：作业调度是演员上场前的准备，进程调度是让演员上场表演。
2、作业调度算法：
先来先服务（first come first serve,FCFS）
按作业进入输入井的先后次序安排。优点是实现简单，用先进先出（first input first output,FIFO）队列顺序工作，对相同的或均衡的作业较为合理，缺点是不利于运行时间短的作业。
最短作业优先法（shortest job fist,SJF）
短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。对预计执行时间短的作业（进程）优先分派处理机。
最短作业优先法也就是选实际运行时间小的优先，也就是只考虑运行时间。优点是短作业得到了优先执行，提高了系统的效率。缺点是当作业不断进入时，长的作业有可能长时间排不上队
最高响应比优先法（highest response-ratio next, HRN）
最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。
定时轮转法
轮转法(Round Robin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
按时间片轮转，可分为短时间的固定时间片（如UNIX 操作系统时间片为几毫秒至几十毫秒）和长时间的不固定时间
片（如：Windows操作系统的抢占式多任务方式）。
优先级法
按优先数排队次序工作。分静态和动态：静态是在排队前计算优先数，动态是在调度过程中计算优先数。又可分为用户给定优先数（反映用户要求）和系统给定的优先数，例如，系统给定前台和后台（比如批处理的作业）工作的优先级，一般前台（与用户直接交互的作业）优先。
多级反馈队列列算法
多级反馈队列算法(Round Robin with Multiple Feedback)是轮转算法和优先级算法的综合和发展。
设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。
3、进程调度算法：
先来先服务 （FCFS，first come first served）
在所有调度算法中，最简单的是非抢占式的FCFS算法。
算法原理：进程按照它们请求CPU的顺序使用CPU.就像你买东西去排队，谁第一个排，谁就先被执行，在它执行的过程中，不会中断它。当其他人也想进入内存被执行，就要排队等着，如果在执行过程中出现一些事，他现在不想排队了，下一个排队的就补上。此时如果他又想排队了，只能站到队尾去。
算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平
算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程
最短作业优先（SJF, Shortest Job First）
短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
算法原理：对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。
算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。
最高响应比优先法(HRRN，Highest Response Ratio Next)
最高响应比优先法(HRRN，Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。
算法原理：响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。
算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。
算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。
时间片轮转算法（RR，Round-Robin）
该算法采用剥夺策略。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
算法原理：让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。
算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当
怎样确定时间片的大小：
时间片大小的确定
1.系统对响应时间的要求
2.就绪队列中进程的数目
3.系统的处理能力
多级反馈队列(Multilevel Feedback Queue)
多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
多级反馈队列调度算法描述：
1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能够较好的满足各种类型用户的需要。
周转时间，平均周转时间，带权周转时间
周转时间=作业完成时间−作业提交时间
特别注意作业提交时间不是作业进内存的时间，而是发出请求，提交就开始计时，如果无法安排进内存，那么就等待，等待的这部分时间也要计数。
四、存储器管理
1、存储器的层次
2、用户程序的主要处理阶段
（1）编辑阶段：创建源文件
（2）编译阶段：生成目标文件
（3）连接阶段：生成可执行文件
（4）装入阶段：重定位，装入内存
（5）运行阶段：得到结果
3、存储器的管理功能：内存分配、地址映射、内存保护、内存扩容
4、存储器有关概念：
（1）逻辑地址：用户程序经编译后的每个目标都以0为基地址顺序编址
（2）物理地址：内存中各物理单元的地址是从统一的基地址顺序编址
（3）重定位：把逻辑地址转为内存的物理地址的过程
（4）静态重定位：是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的内存地址。重定位在程序装入时一次完成。
（5）动态重定位：在程序执行期间，每次访问内存之间进行重定位，这种变换是靠硬件地址变换机构实现的。
（6）碎片：内存中容量太小，无法被利用的小分区
4、存储管理基本技术
三种基本的存储管理技术：分区法、可重定位分区法和对换技术
（1）分区发：把内存划分成若干分区，每个分区里容纳一个作业
固定分区：分区的个数、分区的大小固定不变；每个分区只放一道作业
优点：管理方式简单
缺点：内存空间利用率低
动态分区：分区大小和个数依作业情况而定，作业进入内存时才建分区
优点：按需分配内存
缺点：产生大量碎片
（2）可重定位的分区分配：通过紧缩可解决碎片问题；作业在内存中可移动
优点：解决了碎片的问题，提高了主存利用率
缺点：增加了开销，消耗大量的CPU时间
（3）对换技术：作业（或进程）在内存和磁盘间交换，换出暂时不能运行的作业（或进程）；换入具有运行条件的作业（或进程）
4、虚拟存储器
（1）虚拟存储器是操作系统提供的一个假想的超大存储器
（2）虚拟存储器的特征：
虚拟扩充：不是物理上，而是逻辑上扩充了内存容量
部分装入：每个作业不是全部一次性装入内存，而是只装入一部分
离散分配：不必占用连续的空间，而是“见缝插针”
多次对换：所需的全部程序和数据要分多次调入内存
（3）虚拟存储器受到的限制：
指令中表示地址的字长
外存的容量
5、分页存储管理技术
（1）分页的概念
逻辑空间等分为页
物理空间等分为块
逻辑地址表示：（如，页面大小为1K）
内存分配原则：以块为单位。逻辑上相邻的页可以分配在不同的内存块中。
页表：实现从页号到物理块号的地址映射
（2）请求分页的基本思想
地址空间分页，内存分块，页与块大小相同
作业部分装入内存
作业所占的各块不连续
硬件通过页表生成内存地址
若缺页，进行缺页中断处理，换入内存
利用块表可加速地址转换
6、分段存储管理技术
（1）分段的概念
逻辑空间分段：段是信息的逻辑单位，每段对应一个相应的程序模块，有完整的逻辑意义
程序的地址结构
逻辑地址表示：（二维的地址空间）
内存分配：内存以段为单位进行分配，每个段单独占用一块连续的内存分区
段表：实现每个逻辑段到物理内存中分区位置的映射
（2）分页与分段的区别
7、虚存中的置换算法：
（1）先进先出算法（FIFO）：将最先进入内存的页换出内存
当CPU需要访问的页不在内存中时产生了缺页中断，缺页中断是一段程序，就是把外存中的页调入内存，还需要把内存中原有的页放回到外存。缺页中断率就是一个进程执行过程中缺页的次数除以需访问页的总次数得到缺页中断率，这个值越小越好。
这里每列有三行代表三个内存块，当遇到内存中没有的页时（就是缺页）就要用FIFO算法换页，若遇到内存中已经有的页就维持不变。
（2）最佳置换算法（OPT）：将将来不再使用或最远的将来才被访问的页换出内存
（3）最近最少使用置换法（LRU）：将最近一段时间内最久没有使用过的页面换出内存
（4）最近未使用置换法（NRU）：
系统为每一个页面设置两个标志位：当页面被访问时设置R位，当页面（修改）被写入时设置M位。当发生缺页中断时，OS检查所有的页面，并根据它们当前的R和M位的值，分为四类：
（1）！R&！M（2）！R&M（3）R&！M（4）R&M
编号越小的类，越被优先换出。即在最近的一个时钟滴答内，淘汰一个没有被访问但是已经被修改的页面，比淘汰一个被频繁使用但是“clean”的页面要好。
