/* 1991 ACM Finals Problem B Concurrency Simulator Ed Karrels, May 1996 */ #include #include typedef struct Stmt { int type, cnst, var; struct Stmt *next; } Stmt; typedef struct Proc { int proc_id; Stmt *stmt; struct Proc *next; } Proc; Stmt *ReadStmt() { char str[10]; Stmt *s; int i; s = (Stmt*)malloc(sizeof(Stmt)); s->next = 0; scanf("%s", str); if (!strcmp(str, "print")) { s->type = 1; scanf("%s", str); s->var = *str-'a'; } else if (!strcmp(str, "lock")) { s->type = 2; } else if (!strcmp(str, "unlock")) { s->type = 3; } else if (!strcmp(str, "end")) { s->type = 4; } else { s->type = 0; s->var = *str - 'a'; scanf(" = %d", &s->cnst); } return s; } Proc *Append(Proc *q, Proc *proc) { Proc *head; proc->next = 0; if (!q) { return proc; } else { head = q; while (q->next) q = q->next; q->next = proc; return head; } } int main() { Stmt *procs, *stmt; Proc *ready_q = 0, *block_q, *proc, *tmp_proc; int proc_no, n_proc, runtime[5], quantum, slice_left; int vars[26], i, locked; scanf("%d %d %d %d %d %d %d", &n_proc, runtime, runtime+1, runtime+2, runtime+3, runtime+4, &quantum); procs = (Stmt*)malloc(sizeof(Stmt) * n_proc); for (proc_no=0; proc_nostmt = stmt; proc->proc_id = proc_no+1; while (stmt->type != 4) { stmt->next = ReadStmt(); stmt = stmt->next; } ready_q = Append(ready_q, proc); } for (i=0; i<26; i++) vars[i]=0; block_q = 0; slice_left = quantum; locked = 0; while (ready_q) { proc = ready_q; ready_q = ready_q->next; /* printf("proc %d: ", proc->proc_id); */ stmt = proc->stmt; switch (stmt->type) { case 0: /* printf("%c = %d\n", stmt->var+'a', stmt->cnst); */ vars[stmt->var] = stmt->cnst; break; case 1: printf("%d: %d\n", proc->proc_id, vars[stmt->var]); break; case 2: /* printf("lock\n"); */ if (locked) { block_q = Append(block_q, proc); slice_left = quantum; continue; } else { locked = 1; } break; case 3: /* printf("unlock\n"); */ locked = 0; if (block_q) { tmp_proc = block_q; block_q = block_q->next; tmp_proc->next = ready_q; ready_q = tmp_proc; } break; default: /* printf("end\n"); */ } slice_left -= runtime[stmt->type]; /* if process halts, don't put back in queue */ if (stmt->type != 4) { proc->stmt = stmt->next; if (slice_left <= 0) { ready_q = Append(ready_q, proc); slice_left = quantum; } else { proc->next = ready_q; ready_q = proc; } } } /* while */ return 0; }