第一章 操作系统概论

? 什么是操作系统

? 操作系统的功能和主要特征 ? 操作系统的结构 ? 操作系统的分类 ? 多道程序设计的概念 什么是操作系统?

操作系统是人与计算机之间的接口

操作系统是软件与硬件的接口 操作系统可以：屏蔽细节、统一管理硬件、防止违法操作，使计算机的使用更加方便、简单、高效…

? 操作系统是管理硬件的软件… “目录”管理的是什么硬件?

? 操作系统是管理文件和其它软件的软件… 用户发出命令谁来执行？

? 操作系统是解释执行用户命令的控制软件… 操作系统是管理软件和控制软件 操作系统管理什么？控制什么? ? 管理所有硬件资源

冯?诺依曼认为，计算机由五大部件组成:

输入设备、输出设备、存储器、运算器、控制器 OS需要管理CPU(运算器、控制器) 进程管理 OS需要管理memory(内存)内存管理 OS需要管理disk(外存) 文件系统

OS需要管理I/O(输入/输出设备)I/O系统 监控用户对计算机的使用

eg.用户按下ctrl+c时，该用户的当前任务将被kill; 用户写一个文件时，OS需检查是否有权限 操作系统提供接口

向用户和应用软件提供使用接口

eg.用户输入ls时，OS需要将当前目录下的文件列出; 应用程序调用new()时，OS需要分配内存

管理

关键词？

控制 接口

资源 流程

人机

操作系统的定义

操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合——

它们管理和控制计算机系统中的硬件及软件资源，合理的组织计算机的工作流程，以便有效地利用这些资源为用户提供一个功能强大、使用方便的工作环境，从而在计算机与用户之间起到接口作用。

操作系统的功能和主要特征 操作系统做什么？

? 用户告诉操作系统执行hello程序 用户界面 ? 操作系统找到该程序，检查其类型 用户界面 ? 文件系统找到存储该程序的磁盘块 文件管理、设备管理 ? 操作系统将该程序从磁盘上装入内存，父进程创建一个新的子进程，执行hello程序 存储管理、处理机管理 ? 操作系统检查字符串的位置是否正确

? 操作系统找到字符串被送往的设备 设备管理 ? 你在屏幕上看到hello world

操作系统的功能

处理机管理 存储管理 文件管理 设备管理

用户界面

操作系统的结构

进程管理、内存管理、文件系统、IO系统

这四个部分就能使操作系统运转起来

四个基本部分的组合方式…

“微内核”式操作系统结构

? 压缩内核: 将文件系统、设备驱动等部分从操作系统中移出…怎么调用这些功能? 将文件读写变成服务(C/S)，内核提供通信

“虚拟机”式操作系统结构

? 使用硬件最复杂的地方就是多个任务(程序)共同使用，从而互相影响 如果让一个程序独占整个机器，复杂度大幅降低 VM/370采用虚拟机结构 一台虚拟机器

操作系统的结构

整体或模块结构或强内核

分层结构或虚拟机

客户/服务器模型或微内核结构

“操作系统做什么”是动态变化的

? 操作系统的任务会随环境而变化

如实时操作系统—任务响应需满足一定的时限要求 某些场合要求很严格的时限，如导弹控制 某些场合要求不能太久，如键盘响应 某些场合没有时限要求，如屏保

? 操作系统的任务会随时间而变化

Moore定律表明: 设备体积迅速变小、能力迅速增强 出现了嵌入式设备和嵌入式操作系统

各部分的设计和实现也多种多样

硬件在发展、应用在扩展，实现技术也得跟上 早期的计算机非常昂贵…(1948-1970) 计算机使用原则: 尽量让计算机满载 此时操作系统的典型特征: 批处理(Batch system)

各部分设计都以执行作业的数量的最大化为目标：如内存管理应尽量简单

CPU尽量忙才能尽可能多的完成作业 但操作I/O设备时CPU会等待很长时间(如读作业)

调度处理办法: 等待I/O设备时CPU去执行别的作业

前提是内存中有多个作业: 多道程序 Multics: 19xx年开始开发，1969使用

多个程序“同时执行”需要进程调度、内存管理、磁盘存储等多个部分的配合(操作系统大幅改变) 批处理操作系统使用在现在的大型机上

硬件不断发展，越来越便宜

? 1970-1985，$1000能买一个便宜的终端 用户可以坐在终端设备前思考问题了

此时计算机能响应用户，典型特征: 交互(Interactive) 怎么才能做到及时响应? 分时系统

将时间分成时间片。分时影响了进程调度和时钟处理 分时操作系统也常使用在现在的带有多个终端的大型机上(如银行)

操作系统的分类

批处理操作系统（多道批处理） 分时操作系统 实时操作系统 嵌入式操作系统 个人计算机操作系统 网络操作系统 分布式操作系统

批处理操作系统 工作方式：

? 用户将作业交给系统操作员 ? 系统操作员将许多用户的作业组

? 一批作业之后输入到计算机中，在 ? 系统中形成一个自动转接的连续的 ? 作业流

? 启动操作系统

? 系统自动、依次执行每个作业 ? 最后由操作员将作业结果交给用户 典型的

FMS JOB 结构

批处理操作系统特点 多道：

系统中同时有多道作业，同时处于运行状态。 成批处理：

用户自己不能干预自己作业的运行，一旦发现作业错误不能及时改正，并延长开发软件时间，所以适用于成熟的程序。

 

第二篇：操作系统知识点总结

操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

虚拟机：在裸机的基础上，每增加一层新的操作系统的软件，就变成了功能更为强大的虚拟机或虚机器。

操作系统的目标：1. 方便性2. 有效性 3. 可扩充性4. 开放性

操作系统的作用：OS作为用户与计算机硬件系统之间的接口；OS作为计算机系统资源的管理者；OS实现了对计算机资源的抽象（作扩充机器）。

操作系统的特征：并发性；共享性；虚拟性；异步性

推动操作系统发展的主要动力：不断提高计算机资源利用率 ；方便用户；器件的不断更新换代 ；计算机体系结构的不断发展 。

人工操作方式的特点：用户独占全机；CPU等待人工操作；独占性；串行性。缺点:计算机的有效机时严重浪费；效率低

脱机I/O方式的主要优点:减少了CPU的空闲时间;提高I/O速度。

单道批处理系统的特征:自动性 ; 顺序性 ;单道性

多道批处理系统原理：用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。

多道批处理系统的优缺点 资源利用率高 ；系统吞吐量大 ；可提高内存和I/O设备利用率；平均周转时间长；无交互能力

多道批处理系统需要解决的问题（1）处理机管理问题（2）内存管理问题（3）I/O设备管理问题4）文件管理问题（5）作业管理问题

分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。

时间片：将CPU的时间划分成若干个片段,称为时间片，操作系统以时间片为单位,轮流为每个终端用户服务

实时系统与分时系统特征的比较：多路性；独立性；及时性；交互性；可靠性

操作系统的特征：并发性；共享性；虚拟性；异步性

操作系统的主要功能：处理机管理；存储器管理；设备管理；文件管理；作业管理

对处理机管理，可归结为对进程的管理：进程控制（创建，撤消，状态转换）；进程同步（互斥，同步）；进程通信；进程调度（作业调度，进程调度）。

存储器管理功能：内存分配（最基本）；内存保护；地址映射；内存扩充

设备管理功能：设备分配；设备处理（相当于启动）；缓冲管理 ；虚拟设备

文件管理功能：文件存储空间管理；目录管理；文件读写管理；文件保护。

用户接口：命令接口；程序接口；图形接口

传统的操作系统结构：无结构OS；模块化OS结构 ；分层式OS结构

模块化操作系统结构：操作系统是由按其功能划分为若干个具有一定独立性和大小的模块。每个模块具有某个方面的管理功能，规定好模块之间的接口。

微内核的基本功能：进程管理-存储器管理-进程通信管理-I/O设备管理

进程的特征：动态性（最基本）；并发性；异步性；独立性；结构特征（程序段，数据段，进程控制块PCB）

进程的基本属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

进程控制块的基本组成：进程标识符；处理机的状态；进程调度所需信息；进程控制信息。

进程控制一般是由操作系统的内核中的原语来实现

临界资源：如打印机、磁带机等一段时间内只允许一个进程进行使用的资源。

信号量：整型，记录型，and型，信号量集。实现进程互斥，前趋关系，进程同步。

semaphore

同步P操作在互斥P操作前

Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配

Swait(S, 1, 1)表示互斥信号量

Swait(S, 1, 0)可作为一个可控开关（S³1时，允许多个进程进入临界区；S=0时，禁止任何进程进入临界区）

同步机制应遵循的规则：空闲让进；忙则等待；有限等待；让权等待

