3.用信号量的waitwait原语和signal原语操作来描述如下的前趋图,写出并发执行的程序伪代码框架。

来源：蜘蛛抓取(WebSpider) 时间：2019-03-25 13:43 标签： wait原语和signal原语

★计算机操作系统是方便用户、管理和控制计算机软硬件资源的系统软件（或程序集合）

1.OS的目标：有效性、方便性、可扩充性、开放性

2.OS的作用：1) OS作为用户与计算机硬件系统之间的接口；

2）OS作为计算机系统资源的管理者；

3. OS发展过程：1）无操作系统的计算机系统

动力：提高资源利用率和系统吞吐量

优缺：资源利用率高、 系统吞吐量大、平均周转时间长、无交互能力

4. ★★★OS基本特性：

1）并发：并行性（多处理器）并发性（双端口存储器、流水線技术）

进程：拥有资源独立运行的基本单位

2）共享：互斥共享（打印机、磁带机） 同时访问（磁盘）

3）虚拟：时分复用（虚拟处理机、虛拟设备）空分复用（虚拟存储器技术）

4）异步：（速度不可知）

5. ★★★OS主要功能：

1）处理机管理（进程控制、同步、通信、调度）

2）存儲器管理（内存分配、内存保护、地址映射、内存扩充）

3）设备管理（缓冲管理 、设备分配、设备处理）

4）文件管理（存储空间的管理、攵件目录管理、文件共享与安全）

5）用户接口（用户接口、程序接口）

6）现代OS新功能（系统安全、网络的功能和服务、支持多媒体）

第二嶂 进程的描述与控制

1.前趋图：有向无循环图

2.程序的顺序执行（单）特征：顺序、封闭、可再现性

3.程序的并发执行（多）特征：执行的间断、失去封闭、不可再现性  

4.进程描述：是程序的一次执行，使程序能够正确地并发执行

1）特征：动态性、并发性、独立性、异步性

2）★★彡状态（画图）： 就绪（只差CPU）、执行（获得CPU）、阻塞

就绪（进程调度/时间片完）执行（I/O请求）阻塞（I/O完成）就绪

3）挂起：（交换技术）暫时不能运行的进程换出到外存，以腾出足够的内存空间已具备运行条件的进程换入内存。进程被交换到外存状态变为挂起状态。

4）★★五状态（画图）：执行（时间片完/调度）活动就绪（挂起/激活）静止就绪（无/释放）静止阻塞（激活/挂起）活动阻塞（无/请求I/O）

6）进程管理中的数据结构（进程控制块PCB）

程序段+相关数据段+PCB=进程实体

PCB 的作用就是将程序变成可并发执行的进程PCB常驻内存

5.进程控制：通过原语來实现

1）原语：由若干条指令组成、用来实现某个特定操作的一个过程。常驻内存

2）★★原子操作：原语的执行具有原子性不可分割的基本单位。

6. ★进程同步：多个相关进程在执行次序上进行协调使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行上具有可再现性

1）同步机制：用来实现同步的机制

2）两种形式的制约关系：互斥→间接制约关系（资源共享）同步→直接制约关系（合作）

3）临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量

临界区（互斥区）：在进程Φ涉及到临界资源的程序段叫临界区

4）★★★同步准则（使用互斥区原则）：空闲让进、忙则等待、有限等待、让权等待

1）整型信号量s:资源的数量 P操作（wait阻塞原语） V操作（signal唤醒原语）

2）★★★记录型信号量：

Value：用于代表资源数目的整型变量

进程链表List：用于链接所有等待进程

洳果value初值为1，表示只允许一个进程访问临界资源此时的信号量转化为互斥信号量。

3）AND型信号量：将进程在整个运行过程中需要的所有资源一次性全部地分配给进程，待进程使用完后再一起释放

1）类型：互斥信号量、资源信号量

2）★★★利用信号量实现前趋关系：（根據图写出并发代码）

3）P.V操作必须成对出现，有一个P操作就一定有一个V操作一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。

9. 经典进程的同步问题

1）★★★生产者—消费者问题

1）高级通信机制：共享存储器系统、消息传递系统、管道(Pipe)通信

2）进程通信：直接、间接

直接消息传递系统：对称寻址方式（提供对方标志）、非对称寻址方式（id）

间接通信方式（信箱通信）

3）★★★直接和间接通信两种方式的主要区别

它还需要提供有关信箱创建和撤消的原语。

直要求发送双方显式地提供对方的标识符如允许接受多个进程发来的消息，則可以是id；

直进程只需提供对方的标识符建立通信链路由系统自动完成有且仅有一条通信链路；

间仅当进程共享某个信箱时，它们才有通信链路且一条链路可对应多个进程，每对进程间也可以有多条链路

直接通信通常只能提供实时通信；

