操作系统作业5

矫情吗；* 2021-12-24 03:13 322阅读 0赞

**第五章作业**

**5.1**

题目：In Section 5.4, we mentioned that disabling interrupts frequently can affect the system’s clock. Explain why this can occur and how such effects can be minimized.

回答：

时钟以固定的周期时间间隔产生中断，此时，操作系统将其存储时间值增加一定的量。

但是如果中断被禁用，这种增加就不发生了，并且时间也将是不正确的。也就是说时钟丢失了正确的时间。

另外，在调度过程中，每一次时钟中断，调度器都要来验证当前的时间片有没有走完。如果没有中断，调度器就无法准确分配时间。

在信号量的实现中，也可以通过启用和禁用中断来实现而不是忙等待，或者使用test或者set指令而不是中断来减少影响。

**5.2**

题目：Explain why Windows, Linux, and Solaris implement multiple locking mechanisms. Describe the circumstances under which they use spin- locks, mutex locks, semaphores, adaptive mutex locks, and condition variables.In each case, explain why the mechanism is needed.

回答：

在各种操作系统（windows，linux或solaris）中，有多道程序设计和多处理。在这里，有各种各样的线程同时工作以完成任务，有一个多线程在共享内存上工作。所以维护数据的原子性非常重要，也就是说如果某个人正在处理某些内存地址，那么就不能有其他人可以访问它。

于是就有了多种锁定机制：根据要求使用各种类型的锁。但是所有锁的主要目的是相同的：

一个线程正在处理某内存位置，那么首先它将锁定该位置，然后执行其任务，然后它将释放锁，以便其他线程可以访问它。

*spin locks*自旋锁适用于多处理器系统，自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁。

*mutex locks*互斥对锁定资源是有用的，能用于交互上下文但是不能用于中断上下文，同一时间只能有一个任务持有互斥锁，而且只有这个任务可以对互斥锁进行解锁。

*semaphorse*用于线程间通信*。*

*adaptive mutex locks*大多数操作系统都使用。想法是在尝试访问由当前运行的线程锁定的资源时使用自旋锁，但是如果线程当前没有运行则要休眠。

*condition variables*条件变量是与监视器关联的线程队列，线程可以在该队列上等待某些条件变为真。多个条件变量可以与同一个互斥锁相关联。

当资源必须被长时间保存时，信号量和条件变量是更合适的同步工具，因为长时间旋转是不合适的。

**5.4**

题目：Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.

回答：

如果一个高优先级的线程声明一个低优先级线程已经拥有的自旋锁，那么它将永远循环：低优先级线程永远不会再有机会运行和释放。（即使两个线程以相同的优先级运行，试图声称自旋锁的那个线程也会旋转，直到用完时间片并且浪费了大量的cpu时间：**自旋锁消耗****cpu****资源**。）如果一个中断处理程序试图声称一个拥有的自旋锁线程，中断处理程序也将永远循环。在多处理器设置中，自旋锁更合适，因为多个CPU在多处理器系统中上下文更改的代价更高，可能超出自旋锁的成本；而使用自旋锁，其他进程在其他处理器上执行，从而修改程序状态，来从自旋锁中释放第一个进程。

**5.7**

题目：Race conditions are possible in many computer systems. Consider a banking system that maintains an account balance with two functions: deposit(amount) and withdraw(amount). These two functions are passed the amount that is to be deposited or withdrawn from the bank account balance. Assume that a husband and wife share a bank account. Concurrently, the husband calls the withdraw() function and the wife calls deposit(). Describe how a race condition is possible and what might be done to prevent the race condition from occurring.

回答：分成两部分回答：

**Describe how a race condition is possible**

这里bank account是两个进程之间的共享变量。

当两个进程都尝试使用共享变量余额时，就会出现竞争条件。

也就是说两个或多个线程可以访问共享数据的同时，在同一时间，他们都要对数据做更改，所以竞争会产生意外的结果。

举个例子：

假设股票账户最初有5000余额，现在双方要做申请：

首先，丈夫读出存款为5000，然后他要取走2000。

这个时候丈夫的时间片用完（他还没取钱）

妻子开始读，存款是5000，然后她要存钱，存了4000。所以目前账户里有9000，她还没保存现在的余额的时候，她的时间片也用完了。

这个时候又轮到丈夫操作了，他之前读的是5000，然后取走2000，账户余额就变成3000了。

但是重点是，账户的余额应该是5000+4000-2000=7000。

这就出现了错误。

**what might be done to prevent the race condition from occurring.**

首先，可以锁定共享资源，只有在获得锁定之后才可以使用并且要通知其他人这个进程正在进行中。

或者不要将金额数据声明为全局变量。而该将它声明为取款和存入函数的局部变量。

或者书上写的皮特森算法，让一次只有一个线程进入临界区。一旦线程进入临界区，它就被锁定，除非该线程自己释放锁，否则其他线程不能访问临界区。于是临界区一次只执行一个线程。

**5.9**

题目：The first known correct software solution to the critical section problem for n processes with a lower bound on waiting of n − 1 turns was presented by Eisenberg and McGuire. The processes share the following variables:

