Lab 1

#cs354#xinu#operating-systems#os

system/ contains most code

start.S contains assembly code that calls nulluser() function which is in initialize.c. This then initializes the kernel.

nulluser() calls sysinit() within the same file which updates process table.

3 Inspecting and Modifying XINU §

• Inspect start.S ✅ 2023-09-05
  • Take note of where it calls ‘nulluser()’ function
• Inspect initialize.c ✅ 2023-09-05
  • Take note of nulluser function
  • Take note of sysinit function
  • Trace ‘main’ and try and understand how it works ✅ 2023-09-05

initialize.c(): §

nulluser()**: §

Initializes the system and becomes the ‘null process’

• Called in start.S
• Calls sysinit()
• Prints free memory
• enables interrupts with enable() function
• Creates process to finish startup and start main:
  •    resume(create((void *)startup, INITSTK, INITPRIO, "Startup process", 0, NULL));
• Finally while(TRUE) loop to idle

sysinit(): §

• Called from nulluser() (see above)
• Calls platinit() (platform specific initialization)
• Resets the console
• Calls initevec(), which inits interrupt vectors
• Calls meminit(), which inits the free memory list
• Inits process table entries free
  • for (0, NPROC) -> set it as PR_FREE, and default values
  • Initializes proctab[NULLPROC] for the nullprocess entry.
  • null process is “prnull”
• Inits sephamores (S_FREE)
• Calls bufinit(), which initilizes buffer pools
• Create ready list for processes (calls newqueue())
• Inits real time clock clkinit()
• Calls init(i) for (0, NDEVS) idk what this does

startup(): §

Finish startup tasks that cannot be run from the ‘Null Process’ and then create and resume the main process

• Called from nulluser() (see above)
• Creates main process:

resume(create((void *)main, INITSTK, INITPRIO, "Main process", 0, NULL));

main.c(): §

• main() process created from startup() in initialize.c
• Xinu stuff runs here! Currently it is starting a shell from ‘shell.c’

3.1 (a): §

• Change NPROC from 100 to 10 (defined in config/) ✅ 2023-09-05

3.1 (b): createppid §

(b) XINU idle process and process creation. sysinit() sets up the first process, called the idle or NULL 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 UNIX, 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, createppid(), that has the same function prototype as create() but for an additional argument of type, pid32, that is passed as the fourth argument:

pid32 createppid(void *funcaddr, uint32 ssize, pri16 priority, pid32 reqppid, char *name, uint32 nargs, …);

The argument reqppid specifies the PID (process identifier) requested by the calling process to be its parent. That is, irrespective which process called createppid() to spawn a child, the child process specifies who it wants to be the parent. In Linux/UNIX the parent of a process may change if a process becomes an orphan, i.e., its parent terminates first. Orphaned processes are adopted, by default, by process 1. In XINU as in Linux/UNIX and Windows, system calls to spawn a new process do not allow a process to request to be adopted. The modified system call, createppid(), will allow that.

create() remembers the parent PID of a newly created in process table field, pid32 prparent. createppid() checks if the process with the requested parent PID, reqppid, exists. If so, the child’s prparent field is updated to reqppid. If not, createppid() returns SYSERR (defined as -1). Of course, createppid() must check that reqppid falls within the valid range of PIDs 0, …, NPROC-1, and return SYSERR if it does not. Code createppid() in createppid.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 createppid() as noted in (c) below. The TAs will use their own main.c to test your kernel modification.

• Code createppid() function (See 3.1b in handout) ✅ 2023-09-05
  • Understand ‘Create’ function ✅ 2023-09-05

Create(): §

Create a process to start running a function on x86

pid32   create(
      void      *funcaddr,  /* Address of the function  */
      uint32    ssize,      /* Stack size in bytes      */
      pri16     priority,   /* Process priority > 0     */
      char      *name,      /* Name (for debugging)     */
      uint32    nargs,      /* Number of args that follow   */
      ...
    )

• newpid() is called, which obtains a new (free) process ID
  • loop 1 to NPROC, find a ‘PR_FREE’
• Use obtained PID and create a new process entry for it

createppid(): §

Create parent process id

1. createppid checks if requested parent id process exists
2. If so, child’s parent field is updated to it
3. If not, returns SYSERR
4. Also checks if reqppid falls within 0, …, NPROC - 1 (syserror if not)

pid32 createppid(
		void* funcaddr,
		uint32 ssize,
		pri16 priority,
		pid32 reqppid,   /* requested pid */
		char* name,
		uint32 nargs,
		...
	)

Implementation Strategies §

1. Copy and paste create() and modify it ✔
   • Add a check to see if reqppid exists
   • prptr->prparent = (pid32) getpid() with prptr->prparent = reqppid
