操作系统基本原理

一、进程（PCB）

1、进程的基本状态

2、前驱图

3、进程的同步与互斥

4、信号量机制

5、PV操作

6、死锁问题

7、银行家算法

二、存储管理

1、分区存储组织

2、分页存储管理方式

3、分段存储管理方式

4、段页式存储管理方式

5、快表

6、页面置换算法

三、文件管理

1、索引文件结构

2、文件和树型目录结构

3、空闲存储空间的管理

四、设备管理

1、数据传输控制方式

2、虚设备和SPOOLING技术

3、微内核操作系统

操作系统基本原理

一、进程（PCB）

1、进程的基本状态

就绪状态：是指进程已经获得了除CPU以外的所有必要资源，只要再获得CPU就可以开始运行；就绪队列；

执行状态：是指处于就绪状态的进程获得了CPU开始执行进入到执行状态；

阻塞状态：是指进程在执行过程中因某事的发生而无法继续执行下去，从而执行受阻。比如，进程在执行过程中需要从文件中读取数据进行处理或需要用户输入数据进行处理，当从文件中读取数据没有完成或用户输入数据没有完成时，进程是无法执行的，此时进程将进入阻塞状态从而引发一次进程调度，系统将剥夺当前进程的CPU并从就绪队列中选择一个新的进程将CPU分配给它，让它开始运行；阻塞队列；

创建状态：因所需资源得不到满足，而导致进程创建工作不能完成，此时进程所处的状态。

qian

终止状态：

五种状态转换图：

挂起操作：

具有挂起、激活操作的状态转换图：

2、前驱图

3、进程的同步与互斥

4、信号量机制

5、PV操作

例1：

（1）A（2）C

例2：

（1）C （2）A （3）A

6、死锁问题

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

例：系统有n个进程：A、B、C。这3个进程都需要m个系统资源。如果系统至少有多少个资源，则不可能发生死锁。

总资源：(m-1)*n+1

>死锁的条件

7、银行家算法

例：

答案：B

二、存储管理

1、分区存储组织

>首次适应算法

>最佳适应算法

>最坏适应算法

>循坏首次适应算法

2、分页存储管理方式

>优点：利用率高，碎片小，分配及管理简单；

>缺点：增加了系统开销；可能产生抖动现象；

例：

答案：（1）D（2）B

3、分段存储管理方式

>优点：多道程序共享内存，各段程序修改互不影响；

>缺点：内存利用率低，内存碎片浪费大；

>分页和分段的主要区别

页是信息的物理单位；页的大小固定且由系统决定；分页的用户程序地址空间是一维的；

>分页系统中对程序和数据的共享

在分页系统中，虽然也能实现对程序和数据的共享，但远不如分段系统来得方便

4、段页式存储管理方式

>优点：空间浪费小、存储共享容易、存储保护容易、能动态链接；

>缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

5、快表

块表是一块小容量的相联存储器，由高速缓存器组成，速度快地，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

6、页面置换算法

>最佳置换算法

>随机算法

随机淘汰一个页面；

>先进先出页面置换算法（FIFO）

有可能产生“抖动”。

>最近最久未使用页面置换算法/最近最少使用（LRU）

不会产生“抖动”；

例1：

例2：

答案：（1）B（2）C

三、文件管理

1、索引文件结构

例：

答案：（1）C（2）D

2、文件和树型目录结构

3、空闲存储空间的管理

>空闲区表法

操作系统为磁盘外存上所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数等信息。

空闲表法适用于连续文件结构，其分配的方式是，在系统为某个文件分配空闲块时，首先扫描空闲表项，如找到合适的空闲区项，则分配给申请者，并把该项从空闲表中去掉。如果一个空闲区项不能满足申请者的要求，则把空闲表中的另一项满足要求的分区分配给申请者（连续文件结构除外）。如果一个空闲表项所含块数超过申请者要求，则为申请者分配了所要的物理块后，再修改该表项。

>空闲链表法

将所有空闲盘区拉成一条空闲链，根据空闲链所有的基本元素不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链。

空闲盘块链是将磁盘上的所有空闲分区，以盘块为单位拉成一条链，当用户创建文件请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户；当用户删除文件时，系统将回收的盘块依次加入到空闲盘块链的末尾。

空闲盘区链是将磁盘上的所有空闲盘区（每个空闲盘区可包含若干个盘块）拉成一条链。在管理的线性表中，每一个表项对应一个空闲区，增加一项存放指向空闲块的指针，将磁盘上的所有空闲区（可包含若干个空闲块）拉成一条链。每个空闲区上除含有用于指示下一个空闲区的指针外，还有本盘区大小（盘块数）的信息。

>位示图法

例：

答案：（1）D（2）B

>成组链接法

空闲表法和空闲链表由于空闲表太长而不适合大型文件系统的使用。成组链接法是两种方法相结合的一种管理方法，兼备了两种方法的优点而克服了两种方法的缺点。其大致的思想是：把空闲的n个空闲扇区的地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，以此类推，直至所有空闲扇区都予以链接。

四、设备管理

1、数据传输控制方式

>程序控制方式

优点：工作过程简单，不需要更多的硬件支持

缺点：（1）CPU和外围设备只能串行工作；

（2）CPU在一段时间内只能和一台外围设备交换数据信息，不能实现设备之间并行工作；

