网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
大连交通大学网络...吧 关注：172贴子：311
  • 1回复贴，共1页

信号量习题及答案

写出用DOWN（P）、UP（V）原语实现两个进程（进程PA和进程PB）互斥进入临界区C的算法，说明所用信号量各种可能取值的含义，并注明相关信号量的初值。
Answer:
semaphore mutex=1;
void process (void) //process A or B
{
    while (TRUE)  
    {    
          Down (&mutex);
          Enter-Critical-Section-C();
          Up (&mutex);
          Non-critical-section();
     }
}
某宾馆门前有一出租汽车停车位，假设宾馆每一位顾客出门都要乘坐出租车，并且对顾客约定：如果有其它顾客在此停车位等车则在旁等待；否则在此等车；此停车位有车则乘坐。对出租车做出约定：如果此停车位已停有车，则等待此停车位空闲；否则停到此停车位等待顾客；有顾客则搭载顾客离开。试用DOWN（P）、UP（V）原语编写程序描述顾客与出租车的行为。
Typedef int semaphore;
Semaphore PositionForCustomer=1;
Semaphore PositionForTax=1;
Semaphore Tax=0;
Semaphore Customer=0;
Void Customer(void)
{ 
   Up (Customer);
   Down (PositionForCustomer);
   Waiting for a tax in the stopping position();
   Down (Tax);
   Go away by tax();
   Up (PositionForCustomer)
}
Void Tax(void)
{ 
   Up (Tax);
   Down (PositionForTax);
   Waiting for a customer in the stopping position();
   Down (Customer);
   Go away with customer();
   Up (PositionForTax)
}
两个进程申请两个资源，这两个资源的数目都是1，分析这两段代码的不足之处。
Typedef int semaphore;
Semaphore resource_1=1;
Semaphore resource_2=1;
Void process_A(void)
{ 
Down(&resource_1);
Down(&resource_2);
Use_both_resources();
Up(&resource_2);
Up(&resource_1);
}
Void process_B(void)
{ 
Down(&resource_2);
Down(&resource_1);
Use_both_resources();
Up(&resource_1);
Up(&resource_2);
}
Answer:
May lead to deadlock
甲、乙、丙三人约定到某地集合一起去看电影。试用DOWN(P)、UP(V)原语描述同步过程。
Answer:
Typedef int semaphore;
Semaphore OneToTwo=0;
Semaphore OneToThree=0;
Semaphore TwoToOne=0;
Semaphore TwoToThree=0;
Semaphore ThreeToOne=0;
Semaphore ThreeToOne=0;
Void Process_One(void)
{ 
   Up (&OneToTwo);
   Up (&OneToThree);
   Down (&TwoToOne);
   Down (&ThreeToOne);
   Go_to_the_cinema();
}
Void Process_Two(void)
{ 
   Up (&TwoToOne);
   Up (&TwoToThree);
   Down (&OneToTwo);
   Down (&ThreeToTwo);
   Go_to_the_cinema();
}
Void Process_Three(void)
{ 
   Up (&ThreeToOne);
   Up (&ThreeToTwo);
   Down (&OneToThree);
   Down (&TwoToThree);
   Go_to_the_cinema();
}
有四个进程R1,R2,W1,W2，它们共享可以存放一个数据的缓冲区。进程R1每次把从键盘上读入的一个数据存到该缓冲区中，供另一个进程W1打印输出；进程R2每次从磁盘上读一个数据存放到该缓冲区中，提供给W2打印输出。当一个进程把数存放到缓冲区后，在该数还没有被打印输出之前不准任何进程再向缓冲区中存数。当一个进程已把缓冲区中的数打印输出后，在缓冲区中还没有存入一个新的数据之前不准任何进程再从缓冲区中取数打印。用down, up操作来协调它们的工作。
Answer:
Typedef int semaphore;
Semaphore empty=1;
Semaphore data1=0;
Semaphore data2=0;
Void Process-R1(void)
{ 
   Get a data();
   Down (&empty);
   Put the data into the buffer();
   Up (&data1);
}
Void Process-R2(void)
{ 
   Get a data();
   Down (&empty);
   Put the data into the buffer();
   Up (&data2);
}
Void Process-w1(void)
{ 
   Down (&data1);
   Get the data from the buffer();
   Up (&empty);
}
Void Process-w2(void)
{ 
   Down (&data2);
   Get the data from the buffer();
   Up (&empty);
}
假设有三个进程R、W0、W1共享一个缓冲区B，而B中一次只能存放一个数据。进程R从输入设备上读数据送缓冲区B，若存放的数是奇数，则允许W0将其取出并打印；若存放的数是偶数，则允许W1将其取出并打印。试用信号量和down, up操作写出实现这三个进程能同步工作的程序。
Answer:
Typedef int semaphore;
Semaphore empty=1;
Semaphore data0=0;
Semaphore data1=0;
Void Process-R(void)
{ 
   Get a data();
   Down (&empty);
   Put the data into the buffer();
   If (the data is odd)
Up (&data0);
   Else 
Up (&data1);
}
Void Process-w0(void)
{ 
   Down (&data0);
   Get the data from the buffer and print();
   Up (&empty);
}
Void Process-w1(void)
{ 
   Down (&data1);
   Get the data from the buffer and print();
   Up (&empty);
}



