CS170 KOS

CS170 Lab Assignment 2 -- Processes and Multiprogramming
Rich Wolski and James Plank
URL: http://www.cs.ucsb.edu/~rich/class/cs170/labs/kos_mp
Directory: /cs/faculty/rich/public_html/class/cs170/labs/kos_mp
Culinary advice from a previous chef
An example Makefile that will work for submitting your solution
You must include simulator_lab2.h to pick up the right set of simulator defines for this lab.
A C function for printing the intial stack: printstack.c
Due: Wednesday Nov 16th, 2022 at 11:59 PM

Lab 2 -- Simple time-shared multiprogramming

In this lab, you will add simple, time-shared multiprogramming to KOS. Notice the use of the word "add" in the previous sentence. If your version of Lab 1 isn't working well, you may find yourself tuning that up as well. Operating systems development works in this way. Each piece you develop supports the next piece. If you find yourself spending time on Lab 1 parts to make Lab 2 parts work, you are enjoying a common reality.

Specifically, you will divide the user's memory into eight equal parts, and you will allow up to eight user processes to be in memory at any one time. There will be a timer that you can use to perform time-slicing.

Also, you will be able to compile and execute C programs under KOS that make use of malloc() and the standard I/O library.

When you are done, you will have implemented the following system calls:

ioctl() (in limited form)
fstat() (in limited form)
getpagesize()
sbrk()
execve()
getpid()
fork()
getppid()
wait()
getdtablesize()
close() (in limited form)

Moreover, you'll be able to execute a shell and use it to run user programs (although file redirection and pipes won't work).

Changes to the simulator

For this lab, you need to include the version of simulator_lab2.h from this directory. Note that this is different from the simulator.h in lab 2. You will need to link your code with
/cs/faculty/rich/cs170/lib/main_lab2.o and /cs/faculty/rich/cs170/lib/libsim.a. There is a Makefile in this directory.
For this lab, there are two special simulator variables:
```
extern int User_base;
extern int User_limit;
```
These define what KOS addresses the user sees as its memory. When a user job is executing, its address 0 is KOS's (main_memory + User_Base), and it can use up to User_Limit bytes of memory. It is KOS's job to partition the memory that it has allocated for users to multiple processes in the correct way. A user process cannot access any memory outside of the current values of User_Base and (User_Base + User_Limit). Otherwise a segmentation violation will occur.
User_Base and User_Limit also change the semantics of load_user_program(). It now loads the specified program starting at address (main_memory + User_Base), and will fail if the program contains more than int User_Limit bytes. It returns -1 on a failure. On success, it returns the size of the program loaded. You can use this as the end of the heap (i.e. the initial sbrk() pointer).
There is now a timer interrupting facility: there is a procedure call start_timer(int ticks), which tells the simulator to generate the TimerInt interrupt every ticks ticks of the clock. You may not call start_timer() more than once. The default is no timer.

Your Job in this Lab

Basically, we want to do four things in this lab:

Allow the user to compile and run programs that use the standard I/O library and malloc().
Implement the parts of KOS that enable a simple shell to work: fork(), execve() and wait().
Implement process id's.
Make time-slicing work.

I will describe each of these in turn.

Allow the user to compile and run programs that use the standard I/O library and malloc()

