CPSC 457 - Principles of Operating Systems - Assignment 2

This assignment comes in two parts. Part A is a programming assignment to familiarize you with the methods for modifying Linux and adding new features to it. It should be completed on your virtual machines.

Part B includes questions to be answered which will encourage you to think about some of the work you did in Part A and some of the topics we have discussed in lecture.

This assignment will be marked out of 100 and will count for 20% of your total grade in the course. 60 marks will be dedicated to Part A and 40 marks will be dedicated to Part B (four marks for each question).

You will hand in your assignment by sharing your git repository with your TA through the CPSC gitlab and Tagging the branch which includes all of your files for Part A and Part B, "CPSC457-Assignment2-Complete".

This assignment is due at 2:00pm on Friday June 10.

This assignment was updated to fix some errors and add some clarifications. If you would like to see the original, look here.


Part A - Coding

Your CEO has trouble remembering program names and process ID numbers. He recently left a large search engine company whose motto was "Don't sort -- search!" and encouraged tagging of everything. One day, he asks you to modify the Linux kernel to augment job control by tagging processes with an arbitrary list of keywords. Since he once took an OS course, he dimly remembers a discussion of extended attributes from the filesystem lecture. He asks you to "implement extended attributes for processes" (rather than files). He gives you a few weeks to develop a working prototype.

Your CTO takes pity on you, and gives you a few hints. She says:

You do as your CTO recommends. The CEO is impressed, but complains that he cannot see the status of all the tagged processes. He leaves in a hurry to go golfing. Your CTO says:

Your CEO is delighted, but laments the fact that he cannot do anything useful with these groups of processes, like kill all processes associated with the tag 'green'. After he goes to lunch, your CTO looks at you and says: "You're on your own."

Functional Requirements

Your assignment must:

Non-Functional Requirements

Your assignment must:


Thanks to Mike Clark for the hints.

Part B

Part B includes five questions, which should be answered in one or two paragraphs and included in a text file along with your code, makefile and README when you hand in your assignment. Most questions have several parts, make sure you answer them all.

Question 1 - Why did we do this?

The CEO is fired, the company folds, and you go interview at the bank your former CTO now works for. She asks you one question in the interview: Do you think it would be better to implement process tagging completely in userspace (for example, with a file called /etc/tags) or in the kernel like you did? Why? Do you get the job at the bank?

Question 2 - Kernel routines vs User routines

What are the differences between printf and printk? What are the differences between malloc and kmalloc? Why do we need different libraries to support kernel operations compared to user operations?

Question 3 - Root vs kernel

Both the concepts of the root user (or an administrator account) and the kernel are similar and related, but they are not the same. How they are different and describe how they are similar?

Question 4 - LKMs and system calls

In some operating systems, such as Solaris, it's possible to add new system calls through loadable kernel modules. In others, such as Linux, it isn't possible. Why? What reasons are there for allowing LKMs to add system calls and what reasons are there for restricting this? Which approach do you favour?

Question 5 - Thread Implementation

Threads can be implemented in user space or kernel space. Each way has benefits and draw backs. List some of the benefits and drawbacks of each. Discuss one situation where user space threads are a better choice and one situation where kernel space threadsa are a better choice.

Question 6 - Thread Yielding

Why would a thread every voluntarily give up the CPU by calling thread_yield? Discuss the assumptions that allow us to think of threads as cooperative, but processes as antagonistic. (From Modern Operating Systems, Chapter 2)

Question 7 - Scheduling

Five batch jobs (A, B, C, D, E) arrive to be scheduled at almost the same time. They have estimated burst times of 10, 6, 2, 4 and 8 ms respectively. Their (externally determined) priorities are 2, 0, 3, 4 and 1, with 0 being the highest priority. For each of the following algorithms calculate the the turnaround time for each job.

  1. Round robin - with a quantum of 2ms
  2. Priority scheduling
  3. First-come, first served (assume they arrived in alphabetical order)
  4. Shortest Job First (assume you have perfect knowledge of the burst times)

Assume for 1. that the system is multiprogrammed and that each job gets its fare share of CPU. For 2. through 4. assume that once a job is started it will not be preempted until it finishes. Assume all jobs are completely CPU bound. (Modified from Modern Operating Systems, Chapter 2)

Question 8 - Context Switching and Round Robin Quanta

Explain how time quantum value and context switching time affect each other in a round robin scheduling algorithm. (From Modern Operating Systems, Chapter 2)

Question 9 - fork()

Consider the following piece of C code:

void main(int argc, char *argv[]) { fork(); fork(); exit(); }

How many processes are created? Justify your answer and draw a tree describing the process family (ascii trees are good). (From Modern Operating Systems, Chapter 2)

Question 10 - exec

The exec() family of functions wrap the function execve, which executes a program. What purposes do the wrapper functions serve? What information about a process does execve preserve and what information does it not preserve? Why does execve not have a return condition?


This document is released under a Creative Commons Attribution, ShareAlike licence, excluding Questions 6 - 9 which are copyright Andrew Tanenbaum. This assingment is developed, based on an original developed by Michael Locasto.

Page Updated: June 5, 2016 at 1830 MDT