CS 354 Spring 2021

Lab 1: Getting Acquainted with XINU's Software and Hardware Environment (240 pts)

Due: 02/10/2021 (Wed.), 11:59 PM

1. Objectives

The objectives of the first lab assignment are to familiarize you with the steps involved in compiling and running XINU in our lab, and practice basic ABI programming that will be used as a building block in subsequent lab assignments.

2. Readings

  1. XINU set-up
  2. Chapters 1 and 2 from the XINU textbook.

For the written components of the problems below, please write your answers in a file, lab1ans.pdf, and put it under lab1/. You may use any number of word processing software as long as they are able to export content as pdf files using standard fonts. Written answers in any other format will not be accepted.

3. Inspecting XINU source, compiling, and run-time environment (240 pts)

Follow the instructions in the XINU set-up which compiles the XINU source code on a frontend machine (Linux PC) in the XINU Lab, grabs an unused x86 Galileo backend machine, loads and bootstraps the compiled XINU image. Note that the frontend PC's terminal acts as a (remote) console of the dedicated backend Galileo x86 machine. If XINU bootstraps successfully, it will print a greeting message and start a simple shell called xsh. The help command will list the set of commands supported by xsh. Run some commands on the shell and follow the disconnect procedure so that the backend is released. Do not hold onto a backend: it is a shared resource.

Problem 3.1 (30 pts)

Basic initialization and pathway to app creation in XINU.

(a) XINU initialization and idle process. Inside the system/ subdirectory, you will find the bulk of relevant XINU source code. The file start.S contains assembly code that is executed after XINU loads on a backend. After performing bootstrap/initialization chores (the details are not relevant at this time), a call to function nulluser() in initialize.c is made. At some point, nulluser() calls sysinit() (also in initialize.c) where updates to the data structure proctab[] are made which represents XINU's process table. In XINU, as well as in Linux/UNIX and Windows, a process table is one of the key data structures of an operating system where bookkeeping of all created processes is done. In our Galileo x86 backend which has a single CPU (or core), only one process can occupy the CPU at a time. In a x86 machine with 4 CPUs (i.e., quad-core) up to 4 processes may be running concurrently. Most of XINU's kernel code can be found in system/ (.c and .S files) and include/ (.h header files). At this time, we will use the terms "process" and "thread" interchangeably. Their technical difference will be considered when discussing process management.

When a backend machine bootstraps and performs initialization, there is as yet no notion of a "process." That is, the hardware just executes a sequence of machine instructions compiled by gcc on a frontend Linux PC for our target backend x86 CPU (i.e., the binary xinu.xbin). This includes machine code translated from initialize.c. nulluser() in initialize.c calls sysinit() which sets up the process table data structure proctab[] which keeps track of relevant information about created processes that have not terminated. When a process terminates, its entry is removed from proctab[]. After configuring proctab[] to hold up to NPROC processes (a system constant defined in config/), sysinit() creates the first process, called the idle process. This idle or NULL process exists not only in XINU but also in Linux/UNIX and Windows. It is the ancestor of all other processes in the system in the sense that all other processes are created by this special NULL process and its descendents through system call create(). The NULL process is the only process that is not created by system call create() but instead "handcrafted" during system initialization. Determine in which kernel function (a C function) the NULL process is initialized, then the values of its priority, process state, and process ID (PID). PID is an integer that is used internally by operating systems to identify processes. Whether XINU, Linux or Windows, a process cannot request that a specific PID be assigned to a child process.

(b) Role of XINU's main and removing xsh. After nulluser() handcrafts the first process, it spawns a child process using system call create() which runs the C code startup(). Upon inspecting startup(), you will find that all it does is create a child process to run function main() in main.c. For our purpose, we can skip the intermediate step and directly create the process running main() from nulluser(). Make this modification to nulluser() and verify that XINU works as before.

We will use the child process that executes main() in main.c as the test app for gauging the impact of kernel modifications on application behavior. In the code of main() in main.c, a "Hello World" message is printed after which a child process running another app -- a shell xsh -- is spawned which outputs a prompt "xsh $ " and waits for user command. We will not be using xsh since it is but another app and not relevant for understanding operating systems. Remove the "Hello World" message from main() and put it in a separate function, void helloworld(void), in system/helloworld.c. Call helloworld() from nulluser() before it creates a child process running main(). Customize the "Hello World" message so that it contains your name and username. Modify main() so that it is completely empty but for a message that says "I am a process running main()." The modifications of (b) will carry over to lab2, ..., lab5. We will use main() to create test processes to evaluate app behavior after modifications to the XINU kernel have been made.

For new functions that are added to XINU, insert its function definition in include/prototypes.h. The header file prototypes.h is included in the aggregate header file xinu.h. Every time you make a change to XINU, be it operating system code or app code, you need to recompile XINU on a frontend Linux machine and load a backend with the new XINU binary.

