以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [求助]操作系统,PV原语的问题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54924)


--  作者:sjbird331
--  发布时间:11/6/2007 8:48:00 AM

--  [求助]操作系统,PV原语的问题
超市可以容纳500人同时购物,有6扇可供出入的门,即既可进又可出,每扇门只允许1个人通过。使用PV操作及信号量描述进入和离开该超市的算法,使得超市的购物容量得到最大发挥。
--  作者:EagleSoaring
--  发布时间:11/6/2007 6:01:00 PM

--  
大致写了一个,发现错误请指正,谢谢!

semaphor mutex = 500;
semaphor mutex1 = 6;
semaphor door = 1;

void customer()
{
    p(mutex);
    p(mutex1)
    p(door)
      进入
    v(door);

    购物

    p(door)
    离开
    v(door);
    v(mutex1);
    v(mutex);
}



--  作者:fgffggfg
--  发布时间:11/6/2007 8:34:00 PM

--  
考不考虑进出门费时问题啊,如果考虑的话,
这个算法就不行了吧?
--  作者:EagleSoaring
--  发布时间:11/6/2007 9:10:00 PM

--  

谢谢,有道理!虽然有6个门,但只能同时用一个,有问题 。

修改一下:

对每个门 i, i =1,2...,6,门 i 前要进入超市的顾客都执行下面的程序:

semaphor mutex = 500;
semaphor door[6] ; //初值均为1

void customer()
{
    p(mutex);
    p(door[i])
      进入
    v(door[i]);

    购物

    p(door[i])
    离开
    v(door[i]);
    v(mutex);
}


这回呢?


[此贴子已经被作者于2007-11-7 22:26:34编辑过]

--  作者:albani
--  发布时间:11/6/2007 10:37:00 PM

--  
door=6
--  作者:fgffggfg
--  发布时间:11/7/2007 1:57:00 PM

--  
不用6应该是不对的吧,而且进门出门肯定是分开写的。
我也写个看看:
semaphor mutexroom =500;
semaphor mutexperson=0;
semaphor door =6;
int i=0;
void customerin()                   void customerout()
{p(mutexroom);                       {p(mutexperson);
   p(door);                                  p(door);
   i:=(i+1)mod6;                           i:=(i+1)mod6;
   从i-1号门进入;                           从i-1号门出去;
   v(mutexperson);                       v(mutexroom);
   v(door);                                   v(door);
  }                                             }
我这个只能满足所有人进出门时间都一样的情况,并且要求按门的编号顺序进出。
不知道是不是不用考虑进出门时间不同的情况。
门编号了不知道对不对。


--  作者:buddha
--  发布时间:11/7/2007 3:00:00 PM

--  
不用6显然不对.6扇门应该可以同时进出..
应该没有必要分开吧.分开了反而要考虑更多的情况,有些东西就更不好控制了.
我觉得EagleSoaring第一次写的算法就应该可以描述了吧.
--  作者:sjbird331
--  发布时间:11/7/2007 5:55:00 PM

--  
谢谢大家的指导!!我是这样写的,你们帮我看看可行吗?谢谢
count:semaphore:=500;  
door:semaphore:=6;
进入超市进程:begin  
        p(count);             p(door);             进入超市;             v(door);          end             
离开超市进程:begin              p(door);               离开超市;             v(door);
                       v(count)           end 

--  作者:sjbird331
--  发布时间:11/7/2007 6:30:00 PM

--  
count:semaphore:=500;  
door:semaphore:=6;
进入超市进程:
begin
p(count); 
p(door); 
进入超市;
v(door);
end
离开超市进程:
begin
p(door);
离开超市;
v(door);
v(count);
end

--  作者:EagleSoaring
--  发布时间:11/7/2007 7:34:00 PM

--  
以下是引用fgffggfg在2007-11-7 13:57:00的发言:
不用6应该是不对的吧,而且进门出门肯定是分开写的。
我也写个看看:
semaphor mutexroom =500;
semaphor mutexperson=0;
semaphor door =6;
int i=0;
void customerin()                   void customerout()
  {p(mutexroom);                       {p(mutexperson);
    p(door);                                  p(door);
    i:=(i+1)mod6;                           i:=(i+1)mod6;
    从i-1号门进入;                           从i-1号门出去;
    v(mutexperson);                       v(mutexroom);
    v(door);                                   v(door);
   }                                             }
我这个只能满足所有人进出门时间都一样的情况,并且要求按门的编号顺序进出。
不知道是不是不用考虑进出门时间不同的情况。
门编号了不知道对不对。




