6.2 The first known correct software solution to the critical-section problem for $n$ processes with a lower bound on waiting of $n − 1$ turns was presented by Eisenberg and McGuire. The processes share the following variables:

enum pstate { idle, want_in, in_cs };
pstate flag[n];
int turn;

All the elements of flag are initially idle; the initial value of turn is immaterial (between 0 and n-1 ). The structure of process $P_i$ is shown in Figure 6.26. Prove that the algorithm satisfies all three requirements for the critical-section problem.

image-20211108224130186

答:分析代码,最外层是一个死循环,flag [i] 表示进程 i 的状态。进入 while 循环后,当前进程(i)标记为 want_in,推测 turn 表示当前轮到的进程的编号,因此 j 暂存了当前可以运行的进程的编号。进入 while (i!=j) 循环,此段代码表示:如果当前可以运行的进程 j,不是本进程,并且当前可以运行的进程 j,不处于空闲状态(即正在运行或想要运行),那么就让那个进程运行。如果当前可以运行的进程 j 处于空闲状态,那么就说明 j 让出了临界区,就让 j 的下一个进程运行。

直到轮到本进程,进入 flag_[i] = in_cs 行。j 被清零,然后在 j 的合法范围内,只要 j 是当前进程或者 j 不在临界区(即 j 空闲或等待进入)就让 j 递增。因此推测,这里是为了找出第一个不在临界区的进程,暂存其编号为 j

之后的 if 语句,在 j 的合法范围内,如果轮到本进程或者上次轮到的进程为空闲状态,则跳出循环。

离开临界区后,j 设置为轮到的进程的下一个进程。然后下面的 while 循环用于找出第一个不空闲的进程,将机会交给它,然后将本进程设为空闲。

互斥性:flag [i] = in_cs,且 i 之外的所有进程都不 in_cs 时,才进入临界区。

前进性:turn 是递增的,所以每个进程都能轮到。

有限等待:每个进程需要等待其后的进程,等待的进程最多为 n-1

6.11 The Sleeping-Barber Problem. A barbershop consists of a waiting room with 11 chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.

解:首先写一个会出错的程序:

package main

import (
	"fmt"
	"math/rand"
	"os"
	"os/signal"
	"strconv"
	"syscall"
	"time"
)

// const chairNum = 11

var charAvailable = 11
var wakeup = 0

func main() {
	rand.Seed(time.Now().Unix())
	go spawnBarber()
	go spawnCustomer()
	sigChan := make(chan os.Signal, 1)
	signal.Notify(sigChan, syscall.SIGINT, syscall.SIGTERM)
	<-sigChan
	os.Exit(0)
}

var totalNum = 1000
var maxSpawnDur = 100 // 1000 = 1sec

func spawnCustomer() {
	for i := 0; i < totalNum; i++ {
		var spawnDur = time.Duration((rand.Intn(maxSpawnDur)) * 10e+5)
		time.Sleep(spawnDur)
		for j := 0; j < 10; j++ {
			go (func() {
				var id = j*10 + i
				fmt.Println("Customer " + strconv.Itoa(id) + " comes")
				if charAvailable == 0 {
					fmt.Printf("Customer %v angrily gone for no chair (available = %v) \n", id, charAvailable)
					return
				}
				if charAvailable < 0 {
					panic(fmt.Sprintf("Your program has bug! charAvailable = %v", charAvailable))
				}

				if wakeup != 0 && wakeup != 1 {
					panic(fmt.Sprintf("Your program has bug! wakeup = %v", wakeup))
				}

				for wakeup == 1 {
					time.Sleep(1 * time.Microsecond)
				}

				charAvailable--
				wakeup++
				charAvailable++
				fmt.Printf("Customer %v happily gone (available = %v) \n", id, charAvailable)

			})()
		}
	}
}

