精华内容
下载资源
问答
  • 2021-01-02 23:14:38

    从单机到多机:多机一定比单机快吗?秒杀到底有没有必要用分布式锁?

    一、单机场景

    单机能承受的 TPS

    • tomcat 500~1000
    • mysql 200~800

    在单机状态下,tomcat 能接受的请求肯定比 mysql 更多,此时数据库成为系统瓶颈。为了解决这个问题,可以将自增的累加器(例如请求次数、商品剩余等等)等“公共值”缓存起来,放在 JVM 里面,仅让有效请求到达数据库,让 DB 的 TPS 有最大利用价值。

    Tomcat 是多线程的,会产生并发问题。我们考虑不同商品数量的情况:

    • 最小,只有一件商品供秒杀,此时多线程在扣减商品的时候,要排队串行,串行放进队列里,不需要加锁了
    • 最大,很多件商品的时候,由于商品与商品之间是无关的,不同商品可以看做是并行的,同一个商品在同一个队列里,也不用加锁了

    思考,如果第一件商品10件,第二件商品9999件,第三件商品500件,都在数据库里,如果没有前置判断的话,夹杂着的请求很快会让1件的商品卖光,后续还有很多对卖光商品的请求,白白占用了数据库的性能。所以我们需要前置的拦截,让最终进来的请求都是还有库存的商品。

    目前来看,是不是不用锁了?是的,但是我们大多数人很少在开发的时候去做线程的资源隔离,而是直接把请求打出去,当所有请求是并发达到数据库的时候,我们控制不了请求的顺序性,所以才会有锁的概念。

    二、多机场景

    场景:单机 1 个 tomcat -> 多机 2 个 tomcat

    多机情况下,只有一件商品的时候,也需要加锁,防止超卖。锁是一个参照物,用来参照哪个线程取到了、哪个线程没取到。锁自身要具备排他性,即只能有一个线程取到。那么如何实现排他性?

    • redis worker 线程是串行的

    • zk 两阶段提交,主从,主是串行的

    1、在分布式场景下,有了分布式锁,还需要单机锁吗?

    首先要理解的是,我们在数据库上目的是做有效请求的过滤,让没有意义的操作不去消耗它的资源和网络带宽。在微服务当中,在任何一个节点上,我们都要关注请求的有效性。虽然微服务是“不主动、不拒绝、不负责”,即使打过去的是无效请求,也会正确返回,但 调用方必须考虑请求的“有效性”,不随便去浪费服务方的资源,这是调用方个人价值的体现。这是面试的时候你要强调的,可以区别于其他人的。

    回到这个问题,在分布式场景下,有了分布式锁,还需要单机锁吗?

    • 举一个例子,如果有两台机器一共10个线程去抢锁,在只有1件商品的情况下,最终只有1个线程能拿到锁,而服务方承受的I/O的负载是O(10)。

    • 同样的情况,如果你对每个单机加锁,服务方承受的I/O的负载就只有O(2),在整体的性能上会有提高。另外,如果不想用本地锁,也想达到O(2)的效率的话,你也可以在每个单机上用逻辑做资源隔离,通过队列实现串行。

    2、多件商品情况下,商品之间其实是无关的

    商品之间无关,所以多件商品和一件商品的情况类似。在用户下单后,n 件商品经过过滤,最终每件商品只有有效请求到达数据库,大大减少了数据库的压力。

    在这里插入图片描述
    比如,限制每个用户只能买 3 种商品,每个商品限购 2 件,系统应该怎么设计?

    根据“只能有效请求到达数据库”原则,多余秒杀的商品不应该到达数据库浪费I/O资源,因此应该做前置过滤。解决方法是将 redis 集群前移。在 redis 里面将售卖规则创建成 key,后续用业务逻辑判断此次用户请求是否能够生成订单。

    比如,一个用户请求到达之后,去 redis 取商品种类、商品单品数量、用户 id,带着想要秒杀的商品的 itemid 一起返回到 tomcat,由业务逻辑判断这个用户能不能下单,从而识别“有效请求”。你也可以用 redis 事务来处理一个用户的多个减库存,防止超出限购数量。识别了有效请求(防止超卖)后,生成订单即可,因为第三方支付是异步的,后续订单可以走队列了,无需再加锁。队列的迁移到后续的分库分表,是后续调优要考虑的问题。

    另外,商品数量足够大的话,不同商品可能放在 redis 不同的节点中,稍显复杂,这个是开发人员要考虑的逻辑。redis 分区后,就不能使用 LUA 脚本和事务实现上述多个判断逻辑了,需要自己写逻辑实现了。

    3、服务的无状态性:多机一定比单机快吗?都说秒杀场景一定要用分布式锁,真的是这样吗?

    首先要理解一个概念,就是 服务的状态性。累加器、公共值,属于状态数据。为了维护多机的状态,要保持数据的同步,去做事件传递,去做分布式协调。zk 是主从架构,性能并不高,仅应该用来维护核心且不经常发生变化的那些数据的一致性,并不是一个很好的用于数据同步的技术方案。正确的方式是做服务状态的迁出,而不是去多台机器上做数据的同步。

    单机情况下,没有到达瓶颈的时候,单笔业务处理速度是最快的。加机器并不能提升速度,反而由于网络开销,让单笔请求变慢。而且单机是不需要外部锁的,而多机要做一致性、同步问题,反而加机器会让整个系统变慢。

    那为什么常说多机会变快?这样说的前提是:不只有一件商品。如果只有一件商品,最终都要成为串行去扣这一件商品的库存,多机一定不会带来速度的提升。而在多件商品的情况下,多机可以让无关的商品之间并行,不同商品的减库存进入不同的机器并同时执行,而受制于一台机器的性能问题,虽然可能会排队,但最终的表现是,多机能够“让无关请求并行起来”,因此才会有所谓的“快”。

    最后,无论你怎么变,(考虑到多机存在的数据同步问题和单机存在的CPU调度问题),在“没有资源瓶颈”的时候,并行总是会比串行慢。串行才是效率最高的方式。

    4、升华:从商家的角度,秒杀的目的是什么?

    从商家的角度,不是每个人都能拿到秒杀的便宜。秒杀是为了引流,应该用更低的成本获得更多的用户使用这个平台,完成秒杀。在秒杀的同时,也应该做限购,即一个用户只能拿走一件商品。加了限购的秒杀才是完善的秒杀系统。

    秒杀场景下,会有很多人刷单,因此才更应该仅让有效请求到达数据库。根据上面的方案,无效请求都让 redis +业务逻辑 挡住了,保护了mysql。

    那如果用户下单之后不付款,交易失败怎么办?你仍然要从商家的角度考虑,实际上,卖少了没关系,但不能超卖。况且,如果秒杀没有结束,你可以把库存加回去。这就是产品经理和程序员要换位思考。

    5、秒杀系统还需要分布式锁吗?

    不需要了。redis 所有的操作是串行的,每一个操作拥有了原子性和排他性。分布式锁成本是很高的,上述解决方案将 redis 集群前移来做请求有效性识别、减库存这些事情,就不需要做分布式锁了。

    所以,对于任何系统设计,不要上来就推导“多机”的架构模式。

    6、redis 宕机了怎么办?

    程序员代码不能解决所有问题,要在其他地方做补偿,例如你还是要靠运维、靠linux内核调优、靠监控系统、靠服务器硬件的冗余能力,在秒杀这样的特殊场景,你还是需要对服务器细心照顾、特殊对待。不要因为技术而技术,要从企业的角度其实追求可用性。

    如果不断的追求某个问题的解决方案,很可能会引入其他的问题。也不要把平时的解决方案放进特殊场景中使用,可能会引起蝴蝶效应,风险很大。美团发布过一篇实战文章,在大量并发情况下关闭健康检查,避免一些节点被剔除。必要的时候,让一些用户的请求失效。虽然可能会让用户体验上稍微慢一些,但保证整个服务的可用性才是最重要的。站在产品经理的角度来看,这个方案可以了。

    7、那分布式锁岂不是没用了?什么场景需要分布式锁呢?

    分布式锁其实是在解决并发问题。未来很多公司采用响应式编程、流式编程模型(而且已经有公司落地了),无状态、无锁化将是趋势。

    如果你学过大数据的话会更好理解,map reduce 计算框架,map 处理数据初始状态进行加工,同一数据做 reduce 的时候会有分区概念,最后分治汇总。

    所以,在开发的时候,我们应该尽量去规避分布式锁,去采用无锁化的方式解决问题。

    更多相关内容
  • 操作系统——处理机调度

    千次阅读 2021-02-02 18:44:31
    文章目录一、处理机调度的层次1. 高级调度(作业调度)2. 低级调度(进程调度)3. 中级调度(内存调度)二、处理机调度算法的目标1. 处理机调度算法的共同目标2. 批处理系统的目标3. 分时系统的目标4. 实时系统三、...


    一、处理机调度的层次

    1. 高级调度(作业调度)

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

    2. 低级调度(进程调度)

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

    3. 中级调度(内存调度)

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

    二、处理机调度算法的目标

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

    • 资源利用率:为了提高资源的利用率,应使系统中的处理机和其他所有资源尽可能保持忙碌状态。
    • 公平性:公平性是指应使诸进程都获得合理的CPU时间,不会发生进程饥饿现象。但公平是相对的,对于相同类型的进程应获得相同的服务,对于不同类型的进程,由于其紧急程度和重要性不同,提供不同的服务。
    • 平衡性:为使系统中CPU和各种外部设备都能经常处于忙碌状态,调度算法应保存系统资源使用的平衡性。
    • 策略强制执行: 对所指定的策略其中也包括安全策略,只要需要,就必须提供。

    2. 批处理系统的目标

    • 平均周转时间短:周转时间是指,从作业被提交给系统开始,到作业完成时间这段时间的间隔。它包括:作业在外存后备队列上等待调度的时间,进程在就绪队列等待的调度的时间,进程在CPU上执行的时间,以及进程等待I/O操作完成的时间。
    • 系统吞吐量高:吞吐量是指单位时间内系统完成的作业数,如果单纯为了获得高的系统吞吐量,那么就应该尽可能选择短作业运行。
    • 处理机利用率高:如果单纯为获得处理机利用率高,那么应该尽可能选择长作业运行。

    3. 分时系统的目标

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

    4. 实时系统的目标

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

    三、作业与作业调度

    1. 批处理系统中的作业

    • 作业
      • 作业是一个比系统更广泛的概念,它不仅包含了通常的程序和数据,而且还应配有一份作业说明书,系统根据该说明书来对程序的运行进行控制。
      • 在批处理系统中,是以作业为基本单位从外存调入内存
    • 作业步
      • 在作业运行期间,每个作业都必须经过若干相互独立又相互关联的顺序加工步骤才能得到结果。我们把其中每一步称为一个作业步。
      • 例如,一个典型的作业步可以分为:“编译”作业步,“链接装配”作业步,和“运行”作业步。
    • 作业控制块(JCB)
      • 和进程线程类似,作业中也包含一个作业控制块(JCB)。
      • 通常JCB包含:作业标识,用户名称,用户账号,作业类型,作业专业,调度信息,资源需求,资源使用情况。
    • 作业运行的阶段和状态
      • 收容状态:操作员把用户提交的作业通过某种方式或SPOOLing系统输入到硬盘上,在为该作业建立JCB,并把它放入作业后备对列中。
      • 运行状态:当作业被作业调度选中后,边为它分配必要的资源和建立进程,并把他放入就绪队列。
      • 完成状态:当作业运行完成,或发生异常情况而提前结束时,作业便进入了完成阶段。

    2. 作业调度的主要任务

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

    3. 先来先服务调度算法(FCFS)

    • 既可以用于作业调度,也可以用于进程调度。
    • 作业调度中采取该算法时,系统将按照作业到达的先后次序来进行调度。
    • 进程调度中采用该算法时,每次调度是从就绪的进程队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或者阻塞时,进程调度程序才会将处理机分配给其他进程。
    • 说明:该算法在单处理机系统中已经很少作为主调度算法,但经常把它和其他调度算法结合使用,形成一种更为有效的调度算法。例如,可以在系统中按进程的优先级设置多个队列,每一个优先级一个队列,其中每一个队列的调度都基于FCFS。

    4. 短作业优先调度算法(SJF)

    • 该算法是以作业的长短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的时间来衡量的。
    • 该算法也可以分别用于作业调度进程调度。但用于进程调度时优于作业调度。
    • 缺点
      SJF相比FCFS算法,有很大的改进,但依然有以下缺点
      • 必须预先知道作业的运行时间;
      • 对于长作业非常不利,很可能出现饥饿现象;
      • 无法进行人机交互;
      • 没有考虑作的紧迫程度,不能保证紧迫性的作用能够得到及时的处理。

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

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

    6. 高响应比优先调度算法(HRRN)

    • FSFC算法考虑的只是作业的等待时间,忽略了运行时间;
    • SJF算法考虑的只是作业的运行时间,忽略了等待时间;
    • HRRN算法既考虑了作业的等待时间,又考虑的作业的运行时间,从而改善了处理机调度的性能。
    • HRRN为每一个作业引入了一个动态优先权。该优先权的变化规律如下:
      在这里插入图片描述

    同时,等待时间+要求服务的时间 = 相应时间。所以优先权也可以表示为:
    在这里插入图片描述
    从上式可以看出:

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

    四、进程调度

    1. 进程调度的任务

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

    2. 进程调度的机制

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

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

    3. 进程调度的方式

    • 非抢占式
      • 采用这种调度方式时,一旦把处理机分配给某进程后,就一直让他运行下去,绝不会因为时钟中断或者其他原因抢占当前处理机,直到该进程完成或者阻塞,才把处理机分配给其他进程。
      • 这种方式的好处就是实现简单,系统开销小适用于大部分批处理系统
      • 但是无法适应于分时系统和大部分的实数系统
      • 这种方式下,会引起调度的原因:
        • 正在执行的进程执行完毕,或者因为某些事无法继续执行;
        • 执行的进程提出I/O请求,而暂停执行;
        • 在进程通信或者同步过程中,执行了某种原语操作,比如Block原语。
    • 抢占式
      • 这种调度方式允调度程序根据某种原则,去暂停某个正在执行的进程,将已经分给该进程的处理机重新分给另一进程。
      • 广泛采用抢占式,是因为对于批处理系统,可以防止一个长进程长时间的占用处理机,以确保处理机能够为所有进程提供更为公平的服务。
      • 分时系统中,只有采用抢占式才能实现人机交互,在实时系统中,抢占式能满足实时任务的要求
      • 但同时抢占式比较复杂,所需要的系统开销比较大
      • “抢占式”抢占时也需要按照一定的原则,主要原则有:
        • 优先权原则,指允许优先级高的新到进程抢占当前长进程的处理机,即新进进程到达时,如果他的优先度比正在执行的进程优先度高,则调度程序剥夺当前进程的处理机。
        • 短进程优先原则,指允许新到的短进程抢占当前的长进程的处理机,即新进 进程到达时,如果他的比正在执行的(尚需运行)时间明显短,则调度程序剥夺当前进程的处理机。
        • 时间片原则, 即各进程按时间片轮转运行时,当正在执行的进程的一个时间片段用完后,便停止该进程的执行,而重新进行调度。

    4. 轮转调度算法(RR)

    • 轮转法的基本原理
      在RR中,系统将所有的就绪进程按照FCFS策略排成一个就绪队列,系统可设置每隔一定时间便产生一次中断,去激活进程调度程序进行调度把CPU分配队首进程,并令其执行一个时间片。运行完毕后,又把处理机分配给就绪队列的新的队首。
    • 进程切换时机
      在RR算法中,切换时机有两种情况
      • 若一个时间片未用完,正在运行的进程便已完成,就立即激活调度进程,将它从就绪队列删除,调度就绪队列的队首进程。
      • 在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完成,调度程序将它送往就绪队列的末尾。
    • 时间片大小的确定
      在RR算法中,时间片的大小对系统性能有很大影响
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    5. 优先级调度算法

    • 优先级调度算法的类型
      优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程。同时又可以进一步把该算法分为:
      • 非抢占式优先级调度算法
      • 抢占式优先级调度算法
    • 优先级类型
      • 静态优先级。静态优先级是在创建进程时确定,在进程的整个运行时间不变。优先级的大小确定的依据有:
        • 进程类型;
        • 进程对资源的需求;
        • 用户要求;
      • 动态优先级。动态优先级是指在进程创建之初,先赋予其一个优先级,然后其值随进程的推进或者等待时间的增加而改变,以获得更好的调度性能。

    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. 实现实时调度的基本条件

    • 提供必要的信息
      为了实现实时调度,系统应向调度程序提供以下信息:
      • 就绪时间,是指任务成为就绪状态的起始时间。
      • 开始截至时间和完成截至时间
      • 处理时间,即一个任务从开始执行到完成所需要的程序
      • 资源要求,任务执行是所需要的一组
      • 优先级,如果某任务的开始指向截至时间错过,势必引起故障,则应为该任务赋予“绝对”的优先级;如果其开始截至时间的错过,对任务的继续运行无重大影响,则赋予“相当”优先级。
    • 系统处理能力强
      • 在实时系统中,若处理机的处理能力不够强,则有可能因处理机忙不过,而致使某些实时任务不能得到及时处理,从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务HRT,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件系统才是可调度的:
        在这里插入图片描述
        提高系统处理能力的途径有二:
        一是采用单处理机系统,但须增强其处理能力,以显著地减少对每一个任务的处理时间;
        二是采用多处理机系统。假定系统中的处理机数为N,则应将上述的限制条件改为:
        在这里插入图片描述
    • 采用抢占式调度机制
      • 在含有HRT任务的实时系统中,广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。
      • 但这种调度机制比较复杂。 对于一些小的实时系统,如果能够预知任务法开始截止时间,则对于实时任务的调度可以采用非抢占式调度。
    • 具有快速切换的机制
      为保证硬实时任务能及时运行,在系统中还应具有快速切换机制,使之能进行任务的快速切换。该机制应具有如下两方面的能力:
      • 对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务)。
      • 快速的任务分派能力。为了提高分派程序进行任务切换时的速度,应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销。

    2. 实时调度算法的分类

    实时调度算法按照调度方式可分为:

    • 抢占式
      • 非抢占式轮转调度算法(同上)
      • 非抢占式调度优先算法(同上)
    • 非抢占式
      可根据抢占发生时间的不同而进一步分成以下两种调度算法:
      • 基于时钟中断的抢占式优先级调度算法。
      • 立即抢占(Immediate Preemption)的优先级调度算法。
        在这里插入图片描述

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

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

    • 非抢占式调度方法用于非周期实时任务
      在这里插入图片描述
    • 抢占式用于周期实时任务
      下图有两个周期任务,任务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、…,如下图
      在这里插入图片描述
      在这里插入图片描述

    5. 优先级倒置

    • 优先级倒置是什么:
      系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象,即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。
    • 优先级倒置的解决方法:
      • 一种较简单的解决方法就是,规定进程进入临界区后,该进程占用的处理机不允许被抢占;
      • 另一个比较实用的方法建立在动态优先级基础的基础上:该方法规定,当高优先级进程要进入临界区时,去使用临界资源R时,如果已有一个低优先级进程正在使用该资源。此时高优先进程被阻塞,另一方面低优先级进程继承高优先进程的优先级,直到低优先进程退出临界区。
    展开全文
  • 操作系统8————处理机调度

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

    操作系统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时,如果已有一个低优先级进程正在使用该资源。此时高优先进程被阻塞,另一方面低优先级进程继承高优先进程的优先级,直到低优先进程退出临界区。

    八. 参考资料

    《操作系统第四版》

    展开全文
  • 内核程序员的对称处理和缓存技术(修订版)》是为UNIX内核开发人员写的,它全面而通俗地阐述了高速缓存和对称多处理机的操作、二者协调工作的方法以及为了在融合两者的机器上运行操作系统必须要解决的问题。
  • NLP之人对话系统

    千次阅读 2018-10-11 22:15:32
    对话系统对话系统又称口语对话系统(spoken dialogue system)。一个典型的人对话系统主要包括如下6个技术模块:①语音识别器(speech recognizer);②语言解析器(language parser);③问题求解...

    人机对话系统

    人机对话系统又称口语对话系统(spoken dialogue system)。一个典型的人机对话系统主要包括如下6个技术模块:①语音识别器(speech recognizer);②语言解析器(language parser);③问题求解(problem resolving)模块;④语言生成器(language generator);⑤对话管理(dialogue management)模块;⑥语音合成器(speech synthesizer)。

    语音识别模块实现用户输入语音到文字的识别转换,识别结果一般以得分最高的前n(n≥1)个句子或词格(word lattice)形式输出。语言解析模块对语音识别结果进行分析,获得给定输入的内部表示。语言生成模块根据解析模块得到的内部表示,在对话管理机制的作用下生成自然语言句子。语音合成模块将生成模块生成的句子转换成语音输出。问题求解模块依据语言解析器的分析结果进行问题的推理或查询,求解用户问题的答案。对话管理模块是系统的核心,一个理想的对话管理器应该能够基于对话历史调度人机交互机制,辅助语言解析器对语音识别结果进行正确的理解,为问题求解提供帮助,并指导语言的生成过程。可以说,对话管理机制是人机对话系统的中心枢纽。

    1.口语解析器

    对于一个基于中间表示的口语翻译系统和人机对话系统来说,口语解析器的作用可以简要地用图16-1表示。语音识别模块首先将用户语音转换成文字串,口语解析模块对其分析、理解,并将其转换成中间表示格式。在口语翻译系统中,语言生成器基于中间表示生成目标语言句子,而在人机对话系统中,语言生成器在对话管理模块的指导和控制下生成系统响应的句子。口语翻译系统中的语音合成器生成目标语言的语音,而对话系统中的语音合成器生成用户语言的语音。

    接下来介绍两种面向中间表示格式的汉语口语解析方法,一种是规则方法和HMM统计方法相结合的解析方法;另一种是基于语义分类树的解析方法。(中间表示采用C-STAR定义的IF格式)

    1.1中间表示格式

    IF格式的理论基础是对话行为(dialogue acts, DAs)理论,其基本观点认为,语言不只用来陈述事实,而且还附载着说话者的意图。

    一个IF表达式通常由说话者(speaker)、话语行为(speech act)、概念序列(concept)和参数-属性值对的列表4个部分组成:
    Speaker:Speech-Act[+Concept]*[(Argument=Value[,Argument=Value]*)]
    其中,概念序列与话语行为合称为领域行为(domain action)。
    星号“*”表示它所限定的左边成分可以重复出现多次。 

    (1)说话人标志(Speaker):表示说话人的身份。在IF中只有两种说话人身份,一种是顾客(client),用“c”表示,另一种是代理(agent),用“a”表示。
    (2)语句意图或称话语行为或言语行为(Speech-Act):表示“询问信息、动作请求、返回信息”等各种话语意图。
    如“give-information”表示提供某种信息;“pardon”表示请求说话人重复刚才所说的内容。
    (3)概念(Concept):表示句子的主题(topic)概念。
    如“reservation”表示“预订”,“room”表示“房间”等。各个概念之间按照一定的规则可以组合成更加广泛的主题。概念之间用“+”连接,表示并列关系,如“reservation+room”表示“预订房间”。
    (4)具体参数(Argument):表示句子的具体内容。例如,房间个数、房间标准等。每个具体参数可以有不同的属性值(value),取值可以是原子值、参数-属性值对、或几个原子值按一定关系的组合(常对应句子中的联合结构)。
    例如,参数“room-spec”表示属性“房间种类”,它的取值可以是“single(单间)”、“double(双人间)”等。

    例: 明天我想预订一个单人间。
    IF:c:give-information+reservation+room(room-spec=(room-type=single, quantity=1), reservation-spec=(time=(relative-time=tomorrow)))
    该IF的含义为:说话人为“c”,该句子的意图是提供信息,主题概念为“预订房间”,关于“房间”的具体信息由一组“属性-值”对描述:房间类型(room-type)为单人间(single),数量(quantity)为1;“预订”的具体要求通过“相对时间(relative-time)”这一参数描述,参数值取“明天(tomorrow)”。

    1.2基于规则和HMM的统计解析方法

    本方法的基本思想可以用图表示。对于一个来自语音识别器的待解析句子,首先由词汇分类模块对其词汇进行词义分类,即把句子中的每一个词映射到相应的词义类中去。然后,语义组块分析器从句子对应的词义类序列中分析出语义组块,组块分析器输出的是一个语义组块序列。接下来,统计解析模块从语义组块序列分析出句子IF表示的主要框架。语义组块解释模块把各个语义组块解释为相应的IF表达式片段。最后,经过对上述两部分的合并,得到最终的IF表达式。

    下面具体介绍各个部分的实现方法。1,词汇分类:根据词汇的语义功能,把每个词汇划分到不同的类。为此,我们定义了一个词汇语义类词典。在分类时参考了《同义词词林》和IF的相关规范。其分类依据是词汇在句子中的语义功能,语义功能相同的词汇归为一类。2.语义组块分析: 语义组块是指口语句子中不依赖于其他词汇而能表示某种特定语义的最小部分。同时,我们根据语义组块具体的意义,对语义组块进行了语义分类。语义组块分析器采用基于规则的线图分析算法(chart-parsing)实现组块识别,语法规则为基于词汇语义类的CFG,规则描述的是词汇语义类或语义组块之间组合成新语义组块的条件和结果。这些规则是通过观察和分析语料手工编写的。组块分析器的分析结果不一定是一个句子的完整语义结构树,可能是多个并列的局部语义结构子树。每个子树对应一个组块,一个句子的子树序列对应句子的语义组块序列。3.统计解析过程: 统计解析模块用于从输入的语义组块序列中解析出IF表示的主框架,采用HMM实现,其核心思想是将输入的语义组块序列作为HMM的观察,而将句子的IF表示作为HMM的内部状态。4.组块解释方法: 在语义组块分析时,通过规则方法获得语义组块的同时,也可以得到语义组块内部的层次结构,但这种层次结构并不是我们所需要的IF表示,因此,我们设计了语义组块解释模块,用来把这种层次结构转换为IF表示。语义组块解释模块是与组块分析模块配合工作的,组块分析过程中用到的每一条规则都对应一个规则的解释方法,利用这些解释方法可以把规则所涉及的词汇解释为相应的IF表示。5.IF的生成:从上面的介绍可以看出,基于HMM的解析模块输出的结果和语义组块解释的结果都只是IF的片段,只有把它们合并才能得到完整的IF表示。语义组块解释模块把每个语义组块转换为IF片段,同时每个语义组块经过统计解析模块解析后,又对应一个标注符号,并且该标注符号最终要作为IF表示中的一个结点。在各组块合并时,IF生成器把语义组块解释结果作为该结点的子结点,把经过简化处理的concepts序列还原为原来的concepts序列,这样就得到了IF表示。

    1.3基于语义决策树的口语解析方法

    从上面的介绍中可以看出,基于语义组块的口语解析方法在限定领域内能够获得较好的解析效果。

    但是,该方法存在如下不足之处:①上下文窗口偏小。在使用HMM对句子进行解析时,窗口一般限定在左右两个词汇或组块,而在口语句子中存在很多不规范的现象,很多情况下一个词或短语的语义与离它较远的词汇密切相关,如果窗口太小,不利于处理长距离的约束关系。②领域行为中的多个概念需要根据人工预先定义的语义符号经解释获得。这样,对于每一个可能存在的概念序列都需要定义一个符号和相应的解释规则,这项工作不但繁琐,而且主观性强,并且影响系统的领域移植能力和IF的表达能力。③在获取话语意图时,主要从解析结果的单个特殊单元来理解,这样也存在一定的局限性。

    基于语义决策树的口语解析方法,该方法用统计方法从训练语料中自动获取规则,从而避免了人工编写规则的繁琐和主观性,并具有较高的鲁棒性,用统计模型直接获得整个领域的行为表示,便于句子整体意义的理解。

    通过观察,我们发现一个汉语句子的领域行为和句子中的一些关键词语存在密切关系。因此,我们可以根据词语所在的上下文环境来确定其语义。

    该方法的基本思路是:在对训练语料进行标记的基础上,为每一个与领域行为密切相关的词汇生成一棵语义分类树,语义分类树包含了在其生成过程中从训练语料中自动获取的一系列语义规则和语义的概率信息。当一个需要解析的句子输入时,首先用语义分类树对与领域行为密切相关的词语进行解析,获得它们对应的语义信息及其概率。然后,用统计模型对多个词语的语义结果进行组合,从而获得整个句子的领域行为。为了减小系统规模和数据稀疏问题,可以在对句子进行预处理的基础上对句子的词类或组块进行解析。

    2.基于MDP的对话行为识别

    对话行为(dialog acts, DAs)是说话人对话意图的表现形式。

    2008提出了一种基于马尔可夫决策过程(Markov decision processes, MDPs)和SVM方法相结合的对话行为预测方法,其基本思路是:用MDP预测对话行为,然后将预测结果融入基于语句的SVM分类器,最终获得对话行为的识别结果。对话行为的预测映射为一个马尔可夫决策过程,定义为一个4元组(S, A, T, R),其中,S表示状态,由说话人是否变化的标记(sp_change)和对话行为(DA)的历史描述。如果说话人发生了变化,则sp_change=1,否则sp_change=0。对话历史包括同一说话人前一句话的对话行为和对方说话人前一句话的对话行为。

    A为动作集,一共包括13个动作,每个动作表示一个对话行为标签,作为对下一个对话行为的预测。如s表示陈(statement)、qy表示是非问(Y/N question)、qw表示特指问(Wh-question)等。
    T为状态转移概率矩阵,Tij=P(Sj|Si,Ai)表示系统由状态Si转移到Sj的概率。
    R表示回报(reward)。回报方程(reward function)是预测结果正确或错误的反映。Zhou et al.(2008b)从经验的角度对转移概率矩阵进行回报或惩罚。如果预测结果正确,回报因子为1.1,否则给出的惩罚因子为0.9,该数据为一组实验中测得的最优值。

    最后用SVM分类器对MDP的预测结果进行分类识别。

    3.基于中间表示的口语生成方法

    自然语言生成(natural language generation)技术研究的是如何利用计算机把非自然语言的表示形式转换成某种自然语言的表示形式,从而产生人们可理解的,表达确切、自然流畅的自然语言语句。接下来介绍基于IF的汉语口语生成方法。

    基于IF的汉语口语生成器是面向多语言口语翻译系统设计的,该系统采用基于模板的方法和基于特征的深层生成方法相结合的混合生成方法。采用这种混合方法的主要理由有如下几点:首先,特定领域的口语对话中常用一些固定的表达模式。其次,对于非固定的表达方式,由于其表达形式灵活多样,采用基于特征的深层生成方法无疑更能满足系统对于灵活性的要求。此外,基于特征的生成方法可以把不同语言的差异作为特征加入系统中,更易于用统一的程序框架实现不同语言的生成过程,便于系统扩展和移植。

    根据上述考虑,基于IF的汉语口语生成器主要由三个模块组成:微观规划器、表层生成器和后处理模块。一个给定的IF表达式,首先经过微观规划器得到对应的句法功能结构,然后,句法功能结构通过表层生成器得到最终的汉语句子。这里所用的句法功能结构是基于系统功能语法而定义的,其格式是多个特征-属性值对的集合,包含生成一个句子所必须的各种信息(语气、时态、语态、谓词框架等)。表层生成器采用功能合一文法,利用生成语言的句法知识把句法功能结构中的各个特征逐步聚合,并进行线性化处理。后处理模块完成句子最后的修饰和补充,包括添加助词、量词等。

    3.1微观规划器

    在基于IF的汉语口语生成器中,一个给定的IF表达式与一个句子或词组相对应,生成句子所需要的各项浅层信息都已经在IF的参数中给出,所以生成器所要做的事情就是根据IF和领域知识生成对应的语句,而无需进行句子内容的确定。但是,由于IF没有提供句子生成所需要的谓词-论元信息,需要生成器根据IF表达式、领域知识和中心词的搭配信息进行推断。因此,生成器中的微观规划器需要实现如下几个功能:①根据IF和领域知识确定句子的类型,获得句子生成所必需的谓词-论元框架;②将领域概念转化为词汇,进行词汇选择,并从词典中获得所有与选定词汇相关的词语搭配信息等;③将领域关系转化为语法关系;④获得句子的语气、时态和语态等信息。

    微观规划器完成的任务分为句子规划和短语规划两个层次。句子规划的功能主要是根据IF表达式和领域知识推断句子的顶层信息,如主要动词、时态、语态,语气等,并根据主要动词获得生成句子所必需的谓词-论元框架;短语规划是把IF格式中的属性和概念转换为句子的参与角色,即获得生成句子的浅层短语信息。

    一个IF表达式经微观规划器转换后成为句子的句法功能结构,句法功能结构将直接作为表层生成器的输入。领域知识体现在规划规则的表示上。

    句子规划规则可以由一个三元组(P,C,A)描述。P指IF的主体部分(包括说话者和领域行为)的模式(pattern),C是约束
    (constraints),可以是空集,也可以是对IF所含概念(concepts)和参数(arguments)状况的约束。A是动作(action),指在给定IF满足P和C的条件下,执行A操作获得该IF所对应的句子的功能结构。句子规划时,微观规划器输入的IF首先与P中的模式匹配,如果匹配,再看输入是否满足C中的约束,如果两者都满足,则执行动作A,获得句子的主要动词及框架信息。

    语规划主要处理IF中的“参数-属性值”描述,或者某些概念与“参数-属性值”的组合描述。与句子规划规则类似,短语规划规则也由三元组形式构成。

    3.2表层生成器

    表层生成器是语言生成器的最后一个阶段,其任务是借助于语法规则将微观规划器的输出生成正确、流畅的自然语言句子。

    表层生成器首先利用词法和句法规则对输入的句法功能结构表示进行合一运算,得到非线性化的句子模式,然后,利用句子和短语中各成分排列顺序规则对句子模式进行线性化处理,得到初步的生成语句,并由后处理模块做最后的修饰处理。

    由于IF本身是一种不完备的语义表示,而且语音识别和句子解析模块造成的错误往往使IF含有噪声或出现信息缺失等现象,因此,为了确保生成器具有一定的鲁棒性,能够在给定IF含有错误或不完整的情况下生成正确或可以理解的句子,该生成器中采用了缺省值处理措施,并放宽了对微观规划规则和表层生成器中语法规则的约束,使其能够在某些条件不满足的情况下生成不完整的句子。

     

    展开全文
  • 1-1. 下面对进程的描述中,错误的是 。 A.进程是动态的概念 B. 进程执行需要处理机 C.进程是有生命周期的 D....【答案】D ...【解析】分配到必要地资源获得处理机时的进程状态是执行状态。 1-3.程序的顺序执行
  • 操作系统总结整理第一章引论 本系列博客是源于2018级北航计算机学院的操作系统理论课程的课堂笔记、课堂练习及课后笔记整理而来。相关的参考资料绝大多数来自于北航计算机学院操作系统课程组,同时也参考了机械工业...
  • 进程调度: 分配处理机(1) 资源利用率高 系统吞吐量大 平均周转时间长: 作业周转时间:进入系统(进入外存)到完成并退出系统经历的时间 无交互能力 分时系统 定义 一台主机连接个终端,个用户可以通过自己的终端...
  • UE4摄像机系统解析

    万次阅读 多人点赞 2017-04-01 20:21:39
    摄像工作原理在游戏中,摄像是玩家的眼睛,他控制了玩家的视点(POV即PointOfView,后面简称POV)位置以及玩家的视野大小(FOV即FieldOfView,后面简称FOV)。一句话,摄像决定了我们去观察这个游戏世界。游戏...
  • 掌握操作系统原理的关键:一个观点、两条线索。 一个观点:以资源管理的观点来定义操作系统;从资源管理的角度看,操作系统主要是对处理器、存储器、文件、设备和作业进行管理。 两条线索:如何管理计算机各类资源...
  • 操作系统课程设计

    千次阅读 热门讨论 2020-06-05 13:23:36
    题目一:支持个进程(线程)并发运行的简单进程(线程)管理模拟系统 1.实验内容         学习进程管理的设计与实现,学习和运用操作系统原理,设计一个操作系统系统...
  • 点亮技能 I 人对话系统全面理解

    千次阅读 2019-09-02 22:36:57
    最近针对NLP的人对话系统方向作了学习,首先从底层技术NLP理解其工作原理,再了解基本的智能搜索、对话交互、问答匹配技术,最后体验了chatbot的一些开放平台进而抽象其框架和功能等,从而整理出此篇学习笔记。...
  • 数字音频分析和处理系统

    万次阅读 2018-01-04 22:47:15
    设计一个基于MATLAB的数字音频分析与处理系统,能够实现对数字音频的测试分析与处理。要求: 1) 输入语音信号源为实际环境采集语音; 2)至少实现1种音效测试分析功能(频率响应,瀑布频谱图,相位响应曲线,抗...
  • 第一章操作系统引论 1.设计现代OS的主要目标是什么? 答:(1)2有效性(2)方便性(3)可扩充性"(4)开放性 2.OS的作用可表现在哪几个方面? 答:(1)0S作为用户与计算机硬件系统之间的接口 (2)0S作为计算机系统资源的管理者 (3...
  • 计算机操作系统-1-总览

    千次阅读 2022-03-08 09:09:07
    计算机操作系统-1-总览
  • 分时操作系统道程序操作系统的区别  道程序系统是在计算机内存中同时存放几道相互独立的程序,使它们在管理程序控制之下,相互穿插的运行。 两个或两个以上程序在计算机系统中同处于开始和结束之间的...
  • 手把手教你用Java设计并实现一个城市公交查询系统

    万次阅读 多人点赞 2020-12-19 10:11:33
    为了使得我国公交乘客出行及查询有关信息更方便,本文运用JAVA语言技术,Jsp技术,Mysql数据库开发了B/S结构的城市公交查询系统。 该系统顺应了时代发展且具有以下优点:首先,方便乘客的出行,乘客不用询问站牌工作...
  • 操作系统系统笔记整理

    万次阅读 多人点赞 2020-09-26 13:37:27
    操作系统 前言 本篇文章的内容结合了哈工大李治军老师操作系统课程,王道考研操作系统的资料以及学习了B站CodeSheep的一次知识梳理,以及为了便于理解学习,增加了个人的一些解释。总之,对于开发人员来说,操作...
  • 本文分享主题:Faiss和bert提供的模型实现了一个中文问答系统。旨在提供一个用Faiss结合各种AI模型实现语义相似度匹配的解决方案。
  • 操作系统概述

    千次阅读 2022-03-19 13:02:30
    一、操作系统基本概念、特征、分类。 1、什么是操作系统 操作系统(Operating System,OS)是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分配,以提供给用户和其他软件方便...
  • 【图像处理】工业相机原理详述

    千次阅读 2018-07-03 22:07:37
    工业相机是机器视觉系统中的一个关键组件,其最本质的功能就是将光信号转变成有序的电信号。选择合适的相机也是机器视觉系统设计中的重要环节,相机的选择不仅直接决定所采集到的图像分辨率、图像质量等,同时也与...
  • 语音合成跟语音识别,自然语音理解,作为人交互的基础模块,加上对话管理器,形成人机语音对话系统。 语音合成原理 语音合成(Text to Speech,TTS)是指将文本通过一系列的信号处理转换为“人造”语音(声学...
  • 基于Python的飞机大战游戏系统设计与实现

    万次阅读 多人点赞 2019-09-14 20:21:41
    具有自带的调试器,调试器的功能多样化,可以提供多种功能,用户通过对基于Python和 Django的项目进行调试,同样,系统的单元测试,也可以通过它来解决, 该调试器包括blake点、分步、屏幕视图、窗口和计算表达式...
  • IT系统对接方案汇总

    千次阅读 2021-02-07 09:28:46
    通常,系统之间如果完全企业自主定制开发,且有源代码、服务器的所有权,可以选择数据库直传的方式,方便快捷。如果系统之间存在权限限制或技术限制,可采用接口以保证数据的安全和对接的规范性等等,不同的场景...
  • 人类想要实现一系列的基本活动,如生活、工作、学习就必须依靠自身的器官,除脑以外,最重要的就是我们的眼睛了,(工业)机器人也不例外,要完成正常的生产任务,没有一套完善的,先进的视觉系统是很难想象的。...
  • 单片机的程序可以分为三种:轮循系统、前后台系统任务系统。 轮询系统 即在裸机编程时,先初始化相关硬件,让主程序在一个死循环里面不断循环,顺序地处理各种事件。不能说轮询是低端的,轮询系统是一种非常简单...
  • 计算机系统的设计规则,性能评测

    千次阅读 2015-05-18 23:22:49
    3:软件实现,速度慢,复制费用低,灵活性好,占用内存,容易设计,可改性强, 适应性强,设计周期短理论上,由两种极端实现方法 1:全硬件机器:操作系统,高级语言,应用等 2:硬件只有1位加法和分支操作...
  • 多年来主要从事推荐系统以及机器学习,也做过计算广告、反作弊等相关工作,并热衷于探索大数据和机器学习技术在其他领域的应用实践。 责编:何永灿(heyc@csdn.net) 本文为《程序员》原创文章,更精彩文章请...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 167,712
精华内容 67,084
关键字:

多处理机系统体现了