操作系统期末重点复习 （南昌大学）

本人一名大三学生，最近要期末考试了自己整理一下操作系统需要复习的重点希望对大家的期末复习有帮助^-

带！！的是老师着重强调的

第一章–计算机系统概述

1.线代操作系统的特点和主要功能

并发：指两个或多个事件在同一时间间隔内发生

共享：指系统中的资源可供多个并发执行的进程使用

虚拟：虚拟是指把物理上的实体变为若干逻辑上的对应物

异步：多道程序环境下由于资源有限，进程的执行并不是贯彻到底的，而是走走停停，以不可预知的速度向前执行

功能：

a.操作系统作为计算机资源的管理者：处理机管理、存储器管理、文件管理、设备管理

b.操作系统作为用户和计算机硬件系统之间的接口：命令接口（联机命令和脱机命令）、程序接口

c.操作系统实现了对计算机资源的扩充

2.不同的操作系统的特点：

a.批处理：

单批道：每次内存中仅放一道作业，每当它在运行期间发出IO请求时就会让CPU陷入低速的IO中导致CPU空闲等待时间过长

多批道：允许多个程序同时进入内存并允许它们在CPU上交替的运行，资源利用率高但不提供人机交互能力，无法调试

b.分时操作系统

分时技术：将处理机的运行时间分为很短的时间片，按照时间片轮流把出库胡分配给各个联机作业使用

分时操作系统是指多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时和主机进行交互操作而不受干扰。

主要有同时性、交互性、独立性、及时性的特点

c.实时操作系统

硬实时系统：某个动作必须在规定时间发生

软实时系统：接受偶尔违反时间规定且不会引起永久性伤害

d**.网络操作系统**

网络操作系统将计算机网络中的各台计算机有机的结合在一起，提供一种统一、经济而有效的使用各台计算机的方法，最主要的特点就是网络中各种资源的共享及各台计算机之间的通信

第二章–进程与线程

1.程序顺序执行和并发的特点

顺序执行时

1.顺序性：程序严格按照顺序执行

2.封闭性：程序运行时独占全机资源

3.可再现性：程序按顺序一定的速度执行，可再现

并发执行时

1.间断性：由于资源有限，并发进程之间会相互制约

2.失去封闭性：并发的程序共享计算机资源，这些资源的状态由这些程序一起改变

3.不可再现性：执行速度不确定，不可再现

2.！！进程的基本概念以及进程状态的切换

PCB：为了使参与并发的每个程序都能独立的运行，必须为之配备一个专门的数据结构，称为进程控制块PCB，系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程

进程实体：由程序段、相关数据段和PCB三部分构成进程实体（进程映像）

进程：1）进程是程序的一次执行。2）进程是一个程序及数据在处理机上顺序执行发生的活动。3）进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的基本单位

PCB是进程存在的唯一标识

进程的状态有：就绪态、运行态、阻塞态

就绪态-运行态：操作系统从就绪链表中调度一个进程PCB进CPU

运行态-就绪态：一个进程时间片用完CPU必须去调度下一个进程时

运行态-阻塞态：进程在运行时需要等待一个事件的完成

阻塞态-就绪态：进程等待的事件完成

3.进程同步与互斥

同步：直接制约关系，为了完成某种任务的两个或者多个进程之间相互协调等待传递信息所产生的制约关系

互斥：间接制约关系，临界资源只能被一个进程访问到，其余访问的进程需dengdai

4.！！经典同步问题

1.生产者消费者问题

//简单 
semaphore mutex=1;
semaphore empty=n;
semaphore full=0;
producer(){
    while(1){
        produce an item in nextp;
        p(empty);
        p(mutex);
        add nextp to buffer;
        v(nutex);
        v(full);
    }
}
consumer(){
    while(1){
        p(full);
        p(mutex);
        remove an item from buffer;
        v(mutex);
        v(empty);
        consume the item;
    }
}
//复杂
//桌上只有一个盘子，每次只能放入一个水果，爸爸专门放苹果，妈妈专门放橘子，儿子专门等橘子，女儿专门等苹果

//只有盘子为空的时候才可以放入苹果，只有盘子里有各自需要的水果时儿子女儿才可以取出
semaphore plate=1,apple=0,orange=0;
dad(){
    while(1){
        prepare an apple;
        p(plate);
        put the apple on the plate;
        v(apple);        
    }
}
mom(){
    while(1){
        prepare orange;
        p(plate);
        put the orange on the plate;
        v(orange);
    }
}
son(){
    while(1){
        p(orange);
        take an orange from the plate;
        v(plate);
        eat;
    }
}
daughter(){
    while(1){
        p(apple);
        take an apple on the plate;
        v(plate);
        eat;
    }
}

2.读者-写者问题