--------------------------------------------------------------------------------------------

进门出门分开写是不对的。
理由有两个:
1. 一个顾客的两个活动,是完整的过程,不能分开
2. PV操作中的多个进程都是并发执行的,如果分开写进入和离开,进入和离开就成了两个
   并发进程, 会产生与时间有关的错误。

[此贴子已经被作者于2007-11-7 22:35:26编辑过]

--  作者:fgffggfg
--  发布时间:11/7/2007 9:51:00 PM

--  
照你们的说法,那教材上的生产者消费者问题的语句里,
就不用加“i:=(i+1)mod(n);”了??
如果产生了2个人用1个门怎么办??最起码的临界资源互斥都不要考虑了??
--  作者:fgffggfg
--  发布时间:11/8/2007 10:04:00 AM

--  
EagleSoaring:
我看题目是要求“使用PV操作及信号量描述进入和离开该超市的算法”,所以才那样写的。
如果题目要求“使用PV操作及信号量描述去超市购物的整个过程”的话,只要加上
这段:customerbuy(){
              customerin();
             购物;
              customerout();
               }
       应该就可以了。
还没怎么做过题,不知道这个题目怎么理解啊?
--  作者:fgffggfg
--  发布时间:11/8/2007 10:10:00 AM

--  
啊,还有,EagleSoaring你写的那个用door[i]的也是不对的。
如果一个顾客P(door[1])而此时door[1]有人用,算法里没有自动P(door[2])……P(door[i])的功能,所以他只能一直等door[1]了,即使其他的门空闲也无法使用~
--  作者:EagleSoaring
--  发布时间:11/8/2007 12:04:00 PM

--  
以下是引用fgffggfg在2007-11-8 10:04:00的发言:
EagleSoaring:
我看题目是要求“使用PV操作及信号量描述进入和离开该超市的算法”,所以才那样写的。
如果题目要求“使用PV操作及信号量描述去超市购物的整个过程”的话,只要加上
这段:customerbuy(){
               customerin();
              购物;
               customerout();
                }
        应该就可以了。
还没怎么做过题,不知道这个题目怎么理解啊?

---------------------------------------------------------------------------------
谢谢你的细心。关于分开写
陈老师的教材有个课后习题,阅览室问题,和这个类似。
习题讲评时把两个进程分开写的算作错误解法,
陈老师说法是:一个完整的活动不能分开

助教的补充是:即使再加一个协调进程,(比如你写的customerbuy()),
即使没有顾客进入,离开的那个进程也可以做V操作,这是不对的

我觉得问题的关键就是 并发环境下离开进程不会受那个协调进程制约


--  作者:EagleSoaring
--  发布时间:11/8/2007 12:13:00 PM

--  
以下是引用fgffggfg在2007-11-8 10:10:00的发言:
啊,还有,EagleSoaring你写的那个用door[i]的也是不对的。
如果一个顾客P(door[1])而此时door[1]有人用,算法里没有自动P(door[2])……P(door[i])的功能,所以他只能一直等door[1]了,即使其他的门空闲也无法使用~


------------------------------------------------------------------------------------
你说得对。其实我写的那个解法问题不止这个。

还有一个问题:
我写的解法里,强制的要求顾客从哪个门进入,就从哪个门出,即使别的门空闲,这个顾客也从那个门出去。

我觉得,本来一个简单的问题,让我改来改去,解法越来越复杂,我也没必要再修改了,可能别人有更好的简单的解法,期待中。。。。



--  作者:Supremgoooo
--  发布时间:11/8/2007 3:24:00 PM

--  
以下是引用sjbird331在2007-11-7 18:30:00的发言:
count:semaphore:=500;  
door:semaphore:=6;
进入超市进程:
begin
p(count);
p(door);
进入超市;
v(door);
end
离开超市进程:
begin
p(door);
离开超市;
v(door);
v(count);
end



我来给个观点:

count:semaphore:=500;  
door:semaphore:=6;

begin
p(count);
p(door);
进入超市;
v(door);

买东西....

p(door);
离开超市;
v(door);
v(count);
end


--  作者:sjbird331
--  发布时间:11/8/2007 5:41:00 PM

--  
这样想想,还是觉得将一个顾客的进入超市和离开超市应该写入一个过程
--  作者:xiaojian823
--  发布时间:11/8/2007 7:54:00 PM

--  
semaphor count = 500;//顾客总数
semaphor doors=6;  //初值为6,门的总数
semaphor door[6] ; //初值均为1,用于每个门的互斥

