CS 444/544 Programming Projects 1 to 5 solution

Description

CS 444/544 Programming Project 1

1. Create a single Makefile that will build all of the below C programs. Place them all in a single
directory (no sub-directories). If you don’t have a Makefile, your submission will not be graded. If
your Makefile does not build a portion of your assignment, that portion will receive a zero grade.
I expect to build all the programs below by using the following two commands:
make clean
make all
If this does not work, it will be bad for your grade on this assignment.
2. Write a C program that calls fork(). Before calling fork(), have the parent process assign the
value 100 to int called xx. What value is the value of xx in the child process? Have the parent
process assign the value 999 to xx and have the child process assign the value 777 to xx. What
happens to xx variable when both the child and parent change the value of xx? Have both
processes print the value of xx.
3. Write a C program that opens a file name “JUNK.txt” (with the fopen() function call). Have
the parent process print “before fork” into the file. The parent process should call fork() to
create a new process. Have the parent process perform a for loop that prints “parent” into the
open file 10 times. Have the child process perform a for loop that prints “child” into the open file
10 times. What happens when they are writing to the file concurrently, i.e., at the same time
(answer this in the comments in your code)?
4. Write a C program using fork(). The child process should print “hello” to stdout; the parent
process should print “goodbye” to stdout. Make sure that the child process always prints first.
Can you do this without the parent calling wait() in the parent (and NOT using some big loop in
the parent)?
5. Write a C program that calls fork() and then the child process calls each of the following exec()
functions to run the program “ls -l -F -h”: execl(), execlp(), execv(), and
execvp(). The parent process must wait until the child process is complete before it exits.
Describe the differences of the exec functions in your code as comments.
Final note
The programming projects in this course are intended to give you basic skills. In later programming
projects, we will assume that you have mastered the skills introduced in earlier programming projects. If
you don’t understand, ask questions.

CS 444/544 Lab 2