//读进程优先
int count=0;
semaphore mutex=1;
semaphore  rw=1;
writer(){
    while(1){
        p(rw);
        write;
        v(rw);
    }
}
reader(){
    while(1){
        p(mutex);
        if(count==0)
        	p(rw);
        count++;
        v(mutex);
        reading;
        p(mutex);
        count--;
        if(count==0)
        	v(rw);
        v(nutex);
    }
}
//写进程优先
int count=0;
semaphore mutex=1;
semaphore  rw=1;
semaphore  w=1;
writer(){
    while(1){
        p(w);
        p(rw);
        write;
        v(rw);
		v(w);
    }
}
reader(){
    while(1){
        p(w);
        p(mutex);
        if(count==0)
        	p(rw);
        count++;
        v(mutex);
        v(w)	
        reading;

        p(mutex);
        count--;
        if(count==0)
        	v(rw);
        v(mutex);
       
    }
}

3.哲学家进餐问题

//当哲学家两边的筷子都可用的时候才允许拿起筷子
semaphore chop[5]={1,1,1,1,1};
sempahore mutex=1;
pi(){
    while(1){
        p(mutex);
        p(chop[i]);
        p(chop[(i+1)%5]);
        v(mutex);
        eat;
        v(chop[i]);
        v(chop[(i+1)%5]);
        think;
    }
}

4.吸烟者问题

int num=0;
semaphore offer1=0;
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;
process p1(){
    while(1){
        num++;
        num=num%3;
        if(num==0)
        	v(offer1);
        if(num==1)
			v(offer2);
		if(num==2)
			v(offer3);
		任意两种材料放在桌子上
		p(finish);
    }
}
process p2(){//拥有烟草
    while(1){
        p(offer3)
        拿纸和胶水卷成烟抽掉
        v(finish);
    }
}
process p3(){//拥有纸
    while(1){
        p(offer2)
        拿烟草和胶水卷成烟抽掉
        v(finish);
    }
}
process p4(){//拥有胶水
    while(1){
        p(offer1)
        拿纸和烟草卷成烟抽掉
        v(finish);
    }
}

5.线程的基本概念和进程的区别

线程可以理解为轻量级的进程，是CPU基本的执行单元，也是程序执行流的最小单元，线程自己基本上不拥有系统资源

进程与线程的比较：

1）调度：在引入线程的操作系统中，线程是独立调度的基本单位，线程切换的代价远小于进程

2）并发性：引入线程的操作系统，不仅进程之间可以并发，多个线程之间也可以并发，提高系统的并发量

3）拥有资源：进程是操作系统中拥有资源的基本单位，而线程不拥有系统资源

4）独立性：每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许有其他进程访问。但同一进程间的线程共享进程的资源和地址空间

5）系统开销：在创建和撤销进程时，系统都需要为进程分配PCB以及其他资源空间，但线程所需资源少，切换代价小

6）支持多处理机系统：对于传统的单线程进程，不论有多少处理机，进程只能运行在一台处理机上，但对于多线程进程，可以将进程中的多个线程分配到多个处理机上去执行

6.作业调度和进程调度的基本概念

一个作业从提交到完成往往需要经历三级调度

1）高级调度（作业调度）

按照一定的原则从不外存上处于后备队列的作业中挑选一个（或多个）给它们分配内存、IO设备等资源，并建立相应的进程，以使它们获得竞争处理机的权利

作业调度就是外存和辅存之间的调度（选取作业）

2）中级调度（内存调度）

中级调度是为了提高内存的利用率和系统吞吐量，将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态，当它们具备运行条件并且内存也有空闲，中级调度决定将外存中那些就绪进程调回内存

中级调度实际上是存储器管理中的对换功能

3）低级调度（进程调度）

按照某种算法从就绪队列中选取一个进程，将处理器分配给它

进程三级调度的关联：

1）作业调度为进程活动做准备，进程调度使进程正常活动起来

2）中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间

3）作业调度次数少，中级调度次数略多，进程调度的频率最高

4）进程调度是最基本的 不可或缺的

7.！！典型的调度算法

CPU利用率：CPU有效工作时间/CPU有效工作时间+CPU空闲等待时间

系统吞吐量：单位时间CPU完成作业的数量

周转时间：周转时间=作业完成时间-作业提交时间

平均周转时间：（作业1周转时间+…作业n周转时间）/n

带权周转时间：作业周转时间/作业实际运行时间

平均带权周转时间：（作业1带权周转时间+…作业n带权周转时间）/n

1.先来先服务（FCFS）算法（进程、作业调度）

作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
1	8	2	8	0	10	2	1
2	8.4	1	10	1.6	11	2.6	2.6
3	8.8	0.5	11	2.2	11.5	2.7	5.4
4	9	0.2	11.5	1.5	11.7	2.7	13.5

FCFS属于不可剥夺算法，从表面看对所有作业都公平但是若一个长作业到达系统，会使后面的短作业长时间陷入等待，因此它不能作为分时和实时系统的调度算法

FCFS特点：算法简单但效率低；对长作业有利但对短作业不利，有利于CPU繁忙而不利于IO繁忙

2.短作业优先（SJF）（进程、作业调度）

从后背队列里面选择一个若干运行时间最短的作业

作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
1	8	2	8	0	10	2	1
2	8.4	1	10.7	2.3	11.7	3.3	3.3
3	8.8	0.5	10.2	1.4	10.7	1.9	3.8
4	9	0.2	10	1	10.2	1.2	6

缺点：

1.对长作业帮不利，而且有可能会导致饥饿现象