void customer()
{
    i:=-1;
repeat:
       p(count);
       p(doors);
       i:=(i+1)mod6;
       p(door[i]);
       进入
       v(door[i]);
       v(doors);

       购物;
       p(doors);
       i:=(i+1)mod6;
       p(door[i]);
       离开;
       v(door[i]);
       v(doors);
       v(count);
until false;
}

我发个看下,不知能不能解决


--  作者:fgffggfg
--  发布时间:11/8/2007 11:08:00 PM

--  
谢谢EagleSoaring告诉我陈老师的讲解。我手头上的os资料太少了,呵呵。
那改成下边这个应该就没大问题了~
semaphor mutexroom =500;
semaphor door =6;
int i=0;
void customerbuy()               
  {p(mutexroom);                     
    p(door);                                                        
    i:=(i+1)mod6;   
    从((i-1)mod6)号门进入;  
    v(door);  
    购物;
    p(door);
    i:=(i+1)mod6;
    从((i-1)mod6)号门离去;
    v(mutexroom);
    v(door);                                  
   }


--  作者:fgffggfg
--  发布时间:11/8/2007 11:16:00 PM

--  
xiaojian的算法好象和我最后这个差不多,不同的就是xiaojian用door[i]实现每个门的互斥,
我的是让i先进行自加来避免2个人同时使用1个门。
不知道我那样写考试时给不给分啊哈哈?
啊,还有,xiaojian你的算法里应该把repeat去掉吧,1个人就购物1次吧?


--  作者:sjbird331
--  发布时间:11/9/2007 5:29:00 PM

--  
fgffggfg,我觉得语句"i:=(i+1)mod6;"这样写的话就容易让你理解,每个顾客进入超市必须经过指定的门,而不是只要有空闲的门他就可以进入,你觉得呢?谢谢
--  作者:fgffggfg
--  发布时间:11/9/2007 10:36:00 PM

--  
我的算法已经保证了有空闲门的时候顾客就可以进出了.
只不过如果有2个以上空门的话,优先分配编号小的门罢了.
我觉得用p,v原语没办法写成随机走门的语句,因为那样的话
必须写成P(door0);
               ...
              p(door1);
                 ...类似的语句.
  这样进程运行一定会出错的.
所以我觉得一定要编号.
--  作者:xiaojian823
--  发布时间:11/10/2007 6:08:00 PM

--  
以下是引用fgffggfg在2007-11-8 23:16:00的发言:
xiaojian的算法好象和我最后这个差不多,不同的就是xiaojian用door[i]实现每个门的互斥,
我的是让i先进行自加来避免2个人同时使用1个门。
不知道我那样写考试时给不给分啊哈哈?
啊,还有,xiaojian你的算法里应该把repeat去掉吧,1个人就购物1次吧?




那个是每个顾客都是从那个地方开始的,书上就是那么写的呢,repeat代表重复这个进程,也不一定要这个人总在那,只不过他要再买也没有关系啊!呵呵
--  作者:fgffggfg
--  发布时间:11/11/2007 11:36:00 AM

--  
书上的好像只有生产者消费者问题里是写了repeat的.
读者写者和哲学家问题都没有repeat吧.记不太清楚了呵呵~
--  作者:buddha
--  发布时间:11/11/2007 1:11:00 PM

--  
没有必要想的这么复杂吧.
大家不要在一些细节的东西抠的太多.
其实,真正在考试的时候.要写的往往都没那么复杂的.
--  作者:fgffggfg
--  发布时间:11/11/2007 1:45:00 PM

--  
不抠不行啊,不是都说os就是拼pv题的么??!而且pv题经常不是0分就是10分的么呵呵!
--  作者:sjbird331
--  发布时间:11/11/2007 5:07:00 PM

--  
那大家觉得哪一个写的接受度最高呢?毕竟答案只有一个啊(我也不知道答案) ^_^
--  作者:fgffggfg
--  发布时间:11/13/2007 8:32:00 AM

--  
看了下书,只有读者写者问题里没用repeat。
不知道了呵呵。
楼主哪来的题啊,去找答案哈!
--  作者:xiaojian823
--  发布时间:11/13/2007 3:57:00 PM

--  
以下是引用fgffggfg在2007-11-11 11:36:00的发言:
书上的好像只有生产者消费者问题里是写了repeat的.
读者写者和哲学家问题都没有repeat吧.记不太清楚了呵呵~


这个题应该不用repeat的,初值i在外面先初始化就行了,我写的好象只能先初始化-1才能从0开始的,感觉不符合一般的赋值
--  作者:sjbird331
--  发布时间:11/13/2007 5:58:00 PM

