免费智能真题库 > 历年试卷 > 系统架构设计师 > 2015年下半年 系统架构设计师 上午试卷 综合知识
  第1题      
  知识点:   信号   信号量   信号量与PV操作   工作流   进程   进程间的同步   同步与互斥
  关键词:   工作流   进程   信号量   信号        章/节:   操作系统       

 
某航空公司机票销售系统有n个售票点,该系统为每个售票点创建一个进程Pi(i=1,2,…,n)管理机票销售。假设Tj(j=1,2,…,m)单元存放某日某航班的机票剩余票数,Temp为Pi进程的临时工作单元,x为某用户的订票张数。初始化时系统应将信号量S赋值为(1)。Pi进程工作流程如下图所示,若用P操作和V操作实现进程间的同步与互斥,则图中空(a),空(b)和空(c)处应分别填入(2)。
 
 
  A.  0
 
  B.  1
 
  C.  2
 
  D.  3
 
 
 

 
  第4题    2011年下半年  
   38%
进程P1、P2、P3、P4和P5的前趋图如下:

若用PV操作控制进程P1?P5并发执行的过程,则需要设置5个信号量S1、S2、 ..
  第2题    2011年下半年  
   35%
进程P1、P2、P3、P4和P5的前趋图如下:

若用PV操作控制进程P1?P5并发执行的过程,则需要设置5个信号量S1、S2、 ..
  第4题    2013年下半年  
   29%
