精华内容
下载资源
问答
  • 多处理机系统模型主要有三类:分别是共享存储器多处理机、消息传递计算机、广域分布式系统 共享存储器多处理机:获得高速的一种处理方式就是使用并行处理机。这些机器使用许多CPU, 每一个都以“通常”的速度运行...

    多处理机系统模型主要有三类:分别是共享存储器多处理机、消息传递多计算机、广域分布式系统

    • 共享存储器多处理机:获得高速的一种处理方式就是使用并行处理机。这些机器使用许多CPU, 每一个都以“通常”的速度运行,但是总体上会比单个CPU强大得多的计算能力。
    • 消息传递多处理机系统:许多CPU-存储器通过某种高速互联网络连接在一起。这种系统称为消息传递型多计算机。
    • 广域分布式系统:所有计算机通过一个广域网连接起来,如因特网构成了一个分布式系统。

    在这里插入图片描述

    8.1 多处理机

    共享存储器多处理机是有两个或更多的CPU全部共享访问的一个公用的RAM,运行在任何一个CPU上的程序都看到一个普通的(通常是分页)的虚拟地址空间。这个系统唯一特别的性质是,CPU可对存储器字写入某个值,然后读会这个字,得到一个不同的值(因为另一个CPU改写了它)。

    8.1.1 多处理机硬件

    所有多处理机都具有每个CPU可访问全部存储器的性质,而有些多处理机仍有一些其它的性质,即读出每个存储器字的速度是一样快的。这种及其称为UMA(统一存储器访问)多处理机,而另一种则称为NUMA(非一致存储器访问)多处理机。

    1. 基于总线的UMA多处理机体系结构

    通过给每个CPU添加一个高速缓存(cache),这个高速缓存可以位于CPU芯片内部,CPU附近,处理器板上或所有三种方式的组合。因为许多读操作可以在高速缓存中得到满足,总线流量被大大减少了,这样系统就能支持更多的CPU。

    在这里插入图片描述

    高速缓存一致性协议:每一个高速缓存块或者被标记为只读(此时可以存在与多个告诉缓存中),或者被标记为读写(不能出现在多个高速缓存)。如果CPU试图在一个或多个远程高速缓存中写入一个字,总线硬件检测到写,并把一个信号放到总线上通知所有其它的高速缓存。如果其他高速缓存有个"干净"的副本,也就是同存储器内容完全一样的副本,那么它们就可以丢弃该副本并让写在修改之前从存储器中取出高速缓存块。如果某些其它高速缓存中有“脏”副本(被修改的副本),它必须在处理写之前把数据写回存储器或者它通过总线直接传送到写者上。高速缓存这一套规则被称为高速缓存一致性协议。

    2.使用交叉开关的UMA处理机

    连接n个CPU到k个存储器的最简单的电路就是交叉开关。

    在这里插入图片描述

    交叉开关最好的一个特性是它是一个非阻塞网络,即不会因有些交叉点或连线已经被占据而拒绝连接。

    3.使用多级交换网络的UMA多处理机

    在这里插入图片描述

    有一种完全不同的、基于简单2X2开关的多处理机的设计。这个开关有两个输入和两个输出。到达任意一个输入线的消息可以被交换至另一个输出线上去。就我们的目标而言,消息可用由四个部分组成。Module(模块)域指明使用哪个存储器。Address(地址)域指定在模块中的地址。Opcode(操作码)给定了操作,如READ或者WRITE。最后一个可选的Value(值)域中可包含一个操作数。

    这个2X2开关有多种使用方式,用于构建大型的多级交换网络。

    在这里插入图片描述

    4. NUMA多处理机

    这种机器为所有CPu提供一个统一的地址空间,但是访问本地存储器模块快于访问远程存储器模块。因此,在NUMA机器运行的所有NUMA程序无须做任何改变,但是相同的时钟速率下其性能不如UMA机器的性能。

    所有NUMA机器都具有以下三种关键特性:

    1. 就有对所有CPU都可见的的单个地址空间。
    2. 通过LOAD和STORE指令访问远程存储器。
    3. 访问远程存储器慢于访问本地存储器。

    5.多核芯片

    将两个或者多个完整的CPU。通常称为核(Core),放到同一个芯片上(技术上来说是同一个小硅片)。双核、四核和八核的芯片已经很普及了。

    6.众核芯片

    众核芯片是指包括几十、几百甚至成千上万个核心的多核处理器。

    7.异构多核

    一些芯片会把异构GPU和一些通用的处理器核心放在一起。在一块芯片上封装了不同的处理器的系统被统称为异构多核处理器。

    8.在多核心上编程

    8.1.2 多处理机操作系统类型

    1.每个CPU都有自己的操作系统

    静态地把存储器划分成和CPU一样多的各个部分,为每个CPU提供其素有存储器以及操作系统的各自私有副本。这样的明显优点是,允许所有CPu共享操作系统的代码,而且只需要提供数据的私有副本。

    在这里插入图片描述

    2.主从多处理机

    在这种模型下,操作系统的一个副本机器数据表都在一个CPU上,所有的系统调用都重定向到CPU1上。如果有剩余的CPu时间,还可以在CPU1上运行用户进程。这种模型称为主从模型。

    当某个CPU空闲下来时,它向CPU1上的操作系统请求一个进程运行,并被分配一个进程。这个模型的问题是,如果有很多CPU,那么出CPU会称为瓶颈。

    在这里插入图片描述

    3.对称多处理机

    在存储器中有操作系统的一个副本,但任何CPU都可以运行它。在有系统调用时,进行系统调用但CPU陷入内核并处理系统调用。

    在这里插入图片描述

    当一个CPU要运行操作系统时,它必须首先获得互斥信号量。如果互斥信号量被锁住。就得等待。按照这种方式,任何CPu都可以运行操作系统,但任意时刻只有一个CPU可运行操作系统。这样就需要把操作系统分割成互不影响但临界区。每个临界区由其互斥信号量保护,所以一次只能有一个CPU运行它。

    由于这一事实,可以将操作系统分割成不同的互不影响的临界区。每个临界区由其互斥信号量保护,所以一次只有一个CPU可以执行它。采用这种方式,可以实现更多的并行操作。而某些表格,如进程表,可能恰巧被多个临界区使用。

    大多数但现代多处理机都采用这种安排。更进一步,要尽量避免死锁。

    8.1.3 多处理机同步

    我们仔细讨论一下指令TSL(Test and Set Lock)是如果实现临界区的。这条指令的做法:读出一个存储器字并把它存储到一个寄存器中。同时,它对该寄存器字写入一个1.当然这需要两个总线周期来完成存储器的读写。在单处理机中,只要该指令不被中途中断,TSL指令就如实正常运行。

    在这里插入图片描述

    TSL指令必须首先锁住总线,阻止其它CPU访问他,然后进行存储器的读写访问,再解锁总线。对总线枷锁的典型做法是,先使用通风的总线协议请求总线,然后申明已拥有某些特定的总线线路,直到两个周期全部完成。只要始终保持拥有这一特性的总线线路,那么其他CPU就不会得到总线的访问权。这个指令只有在拥有必要的线路和使用它们的协议上才能实现。

    如果正确的实现和使用TSL,就能保证互斥机制正常工作。但是这种互斥方法使用了自旋锁。因为请求的CPU只是在原地尽可能快得对锁进行循环测试

    高速缓存的实现也许能够消除总线竞争的问题,但事实并非如此。理论上,只要提出CPU已经读取了锁字(Lock word),它就可以在其高速缓存中得到一个副本。只要没有其他CPU试图使用该锁,提出请求的CPU就能够用完其高速缓存,当拥有锁的CPU写入一个0高速缓存并释放它时,搞缓存会自动将它在远程高速缓存中的所有副本失效,要求再次读取正确的值。

    问题:通常,拥有锁的CPU也需要这个锁周围的字。由于TSL指令是一个写指令(因为它修改了锁),所以它需要互斥地访问含有锁的高速缓存块。这样每一个TSL指令都使锁持有者的高速缓存中的块失效,并且为请求的CPU取一个私有的、唯一的副本。只要锁拥有者访问到该锁的邻接字,该高速缓存块就被送到其机器。这样一来,整个包含锁的高速缓冲块就会不断地在锁的拥有者和锁的请求者之间来回穿梭,导致了比单个读取一个锁字更大的总线流量。

    解决方案:

    • CPU首先进行一个存读操作来观察锁是否是空闲的,就可以实现这个目标。只有在锁是空闲的,TSL指令才去真正获取它。这种小小的变化,导致的是大多的行为变成读而不是写。
    • 减少总线流量的方式是泗洪柱面的以太网二进制指数补偿算法。不采用轮询,而将一个延迟插入轮询之间,每次延迟时间加倍。
    • 一个更好的思想是,让每个打算获得互斥信号量的CPU都拥有歌词用于测试的私有锁变量。

    在这里插入图片描述

    自旋与切换

    需要加锁的互斥信号量的CPU只是保持等待。有时对于提出请求的CPU而言,只有等待,不存在其他等待的办法。

    自旋直接浪费了CPU周期,重复地测试锁并不是搞笑的工作。不过,切换也浪费了CPU周期,因为必须保存当前线程的状态,必须获得保护就绪链表的锁,还必须选择一个线程,必须装入其状态,并且使其开始运行。

    多数研究工作是用来一种新的模型:一个未能获得互斥信号量的线程先自旋一段时间,若时间超过某个阙值,则切换。

    8.1.4 多处理机调度

    对于多线程的调度,可以分为两类:分别是用户线程的调度和内核线程的调度。

    • 用户线程的调度:,如果线程是由用户空间库维护,而对内核不可见。那么调度一如既往的基于单个进程。如果内核并不知道线程的存在,它就不能调度线程。
    • 内核线程的调度:而对内核线程,是内核选择线程作为调度单位,内核可以选择任意一个进程的任一线程。

    1.分时

    处理独立线程的最简单的算法是,为就绪线程维护一个系统级的数据结构,它可能只是一个链表,但更多但情况下可能是对应不同优先级但一个链表集合。

    在这里插入图片描述

    使用单一数据结构调度一个多处理机,存在的缺点:

    • 随着CPU数量增加引起但对调度数据结构对潜在竞争
    • 线程由于IO阻塞而因为对上下文切换对开销。

    当线程时间片用完时,也可能会发生上下文切换。

    为了避免这种情况,一些系统采用智能调度算法。获得自旋锁的进程设置一个进程范围的标志表示它目前拥有自旋锁,当释放时,就清除该标志。这样调度程序就不会停止拥有自旋锁的线程,相反,还会给更多的时间。

    为了预装缓冲块将提高高速缓存的命中率,从而提高线程的速度。有些多处理机使用了亲和调度。其基本思想是,尽量使一个线程在前一次运行过的同一个CPU上运行。创建这种请合理的一个途径是采用一种两级调度算法。

    两级调度算法:在一个线程创建的时候,他被分给了一个CPU,列如,可以基于哪个CPU在此刻有最小的负载。这种把线程分给CPU的工作在算法的顶层进行,其结果是每个CPU获得了自己的线程集。

    两级调度算法有三个优点:

    • 将负载大致平均的分配在可用的CPU上。
    • 尽可能发挥了高速缓存亲和力的优势
    • 每个CPU提供一个私有的就绪线程链表,使得对就绪线程链表的竞争见到最小,因为试图使用另一个CPU就绪线程链表的机会相对较小。

    2.空间共享

    当线程之间以某种方式彼此相关联的时候,可以使用多处理机调度方法。在多个CPU同时调度多个线程称为空间共享

    最简单的空间共享算法的基本思想:

    假设一组相关的线程时一次性创建的。在其创建的时刻,调度程序检查是否有同线程数量一样多的空闲CPU存在。如果有,每个线程获得各自的CPU并且都开始运行。如果没有足够的CPU,就没有现车开始运行,直到有足够的CPU开运行。

    8.2 多计算机

    多计算机是紧耦合CPU,不共享存储器。每台计算机中有自己的存储器。

    在这里插入图片描述

    8.2.1 多计算机硬件

    一个多计算机系统的基本节点包括一个CPU、存储器、一个网络接口、有时候还有一个硬盘。

    1. 互联技术

    在每个节点上有一个网卡,带有一根或两根网卡上接出的电缆。这些电缆或者连接到其他节点上去,或者链接到交换机上。

    在多计算机中可采用两种交换机制:

    • 存储转发包交换:每个消息首先被分解(由用户软件或网络接口进行)称为有最大长度限制的快,称为报。该交换机制称为存储转换包交换,由源节点的网络接口卡注入到第一个交换机的报组成。
    • 电路交换:它包括由第一个交换机建立的,通过所有交换机而到达目标交换机的一条路径。一旦电路建立,比特流就从源到目的地通过整个线路不停的传输。在所设计的交换机汇总,没有中间缓存,电路交换需要有一个建立阶段,它需要一点时间。但是一旦建立完成,速度就很快。在包发送结束后,该路径必须被删除。

    在这里插入图片描述

    2. 网络接口

    在多计算机中,所有节点里都有一块插卡板,它包含节点与互连网络的连接,这使得多计算机连城一体。

    很多接口板上有一个完整的CPU,可能另外还有一个或多个DMA通道。它们被称为网络处理器,并且其功能日趋强大。这种设计一位这主CPU将一些工作分给网卡。

    8.2.2 底层通信软件

    问题:如果说进出RAM的复制是性能瓶颈,那么进出内核的额外复制会将端到端的延迟加倍 ,并把吞吐量降低一半。为了避免进出RAM的复制称为系统性能瓶颈。我们有以下三种解决方案:

    1. 将接口板映射到所有需要它的进程中去,但是这样做就需要有一个机制来避免竞争。
    2. 需要某种同步机制,如注入一些同步互斥信号量。

    1. 节点至网络接口通信

    最快的方法是使用板上的DMA芯片直接将他们从RMA复制到板上,这种方法的问题上,DMA使用物理地址。而用户进程通常不知道有关的物理地址,并且独立于CPU运行,除非存大I/O MMU。

    2. 远程直接内存访问

    在上述情况下,降低数据的复制量都需要很大的代价。为了应对这个问题,一些网络接口支持远程直接内存访问技术,允许一台机器直接访问另一台机器的内存。RDMA不需要操作系统地参与,直接从应用的内存空间中读取或者写入数据。

    8.2.3 用户层通信软件

    1.发送和接受

    发送一条消息的系统调用:

    send(dest,&mptr); 
    

    接受消息的调用:

    receive(addr,&mptr)
    

    2.阻塞调用和非阻塞调用

    阻塞调用:当一个进程调用send时,它指定一个目标以及发送消息到该目标的缓冲区。当消息发送时,发送进程被阻塞(挂起)。在消息已经完成发送出去之前,不会执行跟随在调用send后面的指令。

    非阻塞调用:如果send是非阻塞的,在消息发出之前,它立即将控制返回给调用者。这种机制的

    在这里插入图片描述

    通常是由系统设计者作出在阻塞原语和非阻塞原语之间的选择。当然少数系统两种都可以使用。

    问题:非阻塞原语的性能优点被其缺点抵消了——直到消息被送出发送者才能修改消息缓冲区。进程在传输过程中重写消息的后果十分严重,更糟的是,发送进程不知道传输何时结束,所以根本不知道什么时候重用缓冲区是安全的。

    解决方案:

    1. 让内核复制消息到内核缓冲区,然后让进程继续。
    2. 当消息发送之后中断发送,告知缓冲区又可以使用了(用户级中断引发编程问题,而且可能引发竞争条件)
    3. 让缓冲区写时复制。在消息发送出去之前,若有修改,则进行复制(会引发不必要的复制)

    这样在发送端的选择是:

    1. 阻塞发送(CPU在消息传输期间空闲)
    2. 待有复制操作的非阻塞发送(CPU时间浪费在额外的复制上)。
    3. 带有中断操作的非阻塞发送(造成编程困难)。
    4. 写时复制(最终可能造成额外的复制)

    8.2.4 远程过程调用

    尽管消息传递模型提供了一种构造多计算机操作系统的便利,但是它也有不可救药的缺陷:构造所有相同通信的泛型都是输入/输出。

    远程过程调用:运行程序调用其他CPU的过程。当机器1的进程调用机器2的过程时,在机器1中的调用进程被挂起,在机器2中被调用的过程被执行。可以在参数中传递从调用者到调用者的信息,并且可以在过程的处理结果中返回消息。根本不存在对程序可见的消息传递或者I/O。这种技术成为远程过程调用(RPC)。

    在这里插入图片描述

    8.2.6 多计算机调度

    将进程分配到工作节点的工作十分重要。

    因为每个节点都拥有自己的进程,因此可以应用任何本地调度算法,但是仍有可能使用多处理机调度。

    8.2.7 负载均衡

    1.图论确定算法

    将节点分为子网,寻找子网之间流量最小的组合

    在这里插入图片描述

    2.发送者发起的分布式启发算法

    在这里插入图片描述

    当进程创建时,他就运行在创建它的节点上,除非该节点过载了。如果该节点过载了,该节点则随机选择一个节点并询问其负载情况。探查工作不会永远进行,在N次探查之后,如果没有合适的主机,算法就终止。且进程继续在原有机器上运行。

    在负载重的情况下,所有机器都会持续得对其他机器进行探查,徒劳地试图找到一台愿意接收工作的机器,这样的尝试会导致巨大的开销。

    3.接受者发起的分布式启发算法

    由接受者要求更多的工作

    8.3 分布式系统

    分布式系统的每一个节点都是一台完整的计算机,带有全部的外部设备。其次一台多计算机的所有节点一般分布在一个房间内,这样他们就可以通过专门的网络进行高速网络通信。而分布式系统中的节点则可能分散在全世界范文内。

    8.3.1 网络硬件

    网络主要有两种——覆盖一栋建筑物的LAN(局域网)和更大范围的WAN(广域网)

    LAN最重要的类型是以太网

    在这里插入图片描述

    1.以太网

    以太网有其最大电缆长度限制,以及可连接的最多的计算机台数限制。要想超过其中一个限制,就要在一座大建筑物或校园中连接多个以太网,然后用一种成为桥接器的设备把这些意外网连接起来。

    为了避免碰撞问题,现代以太网使用交换机。如果能人后较大的交换机成本,可以使每台机器都拥有自己的端口,从而消除所有的碰撞。作为一种妥协方案,每个端口上连接少量计算机还是可能的。

    2.因特网

    Internet包括了两类计算机,主机和路由器。主机有PC机,路由器是专用的交换计算机,它在许多进线中的一条线上接收进来的包,并在许多个出口线中的一条线傻姑娘按照其路径发送包。

    当一个包到达某个路由器使,该路由器抽取目的地地址并在一个表格进行查询,以找出用哪根出口线发送该包以及传送哪个路由器。路由表是高度动态的,并且随着路由器和链路维护,恢复以及通信条件的变坏在连续不断的更新。

    8.3.2 网络服务和协议

    1.网络服务

    计算机网络为使用网络的主机和进程提供服务。面向连接的服务是对电话系统的一种模仿,而无连接服务则是对邮政系统的一种模仿。

    可靠的,面向连接的服务有两种变种——消息序列和字节流

    不可靠的(意味着没有确认)无连接服务,常常称作是数据报服务。

    2. 网络协议

    用于特定计算机通信的这些规则的集合称为协议。

    所有的现代网络都使用所谓的协议栈把不同的协议一层层叠加起来。每一层解决不同的问题。

    大多数分布式系统都使用Internet 作为基础,因为这些系统使用的关键协议是IP和TCP协议。IP协议是数据报协议,发送者可以向网络上发出长达64kb的数据报并且网它们到达。TCP使用IO来提供面向连接的数据流。为了使用TCP,进程需要首先与一个远程进程建立连接。被请求的进程需要通过机器的IP地址和机器的端口号确定,而对进入的连接感兴趣的进程监听端口。这些工作完成之后,只需要把字节流放入连接。

    DNS作为一个数据库把主机的ASCII名称名称映射为对应的IP地址。

    8.3.4 基于文件系统的中间件

    分布式系统采用一个文件系统模型意味着只存在一个全局文件系统,全世界的用户都能够读写他们各自具有授权的文件。通过一个进程将数据写入文件而另一个进程把数据读出的办法可以实现通信。

    8.3.5 基于对象的中间件

    8.3.6 基于协作的中间件

    展开全文
  • 操作系统处理机调度算法

    千次阅读 多人点赞 2018-06-21 17:26:21
    道程序系统中,调度实际上是一种资源分配,即对处理机资源的分配;处理机调度算法是指根据处理机分配策略所规定的处理机分配方法; 处理机调度 处理机调度的层次 高级调度 高级调度又称为长程调度或者...

    处理机调度算法


    在多道程序系统中,调度实际上是一种资源分配,即对处理机资源的分配;处理机调度算法是指根据处理机分配策略所规定的处理机分配方法;

    处理机调度

    处理机调度的层次

    1. 高级调度

      高级调度又称为长程调度或者作业调度;其调度对象是作业;主要功能是根据调度算法决定从外存中的后备队列中选择哪几个作业调入内存,为它们创建进程、分配必要的资源,然后将其放入就绪队列。高级调度主要用于多道批处理系统中,在分时系统和实时系统中不设置高级调度;

    2. 低级调度

      低级调度又称为短程调度或者进程调度;其调度的对象是进程;主要功能是根据调度算法决定哪个进程可以获得处理机而运行,由分派程序将处理机分配给被选中的进程;进程调度是一种基本调度,多道批处理系统、分时系统和实时系统都需要设置这种调度;

    3. 中级调度

      中级调度又称为中程调度或者内存调度;其调度对象是进程;主要功能是将暂时不能运行的进程调至外存等待,此时进程即处于就绪驻外存状态(挂起状态);当它们具备运行条件而且内存空间又允许的时候,由中级调度来决定把处于外存上的那些具备运行条件的就绪进程再调入内存,修改其状态为就绪状态; 中级调度其实就是存储器管理中的对换功能。

    长程调度、中程调度以及短程调度是根据程序的运行频率和周期来划分的;长程调度运行频率最低,所以其周期较长;短程调度最为频繁,为避免调度本身占用过多CPU时间,其调度算法不能过于复杂,即运行周期最短;而中程调度不论运行频率还是运行周期都在两者之间;

    处理机调度算法的目标

    一般而言,一个操作系统采用什么样的调度方式和算法,取决于系统的类型以及设计目标;

    处理机调度算法的共同目标

    1. 资源利用率。为提高系统资源的利用率,应使系统中的处理机和其它所有资源都尽可能的处于忙碌状态;其中CPU的利用率可以使用该式计算:CPU的利用率=CPU的有效工作时间/(CPU有效工作时间+CPU空闲等待时间);
    2. 公平性。公平性是指应使各个进程都获得合理的CPU时间,不会发生进程饥饿现象;但是公平是相对的,即同一类进程应获得相同的服务,但是不同类的进程由于进程的紧急程度或者重要性不同,则应区别对待;
    3. 平衡性。系统中的资源多种多样,有的属于计算型作业,有的属于IO型,调度算法应使系统资源的使用保持平衡;
    4. 策略强制执行。对于所制定的策略,如安全策略,只要需要,就必须准确地执行;

    批处理系统的目标

    1. 平均周转周期短。作业的周转周期是指从作业提交给系统到作业完成为止这段时间;周转周期通常由四部分组成:作业在外存上后备队列中的等待时间、进程在就绪队列中的时间、执行时间和等待IO操作等阻塞的时间;

      对于用户而言,希望自己的作业周转周期尽可能地短;对于系统而言,希望作业的平均周转周期短,这样不但有利于提高系统资源的利用率也可以使大多数用户满意;总的来说,应使作业的周转周期和平均周转周期都较短;

      平均周转周期T=(所有作业的周转周期之和)/作业总数;

      为了进一步反映调度的性能,更清晰地描述进程在其周转时间中等待和执行时间的具体分配状况,通常使用加权周转时间W,即作业的周转时间T与系统为它提供服务的时间Ts之比:W=T/Ts;平均加权周转周期为各个作业的加权周转时间之和/作业总数;

    2. 系统吞吐量大。如果单纯为了提高系统的吞吐量,应尽量执行较短的作业运行;吞吐量被定义为单位时间里,系统完成的作业数;

    3. 处理机效率高。由于CPU十分昂贵,使得处理机的利用率成为衡量系统性能的重要指标;而调度方式和调度算法由对处理机的利用率起着十分重要的作用。如果单纯提高处理机效率,那么应选择计算量大的作业运行。

    分时系统的目标

    1. 响应时间快。响应时间快是分时系统中调度算法的重要准则,所谓响应时间由三部分组成:命令输入时间、CPU处理时间、命令结果返回时间;
    2. 均衡性。不同的用户对响应时间的要求不同,简单任务要求较短的响应时间,复杂的任务允许较长的响应时间,均衡性是指,系统的响应时间应该和用户所请求任务的复杂度相适应;

    实时系统的目标

    1. 对截止时间的保证。对实时系统而言,调度算法的一个主要目标就是保证实时任务对截止时间的要求;其中对HRT任务,需要调度方式和调度算法必须确保对截止时间的要求;对SRT任务,要求调度方式和调度算法基本可以保证对截止时间的要求;
    2. 可预测性。在实时系统中,可预测性十分重要,主要是通过可预测性提高系统的实时性;

    作业调度

    作业是比程序更加广泛的概念,其中包括程序、数据和作业说明书,系统根据作业说明书来对程序的运行进行控制;

    作业控制块(JCB)

    1. 引入作业控制块的目的:管理和调度作业,系统为每个作业设置一个作业控制块JCB,它是作业在系统中存在的标记;
    2. 作业控制块的内容:它保存了系统对作业进行管理和调度所需要的全部信息。这些内容有:作业标记、用户名称、用户账号、作业类型(CPU型繁忙型、IO型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、内存大小等)、资源的使用状况等;

    作业运行的三种状态

    1. 收容状态。操作员将作业输入到硬盘上,为其建立JCB,将其放入作业后备队列中,等待调度,此时的状态称为收容状态;此时作业在外存上;
    2. 运行状态。作业被调度算法选中,为其分配了所需要的资源并建立了进程,将其进程插入到就绪队列中。从作业第一次进入就绪队列开始到作业完成,作业均处于运行状态;
    3. 完成状态。当作业完成、或者发生异常情况而提前结束时,作业将进入完成状态,系统中的相应程序将回收分配的资源和JCB,并将作业运行的结果输出;

    作业调度的主要任务

    作业调度的主要任务就是根据JCB中的内容,检查系统资源情况是否满足作业的要求,并按照一定的调度算法,从外存的后备队列中选择某些作业调入内存,为它们创建进程、分配资源,然后将进程插入到就绪队列中等待调度;其实归根到底需要解决两个问题:

    1. 接纳多少个作业

      这是由系统的多道程序度(Degree of Multiprogramming)决定的,即允许多少个作业同时出现在内存中;对系统而言,当然希望装入较多的作业以提高CPU的利用率和系统的吞吐量,但是内存中的作业过于多时,由于内存不够而引发的中断就会急剧增加,从而影响系统效率和服务质量;因此,多道程序度是由计算机系统的规模、运行速度、作业大小、以及能否获得较好的系统性能等确定的;

    2. 接纳那些作业

      最简单的调度算法是先到先服务算法;较常见的一中调度算法是短作业优先算法;另一种常见的算法是基于作业优先级的调度算法;比较好的调度算法是响应比高者优先算法;

    值得注意的是,作业调度只有在多道批处理系统中才有;因为分时系统因为要保证较高的响应性,所以用户输入的命令和数据被直接送入内存;所以分时系统中需要考虑的是如何控制用户的数量,无需考虑长程调度问题。实时系统也是类似;

    先来先服务算法(FCFS,First-Come First-Served)

    FCFS调度算法中,优先选择先到的作业或者进程进行服务,或者说,它选择的是在队列中等待时间最长的作业或者进程,而没有考虑作业自身的情况,比如作业的优先级、作业的预计运行时间等;基本上FCFS算法很少作为系统的主调度算法,但经常把它和其他调度算法相结合使用。

    该调度算法既可以用于作业调度也可以用于进程调度(即适用于长程调度和短程调度);

    短作业优先调度算法(SJF,Short-Job First)

    短作业优先算法使用作业或者进程的长短来标记它们的优先级,越短的作业(进程)其优先级越高;

    短作业优先调度算法相比先来先服务算法有了明显的感改进(考虑了作业或者进程自身的相关信息),但是仍然有缺点:

    1. 必须预知作业的运行时间,这不是很容易做到,如果估计偏低,那么系统可能会提前终止作业,而作业此时尚未完成;所以一般都偏长估计;
    2. 对长作业非常不利,一个极端的现象就是长作业根本得不到运行,即系统中总是有比该作业更短的作业,从而出现饥饿现象;即便在普通情况下,长作业的周转周期也会明显增长;
    3. 无法实现人机交互(需要交互的程序得不到运行);
    4. 没有考虑作业的紧急程度,不能保证紧迫的作业得到及时的处理;

    该调度算法既可以用于作业调度也可以用于进程调度;

    优先级调度算法(PSA,Priority-Scheduling Algorithm)

    优先级调度算法中选择作业或者进程的标准是它们的优先级,优先级越高,越早获得调度而执行;其实FCFS中,作业或者进程的等待时间就相当于其优先级;SJF中,作业的长度就相当于其优先级;但是这种优先级并不能反映作业或者进程的紧急程度;PSA算法就是要保证紧迫性任务得到优先运行;

    该调度算法既可以用于作业调度也可以用于进程调度;

    高响应比优先调度算法(HRRN,Highest Response Radio Next)

    FCFS算法中,只考虑作业或者进程等待的时间;SJF算法中,只考虑了作业或者进程的运行时间;高响应比优先调度算法既考虑了等待时间也考虑了作业或者进程的要求时间;是一种动态优先级设定;其优先权计算公式:优先权=(要求服务的时间+等待时间)/要求服务的时间;这样,当两个作业或者进程等待了相同时间时,短作业将获的较大的优先级,类似SJF调度方式;当两个进程要求服务时间相同时,等待时间长的作业将获得较大的优先级,类似于FCFS调度方法;这种调度方法的问题就在于每次进行调度时需要进行响应比的计算,于是会增加一定的系统开销;

    进程调度

    进程调度的任务

    进程调度的主要任务有三:

    1. 保留处理机线程。将当前进程的处理机现场记录到PCB中,包括程序计数器、多个通用寄存器的内容;
    2. 按照某种算法选择下一个执行的进程。调度程序将从就绪队列中选择一个进程,改变其运行状态,将处理机分配给它;
    3. 将处理机分配给进程。由分派程序将处理机分配给该进程,此时需要将对应的PCB中的内容装入相应的寄存器内,让其从上一次中断的地方开始执行;

    进程调度机制

    为实现进程调度,进程调度机制中,应具有以下三个部分:排队器、分派器和上下文切换器;

    1. 排队器的主要任务是将就绪状态的进程组织为一个或多个队列,以便调度程序可以可以快速找到它;每当一个进程转入就绪状态,排队器就把它插入到相应的就绪队列;
    2. 分派器的主要任务是将调度程序所选择的进程从就绪队列中取出来,然后进行从分派器到新进程的上下文切换;
    3. 上下文切换器的主要任务是,在发生进程切换时,首先将当前进程的相关信息存储到对应的PCB中,然后装入分派程序;然后将分派程序的上下文移出,装入新进程的处理机信息;即一次进程切换中,发生了两次处理机上下文的切换;

    由于一次上下文切换中需要执行大量的load和store命令,所以比较费时,现代系统以实现靠硬件来减少上下文切换时间;当然也可以采用两组寄存器,其中一组寄存器供处理机在系统态时使用,另一组寄存器供应用程序使用。这样只需改变指针即可实现上下文的切换;

    进程调度的方式

    早期系统大多采用非抢占式调度方式,但是这很难满足交互性作业和实时任务的需求,后来在进程调度方式中又引入了抢占式调度方式;

    1. 非抢占式调度

      非抢占式调度方式中,一旦把处理机分配给某个进程,就让它一直运行下去,绝不会因为时钟中断或其他原因而抢占当前正在运行进程的处理机,直到该进程完成或者因某事件而阻塞,才将处理机分配给其他进程;非抢占方式中,引起进程调度的原因有:

      1. 正在执行的进程正常结束,或者因为某事件而无法继续执行;
      2. 正在执行的进程提出IO请求而暂停执行;
      3. 在进程同步和通信中,执行了某种原语操作,如挂起原语等;

      这种调度方法的特点是系统开销小,简单,适合大多数批处理系统,但是不能用于分时系统和实时系统;

    2. 抢占式调度

      抢占式调度中,允许调度程序按照某种原则,暂停某个正在执行的进程;将已分配给该进程的处理机分配给另一进程;现代OS中广泛采用抢占式调度,这是因为,抢占式调度方法可以防止一个长进程长时间占用CPU,以确保处理机能为各个进程提供更为公平的服务,另外在分时系统中,只有抢占式调度才能实现人-机交互。实时系统中,抢占式可以满足实时任务的要求。但是抢占式实现起来比较复杂,系统开销较大;

      抢占不是一种任意的行为,它必须遵守一定的规则:

      1. 优先权原则:只有优先级高的进程才能抢占优先级低的进程的处理机,反之不行;
      2. 短进程优先原则:当新来进程所要求的服务时间明显少于当前执行进程还需要执行的时间时,发生抢占;
      3. 时间片原则:各进程按时间片轮转执行时,当正在执行的进程的一个时间片用完后,便停止该进程的执行;

    进程调度算法

    1. 轮转调度算法(RR,Round Robin)

      分时系统中最简单也是最常用的算法;该方式采用非常公平的处理机分配方法,即采用FCFS策略组织就绪队列,让就绪队列中的每一个进程每次都运行一个时间片;这种方法中,进程的切换发生在:

      1. 若时间片尚未用完,正在执行的进程便已完成,就立即激活调度程序;将其从就绪队列中删除,从就绪队列中选择队首进程运行,同时启动一个新的时间片;
      2. 若时间片用完,计时器中断处理程序被激活;如果进程尚未运行完毕,就把它送入就绪队列的末尾,重新排队;

      时间片大小的选取对系统性能有着很大的影响;若选择小的时间片,那么短作业则可能在一次时间片中就结束运行,但是时间片过小,那么系统将频繁发生进程调度和处理机上下文切换,增加系统开销;反之,若时间片太长,则RR退化为FCFS,无法满足短作业和交互式作业的需求;一个可取的策略就是时间片大小应略大一一次交互所需要的时间,这样使大多数交互式作业可以在一个时间片里完成,从而获得较小的响应时间;

    2. 优先级调度算法

      优先级调度算法中,将处理机分配给就绪队列中优先级最高的进程。按照是否允许抢占,分为抢占式和非抢占式;

      1. 非抢占式优先级调度算法

        该算法中,一旦将处理机分配给就绪队列中优先级最高的进城后,该进程便一直执行下去,直到结束(正常结束或者被阻塞、挂起等)才将处理机分配给就绪队列中另一优先级最高的进程;

      2. 抢占式优先级调度算法

        该算法中,把处理机分配给优先级最高的进程,使之执行,但是如果在其执行期间出现优先级更高的进程,调度程序就将处理机分配给新的优先级最高的进程;抢占式优先级调度算法常用于对实时性要求较高的系统中;

      优先级的类型——静态优先级和动态优先级:

      1. 静态优先级在创建进程的时候就已经设定,其运行周期内不再改变;常使用0-255中的一个整数来表示其优先级大小;设定静态优先级时需要考虑进程的类型,通常系统进程的优先级高于用户进程的优先级;进程对于资源的需求量,一般来说,需求量小的具有较高的优先级;用户的要求;静态优先级实现较为简单,系统开销小,但是不够精确,可能出现优先级低的进程长时间得不到运行的情况;
      2. 动态优先级是指进程的优先级会随着其运行发生改变,常见的需要考虑的变量有进程的初始优先级和等待时间等;
    3. 多队列调度算法

      多列调度算法中,将就绪队列组织为多个按照不同调度算法调度的就绪队列,以满足不同用户对调度策略的不同要求,并且这些就绪队列本身也可以设定优先级,方便在多处理机系统中为每个处理机设置一个单独的就绪队列;避免了仅有一个就绪队列时调度算法的固定、单一。这样对于含有多个线程的进程,可以将这些线程分配在一个就绪队列中,全部在一个处理机上运行;对于一组需要相互合作的进程而言,可以将其安排在一组处理机所对应的多个就绪队列中,使它们可以同时获得处理机并发执行;

    4. 多级反馈队列调度算法(Multileved feedback queue)

      前面介绍的进程调度算法,或多或少都有一定的局限性,如果未能指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。多级反馈队列不用提前知道各种进程的执行时间,还可以较好地满足各种类型进程的需要,是目前公认的一种较好地进程调度算法;它的核心为

      1. 设置多个就绪队列;系统中设置多个就绪队列,并且每个就绪队列也有自己的优先级。第一个队列的优先级最高,以此降低;该算法为每个队列中的进程所分配的时间片大小也是不同的,优先级越高的队列,其所分配的时间片越小(便于进程向低优先级转移);
      2. 每个队列都采用FCFS算法。当新进程进入内存时,将其放入第一队列的末尾,然后按照FCFS等待调度;如果该进程在时间片内完成,便撤离系统;否则进入第二队列末尾等待调度;当进程进入最后一个队列时,便采用RR方式运行;
      3. 按照队列优先级调度。调度程序首先调度最高优先级队列中的进程运行,仅当第一队列空闲时才调度第二队列中的进程;如果处理机正在第x队列中为某进程服务时,有新进程进入任意优先级较高的队列,那么该进程立即被送回第x队列末尾,将处理机交给新到的高优先级进程;

      多级反馈队列中,可以使短作业较早的完成,而且长作业经过第1,2,3…队列的执行,到最后一个队列时,采用RR调度算法,也不用担心过其作业长期得不到处理;

    5. 基于公平原则调度算法

      以上几种调度算法,保证了优先运行,但是并不能保证作业占用多少处理时间。另外也没有考虑调度的公平性;这里有两种相对公平的调度算法

      1. 保证调度算法,它向用户所做出的保证不是优先运行而是明确的性能保证,一种比较容易实现的性能保证算法是处理机分配的公平。如果系统中有n个进程,那么需要保证每个进程都获得相同的处理机时间1/n;实施公平调度算法时,系统需要:

        1. 跟踪计算每个进程自创建以来已执行的时间;
        2. 计算每个进程应该获得的处理机时间;
        3. 计算进程获得处理机时间的比率;
        4. 比较各个进程的这个比率,然后选择最小的进程,将处理机分配给它,并让该进程一直运行下去,直到超过最接近它的进程比率为止;
      2. 公平分享调度算法

        公平的角度不同,所使用的算法也就不同;保证调度算法对进程是公平的,但是对用户就不一定:有的用户拥有的进程多,有的用户拥有的进程少。公平分享算法是用户层面的公平调度算法。

    实时调度

    实时系统中存在两类不同的任务:硬实时任务和软实时任务;它们都关联着一个截止时间;实时调度算法必须能够满足实时任务对截止时间的要求;所以实时调度算法有一定的条件。

    实现实时调度的基本条件

    1. 提供必要的信息:系统应向调度程序提供有关任务的信息
      1. 就绪时间:某项任务进入就绪队列的时间;
      2. 开始截止时间和完成截止时间;
      3. 处理时间,从开始执行到结束需要的时间;
      4. 优先级,如果某项任务开始截止时间的错过将势必引起故障,那么将赋予该任务绝对的优先级;如果其开始截止时间的错过,对任务的继续运行没有重大影响,那么可以赋予该任务相对的优先级;
      5. 资源要求;
    2. 系统的处理能力强。如果系统的处理能力不够,那么很有可能因处理机忙不过来而导致一些实时任务得不到执行;提高系统处理能力有两种途径:一是使用单处理机系统,但是需增强其处理能力,以显著降低对每一个任务的处理时间;二是采用多处理机系统。
    3. 采用抢占式调度机制。广泛采用抢占式机制,可以满足HRT任务对截止时间的要求;但是这种调度机制实现比较复杂,对于一些小的实时系统,如果能预知任务的开始截止时间,则对实时任务的调度可以采用非抢占式调度机制,以降低调度程序和任务调度是所花费的系统开销;如果采用非抢占式调度机制,应使每个实时任务都比较小,以便能及时将自己阻塞起来,以便释放处理机;
    4. 具有快速切换机制。一是对中断的快速响应能力,对紧迫的外部事件请求中断能及时响应,要求系统具有快速硬件中断机制,还应使禁止中断的时间间隔尽量短,以避免耽误其他紧迫任务;二是快速的任务分派能力,为了提高分派程序进行任务切换的能力,应使系统中的每个运行功能单元适当的小,以减少任务切换的时间花销;

    实时调度算法的分类

    按照任务类型可以分为:硬实时任务调度算法和软实时任务调度算法;按照调度方式可以分为:抢占式调度算法和非抢占式调度算法;

    1. 非抢占式调度算法
      1. 非抢占式轮转调度算法:将实时任务组织为一个轮转队列,调度程序每次选择队列中的第一个任务投入运行,当该任务运行完毕后即将其放入轮转队列末尾等待。这种调度算法可以获得数秒到数十秒的响应时间,可用于不太严格的实时控制系统;
      2. 非抢占式优先调度算法:即使用优先权组织轮转队列;这种调度算法经过精心处理后,可以获得数秒到数百毫秒的响应时间,可用于有一定要求的实时控制系统;
    2. 抢占式调度算法
      1. 基于时钟中断的抢占式调度算法。在某实时任务到达时,如果它的优先级高于当前任务的优先级,这是并不立即抢占当前任务的处理机,而是等待时钟中断发生时,调度程序才剥夺当前任务的执行;这种算法可以获得较好的响应效果,其调度延迟可以降低到几十到几毫秒,可用于大多数实时任务系统中;
      2. 立即抢占的优先级调度算法。在这种调度策略中,要求操作系统有较高的快速响应外部事件中断的能力;一旦出现外部中断,只要当前任务没有处于临界区便立即剥夺当前任务的执行。这种调度算法可以获得非常快的响应,可把调度延迟减低到几毫秒到几百微秒;

    最早截止时间优先算法(Earliest Deadline First)

    该调度算法中,根据任务的截止时间确定任务的优先级,任务截止时间越早,优先级越大;具有最早截止时间的任务排在队列队首;调度程序选择任务时,直接选择就绪队列中的第一个即可;按照非抢占式和抢占式可以分为:抢占式最早截止时间优先和非抢占式最早截止时间优先这两种。非抢占式算法是指在某个任务执行的过程中,如果新到的任务的截止时间早于正在执行的任务的截止时间,并不会发生抢占;而抢占式则相反,会立即将处理机分配给优先级大的任务;通常而言,非抢占式常用于非周期性任务;抢占式常用于周期性任务;

    最低松弛度优先算法(Least Laxity First)

    该调度算法中,根据任务的紧急程度来确定任务的优先级,越紧急的任务,其优先级越大;而越紧急也意味着它的松弛度越低;在该算法中,任务的松弛度由任务的完成截止时间减去任务要求的处理时间来确定;该算法通常用于可抢占方式中;一般来说,抢占发生在某一任务的最低松弛度为0的时候,即该任务不得不执行,而考虑到任务切换的时间,通常还会提前一点;所以调度发生的情况为:某一任务正常结束或者某一任务的最低松弛度变为0;

    优先级倒置现象及其解决方法

    由于进城之间存在两种约束(直接约束和间接约束),所以有可能出现具有高优先级的进程因低优先级的进程而阻塞的情况;这种情况被称为优先级倒置;比如,低优先级A首先获得了临界资源R(因为比它高级的进程还没到),然后有比它优先级高的进程B到来,A被剥夺处理机,但是临界资源并没有被释放,之后用于最高优先级的进程C到来,B被抢占处理机,而C由于请求临界资源R失败而阻塞(进入阻塞队列),之后B开始运行,结束后A再运行临界区代码,进程A释放临界资源R后,C才能执行。这样B进程比C进程优先级低,但是先得到处理;常见的解决方法有两种:一是当进程处于临界区的时候,不允许中断,这样A执行完毕后,因为C的优先级高,处于就绪队列的前面,所以C可以在B之前执行;但是当A的临界区非常长,则C还是要等待较长时间;另一种办法是建立在动态优先级继承基础上的,该方法规定,当优先级较高的进程要进入临界区,使用临界资源,如果有一个低优先级进程正在使用该资源,那么高优先级进城被阻塞,而低优先级进程将继承高优先级进程的优先级,直到低进程退出临界区;这样就可以避免低进程被中等进程阻塞而出现优先级倒置现象;

    展开全文
  • 操作系统8————处理机调度

    千次阅读 2019-02-02 17:29:01
    操作系统8————处理机调度 一. 目录 二. 处理机调度的层次 在道程序系统中,调度实质是一种资源分配,处理就调度算法是指根据处理机分配策略所规定的处理机分配算法。一个作业从获得处理机...

    操作系统8————处理机调度

    一. 目录

    二. 处理机调度的层次

    在多道程序系统中,调度实质是一种资源分配,处理就调度算法是指根据处理机分配策略所规定的处理机分配算法。一个作业从获得处理机执行到作业运行完毕,可能会经历多级处理机调度。下面介绍处理机的层次。

    1.高级调度

    高级调度又称为长程调度或者作业调度,它的调度对象是作业。主要功能是根据某种算法,决定将外存上处于后备队列中那几个作业调入内存,为它们创建进程,分配必要的资源,并将它们放入就绪队列。高级调度主要用于多道批处理系统,而在分时和实时系统中不设置高级调度。作用调度的频率很低,周期很长,大于几分钟一次。

    2.低级调度

    低级调度有称进程调度或者短程调度,它的调度对象是进程。其主要功能是,根据某种算法,决定就绪队列中的那个进程获得处理机。并由分派程序将处理机分派给选择的进程。进程调度这是一种最基本的调度,在多道批处理,实时和分时三种类型的OS中,都必须配置这级调度。进程调度的频率很高,周期很短,在分时系统中大概仅10~100nm.

    3.中级调度

    中机调度又称为内存调度,引入中级调度的主要目的是,提高内存利用率和系统吞吐量。中级调度的作用就是讲暂时不能运行的进程,调至外存等待(挂起转台),和将外存上已经满足条件的就绪进程在调入内存中。内存调度的频率和周期处于,作业调度和内存调度之间。

    三. 处理机调度的目标

    1.处理机调度算法的共同目标

    a.资源利用率:为了提高资源的利用率,应使系统中的处理机和其他所有资源尽可能保持忙碌状态。

    **b.公平性:**公平性是指应使诸进程都获得合理的CPU时间,不会发生进程饥饿现象。但公平是相对的,对于相同类型的进程应获得相同的服务,对于不同类型的进程,由于其紧急程度和重要性不同,提供不同的服务。

    **c.平衡性:**为使系统中CPU和各种外部设备都能经常处于忙碌状态,调度算法应保存系统资源使用的平衡性。

    d.策略强制执行: 对所指定的策略其中也包括安全策略,只要需要,就必须提供。

    2.批处理系统的目标

    a.平均周转时间短:

    • 周转时间是指,从作业被提交给系统开始,到作业完成时间这段时间的间隔。它包括:作业在外存后备队列上等待调度的时间,进程在就绪队列等待的调度的时间,进程在cpu上执行的时间,以及进程等待I/O操作完成的时间。
    • 平均周转时间:$T = \frac{1}{n}[ \sum_{i=1} ^ {n} T_i] $
    • 平均带权周转时间:带权周转时间,即作业周转时间 T i T_i Ti与系统提供服务的时间 T s T_s Ts时间之比。平均带权周转时间$W = \frac{1}{n}[ \sum_{i=1} ^ {n} \frac{T_i}{T_s}] $

    b.系统吞吐量高: 吞吐量是指单位时间内系统完成的作业数,如果单纯为了获得高的系统吞吐量,那么就应该尽可能选择短作业运行。
    c.处理机利用率高: 如果单纯为获得处理机利用率高,那么应该尽可能选择长作业运行。

    3.分时系统的目标

    a.相应时间快: 响应时间是指,是从用户通过键盘提交一个请求开始,直到屏幕上显示处理结果为止那一段时间。
    b.均衡性: 用户对于响应时间的要求并非完全相同,用户对于简单的任务要求响应时间短,复杂任务时间允许较长。

    4. 实时系统

    **a.截止时间的保证:**截止时间是指:某任务必须开始执行的最迟时间,或者必须完成的最初时间。对于严格的实时系统,其调度方式和调度算法必须要保证这一点。
    **b. 可预测性:**在实时系统中,这一点非常重要,。

    四. 作业

    1. 作业

    作业(Job): 作业是一个比系统更广泛的概念,它不仅包含了通常的程序和数据,而且还应配有一份作业说明书,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存。

    2. 作业步

    作业步(Job Step):在作业运行期间,每个作业都必须经过若干相互独立又相互关联的顺序加工步骤才能得到结果。我们把其中每一步称为一个作业步。例如,一个典型的作业步可以分为:“编译”作业步,“链接装配”作业步,和“运行”作业步。

    3. 作业控制块(JCB)

    和进程线程类似,作业中也包含一个作业控制块(JCB)。通常JCB包含:作业标识,用户名称,用户账号,作业类型,作业专业,调度信息,资源需求,资源使用情况。

    4. 作业运行的阶段和状态

    作业从进入系统到运行,通常要经历收容,运行和完成阶段,相应的也就有了“收容状态” “运行状态” “完成状态”。

    a.收容状态: 操作员把用户提交的作业通过某种方式或SPOOLing系统输入到硬盘上,在为该作业建立JCB,并把它放入作业后备对列中。

    **b.运行状态:**当作业被作业调度选中后,边为它分配必要的资源和建立进程,并把他放入就绪队列。

    c.完成状态: 当作业运行完成,或发生异常情况而提前结束时,作业便进入了完成阶段。

    五. 作业调度

    1. 作业调度的目标

    作业调度的主要任务就是根据JCB中的信息,检查系统中的资源能否满足作业队资源的要求,以及按照一定的调度算法,从外存的后备对列选取某些作业调入内存。在每次执行作业调度时,都需要做出以下两个决定:
    **a.接纳多少个作业:**接纳多少作业取决于多道程序度。而多道程序度取决于:计算机系统规模,运行速度,作业大小,以及能否获得较好的系统性能.
    b.接纳哪些作业: 选择哪些作业取决于,作业调度采用哪种算法,常见的算法如下

    2. 先来先服务(FCFS)

    先来先服务算法,既可以用于作业调度,也可以用于进程调度。当作业调度中采取该算法时,系统将按照作业到达的先后次序来进行调度。

    在系统调度中采用FCFS算法时,每次调度是从就绪的进程队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或者阻塞时,进程调度程序才会将处理机分配给其他进程。

    FCFS算法在单处理机系统中以及很少作为主调度算法,但经常把它和其他调度算法结合使用,形成一种更为有效的调度算法。例如,可以在系统中按进程的优先级设置多个队列,每一个优先级一个队列,其中每一个队列的调度都基于FCFS。

    3. 短作业优先(SJF)

    SJF算法是以作业的短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的时间来衡量的。SJF也可以分别用于作业调度和进程调度。但用于进程调度时优于作业调度。

    缺点:
    SJF相比FCFS算法,有很大的改进,但依然有以下缺点

    • 必须知道作业的运行时间
    • 对于长作业非常不利,很可能出现饥饿现象。
    • 无法进行人机
    • 没有考虑作的紧迫程度,不能保证紧迫性的作用能够得到及时的处理。

    4. 优先级调度算法(PSA)

    优先级调度算法也是既可以用于作业调度,也可以用于进程调度。FSFC和SJF算法都无法使紧迫性的作业得到尽快的处理,而PSA正是基于作业的紧迫程度,由外部赋予的作业优先级,进行作业调度。

    5. 高响应比优先算法(HRRN)

    FSFC算法值考虑的作业的等待时间,SJF只考虑的作业的需要运行时间。而HRRN则既考虑了作业的等待时间,又考虑的作业的紧迫时间,从而改善了处理机调度的性能。

    HRRN为每一个作业引入了一个动态优先权。该优先权的变化规律如下:
    优 先 权 = 等 待 时 间 + 要 求 服 务 的 时 间 要 求 服 务 的 时 间 优先权= \frac{等待时间+要求服务的时间}{要求服务的时间} =+

    同时等待时间+要求服务的时间 = 相应时间。所以优先权也可以表示为
    优 先 权 = R p = 响 应 时 间 要 求 服 务 的 时 间 优先权=R_p= \frac{响应时间}{要求服务的时间} =Rp=

    从上式可以看出

    • 如果作业的等待时间相同,这要求服务的时间越短,则优先权越大。此时类似于SJF算法。
    • 当要求服务的时间相同时,作业的优先权又决定于其等待时间。此时类似于FCFS算法。
    • 对于长作业的优先权,可以随等待时间的增加而提高。当其等待时间足够长,也可以获得处理机。避免出现饥饿现象。

    六. 进程调度

    1. 进程调度的任务

    进程调度的任务有以下几点

    • 保存处理机的现场信息。
    • 按照某种算法选取线程。
    • 把处理机分配给进程。

    2. 进程调度的机制

    为了实现进程调度,在进程调度中应该有以下三个部分:
    这里写图片描述

    • 排队器:为了提高进程调度的效率。应事先将系统中的所有就绪进程按照一定策略排成一个或多个队列,以便调度程序能最快的找到它。以后每当有一个进程转换为就绪状态时,排队器便把它插入到相应的就绪队列中。
    • 分派器:分派器依据调度程序所选定的进程,将其从就绪队列取出,然后进行从分派器到新选的进程间的上下文切换,将处理机分配给新选出的进程。
    • 上下文切换器:在对处理机进行切换时,会发生两对上下文的切换操作。①第一对上下文切换时,OS保存当前进程的上下文,即把当前进程的处理机寄存器内部保存到该进程的PCB中,再装入分派程序的上下文。以便分派程序运行。②第二对上下文切换是移出分派程序的上下文。把新选进程的CPU现场信息装入到处理机的各个相应寄存器中,以便新选进程运行。

    3. 进程调度方法

    进程调度的方法大概分为非抢占式和抢占式。
    a.非抢占式
    采用这种调度方式时,一旦把处理机分配给某进程后,就一直让他运行下去,绝不会因为时钟中断或者其他原因抢占当前处理机,直到该进程完成或者阻塞,才把处理机分配给其他进程。这种方式的好处就是实现简单,系统开销小,适用于大部分法批处理系统。但是无法适应于分时系统和大部分的实数系统。

    这种方式下,会引起调度的原因:

    • 正在执行的进程执行完毕,或者因为某些事无法继续执行。
    • 执行的进程提出I/O请求,而暂停执行
    • 在进程通信或者同步过程中,执行了某种原语操作,比如Block原语。

    b. 抢占式
    这种调度方式允调度程序根据某种原则,去暂停某个正在执行的进程,将已经分给该进程的处理机重新分给另一进程。广泛采用抢占式,是因为对于批处理系统,可以防止一个长进程长时间的占用处理机,以确保处理机能够为所有进程提供更为公平的服务。 在分时系统中,只有采用抢占式才能实现人机交互,在实时系统中,抢占式能满足实时任务的要求。但同时抢占式比较复杂,所需要的系统开销也比较大。

    “抢占式”抢占时也需要按照一定的原则,主要原则有:

    • 优先权原则,指允许优先级高的新到进程抢占当前长进程的处理机,即新进进程到达时,如果他的优先度比正在执行的进程优先度高,则调度程序剥夺当前进程的处理机。
    • 短进程优先,指允许新到的短进程抢占当前的长进程的处理机,即新进 进程到达时,如果他的比正在执行的(尚需运行)时间明显短,则调度程序剥夺当前进程的处理机。
    • 时间片原则, 即各进程按时间片轮转运行时,当正在执行的进程的一个时间片段用完后,变停止该进程的执行,而重新进行调度。

    4. 轮转调度算法(RR)

    在分时系统中,最简单也是教常用的是基于时间片的轮转算法(RR).该算法采用了非常公平的处理机分配方法,即让每个进程每次仅运行一个时间片。如果就绪队列上有n个进程,则每个进程大约获得1/n的处理机时间。

    a.轮转法的基本原理
    在RR中,系统将所有的就绪进程按照FCFS策略排成一个就绪队列,系统可设置每个一定时间便产生一次中断, 去激活进程调度进行激活,把CPU分配队首进程,并令其执行一个时间片。运行完毕后,又把处理机分配给就绪队列的新的队首。
    b.进程切换时机
    在RR算法中,切换时机有两种情况:

    • 若一个时间片未用完,正在运行的进程便已完成,就立即激活调度进程,将它从就绪队列删除,调度就绪队列的队首进程。
    • 在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完成,调度程序将它送往就绪队列的末尾。
      c.时间片大小的确定
      在RR算法中,时间片的大小对西邮有很大影响

    下图是时间片略大于典型交互的时间
    这里写图片描述
    下图是时间片小于典型交互的时间
    这里写图片描述
    下图是时间片分别为q=1和q=4对于平均周转时间的影响
    这里写图片描述

    5. 优先级调度算法

    a.优先级调度算法的类型
    优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程。同时又可以进一步把该算法分为:

    • 非抢占式优先级调度算法
    • 抢占式优先级调度算法

    b.优先级类型

    • 静态优先级。静态优先级是在创建进程时确定,在进程的整个运行时间不变,优先级的大小确定的依据有:①进程类型②进程对资源的需求。③用户要求
    • 动态优先级。动态优先级是指在进程创建之初,先赋予其一个优先级,然后其值随进程的推进或者等待时间的增加而改变,以获得更好的调度性能。

    6. 多队列调度算法

    之前所述的各种调度算法,在应用于进程调度时,由于系统中仅设置一个进程的就绪队列,即低级调度的算法是单一的,固定的,无法满足系统中不同用户对进程调度策略的不同要求,在多处理机系统中,这种单一调度策略实现机制缺点更加明显。因此多级队列算法能够在一定程度上弥补这一缺点。

    多级队列算法将进程就绪队列拆分成若干个,不同的就绪队列采用不同的调度算算法,所以可以很好的满足不同用户对进程调度策略的不同需求,同时也可以满足多处理机系统的需求。

    7. 多级反馈队列调度算法

    多级反馈队列不同与之前的调度算法,他可以不需确定各进程运行的时间,还可以较好的满足各种类型进程的需求。
    调度机制
    多级反馈进程调度算法机制可以描述如下

    • 设置多个就绪队列,如下图
      这里写图片描述
    • 每个队列都采用FCFS算法,当新进程进入内存后,首先将它放在第一队列末尾,按照FCFS原则等待调度,当轮到该进程执行时,如果能在该时间片内完成,便可撤离系统。否则,调度程序便把他转入第二队列末尾等待。如果他在第二队列运行一个时间片认为完成,在一次放入第三队列…以此类推。当进程最后被降到第n队列后,在第n队列中便采用RR方式运行。
    • 安照队列优先级调度,调度程序首先调度最高优先级队列中的诸进程,仅当第一队列空闲时才调度第二队列中的进程运行。换而言之,仅当第1~(i-1)队列均为空时,才会调度第i队列中的进程运行,如果处理机正在为第i队列中的某进程服务时,有新进程进入较高级的队列,此时必须把正在运行的进程放回第i队列的末尾,而把处理机分配给新到的高优先级队列。

    8. 保证调度算法

    保证调度算法是另一种类型的调度算法,它想用户所作出的保证并不是优先运行,而是明确的性能保证,该算法可以做到调度的公平性。一种比较容易的性能保证是处理机的公平性,如果在系统中有n个类型相同的进程同时运行,为了公平期间,每个进程都获得相同的处理机时间1/n。

    在实施保证调度算法时,系统必须具备这样一些功能:

    • 跟踪计算每个进程自创建以来已经执行的处理时间。
    • 计算每个进程应获得的处理机时间,即自创建以来的时间除以n。
    • 计算进程获得处理机时间的比率,即进程实际执行的处理时间和应获得的处理机时间之比。
    • 比较各进程获得处理机时间的比率。如进程A的比率最低,为0.5,而进程B的比率为0.8,进程C的比率为1.2等。
    • 调度程序应选择比率最小的进程将处理机分配给它,并让该进程一直运行,直到超过最接近它的进程比率为止。

    9. 公平分享调度算法

    分配给每个进程相同的处理机时间,显然,这对诸进程而言,是体现了一定程度的公平,但如果各个用户所拥有的进程数不同,就会发生对用户的不公平问题。 在该算法中,调度的公平性是体针对于用户而言。使所有的用户获得相同的处理机时间,或要求的时间比例。

    七. 实时调度

    · 在实时系统中,可能存在着两类不同性质的实时任务,即HRT任务和SRT任务,它们都联系着一个截止时间。为保证系统能正常工作,实时调度必须能满足实时任务对截止时间的要求。为此,实现实时调度应具备一定的条件。

    1. 实现实时调度的基本条件

    a.提供必要的信息
    为了实现实时调度,系统应向调度程序提供以下信息:

    • 就绪时间,是指任务成为就绪状态的起始时间。
    • 开始截至时间和完成截至时间
    • 处理时间,即一个任务从开始执行到完成所需要的程序
    • 资源要求,任务执行是所需要的一组
    • 优先级,如果某任务的开始指向截至时间错过,势必引起故障,则应为该任务赋予“绝对”的优先级;如果其开始截至时间的错过,对任务的继续运行无重大影响,则赋予“相当”优先级。

    b.系统处理能力强
    在实时系统中,若处理机的处理能力不够强,则有可能因处理机忙不过,而致使某些实时任务不能得到及时处理,从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务HRT,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件系统才是可调度的:
    ∑ i = 1 n C i P i ≤ 1 \sum_{i=1} ^ {n} \frac{C_i}{P_i} \leq 1 i=1nPiCi1

    提高系统处理能力的途径有二:一是采用单处理机系统,但须增强其处理能力,以显著地减少对每一个任务的处理时间;二是采用多处理机系统。假定系统中的处理机数为N,则应将上述的限制条件改为:
    ∑ i = 1 n C i P i ≤ N \sum_{i=1} ^ {n} \frac{C_i}{P_i} \leq N i=1nPiCiN

    c.采用抢占式调度机制
      在含有HRT任务的实时系统中,广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统,如果能够预知任务法开始截止时间,则对于实时任务的调度可以采用非抢占式调度。
    d.具有快速切换的机制
    为保证硬实时任务能及时运行,在系统中还应具有快速切换机制,使之能进行任务的快速切换。该机制应具有如下两方面的能力:

    • 对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务)。
    • 快速的任务分派能力。为了提高分派程序进行任务切换时的速度,应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销。

    2. 实时调度算法的分类

    实时调度算法按照调度方式可分为:
    a.抢占式

    • 非抢占式轮转调度算法(同上)
    • 非抢占式调度优先算法(同上)

    b.非抢占式
    可根据抢占发生时间的不同而进一步分成以下两种调度算法:

    • 基于时钟中断的抢占式优先级调度算法。
    • 立即抢占(Immediate Preemption)的优先级调度算法。
      这里写图片描述

    3. 最早截止时间优先算法(EDF)

    该算法是根据任务的截止时间确定任务的优先级,任务的截止时间越早,其优先级越高,具有最高优先级的排在队首。EDF既可以用于抢占式也可以用于非抢占式。

    a.非抢占式调度方法用于非周期实时任务
    这里写图片描述

    b.抢占式用于周期实时任务
    下图有两个周期任务,任务A和任务B的周期时间分别为20 ms和50 ms,每个周期的处理时间分别为10 ms和25 ms。
    这里写图片描述

    4. 最低松弛度优先算法(LLF)

    该算法在确定任务的优先级时,根据的是任务的紧急(或松弛)程度。任务紧急程度愈高,赋予该任务的优先级就愈高,以使之优先执行。 该方式主要用可抢占式调度。

    假如在一个实时系统中有两个周期性实时任务A和B,任务A要求每20 ms执行一次,执行时间为10 ms,任务B要求每50 ms执行一次,执行时间为25 ms。由此可知,任务A和B每次必须完成的时间分别为:A1、A2、A3、…和B1、B2、B3、…,如下图
    这里写图片描述

    利用ELLF算法进行调度的情况:
    这里写图片描述

    5. 优先级倒置

    a.优先级倒置是什么
    系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象,即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。

    b.优先级倒置的解决
    一种较简单的解决方法就是,规定进程进入临界区后,该进程占用的处理机不允许被抢占

    另一个比较实用的方法建立在动态优先级基础的基础上:该方法规定,当高优先级进程要进入临界区时,去使用临界资源R时,如果已有一个低优先级进程正在使用该资源。此时高优先进程被阻塞,另一方面低优先级进程继承高优先进程的优先级,直到低优先进程退出临界区。

    八. 参考资料

    《操作系统第四版》

    展开全文
  • 操作系统处理机管理

    千次阅读 2017-03-14 09:37:58
    处理机管理可归结为对进程的管理。 为什么需要进程?  在单道程序系统中,程序只能够顺序的执行,即两个程序只能等一个执行完再执行下一个。这样就使程序的执行具有三个特型:顺序性、封闭性和可再现性。而到了...

    处理机管理可归结为对进程的管理。

    为什么需要进程?

             在单道程序系统中,程序只能够顺序的执行,即两个程序只能等一个执行完再执行下一个。这样就使程序的执行具有三个特型:顺序性、封闭性和可再现性。而到了多道程序系统中,允许程序并发的执行(宏观并行,微观串行)。此时程序并发执行就具有了:间断性、失去封闭性和不可再现性。为了解决程序并发执行的问题,并且可以对并发执行的程序加以描述和控制,人们就引入了进程的概念。

    什么是进程?

             进程是程序的一次执行,是资源分配和调度的基本单位。进程 = 程序 + 数据 + 程序控制块(Process Control Block,PCB)。

             PCB是进程最重要的数据结构,是进程存在的唯一标识。PCB中记录了系统所需的,用于描述进程的当前情况一起管理进程运行的全部信息。OS通过PCB就能够很好的控制进程。PCB中的记录的内容大致为:进程标识符、处理机状态、进程调度信息、进程控制信息。

             进程的管理下面几个方面:

    • 进程控制
    • 进程同步
    • 进程通信
    • 进程调度      

    进程的状态

            就绪状态——进程所需要的资源都已经到位,只需要等待处理机调度

            运行状态——进程获得处理机,正在执行

            阻塞状态——进程等待某些事件的发生才能继续执行,所以不再占用处理机而转为阻塞状态

            进程的三态图和五态图如下:

                         

    进程控制

            进程的控制主要包括创建进程、撤销进程以及进程的状态转换。进程控制一般有OS的内核通过原语来实现。

            内核(Kernel):一些常驻内存,存在于紧靠硬件的软件层次中的模块的集合。例如中断处理程序、常用设备驱动程序及运行频率较高的模块(时钟管理、进程调度这些)。

            内核一般都包含了支撑功能(中断处理、时钟管理和原语操作)以及资源管理功能(进程、存储器和设备的管理)。

           原语——由若干条指令组成的,用于完成一定功能的一个过程。或者说是系统态下执行的某些具有特定功能的程序段。原语操作是一种“原子操作”,就是不可分的意思。即一个操作中的所有动作要么全做,要么全不做。

           阻塞和唤醒的原语分别是 block 和 wakeup。挂机和激活的原语是 suspend 和 active 。

    进程同步

          进程同步机制的主要任务,是对多个相关进程在执行次序上进行协调,是并发执行的进程能按一定的规则(或时序)共享系统资源,并能很好的相互合作,从而使程序的执行具有可再现性。

          进程之间的制约:

    •  直接制约——共享缓冲区   同步
    •  间接制约——互斥资源   互斥

          临界区:进程中访问临界资源的代码。

          进程必须互斥地进入自己的临界区,系统为此设置了专门的同步机构来协调。同步机制需要遵循十六字真言:空闲让进、忙则等待、有限等待、让权等待。

          1965年Dijkstra提出信号量(Semaphores)机制是一种卓有成效的进程同步工具,这个机制有几种发展产物。我们通常使用记录型信号量。

          记录型信号量只是在整形信号量的基础上增加了将进程阻塞和唤醒的操作,这样符合“让权等待”的规则。

          信号量S是一个表示资源数目的东西,只有在wait(S)和signal(S)这两个原子操作中才能够修改,这就保护了信号量不被其它地方随意改变。这两个操作又称为PV操作。

          P操作就相当于在访问资源之前,先对代表该资源的信号量进行判断,如果有就访问,没有的话该进程就被阻塞等待。

          V操作就是在访问资源之后,释放一个资源,并唤醒一个等待该资源的进程。


    信号量机制实现前驱图也经常考到,但很简单。对于前驱图中一个结点,有多少个箭头指向它,则在执行本身程序之前必须先进行多少次 P 操作来等待所有资源。有多少个箭头从它指出去,在本身程序执行后就要进行多少次 V 操作释放资源。

    信号量机制实现互斥:

          为临界资源设置一互斥信号量mutex,初始值为1。每个进程在进入临界区之前都要对该信号量进行P操作,判断mutex的值,如果为1则表示没有其它进程正在访问该资源,现在可以访问;如果为0则表示当前有进程在访问该资源必须等待。这就相当于用一个标识符给临界区上了锁,实现了互斥访问。

    信号量机制实现同步:

          两个进程共享缓冲池,想象生产者和消费者的问题。设缓冲池具有的可用空间为n,要为该缓冲池设置3个信号量,一个是互斥访问信号量S,初始值为1。一个是S1,初始值为n,表示缓冲池可用空间数。另一个是S2,初始值为0,表示缓冲池中已满空间数(相当于已有产品数)。在这个条件下:

         对于生产者进程,在将产品放入到缓冲池(访问)之前必须先对 S1 进行 P操作,判断 S1 的值,如果不为0,就对 S 执行 P操作,判断该缓冲区中是否有其它进程正在访问。如果为 0,则表示该缓冲区已满不能再放产品,生产者进程只能等待。只有这两个 P操作都通过了,生产者才能将产品放入缓冲池。然后对 S 进行 V操作,释放访问,再对 S2(是S2,不是S1,因为放了一个产品是要给S2加1)进行 V操作。

         对于消费者进程,在从缓冲池拿出产品(访问)之前必须现对 S2 进行 P操作,判断 S2 的值,如果不为0,就对 S 执行 P操作。如果为0,则表示缓冲区为空(没有产品),消费者进程必须等待。只有这两个 P操作都通过,生产者才能拿到产品。然后对 S 进行 V操作,表示自己不再访问临界区了。再对 S1 进行V操作。

    管程

         虽然信号量机制已经是一种方便又高效的进程同步机制,但每个访问临界区的进程必须自备PV操作,这就是大量同步操作分散在各个进程中,不利于系统的管理,也容易产生死锁。为了解决问题,又引进了一个新概念——管程。

         系统中的资源都可以用数据结构抽象地描述其资源特性,而忽略它们的内部结构和实现细节。因此,可以利用共享数据结构抽象地表示共享资源,并且将对该共享数据结构实施特定的操作定义为一组过程。简单理解,这个过程就是我们所说的管程。

         有了管程之后,进程对共享资源的访问,可以不用自备PV操作了。直接通过这一个过程就可以,这一个过程就包括了进程对资源的申请、请求和其它操作。而这个过程可以确保每次只让一个进程进入,实现了互斥。也达到了对共享资源的所有访问的统一管理。

         仔细想想,管程其实包含了面向对象的思想,将数据和操作都封装起来,隐藏实现细节。任何管程以外的过程都不能访问到里面的数据。进程也只需要调用管程中的方法就可实现对资源的访问。

    线程

          如果说进程的引入是为了解决程序并发执行的问题,那么线程的引入则是为了更好的提高程序并发执行的程度。

          因为进程本身是占有资源的,在进行进程调度时有很大的时空开销。所以再将进程分为更小的不带资源(占据很少量资源)的线程,然后以线程作为为调度和分配的基本单位来较小时空开销,提高并发程度。

    进程通信

          进程之间因为存在着互斥和同步的关系,所以进程之间肯定需要进行一定的信息交换。(没有沟通,怎么能懂别人想干什么呢,对吧)

          前面提到了信号量机制其实就是一种低级通信,因为每次只能告知另一个进程一个信息。比如说放了一个产品,而不能说放很多产品了。

          高级通信就是能够高效地传送大量数据,并且使用方便,对用户透明(系统隐藏了实现进程通信的具体细节)。

    一个很关键的概念:在操作系统中,“透明” 一词指某种东西实际存在,但从某个角度看好像没有。就是对应用人员来说不可见(你只能按它说的做,但不能直接控制)。

          高级通信包括:

    • 共享存储器系统
    • 管道(pipe)通信系统
    • 消息传递系统——不借助任何共享存储区,直接以格式化的消息为单位,将通讯数据封装在消息中,并利用OS提供的通信命令(原语)在进程之间进行消息传递。这个方式隐藏了通信细节,对用户透明化,使用简单。计算机网络中就采用了这种方式,不过不叫消息,而叫报文。该方式又可分成直接通信方式(发送进程直接利用发送原语将消息发送给接收进程)和间接通信方式(发送和接收进程通过共享中间实体(邮箱)来进行消息的发送和接收)
    • 客户/服务器系统——主要用于网络环境下,主要技术有:套接字(Socket,一个通信标识类型的数据结构,通过这个套接字,进程就能知道通信目的地址、使用的端口号、传输层协议、进程所在网址等信息),远程过程调用(Remote Procedure Call)和远程方法调用(和过程类似,不过在面向对象中叫方法)。

    进程调度

           三级调度的概念:

    1. 高级调度——又称作业调度(将作业从后备队列调入就绪队列,也就是从外存调入内存)
    2. 中级调度——又称兑换调度(类似于挂起和激活)
    3. 低级调度——又称进程调度

           调度算法:先来先服务、时间片轮转法、优先级调度、多级反馈队列调度(具体算法思想就不再赘述)

           死锁:一组进程中的每个进程都在等待着只能由改组进程才能引发的事件。

           死锁必要条件:互斥条件、请求和保持条件(就是既占有资源,又请求新资源)、不可抢占条件,环路条件。

           死锁预防:通过破环四个必要条件中的一个或几个。一次性分配法(破坏请求和保持条件)、有序资源分配法(破坏环路条件)

           死锁避免:银行家算法,就是对每一次分配资源都要判断是否是安全状态,安全才分配,不安全则不分配,开销很大。

           死锁检测:看图法

           死锁解除:抢占资源、终止进程。

    展开全文
  • 处理器系统进程分配处理器系统 (MPS) 的类型 紧密耦合型:共享内存和 I/O,通过高速总线连接。 松弛耦合型:独立内存和 I/O,通信线路或通道连接。 对称处理器系统 (SMPS) 和非对称处理器系统非对称处理器...
  • 操作系统处理机调度

    千次阅读 2018-05-19 11:15:41
    一般来说,处理机调度最常用的是低级调度,也称为进程调度,进程调度的主要功能是根据某种算法,决定就绪队列中的哪个进程获得处理机。高级调度又称为作业调度,其主要功能是根据某种算法决定将外存上处于后备队列中...
  • 道程序环境下,进程数目往往多于处理机数目,致使它们竞争使用处理机。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统...
  • 操作系统实验-单处理机系统的进程调度

    千次阅读 多人点赞 2018-12-17 17:43:56
    实验项目一:单处理机系统的进程调度 4学时 ...Windows操作系统环境下的个人微机。 (三)实验内容 设计实现一个对N个进程采用动态优先权算法的进程调度。本实验为单机模拟进程调度算法,在程序设计时不...
  • 计算机操作系统处理机的调度

    万次阅读 2019-03-30 10:24:59
    处理机调度层次: 1.高级调度:它调度的对象是作业。其主要功能是根据某种算法,决定讲外存上处于后备队列中的哪几个作业调入内存,为它们创建进程,分配必要的资源,并将它们放入就绪队列。 2.低级调度:它调度...
  • 第二章 进程管理 - 处理机调度 调度的三个层次 高级调度(作业调度) 中级调度(内存调度) 低级调度(进程调度/处理机调度)频率最高 进程的七状态模型 五状态模型 -> 七状态模型 进程调度的时机 1、当前运行的进程...
  • 调度层次 1.高级调度(High Level Scheduling)高级调度又称长程调度或作业调度,它的调度对象是作业。主要功能是根据某种算法,决定将外存上处于...其主要功能是,根据某种算法,决定就绪队列中的哪个进程应获得处理机
  • 操作系统处理机调度及常见的调度算法(先来先服务调度算法(FCFS),短作业(进程)优先调度算法,高优先权优先调度算法,时间片轮转算法)
  • *进程的定义:进程是一个具有独立功能的程序在一个数据集合上的一次动态运行过程(是操作系统进行调度和资源分配的基本单元,进程间的通信、同步及上下文切换的开销略大) *进程的特征 1.动态性:动态性是相对于程序...
  • 操作系统中的处理机是什么?CPU?内核?

    千次阅读 多人点赞 2018-03-21 11:36:37
    处理机:计算机系统中存储程序和数据,并按照程序规定的步骤执行指令的部件。处理机包括中央处理器,主存储器, I/O 接口。处理机再加上外围设备eg:鼠标?键盘?等构成完整的计算机系统。处理器:中央处理器(Central...
  • 处理机是处理计算机系统中存储程序和数据,并按照程序规定的步骤执行指令的部件。程序是描述处理机完成某项任务的指令序列。指令则是处理机能直接解释、执行的信息单位。 2.中央处理器(CPU,Central Processing ...
  • 在计算机操作系统教程(第3版)
  • 操作系统课程设计:设计一个按照时间片轮转法实现处理机调度的程序 一:时间片轮转法实现处理机调度的程序设计提示如下: (1) 假设系统有n个进程,每个进程用一个进程控制块(PCB)来代表。进程控制块的格式如下表...
  • 1.处理机的所有指令可以在()中执行。 目态 浏览器中 任意时间 系统态 解答:D cpu工作状态分为系统态(或称管理态,管态)和用户态(或称目态)。 引入这两个 工作状态的原因是:为了...
  • 处理机调度 调度的基本概念 当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序,这就是"调度"研究的问题。 举个有味道的例子: 现在有4个人要上厕所...
  • 现代操作系统第三版高清

    千次下载 热门讨论 2015-06-16 22:20:01
     8.1.2 多处理机操作系统类型301  8.1.3 处理机同步303  8.1.4 处理机调度306  8.2 计算机309  8.2.1 计算机硬件309  8.2.2 低层通信软件312  8.2.3 用户层通信软件313  8.2.4 远程过程调用314  ...
  • 阵列处理机

    千次阅读 2014-06-14 10:12:53
    阵列处理机: 通过重复设置大量相同的处理单元PE(Processing Element),将它们按一定方式互连成阵列,在单一控制部件CU(Control Unit)控制下,对各自所分配的不同数据并行执行同一组指令规定的操作。是操作级...
  • 操作系统基础知识复习总结

    万次阅读 多人点赞 2018-06-11 13:55:23
    处理机管理 设备管理 文件管理 用户接口 操作系统的定义 是管理和控制计算机系统中各种硬件和软件资源、合理地组织计算机工作流程的系统软件,是用户与计算机之间的接口。 道批处理系统 在...
  • 操作系统

    千次阅读 多人点赞 2018-10-22 22:46:42
    操作使用者认为操作系统是一组命令的集合,程序设计人员认为操作系统是一组功能调用程序的集合,一般认为,操作系统是一种管理计算机资源 ,控制程序执行,改善人界面和为其他软件提供支持的系统软件。...
  • 操作系统概论【一】 - - 操作系统概述

    万次阅读 多人点赞 2020-03-08 15:55:39
    多道批处理系统多处理系统的特点:多道处理系统的缺点:3.分时操作系统分时操作系统的特点:分时操作系统的缺点:4.实时处理系统实时处理系统的特点:实时处理系统的缺点:操作系统产品现状:三:操作系统的特征四...
  • 所谓处理机的态,又称处理...操作系统的管理程序和用户程序在处理机上执行时,二者的职责不同,权限也不同,为了保护操作系统,所以要区分处理机的态。 转载于:https://www.cnblogs.com/luo841997665/p/4658868.html...
  • 操作系统复习习题

    万次阅读 多人点赞 2020-07-07 08:56:31
    A处理机操作和IO操作 1-5要求在规定的时间内对外界的请求必须给予及时相应的OS是?B实时系统 1-6对用户分时系统最重要的是?交互性 1-7在下面关于并发性的叙述正确的是?并发性是指若干事件在同一时间间隔发生 1-8...
  • 《王道操作系统》学习笔记总目录+思维导图

    万次阅读 多人点赞 2020-02-20 19:02:14
    本篇文章是对《2021操作系统》所有知识点的笔记总结归档,会一直更新下去 之后我也会写组成原理、计算机网络、数据结构与算法、Java、Linux等底层和应用层的技术文章,并总结目录 希望在自己可以复习的同时,也能将...
  • 程序员必知的 89 个操作系统核心概念

    万次阅读 多人点赞 2020-03-31 19:13:39
    操作系统需要处理管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。 shell:它是一个程序,可从键盘获取...
  • 软件设计师4--OS处理机管理

    千次阅读 2018-11-16 12:47:26
    道批处理操作系统和分时操作系统中有个并发执行的进程。进程是资源分配和独立运行的基本单位。处理机管理研究的是进程之间的并发性,以及进程之间的相互合作与资源竞争产生的问题。 1. 进程的状态 进程的...
  • 操作系统知识点整理(完整版)

    万次阅读 多人点赞 2017-12-26 22:34:05
    系统软件:操作系统语言处理程序,数据库管理系统 应用软件:各种管理软件,用于工程计算的软件包,辅助设计软件 4)通常把未配置任何软件的计算机称为“裸机” 5)操作系统可以被看作是计算机系统的核心,统管

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,060,061
精华内容 424,024
关键字:

多处理机操作系统