赞
踩
操作系统基本原理包含以下 5 大管理。
我们先来说说进程管理。
因为处理机是计算机系统的核心资源,所以整个操作系统的重心是处理机管理。
处理机管理中最基本的、最重要的概念是进程。进程是系统并发执行的体现。
不同观点 | 操作系统 |
---|---|
静态 | 是一组程序和表格集合的操作系统。 |
动态 | 是进程动态和并发执行的操作系统。 |
不同观点 | 进程 |
---|---|
静态 | 进程是由程序 、 数据和进程控制块 ( ProcessControlBlock , PCB ) 组成的。 |
动态 | 进程是计算机状态的一个有序集合。 |
进程控制块 PCB 是进程存在的唯一标志, PCB 描述了进程的基本情况,具体内容可分为调度信息和执行信息两大部分。调度信息供进程调度使用,包括进程当前的一些基本属性 ; 执行信息即现场,描述了进程的执行情况 。 PCB 随着进程的建立而产生,随着进程的完成而消亡。
顺序程序是指程序中若干操作必须按照某种先后次序来执行,并且每次操作前后的数据、状态之间都有一定的关系。早期的程序设计一般都是按顺序执行的。
多道程序系统,有以下特点:
程序的并行执行和资源共享之间是相辅相成的:
实际情况是:大多数程序段要求操作在时间上是有序的,也就是说有些操作必须在其他操作之前,但其中有些操作却可以同时进行,这时就可以采用并发操作。
由于进程运行的间断性,决定了进程至少具有以下三种状态:
进程的状态会随着自身的推进或外界条件的变化而变化。
状态变化 | 示例条件 |
---|---|
运行态→阻塞态 | 运行中启动了外围设备; 运行中申请资源(主存储空间及外围设备得不到满足);运行中出现了故障(程序出错或主存储器读写错误等) |
阻塞态→就绪态 | 外围设备工作结束;等待的资源能得到满足; |
运行态→就绪态 | 进程用完了一个使用处理器的时间后;有更高优先权的进程要运行时;由于自身或外界原因成为等待状态的进程让出处理器时; |
就绪态→运行态 | 系统按一种选定的策略从处于就绪状态的进程中选择一个进程。 |
注意: 任何一个结束阻塞的进程必须先变成就绪状态,待分配到处理器后才能运行。
引入挂起状态的原因:
挂起状态有以下这些特性:
新的模型是把三态模型中的等待态改名为活跃阻塞态,就绪态改名为活跃就绪态,然后新增了与挂起相关的两种状态(静止就绪态和静止阻塞态)。
进程互斥指的是:一组并发进程中一个或多个程序段,因共享某一共有资源而导致必须以互斥的方式访问。也就是说,互斥指的是要保证临界资源在某一时刻只被一个进程访问。互斥即资源竞争关系。
进程同步指的是:各进程异步执行,但必须按一定的制约顺序和速度执行。同步是进程间协作关系。
临界资源指的是:一次仅允许一个进程使用的资源。比如,物理设备如打印机、磁带机等,某些软件的变量、数据、表格等。
临界区指的是:一个进程访问临界资源的那段程序代码。
进程互斥加入临界区概念之后,可以这样描述:禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。因此必须有专门的同步机制来协调它们。
协调准则如下:
在操作系统中,信号量是一个整数。当信号量大于等于 0 时,代表可供并发进程使用的资源实体数;当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建的信号量所代表的意义和设置初始值,以及建立相应的数据结构,以便指向那些等待使用该临界区的进程。
信号量操作: P 操作和 V 操作。它们都是不可分割的原子操作,也称为原语。原语操作指的是,在执行期间不允许发生中断。
P(sem) 操作会将信号量 sem 值减 1,如果操作前 sem 值为负数,那么调用 P 操作的进程将暂停执行,直到另一个进程对同一信号量做 V 操作。 V(sem) 操作会是将信号量 sem 值加 1,若 sem 的值<=0,操作系统会从与 sem 有关的队列中选一个进程,唤醒它。
总结如下:
P 是减 1,消耗资源;V 是加 1,释放资源。
P(sem) 操作定义:
P(sem) {
sem = sem - 1;
if ( sem < 0 )
进程进入等待状态;
else
继续进行;
}
V(sem) 操作定义:
V(sem) {
sem = sem + 1;
if( sem ≤ 0)
唤醒队列中的一个等待进程;
else
继续进行;
}
利用 P、 V 原语和信号量可以方便地解决并发进程在临界区的互斥问题。
假设信号量 mutex 是用于互斥的信号量,初值为 1,表示没有并发进程使用该临界区。
于是各并发进程的临界区可改写成下列形式的代码段:
P(信号量 S);
临界区
V(信号量 S);
要用 P, V 操作实现进程同步,需要引入私有信号量。注意:私有信号量只与制约进程和被制约进程有关,而不是与整组并发进程。与此相对,进程互斥使用的信号量为公用信号量。
首先为各并发进程设置私用信号量,然后为私有信号量赋初值,最后利用 P, V 原语和私用信号量定义各进程的执行顺序。
最简单的同步控制是进程 A 在另一个进程 B 到达 L2 以前,不应前进到超过点 L1。
要确保进程 B 执行 V 操作之前,不让进程 A 的运行超过 L1 ,就要设置信号量 S 的初值为 0 。 这样,如果进程 A 先执行到 L1 ,那么执行 P 操作 ( S = S - 1 ) 后,则 S < 0 ,就停止执行,让其进入阻塞状态。直到进程 B 执行到 L2 时,再执行 V 操作 ( S = S +1 ) ,唤醒进程 A 让其继续执行 。
“生产者-消费者” 是经典的同步问题。要求存后再取,取后再存,即存在两个制约关系(缓存区如果满了,就停止生产;而缓存区如果空了,则停止消费)。
生产者 - 消费者问题不仅要解决生产者进程与消费者进程的同步关系,还要处理缓冲区的互斥关系,因此需要 3 个信号量来实现:
信号量 | 类别 | 说明 |
---|---|---|
empty | 同步 | 空闲的缓冲区数量。程序刚开始时,缓冲区全部为空。所以,其初始值应为缓冲区的总个数。 |
full | 同步 | 已填充的缓冲区数量。程序刚开始时,所有缓冲区都为空 ,所以,其初始值为 0。 |
mutex | 互斥 | 确保同时只有一个进程正在写缓冲区,因此,其初始值为1。 |
如果对缓冲区的读写无须进行互斥控制的话,那么就不需要 mutex 的互斥信号量了。
假设我们只对生产者与消费者进行同步控制,那么程序如下。
生产者程序 :
loop
生产一个物品;
P(empty); //空闲的缓冲区数量 - 1
物品存入缓冲区;
V(full);//填充的缓冲区数量 + 1
endloop
消费者程序 :
loop
P(full);//填充的缓冲区数量 - 1
从缓冲区中取出物品;
V(empty);//空闲的缓冲区数量 +1
使用它;
endloop
假设,在某并发系统中,有一个发送进程 A 、 一个接收进程 B 、 一个环形缓冲区 BUFFER 、 信号量 S1 和 S2。 发送进程不断地产生消息并写入缓冲区 BUFFER ,接收进程不断地从缓冲区 BUFFER 中取消息。假设发送进程和接收进程可以并发地执行,那么,当缓冲区的容量为 N 时,如何使用 PV 操作才能保证系统能够正常工作。发送进程 A 和接收进程 B 的工作流程如图 8 所示。请在图 8 中的 ①~④ 处填写正确的操作。
显然,这是一个 “ 生产者 - 消费者 ” 问题,这个问题通常需要 3 个信号量来实现 : 两个用来管理缓冲区同步,信号量 empy 表示空闲缓冲区数量,初值为缓冲区最大数 N ,信号量 full 表示已填充缓冲区数量,初值为 0; 第三个信号量用于管理互斥,由信号量 mutex 保证只有一个进程在写缓冲区,初值为 1。 但在本系统中,进程 A 和进程 B 允许并发地访问缓冲区,因此无须管理互斥,因此只需定义两个信号量 : S 1和 S2 ,初值为 N 的 S1 在此承担的是信号量 empty 的功能,初值为 0 的 S2 则承担了信号量 full 的功能。
在这套并发系统的基础上,如果系统中有多个发送进程和接收进程,进程间的工作流程如图 10 所示。发送进程产生消息并顺序地写入环形缓冲区 BUFFER,接收者进程顺序地从 BUFFER中取消息,且每条消息只能读取一次为了保证进程间的正确通信,增加了信息量 SA 和 SB 。请说明信息量 SA 和 SB 的物理意义,并把信息量 SA 和 SB 正确应用到流程中。
这里的关键点是系统中允许有多个发送进程和接收进程,推断系统需要完成的控制是: 发送进程顺序写入,接收进程顺序读取,而且每条消息都只能够读取一次。这显然是两个互斥的问题,即多个发送进程在写缓冲区时是互斥关系,多个接收进程读缓冲区也是互斥关系。因此,信号量 SA 和 SB 用于分别实现这两个互斥控制。
前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺
序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程,结点间的有
向边表示两个结点之间存在的前趋关系。
比例:在计算机中,经常采用流水线方式执行指令,每一条指令都可以分解为取指(取出指令)、分析和执行三步。取指操作为 Ai,分析操作为 Bi 和执行操作为 Ci(i=1,2,3)。图 6 所示即为三个任务各程序段并发执行的前驱图。
图中 A1 没有前趋结点,称为开始结点,它不受任何制约,可以直接执行;而 B1 与 A2 只能在 A1 执行完成之后才能开始,而 B2 必须在 B1 与 A2 完成之后才能开始; C3 没有后继结点,称为终止结点。
在前趋图中,执行先后顺序的制约关系可分为两种:
以下是 PV 操作与前趋图结合的示例。假设进程 P1、P2、P3、P4 和 P5 的前趋图如图 7 所示:
若用 PV 操作控制进程 P1~P5 并发执行的过程,则需要设置5个信号量 S1、S2、S3、S4 和 S5 ,进程间同步所使用的信号量标注在图 7 中的边上,且信号量 S1~S5 的初值都等于零,初始状态下进程 P1 开始执行。则该如何设置信号量来控制这些进程?
根据前趋图,得知进程之间的约束关系为:
这里的信号量用于进程同步。前趋图的进行信号量使用规则如下:
进程调度即处理器调度(又称上下文转换),它的主要功能是确定在什么时候分配处理器,并确定分给哪一个进程,即让正在执行的进程改变状态转入就绪队列的队尾,再由调度原语取出就绪队列的队首进程,并执行它。
引起进程调度的原因有以下几类:
对于不同的系统与目标,会采取不同的进程调度算法:
在进程管理的实现中,如果设计不当,就会出现死锁。
当若干个进程互相争用对方已占有的资源,导致无限期地等待,不能向前推进的情况,就会造成“死锁”。例如, P1 进程占有资源 R1, P2 进程占有资源 R2,这时, P1 又需要资源 R2, P2 也需要资源 R1,它们在互相等待对方占有的资源时,又无法释放自己占有的资源,从而使双方都进入了无限等待状态。
归纳来说,就是多个进程之间互相等待对方的资源,而在得到对方资源之前又不释放自己的资源,这样,就会造成循环等待,这就是死锁。如果一个进程在等待一个永远不可能发生的事件,就会造成死锁。
死锁是系统的一种出错状态,它不仅会浪费大量的系统资源,甚至还会导致整个系统的崩溃,所以死锁是应该尽量预防和避免的。
产生死锁的主要原因是共享资源不足,资源分配策略和进程的推进顺序不当造成的。系统资源既可能是可重复使用的永久性资源,也可能是消耗性的临时资源。
产生死锁的必要条件是:互斥条件、保持和等待条件、不剥夺条件和环路等待条件。
银行家算法指的是,当进程请求资源时,系统将按照如下原则分配资源 :
假设系统中有三类互斥资源 R1、R2 和 R3 ,可用资源数分别是 9、8 和 5。 在 T0 时刻系统中有 P1、P2、P3、P4 和 P5 五个进程,这些进程对资源的最大需求量和已分配资源数如表 1 所示。进程按照 P1→P2→P4→P5→P3 序列执行,系统状态安全吗 ? 如果按P2→P4→ P5→P1→P3 的序列呢 ?
从表 1 中可以看出,还有 2 个 R1 (9-1-2-2-1-1=2)未分配,1个 R2 (8-2-1-1-2-1=1)未分配,而 R3 全部分配完毕(5-1-1-3=0)。
按照 P1 → P2 → P4 →P5→P3 的顺序执行时,首先执行 P1 ,这时由于其R1、 R2 和 R3 的资源数都未分配够,因而开始申请资源,得到还未分配的 2 个 R1 ,1个 R2 。但其资源仍不足 ( 因为没有可用的 R3 资源 ) ,从而进入阻塞状态,并且这时所有资源都已经分配完毕。因此,后续的进程都无法得到能够完成任务的资源,全部进入阻塞,这时死锁就发生了。
而如果按照 P2 → P4 →P5→ P1 →P3 的序列执行时:
处于死锁状态的进程不能继续执行但又占用了系统资源,从而阻碍其他作业的执行。因此必须解决死锁。解决死锁的策略为:
实际上,系统出现死锁的概率很小,故从系统所花的代价上来看,采用死锁发生后的检测与解除策略要比采用死锁发生前的预防与避免策略代价要小一些。所以,推荐采用死锁发生后的检测与恢复策略。
管程由管程名 、 局部子管程的变量说明 、 使用共享资源并在数据集上进行操作的若干过程,以及对变量赋初值的语句等4个基本部分组成。
每一个管程管理一个临界资源。当有多个进程调用某管程时,仅允许一个进程进入管程,其他调用者必须等待,也就是申请进程必须互斥地进入管程。方法是通过调用特定的管程入口进入管程,然后通过管程中的一个过程使用临界资源。当某进程通过调用请求访问某临界资源而未能满足时,管程调用相应同步原语使该进程进入等待状态,并将它放入等待队列。当使用临界资源的进程访问完该临界资源并释放之后,管程又调用相应的同步原语唤醒等待队列中的队首进程。为了表示不同的等待原因,设置条件变量,条件变量是与普通变量不同的变量,条件变量不能取任何值,只是一个排队栈。
线程是进程的活动成分,是处理器分配资源的最小单位,它可以共享进程的资源与地址空间,通过线程的活动,进程可以提供多种服务 ( 对服务器进程而言 ) 或实行子任务并行 ( 对用户进程而言 ) 。每个进程创建时只有一个线程(主线程),根据需要在运行过程中创建更多的线程。显然,只有主线程的进程才是传统意义下的进程内核负责线程的调度,线程的优先级可以动态地改变。
采用线程机制的最大优点是节省开销,传统的进程创建子进程的办法内存开销大,而且创建时间也长。
在多线程系统中,一个进程可以由一个或多个线程构成,每一个线程可以独立运行,每个进程的线程共享这个进程的地址空间。有多种方法可以实现多线程系统,一种方法是核心级线程,另一种方法是用户级线程,也可以把两者组合起来。
多线程实现的并行避兔了进程间并行的缺点 : 创建线程的开销比创建进程要小,同一进程的线程共享进程的地址空间,所以线程切换 ( 处理器调度 ) 比进程切换快。例如, WindowsServer 内核采用基于优先级的方案选定线程执行的次序。高优先级的线程会比低优先级的线程先执行,内核周期性地改变线程的优先级,以确保所有线程均能执行。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。