2.该算法未考虑紧迫性的问题，不能保证紧迫作业会被优先处理

SJF算法的平均等待时间、平均周转时间最少

3.优先级调度算法（进程、作业调度）

根据新高优先级进程能否抢占正在进行的进程可以分为

1）非抢占式优先级调度算法

2）抢占式优先级调度算法

根据进程创建后优先级能否更新可以分为：

1）静态优先级

2）动态优先级

4.高响应比优先调度算法（主要用于作业调度）

先计算每个作业的响应比

响应比=等待时间+要求服务时间/要求服务时间

5.时间片轮转算法

时间片轮转算法主要适用于分时系统，系统将所有的就绪进程按照FCFS策略排成一个就绪队列，按照时间片时间进行服务，如果能进程未结束则重新去队尾排队

6.多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合与发展

实现思路：

1.设置多个就绪队列，并为每一个队列赋予不同的优先级，第一级的优先级最高，越大次之

2.赋予不用优先级不用的时间片，优先级越高时间片越小

3.每一个队列都采用FCFS算法，新进程进入内存后首先将它放在第一级队列的末尾，按照FCFS等待调度，如果可以一个时间片运行玩=完，则撤离系统，如果不能则加入第二级队列，以此类推

4.按照优先级调度，只有第一级队列为空才会调度第二级中的进程，若处理机在执行第i级队列中的某个进程，又有优先级高的新进程进入则必须将当前运行的进程放在该队列的末尾执行新进程

特点：

1）终端型作业用户：短作业优先

2）短批处理作业用户：周转时间较短

3）长批处理作业用户：不会长时间得不到处理

8.死锁的概念产生的原因

死锁：多个进程因为竞争资源而造成互相等待，且若无外力作用进程无法向前推进的现象

原因：

1.系统中资源的竞争

2.进程推进顺序非法

死锁产生的必要条件：

1）互斥条件：临界资源互斥性

2）不剥夺条件：进程表获得资源在未使用完之前不能被其他进程强行夺走，只能自己主动释放

3）请求并保持：获得资源后请求新的资源，而该资源已经被其他进程占有也不释放自己所持有的资源

4）循环等待链：存在进程资源的循环等待链，链中的每个进程都等待下一个进程所持有的资源

9.！！银行家算法以及死锁的解除

1）数据结构：

可利用资源Available：每一类可用资源数目

最大需求资源Max：每个进程对资源的最大需求

分配矩阵：Allocation 已经分配给进程的资源

需求矩阵：Need 对每一类资源的需求 Need=Max-Allocation

2)银行家算法描述

3）安全性算法

设置工作向量work，有m个元素，表示系统中剩余可用的资源数目，在执行安全性算法之前，work=Available

a.初始时安全序列为空

b.从need中找到符合下面条件的行：

该行对应的进程不在安全序列中，而且该行小于或等于work向量，找到后将该进程加入到安全序列；若找 不到执行d步骤

c.进程Pi进入到安全序列之后，可以顺利执行释放分配给它的资源，因此work=work+allocation

d.若此时安全序列已经有所有的进程，则系统处于安全状态，否则处于不安全状态

银行家算法举例

假设当前系统中的资源的分配和剩余情况如表

进程|资源情况	MAX(A B C)	Allocation(A B C)	Need	Available(A B C)
P0	7 5 3	0 1 0	7 4 3	3 2 2
P1	3 2 2	2 0 0	1 2 2
P2	9 0 2	3 0 2	6 0 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 3	0 0 2	4 3 1

(1)p1发出请求（1,0,2）系统按照银行家算法进行检查

Request1(1,0,2)<=Need(1,2,2);

Request1(1,0,2)<=Available(3,2,2);

系统先假定可以为P1分配资源，并修改

Available=Available-Request1=(2,3,0);

Allocation=Allocation+Request=(3,0,2);

Need=Need-Request=(0,2,0);

Work=Available=(2,3,0);

进行安全性检查

进程|资源情况	work（A B C）	Need（A B C）	Allocation（A B C）	Work+Allocation
P1	2 3 0	0 2 0	3 0 2	5 3 2
P3	5 3 2	0 1 1	2 1 1	7 4 3
P4	7 4 3	4 3 1	0 0 2	7 4 5
P0	7 4 5	7 4 3	0 1 0	7 5 5
P2	7 5 5	6 0 0	3 0 2	10 5 7

由安全性检查可得知存在安全序列{1,3,4,0,2}，因此系统是安全的，可以立即将P1申请的资源分配给P1

进程|资源情况	MAX(A B C)	Allocation(A B C)	Need	Available(A B C)
P0	7 5 3	0 1 0	7 4 3	2 3 0
P1	3 2 2	3 0 2	0 2 0
P2	9 0 2	3 0 2	6 0 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 3	0 0 2	4 3 1

死锁解除：

1）资源剥夺法：挂起某些死锁线程，并抢占它们的资源，将这些资源分配给其他死锁线程

2）撤销进程法：强制撤销部分甚至全部死锁线程并剥夺这些线程的资源

3）进程回退法：让一个进程或多个进程回退到没有死发生的地步