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? _________________