Please fill the blanks in the following program (the producer-consumer problem) with DOWN and UP operation: Two processes share a common, fixed-size buffer. One of them, the producer process puts information into the buffer, and the other one, the consumer process, take it out. The buffer has N slots into which the producer can puts information. You should also give the initial values of mutex and full. 
# define N 100 //number of slots in the buffer
typedef int semaphore; //semaphores are a special kind of int
semaphore mutex=1; //controls access to critical region
semaphore empty= N; //counts empty buffer slots
semaphore full=0; //counts full buffer slots
void producer() //the producer
{
 int item;
 while (true)
 {
item=produer_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() //the consumer
{
 int item;
 while (true)
 {
down( &full);
down( &mutex);
item =remove_item(item);
up(&mutex);
up(&empty);
consume_item(item);
}
}
A system with many competing processes wishing to read and write it (known as the reader and writer problem). It is acceptable to have multiple processes reading the database at the same time, but if one process is writing the database, no other processes may have access to the database, not even reader. Please fill the blanks in the following program which descript the behaviors of the reader process and the writer process. Please fill the blanks in the following program with DOWN and UP operation, you should also give the initial values of db and rc.
Typedef int semaphore; //use your imagination
Semaphore mutex=1; //controls access to ‘rc’
Semaphore db=1; //controls access to the database
Int rc=0; //counts the readers
Void reader (void) //readers processes
{
while (TRUE)
{
down(&mutex);
rc=rc+1;
if (rc==1) down(&db);
up(&mutex);
read_data_base();
down(&mutex);
rc=rc-1;
if (rc==0) up(&db);
up(&mutex);
use_data_base();
}
}
Void writer (void) //writers processes
{
while(TRUE)
{
think_up_data();
down(&db);
write_data_base();
up(&db);
}
}
There is a plate in which we can only place one fruit. The father can place an apple or an orange in the plate. The son can eat apple in the plate but he can’t eat orange. The daughter can eat orange in the plate but she can’t eat apple. Please descript the actions of the father, the son and the daughter with UP and DOWN operation. Suppose the plate is empty initially. You should give the initial values of the semaphores and fill in the blanks in the following program. 
 
typedef int semaphore; //semaphores are a special kind of int
Semaphore s1= 1 ; //counts empty plate
Semaphore s2= 0 ; //counts orange in the plate
Semaphore s3= 0 ; //counts apple in the plate
Father () //the father process
{
 While (true)
 {
 Take_up_a_fruit();
 Down(s1);
 if (the fruit is orange) Up(s2);
 else Up(s3);
 }
}
Daughter ( ) //the daughter process
{
 While (true) 
 {
 Down (s2) ;
 Take_up_an_orange_and_eat_the_orange ();
 Up (s1) ;
 }
}
Son ( ) //the son process
{
 While (true) 
 {
 Down (s3) ;
 Take_up_an_apple_and_eat_the_apple();
 Up (s1) ;
 }
}


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 1回复贴，共1页
分享到: