操作系统知识点介绍.doc

操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
虚拟机：在裸机的基础上，每增加一层新的操作系统的软件，就变成了功能更为强大的虚拟机或虚机器。
操作系统的目标：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
#include
#include
#include
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],ORDWR);
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）；
}
18

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

#include
#include>
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

#include

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
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
#include
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());
}