操作系统概念第六章部分作业题答案

操作系统概念第六章部分作业题答案题目一:如果将peterson算法中的flag[i]=true与turn=j两条语句交换顺序,会导致求解临界区问题所需三个要求(互斥、有空让进、有限等待)中的哪些要求得不到满足?请举例并分析说明得不到满足的情况解答:假设两个进程i和j:进程i的进入区代码是这样的flag[i]=TRUE;turn=j;while(flag[j]==TRUE&&…

大家好,又见面了,我是你们的朋友全栈君。

题目一:

如果将 peterson 算法中的 flag[i] = true 与 turn = j 两条语句交换顺序,会导致求解临界区问题所需三个要求(互斥、有空让进、有限等待)中的哪些要求得不到满足?请举例并分析说明得不到满足的情况
解答:
假设两个进程i和j:
进程i的进入区代码是这样的
flag[i] = TRUE;
turn = j;
while(flag[j] == TRUE && turn == j);
进程j的进入区代码是这样的:
flag[j] = TRUE;
turn = i;
while(flag[i] == TRUE && turn == i);
如果进程i和进程j已经在并发执行了,它们的调度顺序是未知的,假设程i先执行,那么它会先将turn“谦让”地设置为j,但接下来轮到进程j执行了,它也“谦让”地将turn设置为i。这时又轮到了进程i执行了,而且我们可以发现,while中第二个条件已经不满足了!这时进程i就进入了临界区!
如果顺序颠倒,总共会六种可能的语句组合情况:
在这里插入图片描述
如果仅仅从结果来看,似乎六种情况都满足三个条件:
在这里插入图片描述
但如果考虑中间能够进入临界区的情况,那么情况三和情况四将会不满足互斥条件,进程i与进程j将有可能同时进入临界区:
在这里插入图片描述
所以,会存在不满足互斥的情况,所以不可以。

题目二:

试分析说明为何自旋锁(spinlocks)不适合单处理器系统但却常用于多处理器系统。
解答:
在单处理机环境中可以使用硬件提供的swap指令或test_and_set指令实现进程互斥,这些指令涉及对同一存储单元的两次或两次以上操作,这些操作将在几个指令周期内完成,但由于中断只能发生在两条机器指令之间,而同一指令内的多个指令周期不可中断,从而保证swap指令或test_and_set指令的执行不会交叉进行。
但在多处理机环境中情况有所不同,例如test_and_set指令包括“取”、“送”两个指令周期,两个CPU执行test_and_set(lock)可能发生指令周期上的交叉,假如lock初始为0, CPU1和CPU2可能分别执行完前一个指令周期并通过检测(均为0),然后分别执行后一个指令周期将lock设置为1,结果都取回0作为判断临界区空闲的依据,从而不能实现互斥。
为在多CPU环境中利用test_and_set指令实现进程互斥,硬件需要提供进一步的支持,以保证test_and_set指令执行的原子性. 这种支持目前多以“锁总线”(bus locking)的形式提供的,由于test_and_set指令对内存的两次操作都需要经过总线,在执行test_and_set指令之前锁住总线,在执行test_and_set指令后开放总线,即可保证test_and_set指令执行的原子性。

题目三:

请用比较并交换指令(compare_and_swap())实现互斥锁机制。互斥锁包含的数据结构及函数如下所示,其中 available == 0 表示锁可用,available == 1 表示锁不可用。
typedef struct {

int available ;
} lock ;
void acquire ( lock *mutex ) ;
void release ( lock *mutex ) ;
解答:
互斥锁是指当一个线程尝试获取某个锁时,如果该锁已被其他线程占用,该线程挂起或睡眠。互斥锁适用于临界区持锁时间比较长的操作,比如下面这些情况都可以考虑:
·临界区有IO操作
·临界区代码复杂或者循环量大
·临界区竞争非常激烈
·单核处理器
CAS(compare and swap),它通过原子操作交换两个变量的值来达到对变量的修改。我们可以把它看作是 i = i+1 这个表达式的原子操作版本。它的实现类似如下:
int compare and swap(int *value, int expected, int new_value) {

int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
在一些线程库里面,mutex 是最简单的一种锁,也是最常见的锁。它的作用主要是对一段临界区上锁,对其他试图访问已经上锁的资源禁止访问。因此 mutex 也叫互斥锁,它的是英文单词 mutual exclustion 的缩写。mutex 可以使用 SAS 或 CAS 来实现:
mutex 通过让试图获取的锁的执行单元进入到一个等待队列里排队,当锁用完了以后再把等待的执行单元拿出来获取锁并继续执行:
void acquire (){

if(lock->available){

//把当前的执行单元加入到等待队列
add_process_to_waitlist(current_pocess)
sleep()//休眠
}
}
void release (){

compare_and_swap(lock,1,0)
//唤醒休眠的线程
wakeup_process()
}
顺便,写一下自旋锁,自旋锁之所以被叫做自旋锁,就是因为他会在锁被其他占用的时候会一直循环,不断地询问锁是否打开,也就是所谓的轮询,即:如果一个执行单元锁住了一块资源,另一个执行单元试图进入会一直轮询知道获取到锁为止:
void acquire (){

while(lock->available)//轮询
;
}
void release (){

compare_and_swap(lock,1,0)
}

题目四:

理发师问题:理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客,理发师便在理发椅上睡觉。当一个顾客到来时,它必须叫醒理发师。如果理发师正在理发时又有顾客到来,如果有空椅子可坐,就坐下来等待,否则就离开。请用信号量机制(wait(),signal())来解决上述问题。
解答:
首先设置一个count表示等待的人数(包括理发椅上的那个人),初值为0,以供后来者判断是否应该离开。同时对count的访问要保证互斥,所以设置mutex信号量来保证互斥,初值为1。
临界资源:凳子,理发椅。 分别设置waitchair,barchair信号量,初值分别为n和1,表示临界资源数量。
同步关系:顾客和理发师之间有同步关系,用ready和done信号量来表示,初值均为0,ready表示顾客有没有准备好,done表示理发师是否完成一次理发。
注意:并非每一个进程都需要while(1)无限循环,比如此例,顾客剪完一次头发就走了,不可能马上再来剪,而以前的生产者-消费者不同,他们都是可以不断生产消费的。
Semaphore waitchair = n;
Semaphore barchair = 1;
Semaphore ready = done = 0;
int count = 0;
Semaphore mutex = 1;
barber:
while(1) {

wait(ready);
理发
signal(done);
}
consumer:
wait(mutex);
if(count <= n) {

count = count + 1;
signal(mutex);
}
else {

signal(mutex);
离开
}
wait(waitchair);
wait(barchair);
signal(waitchair); //离开等待椅去理发椅需要释放等待椅!
signal(ready); //准备好了
wait(done); //等待理发完成
signal(barchair);
wait(mutex);
count = count – 1;
signal(mutex);
离开

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159080.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • graph representation learning_with for什么意思

    graph representation learning_with for什么意思刷新三数据集纪录的跨镜追踪(行人再识别-ReID)技术云从科技在跨镜追踪(行人再识别)技术(ReID)上获取重大突破。同时在Market-1501,CUHK03,DukeMTMC-reID三个数据集刷新了世界纪录,其中最高在Market-1501上的首位命中率(Rank-1Accuracy)达到96.6%,让跨镜追踪(ReID)在准确率上首次达到商用水平,人工智能即将从「刷脸」跨到「识人」的新纪…

  • Kettle工具入门[通俗易懂]

    Kettle工具入门[通俗易懂]Kettle工具入门Kettle工具入门 Kettle是什么? 为什么要用Kettle? 怎么用Kettle? 下载运行 简单应用 表到表转换 json到表的操作 参考 Kettle是什么?Kettle是水壶。“多喝热水”是我们对女朋友美好的祝福。因为未经处理的生水(原始数据),含有各种杂质(脏数据),无法直接饮用(入…

    2022年10月17日
  • linux清屏命令[通俗易懂]

    1)clear这个命令将会刷新屏幕,本质上只是让终端显示页向后翻了一页,如果向上滚动屏幕还可以看到之前的操作信息。一般都会用这个命令。(2)reset这个命令将完全刷新终端屏幕,之前的终端输入操作信息将都会被清空,这样虽然比较清爽,但整个命令过程速度有点慢,使用较少。(3)另外介绍一个用别名来使用清屏命令的方法,如下:[root@localhost~]$aliascls=‘clea…

  • 164. 可达性统计(拓扑排序+数位dp)[通俗易懂]

    164. 可达性统计(拓扑排序+数位dp)[通俗易懂]给定一张 N 个点 M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。输入格式第一行两个整数 N,M,接下来 M 行每行两个整数 x,y,表示从 x 到 y 的一条有向边。输出格式输出共 N 行,表示每个点能够到达的点的数量。数据范围1≤N,M≤30000输入样例:10 103 82 32 55 95 92 33 94 82 104 9输出样例:1633211111#include<bits/stdc++.h>using

  • Winrar去广告图文教程「建议收藏」

    Winrar去广告图文教程「建议收藏」一、前言1.1Winrar解压缩工具  市场上有很多优秀的压缩工具,常用的有Winrar和360压缩工具。Winrar是免费压缩工具,特色是每次使用都会弹出广告。影响用户体验和工作效率,当然最重要的是影响心情。效果如下图。图1-1、Winrar弹广告效果图二、问题处理说明2.1问题解决方式  此处使用工具Resourcehacker对winrar.e…

  • unity3d的入门教程_Unity3D缺点

    unity3d的入门教程_Unity3D缺点Unity3D新手入门初级教程U3D是由UnityTechnologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。可发布游戏至Windows、Mac、Wii、iPhone、Windowsphone8和Android平台。也可以利用Unitywebplayer插件发布网页游戏,支持Mac和Windows的网页浏览。它的网页播放器也被Macwidgets所支持!U3D现已经占领了国内85%的手游

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号