生产者进程i：

     Repeat

    生产数据nextp；

    wait(empty);

    wait(mutex); 

    buffer[in]:=nextp;

    in=(in+1)%n ;

    signal(full);   

    until false;

消费者进程i：

Repeat  

wait(full);

wait(mutex); 

Nextc=buffer(out);

out=(out+1)%n ;

signal(empty);   

until false;

哲学家i：

Repeat

 wait(SM);

wait(chopstick[i]); 

wait(chopstick[(i+1)%5]); 

就餐；

signal(chopstick[i]); 

signal(chopstick[(i+1)%5]);

signal(sm) ;

继续思考；

until false;

Chopstick[0..4]=1;sm=4

读者进程i：

REPAET 

wait(rmutex); 

if readcout=0 wait(wmutex);

     Readcount++; 

signal(rmutex);

 访问数据文件；

wait(rmutex);

 Readcount--;

If readcout=0 wait(wmutex);

signal(rmutex);

until false;

写者进程i：

    REPAET

    wait(wmutex);  

    修改文件；  

    signal(wmutex); 

    until false;

司机与售票员的合作问题

VAR S1=1;S2=0;

司机：

Wait(s1);

启动车辆；

正常行车；

到站停车

Signal(s2);

售票员：

Wait(s2);

开车门；

上下乘客；

关车门

Signal(s1);

售票

读者进程i:    

Var  s=100;mutex=1;

Wait(s);

Wait(mutex);

查登记表，并置某座位为占用态

Signal(mutex);

在座位上坐下阅读；

Wait(mutex);

查登记表，并置某座为空闲状态

Signal(mutex);

Signal(s);

接收原语

Procedure receive(b)

Begin

J=internal name;

Wait(j.sm);

Wait(j.mutex);

Remove(j.mq,i);

Signal(j.mutex);

b.sender=i.sizer;

b.size=i.size;

b.text=i.size;

End;

进程通信的类型：共享存储器系统；消息传递系统；管道通信

管道通信：用于连接一个读进程和一个写进程以实现他们通信的一个共享文件，又名Pipe文件，本身提供了互斥和同步进程的能力。

next:指向下一个消息缓冲区的指针

线程的属性：轻型实体；独立调度和分派的基本单位；可并发执行；共享进程资源

作业的状态 “进入” 或“提交”   “后备”“运行” “完成”

决定作业调度的两个因素：

多道程序度；调度算法

周转时间：完成时间-到达时间

带权周转时间：周转时间/执行时间

先来先服务 (FCFS)

短作业（进程）优先SJ(P)F

高响应比优先调度算法HRRN：响应比R = （1+T-到达时间）/服务时间

时间片轮转法RR

准则：面向用户的准则（周转时间短；反应时间快；截止时间的保证；优先权准则

）；面向系统的准则（系统吞吐量高；处理机利用率好；各类资源的平衡利用）

程序的装入：绝对装入方式；可重定位装入方式；动态运行时装入方式。

程序的链接：1、静态链接：程序运行前先链接，再装入内存：1）对相对地址的改变2）变换外部调用符号

2、装入时动态链接：装入内存时，边装入边链接。

3、运行时动态链接：某些模块的链接推迟到执行时才执行，用不到的模块可以不调入内存。

产生死锁的原因竞争资源：可剥夺和非剥夺性资源/临时性资源；进程间推进顺序非法。

死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，它们都将无法再向前推进。

处理死锁的基本方法：预防死锁；避免死锁；检测死锁；解除死锁

产生死锁的必要条件互斥条件：资源本身的特性；请求和保持条件：在请求不到新资源的时候进程不释放原来的资源 ；不剥夺条件：进程获得的资源，为使用完前不可被剥夺 ；环路等待条件：进程对资源的请求形成一个请求环形链

预防死锁

1、打破请求和保持条件：要求进程一次性申请到全部资源后再运行，不会产生死锁，但效率降低

2、打破不剥夺条件：要求进程提出新资源要求不被满足后，必须释放原来的保持的资源，损失代价严重；

3、打破环路等待条件：对资源进行线性排序编号，要求每个进程必须从低号到高号申请资源，而不考虑进程实际申请资源的先后顺序。

死锁的解除剥夺资源；撤消进程

拼接或紧凑：通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法。

虚拟存储器的特征：多次性；对换性；虚拟性

银行家算法：主要用来判断在当前状态下如果有进程提出资源请求request[]，看是否能满足该请求：

