UVa210 - Concurrency Simulator

主要涉及双端队列和单端队列的使用。

#include <stdio.h>
#include <queue>
#include <string>
#include <cstring>

enum StatementType {
    ASSIGN = 0,
    PRINT,
    LOCK,
    UNLOCK,
    END
};

struct Statement {
    StatementType type;
    int var; // varindex
    int val;
};

struct Process {
    int pid;
    std::queue<Statement> statements;
    
    Process(int pid_) : pid(pid_) {}
};

int gTimeCost[5];
int gVars[26];
int gQuantum;
bool bLocked = false;
std::deque<Process*> readyQueue;
std::queue<Process*> blockQueue;

bool parseStatement(const std::string& str, Statement& sm)
{
    if(str == "lock") {
        sm.type = LOCK;
        return true;
    }
    if(str == "unlock") {
        sm.type = UNLOCK;
        return true;
    }
    if(str == "end") {
        sm.type = END;
        return true;
    }

    if(str.substr(0, strlen("print ")) == "print ") {
        sm.type = PRINT;
        sm.var = str.back() - 'a';
        return true;
    }

    auto pos = str.find_first_of("=");
    if(pos != std::string::npos) {
        sm.type = ASSIGN;
        sm.var = str.front() - 'a';
        sm.val = strtoul(str.substr(pos+1).c_str(), NULL, 10);
        return true;
    }
    return false;
}

void runProcess(Process* p, int quantum)
{
    while(quantum > 0){
        auto sm = p->statements.front();
        switch(sm.type) {
            case PRINT:
                printf("%d: %d\n", p->pid, gVars[sm.var]);
                break;
            case ASSIGN:
                gVars[sm.var] = sm.val;
                break;
            case UNLOCK:
            {
                if(!blockQueue.empty()) {
                    auto bp = blockQueue.front();
                    blockQueue.pop();
                    readyQueue.push_front(bp);
                }
                bLocked = false;
            }
                break;

            case LOCK:
                if(bLocked) {
                    blockQueue.push(p);
                    return;
                } else {
                    bLocked = true;
                }
                break;
            case END:
                return;

            default:
                break;
        }
        p->statements.pop();
        quantum -= gTimeCost[sm.type];
    }
    readyQueue.push_back(p);
}

int main()
{
    int caseN;
    scanf("%d", &caseN);

    while(caseN-- > 0) {
        memset(gTimeCost, 0, sizeof(gTimeCost));
        memset(gVars, 0, sizeof(gVars));
        gQuantum = 0;
        bLocked = false;

        char emptyline[8];
        fgets(emptyline, 8, stdin);
        int n;
        scanf("%d%d%d%d%d%d%d", &n, &gTimeCost[0], &gTimeCost[1], &gTimeCost[2], &gTimeCost[3], &gTimeCost[4], &gQuantum);

        for(int i = 0; i < n; ++i) {
            Process *p = new Process(i+1);
            for(;;) {
                char buf[1024] = {0};
                fgets(buf, 1024, stdin);
                if(buf[strlen(buf)-1] == '\n')
                    buf[strlen(buf)-1] = '\0';
                std::string str(buf, strlen(buf));
                Statement sm;
                if(parseStatement(str, sm)) {
                    p->statements.push(sm);
                    if(sm.type == END)
                        break;
                }
            }
            readyQueue.push_back(p);
        }

        while(!readyQueue.empty()) {
            Process* p = readyQueue.front();
            readyQueue.pop_front();
            runProcess(p, gQuantum);
        }
        if(caseN > 0)
            printf("\n");
    }
}