360 LAB2pre DUE: 1-26-2023 Submit a ZIP file for TA to check and run your program 1. Download lab2pre.tgz from samples/LAB2pre run zcat lab2.tgz | tar xvf - to extract files: ------------------------------------ type.h s.s t.c queue.o wait.c mk mtx ------------------------------------ 2. type.h file #define NPROC 9 #define SSIZE 1024 #define FREE 0 // proc status #define READY 1 #define ZOMBIE 2 #define SLEEP 3 typedef struct proc{ struct proc *next; // next proc pointer: 0 int *saved_sp; // do NOT alter this field: 4 int pid; // pid = 0 to NPROC-1 int ppid; // parent pid int status; // PROC status int priority; // scheduling priority int event; // event to sleep on int exitCode; // exit code value struct proc *child; // first child PROC pointer struct proc *sibling; // sibling PROC pointer struct proc *parent; // parent PROC pointer int kstack[SSIZE]; // processs stack }PROC; 3. s.s file .global running, scheduler, tswitch tswitch: SAVE: # on entry: stack top = retPC pushl %eax # save CPU registers on stack pushl %ebx pushl %ecx pushl %edx pushl %ebp pushl %esi pushl %edi pushfl movl running,%ebx # ebx -> running PROC movl %esp,4(%ebx) # running PROC.saved_sp = esp FIND: call scheduler # pick a new running PROC RESUME: movl running,%ebx # ebx -> (new) running PROC movl 4(%ebx),%esp # esp = (new) running PROC.saved_sp popfl # restore saved registers from stack popl %edi popl %esi popl %ebp popl %edx popl %ecx popl %ebx popl %eax ret # pop stackTop into PC: return by retPC 3 t.c file: /*********** A Multitasking System ************/ #include <stdio.h> #include <string.h> #include "type.h" // #include "queue.c" // comment in to use YOUR queue.c file #include "wait.c" // global variables PROC proc[NPROC]; // 9 PROCs PROC *freeList; // FREE proc list PROC *readyQueue; // priority queue of READY procs PORC *sleepList; // SLEEP proc list PROC *running; // pointer to current RUNNING proc int init() // initialize freeList, readyQueue, sleepList { int i; for (i = 0; i < NPROC; i++){ proc[i].pid = i; // pid = 0 to NPROC-1 proc[i].status = FREE; proc[i].priority = 0; proc[i].next = (PROC *)&proc[(i+1)]; } proc[NPROC-1].next = 0; freeList = &proc[0]; // freeList of procs readyQueue = 0; // readyQueue = NULL sleepList = 0; // sleepList = NULL printFreeList(freeList); // show freeList // create P0 as the initial running process running = dequeue(&freeList); // running = proc[0] off freeList running->status = READY; running->priority = 0; // P0 priority = 0 running->child = 0; running->sibling = 0; running->parent = running; printf("init complete: P0 running\n"); printFreeList(freeList); // show freeList again } int body() { char command[64]; while(1){ printf("***************************************\n"); printf("proc %d running: Parent = %d\n", running->pid, running->ppid); printf("command [ps|fork|switch] : "); // start with 3 commands // printf("command [ps|fork|switch | sleep|wakeup |exit|wait] : "); fgets(command, 64, stdin); command[strlen(command)-1] = 0; // kill \n at end if (strcmp(command, "ps")==0) ps(); else if (strcmp(command, "fork")==0) kfork(body, 1); else if (strcmp(command, "switch")==0) tswitch(); else printf("invalid command\n"); } } /******************************************************* kfork() creates a child porcess to execute func(); returns child pid. When scheduled to run, child PROC resumes to execute func(); ********************************************************/ int kfork(int func, int priority) { PROC *p; int i; /*** get a proc from freeList for child proc: ***/ p = dequeue(&freeList); if (!p){ printf("no more proc\n"); return(-1); } /* initialize the new proc and its stack */ p->status = READY; p->priority = priority // scheduling priority p->ppid = running->pid; // ppid = caller's pid p->child = p->sibling = 0; p->parent = running; // -1 -2 -3 -4 -5 -6 -7 -8 -9 // kstack contains: |retPC|eax|ebx|ecx|edx|ebp|esi|edi|eflag| // func 0 0 0 0 0 0 0 0 for (i=1; i < 10; i++) p->kstack[SSIZE - i] = 0; p->kstack[SSIZE-1] = (int)func; // retPC=address of func() p->saved_sp = &(p->kstack[SSIZE - 9]); // saved sp enqueue(&readyQueue, p); // enter p into readyQueue by priority return p->pid; } /*************** main() ***************/ int main() { printf("Welcome to 360 Multitasking System\n"); init(); // initialize freeList, readyQueue; create P0 as running proc kfork(body, 1); // P0 fork child P1, put in readyQueue printf("P0: switch task\n"); tswitch(); // switch to run P1; P0 in readyQueue while(1); // if P0 resumes, just loop } /*********** scheduler *************/ int scheduler() { printf("proc %d in scheduler()\n", running->pid); if (running->status == READY) enqueue(&readyQueue, running); printList("readyQueue", readyQueue); running = dequeue(&readyQueue); printf("next running = %d\n", running->pid); } 4. mk sh script rm a.out gcc -m32 t.c s.s queue.o a.out 5. Demonstration of mtx ================ Programming Requirements ======================= 1. Write your OWN queue.c file to replace queue.o Modify mk to rm a.out gcc -m32 t.c s.s #include "queue.c" in t.c file a.out YOUR queue.c file must implement the following functions: /****************** queue.c file ********************/ int enqueue(PROC **queue, PROC *p) // NOTE **queue { // enter p into queue by priority; FIFO if same priority } // remove and return first PROC from queue PROC *dequeue(PROC **queue) // NOTE **queue { // remove and return FIRST element in queue } int printFreeList(PROC *p) // print list p { // print the list as freeList=[pid pri]->[pid pri] ->..-> NULL } int printReadyQueue(PROC *p) // print list p { // print the list as readyQueue=[pid pri]->[pid pri] ->..-> NULL } int printSleepList(PROC *p) // print list p { // print the list as sleepList=[pid event]->[pid event] ->..-> NULL } int printChildList(PROC *p) // print list p { // print the list as childList=[pid status]->[pid status] ->..-> NULL } NOTE: you may write a SINGLE int printList(char *name, int what) for ALL the above print functions, name = "listname" what = 0: print [p->pid p->priority], what = 1: print [p->pid p->event], what = 2: print [p->pid p->status as STRING] HOW? Read Chapter 3.3.3 Time needed: 10 minutes? ====================================================================== 3. In wait.c file: implement ksleep() as in 3.4.1 implement kwakeup() as in 3.4.2 Test sleep, wakeup commands to verify YOUR ksleep/kwakeup work: For the sleep command: ensure P1 does NOT sleep Run mtx P1: fork : fork a child P2; switch : switch to run P2 P2 : sleep, with a value, e.g. 123 to let P2 SLEEP. P1 : wakeup with a value, e.g. 234 Did any proc wake up?_____________________ P1 : wakeup with 123 What happens?_____________________________ ==================================================================== 4. Modify kfork() to implement processes as a BINARY tree using the child, sibling pointers of PORCs. When a process runs, print its childList as childList = [pid status]->[pid status]->...->NULL parent->---------- p->-------- | child | | . .-|--sibling=0 ----|------ ----|---- .-------->.------>. ..->NULL child=0 sibling HOW? read Chapter 2 insert() function. ================================================================== 5. In wait.c file: implement kexit() as in 3.5.1 To give children to P1: remove running's childList, insert it into P1's childList implement kwait() as in 3.5.3 if no child: return -1 for error; // has child: loop: To find a ZOMBIE child: same as to delete() a ZOMBIE child; delete() returns a pointer -> ZOMBIE child get ZOMBIE's exitCode FREE ZOMBIE child; return ZOMBIE pid; ksleep(); goto loop; ==================================================================== Test the exit, wait commands to verify YOUR kexit/kwait work: For the exit command, ensure P1 does NOT exit Run mtx; P1: enter wait; What happens?________________ WHY?_________________ CASE 1: child exit first, parent wait later P1: fork a child P2, switch to P2. P2: enter exit, with a value, e.g. 123 ==> P2 will die with exitCode=123. Which process runs now?_______________________ WHY?____________________ enter ps to see the proc status: P2 status = ? ____________________________ (P1 still running) enter wait; What happens?_______________________________ enter ps; What happened to P2?__________________________ CASE 2: parent wait first, child exit later P1: enter fork to fork a child P3 P1: enter wait; What happens to P1?______________________ WHY?______________ P3: Enter exit with a value; What happens?___________________________________ P1: enter ps; What's the status of P3?_________________ WHY? _________________