Heap management – beavalloc
You know you’ve been wanting to do this, so finally, here is your opportunity. Write you own
malloc package. You are going to call it beavalloc() and beavfree(). Those are the
basic functions. You also need to implement beavcalloc() and beavrealloc(), but
those are implemented using beavalloc() (with some extra code). Your code must not
make any use of any of the library malloc() functions. You can use brk() and sbrk() for
requesting or returning portions of the heap. In fact, you must use brk() and sbrk(). You
will manage the memory that is allocated.
You may notice this line in the man page for brk()/sbrk():
Avoid using brk() and sbrk(): the malloc(3) memory allocation package is the
portable and comfortable way of allocating memory.
Ha!!! As an accomplished C programmer and kernel hacker, you are empowered to use brk()
and sbrk() to write your own comfortable heap manager.
There are a lot of various examples of malloc() source code out there. I encourage you to
not rely on those and learn this on your own.
Your implementation of beavalloc() (and the other functions) must be done in a file called
beavalloc.c. You must put your main() in a separate file. I’ll provide you with a main()
that calls a number tests for your beavealloc() functions. I have provided a file
beavalloc.h, read the comments in that file.
You must have a Makefile that builds your project. I have placed a sample Makefile, the
beavalloc.h file, and sample main.c in the following directory on flip/os[12]:
~chaneyr/Classes/cs444/Labs/Lab2
CS 444/544 Lab 2
Fall 2019 Page 2 of 7 R. Jesse Chaney
Do not make changes to the beavalloc.h file. Do what you will with the Makefile, just
don’t hurt my feelings. Do not remove any of the flags for gcc (CFLAGS). I expect to build the
beavalloc program by using the following two commands:
make clean
make all
Be sure to test your code. The main.c file has a few tests in it. Run all the tests and check to
make sure the output is correct. Just because your code does not seg-fault, it does not mean
the code correctly operates. The tests can either be run all at once or individually. I recommend
you run them individually; it makes them easier to validate.
You can use whatever data structure to manage the heap you like. I decided to use a doublylinked list. It worked very well for me. I would say that it is he most space or time efficient, but
that is not the objective.
This is not an exercise to see if you can develop the fastest or most compact malloc()
replacement. Many people have spent years working on that; you don’t need to. This is a
simple 1-week assignment; don’t make it more than that.
Functions you need to write are:
void *beavalloc(size_t size);
The basic memory allocator. If you pass NULL or 0, then NULL is returned. If, for
some reason, the system cannot allocate the requested memory, set the errno
global variable to ENOMEM and return NULL. You must use sbrk() or brk()
in requesting more memory for your beavalloc() functions to manage.
When calling sbrk() for more memory, always request 1024 bytes. It is best if
you use a macro for this value, in case it needs to change. Making kernel calls is
expensive, so we want to minimize them.
Notice that the parameter type is size_t, which is unsigned. If you happen to
pass a negative value, odd things may occur.
When beavalloc() is called, only call sbrk() to request more memory
form the kernel when there is not enough space in the currently allocated space
to accommodate it. You must be able split existing blocks within the allocated
space. If an existing block can be split to hold a new request, split it and use it.
Correctly splitting blocks is probably the second most challenging portion of the
project. You will be using a first-fit algorithm.
First-fit algorithm – when receiving a request for memory, scan along the list for
the first block that is large enough to satisfy the request. If the chosen block is
significantly larger than that requested, then it is split, and the remainder added
to the list as another free block.
CS 444/544 Lab 2
Fall 2019 Page 3 of 7 R. Jesse Chaney
void beavfree(void *ptr);
A pointer returned from a previous call to beavalloc() must be passed. If a
pointer is passed to a block than is already free, simply return. If NULL is passed,
just return. Blocks must be coalesced, when possible, as they are free’ed.
Correctly coalescing may be the most challenging portion of this project.
void beavalloc_reset(void);
Completely reset your heap back to zero bytes allocated. You are going to like
being able to do this. Implementation can be done in as few as a single line of C
code, though you will probably use more to clean up some variables and reset
any stats you keep about heap. The only time you actually give memory back to
the OS is when you make this call. A call to beavfree() will only mark the
space available for reuse.
After you’ve called this function, everything you had in the heap is just
__GONE__!!! You should be able to call beavalloc() after calling
beavalloc_reset() to restart building the heap again.
void beavalloc_set_verbose(uint8_t);
I like to have the ability to enable and disable runtime diagnostic messages. A
call of beavalloc_set_verbose( TRUE ); will enable runtime
diagnostic messages. A call of beavalloc_set_verbose( FALSE ); will
disable runtime diagnostic messages. All runtime diagnostic messages must go
to stderr, not stdout.
void *beavcalloc(size_t nmemb, size_t size);
This function should perform exactly as the regular call to calloc() would
perform. You can read the man page to see what it does. If nmemb or size is 0,
then beavcalloc() returns NULL. Make use of your beavalloc(); don’t
reinvent anything for this. Consider the memset() function.
void *beavrealloc(void *ptr, size_t size);
This function should perform exactly as the regular call to realloc(). You can
read the man page to see what it does. If size is NULL, return NULL. Consider
the memcpy() or memmove() functions. When this function is called with
NULL, it means the pointer has never been allocated. Since this we expect the
memory block size to change (likely upward, this is realloc() after all), when
the ptr is NULL, actually allocate 2 times the size passed as a parameter.
void beavalloc_dump(uint leaks_only);
This is the function you must use to display the contents of your heap. It is a
large and messy function. I understand that you may need to make a few
adjustments to it so that it will work with your data structures. However, make
CS 444/544 Lab 2
Fall 2019 Page 4 of 7 R. Jesse Chaney
as few as possible and DO NOT remove any of the columns of data shown in the
original implementation.
A longer description of the output from the beavalloc_dump() is shown in
an addendum on page 5. This function can be found in the file
beavalloc_dump.c. I recommend you copy it into your beavalloc.c
module.
Look in the beavalloc.h file for declarations of the above functions.
Below is a raw plan on how you can proceed. This plan is basic and not required, but it is pretty
much how I worked through the project.
1. Start your Makefile. Initiate revision control.
2. When beavalloc() is called, just call sbrk() for the new space. Place that new
space into your data structures to manage the space. Don’t worry about the other calls
for now. Check your code into revision control.
3. Make sure beavaalloc_reset() works and deallocates all space previously
allocated using sbrk(). This will probably be a lot easier than you think. Consider
doing a little brk() dancing for this. A static variable within your beavalloc.c
file could make this really easy. Check your code into revision control.
4. When beavefree() is called, set the block as free/unused in your data structures.
Check your code into revision control.
5. Split blocks that are large enough when memory is requested. Check your code into
revision control.
6. Coalesce blocks when adjacent blocks are free-ed. Check your code into revision control.
7. Implement beavcalloc(). This is pretty simple. Check your code into revision
control.
8. Implement beavrealloc(). Slightly more involved that beavcalloc(). Check
your code into revision control.
9. Make sure all the tests work. Just because a test does not seg-fault does not mean the
test ran correctly. Break out a calculator and make sure things add up. Most computerbased calculators have a “programmer” mode that will allow you to calculate the hex
addresses. I know both Mac and Windows have this feature in the calculator. Check
your code into revision control.
10. Celebrate. This was my favorite step.
I recommend you make use of the assert() statement in your code. You can see some
examples of it in the testing code I provide and by looking at the man page. Remember, testing
is good.
You must use the following gcc command line options (with gcc as your compiler) in
your Makefile when compiling your code.
-g
-Wall
CS 444/544 Lab 2
Fall 2019 Page 5 of 7 R. Jesse Chaney
-Wshadow
-Wunreachable-code
-Wredundant-decls
-Wmissing-declarations
-Wold-style-definition
-Wmissing-prototypes
-Wdeclaration-after-statement
Be sure your code does not generate any errors or warnings when compiled. Hunt down and
fix all warnings in your code. You may not use any `std=…` command line options for gcc.
Just use the default standard, i.e. c90.
For a comparison, my beavalloc.c file contains less than 500 lines of code. I have some
comments and some extra things in there taking up space. You don’t have to (completely) write
the beavalloc_dump() function. All in all, it is not a huge chunk of code.
Final note
The labs in this course are intended to give you basic skills. In later labs, we will assume that
you have mastered the skills introduced in earlier labs. If you don’t understand, ask questions.
Addendum – Format of the beavalloc_dump() output.
Below is an example of running my code on test 5 from the suite of tests. The heap map
consists of several columns of data. The beavalloc_dump() function has 2 purposes: 1)
help grade the assignment, 2) help debug the assignment. The columns in the output are:
blk no: I start numbering the blocks managed by beacalloc() from zero, so the initial block
number is block 0. For me, this is the start of the doubly-linked list I use to manage the heap. It
is also the address of the beginning of the heap.
block add: this is the beginning address of a block beavalloc() is managing in the heap. For
me, it is the beginning of an instance of the structure in my doubly-linked list. This address is
shown as hex.
next add: the doubly-linked list I use contains 2 pointers for the previous and next elements in
the list. This is the address of the next element. If the next address is (nil), it means that it is the
head of the list. This address is shown as hex.
prev add: the doubly-linked list I use contains 2 pointers for the previous and next elements in
the list. This is the address of the previous element. If the previous address is (nil), it means that
it is the end of the list. This address is shown as hex.
data add: in my list element data structure, I keep a pointer to where the data for the block
begins. This is that pointer; it is a little wasteful to keep this around as a pointer. This address is
shown as hex.
blk off: this is the offset (in decimal) where the block begins from the beginning of the heap.
CS 444/544 Lab 2
Fall 2019 Page 6 of 7 R. Jesse Chaney
dat off: this is the offset (in decimal) where the data begins from the beginning of the heap.
capacity: this represents the total number of data bytes available in the block (in decimal).
Some or even most of the bytes may not be used. See the size column below.
size: this represents the number of data bytes (in decimal) requested by the user’s call to
beavalloc(). This is the number of bytes the user can use in the block. If the user goes
beyond size bytes, then they have actually gone out of bounds of their allocation. The block
may have a capacity larger than the size. The additional bytes could be used in a call to
beavrealloc() or the block could be split (if large enough).
blk size: the total number of bytes used by the block (in decimal). This will be the sum of the
capacity and the size of the data structure used to manage the heap.
status: this simply represents whether a block is currently in use (allocated to the user) or is
free (awaiting reuse).
The row of data below the per block information shows (in decimal) the total number of bytes
of data capacity that are currently allocated, the total number of bytes the user currently has in
use, and the total number of bytes are allocated in the heap.
The final line in the output from beavalloc_dump() shows: how many blocks are allocated
to the user, how many block are marked as free, what is the address of the beginning of the
heap is (Min heap), and what the address of the end of the heap is (Max heap).
CS
444/544 Lab
2
Fall 2019 Page
7 of
7 R. Jesse Chaney % ./beavalloc -t 5 beavalloc tests starting running only test 5 *** Begin 5 base: 0x12b3000 5 allocs 3 frees ptr5 : 0x12b4030 ptr4 : 0x12b3c30 ptr3 : 0x12b3830 ptr2 : 0x12b3430 ptr1 : 0x12b3030 heap map blk no block add next add prev add data add blk off dat off capacity size blk size status 0 0x12b3000 0x12b3400 (nil) 0x12b3030 0 48 976 510 1024 in use 1 0x12b3400 0x12b3800 0x12b3000 0x12b3430 1024 1072 976 530 1024 in use 2 0x12b3800 0x12b3c00 0x12b3400 0x12b3830 2048 2096 976 550 1024 in use 3 0x12b3c00 0x12b4000 0x12b3800 0x12b3c30 3072 3120 976 570 1024 in use 4 0x12b4000 (nil) 0x12b3c00 0x12b4030 4096 4144 976 590 1024 in use Total bytes used 4880 2750 5120 Used blocks: 5 Free blocks: 0 Min heap: 0x12b3000 Max heap: 0x12b4400 heap map blk no block add next add prev add data add blk off dat off capacity size blk size status 0 0x12b3000 0x12b3400 (nil) 0x12b3030 0 48 976 510 1024 free * 1 0x12b3400 0x12b3800 0x12b3000 0x12b3430 1024 1072 976 530 1024 in use
2 0x12b3800 0x12b3c00 0x12b3400 0x12b3830 2048 2096 976 550 1024 free *
3 0x12b3c00 0x12b4000 0x12b3800 0x12b3c30 3072 3120 976 570 1024 in use
4 0x12b4000 (nil) 0x12b3c00 0x12b4030 4096 4144 976 590 1024 free *
Total bytes used 4880 2750 5120
Used blocks: 2 Free blocks: 3 Min heap: 0x12b3000 Max heap: 0x12b4400
WoooooooHooooooo!!! You survived test 5.
*** End 5
Make sure it is correct.