All the elements of flag are initially idle. The initial value of turn is immaterial (between 0 and n-1). The structure of process Pi is shown in Figure 5.22. Prove that the algorithm satisfies all three requirements for the critical-section problem.

回答：首先，all three requirements for the critical-section problem是：

//  main.cpp

//  操作系统第五章

//  Created by zsy on 2018/10/24.

\#include <stdio.h>

\#include <pthread.h>

\#define n 10

pthread\_mutex\_tlock;

enumpstate\{idle,want\_in, in\_cs\};

enumpstateflag\[n\];

intturn =0;

void\* thread(void\* arg)

inti =0 , j=0;

do\{

while(1)

flag\[i\] = want\_in;

j = turn;

while(j != i)

if(flag\[j\] != idle)

j = turn;

else

j= (j+1)%n;

flag\[i\] = in\_cs;

j=0;

while((j<n) && (j == i || flag\[j\] != in\_cs))

j++;

if( (j >= n) && (turn== i || flag\[turn\] == idle))

break;

pthread\_mutex\_lock(&lock);

j = (turn\+ 1) %n;

while(flag\[j\] == idle)

j = (j+1) % n;

turn=j;

flag\[i\] = idle;

pthread\_mutex\_unlock(&lock);

\}while(1);

//pthread\_exit(NULL);

intmain(void)

pthread\_tt\[n\];

inti =0;

for(i=0; i <n;i++)

pthread\_create(&t\[i\], NULL, thread,NULL);

for(i=0; i <n;i++)

pthread\_join(t\[i\], NULL);

进程要想进入临界区的话，首先设置flag\[i\] = want\_in;然后更新给incs，然后要检查有没有其他进程已经把incs给更新了。

如果不空闲，而且这个进程要进入临界段的话，

当flag\[turn\]是空闲的之后，就跳出循环进入临界段。

单独证明：

**Mutual exclusion**:

首先，假定P1已经进入了临界区了。P2想要进入

他要进来的话肯定要经过while语句。

可以看出来，P1在临界区里面的时候，P2是一直在while里面出不来的。

所以能够保证互斥。

**Progress:**

假如Turn=2

P2将在if语句中为false，因此它在外部while循环中不执行任何操作一直循环循环。

P1会进入关键部分，在里面这个while循环里面循环下去直到时间片用完。

但是P2如果进入关键部分（死锁）。它将设置turn = 1，让P1退出内部的while，并清除自己的标志，消除潜在的死锁。

**Bounded waiting:**

P1结束之后，会设置turn=2，flag【1】=idle

这样就不会让P2饥饿了，因为下一个进入临界区的就是P2了。

**5.10**

题目：Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.

回答：如果用户级程序能够禁用中断，那么它也可以禁用定时器中断，那么对上下文切换就会有很大的影响：比如让一个进程使用CPU而不让其他进程执行

**5.37**

题目：Assume that a finite number of resources of a single resource type must be managed. Processes may ask for a number of these resources and will return them once finished. As an example, many commercial software packages provide a given number of licenses, indicating the number of applications that may run concurrently. When the application is started, the license count is decremented. When the application is terminated, the license count is incremented. If all licenses are in use, requests to start the application are denied. Such requests will only be granted when an existing license holder terminates the application and a license is returned.

The following program segment is used to manage a finite number of instances of an available resource. The maximum number of resources and the number of available resources are declared as follows:

When a process wishes to obtain a number of resources, it invokes the decrease\_count() function:

The preceding program segment produces a race condition. Do the following:

1.  Identify the data involved in the race condition.
2.  Identify the location (or locations) in the code where the race condition occurs.
3.  Using a semaphore or mutex lock, fix the race condition. It is permissible to modify the decrease count() function so that the calling process is blocked until sufficient resources are available.

回答：

感觉题目很像生产者消费者问题

1.  1.  1.  Identify the data involved in the race condition.

它会++或者--，所以涉及到race。

减的时候available\_resources-=count在decrease\_count

增的时候available\_resources+=count在increase\_count

两个进程同时访问和操作相同的数据，执行的结果取决于访问发生的特定顺序。

1.  1.  1.  Identify the location (or locations) in the code where the race condition occurs.

这两个函数里race condition occurs。

1.  1.  1.  Using a semaphore or mutex lock, fix the race condition. It is permissible to modify the decrease count() function so that the calling process is blocked until sufficient resources are available.

为了防止竞争条件，使用信号量变量互斥，同时阻止访问变量可用资源。初始化为1。

在访问共享变量互斥之前，mutex减少。然后修改共享变量。之后，mutex递增。当一个进程正在访问共享变量时，如果其他进程请求这个共享变量，则必须执行等待操作。然后，第二个进程等待，直到第一个进程执行完并增加信号量变量互斥量的值。

semaphore mutex = 1;

intdecrease\_count(intcount)

if(available\_resources >= count)

wait(&mutex);

available\_resources -= count;

signal(&mutex);

return1;

return0;