Problem 3.2 (30 pts)

We will create our first system call, a variant of create(), that allows a process to specify the PID of the child process. The function prototype of the new system call, ncreate(), is the same as create()

pid32 ncreate(void *funcaddr, pid32 reqpid, uint32 ssize, pri16 priority, char *name, uint32 nargs, ...);
except that it has an additional argument where the second argument, reqpid, specifies the requested PID of the child process. ncreate(), instead of finding the next available unused PID in the process table using internal kernel function newpid(), must check if reqpid is valid and available. That is, reqpid must lie within the range 0 and NPROC-1, and the entry proctab[reqpid] must be free. If either condition fails, ncreate() returns SYSERR indicating that the system call failed. XINU system calls follow the format where interrupts are disabled upon entering a system call and re-enabled before returning from the system call. Hence, before returning SYSERR interrupts must be re-enabled by calling restore(mask) where mask is an interrupt mask. The benefit of using a mask instead of directly reenabling interrupts will be discussed later. Until then, note that disable() disables all interrupts including the clock interrupt, and restore() re-enables them. To perform the argument checks in ncreate(), look up the struct definition of process table data structure proctab[] in include/process.h and the parts of create() relevant to assigning an unused PID. create() is a complex system call, and its other parts will be covered in later labs.

Place ncreate() in system/ncreate.c and perform tests to evaluate correctness. For example, from the process running main() you may use create() to spawn a child process and remember its PID returned by create(). Then spawn a second child from main() using ncreate() where the PID of the first child is given as the second argument of ncreate(). This should cause ncreate() to fail since the first child, not having been unsuspended by calling resume(), still exists. On the other hand, calling ncreate() with second argument of an unused PID, say 30, should succeed. One critical feature of system calls is that sanity checks surrounding validity of arguments must be exhaustive. Otherwise a process making a system call with invalid arguments can unintentionally -- or intentionally (i.e., maliciously) -- comprise a computing system. The TAs will be using their own main() process to test your implementation of ncreate(). Your task is to utilize main() to test for all relevant cases which is the most important part of implementing ncreate(). Remember to include all new function definitions in include/prototypes.h.

Problem 3.3 (20 pts)

Some system parameters of XINU are configured in config/Configuration which contains meta data from which C code (conf.c and conf.h in config/) is produced using automated translation tools. These parsing and lexical analysis tools covered in a compiler course will not concern us as they are useful but not necessary for understanding and coding XINU. The IRQBASE constant 32 in config/Configuration results in its inclusion as a C preprocessor directive in config/conf.h. IRQBASE defines the component of the x86 interrupt vector to which clock interrupts are mapped to. Recall from computer architecture that the interrupt vector serves as an interface between hardware and software so that when an interrupt occurs it is routed to the responsible software component for handling it. That is, the interrupt handling code of an operating system that is tasked with responding to the interrupt. The clock interrupt in our x86 Galileo backends is configured to go off every 1 millisecond (msec), i.e., 1000 clock interrupts per second. Several years back a popular configuration was 10 msec. x86 supports 256 interrupts numbered 0, 1, ..., 255 of which the first 32, called exceptions (or faults), are reserved for dedicated purposes. Thus XINU configures clock interrupts at interrupt number 32.

When a clock interrupt is generated, it is routed through interrupt number 32 to XINU's kernel code clkdisp.S in system/ which, in turn, calls clkhandler() in system/clkhandler.c to carry out relevant tasks. Modify clkhandler() in clkhandler.c so that a message is output using kprintf() after 2000, 3000, and 4000 clock interrupts. Thus a message should be printed at approximately 2, 3, and 4 seconds after XINU starts to run on a backend. To perform this modification, make use of the fact that a global variable of XINU, clktime of type unsigned int, keeps track of the time elapsed since a backend has been bootstrapped. Use grep to find where clktime is declared. Inspecting the code of clkhandler(), you will find that it utilizes a static variable, count1000, initialized to 1000 as a countdown counter that is decremented each time a clock interrupt occurs. When count1000 reaches 0, XINU decides that 1 second has elapsed, updates clktime, and resets count1000 to 1000. Usage of kprintf() is similar to printf(), albeit with reduced support of data types in the format string. Implement the change to clkhandler() so that kprintf() is called thrice.

Problem 3.4 (20 pts)