--  
同学给的 他也没答案 我很郁闷啊 .......
fgffggfg,你觉得我在前面发的我写的程序,有哪些不妥之处?谢谢
--  作者:fgffggfg
--  发布时间:11/14/2007 2:08:00 PM

--  
反正不用上i:=(i+1)mod6可能就是错的了。
怎么论坛里那么多高人不来给个标准答案呢??
--  作者:sjbird331
--  发布时间:11/14/2007 5:57:00 PM

--  
希望论坛上的高手们给出一个标准答案,谢谢
--  作者:九九
--  发布时间:11/15/2007 12:15:00 PM

--  
semaphor count=500;
semaphor door=6;
void customor_buy()
      {
        p(count);
        p(door);
        进入超市:
        v(door);

   购物。。。。
      
       p(door);
       离开超市
       v(count);
       v(door);
      }

改过了,这样就该可以了,我以为;

[此贴子已经被作者于2007-11-15 14:21:56编辑过]

--  作者:fgffggfg
--  发布时间:11/15/2007 1:39:00 PM

--  
晕,九九  你没看前面我们的讨论啊!你的答案和前面我们严重不同意的那个一样滴~

--  作者:九九
--  发布时间:11/15/2007 2:07:00 PM

--  
不是我没有看,
而是我觉得这个是最有道理的!
对门进行编号操作没有意义


--  作者:fgffggfg
--  发布时间:11/15/2007 3:13:00 PM

--  
那么你觉得书上多个生产者消费者问题算法里的i:=(i+1)mod(n)
是因为什么有意义的?
和本题的6个门有什么本质区别?
--  作者:九九
--  发布时间:11/15/2007 5:11:00 PM

--  
书上那个是给你一个环形缓冲池的例子
他的具体操作是按照一个环形的顺序来应用资源
而这道题目中并没有涉及到门的可通过次序的问题
书上的Buffer[i]只是确定了执行过程中选择确定的缓冲区
不会是这里把大家迷惑了吧!
--  作者:fgffggfg
--  发布时间:11/15/2007 9:46:00 PM

--  
书上并不是给了一个环行缓冲池的例子,生产者消费者问题提出时也并没有限定必须按顺序生产消费。
是为了解决多个生产者消费者问题才引入的环行缓冲池。
九九你把原因和结果弄反了吧??

--  作者:九九
--  发布时间:11/16/2007 11:00:00 AM

--  
你有没有思考过,书上的问题有没有buffer[i]的区别?
而且你有没有发现这道题与生产者消费者的不同?
生产者消费者是必须向第buffer[i]缓冲区放过货物才能取出;
而这个题中这个门就算没有人进去过也可以走出人来(人不是货物,可以任意选择门进出)
buffer[i]中送货量和取货量相同 而 door[i]中进出的人数可以不等!
--  作者:fgffggfg
--  发布时间:11/16/2007 8:23:00 PM

--  
你的意思是不用在pv语句中实现对门的选择吧?
如果有这样的途径的话,假设是方法A,那么生产者消费者
也大可不必用i=(i+1)mod(n)了。
每次生产者只要用p判断有空间就可以生产产品,选择放在什么位置的
问题大可以交给方法A,而消费者也只要判断下有产品就可以消费了,
选择哪个产品的问题也可以直接交给方法A了。
不要说对产品所在位置的动态记录是和本题的根本区别,因为象你那样写
的话一样要对空门的编号进行动态记录的。
其实我们怎么争论也没用呵呵,慢慢等着高人给个确定答案吧~
--  作者:dtdnh520
--  发布时间:1/18/2008 11:01:00 AM

--  
生产者和消费者的例子中对缓冲区加锁只是为了防止多个生产者或多个消费者同时去对循环队队进行读的操作,或写的操作,也就是说缓冲区是一个临界资源.
  而这题,每个门就可以当成一个临界资源,他们是相互独立的,当你想进入超市,只要随便找个门去就行,出来时,水边找个门来.所以,我是支持"九九"的看法的.
--  作者:wanginvc
--  发布时间:4/28/2008 5:51:00 PM

