精华内容
下载资源
问答
  • 操作系统中的饿死现象怎样理解?
    千次阅读
    2020-12-23 12:41:59

    什么是进程的饥饿和饿死?

    在一个动态系统中,资源请求与释放是经常性发生的进程行为.对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。 资源分配策略可能是公平的(fair),能保证请求者在有限的时间内获得所需资源;资源分配策略也可能是不公平的(unfair),即不能保证等待时间上界的存在。 在后一种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待.当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿(starvation),当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。

    考虑一台打印机分配的例子,当有多个进程需要打印文件时,系统按照短文件优先的策略排序,该策略具有平均等待时间短的优点,似乎非常合理,但当短文件打印任务源源不断时,长文件的打印任务将被无限期地推迟,导致饥饿以至饿死。

    当等待时间给进程的推进和相应带来明显的影响时,就称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时,称该进程被饿死。

    当一组进程到达时,CPU根据算法进行进程调度。有的进程因此而需要等待,而不能及时得到资源,这就叫饥饿。进程得到资源时,再完成已经不再具有意义,这就叫做饿死。

    Starvation is simply when a process or service is not being serve, even when there is no deadlock on the system.

    This is an example I just made up just for clarification purposes.

    Imagine an algorithm that control computers access to a WAN or something like that. This algorithm could have a policy that says "Provide priority access to those computers that will use less bandwidth.", that will seem like a proper policy, but then what happens when a single computer wants to access the network for an ftp upload that will send several GB somewhere. With this policy alone, that computer will starve since the algorithm will never select that computer, since there will be always other computers requesting smaller bandwidth usage.

    That is called starvation.

    摘自我的CSDN博客 blog.csdn.net/yming0221/article/details/7104508

    更多相关内容
  • 操作系统

    千次阅读 2020-12-23 12:42:57
    如果没有就绪进程,系统会安排一个系统空闲进程或idle进程;系统场景:N个进程就绪、等待上CPU运行;M个CPU,M>=1;需要决策:给哪个进程分配哪个CPUCPU调度要解决的3个问题:what:按什么原则原则下一个要执行的...

    CPU调度:控制、协调进程对CPU的竞争;按一定的调度算法,从就绪序列里选一个进程,把CPU的使用权交给被选中的进程;如果没有就绪进程,系统会安排一个系统空闲进程或idle进程;

    系统场景:N个进程就绪、等待上CPU运行;M个CPU,M>=1;需要决策:给哪个进程分配哪个CPU

    CPU调度要解决的3个问题:what:按什么原则原则下一个要执行的进程,调度算法;when:合适选择,调度时机;how:如何让被选中的进程上CPU运行,调度过程(进程的上下文切换)

    CPU调度时机:事件发生—-当前运行的进程暂停—-硬件机制响应后—-进入操作系统,处理相应的事件—-结束处理后:某些进程的状态会发生变化,也可能又创建了一些新的进程—-就绪队列改变了—-需要进程调度根据预设的调度算法从就绪队列选一个进程。包括下面4个情况:

    进程正常终止 或 由于某种错误终止

    新进程创建 或 一个等待进程变成就绪

    当一个进程从运行态进入等待态

    当一个进程从运行态变为就绪态

    调度过程——进程切换:一个进程让出CPU,另一个进程占用CPU的过程;包括了对原来运行进程各种状态的保存和对新的进程各种状态的恢复。切换时要做的两件事:

    1 切换全局页目录 以 加载一个新的地址空间

    2 切换内核栈和硬件上下文,其中硬件上下文包括了内核执行新进程需要的全部信息,如CPU相关寄存器

    上下文切换具体步骤:进程a下CPU,进程b上CPU

    保存进程a的上下文环境(程序计数器、程序状态字、其他寄存器)

    用新状态和其他相关信息更新进程a的PCB

    把进程a移至合适的队列(就绪、阻塞。。)

    将进程b的状态设置为运行态

    从进程b的PCB中恢复上下文(程序计数器、程序状态字、其他寄存器。。)

    上下文切换开销:直接开销:内核完成切换所用的CPU时间;间接开销:高速缓存cache、缓冲区缓存、TLB失效

    CPU调度算法衡量指标:

    吞吐量:每单位时间完成的进程数目

    周转时间:每个进程从提出请求到运行完成的时间

    响应时间:从提出请求到第一次回应的时间

    其他:CPU利用率,CPU做有效工作的时间比例;等待时间,每个进程在就绪队列中等待的时间

    进程优先级(数):

    优先级,反映紧迫程度;

    优先数,反映优先级,UNIX优先数小的优先级高;

    静态、动态优先级。等待久的动态优先级高

    抢占与非抢占:

    抢占:有高优先级进程就绪时,系统可以强行剥夺优先级低的进程的CPU给高优先级的进程先用

    不可抢占:除非自身放弃CPU,否则一直运行

    I/O密集型和CPU密集型:

    I/O密集型,I/O型,频繁进行I/O,通常会花很多时间等待I/O操作完成;一般的输入输出程序对i/o更友好

    CPU密集型,需要大量的CPU时间进行计算

    时间片

    一个时间段,分配给调度上CPU的进程,允许该进程运行的时间长度

    如何选择时间片:考虑进程切换开销、对响应时间的要求、就绪进程个数、CPU能力、进程的行为

    批处理系统中采用的调度算法:先来先服务、最短作业优先、最短剩余时间优先、最高响应比优先

    算法选择原则:吞吐量、周转时间、CPU利用率、公平服务

    先来先服务FCFS:先进先出,按照进程就绪的先后顺序使用CPU,非抢占

    公平,实现简单,长进程后的短进程需要等很长时间,不利于用户体验

    最短作业优先SJF:具有最短完成时间的进程优先执行,非抢占

    最短剩余时间优先SRTN:就是sjf的抢占式版本,当一个新就绪的进程比当前运行进程具有更短的完成时间时,系统抢占当前进程,选择新就绪的进程执行

    短作业优先调度算法:最短的平均周转时间(前提是所有进程同时可运行时);不公平(源源不断的短任务到来,可能使长的任务长时间得不到运行,产生饥饿现象

    最高响应比优先HRRN:折中权衡,先来先服务和短作业优先的取长补短

    调度时,先计算每个进程的响应比R;之后,总是选择R最高的进程执行

    响应比R=周转时间/处理时间=(处理时间+等待时间)/ 处理时间 = 1+(等待时间/处理时间)

    交互式系统中采用的调度算法:轮转调度、最高优先级调度、多级反馈队列,最短进程优先;追求指标:响应时间、公平平衡;

    时间片轮转调度算法:目标:为短任务改善平均响应时间,解决周期性切换,每个进程分配一个时间片,时钟中断–轮换。

    如何选择合适的时间片:太长–大于典型的交互时间–退化成先来先服务算法,延长短进程的响应时间;太短–小于典型的交互时间–进程切换浪费CPU时间;经验值50ms左右;

    时间片轮转算法优缺点:公平、有利于交互式计算、响应时间快、由于进程切换,时间片轮转算法要花费较高的开销、RR对不同大小的进程是有利的,但是对于大小相同的进程可能就不利了

    虚拟轮转算法:所有I/O型进程,从等待变成就绪时,进入辅助队列,调度算法在选择进程时,首先从辅助队列选择进程,直到辅助队列为空,再去执行就绪队列,改善了时间片轮转算法对I/O型进程的不公

    最高优先级调度算法:

    选择优先级最高的进程投入运行;

    系统进程一般高于用户进程;前台进程一般高于后台进程;操作系统更偏好i/o型进程;

    优先级可以是静态的,也可以是动态变化的:优先数可以决定优先级

    就绪队列可以安札优先级组织

    实现简单;不公平,容易导致优先级低的进程产生饥饿现象

    优先级反转问题:

    基于优先级的抢占式:一个低优先级进程占有一个高优先级进程所需要的资源,使得高优先级进程等待低优先级进程运行;

    影响:系统错误;高优先级进程停滞不前,导致系统性能降低

    解决方案:

    (1)设置优先级上限:凡是进入临界区的进程,给它个高的优先级,便于先执行完,把临界区的控制权还回去,不进临界区的,给个低优先级;

    (2)优先级继承:低的阻碍了高的,他可以继承这个高的优先级,先把任务执行完,把临界区还回去

    (3)使用中断禁止:凡是进入临界区的进程就不再响应中断了,直到他出了临界区才响应中断,就保护了这个进程,让他去执行,直到把临界区还回去

    多级反馈队列调度算法:

    设置多个就绪队列,第一级队列优先级最高

    给不同就绪队列中的进程分配长度不同的时间片,第一级队列时间片最小,级别降低,时间片变长

    第一级队列为空是,在第二级队列调度,以此类推

    每个队列都按照时间片轮转方式进行调度

    当一个新创建进程就绪后,都进入第一级队列

    当进程用完时间片,而放弃CPU,进入下一级就绪队列

    由于阻塞而放弃CPU的进程进入

    各种调度算法对比

    FCFS

    Round Robin

    SJF

    SRTN

    HRRN

    Feedback

    多处理器调度算法设计:

    不仅要决定选择哪个进程执行,还要决定在哪个CPU上执行;

    要考虑进程在多个CPU之间迁移时的开销,应该尽可能使进程总是在同一个CPU上执行,考虑负载均衡问题

    典型操作系统所采用的的调度算法:

    UNIX:动态优先数法

    5.3BSD:多级反馈队列法

    Linux:抢占式调度

    Windows:基于优先级的抢占式多任务调度

    Solaris:综合调度算法

    Linux调度算法的演化过程:

    Linux2.4简单的基于优先级调度

    Linux2.6 O(1)调度算法

    Linux2.6 SD调度器补丁

    Linux2.6 RSDL调度器补丁

    Linux2.6 CFS调度算法(完全公平调度算法)

    Windows的线程调度:

    调度单位是线程(因为Windows系统支持内核级线程)

    采用基于动态优先级的、抢占式调度,结合时间配额的调整

    基本思想:

    就绪线程按照优先级进入不同的就绪队列

    操作系统总是选择优先级最高的就绪线程运行

    同一优先级的各线程按时间片轮转进行调度

    多CPU系统中允许多个线程并行运行

    Windows线程调度:

    引发条线程调度的条件:一个线程的优先级改变了

    一个线程改变了他的亲和处理机集合

    线程正常终止 或 由于某种错误终止

    新线程创建 或 一个等待线程变成就绪

    当一个线程从运行态进入阻塞态

    当一个线程从运行态变成就绪态

    线程优先级:

    windows使用32个线程优先级,分成3类:

    16-31:实时优先级线程,一旦确定就不改变优先级了

    1-15:可变优先级:可以在一定范围内提升或降低,分为基本优先级、当前优先级

    0:零页线程:用于对系统中空闲物理页面清零

    时间配额:多给点时间配额,就像是给某个进程多点时间运行

    Windows线程调度策略:

    主动切换

    抢占:当线程被抢占时,它被放回相应优先级的就绪队列的队首;处于实时优先级的线程被抢占时,时间配额被重置为一个完整的时间配额,再次上CPU运行的时候运行的是一个完整的时间配额;处于可变优先级的线程在被抢占时,时间配额不变,重新得到CPU后将运行剩余的时间配额。区别出两种不同类型的线程

    时间配额用完:1

    2

    3线程a的优先级没有降低:如果队列中有其他就绪线程,选择下一个线程执行,a回到原来就绪队列末尾;如果队列中没有其他就绪线程,系统给线程a重新分配一个新的时间配额,让他继续运行;

    线程a的优先级降低了:Windows将选择一个更高优先级的线程去运行;

    线程优先级提升与时间配额调整:1

    2

    3提升线程的优先级

    给线程分配一个很大的时间配额

    提升线程的优先级:(只针对可变优先级线程)1

    2

    3

    4

    5

    6

    7

    8

    9I/O操作完成

    信号量或时间等待结束

    前台进程中的线程完成一个等待操作

    由于窗口活动而唤醒窗口线程

    线程处于就绪态超过了一定的时间还没有被调度运行(产生了饥饿现象)

    展开全文
  • 操作系统基础概念

    千次阅读 2020-12-23 12:41:57
    计算机系统概述基本构成CPU内存I/O系统总线中断中断:其他模块(I/O,存储器)中断 处理器正常处理过程 的机制。程序中断时钟中断硬件失效中断I/O中断多中断的处理方式第一种方法是当正在处理一个中断时,禁止再发生...

    计算机系统概述

    基本构成CPU

    内存

    I/O

    系统总线

    中断

    中断:其他模块(I/O,存储器)中断 处理器正常处理过程 的机制。程序中断

    时钟中断

    硬件失效中断

    I/O中断

    多中断的处理方式

    第一种方法是当正在处理一个中断时,禁止再发生中断。

    第二种方法是定义中断优先级,允许高优先级的中断打断低优先级的中断 处理器的运行。

    高速缓冲存储器

    高速缓冲存储器是比主存小而快的存储器,用以协调主存跟处理器,作为最接近储存地址的缓冲区。

    存储器的层次结构

    考虑因素: 价格, 容量, 访问时间

    速度: 寄存器 > 高速缓存 > 内存 > 磁盘

    高速缓存的设计高速缓存大小

    置换算法

    块大小

    写策略

    映射函数

    高速缓存的级数

    I/O操作的三种技术可编程I/O

    中断驱动I/O

    直接存储访问

    操作系统概述作为 用户/计算机 接口

    作为资源管理器

    批处理(多道程序设计)的目标 : 充分使用处理器 分时的目标: 减少响应时间

    操作系统的内核

    内核是操作系统最常使用的部分,它存在于主存中并在特权模式下运行,响应进程调度和设备中断。

    多道程序设计

    多道程序设计是一种处理操作,它在两个或多个程序间交错处理每个进程。

    实地址和虚地址

    虚地址指的是存在于虚拟内存中的地址,它有时候在磁盘中有时候在主存中。 实地址指的是主存中的地址。

    内存管理的任务进程隔离

    内存自动分配和管理

    支持模块化程序设计

    保护和访问控制

    长期存储

    操作系统的控制结构

    操作系统维持着四种不同类型的表:内存,I/O,文件,进程

    内存,I/O和文件是代表进程而被管理的,因此进程表必须有对这些资源的直接或者间接引用。

    进程

    进程是操作系统对正在运行的程序的一种抽象

    进程状态运行态:该进程正在执行

    就绪态:进程做好了准备,只要有机会就开始执行

    阻塞态:进程在某些事件发生前不能执行,如I/O操作完成

    新建态:刚刚创建的进程,操作系统还没有把它加入到可执行进程组中

    退出态:操作系统从可执行进程组中释放出的进程,或者是因为它自身停止了,或者是因为某种原因被取消

    进程阻塞和挂起

    阻塞:进程是否等待一个事件 挂起:进程是否已经被换出内存

    进程抢占

    处理器为了执行另外的进程而终止当前正在执行的进程,这就叫进程抢占

    进程映像用户数据

    用户程序

    系统栈

    进程控制块

    交换

    交换是指把主存中某个进程的一部分或者全部内容转移到磁盘。当主存中没有处于就绪态的进程时,操作系统就把一个阻塞的进程换出到磁盘中的挂起队列,从而使另一个进程可以进入主存执行

    进程间通信

    1、管道:管道是单向的、先进先出的、无结构的、固定大小的字节流,它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据,读进程在管道的道端读出数据。数据读出后将从管道中移走,其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时,在有数据写入管道前,进程将一直阻塞。同样地,管道已经满时,进程再试图写管道,在其它进程从管道中移走数据之前,写进程将一直阻塞。

    无名管道:管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系(通常是指父子进程关系)的进程间使用。

    命名管道:命名管道也是半双工的通信方式,在文件系统中作为一个特殊的设备文件而存在,但是它允许无亲缘关系进程间的通信。当共享管道的进程执行完所有的I/O操作以后,命名管道将继续保存在文件系统中以便以后使用。

    2、信号量:信号量是一个计数器,可以用来控制多个进程对共享资源的访问。它常作为一种锁机制,防止某进程正在访问共享资源时,其它进程也访问该资源。因此,主要作为进程间以及同一进程内不同线程之间的同步手段。

    3、消息队列:消息队列是由消息的链表,存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

    4、信号:信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生。

    5、共享内存:共享内存就是映射一段能被其它进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问。共享内存是最快的IPC方式,它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制(如信号量)配合使用,来实现进程间的同步和通信。

    6、套接字:套接字也是一种进程间通信机制,与其它通信机制不同的是,它可用于不同机器间的进程通信。

    进程控制块

    进程标识,处理器状态信息,进程控制信息

    用户模式和内核模式

    用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系统受到破坏或者修改。而在内核模式下则没有这些限制,从而使它能够完成其功能

    创建新进程的步骤给新进程分配一个唯一的进程标识号。

    给进程分配空间。

    初始化进程控制块。

    设置正确的连接。

    创建或扩充其他的数据结构。

    模式切换和进程切换的区别

    发生模式切换可以不改变当前正处于运行态的进程的状态。发生进程切换时,一个正在执行的进程被中断,操作系统指定另一个进程为运行态。进程切换需要保存更多的状态信息。

    线程 和 进程的 区别 联系

    进程是系统进⾏资源分配和调度的基本独⽴单位; 线程是进程的⼀个实体,是CPU调度和分派的基本单位。

    ⼆者联系:⼀个线程只属于⼀个进程,⼀个进程中可以有多个线程

    资源分配给进程,进程内的线程共享该进程的资源

    多进程和多线程在执⾏过程中都需要⼀定的同步机制进⾏同步

    ⼆者区别:本质:进程是拥有系统资源的基本单位,⽽线程是调度和分配的基本单位

    地址空间和其他资源:进程间(⼀般)相互独⽴,⽽同⼀进程的各线程之间共享进程资源

    通信:进程间通信根据场景不同会使⽤不同的通信⼿段(信号、共享内存、管道、套接字等),⽽线程通常使⽤共享内存⽅式并需要⼀定的同步与互斥⼿段辅助

    系统开销:进程在创建和切换的开销远⼤于线程,但进程相⽐线程更加健壮(因为进程之间相互独⽴)

    线程和进程的区别

    从概念上: 进程:一个程序对一个数据集的动态执行过程,是分配资源的基本单位。 线程:一个进程内的基本调度单位。线程的划分尺度小于进程,一个进程包含一个或者更多的线程。

    从执行过程中来看: 进程:拥有独立的内存单元,而多个线程共享内存,从而提高了应用程序的运行效率。 线程:每一个独立的线程,都有一个程序运行的入口、顺序执行序列、和程序的出口。但是线程不能够独立的执行,必须依存在应用程序中,由应用程序提供多个线程执行控制。

    从逻辑角度来看(重要区别): 多线程的意义在于一个应用程序中,有多个执行部分可以同时执行。但是,操作系统并没有将多个线程看做多个独立的应用,来实现进程的调度和管理及资源分配。

    多进程和多线程对比

    数据共享、同步

    继承数据是分开的:共享复杂,需要用IPC;同步简单。

    多线程共享进程数据:共享简单;同步复杂。

    内存、CPU

    进程占用内存多,切换复杂,CPU利用率低

    线程占用内存少,切换简单,CPU利用率高

    创建销毁、切换

    进程创建销毁、切换复杂,速度慢

    线程创建销毁、切换简单,速度快

    编程调试

    进程编程简单,调试简单

    线程编程复杂,调试复杂

    可靠性

    进程间不会相互影响

    一个线程挂掉将导致整个进程挂掉

    分布式

    进程适应于多核、多机分布 ;如果一台机器不够,扩展到多台机器比较简单 线程适应于多核分布

    1 需要频繁创建销毁的优先用线程。

    2 需要进行大量计算的优先使用线程。

    3 强相关的处理用线程,弱相关的处理用进程。

    4 可能扩展到多机分布的用进程,多核分布的用线程。 5 都满足需求的情况下,用你最熟悉、最拿手的方式。

    互斥和同步

    临界区

    临界资源就是一次只允许一个进程访问的资源 所谓临界区就是进程中访问临界资源的那段程序代码

    同步机制应遵循的准则

    空闲让进,忙则等待,有限等待,让权等待

    PV

    P,V操作是因为Dijkstra是荷兰人,P指的是荷兰语中的“proberen”,意为“测试”,而V指的是荷兰语中的“verhogen”,意为“增加”。

    P(S): while (S≤0) {do nothing};

    S=S-1;

    V(S): S=S+1;

    但是这样明显违反了“让权等待的原则”

    记录型信号量

    P(S): S.value = S.value-1;

    if(S.value < 0)

    block(S,Q);

    V(S): S.value = S.value + 1;

    if(S.value <= 0)

    wakeup(S,Q);

    P操作相当于“等待一个信号”,而V操作相当于“发送一个信号”,在实现同步过程中,V操作相当于发送一个信号说合作者已经完成了某项任务,在实现互斥过程中,V操作相当于发送一个信号说临界资源可用了。实际上,在实现互斥时,P,V操作相当于申请资源和释放资源。

    同步与互斥实现的P,V操作虽然都是成对出现,但是互斥的P,V操作出现在同一个进程的程序里,而同步的P,V操作出现在不同进程的程序中

    死锁和饥饿死锁预防

    死锁避免

    死锁检测

    死锁的条件互斥

    占有且等待

    非抢占

    循环等待

    内存管理

    内部碎片和外部碎片

    内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象,它是指在所有分区外的存储空间会变成越来越多的碎片的

    逻辑地址、相对地址和物理地址

    逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址,在执行对内存的访问之前必须把它转化成物理地址。

    相对地址是逻辑地址的一个特例,是相对于某些已知点(通常是程序的开始处)的存储单元。

    物理地址或绝对地址是数据在主存中的实际位置。

    页和帧

    在分页系统中,进程和磁盘上存储的数据被分成大小固定相等的小块,叫做页。而主存被分成了同样大小的小块,叫做帧。一页恰好可以被装入一帧中。

    页和段

    分段是细分用户程序的另一种可选方案。采用分段技术,程序和相关的数据被划分成一组段。尽管有一个最大段长度,但并不需要所有的程序的所有段的长度都相等

    虚拟内存

    简单分页与虚拟分页

    简单分页:一个程序中的所有的页都必须在主存储器中程序才能正常运行,除非使用覆盖技术。

    虚拟内存分页:不是程序的每一页都必须在主存储器的帧中来使程序运行,页在需要的时候进行读取。

    页表项帧号:用来表示主存中的页来按顺序排列的号码。

    存在位(P):表示这一页是否当前在主存中。

    修改位(M):表示这一页在放进主存后是否被修改过。

    驻留集和工作集

    一个进程的驻留集是指当前在主存中的这个进程的页的个数。

    一个进程的工作集是指这个进程最近被使用过的页的个数。

    单处理器调度短程调度

    中程调度

    长程调度

    多处理器和实时调度

    I/O管理和磁盘调度

    文件管理

    文件组织堆

    顺序文件

    索引顺序文件

    索引文件

    直接或者散列文件

    文件分配方法连续文件

    链接文件

    索引文件

    展开全文
  • 这个类似先检查,如果 J I 都同时上来把自己置为了TRUE,则会相互无线等待下去,造饥饿现象。 4)peterson's Algotithm //Pi进程 flag[i]=TRUE; turn=j; while(flag[i]&&turn==j) critical section, flag[i]=false;...

    进程同步

    一、进程同步的基本概念

    1.临界资源

    一次仅允许一个进程使用的资源称为临界资源。

    临界资源的访问:

    do{

    entry section;//进入区,设置正在访问标志,以阻止其他进程同时访问。critical section;//临界区,访问临界资源那段代码,临界段。exit section;//退出区,清除正在访问标志。remainder section;//代码中剩余的部分。}while(true)

    2.同步同步亦称直接制约关系,是指为完成某种任务而建立的两个或多个进程,这些进程因为需要 在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。

    3.互斥互斥也称间接制约关系。当一个进程进入临界区使用临界资源时,另一个进程必须等待,当 占用临界资源的进程退出临界区后,另一进程才允许去访问此临界资源

    同步机制应遵循的准则空闲让进

    忙则等待

    有限等待:对于请求访问的进程,应保证能在有限的时间内进入临界区。

    让权等待:进程不能进入临界区时,应立即释放处理器,防止进程忙等待。

    忙等状态:

    当一个进程正处在某临界区内,任何试图进入其临界区的进程都必须进入代码连续循环,陷入忙等状态。连续测试一个变量直到某个值出现为止,称为忙等。

    让权等待:

    当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”状态~(受惠的是其他进程)

    二、实现临界区互斥的基本方法

    1.软件实现方法

    1)单标志法

    用公共变量turn标志该谁进入临界区

    //P0进程

    while(trun != 0);

    critical section;

    turn=1;

    remainder section;

    //P1进程

    while(turn != 1);

    critical section;

    turn=0;

    remainder section;

    这个方法的缺点是两个进程必须交替进去临界区,如果一个进程不进入的话,turn就无法再被改变了,就会导致另一个进程一直等待下去。

    2)双标志法先检查:

    设置了两个标志,分别表示两个进程的状态,可以不用交替执行,可以连续使用。

    //Pi进程

    while(flag[j]);//1

    flag[i]=TRUE;//3

    critical section;

    flag[i]=FALSE;

    remainder section;

    //Pj进程

    while(flag[i]);//2

    flag[j]=TRUE;//4

    critical section;

    flag[i]=FALSE;

    remainder section;

    但是也有缺点,比如进程 i 执行语句1,先判断进程 j 没有要进入临界区。同时 j 也在执行语句2,它觉得 i 也没有去临界区的意思。于是 i 把自己的flag置为了TURE,此时 j 在判断时 i 还没来得及置标志,所以 j 也把自己置成了TRUE,然后此时有两个进程都在临界区,违背了基本原则。

    3)双标志法后检查

    //Pi进程

    flag[i]=TRUE;

    while(flag[j]);

    critical section;

    flag[i]=FALSE;

    remainder section;

    //Pj进程

    flag[j]=TRUE;

    while(flag[i]);

    critical section;

    flag[i]=FALSE;

    remainder section;

    这个类似先检查,如果 J I 都同时上来把自己置为了TRUE,则会相互无线等待下去,造饥饿现象。

    4)peterson's Algotithm

    //Pi进程

    flag[i]=TRUE;

    turn=j;

    while(flag[i]&&turn==j)

    critical section,

    flag[i]=false;

    remainder section;

    //Pj进程

    flag[i]=TRUE;

    turn=j;

    while(flag[i]&&turn==j);

    critical section;

    flag[i]=false;

    remainder section;

    一个标志自己的状态(申明),一个标志该谁使用临界区(钥匙)。

    也就是只有一把钥匙。就是双方想执行的时候都要把钥匙先给对方,所以无论是谁先申明还是同时申明,最后钥匙是在一个人手里的,然后在进入临界区之前判断,如果对方想要进入而且拥有钥匙,我就等待。如果对方没有钥匙或者不想进入,那我就进入。不可能出现两个人都有想进入两个人都有钥匙的情况(钥匙只有一把),解决了死等的问题。

    如果此时 j 执行完了,不再执行了。while 就会放开 i ,i 可以继续执行。即使后 j 都不再执行力,i 也不会再次被 while 捕捉。解决了交替执行的问题。

    2.硬件实现的方法

    1)中断屏蔽法

    进入临界区后禁止一切中断发生。这种方法限制了处理机交替执行程序的能力,因此执行的效率会明显降低。对内核来说,在 它执行更新变量或列表的几条指令期间,关中断是很方便的,但将关中断的权力交给用户则很不明智,若一个进程关中断后不再开中断,则系统可能会因此终止。

    2)硬件指令的方法

    TestAndSet指令:原子操作,执行过程不允许被中断,其功能是读出某标志后置为真。

    boolean TestAndSet(boolean *lock){

    boolean old;

    old=*lock;

    *lock=true;

    return old;

    }

    进入临界区之前使用TestAndSet检查修改标志lock,如果为true则重复检查。

    如果为false则不会被while捕捉,如果为true就相当于一直在置true,直到其他进程将lock置为了false,while才放走。

    while TestAndSet(&lock);

    进程的临界代码块;

    lock=false;

    进程的其他代码;

    swap指令:交换两个字节的内容

    Swap(boolean *a,boolean *b){

    boolean temp;

    temp=*a;

    *a=*b;

    *b=temp

    }

    这里key是局部变量,lock是共享变量,同样可以理解为声明和钥匙。

    申明我要进入临界区,然后进入while循环,此时如果临界区没人,lock等于false,此时钥匙在,然后swap交换之后key拿到了false值(钥匙),就可以走出循环进入临界区。

    key=true;

    while(key!=false)

    swap(&lock,&key);

    进程临界区代码段;

    lock=false;

    进程其他代码;硬件方法的优点:适用于任意数目的进程,而不管是单处理机还是多处理机。简单、容易验 证其正确性。

    硬件方法的缺点 :进程等待进入临界区要耗费处理机时间,不能实现让权等待。从等待进程中随机选择一个进入临界区,有的进程可能一直选不上,从而导致“饥饿”现象。

    三、信号量

    1.整型信号量

    wait(S)/signal(S)

    可记为P操作和V操作

    wait(s){

    while(s<=0);

    s=s-1

    }

    singal(s){

    s=s+1

    }

    在wait中,会一直去测试s是否小于等于0,所以该机制还是处于一个忙等的状态。

    2.记录型信号量

    相比整型,他不存在忙等现象。

    typedef struct{

    int value;

    struct process *L;

    } semaphone

    void wait(semaphore s){

    s.value- -;//申请一个资源,老板我要一个小熊饼干

    if(s.value<0){//如果该类资源不够,老板说小熊饼干卖完了

    add this process to s.L;//加入等待队列,老板说帮你预定一个你明天来拿

    block(s.L);//block原语,自我阻塞,释放处理器资源,回家去等

    }

    }

    void signal(semaphonre s){

    s.value++;//释放一个资源,有个顾客退回了一个小熊饼干

    if(s.value<==0){//老板发现还有人在等

    remove a process p from s.L;//打电话叫他来拿了

    wakeup(p);//唤醒进程,来店里了

    }

    }

    3.利用信号量实现同步

    semahore s=0;//初始化信号量

    p1(){

    ....

    x;//语句x

    V(s);//告诉p2语句x已经完成

    ...

    }

    p2(){

    ...

    p(s);//看看x是不是已经完成

    y;//无误,执行y

    ..

    }

    4.利用信号量实现互斥

    semaphore s=1;//初始化信号量

    p1(){

    ..p(s);//上锁

    进程P1临界区

    v(s);//开锁

    ..

    }

    p2(){

    ..

    p(s);//上锁

    进程p2的临界区;

    v(s);//开锁

    ..

    }

    5.实现前驱关系为了保证执行顺序,设置信号量如图

    semaphore a1=a2=b1=b2=c=d=e=0;

    s1(){

    ..;

    v(a1);

    v(a2);

    }

    s2(){

    p(a1);

    ...;

    v(b1);

    v(b2);

    }

    s3(){

    p(a2);

    ..;

    v(c);

    }

    s4(){

    p(b1);

    ..;

    v(d);

    }

    s5(){

    p(b2);

    ..;

    v(e);

    }

    s6(){

    p(c);

    p(d);

    p(e);

    ..

    }

    6.分析进程同步和互斥问题的方法步骤

    1)分析关系

    2)整理思路

    3)设置信号量

    四、管程

    1.定义代表共享资源的数据结构 ,以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序,称为管程( monitor )。

    管程由四个部分组成:

    1)名称

    2)局部于管程内部的共享数据结构数据说明

    3)对该数据结构进行操作的一组过程

    4)对局部于管程内部的共享数据设置初始值的语句

    例如

    monitor Demo{

    //定义共享数据结构

    共享数据结构s;

    //初始化数据结构

    init_code(){

    s=5;//初始资源

    }

    take_away(){

    对共享数据结构x的一系列处理;

    s--;

    ..

    }

    give_back(){

    对共享数据结构x的一些系列处理;

    s++;

    ..

    }

    }

    2.条件变量

    当一个进程进入管程后被阻塞,如果一直阻塞的原因没有解除,则不会释放管程则其他进程不能进入管程。

    monitor Demo{

    共享数据结构;

    condition x;

    init_code(){

    ..

    }

    take_away(){

    if(s<=0) x.wait();//资源不够,在x上阻塞等待

    资源足够,分配资源,处理;

    }

    give_back(){

    归还资源,做处理;

    if(有进程在等待)x.signal;//唤醒一个阻塞进程

    }

    }

    展开全文
  • 一、资源 把需要排他性使用的对象称为资源。资源可以是硬件也可以是软件,比如打印机或者数据库中的...这就是饥饿现象,可以考虑通过动态优先级机制,可以动态提高长时间得不到运行的进程的优先级,从而使它可以运行。
  • 了解死锁与饥饿产生的条件 了解死锁的解决方法 掌握利用银行家算法进行死锁避免
  • 操作系统:死锁和饥饿

    千次阅读 多人点赞 2019-11-13 18:17:47
    饥饿:指系统不能保证某个进程的等待时间上界,从而使该进程长时间等待,当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被...
  • 操作系统:线程死锁、饥饿、活锁
  • 操作系统试题

    2020-12-23 12:41:53
    题号一二三四五六总分得分评卷人一、单项选择题(每小题2分,共20分)1.当CPU处于管态时,它可以执行的...操作系统提供给程序员的接口是________。A.进程B.系统调用C.库函数D.B和C4.进程从运行状态到阻塞状态可能是由于...
  • 防止饥饿:避免总是选择同 一 个牺牲者 ( 考虑其回滚次 数 ) 某系统中仅有 5 个并发进程竞争某类资源, 且都需要 3 个该类资源,那么至少有(11)个 该类资源,才能 保证 系统不会发生死锁 解析:5个并发进程,需要3个...
  • 操作系统理论中,什么是饿死饥饿饿死 饥饿   在操作系统理论中,饥饿指的是一个进程长期得不到运行,而处于长期等待的状态。 饿死   在操作系统理论中,饿死指的是一个进程一直及以后也不会得到运行,处于永久...
  • 内核级线程的调度由操作系统完成B.操作系统为每个用户级线程建立一个线程控制块C.用户级线程间的切换比内核级线程间的切换效率高D.用户级线程可以在不支持内核级线程的操作系统上实现【答案】B【解析】用户级线程...
  • 进程 vs 线程进程(process)与线程(thread)最大的区别是进程拥有自己的地址空间,某进程内的线程对于其他进程不可见,即进程A不能通过传地址的方式直接读写进程B的存储区域。...进程作为操作系统中拥有资源和独立调度...
  • 区别 死锁 饥饿 死循环 概念 各进程相互等待对方手里的资源。导致各进程都阻塞,无法向前推进的现象。...由于长期得不到想要的资源,某进程无法向前推进的现象。...操作系统分配资源的策略不合理导致5.是管理者(操...
  • 出题方向:“进程会/不会死锁”、“能/不能保证进程互斥进入临界区”、“会/不会出现‘饥饿现象”,本人整理了遇到的共6个相关问题,并附上答案:
  • 死锁:进程间因循环等待资源出现的永久性阻塞现象 可抢占性资源:可以从拥有它的进程中剥夺而不会产生任何不良影响的资源(竞争可抢占性资源不会引起死锁问题) 不可抢占性资源:拥有它的进程在主动释放前,不能被...
  • 操作系统常见面试题

    2020-12-23 12:41:58
    (2)消息传递系统(进程间的数据交换以消息(message)为单位,当今最流行的微内核操作系统中,微内核与服务器之间的通信,无一例外地都采用了消息传递机制。应用举例:邮槽(MailSlot)是基于广播通信体系设计...
  • 下列调度算法中,不可能导致饥饿现象的是( )。A.时间片轮转 B.静态优先数调度C.非抢占式短作业优先 D.抢占式短作业优先答案:A24.某系统有n台互斥使用的同类设备,三个并发进程分别需要3、4、5台设备,可确保...
  • 操作系统课件——05死锁与饥饿_922004864.ppt
  • 山大操作系统实验5

    2021-06-18 02:13:32
    山大操作系统实验5(25页)本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!19.90 积分实用文档进程同步实验张咪软件四班一、实验目的总结和分析示例实验和独立实验中观察到的...
  • 操作系统概念 控制和管理整个计算机的硬件与软件资源**(系统资源管理者,安全、高效)** 提供给用户和其他软件方便的接口与环境 (向上层提供方便易用的服务),用户无需关心底层实现原理,只需向操作系统发出命令...
  • 5. 移臂调度算法中最短寻道调度算法可能出现请求的饥饿现象。( ) 【答案】对 7. 磁盘旋转调度的原则是总让首先到达读写磁头位置下的扇区先进行传输操作。( ) 【答案】对 8. 执行系统调用时会产生中断。( ) ...
  • [操作系统] - No.2 死锁、活锁,饥饿

    千次阅读 2017-08-17 10:32:14
    死锁的规范定义是:如果一个进程集合中的每个进程都在等待只能由...饥饿:当一个进程一直无法得到自己的资源而一直无法进行后续的操作时(不一定是阻塞),我们称这个进程会饥饿而死。显然,死锁和活锁都会饥饿
  • 1. 下列选项中,操作系统提供给应用程序的接口是___A__。A.系统调用 B.中断 C.库函数 D.原语系统调用是操作系统提供给编程人员的唯一接口。--《计算机操作系统教程》2. 下列选项中,导致创建新进程的操作是___C___。I ...
  • 操作系统-并发:死锁和饥饿

    千次阅读 2019-05-26 13:32:22
    本章介绍并发处理中需要解决的两个问题:死锁和饥饿。本章首先讨论死锁的基本原理和饥饿的相关问题;接着分析处理死锁的三种常用方法:预防、检测和避免;然后考虑用于说明同步和死锁的一个经典问题;哲学家就餐问题...
  • 操作系统(OS) 笔记根据B站王道计算机考研——操作系统视频整理所得,视频链接:https://b23.tv/0I2qex 视频中所用课件:链接:https://pan.baidu.com/s/101bFWm0Tv0emNpEneidYPA 提取码:y3dd 1.计算机...
  • 【1】操作系统中常见的一些调度算法对比分析 算法名称 算法思想 适用调度场景 是否可抢占 优缺点 是否导致饥饿 先来先服务算法(FCFS) 按照作业/进程到达的先后次序来进行调度 作业调度&进程调度 不可...
  • 文章目录一、作业的基本知识1.作业和作业步2.作业运行的三个阶段二、先来先服务(FCFS)...系统根据该说明书来对程序的运行进行控制。 (2)作业步:在作业运行期间,每个作业都必须经过若干个相对独立,又相互关联.
  • 操作系统复习笔记

    万次阅读 多人点赞 2021-01-20 15:11:12
    第一章 计算机系统概述 基本概念 基本构成:处理器、内存、输入/输出模块、系统总线 处理器中各寄存器的作用 处理器分为执行单元、控制单元、寄存器(用户可见寄存器、控制和状态寄存器) 用户可见寄存器 数据...
  • 一组进程中,每个进程都无限等待被该组进程中另一个进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程(处于阻塞态) 2,什么是可重用资源?(P186) 一次只能供一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,107
精华内容 3,642
关键字:

操作系统饥饿现象

友情链接: teafa.zip