As before, set up KOS so that it loads the program a.out as its user process when it starts up. What we first want to do is allow these a.out programs to use the standard I/O library and malloc(). To do this, we need to do some busy work and implement some system calls that normally we would not care about. The first few are: getpagesize(), getdtablesize(), and a simple close(). Getpagesize() should return the value of the PageSize variable in simulator.h. Getdtablesize() should return 64. Close() should be implemented so that it returns an error (that's not really how to implement close(), but it will suffice for this lab).

We also have to implement one case of ioctl() and one case of fstat(). Read the man page on ioctl(). I don't expect you to understand much about ioctl() except for its syntax. You are going to need to implement ioctl() when the first argument is 1 and the second argument is JOS_TCGETP. Your job is to fill in the third argument which is a pointer to a (struct JOStermios). You do this by calling ioctl_console_fill(char *addr), where addr is the KOS address of the third argument. Then return zero. This is probably confusing, but it must be done.

Fstat() is called by the standard I/O library in order to find out how it should buffer I/O on file descriptors 0, 1 and 2. You will service these system calls by calling stat_buf_fill(char *addr, int blk_size), where addr is the KOS address of the stat struct that the user passed to fstat(), and blk_size is the amount of buffering that the file descriptor should allow. For file descriptor zero, this should be one. For file descriptors one and two, try 256.

Last, you must implement sbrk(). Read the nearest man page for more detail. As before, the stack and the heap can collide if the user messes up. However, sbrk() should not be allowed to increase past User_limit.

When you have implemented all of these system calls, the a.out programs should be allowed to use the standard I/O library (most notably printf() and malloc()). Look at the programs in

/cs/faculty/rich/cs170/test_execs

, and try ones like hw2.c that use printf(). You can write, compile and run your own programs too -- just follow the compilation steps in Makefile.xcomp and the instructions from lab 1.

Implement the parts of KOS that enable a simple shell to work: fork(), execve() and wait()

This means you must do multiprogramming. In the last lab, you allowed one user program to execute and gave it all of memory. This time, you should divide memory into 8 equal parts and when you create a new process, it will use one of those parts. Context switching will now involve saving/restoring the registers, User_base and User_limit.

You'll need to modify the exit() system call so that instead of halting KOS, it simply terminates a process. Fork() and execve() are rather straightforward. You should ignore the third argument to execve() -- we won't have any environment variables. You also must implement wait() and process id's, which should work as in Unix. In particular, processes have parents; otherwise they are orphans. If a process exits and its parent hasn't called wait() it becomes a zombie -- it releases its memory but maintains a PCB until its parent either dies or calls wait(). Orphans must do the correct thing when they die.

To test this, run

/cs/faculty/rich/cs170/test_execs/ksh

in your version of kos.

WARNING: This is a simple shell with few features. You do not need to use it and can instead, write your own test codes.

The ksh binary is capable of running other programs. For example you can run hw from ksh thus:

./kos -a /cs/faculty/rich/cs170/test_execs/ksh

and you should see

KOS booting... done.
Probing console... done.
ksh:

now run hw

ksh:/cs/faculty/rich/cs170/test_execs/hw
Hello world
the write statement just returned 12
ksh:

The ksh binary forked and execed the hw binary and called wait() to wait for it to complete before printing the ksh: prompt again.

This binary has few features and many bugs. You can use it to test fork, exec, and wait or you can write your own test codes. If it doesn't work for you, then you must write your own test codes (which is a good idea anyway). The TAs will not be able to answer questions about ksh -- either it works for you and you trust it or it doesn't and/or you don't in which case write your own testers.

Implement process id's

Finally, you need to implement getpid() and getppid() to work with your process id's. This is straightforward. I have no process with process id 0. Orphans return pid 0 as their parent.

Make time-slicing work

This is straightforward -- set the timer for some number of ticks, and then reschedule the CPU when you get the interrupt.

As in the last lab, there is a cook book of things that you might do to get this lab working. As before, it is not mandatory that you do things the same way that I did. However, it may make your life easier.

A Word About System Calls

In this lab, you need to implement working or almost working versions of several system calls. If you do not know what a system call is, don't panic. I'll tell you. When you want the operating system to do something for you, you make a system call. The arguments for the system call are documented. For example, try the command

man getpid

on your favorite Linux system in the CSIL. What you get are the header files (for the types) and the prototype for the getpid() system call. When you call getpid() on a Linux system, the program traps into the kernel and the kernel figures out how to service the call, and return the necessary values -- just like in KOS. You are implementing the KOS kernel so you have to implement the system calls that KOS supports. The ones that are specified in the lab are necessary to run a small shell called ksh. The lab gives you some details on what they should do, but for many of them, you can simply look at the man page on the CSIL systems to see what they do, what their arguments are, and what their return values are. In other words, your system calls really implement the same thing that the "real" system calls do, so the man pages are relevant.

There are some exceptions, however, which the lab points out. These have to do with the way things like the standard I/O libraries work. In these cases, the lab will tell you what values to return regardless of what the man page says.

Thus, if you find yourself a little confused over the system calls, speak to the TAs, but also consult your local man page for details.

File Modularity for Submission

For this lab, your solution needs to conform to the following file modularity:

console_buf.c
console_buf.h
exception.c
kos.c
kos.h
memory.c
memory.h
scheduler.c
scheduler.h
syscall.c
syscall.h

The submission acceptance program will be looking for these files. You should design your solution so that it is contained in files with these names.

This requirement has a few ramifications. First, this list is the file list -- not a subset of the file list. Thus, you can't include extra files and then use "#include" to include those files in these file names. The submission program will use these files and a prepared Makefile to build your program. It will not be prepared for hidden dependencies introduced by extra included files.

This requirement also means that you simply can't concatenate a bunch of files that contain your solution to create one of more of these files. The concatenation is likely to cause double definitions as header files are included multiple times which will cause your compile to fail.

Header files and libraries that are included with the makefiles we have been using in class (like libfdr, kt.h, etc.) will be referenced using the same paths that the class makefile use. Thus you should modify the class makefiles and use them as well or use the example included here.