进程P1、P2、P3和P4的前趋图如下所示:
   知识点讲解    
   · 信号    · 信号量    · 信号量与PV操作    · 工作流    · 进程    · 进程间的同步    · 同步与互斥
 
       信号
        信号是当一个事件发生时产生的软中断,它将信号接收者从其正常的执行路径移开并触发相关的异步处理。本质上,信号通知其他任务或ISR运行期间发生的事件,与正常中断类似,这些事件与被通知的任务是异步的。信号的编号和类型依赖于具体的嵌入式系统的实现。通常,嵌入式系统均提供信号设施,任务可以为每个希望处理的信号提供一个信号处理程序,或是使用内核提供的默认处理程序,也可以将一个信号处理程序用于多种类型的信号。信号可以有被忽略、挂起、处理或阻塞等4种不同的响应处理。
 
       信号量
        为了同步一个应用的多个并发线程和协调它们对共享资源的互斥访问,内核提供了一个信号量对象和相关的信号量管理服务。信号量是一个内核对象,就像一把锁,任务获取了该信号量就可以执行期望的操作或访问相关资源,从而达到同步或互斥的目的。
        信号量可以分为如下3类:
        (1)二值信号量。二值信号量只能有两个值:0或1,当其值为0时,认为信号量不可使用。当其值为1时,认为信号量是可使用的。当二值信号量被创建时,既可以初始化为可使用的,也可以初始化为不可使用的。二值信号量通常作为全局资源,被需要信号量的所有任务共享。
        (2)计数信号量。计数信号量使用一个计数器赋予一个数值,表示信号量令牌的个数,允许多次获取和释放。初始化时,如果计数值为0,表示信号量不可用;计数值大于0,表示信号量可用。每获取一次信号量其计数值就减1,每释放一次信号量其计数值就加1。在有些系统中,计数信号量允许实现的计数是有界的,有些则无界。同二值信号量一样,计数信号量也可用做全局资源。
        (3)互斥信号量。互斥信号量是一个特殊的二值信号量,它支持所有权、递归访问、任务删除安全和优先级反转,以避免互斥固有的问题。互斥信号量初始为开锁状态,被任务获取后转到闭锁状态,当任务释放该信号量时又返回开锁状态。
        通常,内核支持以下几种操作:创建和删除信号量操作、获取和释放信号量操作、清除信号量的等待队列操作以及获取信号量信息操作。
 
       信号量与PV操作
        对于本知识点的考查,重点在于理解信号量与PV操作的基本概念,能够正确地理解在互斥、同步方面的控制应用,并能够灵活地运用,相对来说是个难点。
        在操作系统中,进程之间经常会存在互斥(都需要共享独占性资源时)和同步(完成异步的两个进程的协作)两种关系。为了有效地处理这两种情况,W. Dijkstra在1965年提出信号量和PV操作。
        (1)信号量:是一种特殊的变量,表现形式是一个整型S和一个队列。
        (2)P操作:S=S-1,若S<0,进程暂停执行,进入等待队列。
        (3)V操作:S=S+1,若S≤0,唤醒等待队列中的一个进程。
               互斥控制
               互斥控制是为了保护共享资源,不让多个进程同时访问这个共享资源,换句话说,就是阻止多个进程同时进入访问这些资源的代码段,这个代码段称为临界区,而这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥地进入自己的临界区,代码可以写为:
               
               由于只允许一个进程进入,因此信号量S的初值应该为1。该值表示可以允许多少个进程进入,当S<0时,其绝对值就是等待使用临界资源的进程数,也就是等待队列中的进程数。而当一个进程从临界区出来时,执行V操作(S=S+1),如果等待队列中还有进程(S≤0),则调入一个新的进程进入(唤醒)。
               同步控制
               最简单的同步形式是进程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个信号量来实现,如下表所示。
               
               生产者-消费者问题
               如果对缓冲区的读写无须进行互斥控制的话,那么就可以省去mutex信号量。
               理解PV操作
               信号量与PV操作的概念比较抽象,在历年的考试中总是难倒许多考生,其实主要还是没有能够正确地理解信号量的含义。
               (1)信号量与PV操作是用来解决并发问题的,而在并发问题中最重要的是互斥与同步两个关系,也就是说只要有这两个关系存在,信号量就有用武之地。因此,在解题时,应该先从寻找互斥与同步关系开始。这个过程可以套用简单互斥、简单同步、生产者-消费者问题。
               (2)通常来说,一个互斥或一个同步关系可以使用一个信号量来解决,但要注意经常会忽略一些隐藏的同步关系。例如,在生产者-消费者问题中,就有两个同步关系,一个是判断是否还有足够的空间给生产者存放产物,另一个是判断是否有足够的内容让消费者使用。
               (3)信号量的初值通常就是表示资源的可用数。而且通常对于初始为0的信号量,会先做V操作。
               (4)在资源使用之前,将会使用P操作;在资源用完之后,将会使用V操作。在互斥关系中,PV操作是在一个进程中成对出现的;而在同步关系中,则PV操作一定是在两个进程甚至是多个进程中成对出现的。
               实际应用
               在考试时,可能会出现一些需要综合应用的问题,需要考生根据基本的概念,结合实际问题进行解答。
               例如,在某并发系统中,有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1S2。发送进程不断地产生消息并写入缓冲区BUFFER,接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行,那么,当缓冲区的容量为N时,如何使用PV操作才能保证系统能够正常工作。发送进程A和接收进程B的工作流程如下图所示。请在下图中的①~④处填写正确的操作。
               
               PV操作实例一
               根据题意,很显然,这是一个“生产者-消费者”问题,根据该问题的特性,通常需要3个信号量来实现:两个用来管理缓冲区同步,信号量empty表示空闲缓冲区数量,初值为缓冲区最大数N,信号量full表示已填充缓冲区数量,初值为0;一个用于管理互斥,由信号量mutex保证只有一个进程在写缓冲区,初值为1。但在本题中,进程A和进程B允许并发地访问缓冲区,因此无须管理互斥,就不需要使用信号量mutex了。因此只需定义两个信号量:S1S2,初值为NS1在此承担的是信号量empty的功能,初值为0的S2在此则承担的是信号量full的功能。
               通过这样的分析,不难得出结论:①处应该是P(S1),将空闲缓冲区数量减1;②处应该是V(S2),将已填充的缓冲区数量加1;③处则是P(S2);④处为V(S1)。
               在这个例子的基础上,如果系统中有多个发送进程和接收进程,进程间的工作流程如下图所示,其中空①~④的内容与上图相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER,接收者进程顺序地从BUFFER中取消息,且每条消息只能读取一次。为了保证进程间的正确通信,增加了信息量SASB。请说明信息量SA和SB的物理意义,在下图中的⑤和⑥处填入正确的内容,并从下图的~①中选择4个位置正确地插入P(SA)、V(SA)、P(SB)和V(SB)。
               
               PV操作实例二
               上图所涉及的问题在普通的“生产者-消费者”问题上增加了一些复杂度:“系统中有多个发送进程和接收进程”,根据题意,我们可以得知它要完成的控制是:发送进程顺序写入,接收进程顺序读取,而且每条消息都只能够读取一次。这显然是两个互斥的问题,即多个发送进程在写缓冲区时是互斥关系,多个接收进程读缓冲区也是互斥关系。因此,信号量SASB分别实现这两个用来完成两个进程的互斥控制。
               (1)SA:初值为1,表示允许同时对缓冲区进行写操作的进程数量。
               (2)SB:初值为1,表示允许同时对缓冲区进行读操作的进程数量。
               当然,两个对调也是可以的。在发送进程和接收进程中分别有一组信号量SASB的PV操作。因此,接下来的问题就是找插入点。互斥控制的要点在于判断出临界区的范围,也就是哪部分程序必须互斥进入,否则将出现问题。根据这一点,可以进行如下分析。
               (1)发送进程:在进程产生消息之后准备写入缓冲区时,这时就需要进行互斥判断,因此在位置应插入P(SA);而直到完成“i=(i+1)mod N”操作后,才完成缓冲区操作,因此必须在位置插入V(SA)。
               (2)接收进程:由于接收进程是负责读数据的,如果数据区是空的则应该等待,因此必须先完成P(S2)操作,来决定其是否需要阻塞。如果没有阻塞时,再进入临界区,因此应该在位置处操作P(SB);而“对读取的消息进行处理”已显然在临界区之外,因此应该在位置插入V(SB)。
 
       工作流
               工作流的定义
               工作流(Workflow)是针对业务流程中具有固定程序的常规活动而提出的一个概念,通过将业务流程分解定义良好的任务、角色、规则和过程来进行执行和监控,达到提高生产组织水平和工作效率的目的,工作流技术为企业更好地实现经营目标提供了先进的手段。工作流要解决的主要问题是:为实现某个业务目标,在多个参与者之间,利用计算机,按某种预定规则自动传递文档、信息或者任务。
               一个工作流包括一组活动及它们的相互顺序关系,还包括过程及活动的启动和终止条件,以及对每个活动的描述。
               工作流管理系统
               工作流管理系统指运行在一个或多个工作流引擎上用于定义、实现和管理工作流运行的一套软件系统,它与工作流执行者(人、应用)交互,推进工作流实例的执行,并监控工作流的运行状态。
               工作流管理系统将业务流程中工作如何组织协调在一起的规则抽象出来,从而分离了具体工作的逻辑和流程组织的逻辑。我们在工作流管理系统的协助下:开发人员遵从一定的编程接口及约定,就可以开发出更具灵活性的事务处理系统;最终用户无需重新开发事务处理系统,就可以自己更改工作流程,以适应业务变化的需要。
               工作流管理系统可以描述不同覆盖范围和不同时间跨度的经营过程,根据经营过程以及组成活动的复杂程度,工作流管理系统可以采取多种实施方式,在不同实施方式中,所应用的信息技术、通信技术和支撑系统结构会有很大的差别,工作流管理系统的实际运行环境也可以在一个工作组内部,也可以在全企业所有业务部门。
               工作流管理系统在实际系统中的应用一般分为三个阶段:即模型建立阶段、模型实例化阶段和模型执行阶段。在模型建立阶段,通过利用工作流建模工具,完成企业经营过程模型的建立,将企业的实际经营过程转化为计算机可处理的工作流模型。模型实例化阶段完成为每个过程设定运行所需的参数,并分配每个活动执行所需要的资源,模型执行阶段完成经营过程的执行,在这一过程中,重要的任务是完成人机交互和应用的执行。
               工作流的功能
               工作流最大的优点是实现了应用逻辑与过程逻辑的分离,因此可以在不修改具体功能的实现情况下,通过修改过程模型来改变系统功能,完成对生产经营部分过程或全部过程的集成管理,有效地把人、信息和应用工具合理地组织在一起,发挥系统的最大效能。工作流技术可以支持企业实现对经营管理和生产组织的过程控制以及决策支持,实现现代企业对“在适当的时间把适当的信息传给适当的人”的要求。
               对于引入工作流的组织,能够在软件开发和业务两个层次受益。
               .方便开发,工作流管理系统能够简化企业级软件开发甚至维护。
               .降低开发风险——通过使用状态和动作这样的术语,业务分析师和开发人员使用同一种语言交谈。这样开发人员就不必将用户需求转化成软件设计了。
               .实现统一集中——业务流程经常变化,使用工作流系统的最大好处是:业务流程的实现代码,不再散落在各种各样的系统中。
               .加快应用开发——软件不用再关注流程的参与者,开发起来更快,代码更容易维护。
               .业务流程管理(BPM)——提高效率,在自动化过程中会去除一些不必要的过程。
               .提高对迭代开发的支持。
               如果软件中业务流程部分不容易更改,组织就需要花很大的精力在开发前的业务流程分析中,希望一次成功。但可悲的是,在任何软件项目开发中,这都很少能实现。工作流系统使得新业务流程很容易部署,业务流程相关的软件可以一种迭代的方式开发,因此使用工作流系统使开发更有效、风险更低。
 
       进程
        简单而言,一个进程就是一个正在运行的程序。一般来说,一个进程至少应该包括以下几个方面的内容。
        .相应的程序:进程既然是一个正在运行的程序,当然需要有相应程序的代码和数据。
        .CPU上下文:指程序在运行时,CPU中各种寄存器的当前值,包括:程序计数器,用于记录将要取出的指令的地址;程序状态字,用于记录处理器的运行状态信息;通用寄存器,用于存放数据或地址;段寄存器,用于存放程序中各个段的地址;栈指针寄存器,用于记录栈顶的当前位置。
        .一组系统资源:包括操作系统用来管理进程的数据结构、进程的内存地址空间、进程正在使用的文件等。
        进程有动态性、独立性和并发行三个特性。
        (1)动态性。进程是一个正在运行的程序,而程序的运行状态是在不断地变化的。例如,当一个程序在运行的时候,每执行完一条指令,PC寄存器的值就会增加,指向下一条即将执行的指令。而CPU中用来存放数据和地址的那些通用寄存器,它们的值肯定也不断地变化。另外,堆和栈的内容也在不断地变化,每当发生一次函数调用时,就会在栈中分配一块空间,用来存放此次函数调用的参数和局部变量。而当函数调用结束后,这块栈空间就会被释放掉。
        (2)独立性。一个进程是一个独立的实体,是计算机系统资源的使用单位。每个进程都有自己的运行上下文和内部状态,在它运行的时候独立于其他的进程。
        (3)并发性。从宏观上来看,在系统中同时有多个进程存在,它们相互独立地运行。
        下图表示四个进程A、B、C、D在系统中并发地运行。从中可以看出,虽然从宏观上来说,这四个进程都是在系统中运行,但从微观上来看,在任何一个特定的时刻,只有一个进程在CPU上运行。从时间上来看,开始是进程A在运行,然后是进程B在运行,然后是进程C和进程D。接下来又轮到了进程A去运行。因此,在单CPU的情形下,所谓的并发性,指的是宏观上并发运行,而微观上还是顺序运行,各个进程轮流去使用CPU资源。
        
        四个进程在并发运行
        在具体实现上,以CPU中的程序计数器PC为例,真正物理上的PC寄存器只有一个。当四个进程在轮流执行时,PC取值的运动轨迹是先在进程A内部流动,然后再到进程B的内部流动,再到进程C和D。从进程的独立性角度来说,每个进程都有“自己”独立的PC寄存器,即逻辑上的PC寄存器,它们的取值相互独立、互不影响。所谓的逻辑PC,其实就是一个内存变量。例如,在上图中,当进程A要执行的时候,就把A的逻辑PC的值拷贝到物理PC中,然后开始运行。当轮到B运行的时候,先把物理PC的当前值保存到A的逻辑PC中,然后再把B的逻辑PC的值装入到物理PC中,即可运行。这样就实现了各个进程的轮流运行。
 
       进程间的同步
        在计算机系统中,多个进程可以并发执行,每个进程都以各自独立的、不可预知的速度向前推进,但是需要在某些确定点上协调相互合作进程间的工作。例如,进程A向缓冲区送数据,进程B从缓冲区取数据加工,当进程B要取数据加工时,必须是进程A完成了向缓冲区送数据的操作,否则进程B必须停下来等待进程A的操作结束。
        可见,所谓进程间的同步是指在系统中一些需要相互合作,协同工作的进程,这样的相互联系称为进程的同步。
 
       同步与互斥
        同步是合作进程间的直接制约问题,互斥是申请临界资源进程间的间接制约问题。
               进程间的同步
               在计算机系统中,多个进程可以并发执行,每个进程都以各自独立的、不可预知的速度向前推进,但是需要在某些确定点上协调相互合作进程间的工作。例如,进程A向缓冲区送数据,进程B从缓冲区取数据加工,当进程B要取数据加工时,必须是进程A完成了向缓冲区送数据的操作,否则进程B必须停下来等待进程A的操作结束。
               可见,所谓进程间的同步是指在系统中一些需要相互合作,协同工作的进程,这样的相互联系称为进程的同步。
               进程间的互斥
               进程的互斥是指系统中多个进程因争用临界资源而互斥执行。在多道程序系统环境中,各进程可以共享各类资源,但有些资源一次只能供一个进程使用,称为临界资源(Critical Resource,CR),如打印机、共享变量和表格等。
               临界区管理的原则
               临界区(Critical Section,CS)是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下:
               (1)有空即进。当无进程处于临界区时,允许进程进入临界区,并且只能在临界区运行有限的时间。
               (2)无空则等。当有一个进程在临界区时,其他欲进入临界区的进程必须等待,以保证进程互斥地访问临界资源。
               (3)有限等待。对于要求访问临界资源的进程,应保证进程能在有限的时间进入临界区,以免陷入“饥饿”状态。
               (4)让权等待。当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入忙等状态。
   题号导航      2015年下半年 系统架构设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第1题    在手机中做本题