a： 判断请求的合法性，是否满足小于NEED矩阵中的向量；

b：请求的可满足性判断，是否小于available[]向量；

c：试探分配，修改相应的参数               available[]\allocation\need;

d：进行安全性检查，若分配后安全，则进行分配，若判断从此进入了不安全状态，则恢复原来数据，对进程请求不予满足。

安全性算法检查：

（1）设定两个向量work=available;finish[i]=true（2）从进程集合中找到一个能满足下述条件的进程：finish[i]=false;need[i][j] ≤work[j];若找到，执行步骤3，否则执行步骤4

（3）当进程pi获得资源后，可顺利执行，直到执行，并释放出分配给它的资源

work[j]= work[j]+allocation[i][j]; finish[i]=true; 

Go to  step2

(4) 如果所有进程finish[i]=true都满足，则系统处于安全状态，否则处于不安全状态。

Work need、allocation work+allocation

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定的。

动态分区分配算法：首次适应算法：按地址递增的顺序；循环首次适应算法：从上次找到的空闲分区的下一个开始；最佳适应算法：按大小递增的顺序；最坏适应算法：按地址递减的顺序

地址为A，页面大小L页号P，页内地址d：

p=int(A/L)

d=AmodL     

分段系统的基本原理：   分段：将作业的逻辑地址空间分为若干个段，每个段内定义一组逻辑信息。作业的地址空间分为段号（名）+段内地址两部分。

段表：将不同的段分配到内存不连续的存储空间，当然，具体每个段，因为长度可能不同，但是需连续的存储空间，因此，段表内需确定段号、段的长度、段在内存的起始地址。

分页与分段区别：（1）页是信息的物理单位，为了提高内存利用率引入的；段是信息的逻辑单位，是考虑用户编程需要分成的段。（2）页的大小固定，段的大小不确定（3）页的逻辑地址是1维的，段的逻辑地址是2维的。

段页式存储管理方式

基本原理：首先用户程序分成若干个段，每个段内再实施分页，为每个段赋予一个段名。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分组成。

页号、物理块号、状态位p、访问字段A、修改位M、外存地址

页表机制：页号和物理块号，状态位P（0表示在外存，没有调入，1表示在内存）；访问字段A（一段时间内访问次数或是否被访问过，供页面置换出去时参考）；修改位M（一段时间内是否被修改过，置换时需要回写到外存对换区）；外存地址（将来调入内存时使用）；

物理块的分配策略

（1）固定分配局部置换

（2）可变分配全局置换

（3）可变分配局部置换

物理块分配算法

（1）平均分配算法

（2）按比例分配算法（3）考虑优先权的分配算法

最佳置换算法（Optimal）

先进先出置换算法（FIFO）

最近最久未使用（LRU）

Clock置换算法

设备控制器是在CPU和I/O设备之间的接口，一个设备控制器控制几个设备。

设备控制器的功能接收和识别命令；数据交换；标识和报告设备的状态；地址识别；数据缓冲；差错控制

通道是通过执行通道程序，并与设备控制器共同实现对I/O设备的控制的。通道程序是由一系列通道指令所构成的。

通道程序每条指令： （1）操作码（2）内存地址（3）计数（4）通道程序结束位（5）记录结束标志。

设备分配中的数据结构

1、设备控制表DCT

2、控制器控制表COCT、通道控制表CHCT

3、系统设备表

联机命令的类型

系统访问类（login）；磁盘操作类format、diskcopy；文件操作类type；目录操作类mkdir；其它命令

spooling 系统组成

（1）输入井和输出井

（2）输入缓冲区和输出缓冲区（3）输入进程spi和输出进程spo

SPOOLING 系统的特点

提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能

设备处理程序通常又称为设备驱动程序。是I/O进程与设备控制器之间的通信程序，以进程的形式存在，故称为设备驱动进程。

连续分配的优缺点：

（1）顺序访问容易（2）顺序访问速度快（3）要求有连续的存储空间（4）必须事先知道文件的长度。

显示链接是把链接文件个物理块的指针显式的存放在内存的一张链接表中，整个磁盘仅设置一张

混合索引分配方式：UNIX系统V的索引结点中：

直接寻址iaddr(0)-iaddr(9)；

一次间接寻址iaddr(10)；

多次间接寻址iaddr(11) iaddr(12)

对目录管理的要求如下：

（1）实现“按名存取”

（2）提高对目录的检索速度