CS 444/544 Lab 3

Working with inodes – mystat (100 Points)
For this part of this assignment, you will write a C program that will display the inode meta data for
each file given on the command line. You must call you source file mystat.c and your program will be
called mystat. This program will run directly on os2, not within xv6.
An example of how my program displays the inode data is shown the Figure 4. You might also want to
look at the output from the stat command (the command not a system function, man section 1).
Though not as pretty (or in some cases as complete as the replacement you will write), it is the standard
for showing inode information.
Requirements for your program are:
1. The output of your program should look exactly like mine.
2. Display the file type (regular, directory, symbolic link, …) as a human readable string. If the file is
a symbolic link, look 1 step further to find the name of the file to which the symbolic link points.
If the file to which the link points does not exist, indicate that. See Figure 4.
3. Display the inode value.
4. Display the device id.
5. Display the mode as both its octal value and its symbolic representation. The symbolic
representation will be the rwx string for user, group, and other. See Figure 4 or ‘ls -l’ for
how this should look.
6. Show the hard link count.
7. Show both the uid and gid for the file, as both the symbolic values (names) and numeric
values. This will be pretty darn easy if you read through the list of suggested function calls. See
Figure 4 for how this should look.
8. File size, in bytes.
9. Block count.
10. Show the 3 time values in local time/date. This will be pretty darn easy if you read through the
list of suggested function calls. See Figure 4 for how these appear.
CS 444/544 Lab 3
Fall 2019 Page 2 of 4 R. Jesse Chaney
System and function calls that I believe you will find interesting include: stat()and lstat() (you
really want to do “man 2 stat” and read that man entry closely, all of it [yes really, all of it]),
readlink(), memset(), getpwuid(), getgrgid(), strcat(), localtime(), and
strftime(). Notice that ctime() is NOT in that list and you don’t want to use it. Since you must be
able to show the file type if a file is a symbolic link, I encourage you consider lstat() over stat().
My implementation is about 280 lines long, but there is some dead code in my file. I have code
commented out to support features not required for your assignment. There is no complex logic for this
application, just a lot of long code showing values from the struct stat structure from
sys/stat.h. Honestly, the longest portion of your code will likely be devoted to displaying the
symbolic representation of the mode. Formatting these strings is a little awkweird. I suggest you create
a function. Don’t worry about sticky bits or set uid/gid bits. Do you know what sticky bits are for or how
they used to be used?
You must to be able to show the following file types:
• regular file,
• directory,
• character device,
• block device,
• FIFO/pipe,
• socket, and
• symbolic link (both a good one and a broken one).
When formatting the human readable time for the local time, I’d suggest you consider this “%Y-%m-%d
%H:%M:%S %z (%Z) %a”, but read through the format options on strftime(). The executable
version of my code is in the directory. You are welcome to run it to see the output.
I have some examples of both a FIFO/pipe, a socket, symbolic link in my Lab3 directory for you to use in
testing (the FUNNY*
files, Figure 2). You can
find a block device as
/dev/sda and a
character device as
/dev/sg0. See Figure 3.
You must have a Makefile that builds the mystat program, without any warnings from the
compiler. You must use the following gcc command line options (with gcc as your compiler) in your
Makefile when compiling your code:
Figure 2: The FUNNY* files.
Figure 3: Block and character files.
Figure 1: A sample of files to use for your testing. Found in ~chaneyr/Classes/cs444/Labs/Lab3
CS 444/544 Lab 3
Fall 2019 Page 3 of 4 R. Jesse Chaney
-g
-Wall
-Wshadow
-Wunreachable-code
-Wredundant-decls
-Wmissing-declarations
-Wold-style-definition
-Wmissing-prototypes
-Wdeclaration-after-statement
When we grade your program, we will issue the following commands to build your executable.
make clean
make all
There must be zero (0) warnings from the compiler. If your program compiles and produces warnings
(using the above command line options for gcc), then it is a zero.
Final note
The labs in this course are intended to give you basic skills. In later labs, we will assume that you have
mastered the skills introduced in earlier labs. If you don’t understand, ask questions.
For those of you have read this far and are actually reading the entire assignment, thank you. As a
reward, if you look at the section 2 man page for stat(), down near the bottom, I think you’ll like it.
That is:
man 2 stat
CS 444/544 Lab 3
Fall 2019 Page 4 of 4 R. Jesse Chaney
Figure 4: The inode information of the FUNNY files. Sorry the image is so small.
A directory.
A pipe.
A regular file.
A socket.
A symbolic link.
A broken symbolic link.

CS 444 Lab 4