semaphore mutex = 1;

voidincrease\_count(intcount)

wait(&mutex);

available\_resources += count;

signal(&mutex);

**5.41**

题目：A barrier is a tool for synchronizing the activity of a number of threads. When a thread reaches a barrier point, it cannot proceed until all other threads have reached this point as well. When the last thread reaches the barrier point, all threads are released and can resume concurrent execution.

Assume that the barrier is initialized to N—the number of threads that must wait at the barrier point:

Each thread then performs some work until it reaches the barrier point:

Using synchronization tools described in this chapter, construct a barrier that implements the following API:

1.  int init(int n)—Initializes the barrier to the specified size.
2.  int barrier\_point(void) — Identifies the barrier point. All threads are released from the barrier when the last thread reaches this point.

The return value of each function is used to identify error conditions.Each function will return 0 under normal operation and will return −1 if an error occurs.A testing harness is provided in the source code download to test your implementation of the barrier.

回答：

//  main.cpp

//  操作系统第五章

//  Created by zsy on 2018/10/24.

\#ifndef \_REENTRANT

\#define \_REENTRANT

\#endif

\#include <pthread.h>

\#include <stdio.h>

/\*对于Linux \*/

\#include <stdlib.h>

\#define SHARED 0

\#define MAXSIZE 100/\*最大矩阵大小\*/

\#define MAXws 4/\*最大工作人数\*/

intcntws;

intcntreachd = 0; /\*已抵达的人数\*/

/\*障碍开始\*/

\#include <semaphore.h>

intcount = 0; /\*计数\*/

sem\_treach, start; /\* 信号量\*/

/\* 初始化障碍的功能。比在main（）\*/

voidbar\_init(void) \{

count= 0;

sem\_init(&reach, 0, 1);

sem\_init(&start, 0, 0);

/\* 屏障功能。参数是在释放障碍之前到达的人数量\*/

voidbar(inth) \{

inti;

sem\_wait(&reach);

++count;

if(count== h) \{

printf("一个人正在做障碍\\n");

for(i = 0; i < h-1; ++i)

sem\_post(&start);

sem\_post(&reach);

return;

sem\_post(&reach);

printf("在等待\\n");

sem\_wait(&start);

printf("开始!\\n");

/\* Destroy the bar. \*/

voidbar\_destroy(void) \{

sem\_destroy(&reach);

sem\_destroy(&start);

/\*结束屏障\*/

/\* 重复使用的反屏障\*/

intsize, size\_; /\* assume size is multiple of cntws \*/

intsums\[MAXws\];

intmatrix\[MAXSIZE\]\[MAXSIZE\];

void\*Temp(void\*);

/\* 读命令行，初始化和创建线程\*/

intmain(intargc, char\*argv\[\]) \{

inti, j;

pthread\_attr\_tattr;

pthread\_ttempid\[MAXws\];

/\*启动障碍\*/

bar\_init();

/\*设置全局线程属性\*/

pthread\_attr\_init(&attr);

pthread\_attr\_setscope(&attr, PTHREAD\_SCOPE\_SYSTEM);

size= (argc > 1)? atoi(argv\[1\]) : MAXSIZE;

cntws= (argc > 2)? atoi(argv\[2\]) : MAXws;

if(size> MAXSIZE) size= MAXSIZE;

if(cntws> MAXws) cntws= MAXws;

size\_= size/cntws;

/\*初始化矩阵\*/

for(i = 0; i < size; i++)

for(j = 0; j < size; j++)

matrix\[i\]\[j\] = 1;

printf("大小是：%d工作人数是: %d\\n", size, cntws);

/\*创建然后退出\*/

for(i = 0; i < cntws; i++)

pthread\_create(&tempid\[i\], &attr, Temp, (void\*) i);

pthread\_exit(NULL);

/\* 每个工人将矩阵的一个strip中的值相加。在屏障之后，temp（0）计算并打印总合\*/

void\*Temp(void\*arg) \{

uintptr\_tid\_ = (uintptr\_t) arg;

intzong, i, j, fst, lst;

printf("第%lu 个(pthread id %d) 开始\\n", id\_, pthread\_self());

/\*确定第一行和最后一行\*/

fst = id\_\*size\_;

lst = fst + size\_\- 1;

/\*总和\*/

zong = 0;

for(i = fst; i <= lst; i++)

for(j = 0; j < size; j++)

zong += matrix\[i\]\[j\];

sums\[id\_\] = zong;

/\*调用屏障\*/

bar(cntws);

if(id\_ == 0) \{

zong = 0;

for(i = 0; i < cntws; i++)

zong += sums\[i\];

printf("总和是%d\\n", zong);

/\* 最后一个摧毁障碍\*/

bar\_destroy();

returnNULL;

最大工作人数设置为4

操作系统作业5

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关操作系统-作业管理

相关操作系统作业 - 进程调度

相关操作系统作业9

相关操作系统作业8

相关操作系统作业6

相关操作系统作业5

相关操作系统作业4

相关操作系统作业3

相关操作系统作业2

相关操作系统作业1