新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → 关于北大操作系统教程第四章35题的讨论 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 15401 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 关于北大操作系统教程第四章35题的讨论 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第11楼
    发贴心情 

    这句话很有道理，但是很遗憾，它是无法实现的。

    我在前面反复说过，P，V不能实现先来先服务。这个是由于P，V本身的随机性导致的。

    对随机性的理解：
    （1）多进程并发执行时的相对速度在执行前不能做任何假设。
    （2）在一组进程执行之后，它们刚才的执行速度不可能重现。
    （3）V的定义是从等待队列中随机的释放一个进程。
    （4）一个进程的执行也受到其它进程不可估计的干扰。

    以上是理论。我在这方面曾经专门研究过，先来先服务并不是绝对不行的，我提供两种方法：
    （1）按照写者优先思想，一个进程一个队列，n个进程设置成为n个队列。该算法比较容易理解，但是几乎是无法编成实现的。
    （2）引入队列，一个进程被阻塞到队列尾，释放时释放队列首进程。这似乎有些不伦不类，已经不像是P，V题了。

    UNIX中有过所谓的Hard semaphore的概念，说V时释放队首进程。这主要可能是为实时系统提供的，而且它似乎从没有被实现过。所有基于POSIX标准的os几乎都是采用weak semaphore，这与人们对实时系统本质的理解有关。“实时系统中其实可能不存在抢占”。

    以下是引用ychj在2006-10-29 2:19:00的发言：
    所谓银行叫号就是要让先拿号的顾客一定先得到服务。
    请大家仔细分析一下代码，存在以下问题：
    (1) 上面这段代码有这种可能性：i+1号顾客在i号顾客之前进入Staff等待队列，从而先得到服务，这显然是有问题的。
    (2) 服务于接受服务之间缺乏同步。例如：Customer也许已经执行完“接受服务”了，Staff可能才开始执行“服务”。
    (3) 当Customer进程唤醒Staff进程后，可能Staff还没开始叫号，而Customer已经接受完服务并离开了，这都是不合理的。
    这是上述算法的明显问题，大家想想有什么好的解决方案。




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/29 23:18:00
     
     citeator 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：65
      门派：XML.ORG.CN
      注册：2006/8/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给citeator发送一个短消息 把citeator加入好友 查看citeator的个人资料 搜索citeator在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看citeator的博客第12楼
    发贴心情 
    临界区是 staff提供的服务，一次只能一个customer享受。
    先是要搞清楚临界区是哪个。
    其他的好像不麻烦。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/30 11:58:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第13楼
    发贴心情 
    我给出apolor算法的改进算法。
    //////////////////////////////////////////////
    int count_s = 0;
    int count_c = 0;
    semaphore customer;//初值为0
    semaphore mutex_s;//初值为0
    semaphore mutex_c;//初值为0
    semaphore staff;//初值为0
    semaphore begin;//初值为0

    void Staff(i){
            while(true){
                    P(customer);
                    P(mutex_s);
                            count_s ++;
                            叫编号为count_s的顾客；
                    V(mutex_s);
                    V（staff）；
                    P（begin）；
                    服务；
            }
    }

    //////////////////////////////////////////////////////////

    void Customer(int &i){
            P(mutex_c);
                    i=count_c ++; //i表示自己的号码
            V(mutex_c);
            V(customer);
    L：     P(staff);
            if（check（i）） //看一下是否叫的是自己，是则执行；否则让权   
            { V（begin）；被服务；}
            else
            { V（staff）；goto L；}
            离开；
    }
    注：这个算法虽然有缺点，但是解决了ychj的问题。


    [此贴子已经被作者于2006-10-31 8:59:42编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/30 22:15:00
     
     ychj 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：58
      积分：440
      门派：XML.ORG.CN
      注册：2006/8/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给ychj发送一个短消息 把ychj加入好友 查看ychj的个人资料 搜索ychj在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看ychj的博客第14楼
    发贴心情 
    "（3）V的定义是从等待队列中随机的释放一个进程。" 这句话感觉有问题，既然是用队列存储，肯定是按先进先出的顺序。
    (1) Supremgoooo说的对，的确是要引入一个队列；
    (2) 同时引入一个共享变量next，记录下次首先接受服务的顾客的编号（因为go to语句有害，所以Java,C++里应该都没有了吧，尽量不使用它）；
    (3) 另外，需要一个信号量数组，它恰好实现了两个功能：
         (a) 当一个顾客先进入服务，他可以唤醒下一个号顾客进程；
         (b) 当顾客服务结束后，Staff对相应的顾客进程做V操作，告诉他服务结束了。

    我个人觉得，PV操作中既然可以用数组，用队列是没有什么问题的，并且都是伪码级的。
    大家觉得呢？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 0:59:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第15楼
    发贴心情 
    先进先出违反了随机性原则，在绝大多数的os中是不被采用的。

    另外：北大的教材和Tanenbaum的教材上的V定义均是随机释放。

    以下是引用ychj在2006-10-31 0:59:00的发言：
    "（3）V的定义是从等待队列中随机的释放一个进程。" 这句话感觉有问题，既然是用队列存储，肯定是按先进先出的顺序。
      

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 9:12:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第16楼
    发贴心情 
    想了一下，13楼的算法虽然使用的是busywaiting软件解法的思想，但是它问题不大。算是这个题的正确解法了。

    如果谁还对busywaiting这种方式不满，可以采用我给的先来先服务思想解决这个问题。欢迎跟帖讨论。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 9:17:00
     
     mxf3306 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：112
      积分：823
      门派：XML.ORG.CN
      注册：2006/7/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mxf3306发送一个短消息 把mxf3306加入好友 查看mxf3306的个人资料 搜索mxf3306在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看mxf3306的博客第17楼
    发贴心情 
    shared variable
    Choosing: array[1..N] of 0..1 initially 0;
    Number: array[1..N] of 0..cx~ initially 0
    process p: /* 1 < p < N */
    private variable
    q: 1..N
    while true do
    0: Noncritical Section;
    1: Choosing[p] := 1;
    2: Number[p] := 1 + max{Number[l], ..., Number[N]};
    3: Choosing[p] := 0;
    4: for q:=l to N skip p do
    5: await Choosing[q] = 0; /* busy wait */
    6: await Number[q] = 0 V (gumber[p],p) < (gumber[q],q) /* busy wait */
        od;
    7: Critical Section;
    8: Number[p] := 0
    od
    (In line 6, the notation (a, b) < (c, d) is a shorthand for (a < c) V (a = c A b < d).)


    [此贴子已经被作者于2006-10-31 16:52:01编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 16:20:00
     
     mxf3306 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：112
      积分：823
      门派：XML.ORG.CN
      注册：2006/7/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mxf3306发送一个短消息 把mxf3306加入好友 查看mxf3306的个人资料 搜索mxf3306在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看mxf3306的博客第18楼
    发贴心情 
    以上就是最经典的bakery algorithm的阐述形式。在网上查了很久，我还没找到它的PV实现形式。我觉得，PV的优点在于它能有效地避免不必要的busy waiting。而且这个学期，北大的实习里就有这么一题，我很怀疑supremgoooo的算法是否能直接付诸实践，许多进程在不停的CHECK，效率会极其低下。
    所以我觉得可能会有更好的算法，但在这个题目上面已经花了太多时间了，所以先搁置下来吧。如果考试考到的话，也只能按照supremgoooo的算法了。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 16:34:00
     
     mxf3306 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：112
      积分：823
      门派：XML.ORG.CN
      注册：2006/7/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mxf3306发送一个短消息 把mxf3306加入好友 查看mxf3306的个人资料 搜索mxf3306在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看mxf3306的博客第19楼
    发贴心情 
    关于FCFS 我在ACM一篇文章（Lamport on Mutual Exclusion: 27 Years of Planting Seeds）中找到这句话：The bakery algorithm is also of interest because it satisfies the following rather strong progress property.
    • First-come, First-served (FCFS) Priority: If process p enters the bakery before q enters the doorway,then p executes its critical section before q.
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 16:38:00
     
     ychj 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：58
      积分：440
      门派：XML.ORG.CN
      注册：2006/8/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给ychj发送一个短消息 把ychj加入好友 查看ychj的个人资料 搜索ychj在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看ychj的博客第20楼
    发贴心情 
    查了一下，不同的操作系统对于信号量队列的处理是不一样的，分为强、弱两种设计方法。强者在作V操作时唤醒进程是按先进先出的。因此在这里我们肯定必须考虑先进先出（否则没法做），其实在操作系统实现上，我们也完全可以简单地实现先进先出的信号量队列。
    这道题的解法我几天前已经完全做出了，暂时先不告诉大家的源代码实现。
    只是告诉大家几个关键的地方，大家想想看，因为只有自己经过认真思考后才有可能长进，呵呵。
    (1) 引入一个队列；
    (2) 声明一个信号量next，用于指示下一次将首先接受服务的顾客编号；
    (3) 一个信号量数组wait[0...m-1]，m为一天接受服务的顾客人次的最大值；
    这里需要的一种思路就是，由于领号之后顾客进程进入同一个信号量的队列(比如counter)的顺序是随机的，因此不能让这些进程进入一个信号量等待，这是关键。
    当然另外还需要一些信号量，比如counter、ready 以及几个互斥信号量等等。
    这种做法应该说是趋于完善的，因为它接近于当你实际编程时需要考虑的各种细节问题（当然实际编程时还要更复杂）；而上述大家提出的算法其实都是很粗糙的，并且在实际编程时离实现还有很远的距离。
    当你设计的一个算法，不管它是PV的伪代码形式还是实际代码，我想都应该是没有漏洞的才行。
    比如：
    Customer与Staff的进程里对于一个同时发生的行为“理发”与“接受理发”，我们只能用文字说明的形式去告诉别人，这两个行为是同时发生，是一个行为的两个角度而已。
    但是当你用程序来运行时，程序是不知道的，这样的程序，一运行肯定就错了。
    因此，更加完善的设计方法是需要我们考虑的。
    当然，若有一种情况，大家则不需要考虑这些，就是如果老师不要求我们掌握那么深入，呵呵。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 2:02:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/9/21 16:26:40

    本主题贴数20，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 109.375ms