操作系统概述

作用：
（1）通过资源管理，提高计算机系统的效率；（系统软件）
（2）改善人机界面，向用户提供友好的工作环境。（人机交互）
分类：
（1）批处理操作系统：把一系列指令写成一个批作业，计算机在执行这个批作业的时候不需要人工一条一条的输入，然后提交给计算机，计算机会按照指令依次执行可以减少人工的操作，提高计算机运行的效率。
（2）分时操作系统：CPU分成很多个时间碎片，每个碎片分给不同的作业，使得每个作业宏观上都在运行。
（3）实时操作系统：在可以接受的范围内，提交作业可以产生结果，系统是足够快的
（4） 络操作系统：提供 络相关的功能
（5）分布式操作系统： 络操作系统更高层次的一个形态，有更高的可靠性、可扩展性。将 络中物理区域不在同一个的计算机组合在一起形成 络系统，通过分布式系统进行 络资源的分布和调用。
（6）微机操作系统
（7）嵌入式操作系统：体系较小

进程管理及PV

进程的概念及三态模型

进程：是程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。它由程序块 、进程控制块（PCB）和数据块三部分组成。
（运行结束以后进程就消失了）

进程与程序的区别：

程序是静态的，进程是动态的，程序是存储在某种介质上的二进制代码，进程对应了程序的执行过程，系统不需要为一个不执行的程序创建进程，一旦进程被创建，就处于不断变化的动态过程中，对应了一个不断变化的上下文环境。

程序是永久的，进程是暂时存在的。程序的永久性是相对于进程而言的，只要不去删除它，它可以永久的存储在介质当中。

三态模型：

运行态：进程处于运行态，当前进程已经获取到了CPU资源，正在利用CPU进行运算

就绪态：进程处于就绪态，当前进程已经准备好了运行的所有资源，等待CPU的调度

阻塞态：进程处于阻塞态，当前进程没有准备好运行的资源

V操作：释放资源的操作，使信 量的值加1，加1后小于等于0，说明当前S资源的队列中有进程在排队，系统就会在等待队列中唤醒一个进程执行

PV必须成对出现

例：
1、互斥模型

多个V进程共享一台打印机的问题：
P（S）；
使用打印机；
V（S）；
后续代码；

互斥信 量S的初值为1。

2、同步模型

单个缓冲区生产者、消费者问题：
生产者–>市场–>消费者

例：(互斥)
银行办理业务，开放两个窗口，有四个人（P1、P2、P3、P4）办理业务
对于四个进程P来说，有两个可用资源，属于互斥资源，信 量S初始值S=2（对于互斥类资源，资源数=信 量值）

死锁

死锁问题

进程管理是操作系统的核心，但如果设计不当，就会出现死锁问题。如果一个进程再等待一个不可能发生的事情，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

答：
（1）

（4）
在(3)中，work已更新为(0 3 2)
P1:Request(0,2,0) < work(0 3 2)，
先假设分配给P1，看分配后能否得到一个安全状态，更新资源分配表：

一、首次适应算法（First Fit）：该算法从空闲分区链首开始查找，直至找到第一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。

三、最坏适应算法（Worst Fit）:最坏适应算法是将输入的作业放置到主存中与它所需大小差距最大的空闲区中。空闲区大小由大到小排序。

1、一个进程对应一张页表
2、进程的每一页对应一个页表项
3、每个页表项由页 和块 组成
4、页表记录进程页面和世界存放的内存块之间的对应关系
5、每个页表项的长度是相同的，页 是隐含的

优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销；可能产生抖动现象

段式存储

四种磁盘调度算法
1、先来先服务算法（FCFS）First Come First Service

它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。

2、最短寻道时间优先算法（SSTF） Shortest Seek Time First

该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。

3、扫描算法（SCAN）电梯调度

扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

4、循环扫描算法（CSCAN）

循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道 紧接着最大磁道 构成循环，进行扫描。

磁盘读数据的时间
（找道时间）+（找扇区时间）+（传输时间）
注：磁盘是不停的旋转的

位示图
是利用二进制的一位来表示磁盘中的一个盘块的使用情况，其值为0时，表示对应的盘块空闲；为1时。表示已分配
先判断块的标 从开始还是从1开始。

文件系统

树形目录结构