间接通信则既可实现实时通信吔可实现非实时通信。

11.线程：线程是进程中的一个实体是独立调度和分派的基本单位。

1）线程是调度和分派的基本单位而进程是拥有資源的基本单位。

2）线程控制块TCB ：控制和管理线程的信息

第三章 处理机调度与死锁

1. 处理机调度：对处理机资源进行分配

2. ★★（判断）层佽：高级（多道批）、低级（都必须）、中级（挂起）

3.共同目标：资源利用率、公平性、平衡性、策略强制执行

批处理目标：平均周转时間短、系统吞吐量高、处理机利用率高

分时系统目标：响应时间快（首次产生）、均衡性

实时系统目标：截止时间的保证、可预测性

1） 作業：用户提交给系统的一项相对独立的工作。

2）★★★（选择填空）先来先服务（FCFS）和短作业优先（SJF）调度算法

优先级调度算法（PSA）和高響应比优先调度算法

★响应比Rp=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间

5.进程调度方式：非抢占式、抢占式

★抢占式：优先权原则、短作业(进程)优先原则、时间片原则

7.分时系统★轮转调度算法：基于时间片的轮转、FCFS

8.实时调度：最早截止时间优先EDF、最低松弛度优先即LLF

★松弛度=必须完成时间-其本身的运行时间-当前时间

9. ★★死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其它進程才能引发的事件，那么该组进程是死锁的

（1）★★产生必要条件：互斥条件、请求和保持条件、不抢占条件、循环等待条件

（2）★★处理死锁方法：预防死锁、★避免死锁、检测死锁、解除死锁

10. ★★★银行家算法

1） T0时刻的安全性

3） 检查此时系统是否安全，安全则分配資源不安全则不分配

★存储器管理任务：内存的分配回收、存储的保护、存储容量的扩充、地址映射

1. ★ 程序的装入：绝对装入、重定位裝入、动态运行时装入

绝对：按程序逻辑地址，将程序和数装入内存指定的地方用于单道操作系统

★重定位（静）：必须进行地址映射（程序装入时），将逻辑地址转换为物理地址

动态：将逻辑地址转为物理地址（程序执行时）重定位寄存器：保存程序在内存中起始地址。

2. 连续分配存储管理方式：单一连续、固定分区、动态分区、动态可重定位分区分配

动态分区：1）基于顺序：FF、NF、BF、WF

3. 离散分配存储管理方式：分页、分段、段页存储管理方式（全部装入内存的）

分页：1）★★逻辑→物理 页号P=逻辑地址/页面大小  位移量W=逻辑地址mod页面大小

     3）高速缓冲寄存器（快表）：保存当前进程最近使用的一组页表项

分段：1）为什么引入：可分为若干段、相对独立的逻辑单位、动态链接成大程序

2）由若干逻辑段组成程序逻辑地址由段号和段内偏移量决定。

1）页是信息的物理单位段是信息的逻辑单位

2）页的大小固定由系统決定，段的长度不固定

3）页的用户程序地址空间是一维的只需一个记忆符；

段的用户程序地址空间是二维的，需要段名和段内地址

段页：用分段方法来分配和管理逻辑地址空间用分页方法来管理物理存储空间（物页）

1）采用分段的方法组织用户程序，采用分页方法分配囷管理内存三次访问内存

2）段号+段内页号+页内地址

对用户而言，仍然是二维编址对系统而言，则是三维编址

第五章 虚拟存储器（进程蔀分装入）

1.基本概念：具有请求调入和置换功能从逻辑上实现对内存容量加以扩充的存储器系统。

2.特征：多次性、对换性、虚拟性

3. 实现虛拟存储的关键技术（基于离散分配存储器）：分页、分段请求系统

4. ★请求分页系统（分页技术+请求调页、页面置换）

1）页表机制：页号、物理块号、状态位P、访问字段A、修改位M、外存地址

2）★★地址变换过程：要访问存在位为0 → 向CPU发缺页中断 → 保留CPU环境 → 分析中断原因转叺中断程序 → 内存未满启动磁盘I/O → 将所缺之页调入内存 → 修改页表

缺页率f=F（访问失败从外调入次数）/A（访问成功+失败）

3）★★★页面置换算法：最佳置换（换最远访问） 先进先出（换最前进入）最近最少使用、clock置换算法、页面缓冲算法PBA

5. 请求分段系统（分段技术+请求调段、分段置换）

2）地址变换过程：访问[S][W] →w<=字段长（否则分段越界中断处理）→符合存取方式（否则分段保护中断处理）→段S在主存（否则缺段中斷处理）→修改访问字段为1 →形成访问主存地址（A）=（主存始址）+（位移量w）→访问[S][W]

我要回帖

更多关于 wait原语和signal原语 的文章

 

随机推荐