For the written components of the problems below, please write your answers in a file, lab1answers.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.
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.
(a) 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/ and include/ (header files). At this time, we will use the terms "process" and "thread" interchangeably. Their technical difference will be considered when discussing process management.
Some configuration related parameters of XINU can be found in config/. The total number of processes supported in XINU is defined by the constant NPROC. Do some detective work to locate where NPROC is defined. Using the command grep to search for a string in files is a common method. Based on what you find, determine how many processes can exist in XINU. Increase this number by twice and make it the new parameter value for your XINU version this semester. Most kernel configuration parameters are defined in header files in subdirectory include/. Look for header files where NPROC is conditionally defined (i.e., C preprocessor statement) and change the value to match the updated value defined under config/. Recompile XINU on a frontend machine, download and test on a backend machine to verify that it continues to run xsh after initialization. Note that running xsh without overt problems does not imply that there aren't other hidden issues stemming from redefining NPROC. It is but one test.
(b) 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. Function 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, sysinit() creates the first process, called the NULL (or idle) process. This NULL process which exists not only in XINU but also in Linux/UNIX and Windows is the ancestor of all other processes in the system. It is the only process that is not created by the system call create() but is "handcrafted" during system initialization. Determine the process ID (PID) of this very first process and explain how you did so.
One of the properties of a process is its priority. In XINU, the larger the priority value (an integer) the higher preference a process is given during scheduling when the kernel decides which process to allocate a CPU next. In the header file process.h under include/ the process table data structure, struct procent, is defined. Look at the priority field of procent and using detective work determine how many bits are consumed by the priority field and whether its value can be negative. Explain how you found the answer. If the value can be negative, configure the priority of the NULL process to be -1 during initialization. Recompile XINU on a frontend machine, download and test on a backend machine to verify that it continues to run xsh after initialization.
(c) XINU's shell app, xsh, eventually runs as a process which then outputs a shell prompt "xsh $ " waiting for user input. The steps leading to the creation of a process executing the code of xsh is as follows. nulluser() in initialize.c calls create() where the first argument, startup, is a function pointer to startup() whose code is also contained in initialize.c. The newly created process running the code startup(), in turn, calls create() to create a new process that runs the function main() in main.c. Lastly, the process running main() calls create() to create yet another process that runs the function shell() which is the shell app. The code of the shell app is contained in subdirectory shell/. Outside of lab1, we will not be concerned with XINU's shell, xsh, since it is but an app. We are concerned with the internals of the XINU operating system. Call getpid() which returns the PID of the current process from within the processes running nulluser(), startup(), and main(), and output their values to the console using kprintf() which follows a similar format as stdio's printf(). Do not use the shell command ps for this purpose. Determine the priorities of the two processes running startup() and main(). Explain how you did so.
(d) When configuring the priority of the NULL process (see part (b)) set the value to be strictly greater than the priorities of the two processes running startup() and main(). What happens when you load and run the recompiled XINU on a backend machine? Based on our discussion of how processes are scheduled in XINU, explain the observed behavior. Note that in XINU all processes created using create() start off in a suspended state which means they are not assigned to the CPU. The system call resume() is necessary to change the state of a newly created process to a ready state which allows it to compete with other ready processes for CPU allocation. In our version of XINU, the only task performed by startup() is to create (and resume) a process running the function main().
Remove the "Hello World!" welcome message that is output on console by main(). Instead, write a function, void myhello(void), in myhello.c under system/ which outputs using kprintf() a hello message containing your username and name. Remember to add new function definitions to include/prototypes.h. Make a call to myhello() from startup() just before it creates a process running main(). Since now you have added code residing in a new file, myhello.c, under system/, the question arises as to whether changes need to be made to Makefile in compile/. In earlier versions of Makefile, new code files needed to be explicitly specified. In the current version, all files in system/ are automatically compiled and linked during a build. Verify that your mod works correctly by recompiling XINU and testing on a backend machine. In lab assignments where new functionalities are added to XINU, this will entail adding files containing C and assembly code to system/ and header files to include/. When making changes to source code, it is good practice, even if changes are minor, to annotate the code using comments that specify what was done, by whom, when. Follow this practice when making changes to XINU.
In Linux/UNIX, to create a new process that runs an executable binary, say, /bin/ls, we first use the system call fork() to create a child process and then call the system call execve() with /bin/ls (or a.out) as an argument. In XINU a newly created process is put in a suspended state after it is created using create(). That is, the child process exists as an entry in the process table but it is marked as suspended (constant PR_SUSP in include/process.h). Being in suspended state has the consequence that XINU will not assign CPU cycles to the process until its state is changed to ready (constant PR_READY) by calling resume(). Two steps are needed to put a process into ready state so that XINU's scheduler eventually allocates CPU cycles to the process. The first step is to change the state of the process to PR_READY. The second step is to insert the process into a data structure called a ready list where other ready processes who are waiting to receive CPU cycles are kept. Both steps are performed by the kernel function ready(). ready() is not a system call but an internal kernel function that is called by system calls and other kernel functions.
Code a new XINU system call, pid32 createready(), in createready.c under system/ which is a copy of create() with the same arguments, albeit with a modification that puts a newly created process in ready state. To do so, call ready() toward the end of the code of create() just before restore(mask) is called. Test that the new system call works correctly by calling createready() to create a new process running main() in startup() in place of resume() after create(). When a process is created using createready(), the child is ready to execute on a CPU, similar to how child processes behave in Linux/UNIX and Windows.
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. When that is the case, functions written in assembly may be called from functions coded in C, and vice versa. We may also embed assembly code within C code using a technique called inline assembly. 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, but that is secondary to understanding how to interface functions at the machine code level, called ABI (application binary interface) programming.
Code a function addtwo() of function prototype, int addtwo(int x, int y), in AT&T assembly and place it in addtwo.S under system/. For new functions that are added to XINU, include its function definition in prototypes.h under include/. prototypes.h, in turn, is included in the aggregate header file xinu.h. Your function addtwo() adds the two arguments it is passed and returns the resultant value. Call addtwo() from the XINU process running the function main() (i.e., C code) to test its behavior. When testing, remove the code that creates the process executing xsh which will not be needed.
You will need to make use of machine instructions pushl and popl to push onto and pop from a process's run-time stack, movl to copy content between registers or register/main memory, addl to add values in registers (one of the registers can contain an address, i.e., point to a memory location and through indirection access its content), ret to return from addtwo to its caller, among other instructions. Check the reference material for AT&T assembly for details of their usage. The potentially tricky part lies in ensuring that the caller main() coded in C, and the callee addtwo() coded in assembly, interface correctly to (1) pass the two arguments from caller to callee, (2) callee returns the added value to the caller, and (3) callee jumps back to the caller so that it can continue where it left off. That is, statement in main() after the call to addtwo(). The assembly code of main() is generated by gcc which follows CDECL for our 32-bit x86 backend CPUs. For your code addtwo.S to work seemlessly with main(), you must make sure to follow CDECL as well. When you understand ABI programming on our software/hardware platform, you will be able to apply the framework to other platforms although details will vary.
For our CDECL software/hardware environment, the caller main() pushes the two arguments of addtwo() parsed right-to-left onto the stack frame of main() followed by pushing of the return address. The return address is contained in the 32-bit x86 program counter, called instruction pointer (a register), EIP. If the caller uses registers EAX, ECX, EDX, it is the caller's responsibility to safekeep their values in case the callee overwrites them. All other register values must be safeguarded and restored by the callee in case it uses them. As discussed in the lectures, the traditional approach to facilitate bookkeeping chores of the stack by the callee is to use the frame pointer register, EBP, called base pointer in Intel nomenclature. Use of EBP is not necessary, however, for clarity and straightforward coding, please utilize EBP in CS354 implementations.
Your code in addtwo.S accesses the two arguments with the help of EBP. Before doing
so, it must safekeep its old value by pushing it on the stack. Then update EBP by copying
the value of the stack pointer, ESP, which points to the top of the stack (now
containing the old EBP value belonging to the caller) into EBP. Thus EBP contains an
address that acts as the boundary of the caller's stack frame and the callee's stack
frame. An instruction such as
would copy the first argument of addtwo() into register EAX by adding an offset of 8 bytes to the value of EBP and following it via indirection operation ( ). Remember that EBP contains an address that points to the old EBP value stored on the stack, below which are stored the return address followed by the first and second arguments passed by the caller. After performing addition of the two arguments, returning the result to the caller is done in CDECL by putting the value into register EAX. The caller main()'s assembly code, generated by gcc, will expect the return value to be stored in EAX. Eventually, the callee will need to prepare to jump back to the callee by making the stack pointer, ESP, point to the end of the stack frame of the caller where the return address was placed. Using EBP, we can pinpoint this location as EBP + 4. Hence the usefulness (but not necessity) of EBP. Executing the instruction ret will prompt x86 to copy the address pointed to by ESP into EIP which will then cause a jump to this address. Begin your assembly code in addtwo.S with
.text .globl addtwo addtwo: /* insert your code here */Annotate your assembly code with comments which will help the TAs evaluate your code. By using the capital letter .S suffix in the filename addtwo.S, the preprocessor will be invoked first after which the processed code (e.g., removal of comments) is forwarded to the assembler.
Additional issues to consider when coding addtwo.S include if you need or decide to use a register besides EAX (e.g., EBX, ECX, EDX) to store the second argument before performing an addl ALU instruction in the CPU. If you do, determine whether it is the callee's responsibility to safeguard and restore its old value before returning to the caller in keeping with CDECL. Addition, an ALU operation, can potentially alter bits in the EFLAGS register such as the carry flag. To guarantee that when the callee returns to the caller it continues in the same machine state prior to calling addtwo(), EFLAGS needs to be safeguarded in the stack by the callee and restored before executing ret. Use pushfl/popfl instructions to perform this task. Although the number of lines of addtwo.S is small, each instruction will matter and play a necessary role in your code. Use this exercise to solidify and remove any ambiguity in your understanding of how function calls, as basic building blocks of software systems including OS, work at the ABI level where fast and efficient software execution is facilitated by hardware support.
We will do a role reversal of Problem 3.4 where instead of calling a function coded in assembly from a function coded in C, we will focus on calling a function coded in C from a function coded in assembly. That is, you will perform the chores of the caller following CDECL when writing assembly code, keeping in mind that the callee's C code is translated by gcc following CDECL. For testing purposes, your caller, int mycaller(void), in mycaller.S under system/ will be called from main(). mycaller() in mycaller.S will then call a C function, int addtwoinC(int a, int b), placed in addtwoinC.c in system/. addtwoinC() just returns a + b. Hardcode the two arguments passed by mycaller() to addtwoinC() so that their values are 3 and 5. Since you are responsible for the caller code, you will need to push the two arguments (5 followed by 3) onto the stack, followed by the return address before jumping to addtwoinC(). After addtwoinC() returns the result in EAX, you will need to preserve it so that main() can inspect EAX and output its value by calling kprintf(). Since main() is coded in C, gcc will handle copying EAX to a C variable. For example, s = mycaller() where s is a local variable of main() of type int. Following CDECL, consider if you are responsible for safekeeping and restoring any register values that are not the responsibility of the callee addtwoinC() or your caller main(). That is, mycaller() is both a caller and a callee. Code, test and verify that your implementation works correctly.
In operating systems such as Linux/UNIX and Windows, a question arises after a parent process creates a child process: who runs first, child or parent? On the frontend Linux PCs, write test code in childorparent.c that evaluates who runs first after spawning a child using fork(). Do not look up answers in books or online. This is an empirical evaluation from which a definitive answer cannot be drawn. Using real-world apps such as concurrent client/servers where a parent forks multiple worker processes to carry out tasks, discuss if one design (e.g., parent first) is more suited than the other. Discuss what decides who runs first in XINU. Include your answer in lab1answers.pdf. Place childorparent.c in lab1/, not subdirectory system/.
Note: The bonus problem provides an opportunity to earn extra credits that count toward the lab component of the course. It is purely optional.
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.
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-fall2020/compile directory and run "make clean".
ii) Go to the directory where lab1 (containing xinu-fall2020/ and Lab1Answers.pdf) is a subdirectory.
For example, if /homes/alice/cs354/lab1/xinu-fall2020 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.