首页 博客

# 斯坦福编程范式 CS107_15

# 接着上一次的卖票问题

int main(){
    int numAgents = 10;
    int numTickets = 150;
    for(int agent = 1;agent <= numAgents;agent++){
        SellTickets(agent,numTickets/numAgents);
    }
    return 0;
}
void SellTickets(int agentID,int numTicketsToSell){
    while(numTicketsToSell > 0){
        printf("Agent %d sell a ticket \n",agentID);
        numTicketsToSell--;
    }
     printf("Agent %d All done!\n",agentID);
}
上述的这个程序是顺序执行的，在售货员 2 号行动之前，售货员 1 号会先卖完他的 15 张票。但是在售票点中，我想要看到的是所有的售票员都在同时卖票，是竞争性的，而不是合作性的来卖一共 150 张票（哈哈哈哈）。我们想要 10 名售票员按照相同的步骤来销售这些票，并且他们看起来是同时在做这些事。


我们可以使用一个线程包和库来解决上述问题。


卖票的函数不需要任何改变，我们主要对主函数进行修改，使用一个不一样的 for  循环。如下所示。


InitThreadPackage  这里的 false  表示请不要打印任何东西，如果传入 True ，它就会打印出所有线程的信息。 sprintf  是输出到字符串缓冲区中而不是屏幕。这里的 name  指的是线程的名字， SellTickets  是传入的单一线程需要执行的函数的地址。 TreadNew  还需要知道执行函数的参数个数，在这里就是 2，以及传入参数。


在这里 SellTickets  并不会执行，它所作的只是一个入口。 RunAllThreads  将所有线程开始执行，当所有线程执行完毕后，它会将运行结果传递给程序的最后一部分。


int main(){
    int numAgents = 10;
    int numTickets = 150;
    InitThreadPackage(false);
    for(int agent=1; agent <= numAgents; agent++){
        char name[32];
        sprintf(name,"Agent %d turned",agent);
        ThreadNew(name,SellTickets,2,agent,numTickets/numAgents);
    }
    RunAllThreads();
    return 0;
}
ThreadSleep  进程休眠，单位是毫秒。下面添加的改动意味着，线程执行 SellTickets  时，会有百分之十的概率被强制暂停运行。这里加入这部分内容，引入了随机化，是为了模拟现实世界，每个人卖票的能力不同，运气好的能在这一轮中卖的更多。


C 中的线程库采用的是一种简单的轮换策略，系统会为每个线程分配时间片，每个线程都是平等的。JAVA 中可以指定线程不同的等级，等级高的具有优先执行的权力。在这里 10 个线程共用一份代码。


void SellTickets(int agentID,int numTicketsToSell){
    while(numTicketsToSell > 0){
        printf("Agent %d sell a ticket \n",agentID);
        numTicketsToSell--;
        if(RandomChance(0.1))
            ThreadSleep(1000);
    }
     printf("Agent %d All done!\n",agentID);
}
更改为不固定每个人卖票的数量，只要总数不超过需要卖的数量即可。使用指针使卖票的人员能够知道主函数中还剩多少张票


void SellTickets(int agentID,int *numTicketsp){
	while(*numTicketsp > 0){
        (*numTicketsp)--;
    }
}
这时主函数也要相应改变。这时假设还有 1 张票，售票员 1 一看 1>0 ，所以他打算卖了这张票，结果他执行了卖票操作，但是这个 (*numTicketsp)--  操作没有执行完，就突然被退出占用了；于是卖票员 2 来了，他一看，哦还有 1 张票，我把他卖了，于是他尝试去卖这张票，但是还是被立即暂停使用处理器了。同样的事发生在其余的售票员身上，每个人都试图卖掉这张票。当他们再重新获得处理器的使用权时，它们不会重新检查之前操作的执行过程，毕竟这不是概率编码。因此他们都试图减少这个共享全局变量，因此这个变量最终有可能变成 -9 ！


这是并发的一个小问题。如果他们不注意操作这些数据的方式，执行操作的过程中退出，并依据很快就会过时的数据进行判断，这样当他失去处理器的控制权的时候，全局数据的完整性就被破坏了。 while(*numTicketsp > 0){ (*numTicketsp)--;   这部分被称为临界区域。解决问题的方式就是当一个进程在处理这个临界区域内的操作时，其余进程不应该有权利进入这个临界区域进行处理，那么就需要有一些语句在临界区域前以便阻塞其他进程，即二进制的锁。


int main(){
    int numAgents = 10;
    int numTickets = 150;
    InitThreadPackage(false);
    for(int agent=1; agent <= numAgents; agent++){
        char name[32];
        sprintf(name,"Agent %d turned",agent);
        ThreadNew(name,SellTickets,2,agent,&numTickets);
    }
    RunAllThreads();
    return 0;
}
# 下面介绍信号量


SemaphoreNew  信号量的第一个参数先不管，第二个参数是一个整数。在编程中，Semaphore 变量作为一个非负整数发挥作用，支持 +1  和 -1  原子操作功能的变量。 SemaphoreWait(lock)  会改变 lock  这个变量， -1 。 SemaphoreSignal(lock)  也会接管 Semaphore 变量并 +1 。如果执行 SemaphoreWait  的时候， Semaphore  变量已经是 0 了，因为不允许 Semaphore  是负数，那么线程它就会做一个阻塞的动作，暂停占用处理器资源，因为它现在处于等待状态，临界区有其他线程在操作，需要等一个 signal  操作， lock  从 0 变为 1，它才能再进入临界区。


int main(){
    int numAgents = 10;
    int numTickets = 150;
    Semaphore lock = SemaphoreNew(???,1)
    InitThreadPackage(false);
    for(int agent=1; agent <= numAgents; agent++){
        char name[32];
        sprintf(name,"Agent %d turned",agent);
        ThreadNew(name,SellTickets,3,agent,&numTickets,lock);
    }
    RunAllThreads();
    return 0;
}
void SellTickets(int agentID,int *numTicketsp,Semaphore lock){
	while(true){
        SemaphoreWait(lock);
        if(*numTicketsp == 0)
            break;
        (*numTicketsp)--;
        printf("Agent %d sell a ticket \n",agentID);
        SemaphoreSignal(lock);
    }
    SemaphoreSignal(lock);	// 进入临界区处理，发现票卖完了，退出循环了，再把 lock+1，表示退出临界区了
}
如果我把  Semaphore lock = SemaphoreNew(???,1)  写成了   Semaphore lock = SemaphoreNew(???,0) ，那么进程会一直阻塞下去。这就是死锁现象，10 个进程都在等某一个进程从临界区出来，但其实没人再临界区，也就不会有进程从临界区出来。如果写成了 Semaphore lock = SemaphoreNew(???,2) ，那这个对临界区的锁就形同虚设。（当然也有可能其他地方， Semaphore  变量初始可以不一定是 1）。