func spawnBarber() {
	for {
		for wakeup == 0 {
			time.Sleep(1 * time.Microsecond)
		}
		fmt.Printf("Barber woke up. wakeup = %v \n", wakeup)
		var workDur = time.Duration((rand.Intn(maxSpawnDur)) * 2 * 10e+5)
		time.Sleep(workDur)
		fmt.Printf("Barber sleep down. wakeup = %v \n", wakeup)
		wakeup--
	}
}

运行结果:

Customer 178 comes
Customer 179 comes
Customer 189 comes
Customer 184 comes
Customer 186 comes
Customer 180 comes
Customer 185 comes
Customer 187 comes
Customer 183 comes
Customer 188 comes
Customer 181 comes
Customer 182 comes
Barber sleep down. wakeup = 1 
Customer 187 happily gone (available = 9) 
panic: Your program has bug! charAvailable = -2

goroutine 140 [running]:
main.spawnCustomer.func1()
        C:/Repo/Sleeping-Barber-Problem/main.go:67 +0x294
created by main.spawnCustomer
        C:/Repo/Sleeping-Barber-Problem/main.go:43 +0x9c
panic: Your program has bug! charAvailable = -4

程序通过:

				if charAvailable < 0 {
					panic(fmt.Sprintf("Your program has bug! charAvailable = %v", charAvailable))
				}

				if wakeup != 0 && wakeup != 1 {
					panic(fmt.Sprintf("Your program has bug! wakeup = %v", wakeup))
				}

判断竞争条件造成的异常。

可以看到 charAvailable 变成负数。

加上 Mutex 锁:

package main

import (
	"fmt"
	"math/rand"
	"os"
	"os/signal"
	"strconv"
	"sync"
	"syscall"
	"time"
)

// const chairNum = 11

var charAvailable = 11
var wakeup = 0

func main() {
	rand.Seed(time.Now().Unix())
	go spawnBarber()
	go spawnCustomer()
	sigChan := make(chan os.Signal, 1)
	signal.Notify(sigChan, syscall.SIGINT, syscall.SIGTERM)
	<-sigChan
	os.Exit(0)
}

var mu sync.Mutex
var muId sync.Mutex

var totalNum = 1000
var maxSpawnDur = 100 // 1000 = 1sec

func spawnCustomer() {
	for i := 0; i < totalNum; i++ {
		var spawnDur = time.Duration((rand.Intn(maxSpawnDur)) * 10e+5)
		time.Sleep(spawnDur)
		for j := 0; j < 10; j++ {
			muId.Lock()
			var id = i*10 + j
			muId.Unlock()
			go (func() {
				fmt.Println("Customer " + strconv.Itoa(id) + " comes")
				if charAvailable == 0 {
					fmt.Printf("Customer %v angrily gone for no chair (available = %v) \n", id, charAvailable)
					return
				}
				if charAvailable < 0 {
					panic(fmt.Sprintf("Your program has bug! charAvailable = %v", charAvailable))
				}

				if wakeup != 0 && wakeup != 1 {
					panic(fmt.Sprintf("Your program has bug! wakeup = %v", wakeup))
				}

				for wakeup == 1 {
					time.Sleep (1 * time.Microsecond) // 等待理发机会
				}
				mu.Lock()
				charAvailable--
				wakeup++
				for wakeup == 1 {
					time.Sleep (1 * time.Microsecond) // 等待理发完成
				}
				mu.Unlock()
				if charAvailable < 0 {
					panic(fmt.Sprintf("Your program has bug! charAvailable = %v", charAvailable))
				}

				fmt.Printf("Customer %v happily gone (available = %v) \n", id, charAvailable)

			})()
		}
	}
}

func spawnBarber() {
	for {
		for wakeup == 0 {
			time.Sleep(1 * time.Microsecond)
		}
		fmt.Printf("Barber woke up. wakeup = %v \n", wakeup)
		var workDur = time.Duration((rand.Intn(maxSpawnDur)) * 2 * 10e+5)
		time.Sleep(workDur)
		fmt.Printf("Barber sleep down. wakeup = %v \n", wakeup)
		wakeup--
		charAvailable++
	}
}

此时一直运行也不会出现异常值。