（3）文件共享

（4）允许文件重名

文件与文件控制块一一对应，人们把文件控制块的有序集合称为文件目录

多级目录结构

（1）提高了检索目录的速度（2）在不同的用户目录中，可以使用相同的文件名

（3）不同用户还可以使用不同的文件名来访问同一个共享文件。

输入下列命令：cp   file1   file2时，将文件file1拷贝成file2

#include<stdio.h>

#include <fcntl.h>

#include <sys/types.h>

#include<sys/stat.h>

int main(int argc,char *argv[])

{char buf[88];

int j,n,m;

int fd,fd1;

fd=open(argv[1],O_RDWR);

if(fd<0) printf("open %s failed",argv[1]);

else j=creat(argv[2],S_IWRITE | S_IREAD);

if(j<0)  printf("creat %s failed",argv[2]);

else n=read(fd,buf,sizeof(buf));

if(n<0) printf("read %s failed",argv[1]);

else close(fd);

fd1=open(argv[2],O_RDWR);

if(fd1<0) printf("open %s failed",argv[2]);

else

m=write(fd1,buf,n);

if(m<0) printf("write %s failed",argv[2]);

else

close（fd1）；

}

利用无名管道（用pipe()创建）实现进程间的通信。父进程创建两个子进程，两个子进程分别向管道中写一条消息：

         “I am  child1.”    和    “I  am child2.”

#include<stdio.h>

#include<unistd.h>

int main()

{int j,k,m;

int fd[2];

char line[40];

pipe(fd);

if(j=fork()==0)

{lockf(fd[1],1,0);

write(fd[1],"i am chlid1\n",13);

lockf(fd[1],0,0);

}

else {if((k=fork())==0)

{lockf(fd[1],1,0);

write(fd[1],"I am chlid2\n",13);

}

else

{lockf(fd[0],1,0);

m=read(fd[0],line,26);

write(STDOUT_FILENO,line,m);

}

}

}

系统调用的类型

（1）进程控制类

（2）文件操纵类

（3）进程通信类

对对象操纵和管理的软件集合是文件管理系统的核心部分。

Hash函数，可将记录键值转换为相应记录的地址。

盘块的分配：

（1）顺序扫描位示图，找出值为0的二进制位进行分配。（2）将所找到的每一个位，转换为相应的盘块号b=n(i-1)+j（n为每行位数）  (3)修改位示图，令map[i,j]=1

盘块的回收:

1、  将回收的盘块号转换为行号和列号

i=(b-1)/n+1   j=(b-1)%n+1 

2、修改位示图。令map[i,j]=0

系统调用在本质上是应用程序请求操作系统内核完成某功能时的一种过程调用，属于特殊的过程调用

系统调用的类型

（1）进程控制类

（2）文件操纵类

（3）进程通信类

父进程创建一个子进程，父进程等待子进程，子进程执行完后自我终止，并唤醒父进程，父、子进程执行时打印有关信息。

#include<sys/types.h>

#include<unistd.h>

int main()
{
    

int childpid = 0;

int retpid = 0;
    

intstatus=0;

     childpid=fork();
        if(childpid < 0)
       {
           printf("fail\n");
       }
       else if(childpid == 0)
       {printf("son\n");   }
       else
      

{
               printf("father");

             retpid = waitpid(childpid,&status,0);

if(retpid == childpid)
     {
                            printf("son finished, ready to start father...\n");
 }
 

 }

  

 return 0;
}

父进程创建一个子进程，在子进程运行时显示当前目录下的所有文件和目录，父进程输出子进程和自己进程的ID。在程序运行时控制进程的顺序；子进程先执行，父进程后执行。

#include <stdio.h>

main ()

{

 int i;

i=fork()

 if((i==-1)

    printf("create child process failed");

 else if (i==0)       

    { sleep(3);        

      execl("/bin/ls","ls",0,0); 

      exit(0);      

     }

 else {wait(0);          

      printf("parent process is %d, child process is %d \n",getpid(),i);

     }

}

实现父进程创建子进程，每个进程都在屏幕上显示自己的ID号。观察记录ID显示的顺序并分析原因。

#include<stdio.h>

#include<unistd.h>

 main()

{ int i,j;

 if (i=fork()==0)

   printf("child1's pid is %d",getpid());

 else if (j=fork()==0) 

   printf("child2's pid is %d",getpid());

      else printf("parent 's pid is %d",getpid());

}