复杂多线程问题

卖冰淇淋
这个系统里面有四个角色，1 位收银员 (Cashier)、10 位顾客 (Customers)、10 - 40 位员工 (Clerks) 和 1 位经理 (Manager)，如下图所示：
​
角色之间的关系如下：
每位顾客可能向员工购买 1 - 4 个冰淇淋，且顾客排队购买，存在有先后顺序。
每位员工只能同时制作 1 个冰淇淋。
每位员工完成冰淇淋制作后，必须经过经理检查。经理同意可以将冰淇淋交给顾客；经理不同意则需要重新制作。
经理在同一时间只能检查 1 个冰淇淋。
每位顾客拿到自己所购买的所有冰淇淋后，按排队顺序与收银员结账，收银员只能同时为一名顾客结账。
构建程序主体
int main() {
    int totalCones;
​
    InitThreadPackage();
    SetupSemaphores();
    for (int i = 0; i < 10; i++) {
        int numCones = RandomInteger(1, 4);
        // Clerk Thread 由 Customer Thread 来 spawn
        ThreadNew("", Customer, 1, numCones);
        totalCones += numCones;
    }
​
    ThreadNew("", Cashier, 0);
    ThreadNew("", Manager, 1, totalCones);
    RunAllThreads();
    FreeSemaphores();
    return 0;
}
Manager Thread
struct inspection {
    bool passed;         // init to false
    Semaphore requested; // init to 0
    Semaphore finished;  // init to 0
    Semaphore lock;      // init to 1 , get the access to manager's office
}
​
void Manager(int totalConesNeeded) {
    int numApproved = 0;
    int numInspected = 0;
​
    while (numApproved < totalConesNeeded) {
        SemaphoreWait(inspection.requested);
        numInspected++;
        inspection.passed = RandomChoice(0, 1);
        if (inspection.passed) {
            numApproved++;
        }
        SemaphoreSignal(inspection.finished);
    }
}
Clerk Thread
void Clerk(Semaphore semaToSignal) {
    bool passed = false;
    while(!passed) {
        MakeCone();
        SemaphoreWait(inspection.lock);
        SemaphoreSignal(inspection.requested);
        SemaphoreWait(inspection.finished);
        passed = inspection.passed;
        SemaphoreSignal(inspection.lock);
        SemaphoreSignal(semaToSignal);
    }
}
Customer Thread
void Customer (int numCones) {
    Browse();
    Semaphore clerksDone; // init to 0
​
    for (int i = 0; i < numCones; i++) {
        ThreadNew("...", Clerk, 1, clerksDone);
    }
​
    for (int i = 0; i < numCones; i++) {
        SemaphoreWait(clerksDone);
    }
    SemaphoreFree(clerksDone);
​
    WalkToCashier();
​
    SemaphoreWait(line.lock);
    int place = line.number++;
    SemaphoreSignal(line.lock);
    SemaphoreSignal(line.requested);
    SemaphoreWait(line.customers[place]);
}
Cashier Thread
struct line {
    int number;               // init to 0
    Semaphore requested;      // init to 0
    Semaphore customers[10];  // init to [0, ..., 0]
    Semaphore lock;           // init to 1
}
​
void Cashier () {
   for (int i = 0; i < 10; i++) {
       SemaphoreWait(line.requested);
       checkout(i);
       SemaphoreSignal(line.customers[i]);
   } 
}
参考
​Stanford-CS107-lecture-18​

Stanford-CS107 - Previous

信号量与多线程 2

Next - Stanford-CS107

函数式编程 - Scheme 1

Last modified 3yr ago

Copy link