Part 1 – Some additional programs – (10 points)
In class, we added the mult.c and mfork.c programs into the xv6 system (by adding the C
code, and editing the Makefile). I need you to make sure those programs are a regular part
of your xv6 system. You will use these programs to test the correct functioning of your code
and they will be used to test your code when grading your assignment. The C files mult.c and
mfork.c can be found in my Lab4 directory, ~chaneyr/Classes/cs444/Labs/Lab4
The purpose of the mult program is to just take a long time to complete. The purpose of the
mfork program is to just fork a number of processes in xv6. Add these into the UPROGS
macro in your Makefile.
Part 2 – Add some tracking information to each process (100 pts)
Add four members to the struct proc data structure (found in proc.h). Remember, you
are the kernel developer and master level C programmer, so you should be comfortable
manipulating the kernel structures. Of course, I put all this stuff within #ifdef blocks using a
macro called PROC_TIME.
1. Add a member type struct rtcdate. You’ll find the definition of that structure in
the date.h file. I like to call this member begin_date.
2. Add 3 members of type unsigned int. Good names for those 3 members are:
a. ticks_total – this will represent the total number of time ticks that the
process has run.
CS 444 Lab 4
Fall 2019 Page 2 of 7 R. Jesse Chaney
b. ticks_begin – this will be used to help calculate the total number of time
ticks the process has used.
c. sched_times – this will be used to count the number of times the process has
been scheduled to run.
You can find the definition of struct rtcdate in the date.h file. While you are in the
date.h file, make sure it has multiple-include protection.
Now that you have the new data members in the struct proc data structure, it’s time to
put them to use. When a process is first allocated, set the begin_date to the “current”
date/time. How do you know where a process is first allocated? You might look for a function
called something like allocproc(). The qemu clock seems to synchronize to UTC time at
startup. If you really want it set to the current Pacific time, ask me how (it is a little make
magic). Finding the right call to get the date/time is a little awkward. I recommend you look in
the lapic.c file for the function cmostime(). However, you probably don’t want to spend
too much time looking at that in that file, it’s a bit icky. Calling the cmostime() function is a
wee bit awkward, because you must pass an address or pointer. Remember that putting an & in
front of a variable/structure when calling a function will pass the address of the
variable/structure. Decide to ignore the goto and the label found in that function; we won’t
talk about them.
Once you set the begin_date member, set ticks_total , ticks_begin, and
sched_times to zero in the same area of the code (when a new process is allocated).
Now let’s look at the scheduler() code (in proc.c). You’ll notice that the scheduler runs
as an infinite loop (see the for(;;) ?). There are 2 places where you want to add a few lines
of code into the scheduler() routine. One is just before the newly chosen process is
scheduled and the other is just after that process returns back to the scheduler. The first place
(before the newly chosen process runs), is pretty easy to find. Look for the place where the
state of the process is set to RUNNING. I dropped an #ifdef block just before that. That block
does 2 things, it increments the sched_times member for the chosen process, and sets the
begin_ticks member to the current number of ticks that have accumulated for the vm.
How do you find out how many “ticks” the system has been up? That is an excellent question.
My recommendation is to look for a function called uptime(). Unfortunately, because of how
the kernel function uptime() is defined and implemented (as sys_uptime()), you cannot
directly call it. You have a choice to either 1) replicate the capability of uptime() in the
scheduler() code (which I do not like), or 2) make a new function that returns the same
thing (which I do like). If you decide to do the second option, I recommend you have
sys_uptime() directly call your new function. I went with option 2; I don’t like to duplicate
code.
Now, about that second place to drop in a few lines of code. What do you think the following 2
lines of code from the scheduler() function do?
swtch(&(c->scheduler), p->context);
switchkvm();
CS 444 Lab 4
Fall 2019 Page 3 of 7 R. Jesse Chaney
ln addition, notice that immediately after those lines of code, the c->proc variable is set to 0
(aka NULL). So, might this be that when a new process is actually scheduled to run by calling
swtch() and switchkvm(), and it returns back to scheduler following those calls? Looks
like a good place to update the total_ticks member of the process (after return from
switchkvm()).
Part 3 – Modify ps to show time tracking information (50 pts)
Now that you have all this great time tracking information for each process, modify your ps
program to display it.
You should display the information as follows.
One of the fun things you’ll notice is that you may need to put a zero in where a value is
represented as a single digit. Notice that the month shown in the start time is 05, not just
5. It’s a simple trick, but worth learning. If you had a fully functioning printf() (or for this
example cprintf()), it would be just a change to the format string. However, your
printf() is not capable of that (and don’t spend the month or 6 working on the format
characters in the xv6 version of printf()).
Part 4 – Add a rand() function (50 pts)
You will need to use a function the generates random numbers. More specifically, pseudorandom numbers. This does not need to be cryptographically secure random numbers, just
something reasonable, such as the standard Unix/Linux rand() function returns.
Amazingly, if you happened to read to the bottom of the man page for rand, in section 3 of
the man pages, you can see some source code for a version of rand() that works just fine for
this purpose. Differing from the man page example, you will call your functions rand() and
srand(), NOT myrand() and mysrand(). If you prefer to use some other swanky random
number generator, that’s fine but not required.
Your implementation of rand() must be done in 2 files: rand.c and rand.h. The rand.c
file will contain the implementation of rand() and srand(). The rand.h file will contain
the declarations (aka prototypes) of rand() and srand() AND must contain the macro
RAND_MAX, yep you need a macro.
CS 444 Lab 4
Fall 2019 Page 4 of 7 R. Jesse Chaney
Based on the code in the man page, you’d establish RAND_MAX to be 32767 (2^15), but we are
going to use 2^31. So, your RAND_MAX macro should be (1 << 31). Yes, use parenthesis
around the shift operation. Do you see in the code in the man page where the random value is
returned? It does a % 32767. You will replace the 32767 with your RAND_MAX macro.
Great, you’ve written your code for rand() and srand(), but you need to get them into the
kernel. They must be callable from within the kernel, so they must be linked with the kernel.
Luckily, this is very easy. Up at the top of the Makefile, there is a variable called OBJS. At
the end of the list of .o files in the OBJS variable, just add rand.o\ (and don’t omit the
trailing backslash). Assuming that your rand.c and rand.h files don’t have any compilation
errors, simply running make should rebuild the xv6 kernel with your new calls in it.
Part 5 – Create the rand command (50 points)
Since we have our great kernel function rand(), let’s go
ahead and create a command that makes use of the rand()
function. This is a command in the same way that cps and
getppid are new commands that we’ve added to xv6. Since
we already have a file called rand.c, we will call our new
command random and implement it in a file called
random.c.
If you use grep to look for where and how getppid() and
cps() functions are created and used in commands, you’ll see
how to create the random command. Think about the
following command to find things:
grep getppid *.[chS]
Be sure you add random in the PROGS variable in the Makefile.
You want to make sure you understand what the argint() (and its friends argstr() and
argptr()) function does with the functions in the sysproc.c file.
By the way, a full implementation of the rand() functions would allow us to generate
repeatable sequence of random numbers, per application. This one may not do that, but that is
okay for this project.
Part 6 – Modify the scheduler function (175 pts)
Now you going to make some real changes to the scheduler function. You are going to
implement lottery scheduling. This would be an excellent time to review/read chapter 9 from
the OSTEP book. This is another terrific time to use #ifdef blocks in your code to make it easy
to go back and forth between a previous working version and a new version. I used
LOTTERY_SCHED as the #define in my code.
In the proc.h file, you are going to define 3 macros: DEFAULT_NICE_VALUE,
MAX_NICE_VALUE, and MIN_NICE_VALUE. The values to use for these macros are: 20, 40,
and 1. In the struct proc data structure, you need to add an additional member, called
Don’t forget the S.
CS 444 Lab 4
Fall 2019 Page 5 of 7 R. Jesse Chaney
nice_value. The values we are going to use for the lottery scheduling will vary from 1 to 40,
with 20 as the default “nice” value. A higher value means that the process has a higher
probability to be scheduled. A lower nice value means the process has a lower probability to be
scheduled.
Typically, when a process is allocated from them shell, it is assigned the default nice value (20
aka DEFAULT_NICE_VALUE). However, when a child process is created via fork(), the
child process inherits the nice value from its parent process.
Implementing lottery scheduling is pretty easy. In the scheduler()
function, sum the nice values for all the RUNNABLE processes. Generate
a random number (using your brand spanking new random number
generator) between 1 and the sum of nice values (put your mod hat on,
there’s a high % you’ll need it). Loop through the process table for all
RUNNABLE processes, summing the nice values (this is different from the
initial sum of nice values before). As soon as the sum of nice values
exceeds the random number, schedule that process. Easy peasy.
I will warn you about a condition that slowed me down. There will be
times when there are not any RUNNABLE processes (i.e. the sum of nice values for all
RUNNABLE processes is zero). When this is true, just keep looping in the scheduler.
Part 7 – Write a new system function called renice() (50 pts)
Just as your created system functions for getppid(), cps() and rand(), you need to
create a system function called renice(). The renice() system function takes 2
arguments, a pid and a new nice value. The process with the given pid has its
nice_value changed to the given new value. Make sure the new nice value is between
MAX_NICE_VALUE, and MIN_NICE_VALUE.
If the nice value is out of bounds, renice() returns a 1 and leaves the nice value of the
process unchanged. If the pid given to renice() does not exist, return a 2. If renice()
succeeds, return a 0.
Part 8 – Write programs called renice and nice (50 pts)
The new program nice takes 2 command line options: the nice value as arrgv[1]] and
the name of the program to exec as argv[2]. It should first set its own nice value (using
renice()) and then exec the program on the command line, in argv[2]. See the image
below.
The program renice takes a new nice value as argv[1] and applies that to all the pids
following on the command line. See the image below.
The other place to look for information about nice and renice are the man pages. Your
implementation of nice and renice should behave a lot like Unix/Linux commands of the
same name.
CS 444 Lab 4
Fall 2019 Page 6 of 7 R. Jesse Chaney
Part 9 – Modify ps to show the nice values (25 pts)
Now that you have nice values for all your programs and can change them, you need to add
the ability to ps to view the nice values.
The following image shows you what this should look like.
When you have processes with large differences in nice values, you should notice that the
processes with large nice values get scheduled more frequently and accumulate more
time/ticks on the CPU. If you don’t notice this, something is wrong with your implementation.
Submit to TEACH
When you are done with the Lab4, submit your code to TEACH. Remember how we used the
command “make teach” to produce a tar and gzipped file that you can submit into
TEACH? Do that and be done.
CS 444 Lab 4
Fall 2019 Page 7 of 7 R. Jesse Chaney
Final note
The labs in this course are intended to give you basic skills. In later labs, we will assume that
you have mastered the skills introduced in earlier labs. If you don’t understand, ask questions.

