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.
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 a frontend PC's terminal acts as a remote console of the selected 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) XINU initialization, idle process, and process creation. Inside the system/ subdirectory in xinu-spring2023/, you will find the bulk of relevant XINU source code. The file start.S contains assembly code following AT&T syntax that is executed after XINU bootstraps on a backend using the Xboot bootloader. Some system initialization is performed by Xboot, but most OS related hardware and software initialization is carried out by start.S and other XINU code in system/ after Xboot jumps to label start in start.S. Eventually, start.S calls nulluser() in initialize.c which continues kernel initialization. nulluser() calls sysinit() (also in initialize.c) where updates to the process table data structure proctab[] are made. In XINU, as well as in Linux/UNIX and Windows, a process table is a key data structure where bookkeeping of all created but not terminated processes is performed. In a 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 discussed under 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 and statically linked on a frontend Linux PC for our target backend x86 CPU, i.e., the executable binary xinu.xbin. 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 parameter defined in config/), sysinit() sets up the first process, called the NULL or idle process. This idle 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 descendants through system calls, e.g., fork() in Linux, CreateProcess() in Windows, and create() in XINU. The NULL process is the only process that is not created by system call create() but instead custom crafted during system initialization.
Code a new XINU system call, createmod(), that has the same function
prototype as create() but for an additional argument of type, pid32, that
is passed as second argument:
pid32 createmod(void *funcaddr, pid32 reqpid, uint32 ssize, pri16 priority, char *name,
uint32 nargs, ...);
The argument reqpid specifies the PID (process identifier) requested by the
calling process. In XINU as in Linux/UNIX and Windows system calls to spawn a new
process do not allow a specific PID value to be requested. The modified system
calls, createmod(), will allow that.
createmod() checks if a process with PID reqpid already exists. If so, it returns
SYSERR indicating that process creation failed. If reqpid equals 0 (the PID of the
NULL/idle process) then createmod() allocates an unused PID (if one exists).
Since XINU puts a limit on the total number of processes allowed to co-exist at
the same time (examine the code create.c to gauge what this limit may be),
your createmod() must explicitly check that reqpid does not fall outside the
allowed range. Code createmod() in createmod.c under system/. Compile a
new XINU binary xinu.xbin on a frontend machine. Use main() in main.c as your
application layer test code to assess correct operation of createmod() as
noted in (b) below.
The TAs will use their own main.c to test your kernel modification.
Important: When new functions including system calls are added to XINU, make sure to add its function prototype to 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 (e.g., system call or internal kernel function) or app code, you need to recompile XINU on a frontend Linux machine and load a backend with the new xinu.xbin binary.
(b) Role of XINU's main and removing xsh. After nulluser() sets up the NULL/idle process, it spawns a child process using system call create() which runs the C code startup() in intialize.c. Upon inspecting startup(), you will find that all it does is create a child process to run function main() in main.c. We will use the child process that executes main() as the test app for evaluating the impact of kernel modifications on application behavior as noted above. In the code of main() in main.c, a "Hello World" message is printed after which a child process that runs another app, xsh, is spawned which outputs a prompt "xsh $ " and waits for user command. We will not be using xsh since it is but an app not relevant for understanding operating systems. Remove the "Hello World" message from main() and put it in a separate function, void mymotd(void), in system/mymotd.c. Call mymotd() from nulluser() before it executes an infinite while-loop as idle process. Customize the "Hello World" message so that it contains your name and username. Don't forget to insert the function prototype of mymotd() in include/prototypes.h. Modify main() so that it is completely empty but for a message that says "Executing main() by test process:" followed by the PID of process. You may determine the PID of the current process by calling getpid(). Carry over these modifications to subsequent lab assignments unless specified otherwise. When performing testing in (a), use the XINU version of (b).
(c) Process termination. We will consider what it means for a process to terminate in XINU. There are two ways for a process to terminate. First, a process calls exit() which is a wrapper function containing system call kill(): kill(getpid()). In the relevant part of kill() the current process (i.e., process in state PR_CURR executing on Galileo's CPU) removes itself from the process table and calls XINU scheduler so that it may select a ready process to run next. As noted in class, XINU selects the highest priority ready process that is at the front of the ready list to run next. The ready list is a priority queue sorted in nonincreasing order of process priority. Since XINU's idle process is always ready when it is not running (it only runs when there are no other ready processes since it is configured to have strictly lowest priority), the ready list is never empty unless the idle process executes on the CPU. Other chores carried out by kill() include closing descriptors 0, 1, 2, and freeing the stack memory allocated to the terminating process.
Second, a process terminates "normally" without calling exit() (i.e., kill()). Since the first argument of create() is a function pointer, normal termination implies returning from the function, i.e., executing the ret instruction in x86. The question, therefore, is where does the function return to since it was not called by another function. For example, if a process calls create(main, 1024, 20, "main", 0, NULL) then a child process is created which executes the code of function main(). When main() executes return where does it return to? The technique used by XINU is to set up the run-time stack upon process creation so that it gives the illusion that another function called the function executed by create(). This function that acts as the caller is identified by the macro INITRET whose definition can be found in a header file in include/. Playing detective, trace the sequence of events that transpire when the function executed by create() returns. Describe the sequence in lab1ans.pdf.
(d) Keeping track of child processes. Add a new process table field, uint16 pr_children, which keeps track of how many child processes created by a process have not terminated. Modify the procent structure in include/process.h to do so. pr_children should be initialized to 0 in createmod(). Whenever a new process is created by createmod(), the pr_children field of the parent should be incremented. When a process terminates the pr_children field of its parent should be decremented. Note that one of the process table fields holds the PID of the parent process. Of course, a process that is about to terminate may have been an orphan process, i.e., its parent already has terminated, in which case, no update to pr_children needs to be made. Implement a new system call, syscall childrennum(pid32 pid), in system/childrennum.c that returns the number of children of the process specified in the argument. If the process does not exist childrennum() returns SYSERR. Test and verify that your code works correctly.
(a) Main differences. Discuss the main differences between how a new process is spawned using create() in XINU vs. fork() in Linux. This includes what code is executed by a newly created child process, its priority, its state (e.g., ready), and at least one additional difference.
(b) Process priority and execution of sample XINU code. Implement the sample code involving main, sndA, sndB in Presentation-1.pdf discussed in class. In the first scenario, let startup() in initialize.c call create() to spawn a child process to execute main() where the child's priority is set to 15. In sndA and sndB, use kputc() in place of putc(). Test your XINU code on a backend and describe what you find in lab1ans.pdf. Explain the results based on our discussion of how fixed priority scheduling works in XINU. Repeat the above with the priority of the child process executing main() to 23. Discuss your results.
As discussed in class, XINU as well as Linux and Windows, can be viewed conceptually as being comprised of two main parts: upper half code that responds to system calls and lower half code that responds to interrupts. We introduced simple changes to XINU's upper half in Problem 3. Here we will consider a basic operation of the lower half involving clock interrupt handling. When discussing the code examples/gaussadd.c in the course directory we noted that even though gaussadd.c does not contain any system calls, a process executing its code may still transition from user mode to kernel code due to interrupts while the process is running. For example, a hardware clock may generate an interrupt that needs to be handled by XINU's lower half. We noted that a process is given a time budget, called time slice or quantum, when it starts executing. Noticing when a process has depleted its time budget is achieved with the help of clock interrupts.
In computer architecture the term interrupt vector is used to refer to an interface between hardware and software where if an interrupt occurs it is routed to the responsible component of the kernel's lower half to handle it. In our case, the interrupt handling code of XINU that is tasked with responding to the clock interrupt, called system timer. The clock interrupt on 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. The default value varies across kernels. We will investigate the role of system timers in more depth when discussing device management later in the course. For now, we will be concerned with its basic operation which is needed for understanding how kernels, including XINU, behave. Our x86 backend processor supports 256 interrupts numbered 0, 1, ..., 255 of which the first 32, called exceptions (or faults), are reserved for dedicated purposes. The source of interrupts 0, 1, 2, ..., 31 are not external devices such as clocks and network interfaces (e.g., Bluetooth, Ethernet) but the process currently executing on Galileo's x86 CPU. For example, the process may attempt to access a location in main memory that it is not allowed which will likely result in interrupt number 13, called general protection fault (GPF). The process may attempt to execute an instruction that divides by 0 which maps to interrupt number 0. XINU chooses to configure clock interrupts at interrupt number 32, i.e., the 33rd interrupt, the first interrupt number that is not reserved for special use.
When a clock interrupt is generated, it is routed as interrupt number 32 with the help of x86's interrupt vector -- called IDT (interrupt descriptor table) -- to XINU's kernel code clkdisp.S in system/ which, in turn, calls clkhandler() in system/clkhandler.c to carry out relevant tasks. Modify clkdisp.S so that a global variable, int msclkcounter1, declared and initialized to 0 in clkinit.c, is incremented when clkdisp.S executes every 1 msec when a clock interrupt is generated. That is, unless clock interrupts are disabled by XINU in which case msclkcounter1 does not get updated. The more XINU disables clock interrupts the more inaccurate msclkcounter1 becomes as a software timer that keeps track of time elapsed in unit of 1 msec since bootloading a backend. Declare a second global variable, int msclkcounter2, in clkinit.c initialized to 0, that is incremented by clkhandler() in clkhandler.c which is called by clkdisp in clkdisp.S. Verify that both msclkcounter1 and msclkcounter2 keep the same time using test code in main(). Describe your method for verifying using main() in lab1ans.pdf. Note: Testing and verification of correctness of real-world software is rarely perfect. What we aim for is a high standard of confidence which develops through putting into practice knowledge and skill.
(b) An important task carried out by XINU's clock interrupt handler is keeping track of how much of a process's time budget (i.e., time slice or quantum) has been expended. If the time slice remaining reaches 0, clkhandler() calls XINU's scheduler, resched() in system/resched.c, to determine which process to execute next on Galileo's x86 CPU. When a process runs for the first time after creation, its time slice is set to QUANTUM which is defined in one of the header files in include/. Its default value is on the small side. Reconfigure it to 15 (msec). Unused time slice of the current process is maintained in the global variable preempt which is decremented by clkhandler(). If preempt reaches 0, XINU's scheduler is called. Rerun the test of Problem 3.2(b) where the priority of the process executing main() is set to 23. Compare your new results against the output of 3.2(b). Discuss what you find.
Some aspects of operating system code cannot be implemented in C but requires coding in assembly to make the system do what we want. There are two methods for invoking assembly code from C code: calling a function coded in assembly from a C function and in-line assembly. Here we will look at the former. In-line assembly will be considered in lab2. When programming entails interfacing C code with assembly code it falls under ABI (application binary interface) programming, as opposed to API programming. When controlling computing systems using C is not possible, ABI programming becomes an important tool. We will only be needing basic elements of AT&T assembly coding on x86 CPUs. We will practice coding functions in assembly so that they can be called from a function coded in C. Coding in assembly to interface with C functions is also an exercise that helps check that you understand how the CDECL caller/callee convention for our 32-bit x86 Galileo backends works.
You are provided a function addtwo() of function prototype, int addtwo(int x, int y), coded in AT&T assembly in addtwo.S in the course directory. Copy the file into your system/ directory on a XINU frontend. Please remember to update include/prototypes.h. Call addtwo() from main() and verify that it works correctly. Beyond the algorithmic aspect of addtwo() (i.e., performing addition of two integers passed as arguments), note that addtwo() saves the content of EFLAGS (by executing instruction pushfl) and EBX registers onto the stack and restores them before returning to the caller. In x86 CDECL the calling function is responsible for saving and restoring the content of registers EAX, ECX, EDX. Hence the callee may use these registers without worrying about disturbing their content. EBX, if utilized by the called function, is the responsibility of the callee. Some arithmetic operations may modify bits of the EFLAGS register, hence the callee addtwo() must ensure that EFLAGS is restored to its original content before returning. If the callee does not change the bits of EFLAGS, this step can be omitted. The sample code addtwo.S shows typical steps that called functions need to consider performing. It is not optimized code where all unnecessary steps are removed.
Using addtwo.S as a reference, code mintwo() with function prototype, int mintwo(int, int), in AT&T assembly in system/mintwo.S that returns the minimum of the two values passed in the argument. Annotate mintwo.S with comments, and add your name and username at the beginning of the file. You may check reference material for background on AT&T assembly programming. Although assembly code syntax varies across different hardware and software platforms, the underlying logic behind ABI programming remains invariant. It is this understanding that is important to acquire. Test and verify that mintwo() works correctly.
Code a C function, int multhree(int, int, int), in system/multhree.c where multhree() returns the multiplication value of the three arguments. Code a function testmulthree(int a, int b, int c) in system/testmulthree.S in AT&T assembly which calls multhree() with arguments a, b, c. testmulthree(), in turn, is called by main() which prints the value returned by testmulthree(). In x86 CDECL the return value is communicated from callee to caller through register EAX. gcc will ensure that multhree() puts the multiplied value in EAX before returning to its caller testmulthree(). Your assembly code testmulthree() must make sure that the value contained in EAX is not disturbed and communicated back to its caller main(). testmulthree() must access the three arguments passed by main() and pass them to multhree() by placing them in the correct order on the stack before executing "call multhree". Test and verify that your code works correctly.
On a frontend Linux PC, code a function LinCreateProcess() with function prototype, int LinCreateProcess(char *, unsigned, ...), that uses system calls fork() and execve() to spawn a new process that executes the binary executable (full pathname) passed as a string in the first argument. The second argument specifies how many command-line arguments (if any) the binary executable accepts. For example, LinCreateProcess("/bin/ls", 2, "-l", "-a") results in a child process being forked using fork() which then executes /bin/ls by calling execve() on a frontend Linux PC in the XINU Lab. Place your code LinCreateProcess.c in xinu-spring2023/ (not in subdirectory system/). In what way is Linux's clone() library function (it is not a system call) closer to XINU's create() than LinCreateProcess()? Explain your reasoning in lab1ans.pdf.
Note: The bonus problem provides an opportunity to earn extra credits that count toward the lab component of the course. It is intended to help reach the maximum contribution of the lab component (45%) more easily. It is purely optional.
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-spring2023/compile directory and run "make clean".
ii) Go to the directory where lab1 (containing xinu-spring2023/ and lab1ans.pdf) is a subdirectory.
For example, if /homes/alice/cs354/lab1/xinu-spring2023 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.