2. Call create(), then find process in table and change it’s parent to be the reqppid.

3.1 (c): §

• Remove xsh and code helloworld.c. See handout ✅ 2023-09-05

3.1 (d): §

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 the XINU scheduler, resched(), 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 of 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 create() to its caller by executing the ret instruction in x86. The question is where does create() 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 ret 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 create(). This fake 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 a process terminates normally by create() executing the x86 ret instruction. Describe your finding in lab1.pdf. Does the fake caller of main() specified by INITRET return? Explain your reasoning. Are there system calls in Linux that, upon success, do not return? If so, describe the system calls and explain why they may not return. Make sure to distinguish system calls from user library functions.

• Investigate process return technique XINU uses from the macro “INITRET” ✅ 2023-09-06 INITRET is the address of a function called “userret”

userret(): §

Called when a process returns from the top-level function. Calls kill on current process upon return.

kill(getpid());            /* Force process to exit */

kill(): §

Kill a process and remove it from the system

• Closes ‘prdesc’s
• Free stack memory
• If PR_CURR: Sets process state to ‘free’ & reschedules
• If PR_SLEEP or RECTIM, unsleeps and marks free
• If PR_WAIT -> does some sephamore stuff idk and then falls through to ready
• If PR_READY (or wait): removes from queue with getitem(pid)
• default (also fall through by pr_ready and wait): Mark prstate as free

3.1 (e): §

(e) Ancestry lineage. Code a new XINU system call, int32 listancestors(pid32), in system/listancestors.c that uses the prparent process table field to output all the ancestor process IDs of the process specified in the argument. listancestors() returns the number of ancestor processes. Annotate your code, test and verify that it works correctly.

• Code systemcall listancestors() ✅ 2023-09-07
• Implementation (list traversal)

int cnt = 0;
while(pr->prparent != NULL) {
	cnt += 1;
	pr = proctab[pr->prparent];
}

• Question: How come I am getting a cycle with my prparent process table? ✅ 2023-09-11
  • Theory: Process cleans up, new process assigned to cleanup, but ‘prparent’ is never ‘cleaned’, so the real ‘child’ process actually ends up taking the spot of the old parent.
  • Why are created processes marked as “PR_FREE”?
    • Parent process ends before child can run listancestors. Fix is to add a delay to the parent.

Todo: §

• Add a process printer

3.2 Round Robin Scheduling §

Implement a modified version of the sample code involving main, sndA, sndB in Presentation-1.pdf discussed in class. Note that a parent process executing main() spawns two child processes by calling create() which execute sndA and sndB, respectively. Add two additional functions, sndC and sndD, that output characters ‘C’ and ‘D’ to console, respectively. First, let startup() in initialize.c call create() to spawn a child process to execute main() where the child’s priority is set to 30. In sndA, sndB, sndC, and sndD, use kputc() in place of putc(). Test your XINU code on a backend and describe what you find in lab1.pdf. Explain the results based on our discussion of how fixed priority scheduling works in XINU.

Second, repeat the above with the priority of the child process executing main() set to 10. Explain your results.

Third, repeat the first scenario with the priority of the child process executing main() set to 20. Discuss your finding.

With Priority 30: A consecutively, then B then C then D. With Priority 20: similar behavior to 30 With Priority 10: Just ‘A’ is being printed.

4 Kernel Response to Interrupts §

4.1 Clock Interrupt and System Timer §

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/. Code in clkdisp.S, in turn, calls clkhandler() in system/clkhandler.c to carry out relevant tasks. Declare a new global variable, uint32 clkcountermsec, in clkinit.c and initialized it to 0. Modify clkdisp.S so that clkcountermsec is incremented when clkdisp.S executes every 1 msec due to clock interrupt. Note that the software clock, clkcountermsec, does not get updated if XINU’s hardware clock that acts as the system timer is disabled. The more XINU disables clock interrupts the more inaccurate clkcountermsec becomes as a timer that counts how many milliseconds have elapsed since a backend was bootloaded. Legacy XINU uses a global variable, uint32 clktime, that is updated in clkhandler() to monitor how many seconds have elapsed since a backend was bootloaded. Test and assess whether both clkcountermsec and clktime keep the same time using test code in main(). Describe your method for testing and your finding in lab1.pdf.

Clock interrupt: 32

clkdisp.S §

Interrupt dispatcher for clock interrupts

• Calls ‘clkhandler’ function ‘high level handler’

clkhandler.c §

High level clock interrupt handler

• Counts every 1000ms then increments clktime (1 second)
• Handles sleeping timer
• Handle ‘preemption counter’, and reschedules when remaining time is 0