CS 444 Lab 5 Kernel Threads in xv6

Part 0 – Clone the xv6-kthreads directory
I have created a directory from which you can easily begin your coding journey. The directory is
called xv6-kthreads. It is in the same location where I keep the rest of my xv6 code. You
can clone a copy of that directory using the following command:
~chaneyr/Classes/cs444/xv6/xv6-clone.bash -s xv6-kthreads -d xv6-kthreads
That will create for you a directory called xv6-kthreads which contains all the beginning
code for your kernel threads xv6 adventure. Starting with this directory is not a requirement,
but it already includes a lot of code to help you get started.
I have marked many/most of the places in the code where you’ll need to make some changes
or add code. They are marked with KTHREADS in #ifdef/#endif blocks. Currently within
those blocks are #error preprocessor directives. If you enable the KTHREADS in the
Makefile, those will cause the compiler to emit the error message and stop. You’ll need to
remove the #error directives as you develop the code. The beginning code will compile and
run. The beginning code includes most of the things we’ve added during class, such as the
shutdown command and the kdebug command.
CS 444 Lab 5
Fall 2019 Page 2 of 13 R. Jesse Chaney
Part 1 – Add some additional programs – (5 points)
You need to add a couple new user commands/programs into you xv6-kthreads directory
for some testing. If you are starting with a clone of my xv6-kthreads directory, this entire
part is already done for you. If not, copy the following programs from my xv6-kthreads
directory:
memalgn.c – this is just a small program you can run to make sure that the steps
taken to assure a block of memory is page aligned is correct.
thtst1.c – the simplest of simple thread tests. It creates a thread, makes sure that
memory between the new thread and the main thread is shared, joins with the
thread, and exits. This program uses assert statements to validate values in variables
for correctness. See Figure 3, page 13 and Figure 4, page 13.
thtst2.c – another small simple test of the thread functions, but this one can run
with multiple threads, as given from the command line. I’ve run it with 10 threads. I
don’t know how much higher it can go under the current limits of xv6. It will simply
compute away for a few seconds (usually 30 seconds with 10 threads and 13 seconds
with 3 threads, when run in qemu emulating 4 CPUs). See Figure 9, page 13.
thtst3.c – this is a much smaller version of the multi-threaded matrix
multiplication that we did in class. Simplifications include: this is a fixed work
allocation (we don’t have locks we can use between threads, yet), it generates the
same data instead of reading files, it only works on matrices of up to 30×30 (which is
the default), it is limited to at most 10 threads, and the output always goes into the
same named file (op.txt). If you really want to try a larger matrix or more threads,
go ahead, but the process memory limit of xv6 (as we have it configured) will limit
you. Interestingly, most of the run time for this program is spent writing the output
file. See Figure 8.
thtst4.c – this program tests 2 things. 1) is the parent for a thread correctly
established. 2) can a thread join with a thread it did not create. There is nothing
complex about this code, it simply creates a few threads, runs for a bit, and joins with
them. See Figure 7.
thtst5.c – this program tests 1 thing. 1) you should receive a graceful error if you
try to join with a non-existent thread. See Figure 6.
thtst6.c – this program tests 1 thing. 1) if you pass a non-page aligned pointer to
memory to kthread_create(), it should gracefully reject the new thread
creation. See Figure 5.
Table 1: Some simple testing programs.
Now modify your Makefile so that the new programs are compiled and built into the file
system when xv6 starts. As mentioned above, if you cloned my xv6-kthreads directory,
this is already done. Add the new programs into the UPROGS variable in the Makefile.
CS 444 Lab 5
Fall 2019 Page 3 of 13 R. Jesse Chaney
Though these are the current set of test/interesting programs for this project. It is very possible
that additional test programs are developed. I will make them available in the xv6-kthreads
directory.
Part 2 – Add some data members to the proc structure – (5 points)
You need to add some data members to the struct proc data structure that is in the file
proc.h. The data members you add are:
oncpu – we will use this to show on CPUs a thread/process is currently running. Later
in the assignment, we will switch from having a single CPU for qemu to having
multiple CPUs. The qemu software will allow up to 8 CPUs, but I’ve always just used 4.
Switching from a single CPU to multiple CPUs is just a small change to the Makefile.
isThread – this is use to indicate that a thingie1 taking up a slot in the ptable
structure is a thread of another process, not a process itself. Since we want the
threads scheduling to be handled by the kernel, we are going to make them entries in
the ptable, just as regular processes are. When determining how an entry in the
ptable should be handled (by something like the wait() call), this will be very
helpful.
isParent – indicates that this process has (or had) threads within it. Like the
isThread data member, this is useful when managing processes.
tid – if this thingie is a kernel thread (which is what you are building), this this hold
the unique (to the process) identifier for the thread. The tid will be unique for a
process, but may not be unique for across all processes (just like PThreads).
nextTid – the main thread keeps track of what is the next unique tid to give to a
newly created thread. This value should start at 1 and be incremented each time a
new thread for that main thread is created. The first thread created for a process will
have a tid of 1.
threadExitValue – if this thingie is a thread, this is will hold the exit value from
that thread (set in kthread_exit/benny_thread_exit). Though I had
marvelous plans for this, I never took advantage of it.
Table 2: New data members for proc structure.
Be sure to initialize all these data mambers in the allocproc() function.
If you cloned my xv6-kthreads directory, the date members are already in the structure.
1 Thingie is considered by a few to be a non-technical term. In this case, it is either a process or a kernel thread.
CS 444 Lab 5
Fall 2019 Page 4 of 13 R. Jesse Chaney
Part 3 – Copy the benny_thread code – (5 points)
Copy the benny_thread.h and benny_thread.c files from my xv6-kthreads
directory into your development directory. Modify the Makefile to build the
benny_thread.o file from the benny_thread.c file. Modify the
Makefile so that user programs/commands are linked with the
benny_thread.o object module.
The modification of the Makefile to build the benny_thread.c
module only requires you add benny_thread.o into the ULIB macro.
Doing this will also cause the user programs/commands to link with the
benny_thread.o file. Not all of them actually need it, but they are fine
with it.
Guess what? If you cloned my xv6-kthreads directory, this is already done. Otherwise, copy
it from my xv6-kthreads directory.
What are the benny_thread functions? An excellent question. The benny_thread
functions are just a few user level functions that make managing the kernel threads a bit
easier. The benny_thread functions are all user space functions. All, except
benny_thread_tid(), make kernel space calls to similarly named functions that run in
privileged mode. The benny_thread functions are just wrappers that help with the kernel
threads; in the same way that malloc() is a user level function that makes memory
management easier than having to make a bunch of calls to sbrk() to handle the heap.
benny_thread_create Return type: int
Parameters:
vbt: the address of a benny_thread_t data type
(typedef-ed in benny_thread.h).
func: A function pointer. The function is a void
return and accepts a single parameter, a void *. This
should make you think of the start_routine
parameter to the function pthread_create.
arg_ptr: a void * pointer that represents a pointer
sized value for the single parameter that is passed to
the function func (from above). This should make you
think of arg parameter to the function
pthread_create.
This function is where the memory allocated from the
heap that was used as the stack for the thread is
allocated.
benny_thread_join Return type: int
CS 444 Lab 5
Fall 2019 Page 5 of 13 R. Jesse Chaney
Parameters:
tid: a benny_thread_t pointer. The tid is passed
on to the kthread_exit function.
This function is where the memory allocated from the
heap that was used as the stack for the thread is
deallocated.
Any thread can join with another thread, except that no
thread can join with the main thread (thread 0 for a
process). It is important to note that this is a blocking
function.
benny_thread_exit Return type: int
Parameters:
tid: a benny_thread_t pointer. The tid is passed
on to the kthread_exit function.
This is called by a thread when is it complete and ready
to terminate. It is to die for.
benny_thread_tid Return type: int
Parameters:
tid: a benny_thread_t pointer that the
benny_thread_tid function will cast back to the
benny_thread_s structure and return the tid of
the given thread. The benny_thread_t is
considered opaque to functions outside of the
benny_thread.c module.
This is when a benny_thread wants to know “Who is
that?” of another thread.
Table 3: The benny_thread functions.
Any code that wants to use the benny_thread functions must include the
benny_thread.h file (as thtst[123].c do). While it is possible to directly call the
kthread_ functions from user mode (as the benny_thread functions do), it is simpler to
use the wrappers. Simplicity is a benny-fit of the functions.
Part 4 – Stub out the kthread_ functions – (5 points)
In the proc.c file, stub out the following kthread_ functions:
kthread_create Return type: int
Parameters:
CS 444 Lab 5
Fall 2019 Page 6 of 13 R. Jesse Chaney
func: A function pointer. The function is a void return and
accepts a single parameter, a void *. This should make you
think of the start_routine parameter to the function
pthread_create.
arg_ptr: a void * pointer that represents a pointer sized
value for the single parameter that is passed to the function
func (from above). This should make you think of arg
parameter to the function pthread_create.
tstack: a void * pointer to the space that this newly
created thread will use as its stack. The tstack pointer must
point to a page aligned lump of memory.
This is where an actually kernel thread is created. It gets spot
in the ptable, has a kernel stack allocated, has its state set to
RUNNABLE, and so much more…
kthread_join Return type: int
Parameters:
tid: an integer that represents the thread identifier (aka tid)
for the thread within this process for which the calling thread
will join.
This is where most of the cleanup for a thread is done. It is
important to note that this is a blocking function. If the passed
thread is not yet complete (called kthread_exit), this
function will not return until the thread has terminated.
kthread_exit Return type: void
Parameters:
exitValue: an integer that represents the exit status of the
thread. A value of 0 is successful termination of the thread.
Any value other than zero indicated a nonsuccessful termination of the thread.
This is where a thread declares is it done and
terminates. However, even though it is done, it
must remain in the ptable (as a ZOMBIE) until
another thread joins with it. The brains of the
thread are removed and it turns in a zombie.
Table 4: The kthread functions
If you are starting with a clone of my xv6-kthreads directory, these functions are already
stubbed out in proc.c.
CS 444 Lab 5
Fall 2019 Page 7 of 13 R. Jesse Chaney
You have soooo much already done and it has been so easy. Sorry partner, but the easy part is
about to change. It is time to release your inner wild kernel hacker.
Part 5 – Implement kthread_ Functions – (300 points)
This is where it starts to be challenging and just downright fun. While the following instructions
are extensive, they are not intended to represent everything necessary in the kthread_
functions.
kthread_create()
This is going to be a lot like the fork() function. In fact, starting with a copy of
fork() is not a bad idea at all. I’m going to assume you did this and use the variable
names from the fork() function below.
The first thing the kthread_create function must do is to check to make sure the
tstack pointer is page aligned. Remember the memalgn program (mentioned in Table
1), look at the source code for it. If it is not page aligned, return -1.
Next, call allocproc().
The next thing fork() does is make a copy of the page table (the call to copyuvm).
But, that is for a process (where each process has its own page table). This is a thread,
so all you need to do is have the pgdir member of np point to the pgdir of
curproc. This is one of the most important things about a thread, all threads in a
process share a single page table.
The size of the thread (the sz member) is the same size as curproc (since they are the
same process). This is actually an issue, but we address in a future lab.
Make sure you set the isThread member for np.
There is not a parent-child relationship
between threads, but we need to keep
track of which threads are related to a
process. So, set the parent of the new
thread np to curproc, UNLESS
curproc is itself a thread. If
curproc is a thread, then the parent
of np is the parent of curproc. Use
this opportunity to also set the
isParent member in the process
(main thread) and increment the threadCount of the parent process (the once
running main()). When inspecting the parent data member in the proc structure, all
threads should point back to the main thread (as shown in Figure 1). You do not want to
have a multi-level hierarchy of relationships.
The new thread, np, has the copy of tf (trap frame) as curproc. Do this (yes the *
characters are required, that’s how it is copied):
Figure 1: Relationship between newly created threads and the main
thread (thread 0). All threads created with kthread_create(),
for a given process, have the same parent, the main thread.
CS 444 Lab 5
Fall 2019 Page 8 of 13 R. Jesse Chaney
*np->tf = *curproc->tf;
The eax register for the new thread is cleared just as it is for a new process, though
frankly it does not really apply here.
The eip register (in the tf structure) represents the instruction pointer for the new
thread. You should assign func to it. This is not touched in the fork() function.
We need to assign the esp (extended stack pointer) data member (from the tf
structure in np) to the tstack that was passed as a parameter. However, the tstack
variable is the opposite end of the stack (as the stack grows low address to high
address). So, try something like this:
np->tf->esp = ((int) tstack) + PGSIZE;
We are going with the assumption that the size of the stack for each thread is a single
page (PGSIZE). It would be nice to be able to create threads with different stack size,
but that is beyond this assignment.
We need to push a value on the stack. Specifically, we need to push the arg_ptr
variable value onto the stack for the thread function to pick up. This will take 2
statements. See if these make sense.
np->tf->esp -= sizeof(int);
*((int *) (np->tf->esp)) = (int) arg_ptr;
The first line decrements the value for the beginning of the stack pointer. The thread
function will pull the value from the esp register beginning at this location. The second
line copies the value from within the arg_ptr variable on the stack. We have to do
some magic C casts to make sure everything is happy.
We have 2 more manipulations of the stack pointer. We need to push the value of the
new thread’s tid onto the thread stack. This is the return value from
kthread_create that the thread function can pick up. Assign the new tid value to
a local variable (called maybe something wild, like tid). Assign the same value to the
tid data member for np. The new tid should come from the parent tid data
member (np->parent). Make sure you increment the parent’s nextTid value as
well (as a post increment). Now
np->tf->esp -= sizeof(int);
*((int *) (np->tf->esp)) = tid;
You are getting to be a real pro at this. We are almost there for kthread_create.
In fork() there is a little loop where the file descriptors from curproc are
duplicated (using filedup()) into np. You need to do this for the thread.
You need to idup() the curproc->pwd into np->pwd. As fork() does. This is
immediately after the loop above.
As fork() does, do the safestrcpy(), acquire the ptable lock, set the state of
the thread to RUNNABLE, and release the lock.
CS 444 Lab 5
Fall 2019 Page 9 of 13 R. Jesse Chaney
Return the tid.
I liberally sprinkled a number of if statements that use the debugState variable in the
function. Some simply check to see if debugState is non-zero while others check to
see if debugState is greater than 1 or 2. This allows me to change the number of
diagnostic messages from the kernel at runtime. I found use of the kdebug command
very useful.
Whew… done with kthread_create().
kthread_join()
The kthread_join() function is a bit easier
than kthread_create(), but it has a few
subtle requirements. The kthread_join() has a lot in common with the wait()
function. In fact, you will need to make a change to the wait() function as part of
developing the kthread_join() function. Anything you do in the
kthread_join() function that makes a change to the ptable process array will
require a lock on that structure. Make sure that you also unlock it before returning.
There is a lot more room for creativity in development of this function. I’m going to walk
through how I did it, but there are a lot of opportunities for variation.
If the curproc is a parent (of threads), but has a current thread count of 0, just release
and return -1.
If the given tid is 0, just release and return -1. As I have designed my code, a thread
cannot join with thread 0 (the main thread). This is not a requirement, just how I did my
code. In the future, I’d like to change this.
This is a bit tricky here, I want to make sure that I decrement the correct
threadCount data member, so I check to see if curproc->isThread is TRUE. If
so, I set curproc = curproc->parent. Remember back in the
kthread_create() function, this statement “There is not a parent-child
relationship”? We made sure that all threads parent pointer went back to the main
thread (thread 0, see Figure 1). This is where that becomes important. The thtst4
program will test this.
Acquire a lock on the ptable.
If you look at the code for wait(), you’ll see that it has an infinite for loop around a
loop through the ptable at this point. I’m going to take a slightly different approach
on this (let me know if you find a flaw in it).
Look through the ptable with a for loop (I do it in the same way as wait() does,
where p is the current entry in the table). If p->parent != curproc || p->tid
!= tid, just continue in the loop.
If we get through the test p->parent != curproc || p->tid != tid, we
know we’ve found the right parent and tid combination. I go into the following loop:
CS 444 Lab 5
Fall 2019 Page 10 of 13 R. Jesse Chaney
while (p->state != ZOMBIE) {
release(&ptable.lock);
yield();
acquire(&ptable.lock)
}
Basically, if the thread is not marked as a zombie, release the ptable lock, and yield
the processor. Remember when we talked about yielding the time slice for a process?
Once the thread is scheduled again, acquire the ptable lock and repeat the test. The
thread will be marked as a zombie in the kthread_exit() routine.
Once we get through the above loop, we know we have the right thread and that the
thread has exited. We need to clean it up.
Decrement the threadCount of curproc (which is the main thread).
Do the stuff done in wait(), but DO NOT call freevm(). This is the stuff
in the if block where p->state == ZOMBIE. The main thread owns the
virtual memory for the entire process. Only when the main thread exits is the
virtual memory freed.
Break out of the loop.
If you found the right parent and tid combination, return 0. Otherwise, return -1.
Make sure you release the ptable lock before the return.
Okay, let’s go make that change to the wait() function.
Remember that the kernel is periodically looking for zombie processes. As we write
these as kernel threads, they look a lot like processes to the kernel. We do not want the
kernel doing cleanup on the threads until we are ready for it.
So, there is an if block in the wait() function that looks like this:
if (p->parent != curproc)
continue;
We must change it condition to look like this:
if(p->parent != curproc || p->isThread == TRUE)
If the thingie the kernel (or other process) is inspecting is a thread, just move along. It
does not make sense to call wait() on a thread, you must join with it.
2 functions down (kthread_create() and kthread_join()); 1 more to go.
kthread_exit()
The code for kthread_exit() is pretty straight forward.
Get the curproc (as exit() does). If curproc data member
isThread is TRUE, then:
Close all the open files (see exit()).
CS 444 Lab 5
Fall 2019 Page 11 of 13 R. Jesse Chaney
Cleanup the cwd (exacly as exit() does it with begin_op and end_op). In previous
development, I have experienced some issues when cleaning up the
cwd, but have not with this development.
Set killed to FALSE, the thread data member threadExitvalue to the
passed exitValue, oncpu to -1, and state to ZOMBIE.
Now, acquire the ptable lock and call sched() (not scheduler()). Follow the call
to sched() with a panic(“kthread_exit”) call.
Obviously, it should never get to the call to panic.
That’s it for kthread_exit().
Time to give a big woohoo!
Part 6 – Refresh the ps/cps() code – (50 points)
We’ve added a couple data members to the proc structure
(Remember Part 2? Seems like ages ago.). We want those to show up when we run the ps
command.
You need to add the
following to the output
from the cps() function:
oncpu, isParent,
isThread, and
threadCount. The
header information should
be: “cpu”, “is par”, “is
thrd”, and “thrd #”.
You only show the oncpu
value when it is >= 0. If
you’ve followed the
instructions from above,
this should be easy. Only a
RUNNING process/thread
should have a value of
oncpu that is greater than
or equal to 0. Do not show
the negative value for
oncpu.
For isParent (which means it is a main thread) and isThread, just show 0 for false and 1
for true.
The threadCount value should be zero except for a main thread in a process.
See Figure 2 for how this should look.
Figure 2: The ps command with new columns.
CS 444 Lab 5
Fall 2019 Page 12 of 13 R. Jesse Chaney
The easy way to see this data is to run “thtst2 6 &” (in the background) and then run ps a
couple of time to see the output. If you see a “zombie!” after doing this, don’t worry, it is
only a flaw in their shell.
Part 7 – Update and Validate on 4 CPUs – (100 points)
Change the CPUS macro in the Makefile to 4. It is fine for you to do your development with
a single cpu in qemu. However, you code will be tested with the value of the CPUS macro in
the Makefile set to 4. I highly recommend you test your code this way. In the Makefile,
look around line 251. The points for this part are not awarded to simply changing the
Makefile, but for all the test commands working correctly with 4 CPUs.
How It will be Graded
When we grade, we will first run the 6 test commands with a single CPU. We will run 1 test
program, then exit qemu before running the next test program. I know this stuff is hard and we
really don’t have the 6 months to develop a full test suite, that’s why we will exit qemu
between tests.
We can run qemu using a single CPU with the following command:
make nox CPUS=1
We can run qemu using 4 CPUs with the following command:
make nox CPUS=4
The macro on the command line will override the setting within the Makefile.
Other Tips
I have to be honest, there are a couple places where I struggled
when writing this code. One of the biggest is where I called
kfree() in the kthread_join() function (you can put it in
kthread_exit()). If you look in the code for kfree(), you’ll
see that it does a memset() on the page of kernel memory to be
freed. Doing the memset() is an excellent idea, for the reason
mentioned in the comment. However, somewhere I must have some
boundary conditions messed up. When I run thtst2 and do the memset(), I will usually get
“unexpected trap 14 from …”. If #ifdef out (or comment out) the call to memset() in
kfree(), all is fine. Many web searches later, it would seem that I have overrun a buffer and
stomped all over an instruction pointer. But, I cannot see where I’ve gone astray. I would really
like to know what I am doing wrong. L If you find out what my error is, have pity on me and let
me know.
Submit to TEACH
When you are done with the Lab5, submit your code to TEACH. Remember how we used the
command “make teach” to produce a tar and gzipped file that you can submit into
TEACH? Do that and be done.
CS 444 Lab 5
Fall 2019 Page 13 of 13 R. Jesse Chaney
Final note
The labs in this course are intended to give you basic skills. In later labs, we will assume that
you have mastered the skills introduced in earlier labs. If you don’t understand, ask questions.
Example Output from Test Programs
Figure 8: Successful run of thtst1. Figure 9: Failed run of thtst1
Figure 5: Successful run of thtst2.
Figure 7: Sample test run of thtst3
Figure 6: Sample output from thtst4
Figure 4: Sample output from thtst5
Figure 3: Sample output from thtst6