（3）程序直接控制方式只适用于那些CPU执行速度较慢，而且外围设备较少的系统；

>程序中断方式

在I/O中断方式下，数据的输入按如下步骤操作：

　　（1）需要数据的进程通过CPU发出启动外设输入数据的指令，该指令同时置状态寄存器的中断允许位。

　　（2）在进程发出指令启动设备之后，该进程放弃处理机，等待输入完成。这时，进程调度程序可以调度其他就绪进程占据处理机。

　　（3）当输入工作完成时，I/O控制器通过中断请求线向CPU发出中断信号。CPU在接收到中断信号之后，转去执行设备中断处理程序。设备中断处理程序把输入数据寄存器中的数据传送到相应的进程使用。同时把等待输入完成的那个进程唤醒，再返回到被中断的进程继续执行。

　　（4）在以后的某个时刻，进程调度程序选中提出请求输入的进程，该进程从指定的内存单元中取出数据做进一步处理。

　　　　优点：与程序直接控制方式相比，中断方式使CPU的利用率大幅度提高了。

　　　　缺点：设备每输入/输出一个数据都要求中断CPU，这样在一次数据传送过程，中断发生次数较多，耗去大量CPU处理时间。

>DMA方式

　DMA方式的数据输入过程如下：

　　（1）当进程要求设备输入一批数据时，CPU将准备存放输入数据的内存起始地址以及要传送的字节数分别送入DMA控制器中的内存地址寄存器和传送字节计数器，准备开始进行数据输入并且允许中断

　　（2）发出数据要求的进程进入等待状态，进程调度程序调度其它进程占据CPU

　（3）输入设备不断的挪用CPU工作周期，将数据寄存器中的数据源源不断的写入内存，直到所要求的字节全部传送完毕

　　（4）DMA控制器在完成数据传送后通过中断请求线发出中断信号，CPU收到中断信号后转到中断处理程序，唤醒等待输入完成的进程，并返回被中断程序

　　（5）中断处理结束后，CPU返回被中断的进程或去运行重新被调度的进程。

　　DMA方式与中断方式的主要区别：

　　1、前者在全部数据传送结束时才中断CPU，后者每传送一个数据中断一次CPU

　　2、中断方式的数据传送在中断处理时由CPU控制完成，而DMA方式则是在DMA控制器的控制下完成

>通道

　通道是专门用来输入和输出的处理机，它控制内存和设备直接进行数据交换

　　按信息交换方式，可以把通道分为：（1）字节多路通道（2）选择通道（3）数组多路通道

　　通道指令一般包含有数据在内存中的地址、传送方向、数据块长度以及I/O设备的地址信息、特征信息（是磁带还是磁盘设备）等

　　通道控制方式的数据输入过程如下：

　　（1）当进程要求输入数据时，CPU发出启动指令指明I/O操作、设备号和对应通道

　　（2）对应通道接收到CPU发来的启动指令之后，把通道指令程序读出，并执行通道程序

　　（3）如果数据传送结束，就向CPU发出中断请求。CPU收到中断信号后转向中断处理程序，唤醒等待输入完成的进程，并返回被中断程序

　　（4）在以后的某个时刻，进程调度程序选中提出请求输入的进程，该进程从指定的内存起始地址取出数据，做进一步处理。

>输入输出处理机

输入输出处理机（IOP）：通道是一个具有特殊功能的处理器，又称为输入/输出处理机，它分担了CPU的一部分功能，可以实现对外围设备的同一管理，完成外围设备与主存之间的数据传送。

2、虚设备和SPOOLING技术

SPOOLING技术：

SPOOLING技术:慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。(假脱机技术是通过软件的方式模拟脱机技术)
①提高了I/O速度,缓和了CPU与低速I/O设备速度不匹配的矛盾.
②实现了虚拟设备功能.多个进程同时使用一独享设备(实质是分时复用),而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备.

SPOOLING组成:

(1) 输入井和输出井。这是在磁盘上开辟出来的两个存储区域。输入井模拟脱机输入时的磁盘，用于收容I/O设备输入的数据。输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据。输入/输出井中的数据一般以文件的形式组织管理，我们把这些文件称为井文件。一个文件仅存放某一个京城的输入（或者输出）数据，所有进程的数据输入（或输出）文件链接称为一个输入（或输出）队列。

(2)输入缓冲区和输出缓冲区。这是在内存中开辟的两个缓冲区，用于缓和CPU和磁盘之间速度不匹配的矛盾。输入缓冲区用于暂存由输入设备传送的数据，之后再传送到输入井。输出缓冲区用于暂存从输出井传送的数据，之后再传送到输出设备。

(3)输入进程和输出进程。输入进程也称为预输入进程，用于模拟脱机输入时的外围控制机，将用户要求的数据从输入设备传送到输入缓冲区，再存放到输入井。当CPU需要输入设备时，直接从输入井读入内存。输出进程也称为缓输出进程，用于模拟脱机输出时的外围控制机，把用户要求输入的数据从内存传送并存放到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区输出至输出设备上。

(4)井管理程序。用于控制作业与磁盘井之间信息的交换。当作业执行过程中向某台设备发出启动输入或输出操作请求时，由操作系统调用井管理程序，由其控制从输入井读取信息或将信息输出至输出井。

输入输出缓冲区都在内存中，输入井和输出井是磁盘中的存储区。