# 斯坦福编程范式 CS107_16

# 接着上节课的多线程卖票例子

	void SellTickets(int agent,int *numTicketsp,Semaphore lock){
	while(true){
	SemaphoreWait(lock);
	if(* numTicketsp == 0)
	break;
	(*numTicketsp)--;
	SemaphoreSignal(lock);
	printf(" ");
	}
	SemaphoreSignal(lock);
	}

有人会问，如果现在只剩 1 张票了，而在 (*numTicketsp)-- 处线程突然中断了处理器的权限，这时候会不会出现一些意外的情况。如果有锁的话，实际上不会，现在来更详细的说说，线程处理时汇编指令和相关寄存器的状态。假设只有两个售票员即两个线程的情况，我们知道 (*numTicketsp)-- 可以转换为好几行汇编指令，比如 R1 指向这个 numTicket ， R2=R1 ，然后 R2-- 现在突然中断了处理器的使用权，那么此时这些寄存器中的数值，所有寄存器的状态，都会被保存在该线程底部的小的堆栈结构中。当他再次获得处理器的控制权后，他会将自己之前保存的寄存器状态恢复到系统的寄存器，继续进行执行。

# 使用全局结构设计

我想要写一个程序，模拟写和读取的过程。我想用 Writer 线程从互联网上写入 40 个字符，用 Reader 线程接收写在互联网上的 40 个字符。在这种情况下，可能会出现 Reader 还没读去， Writer 就又写上新的内容，或者在 Writer 还没写入新的内容， Reader 就进行读取了。

	char buffer[8];

	int main(){
	ITP(false);
	ThreadNew("Writer",Writer,0);
	ThreadNew("Reader",Reader,0);
	RunAllThread();
	}

	void Writer(){
	for(int i = 0; i<40; i++){
	char c = PrepareRandomChar();
	buffer[i%8] = c;
	}
	}

	void Reader(){
	for(int i=0; i<40; i++){
	char c = buffer[i%8];
	ProcessChar(c);
	}
	}

针对上述问题我们可以引入两个 Semaphore 信号量。

	char buffer[8];
	Semaphore emptyBuffers(8);
	Semaphore fullBuffers(0);

	int main(){
	ITP(false);
	ThreadNew("Writer",Writer,0);
	ThreadNew("Reader",Reader,0);
	RunAllThread();
	}

	void Writer(){
	for(int i = 0; i<40; i++){
	char c = PrepareRandomChar();
	SemaphoreWait(emptyBuffers);
	buffer[i%8] = c;
	SemaphoreSignal(fullBuffers);
	}
	}

	void Reader(){
	for(int i=0; i<40; i++){
	SemaphoreWait(fullBuffers);
	char c = buffer[i%8];
	SemaphoreSignal(emptyBuffers);
	ProcessChar(c);
	}
	}

这个例子中的信号量起的不是一个二进制锁的作用，而是类似一个电话，告诉对方是否可以继续进行，这是一种二进制约定。

如果我们把 emptyBuffers 的 8 变成 4，意味着 Writer 不可以超出 Buffer 携带互联网数据量的一半， Writer 和 Reader 的效率更低一些。

# 典型问题，死锁问题

五个哲学家吃饭问题，每个哲学家之间有一个叉子，他们只进行吃、思考、吃、思考两件事，吃饭需要两个叉子。

现在来编程进行建模：

	Semaphore forks[] = {1,1,1,1,1};
	void philosopher(int id){
	for(int i=0;i<3;i++){
	Think();

	SemaphoreWait(fork[id]);
	SemaphoreWait(fork[(id+1)%5]);
	Eat();
	SemaphoreSignal(fork[id]);
	SemaphoreSignal(fork[(id+1)%5]);
	}
	}

上述的代码存在问题，那就是每个人都只拿了右手的 fork 时，无论如何也不会拿到另一个 fork，这样大家都在等一个人放下 fork，但那是不可能的，于是就陷入了死锁。要想高效的解决上述问题，就需要一个添加一个允许吃饭的数量这一信号量。我们只需要阻止任意一个哲学家能够吃饭就可以解决这个问题。

	Semaphore forks[] = {1,1,1,1,1};
	Semaphore numAllowedToEat(4);
	void philosopher(int id){
	for(int i=0;i<3;i++){
	Think();
	SemaphoreWait(numAllowedToEat);

	SemaphoreWait(fork[id]);
	SemaphoreWait(fork[(id+1)%5]);
	Eat();
	SemaphoreSignal(fork[id]);
	SemaphoreSignal(fork[(id+1)%5]);

	SemaphoreSignal(numAllowedToEat);
	}
	}

斯坦福编程范式CS107

# 斯坦福编程范式 CS107_16

# 接着上节课的多线程卖票例子

# 使用全局结构设计

# 典型问题，死锁问题

斯坦福编程范式CS107_14

斯坦福编程范式CS107_17