After nulluser() handcrafts the first process and spawns a child process running the code of main(), nulluser() enters into an infinite while loop, hence does not terminate. The purpose of the idle or NULL process in XINU -- the same holds for Linux/UNIX and Windows -- is so that there is always a process to run on a CPU when no other processes require CPU cycles. It may be that all other processes are sleeping, suspended, or waiting for events such as a response from a server. When an interrupt occurs XINU temporarily ceases running the code of the process executing on Galileo's x86 CPU. With the help of x86's interrupt vector jumps to its clock interrupt handling code, then returns to the code that was interrupted to resume where it left off. We adopt the view that the interrupt handling code has been executed by the process whose own code was temporarily put on hold. We say that the interrupt handling code was executed by borrowing the context, or state, of the current process occupying the CPU. Thus except at bootloading before the first process is created, all code executed on a CPU is viewed as being carried out by a process. Even interrupt handling code that may have nothing to do with the currently running process on a CPU. To enforce this abstraction, we need an idle or NULL process that is always ready to run on the CPU in case no other processes require CPU cycles.

In mobile devices, conserving battery power is important, hence a different strategy is needed than to just execute infinite while loop in the idle process which expends energy. In server farms powered by electrical grid, a primary concern is cooling to dissipate heat generated by machines in confined spaces. A CPU that executes instructions consumes battery power and generates heat. We will implement an energy consumption reduction method by putting the CPU in a halted state using the x86 hlt assembly instruction. The hlt instruction puts the CPU in a hibernating state until an external interrupt occurs. On our backends, this will likely be a clock interrupt which wakes up the CPU so that the interrupt can be serviced. To prevent XINU's NULL process from continually executing unconditional jumps (which is what an infinite while loop with an empty body does) when it occupies the CPU, we add x86's hlt instruction to the body of the while loop. Until an interrupt occurs, the NULL process puts Galileo's CPU into hibernation which reduces energy consumption and heat generation.

One way to accomplish that is to code an assembly function that executes hlt, which is called from the body of the while loop of C function nulluser(). Function calls entail caller/callee coordination which requires additional instruction execution which is what we are aiming to reduce. A more efficient method embeds the assembly instruction hlt within the C code of nulluser using in-line assembly. By adding the statement asm("hlt") to the body of nulluser()'s infinite while loop, we instruct the C compiler gcc to insert the hlt instruction when translating the C code into assembly. There is no need for a function call and resultant overhead. Modify the code of nulluser() in initialize.c to implement the energy saving update. Perform the test of Problem 3.3 with main() empty so that we are assured that only the NULL process runs on the CPU when clock interrupts at 2, 3, and 4 seconds induce clkhandler() to call kprintf().

Problem 3.5 (20 pts)

When multiple processes wanting to run on shared a CPU compete, XINU determines who gets to run based on their priority values. The same principle applies to Linux/UNIX and Windows. The component of an operating system that decides who gets to run next is called the scheduler. In XINU the larger the priority value of a process, the more important it is, and the scheduler allocates Galileo's x86 CPU to a process that has highest priority. We cannot say "the" process since two or more processes may have equal and highest priority. In the case of a tie, XINU performs round-robin scheduling which means running one process for a while, then switching to another of equal and highest priority, and so forth, until coming back to the first highest priority process. Then the procedure repeats itself. The time spent running a process before switching to another is called time slice or quantum. It is given by system constant QUANTUM which is defined in include/kernel.h. Increase its value from 2 to 20 msec. In order to assure that the NULL process only runs if there are no other processes wanting to run -- i.e., there are no other ready processes -- we must assign the NULL process the lowest priority and there can be no tie. Inspect create.c and determine if this property is satisfied by create() when a new process is created. Another system call, chprio(), allows the priority of an existing process to be changed. Check if chprio() ensures that the NULL process is guaranteed to have lowest priority. Explain your findings in lab1ans.pdf. If needed, modify create() and chprio() so that the property is satisfied.

Problem 3.6 (40 pts)

Some parts of operating system code cannot be implemented in C but require assembly language coding to make the hardware do what we want it to do. There is no other choice. We saw an example in Problem 3.4. In general, functions written in assembly may need to be called from functions coded in C, and vice versa. As in 3.4, we may embed assembly code within C code when the amount of code is small. Here we will practice coding a function in assembly so that it can be called from a function coded in C. This is mainly an exercise in checking that you understand how the CDECL caller/callee convention for our 32-bit x86 Galileo backends works. You will pick up basics of AT&T assembly coding on x86 CPUs. This is useful but secondary to understanding how to interface functions at the machine code level, called ABI (application binary interface) programming.