Task: §

• Declare uint32 clkcountermsec ✅ 2023-09-07
• Modify clkdisp.S to increment counter every ms due to interrupt ✅ 2023-09-07
• Compare clktime in clkhandler() to your counter ✅ 2023-09-07
• Test and assess if both are the same ✅ 2023-09-07
• Discuss findings in lab1.pdf ✅ 2023-09-07

4.2 Wall Clock Time Termination §

Code a new system call, uint32 wallclkterm(uint32), in system/wallclkterm.c. wallclkterm() compares clkcountermsec with the argument that was passed. If clkcountermsec is strictly less, wallclkterm() subtracts clkcountermsec from the argument and returns the result. Otherwise, wallclkterm() calls exit() to terminate the current process. Test and verify that your implementation works correctly.

As part of testing and an application of wallclkterm(), modify the first benchmark scenario of 3.2 so that sndA, sndB, sndC, sndD are not in a never-ending loop whose execution you have to manually terminated. Instead, the functions replace while(1) with while(wallclkterm(5000)) so that each process terminates 5 seconds after bootloading. Note that wallcklterm() helps achieve synchronized termination, albeit approximately.

• Implement wallclkterm() ✅ 2023-09-07
• Test it ✅ 2023-09-07

4.3 Time Slice Management §

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 2 is on the small side. 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 3.2 and compare QUANTUM size 2 and 10 ✅ 2023-09-07
  • How many ‘consecutive’ characters being printed is much more than it was before. Individual process has more cpu time to print, thus printing more before switching to a different process (say, A to B)
• List findings in lab1.pdf ✅ 2023-09-07
  • **problem: ** there is no difference between quantum size 2 and 10 from my findings.

5 Interfacing C and Assembly Code §

5.1 Calling Assembly Functions From C §

Two methods for invoking assembly code from C:

1. Calling a function coded in Assembly from C ^00b2e1
2. In-Line assembly We will use 1. Interfacing C with assembly is known as ”ABI” programming (application binary interface). Provided function: ‘addtwo()’, int addtwo(int x, int y), coded in addtwo.S in course directory.

• Copy the file into system/ directory on Xinu frontend ✅ 2023-09-11
• Call and test if it works properly ✅ 2023-09-11
• Create addsub() int addsub(int, int, int) ✅ 2023-09-11
  • If first argument is 0, subtract 2nd arg from 3rd, and returns result
  • If first argument is 1, returns sum of 2nd and 3rd argument
  • Else returns -1
  • Refer to Reference Manual for additional background

5.2 Calling Assembly Functions From C V2 §

Flaw of 5.1’s addsub() is that -1 is overloaded (we can get -1 from adding/subtracting certain numbers).

• Implement addsubv2(int, int, int, int*), where 4th argument is a pointer to an integer where result is stored. ✅ 2023-09-11
  • Return value is now 0 if proper 1st argument, -1 if not.

5.3 Calling C function from assembly function §

• Write addsubC(int, int, int) in system/addsubC.c doing the same as 5.1 ✅ 2023-09-11
• Code testaddsubC(int,int,int) in system/testaddsubC.S in assembly, which calls addsubC with three arguments. This assembly is then called by main(), which prints the return of testaddsubC. ✅ 2023-09-11 Return value is communicated from callee to caller by EAX register gcc will ensure that addsubC() puts result in EAX before returning to testaddsubC. So, testaddsubC must not mess up the EAX register and communicate the arguments passed by main properly. Argument Movement: Main -> TestAddSubC -> addsubC

Bonus Problem §

From the viewpoint of a system programmer compare XINU’s create() system call to spawn a new process to fork()/execve() and clone() in Linux, and CreateProcess() in Windows. Make create() the reference point, and ignore features in fork()/execve(), clone(), CreateProcess() that go beyond the basic tasks carried out by create(): create a separate process, specify what code the child should execute, its stack as the principal private resource, and any optional arguments to be conveyed to the child. Shared file descriptors, virtual memory, etc. are topics to be ignored. We will cover them later in the course. Which of the methods is closest to XINU’s create()? Discuss your reasoning in lab1.pdf.

• Write solution to bonus problem ✅ 2023-09-11

fork() §

• Creates a child process — runs the ‘same program’ after that instruction

execve() §

• Executes program specified by path name
• Causes program currently being run to be replaced by new program with a new stack, heap, and data segments.
• Does not create a new process, instead just replaces current one.
• never returns

clone() §

• Creates a new process which executes specified function.
• New process has shared memory space with caller (optional)

CreateProcess §

• Creates new process which runs independently of creating process - parent/child.
• Runs in security context of parent process
• Share memory space (optionally)