--  
一名过客, 我对这个问题的理解是这样的,仅供参考,因为忙可能不会继续回复此帖,见谅-_-:
立场不同, 问题的理解也不同.
1. 超市客户的角度,我们需要描述购物过程(进门,购物,出门), 那么有多少个用户就会有多少个并发线程或进程. 也就是说每个用户就是一个独立的线程,他们之间需要用信号量进行同步.这应该适用用户作为已知条件的情况,比如已经知道张三,李四,王五等人的时候,他们就是我们描述的对象.
2. 超市运行角度, 我们同样需要描述购物过程(进门,购物,出门), 但是这时只会有两个并发线程或进程, 一个客户进门购物进程和一个客户出门进程. 超市是我们的描述目标, 超市提供了这两种服务,我们需要用信号量来同步进门和出门两种服务. 本人认为, 此题适合这种情况. 下面是我提供的这种情况的解决方案:
Semaphores:
MarketFreeSpace: 0 ~ 500, initilized to 500
CustomersInMarket: 0 ~ 500, initilized to 0
DoorsAvaiable: 0 ~ 6, intilized to 6
In:

P(MarketFreeSpace);
P(DoorsAvaiable);
Shopping();
V(CustomersInMarket);
V(DoorsAvaiable);

Out:
P(CustomersInMarket);
P(DoorsAvaiable);
Cashing();
V(MarketFreeSpace);
V(DoorsAvaiable);

附源代码:
// Semaphore.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Windows.h"

HANDLE hSemSpace;
HANDLE hSemPeople;
HANDLE hSemDoors;

void InMarket(const char * threadName)
{
 long lPrevCountPeople;
 long lPrevCountDoors;
 WaitForSingleObject(hSemSpace, INFINITE);
 WaitForSingleObject(hSemDoors, INFINITE);
 printf("%s: I am into market.\n", threadName);
 ReleaseSemaphore(hSemPeople,1, &lPrevCountPeople);
 ReleaseSemaphore(hSemDoors, 1, &lPrevCountDoors);
 printf("%s: Current %d people in market.\n", threadName, lPrevCountPeople + 1);
 printf("%s: Current %d doors opened.\n", threadName, lPrevCountDoors + 1);
}

void OutMarket(const char * threadName)
{
 long lPrevCountSpace;
 long lPrevCountDoors;
 
 WaitForSingleObject(hSemPeople, INFINITE);
 WaitForSingleObject(hSemDoors, INFINITE);
 printf("%s: I am out market.\n", threadName);
 ReleaseSemaphore(hSemSpace, 1, &lPrevCountSpace);
 ReleaseSemaphore(hSemDoors, 1, &lPrevCountDoors);
 printf("%s: Current %d doors opened.\n", threadName, lPrevCountDoors + 1);
 printf("%s: Current %d free space for people in market.\n", threadName, lPrevCountSpace + 1);
}

DWORD WINAPI ThreadInMarket(LPVOID lpParameter)
{
 while(TRUE)
 {
  InMarket("ThreadInMarket");
 }
 return 0;
}

DWORD WINAPI ThreadOutMarket(LPVOID lpParameter)
{
 while(TRUE)
 {
  OutMarket("ThreadOutMarket");
 }
 return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
 HANDLE hInMarket;
 HANDLE hOutMarket;
 DWORD dwWaitResult;
 long lPrevCount;
 setbuf(stdout, NULL);
 //Open/Create semaphore
 hSemSpace = CreateSemaphore(NULL, 1, 1, L"Space");
 if(hSemSpace == NULL)
 {
  printf("CreateSemaphore \"Space\" fail, erro code:%d\n, exit", GetLastError());
  return 0;
 }
 else
 {
  printf("CreateSemaphore \"Space\" succeeds.\n");
 }
 
 hSemPeople = CreateSemaphore(NULL, 0, 1, L"People");
 if(hSemPeople == NULL)
 {
  printf("CreateSemaphore \"People\" fail, erro code:%d\n, exit", GetLastError());
  return 0;
 }
 else
 {
  printf("CreateSemaphore \"People\" succeeds.\n");
 }

 hSemDoors = CreateSemaphore(NULL, 1, 1, L"Doors");
 if(hSemDoors == NULL)
 {
  printf("CreateSemaphore \"Doors\" fail, erro code:%d\n, exit", GetLastError());
  return 0;
 }
 else
 {
  printf("CreateSemaphore \"Doors\" succeeds.\n");
 }

 hInMarket = CreateThread(NULL, 0, ThreadInMarket, NULL, CREATE_SUSPENDED, NULL);
 hOutMarket =CreateThread(NULL, 0, ThreadOutMarket, NULL, CREATE_SUSPENDED, NULL);
 ResumeThread(hInMarket);
 ResumeThread(hOutMarket);
 while(TRUE)
 {
  Sleep(10000);
 }
 return 0;
}


--  作者:zhangzijun
--  发布时间:5/21/2008 4:07:00 PM

--  
呵呵,顶
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
702.637ms