首页 博客

# 斯坦福编程范式 CS107_17

# 接着上节课的哲学家问题进餐问题

Semaphore forks[] = {1,1,1,1,1};

void philosopher(int id){
    for(int i =0;i<3:i++){
        Think();
        SemaphoreWait(forks[id]);
        SemaphoreWait(forks[(id+1)%5]);
        Eat();
        SemaphoreSignal(forks[id]);
        SemaphoreSignal(forks[(id+1)%5]);
    }
    Think();
}

上节课我们知道上述情况下，可能会出现死锁状态，所有人都在等待另一个人放下筷子以便自己进行吃饭动作。那么我们知道一共有 5 个叉子，并且 5/2=2，所以也就是说最多只能有两个哲学家在同一时刻进行进餐。所以最简单的方法就是再加一个信号量，并且信号量为 2。

Semaphore forks[] = {1,1,1,1,1};
Semaphore  numAllowedToEat(2);
void philosopher(int id){
    for(int i =0;i<3:i++){
        Think();
        SemaphoreWait(numAllowedToEat);
        SemaphoreWait(forks[id]);
        SemaphoreWait(forks[(id+1)%5]);
        Eat();
        SemaphoreSignal(forks[id]);
        SemaphoreSignal(forks[(id+1)%5]);
        SemaphoreSignal(numAllowedToEat);
    }
    Think();
}
但是与其写 2，不如写 4，写 4 是可以的，因为只要有一个人不被允许拿叉子，那么其他人总有 1 个可以拿齐叉子并进行吃饭，尽管可能会有另几个人暂时被阻塞了。


填 2 和 4 的区别在于，如果填的是 2，那么会有多个线程过早的钝化掉，被阻塞在 numAllowedToEat 这里；而 4 就是尽可能多的线程进行运行。


问题：为什么要使用 Semaphore，不用一个 int 来解决？


答： 使用信号量 Semaphore 是将这个监督过程交由线程管理器管理了。如果采用比如说循环的形式不断的人工去检查一个整数是否大于 0 或小于 0，那么你就无法做任何有意义的事，除非跳出这个循环，可能在一段时间里，你为了确认这个锁是不是 0 而不断重复获取并释放该锁，这种现象被称为 “忙等待”。当你有许多处理器的时候，你可以将线程运行在其他处理器上，并采取 “忙等待” 的方式进行检查，如果只有一个处理器，这样就是无意义的，会浪费大量处理器的时间 。


# 例子一


FTP 下载，一个 1990 年的技术。现在假设我们有一个函数，这个函数叫 DownloadSingleFile 。这里的返回值就是我们要下载文件的字节数量。


现在我想要实现一个下载所有文件的函数 DownloadAllFiles ，这里的 n 意味着 n 个线程，每一个线程用于下载一个文件。每一个线程都有一个存储下载文件字节数的大小的变量，并且我想要把这个变量的地址存储，并对它上锁，防止多个线程同时对其值进行修改。


为什么在 ThreadNew  中不直接调用 DownloadSingleFile  呢？因为传递到 ThreadNew  的函数，返回值类型为 void ，即使返回值不为 void ，也没有办法抓取到来自 ThreadNew  环境下的返回值。所以我们通过另一个函数 DownloadHelper  帮助我们获取下载文件的字节数，并通过累加将值加到 totalBytes  中。


下面来构建 DownloadHelper ，记住 Semaphore 本身就是指针，不需要加取址符，直接传入 lock 即可。这里直接赋值 bytesDownloaded  的含义是多个线程可以 “同时” 都在进行下载操作，后面线程对唯一的下载总字节数进行操作时才需要对其上锁。


int DownloadSingleFile(const char * server,const char * path);
int DownloadAllFiles(const char * server,const char * files[],int n){
    int totalBytes = 0;
    Semaphore lock = 1;
    for(int i =0;i<n;i++){
        ThreadNew(ThreadName,DownloadHelper,4,server,files[i],&totalBytes,lock);
    }
    return totalBytes;
}
void DownloadHelper(const char * server,const char * path,int *numBytesp,Semaphore lock){
    int bytesDownloaded = DownloadSingleFile(server,path);
    SemaphoreWait(lock);
    (*numBytes)+=bytesDownloaded;
    SemaphoreSignal(lock);
}
但是这样编程有一点小问题，就是有可能我最后得到的返回值 totalBytes  是 0，为什么呢？因为从 for 循环的最后一跳到 return 假如很快，而在这个时间段内，所有线程中的写入操作还没有完成，那么这个时候就直接结束了 for 循环，导致最终得到的 totalBytes  不是一个准确的值。所以其实真正的工作量在这里，for 循环之前，我们需要阻塞住这个父进程，不能让他提前跳转到 return  语句。


我们定义一个 childrenDone  信号量作为纽带。并让子线程结束后就 + 1。当然也可以初始化信号量为负值，但那是 JAVA 才有的内容，C 不行。


int DownloadAllFiles(const char * server,const char * files[],int n){
    Semaphore childrenDone = 0;
    int totalBytes = 0;
    Semaphore lock = 1;
    for(int i =0;i<n;i++){
        ThreadNew(ThreadName,DownloadHelper,5,server,files[i],&totalBytes,lock,
               ChildrenDone);
    }
    for(int i = 0;i<n;i++)
        SemaphoreWait(childrenDone);
    return totalBytes;
}
        
 void DownloadHelper(const char * server,const char * path,int *numBytesp,Semaphore lock,
                    Semaphore ParentToSignal){
    int bytesDownloaded = DownloadSingleFile(server,path);
    SemaphoreWait(lock);
    (*numBytes)+=bytesDownloaded;
    SemaphoreSignal(lock);
   	SemaphoreSignal(ParentToSignal);
}
** 想法：** 如果 totalBytes 不使用 int 类型，而使用数组，那么进程在写入时就不会产生冲突，可以减少一个信号量。这是一个很好的想法，但如果 N 很大的时候，这个想法就不是很适用了，当 N 较小时这个方法很好。


# 为下一节课留的大例子


# Ice Cream Store Simulation


在冰淇淋店，我们有 10 个顾客，我们还知道每个顾客定了几个冰淇淋 (1~4)，并且店里有一个收银员，每一个顾客都会走过去向他付钱，因此会产生小小的竞争。还有有个小经理决定做不做冰淇淋。10 到 40 个店员 ，店员可以同时做冰淇淋。顾客向店员订冰淇淋。店员还要和经理交互，并且一次只能一个人去见经理，经理会批准是否出售该冰淇淋。


一共有四种不同的线程。我需要：


经理一直呆在办公室中批准冰淇淋，直到批准售出的冰淇淋数量达标。


每个店员，都能制作出好吃的冰淇淋并交给顾客。


每个顾客，都能订到他们想要的冰淇淋，付完钱，离开商店。


收银员，知道他要应对 10 个不同的顾客。


image-20231219170836381