You are given a function addtwo() of function prototype, int addtwo(int x, int y), coded in AT&T assembly in addtwo.S under the course directory. Copy the file into your system/ directory and update include/prototypes.h. Modify main() so that it calls addtwo() with two integer arguments whose addition addtwo() returns. Use kprintf() to output the results from main() to verify that the code in addtwo.S works correctly. Using your understanding of CDECL which we reviewed in the lectures and looking up the meaning of basic AT&T assembly instructions (utilize the reference material pointed to in the course web page), explain line-by-line what the code in addtwo.S does, and why. The objective is for you to demonstrate that you understand the logic behind the code. The code itself can vary from x86 to ARM architecture and AT&T vs. Intel assembly syntax. However, the logic behind what the code needs to accomplish remains invariant. It is this understanding that is important to acquire. Of course, you will be asked to put the understanding to work by implementing working code in our specific system environment. This is an exercise to help you prepare for operating system coding in lab2 and beyond.

Problem 3.7 (40 pts)

Using the code of 3.6 as starting point, code a function, int addthree(int x, int y, int z), in assembly in system/addthree.S. As the name indicates, addthree() adds its three arguments and returns the result. Call addthree() from main() to verify that it works correctly. Annotate addthree.S with comments, and add your name, username, and date at the beginning of the file.

Problem 3.8 (40 pts)

We will do a role reversal of Problem 3.7 where instead of calling a function coded in assembly from a function coded in C, we will call a function coded in C from a function coded in assembly. You will perform the chores of the caller following CDECL when writing assembly code, keeping in mind that the callee's C code, named int threeadd(int x, int y, int z), in system/threeadd.c to distinguish from its assembly counterpart, will be translated by gcc into assembly following CDECL. For testing purposes, code an assembly function, int test38(void), in test38.S under system/ which will be called from main(). test38 in test38.S will then call C function, int threeadd(int x, int y, int z) which returns x + y + z. Hardcode the three arguments passed by test38() to threeadd() so that their values are 2, 3, and 4. Since gcc is responsible for threeadd.c and you are responsible for caller code test38.S, you will need to push the three arguments (in the right-to-left order dictated by CDECL) onto the stack, followed by the return address before jumping to threeadd(). The last two steps are performed by assembly instruction call. After threeadd() returns the result in EAX, you will need to preserve it (tantamount to returning the value to main()) so that main() can output its value by calling kprintf(). Since main() is coded in C, gcc following CDECL will expect the return value of test38() to reside in EAX. For example, if main() contains statement d = test38() where d is a local variable of main() of type int, then gcc will make sure to copy the content of EAX into d. Note that test38() is both a caller and a callee, hence you need to consider its dual role when writing code that complies with CDECL. Code, test and verify that your implementation works correctly.

Bonus problem (20 pts)

In Problem 3.4, we used in-line assembly to implement an energy efficient version of nulluser(). As an exercise, instead of using in-line assembly write assembly function, void haltnull(void), in system/haltnull.S that is called from the body of the infinite while loop. The essential job of haltnull.S is to execute the hlt instruction which puts the CPU in hibernation. When a clock interrupt occurs, after the clock interrupt handling is completed haltnull.S will execute the instruction following htl which should return to nulluser()'s infinite while loop which then calls haltnull() again. When submitting after performing testing, turn in initialize.c where nulluser() executes asm("hlt"). The TAs will modify initialize.c to call haltnull() for students who have completed the bonus problem.

Note: The bonus problem provides an opportunity to earn extra credits that count toward the lab component of the course. It is purely optional.

Turn-in instructions

General instructions:

When implementing code in the labs, please maintain separate versions/copies of code so that mistakes such as unintentional overwriting or deletion of code is prevented. This is in addition to the efficiency that such organization provides. You may use any number of version control systems such as GIT and RCS. Please make sure that your code is protected from public access. For example, when using GIT, use git that manages code locally instead of its on-line counterpart github. If you prefer not to use version control tools, you may just use manual copy to keep track of different versions required for development and testing. More vigilance and discipline may be required when doing so.

The TAs, when evaluating your code, will use their own test code (principally main()) to drive your XINU code. The code you put inside main() is for your own testing and will, in general, not be considered during evaluation.

If you are unsure what you need to submit in what format, consult the TA notes link. If it doesn't answer your question, ask during PSOs and office hours which are scheduled M-F.

Specific instructions:

1. Format for submitting written lab answers and kprintf() added for testing and debugging purposes in kernel code:

2. Before submitting your work, make sure to double-check the TA Notes to ensure that any additional requirements and instructions have been followed.

3. Electronic turn-in instructions:

        i) Go to the xinu-spring2021/compile directory and run "make clean".

        ii) Go to the directory where lab1 (containing xinu-spring2021/ and lab1ans.pdf) is a subdirectory.

                For example, if /homes/alice/cs354/lab1/xinu-spring2021 is your directory structure, go to /homes/alice/cs354

        iii) Type the following command

                turnin -c cs354 -p lab1 lab1

You can check/list the submitted files using

turnin -c cs354 -p lab1 -v

Please make sure to disable all debugging output before submitting your code.

Back to the CS 354 web page