Important links:

Xv6 site: [Link]

Three easy pieces text: [Link] (Note I usually abbreviate this
to 3EP in typing)
Xv6 installation instructions: [Link]
XV6 Install and Add Commands (More help for installing xv6)
Xv6 text: [Link]

LEC 1 - INTRO 01/05/2023

To use school XV6 emulator, login to server

Create directory cs330 . ENSURE IT IS NAMED cs330 AS THE EMULATION IS DEPENDENT
ON THIS. Make sure it's in your home directory.
→ I know directory doesn’t technically doesn’t matter, but Chen said it did. If you
really care about things being 1:1 with Chen's examples then do this, but otherwise
you can ignore it.

Run command git clone [Link]

After cloning and you are in xv6-public directory run command:

make qemu-nox

This will start the xv6 emulator. You will see the shell prompt for the emulation along with some
emulator startup messages.
The startup messages will list the processors as cpuX (where X is the processor number)
You can run command ls to list directories.

To exit xv6 use: ctrl-a, then hit x

What is OS?
→ Manages system processes/resources along with hardware, intermediary between
hardware and applications (an abstraction of hardware from physical resources that
allows higher-level interaction with the hardware)
→ Primarily about management of memory and processes.
This management involves isolation. Allocate specific parts of memory to specific
processes and ensure they don't violate each other's space.
→ Also isolate OS from user code (Ensures that user programs cannot alter OS).
→ OS also heavily involves multitasking. Schedule different tasks to run at different
times, or concurrently.

Consider the hierarchy: Application → Library Function/Command Shell → System

Calls → Kernel → Hardware
In other courses (systems programming) we have used the first 3 parts of this hierarchy.
In this course we will be implementing/creating system calls through use of the kernel; that is to
say, we will focus on the 4th part of this hierarchy.

What do we include an OS? → There’s not really a clear-cut answer. What is included is
dependent on the wishes of the developer of the OS. Oftentimes utility programs,
interpreters, and library functions are included, but these are not necessary for an
operating system.

Why kernel at all?

Two different types of process management methodologies for OS:
Cooperative Scheme: Applications/programs must be monitored and must be bug-free. This is
not optimal and highly dependent on the applications/programs, and therefore it is not a popular
OS model. See more: [Link]

Non-cooperative Scheme: Distinguishes between 2 different modes, kernel mode and user
mode. Different processes are restricted to specific modes, you may need to switch to kernel
mode in order to execute higher-privilege operating system level code. This allows user
software to be independent of the kernel level functions.

What should be included in the kernel?

Like OS, it’s not exactly clear-cut. Two different approaches to kernel design: Monolithic and
microkernel.
In a monolithic model, the entire OS operates within kernel space. This has setbacks, however,
in that if there is a single failing in the kernel, a system crash will occur (ie. it will affect the whole
system). The OS that we will be working with is based off of a monolithic approach. Observe the
diagram below that I so cleverly yoinked from Wikipedia:

Application accesses kernel level through system calls, system returns results to applications.
Kernel passes data to hardware, hardware passes data to kernel.

Some examples of user programs included in xv6 are: printf.c, umalloc.c, echo.c, sh.c,
usertests.c, string.c, wc.c

Some examples of kernel programs include: syscall.c, sysproc.c, trap.c, spinlock.c, sleeplock.c

Consider the bash command uname, which returns the kernel name.
Chen gives the example of the program uname.c. Note that uname.c is not previously provided
by xv6, it is a program that Chen wrote herself.
uname.c functions in a similar way to cat.c.

LEC 2 - CPU VIRTUALIZATION 01/10/2023

Some code examples are discussed below. Note that they are also discussed in the textbook
(Three Easy Three Easy Pieces, Introduction section, pages 3, 4), I highly recommend citing
that as a source over my notes because I can only type so fast. Note that the code for the
programs below is provided at:
[Link]

Chen discusses the program cpu.c.

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int
main(int argc, char *argv[])
{
if (argc != 2) {
fprintf(stderr, "usage: cpu \n");
exit(1);
}
char *str = argv[1];
while (1) {
Spin(1);
printf("%s\n", str);
}
return 0;
}

Note that this program will not run in xv6 as it is above; it must be modified and added to
the Makefile. See mem.c below where I did this; the process is relatively the same.
She demonstrates the command ./cpu A, which prints out A and a new line repeatedly.
The command ./cpu A & ./cpu B prints out A and a new line repeatedly and B and a new line
repeatedly (A printing is handled by 1 process, while B printing is handled by a separate
process. They both run simultaneously).
This example demonstrates CPU virtualization. If a single processor/cpu is running this, the
processes are virtually separated; the cpu is divided into multiple virtual cpus.

mem.c
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int
main(int argc, char *argv[])
{
int *p = malloc(sizeof(int)); // a1
assert(p != NULL);
printf("(%d) address pointed to by p: %p\n",
getpid(), p); // a2
*p = 0; // a3
while (1) {
Spin(1);
*p = *p + 1;
printf("(%d) p: %d\n", getpid(), *p); // a4
}
return 0;
}

Similar to cpu.c, mem.c will not run as it is above. Outlined in later lectures, the program
needs to be changed as follows:
spin() must be replaced by sleep()
printf() must be modified to match xv6’s printf
NULL must be defined as a macro (if you wish to replicate assert())
Must be edited to run as a user program similar to echo.c
All header files are in the current file directory (see echo.c again)
Also match header files for function call syntax.

My edited mem.c:
#include "types.h"
#include "stat.h"
#include "user.h"
#define NULL 0L

int main(int argc, char *argv[]) {

int *p = malloc(sizeof(int)); // a1
if(p == NULL) {
printf(2, "Error allocating memory.\n");
exit();
}
//assert(p != NULL);
 printf(1, "(%d) address pointed to by p: %p\n", getpid(), p);
//printf("(%d) address pointed to by p: %p\n", getpid(), p);
*p = 0; // a3
while (1) {
sleep(1);
*p = *p + 1;
printf(1, "(%d) p: %d\n", getpid(), *p);
//printf("(%d) p: %d\n", getpid(), *p);
}
exit();
}

Also note that in order to run this program, I made edits to the Makefile. You can find this
in the xv6-public directory. There’s no file extension, the file is simply called Makefile .
In order to add this user program, I made the following edits to the Makefile:
1. I added mem to the list of user programs. You can see below my UPROGS section
after adding mem .
UPROGS=\
_cat\
_echo\
_forktest\
_grep\
_init\
_kill\
_ln\
_ls\
_mkdir\
_rm\
_sh\
_stressfs\
_usertests\
_wc\
_zombie\
_mem\

2. I added mem.c under EXTRA. Again, see below.

EXTRA=\
mkfs.c ulib.c user.h cat.c echo.c forktest.c grep.c kill.c\
ln.c ls.c mkdir.c rm.c stressfs.c usertests.c wc.c zombie.c\
mem.c\
printf.c umalloc.c\
README dot-bochsrc *.pl toc.* runoff runoff1 [Link]\
 .[Link] gdbutil\

I will not be including my whole Makefile as that’s a little bit too much for this document.
These should be the only sections in it that require editing in order to get mem to work,
however.

For program mem.c, which requests memory for a value p using malloc, prints out the address
of the memory allocated, and infinitely loops while increasing the value of p:
Upon running mem.c, it will print the address and gradually increment p.

Running mem.c with two different processes simultaneously, its output is:
Printouts of the memory address for each process (they are the same address)
Printouts of the value p that each increment independently.
The addresses are the same, but the memory itself is different. This is because the memory is
virtualized; each process has its own virtual address space/memory that operates
independently.

LEC 3 - CPU VIRTUALIZATION II 01/12/2023

>>ps -ax
→ ps is a command that lists the current running processes, along with their process
IDs.
→ -ax indicates to list all processes (a) owned by the current user (x)
More: [Link]

>>wc (argument)
→ Counts the words in given argument
→ If you do >>wc -l, this returns the number of lines in a given argument
More: [Link]

Demonstrating a run of cpu.c from last lecture, indicating that in order to terminate the program,
instead of simply inputting cntrl-C, you must first bring the process to the foreground by running
command fg.

Demonstrating command >> mem & in the xv6 environment, a run of this command
→ Lists the address pointed to by p
→ Lists the pid and increments p every second
She then demonstrates a run of kill(4) (where 4 is the pid of the current running process mem)
→ The console prints out “zombie!”
She then runs >>mem & mem &. The values p for each process have the same address, but the
p values increment independently, and their process ids are independent, due to memory
virtualization (see last lecture for more details). The addresses listed are not the true, physical
memory addresses, they are virtual memory addresses. These virtual memory addresses are
relative to the memory space assigned to the process.
What does argument “&” indicate? → The process run with this argument will run as a
background process.

On persistence: What memory persists between boots/sessions, and what does not?
→ Process memory is not stored on disk; it is loaded into memory. Disk is used for
more permanent/persistent storage.
→ Memory is fast, but expensive. As such it should only be used for temporary
storage.

As an exercise, we considered the bash command echo. Recall that echo prints out a string
passed in as an argument.
Examine the echo.c code in xv6.

Also consider the bash command cat (which is included as cat.c in xv6).
If there is no argument, then simply exit; if not, for every argument, open the file, then write its
contents to stdout.

Next we examined the code for sh.c (shell).

She suggests trying exec, as it is a system call.
She also indicates the importance of parsing.

Basically, read these files, and try to understand them, as I read them I’ll likely add notes and
comments.

Also consider init.c.

Each process created by fork() creates a parent and a child process tied to it. Init.c is user level
code for the first parent user process; it runs/creates the user shell, which the other processes
are forked from.

LEC 4 01/17/2023

More on the & operator: Often we will run programs with this operator in this class, as not using
it will cause the shell to wait on the process to terminate before displaying the result and
receiving more input.

The sample run of mem.c will result in different addresses for A and B on Mac OS. This is due
to different behaviour of malloc on Mac.

Chen demonstrates how to compile programs properly in xv6. She opens the makefile
contained in the xv6-public directory. Note that this is not a .c file. In this file there is a section
UPROGS (user programs) in which all of the user programs are listed. As for the underscore in
front of each user program, Chen says to figure out what that means.
For the implementation of whoami, we must avoid invoking exec. This means instead of
modifying the makefile and adding something to UPROGS, we must add it somewhere else.

On cprintf vs printf : cprintf is kernel level. This means that printf cannot be used in kernel level
code; printf is user-defined.

Header file in cprintf is in exec.c

sh.c is a user-level program.

Some parts of the shell code (sh.c) that might be important:
She didn’t actually indicate anything here.

LEC 5 01/19/2023

grep is a useful command in working with xv6. Enter: grep (search term) to search for a string in
the files of the current directory. More info: [Link]
command-in-linux-unix/
Also note if you’d like to search for a specific file extension, you may add a third argument. For
example, if you’d like to look for a header file containing malloc, enter: grep malloc *.h

For assignment 1, whoami must be implemented in sh.c . Also note our code will be tested to
ensure that no calls to exec are made within it.

What is a process? → Processes are not programs. Their existence allows for isolation
between user-level and kernel level operations. Processes are programs that are
loaded into memory, each with their own process control blocks containing various
info related to each process. Software code is used to load these processes into
memory.

The init process is the very first process that starts the shell process; this process never dies
while the system is running.

How do I exit running a program in xv6? → Enter kill pid, where pid is the process id of the
process you’d like to kill.

LEC 6 01/24/2023

On the topic of processes, take an example of a shell command myprog that runs a user
program myprog.c . This program is on the disk, it needs to be loaded into the memory to run.
The steps to run the program are:
1. Loading the program code
2. Preparing the stack/heap
3. Assign pid
4. Prepare register values (stack pointer, instruction pointer)
 5. Open file

The shell process runs the current command. A struct is created in order to represent this
process. Shell process will call fork in order to create a process for the new program. Recall that
in systems programming, upon calling fork the return value was the pid; if this pid is 0 it is a
child process, and if it is > 0 it is the parent process. In the shell a new pid is created for the new
child process, then exec will be called and the code will be replaced.

Say there are two processes in memory, and we wish to switch between them. In this case, we
will need to adjust the current stack and instruction pointer to reference process being switched
to.

Here is a diagram of virtualized address space as shown in the xv6 text.

Considering PCB (process control block), we have a struct proc (process structure) in order to
manage processes.
 - Trapframe and context contain register information.

Now observe the code for init.c.

This process never dies (notice the infinite loop). It forks to a child process, replaces it with the
shell process, and waits for the child process to finish. Note that the printf below exec will only
run on failure of the exec call (as will the exit below it). The for loop is entered whenever the
shell terminates; this ensures that the shell is constantly active.

Observe xv6’s proc.c .

The cpu struct pointer represents the cpu running the process; other relevant process
information (ie PCB info) is stored in the proc structure.

Considering buffering: In c, printf() and write() differ in how they are buffered (write is
unbuffered, printf is buffered). Printf is unbuffered by default in xv6. She demonstrates a run of a
printf that is buffered (ie. printf() as it is implemented normally in c). It waits either until the buffer
is full, a linefeed character is reached (\n) or the execution of the current program is terminated
to flush the buffer and give an output.

LEC 7 01/26/2023
Today we examined sh.c.

You can see here that in the case of a list of commands being passed to the shell, the child
process runs the left command, while the parent process runs the right command. For more
info, see the struct listcmd, which is also in sh.c.

We also went over the function of init.c again; it loops constantly and calls exec in order to run
the shell code.
On the topic of exit(), wait(), and sleep(): See proc.c, the code snippets below are from there.
What happens when you call exit()? → Open files are closed, the parent process is
“woken up”, iterate through the process table in order to find children of the
process being exited, and set their new parent to the init process. If the process’
state is ZOMBIE, then have the init process handle the cleanup. The sched() call is a
cleanup function that will be discussed later.
exit() in proc.c (line 228)
void
exit(void)
{
struct proc *curproc = myproc();
struct proc *p;
int fd;

if(curproc == initproc)
panic("init exiting");

// Close all open files.

for(fd = 0; fd < NOFILE; fd++){
if(curproc->ofile[fd]){
fileclose(curproc->ofile[fd]);
curproc->ofile[fd] = 0;
}
}

begin_op();
iput(curproc->cwd);
 end_op();
curproc->cwd = 0;

acquire(&[Link]);

// Parent might be sleeping in wait().

wakeup1(curproc->parent);

// Pass abandoned children to init.

for(p = [Link]; p < &[Link][NPROC]; p++){
if(p->parent == curproc){
p->parent = initproc;
if(p->state == ZOMBIE)
wakeup1(initproc);
}
}

// Jump into the scheduler, never to return.

curproc->state = ZOMBIE;
sched();
panic("zombie exit");
}

What happens when you call wait()? → When you wait, you wait for a child process to
finish. Search for a child of the calling process in the process table. If you find a
child process in ZOMBIE state, perform cleanup. Once the cleanup is finished, return
the pid of the child process. If no children are found, wait returns -1. If the child
exists and is not in a ZOMBIE state, then the current process will sleep until the
child process is complete (in the ZOMBIE state).

wait() in proc.c (line 273)

int
wait(void)
{
struct proc *p;
int havekids, pid;
struct proc *curproc = myproc();

acquire(&[Link]);
for(;;){
// Scan through table looking for exited children.
havekids = 0;
 for(p = [Link]; p < &[Link][NPROC]; p++){
if(p->parent != curproc)
continue;
havekids = 1;
if(p->state == ZOMBIE){
// Found one.
pid = p->pid;
kfree(p->kstack);
p->kstack = 0;
freevm(p->pgdir);
p->pid = 0;
p->parent = 0;
p->name[0] = 0;
p->killed = 0;
p->state = UNUSED;
release(&[Link]);
return pid;
}
}

// No point waiting if we don't have any children.

if(!havekids || curproc->killed){
release(&[Link]);
return -1;
}

// Wait for children to exit. (See wakeup1 call in proc_exit.)

sleep(curproc, &[Link]); //DOC: wait-sleep
}
}

Inside init.c, the shell process is created and a while loop is run to wait until it’s finished. In sh.c,
the shell waits until the forked child process is finished.

Inside exit(), the parent is woken up, and the child processes are checked; then the process
state is set to ZOMBIE to await cleanup by a parent [Link] child processes that are
finished are ZOMBIE processes; the ones that have not are orphaned and are made to be
children of the init process.

Inside wait(), if a zombie child is found clean up and return its pid, if no child is found return -1, if
there is a child sleep until the child is finished and in ZOMBIE state.

Note that these are all user-level code.

The init process creates the shell process when it forks and exec()s to “sh”. Suppose the shell
creates a process PA, with a command “myprog”. This PA calls exit(). At this point the init
process is sleep()ing, waiting for its child (the shell process) to be in a ZOMBIE state. The shell
process is currently waiting for its child PA to finish and become a ZOMBIE.

What happens when a parent process doesn’t call wait()? Courtesy of stack overflow,

She also discussed buffering again. See last lecture for more details.

LEC 8 01/31/2023

We continued to discuss buffered I/O.

In unix, if you use printf(), it will be buffered. stdio has 3 modes, one in which it is fully buffered,
one for line buffered, one for no buffer. Standardly it is line buffered. stderr is not fully buffered.
System calls to read/write are not buffered.

What is the motivation for having a buffer? → You cannot access a device directly; you
must communicate to them using system calls through the OS. However, this involves a certain
amount of overhead. Without any buffer, there will be a system call for every printf() operation.
Introducing a buffer reduces the number of calls, and in turn, the overhead, and ensures that the
system call will only be executed when necessary.

printf() in standard Unix is a library function. It is a user level function, and is not executed in
kernel mode. It implements a call to a kernel-level function, but itself is not a kernel-level
function. Chen discusses the introduction of cprintf() (see console.c if you’re curious about the
implementation, it’s a console print function) into the code of exec.c; it prints normally upon
every call of exec.
She then introduces the call to cprintf() in the code of consputc() (again, see console.c); in this
case it causes a crash. She doesn’t want to explain why this is as it’s very complicated.

Next is a demonstration of cprintf() when introduced in the same place where write is
implemented, in sysfile.c (specifically, in sys_write).

Adding a cprintf() that prints a ~ every call to sys_write, it prints a ~ for each character (when
printing “init: starting sh” it prints instead “~i~n~i~t~:~ ~s~t~a~r~t~i~n~g~ ~s~h~”. Introducing
buffered I/O will prevent the constant system calls.

For the assignment, please note that printf.c should be examined. Also observe cat.c, which is
buffered.

Adding a single star print to sys_read (also in sysfile.c), and running a command echo (with any
text, doesn’t really matter) it prints a number of asterisks equal to the number of characters
passed to the command line; there is one system call for every single character read into the
console.

Upon a command of “cat data”, with the printing of ~ and * implemented, it only prints a single ~
and *. Why is this? → cat is buffered.

Next she changes the size of the buffer in cat.c . Normally cat.c has a buffer of size 512 (see
cat.c, there is a line char buf[512] ; this is the line she changes). Now upon a command of “cat
data”, there is a * and ~ printout every third character.

On file descriptors vs file pointers: File descriptors are used by the kernel. The file pointer is a
pointer to a file struct, which contains a file descriptor, as well as buffer information. She then
shows the Unix file struct:
typedef struct {
int level; //The fullness level of the buffer
unsigned flags; //Status flags for file
char fd;
unsigned char hold; //Ungetc char if no buffer
int bsize; //Buffer size
unsigned char *buffer;
unsigned char *curp; //Pointer to current posn
unsigned istemp;
short token;
 } FILE;

Note that our implementation of the file struct does not necessarily need to be as robust as the
one above. It’s only meant to be an example, the key takeaway here is the differences from
xv6’s default implementation (ie. the buffer).

In choice B for the assignment, we will need to implement fopen() and fclose(). We have to
figure out how.

In Unix, how do you implement a library? → Good question. Chen says to figure it out. I
don’t remember myself but when I go to figure it out I’ll add some tips.

LEC 9 01/02/2023

On interrupts: The management of the system is dependent on interrupts. In the normal flow of
the CPU, it reads the instruction from the IP (instruction pointer), goes to that memory location,
then moves the IP to its next position (incrementally or by jumping); it then executes the
instruction associated with the given location, and repeats this process. The CPU does not do
much management in this regard, which is why scheduling is necessary.

Trap is similar to an interrupt.

In Ch 6 of Three Easy Pieces, direct execution is discussed.

Some notes:
- Creating an entry for process list = Setting up the PCB (process control block)
- The stack initialization is handled in exec()

The concept of delegating control over the process from the OS to a program and back is
referred to as transfer of control.
What happens if you introduce another process? → Given the design above in Figure 6.1,
this becomes a problem. The Program portion of the diagram above indicates a user program,
meaning that it cannot control the instruction pointer. So the user program/process will not be
able to switch to the newly introduced process.

What happens if the Program above gets stuck in an infinite loop? → There’s no way to
“jump out of” the infinitely looping Program. This is another problem with the above
model.

Another potential issue is introduced if the Program above contains malicious code. The OS
would need to be able to detect this; this is possible, but it leaves dealing with this issue to the
OS. I/O in the above model is also slower for the running program.

Next we address the concept of restricted operation. User and kernel modes are used to
achieve this; you must enter from the user mode into the kernel mode in order to execute any
code/process; requests are made from user mode to the kernel, which executes processes.

When a request is made to the kernel (ie. a system call is made), what happens? →
Recall that function calls themselves are not system calls. printf() for example is a library
function. However the implementation of printf() involves calling system call write(). Calling this
write() introduces an interrupt, which notifies the CPU that a change in operation mode is
necessary (from user to kernel mode). In the running of a system call, kernel level code needs
to be jumped to; this is a rather involved process.

On the user stack, say the stack pointer is in a specific position while the instruction pointer is in
another. These will be moved to point to somewhere else when kernel code is jumped to. But
the previous positions of the instruction and stack pointer in the user stack must be saved
somewhere.

No user is supposed to know the functions defined in the kernel. So how is this achieved? The
user requests the service/function. The only entrypoint to kernel-level functionality is trap. With
trap the kernel determines whether the requested service/function is “legal” and runs it if so. All
system calls must go through this same place in order to jump to kernel level code and execute.

Referring once again to the 3EP text chapter 6, now to figure 6.2,
Some notes on this:
- The trap table indicates the legal operations; the requests made by the user processes
are checked against it. (See: [Link]
purpose-of-using-trap-table)
- The first step in OS run in kernel mode is handled by exec().
- User code should not have any knowledge of the trap table or its contents.

LEC 10 02/07/2023
An example of the flow of CPU operation:
Fetch instruction → advance program counter → execute instruction → fetch next
instruction…
Advancing the program counter can be considered jumping from one program location to the
next.

A trap can be thought of as a jump from user code to kernel code. Before this jump occurs, a
change in privilege level must be done; kernel code cannot be jumped to from user code. The
change in privilege level is not handled at the user level.

Say a CPU 0 is running process A, and CPU 1 is running process B. CPU 0 has a stack pointer
pointing to its own stack, and an instruction pointer pointing to its own instruction. Upon a trap
and switching to kernel code, the instruction pointer should be moved to point to the kernel code
and the stack pointer moved to point to the kernel stack.

Next we will be covering chapter 3 of the xv6 text, which involves traps and interrupts.

How do we trace kernel level code? We can trace user-level code by checking their
implementation in a .c or .h file. But for a system call, they are not contained in user-level
libraries. See usys.s:

On a sys call of name, the number of the system call with name = name is moved into the eax
register. T_SYSCALL represents the trap number (trap will be called with id T_SYSCALL; the
interrupt indicates that a system call needs to be made with this int). To see a list of system call
name and their corresponding numbers, see syscall.h :
Assignment 3 will involve implementing a system call.

We also examined the diagram below.

Below is a description of the diagram from the text. For more detail reference the text (ch 3, as
linked above)
So, on a system call, the instruction pointer is moved to point to the kernel code from the user
code and the stack pointer is moved to point to the kernel stack. But upon moving the stack
pointer its previous position must be stored in order to be preserved; therefore it is moved
to/stored in a register. That is to say, before the stack pointer for the current user stack is
pushed to the kernel stack, you must store it in a register. This is because the pushing operation
alters the stack pointer (?).

Also worth noting is that each CPU has an array which contains the kernel stack pointer of the
current process that the CPU is running. There is an individual kernel stack for each process;
traps are handled considering each kernel stack for their respective CPU/process.

Note above that each process has a char* kstack.

From assembly ([Link]), trap.c is jumped to (ie trap is called).

So if a trap is a system call, it will save the pointer to the trap frame into the process control
block (see myproc()->tf = ft) and then perform a system call.

Assignment 2: Some tips

I started by implementing myfprintf, and made the other functions afterwards, it made it easier
for me to determine exactly what I’d need in my file struct.
If you are stuck implementing myfprintf: Look at printf.c in xv6.

The c struct we need to make in this assignment is the FILE struct. If you’re stuck on c structs,
here’s some general info.

Programiz page: [Link]

Say we have a variable structname, with a member structvalue
- To access values of a struct variable, do: [Link]
- To access values of a struct pointer, do: structptr->structvalue
- You can get a pointer to a struct by using the & operator (&structname)
- To initialize a struct object by its pointer, you have to use malloc: do STRUCTTYPE
*structname = malloc(sizeof(STRUCTTYPE));

open() and close() exist as system calls in xv6 just as they do in c. xv6 also has its own fcntl.h
header for the open() flags.

For part B, we need to make a library, so a header file and a file with the function
implementation. Some notes on this:
- You need to #include the header.h file in the implementation.c file.
- In xv6, you need to add your header file to the makefile. You need to make edits to the
makefile as follows:
In the EXTRA section:
 EXTRA=\
mkfs.c ulib.c user.h cat.c echo.c forktest.c grep.c kill.c\
ln.c ls.c mkdir.c rm.c stressfs.c usertests.c wc.c zombie.c\
mystdiotest.c mystdio.h\
printf.c umalloc.c\
README dot-bochsrc *.pl toc.* runoff runoff1 [Link]\
.[Link] gdbutil\

In the ULIB section:

ULIB = ulib.o usys.o printf.o umalloc.o mystdio.o

In particular, make note of the fact that in the ULIB section the extension is .o, not .h .
You still need to add your user program to UPROGS and EXTRA as normal, these are just the
extra steps for adding a library/header file.

If you’d like a struct to be accessed globally from a header, you can define it as such:
In the header:
extern int someglobalvar;
In the implementation:
int someglobalvar = 2;
This variable can be used as such:
#include "header.h"

int main(){
printf("%d\n", someglobalvar); // this just works
}
Thanks to Jeremie for the tip.

Something else to note: if you create a file in xv6, that does not mean that the file is made in the
xv6-public folder. Don’t panic if you don’t see it there. Only an idiot like me would do something stupid like that. Use the ls
command in the emulated xv6 environment, and if you’ve made it correctly then the file should
be there.

Also, if you're getting an error that relates to [Link]: remove usertests from the Makefile.

LEC 11 02/09/2023

Some tips about assignment 2: Take some example calls…

myfprintf(...”Complex system\n”);
myfprintf(...”Too hard!\n”);
myfclose(fp);
Also, suppose you have a buffer of size 28. Your buffer should “remember” its contents across
calls to myfprintf; that is to say, if your buffer is not full from “Complex system\n”, and is filled
partway through adding “Too hard!\n” to the buffer, it should only print once when the buffer is
filled. Also note that myfprintf needs to print on file close.
To open the file, you must get a file descriptor from open() system call, and assign this to the file
descriptor part of a file struct.

She also demonstrates her own test program. The program first demonstrates printing a set of
lines with printf; it writes a line at a time and then sleeps. Then it prints using myfprintf, and
pauses partway through lines due to the buffering.

If you encounter an error in which the file size is too large, remove usertests from the Makefile.

She then goes over Assignment 3, in which we must list the current running processes: Their
PIDs, names, states (sleeping, running, etc.), and parents. We need to access kernel data in
order to do this. The implementation will be similar to UNIX ps, but without arguments. Note that
we will not be modifying the kernel. It is recommended that you look at usys.s. To add a system
call this file will need to be modified, along with syscall.h. You can #define the SYSCALL(pstate)
similarly to how SYSCALL(name) is implemented. She also says to look at the traps.s (and
trap.c). From trap.c, you can trace syscall() (in syscall.c). See below…

Trap calls this syscall(), checks if the process is a valid system call, and sets it to the system call
with the given system call number.
In syscall.c, note that there is also a set of syscalls listed. Many of the syscalls are implemented
externally, (lots of them are in sysproc.c) and so they are listed as extern functions at the
beginning of syscall.c .

LEC 12 02/14/2023

Where can I find the implementation of a system call? → Start by looking in usys.s. All the
syscalls listed there are #defined as syscall(name) for their name. It starts by
moving the system call number associated with the given name into the eax
register. Then, int is called with $T_SYSCALL; this is the trap number. This is where
control is transferred to the kernel.
The system call numbers are in syscall.h . To define a system call, you must give it a system
call ID.

Also note that the trap numbers are defined in traps.h .

Referencing the xv6 text, the call to int saves the stack pointer and instruction pointer and then
moves them to point to kernel-level instructions/stack.
In the assembly portion of the trap call (see trapasm.s), trap frame parameters are pushed into
the kernel stack. This is also where trap is called.

Observing trap.c, see the call to trap; note that the call contains the pointer to the trap frame.

The trapframe pointer is set to the pointer to the trap frame of the PCB before making a
syscall(). In syscall (see syscall.c), the system call ID is retrieved from eax (from the kernel).
Then syscalls() is called with the given system call ID. Some of these syscalls are contained in
sysproc.c ; for example, sys_fork() is contained in sysproc.c, and will be called if the system call
ID associated with fork is passed to syscall(). From sysproc.c, fork() is called.
In order to create a shell command pstate, we need to make a user program that makes a call
to the pstate() system call. Changing header files may also assist in implementing this.

Note that inside the kernel, cprintf() is what is used to print to the console. Once inside the
kernel, various information pertaining to the process struct must be printed.

Internally, there is an array of CPUS; each element is a pointer to a CPU struct. Contained in
this CPU struct there is a pointer to the PCB of the current process (struct proc *proc; note that
if it is NULL the CPU currently is not running any process). See proc.h:

You can also see the various members of struct proc in proc.h. Note the different possible
states for a process: Running indicates that the process is running, runnable indicates that the
process is ready to run but has not been taken on by any CPU yet. RUNNABLE state is reached
from the SLEEPING state before the process is scheduled. Also useful in scheduling, which will
be discussed later, are pgdir and context.

Next we observe the ptable in proc.c. Each ptable consists of a spinlock lock (which will be
discussed later) and an array of process structures called proc (note that NPROC is the array
size, and is defined as a constant that represents the maximum number of processes). Each
element is a PCB, so obtaining process info for pstate should involve some form of access to
this proc array. Note that we need to obtain all processes across all CPUs.
LEC 13 02/16/2023

3 categories/cases of switching to kernel control:

- Interrupt
- Timer, keyboard, other hardware
- Exceptions
- Divide by 0, wrong address; software-related
- Trap
- System calls.
More detail from Ch. 3 of the xv6 text:
“There are three cases when control must be transferred from a user program to the kernel.
First, a system call: when a user program asks for an operating system service, as we saw at
the end of the last chapter. Second, an exception: when a program performs an illegal action.
Examples of illegal actions include divide by zero, attempt to access memory for a page-table
entry that is not present, and so on. Third, an interrupt: when a device generates a signal to
indicate that it needs attention from the operating system. For example, a clock chip may
generate an interrupt every 100 msec to allow the kernel to implement time sharing. As
another example, when the disk has read a block from disk, it generates an interrupt to alert
the operating system that the block is ready to be retrieved.”

Polling vs. interrupts: Polling involves constantly checking for input, while interrupts involve
doing an action upon input. Interrupts are more popular, since they are more efficient.

Suppose you are running a process A and there is a timer event. Instead of a system call, this
will be a timer event (the number passed to trap will not be a syscall number, but a different
number relating to a timer event). There is a number that increments upon each timer event.
How do we switch from process A to the kernel code for A? This is called a context switch, and
is handled by the trap function. Since there is a timer event, the scheduler will also be involved,
along with the kernel stack from the scheduler; there will be a context switch from the kernel
code for A to the kernel code for scheduling. The scheduler code will choose which process to
run next, and then context switch to the kernel code for the process it has chosen. If this
process is not A, then the context information for A will still need to be saved somewhere. Say
this is a process B; then there is a context switch to the kernel code for B, and then another
context switch is performed to switch to the user-level process B.

See the process flow below, where each arrow denotes a context switch:
user process A → kernel code of A → kernel stack of scheduler → kernel code of B → user
process B

Where A’s context information saved? → The register values relating to A’s context are
saved in the kernel stack of A, where the stack pointer to the context of A is saved
in the PCB for A.
Also see the diagram below from 3EP chapter 6: (Note that proc_t(A) = PCB of A)

What about the code for context switching? Diagram from the xv6 text:

Further explanation for the actual code:

“Switching from one thread to another involves saving the old thread’s CPU registers, and
restoring the previously-saved registers of the new thread; the fact that %esp and %eip are
saved and restored means that the CPU will switch stacks and switch what code it is
executing. The function swtch performs the saves and restores for a thread switch. swtch
doesn’t directly know about threads; it just saves and restores register sets, called contexts.
When it is time for a process to give up the CPU, the process’s kernel thread calls swtch to
 save its own context and return to the scheduler context. Each context is represented by a
struct context*, a pointer to a structure stored on the kernel stack involved. Swtch takes two
arguments: struct context **old and struct context *new. It pushes the current registers onto
the stack and saves the stack pointer in *old. Then swtch copies new to %esp, pops
previously saved registers, and returns.”

Next, we observe trap.c again. Note particularly the switch case in which the trap number is
equal to T_IRQ0+IRQ_TIMER (ie. trap is a timer event):

The ticks are acquired and incremented, and then wakeup is called in order to wakeup
processes that are sleeping for a specific amount of ticks.

Later in the code:

If a process is running, and there is a timer event, the process yields and awaits its turn to run.
yield() is in proc.c.

The process’ state is set to RUNNABLE, as opposed to RUNNING. sched() is where the context
switch() is called. It switches from the context of p (the process that was just set to a
RUNNABLE process by yield()) to the scheduler. (This is also in proc.c)
The swtch() is handled by swtch.s:
The stack pointers are saved, current registers are pushed onto the stack, stacks are switched,
and the previously saved registers are popped.

Observe the PCB in proc.h:

Note that there is a context variable here for the swtch.

Assignment 3: Some Tips

There are some tips on what edits need to be made in order to add a system call in lectures 11
and 12. Also, here is an article by GeeksForGeeks on how to add a system call. The files you
need to modify for this assignment are:

Makefile
defs.h
proc.c
syscall.c
syscall.h
sysproc.c
user.h
usys.s
And technically pstate.c, but you’re creating this, not modifying it from an existing xv6 file.

The main implementation for your system call will need to be added to proc.c. To have it work
as a command, you will need to create a user program that calls the system call. Some tips for
the actual implementation:
- We need to iterate through the processes in the process table and the currently running
cpus. These are arrays of structs. If you don’t remember how to iterate through an array
of structs, you can see how to do it in proc.c; allocproc() is one example of a function
that does this.
- ncpu is the number of cpus running processes (a variable in proc.c) where NCPU is the
maximum number of cpus supported (a global variable). If you're iterating through the
cpus use the first of the two as your maximum element.
- If you don’t remember how to access members of a struct, see my Assignment 2 tips.
LEC 14 02/28/2023

A practice exercise/review session will be held next lecture for the midterm. The midterm will
include everything from up to this lecture.

On process scheduling…

Honestly, rather than reading this, just read Ch 7 of 3EP. It’s significantly better than the
explanation below and has diagrams.

Assumptions that will be made with our current process scheduling design:
1. Each job runs the same amount of time
2. All jobs arrive at the same time
3. Once started, each runs to completion
4. All jobs are computation only
5. Runtime of each job is known

Note that most of the time these expectations/assumptions are unrealistic. These assumptions
only exist in order to simplify our design.

If a timer event triggers an interrupt, which waiting process do we switch to? → First ensure
that the process is a RUNNABLE state (property given in PCB). The scheduler will
handle the context switch; it will choose the next process to run and switch to.

The scheduler can run according to different policies. One that is implemented in xv6 is… going
to be examined after the midterm.

In deciding and designing these policies, we consider certain metrics. These include:
- Turnaround time: Completion time - arrival time; the amount of time it takes to complete
a process.
- Response time: Time first run - arrival time; the amount of time it takes for a process to
be started.

Given a process A, B, and C:

A, B, and C are all runnable processes ready to be scheduled (A has arrived first, B second, C
third). A runs to completion, taking 10 seconds. B then runs to completion, taking another 10
seconds. C then runs to completion taking 10 seconds. (*Note that process run time is not
always measured in seconds, we are just using this in order to model our process runtimes
intuitively*)

Measuring these processes by turnaround time: A takes 10 seconds, B takes 20 seconds, C

takes 30 seconds (this is assuming that A, B, and C have all arrived at around the same time,
within a second). The average turnaround time for running these processes is therefore 20
seconds.

What if we remove the assumption that all processes take the same amount of time? Say A has
a run time of 100 seconds, where B and C’s run times remain the same. In terms of turnaround
time, A will take 100 seconds, B 110 seconds, and C 120 seconds; the average turnaround time
is 110 seconds in this case. Processes that take a shorter amount of time have to wait a long
time in order to be completed-- this means that in this case, a first-come first-served process
scheduling model may not be the best option.

This brings us to the first policy: SJF, or Shortest Job First. This policy involves prioritizing the
shortest job/process in order to reduce the amount of time that processes must wait in order to
run as much as possible.

Consider the processes A, B, C again in the same order, with A’s runtime being 100 seconds, B
being 10, C being 10, and now with the SJF policy for process selection. B runs first and has a
turnaround time of 10s, then C for a turnaround time of 20s, and A for a turnaround time of
120s; the average turnaround time is significantly reduced with the introduction of this policy
(from 110s with a first-come first-serve model to 50s with an SJF model).

Now, let us consider what happens if the processes do not all arrive to be scheduled at the
same time. Given a process A, B, C, A with a completion time of 100s, B with 10s, C with 10s. A
arrives first, followed by B and C 10s later.

In this case, A will inevitably be scheduled first. Also, due to our assumptions earlier, A must run
to completion. So the turnaround time of A will be 100s, B will be 100s (110 - 10), and C will be
110s (120 - 10); the average turnaround time will be 103s.

But we can make this more efficient. Consider removing assumption 3; what if we stop process
A partway through its completion? The turnaround time of B and C will be shorter in this case.
Considering the previous scenario, now pausing A once processes B, C arrive and switching to
them: A runs for 10s, B is switched to and run for 10s to completion, C is switched to and run for
10s to completion, and then A is run for another 90s to completion. So the turnaround times for
A, B, C respectively are: 120s, 10s, 20s. The average turnaround time is reduced to 50s.

Given this model, we should now make use of a different policy: STCF, or Shortest Time to
Completion First. This selects the process with the shortest amount of time to be completed to
run first.

What if we measure the previous scenario under a different metric? Recall that response time is
measured as the difference between the time that a process starts running and its arrival time.
A’s response time is 0s, B’s response time is 0s, and C’s response time is 10s. The average
response time is 3.3s-- what if we want to optimize this metric instead?
Consider a different scenario. A, B, and C run in 10, 20, and 30 seconds respectively, all with
the same arrival time. A will be scheduled first, run for 10s, then B will run for 20s, and then C
will run for 30s. This illustrates another instance in which turnaround time is good but response
time is poor.

In order to optimize response time, we will use a different policy: Round Robin, or RR. In this
policy, each process is allotted a set amount of time, and then another process is selected to
run, again for a set amount of time. Essentially, the processes “take turns”.

Given processes A, B, C, with runtimes of 5s for all, and the same arrival time for all:
SJF yields turnaround times: 5s, 10s, 15s for an average of 10s, and response times: 0s, 5s,
10s for an average of 5s.
STCF yields the same turnaround and response times as SJF in this scenario.
Round Robin with an allotted time of 1s/round yields turnaround times: 13s, 14s, 15s for an
average of 14s, and response times: 0s, 1s, 2s for an average of 1s.
Considering the response time metric, then, in this case, Round Robin is more efficient.

Now let us remove another of our assumptions, assumption 4. What if a process needs access
to I/O?

Consider this process scheduling scenario. A and B both arrive at the same time, with running
times of 50s. However, A needs to make use of I/O after every 10s of its run time. I/O involves
accessing the disk, which takes time in order to process requests itself (note that in general the
disk is slow). For this example, assume A’s access to the disk each time takes 10s.
In this case, A runs for 10s, then accesses the disk in order to do I/O. The CPU here will wait for
A to finish I/O before continuing to run it. So the turnaround time of A in this scenario will be 90s,
and B will be 140s. In order to reduce the turnaround time, when A is accessing the disk, we
should run process B. A’s turnaround time will remain the same, but in this case, B’s turnaround
time will be reduced to 100s.

For a more detailed explanation with diagrams, see 3EP chapter 7.

In xv6, we will examine the scheduler, which handles process scheduling.

MIDTERM INFO!! LEC 15 03/02/2023

On Assignment 3: If you type pstate, it should call the program pstate.c. Inside this program, the
system call is called (and the program is exited); there is no other code in pstate.c. The system
call has an ID and is implemented in proc.c; in this file, cprintf will be used to print to the
console.

In completing Assignment 3, you should have observed the proc structure (the PCB).
Scheduling involves performing a context switch to processes that are in a RUNNABLE state.
This context switch is performed in trap, and the process selected to run is determined by the
scheduler. Say there is a process A with state RUNNING, and a process B with a state
RUNNABLE (also referred to as ready state, in 3EP). Upon the context switch, A’s state (in its
proc structure/PCB) will be changed to RUNNABLE. The context switch will pass control over to
the scheduler, changing the program counter to do so; the scheduler facilitates the change to
process B, changing program counter again in the process. The process B’s state will be set to
RUNNING. So, there are two context switches that occur: from process A to the scheduler, then
from the scheduler to process B. Note that multiple CPUs may be running the scheduler at the
same time. We will be going over the code for this in more detail during the next lecture.

Midterm Info:

There will be seating info for the midterm posted on Saturday; note in particular that there are
two rooms. The room in which we usually have class is Toldo 200, whereas the class across
from it is Toldo 202.

The midterm will cover chapters 1-7 of 3EP. For those using the extra content linked as study
material, the first 6 OSLAB slidesets are relevant, the first 2 weeks of OSLAB videos are
relevant, the first 4 HexHive OSTEP slides are relevant.

The format will be multiple choice (30) and fill in the blanks (15-20). No coding (though filling
in the blanks may involve code). There will be a part A, B, and C; multiple choice with single
answers, multiple choice with multiple answers, and fill in the blanks.

Multiple choice with single vs. multiple? → Single will always have 1 correct
answer. Multiple will have at least 0 correct answers. Part marks will be given on
multiple.

The number of points each question is worth will not be indicated. The weighting will be
determined after the midterms are graded, in order to curve the class.

The FITB will mostly be definitions. Eg. I have a proc A, B, both are running at time 0, A takes
a certain amt of time; under SJF what is the average turnaround time?

FITB will involve code. You will need to fill in the blanks to suit Chen’s definition of how code
will work. Multiple choice may also involve code.

For those wishing for study resources, there are various resources linked at the beginning and
end of this document.

Also useful for the midterm, my summary of various xv6 files:

Notes on Various Programs in xv6:

Echo.c: User level. Does pretty much what you’d expect, reads the command line argument
and prints it.

Cat.c: User level. Again this basically works as expected; opens the file associated with the
cmd line argument and prints its contents. Notably, cat is buffered.

Init.c: User level, code for the first process. Opens the console for reading and writing, then
dup()s the console’s file descriptor (0) in order to create the stdout (FD 1) and stderr (FD 2)
streams (0 is stdin). In an infinite loop, it forks to a child process, exec()s to replace the child
process with sh.c, and wait()s for it. Because it loops infinitely, it ensures that the shell is
reopened if it is closed.

Sh.c: User level. Ensures that FDs 0, 1, and 2 are open. Reads from stdin. Forks to a child
process, and if the command is valid, exec()s to a process based on user input. (Note: for the
cd command, the shell itself does not fork to a child process, it system calls chdir().)

Exec.c: Kernel-level (exec is a system call). Gets the current process using myproc(),
prepares its stack, and reassigns its proc struct members (of particular note is the
reassignment of the instruction pointer eip in the process’ trap frame, and the stack pointer in
the process’ trap frame)

Proc.h: Header that contains important info for processes. Contains the cpu struct, the array
of cpus, the context struct (ie the registers saved upon context switch), an enum for process
states procstate (UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE), and of
course the proc struct, which contains PID, kernel stack ptr, process state, parent process,
trap frame, context, open files, and current directory, among other things of note (that we
haven’t covered yet).

Traps.h: Trap numbers for various trap events, notably system call is trap number 64, timer is
trap number 32.

X86.h: Lot of things here, but notably it contains the trapframe struct, which has the registers
pushed on context switch.

Proc.c: Kernel-level. Notably contains the ptable (process table) struct. Has
- allocproc(), which finds an unused proc in the ptable for use
- fork(), which allocates a new process (with allocproc()) and copies its state over and
changes some of its parameters in order to create a child process
- exit(), which closes all open files relating to the process, wakes up its parent if it is
sleeping, passes any of the process’ children to init, and sets the exit()ed process’
state to ZOMBIE
 - wait(), which sleep()s to wait for children; if any children are in ZOMBIE state, frees up
their memory/stack and marks their spot in the ptable as UNUSED/usable.
- scheduler(), which calls swtch() to do a context switch to a chosen/scheduled process
- sleep(), which makes a process sleep and updates its status to SLEEPING
- wakeup1()/wakeup(), which wake up a process
- kill(), which kills a process
Essentially, proc.c contains the implementation for various process-related system calls; as a
general rule anything that needs access to the ptable is contained here.

Sysproc.c: Kernel level. Contains implementation of various process-related system calls,

many of which call functions in proc.c. Also contains sys_getpid(), sys_uptime()

Sysfile.c: Kernel level. Contains implementation of various system calls relating to file
processing, including sys_open(), sys close(), sys_read(), sys_write()

Printf.c: User level. Contains the implementation of printf. Parses a given string, prints it to
the given file descriptor by system calling write(). Note that it calls write for each individual
character (unbuffered)

Trap.c: Kernel level. Handles various trap events, based on the trap number (obtained from
the passed-in trap frame; recall this is part of a PCB/process struct). In particular, on a system
call, checks if the system call number is valid and runs the system call if so.

Trapasm.s: Kernel level. Where trap frame parameters are pushed to the kernel stack. Also
calls trap().

Swtch.s: Kernel level. Saves old registers, loads new ones. (ie performs a context switch)

Defs.h: Contains various structs and function “definitions”. In particular contains the header
functions for system calls.

User.h: Contains the function headers for the user-level versions of system calls.

Syscall.c: Kernel level. Gets the syscall number from the trapframe’s eax register, and runs
the syscall associated with that number. Trap() ensures that the syscall is valid first (trap
verifies validity, then calls syscall()). Also contains global function headers for all syscalls.

Syscall.h: List of system call numbers, there are 21 of them (indexed from 1).

Usys.s: Kernel level. The assembly code for a system call. Moves the syscall name into eax,
and interrupts with the trap number for system call.

Makefile: Not really something that needs to be understood so much as manipulated. To add
 a new user program, add the program to UPROGS (command line argument), add the file
name to EXTRA. To add a new user library, add the library name with extension .o to ULIB,
and the file name to EXTRA.

We observed syscall.c:

The syscall number is obtained from register eax; if this number is a valid system call number,
then syscalls[num](); (ie the return value of the system call) is saved into eax.

Inserting 1 print statement for each system call (in syscall.c; directly before the if statement in
the code above), upon starting xv6: Syscall 7 is called once (exec), syscall 15 (open) is called
once, syscall 10 (dup) is called twice, syscall 16 (write) is called… a lot, syscall 1 (fork) is called,
syscall 3 (wait) is called, syscall 7 (exec) is called. Then by sh syscall 15 is called, then syscall
21, (note that these are all listed in order). Also, each print statement prints the name of the
process running the system call. The first name is init code, where the following calls all have
name init.

Looking at the code for init, we can see where the syscall to 15 (open) and the syscalls to 10
(dup) are made. open is used to open the console for reading/writing; dup is used to assign file
descriptors for stdout/stderr; the dup(0) is because the fd 0 is assigned to the console. Basically,
it duplicates the file descriptor that points to the console twice, once for stdout, again for stderr.

The calls to write are performed by the function calls to printf. Then, we can see where syscall 1
is called (fork). The parent will then call syscall 3 (wait), and the child proc created from fork
calls syscall 7 (exec).

Inside the code for exec in the kernel, every single time a process is loaded into memory it
prepares the stack. sh.c calls open, which we can see among the printed syscalls. The shell
code parses the command typed into the shell, then forks to a child process to run the
command if it is valid, and wait()s.

LEC 16 03/07/2023

Given a set of processes with burst times (time for which a process occupies a CPU to
complete) and printing values as below:
Process Burst time Priority value

p0 10 3

p1 1 1

p2 2 4

p3 1 5

p4 5 2

How do we determine the priority of their scheduling? → In SJF (shortest job first), the
inverse of the process’ completion time is its priority (that is to say, processes with
less completion time have higher priority). However, there are other ways to
measure and determine priority.

Priority can be also be defined by external factors. More important processes could be
scheduled to run first. Another example is when processing time is being paid for; if a user pays
more to use a CPU then their process may be prioritized.

There are also internal factors, such as burst time.

Which of the above processes will be scheduled first? → Job p1. It has a higher priority (a
lower priority value corresponds to a higher priority; the 1st highest priority process
has priority 1.) p1 will be followed by p4, followed by p0, followed by p2, followed by
p3.
Priority scheduling can be done preemptively or non-preemptively. Preemptive scheduling
involves interrupting processes in order to ensure that highest priority processes are running
first, whereas in non-preemptive scheduling the processes are never interrupted.

Process Burst time Priority value

p0 4 3

p1 5 2

p2 8 2

p3 7 1

p4 3 3
Consider the above processes with priority and Round Robin scheduling. Suppose the quantum
time (Round Robin time slice/allotted running time) is 2s. Also note that processes with the
same priority will “take turns” in this scheduling format.

p3 runs for 7s, p1 runs for 2s, p2 runs for 2s, p1 runs for 2s, p2 runs for 2s, p1 runs for 1s, p2
runs for 4s, p0 runs for 2s, p4 runs for 2s, p0 runs for 2s, p4 runs for 1s.

Starvation: What if a process has a very low priority? It may never be scheduled, or be allotted
very little of the process time (since higher-priority processes that arrive to the scheduler will be
scheduled first). This means that the low-priority process will be starved.
Aging: A concept introduced in order to prevent starvation. As processes wait to be scheduled,
aging makes their priority increase. This way, it is less likely that they will be starved for CPU
time.

Another source on starvation, aging, and priority scheduling with examples:

[Link]
%20Starvation%20occurs%20in%20Priority,the%20process%20will%20be%20executed.

A4: Implement preemptive priority scheduling with RR. We also need to make 2 sys calls for
testing, one is a modified ps (pstate that displays priority values) and set (modifies the priority of
a given process by pid). We will also need to provide a user program that is used to test the
scheduling.

In running her sample solution, she runs a few processes in the background; all processes are
assigned a 0 priority as default (Note that the default priority in the assignment is not defined,
and we can alter this as we wish). Running ps throughout the running of the background
processes demonstrates the processes “taking turns” through RR scheduling. She then set s
one of the processes to have a priority of 1 (greater priority = scheduled later), and running ps
demonstrates that this process gets taken out of the RR rotation (until the other processes are
finished).

We looked at trap.c to observe what happens on a timer event.

Notice that yield() is called, which is contained in proc.c. Observing proc.c, sched calls swtch,
which takes the context of the current process and switches to the scheduler’s context.
The scheduler finds a runnable process in the ptable, calls switchuvm(p) on it (switches page
table), and switches from the scheduler’s context to that process’ context. The scheduler loops
infinitely as it is constantly scheduling processes while it is running.

LEC 17 03/09/2023

A4 drawbacks: Starvation. To circumvent this, aging could be implemented (see last lecture). All
scheduling policies have some sort of drawback; optimizing turnaround time may come with a
cost to response time. Many of the policies that we have worked with so far come with the
assumption that we know their burst/computation time, where that is not always realistic.
Finding the computation time can be CPU-intensive.

Multi-Level Feedback Queue: Algorithm used for scheduling, to predict computation time.
We don’t know the computation time, and we want to achieve something close to SJF.
Therefore, assume all jobs are short initially, and assign them high priority; as the process
spends more time running, lower its priority.

For a better definition, see 3EP Ch 8:

MLFQ is often used in real operating systems.

Rules of MLFQ:
- Rule 1: If priority value of A < priority value of B, then A is more important and should be
run. (Recall that lower priority value corresponds to higher priority)
- Rule 2: If the priority values of A and B are equal, schedule them Round-Robin.
- Rule 3: Newcomers are assumed to have highest priority.
- Rule 4(a): If a process used an entire Round-Robin timeslice (quantum) and does not
finish, drop its priority by 1 level.
- Rule 4(b): However, if the process somehow gives up the CPU before the timeslice is
completed (usually happens when the process utilizes I/O), the process’ priority will not
drop.
- Rule 5: After some time period S, move all the jobs in the system to the topmost queue
(ie. aging).
A diagram from 3EP showing a process’ position in MLFQ/priority value over time. Note that in
this example, a lower priority value (Q0) corresponds to a lower priority.

This diagram, however, only considers a single process. What happens when we introduce a
new process to the queue? Again from 3EP Ch 8:
 “A (shown in black) is running along in the lowest-priority queue (as would any long-running
CPUintensive jobs); B (shown in gray) arrives at time T = 100, and thus is inserted into the
highest queue; as its run-time is short (only 20 ms), B completes before reaching the bottom
queue, in two time slices; then A resumes running (at low priority).”

What about an example with I/O?

“As Rule 4b states above, if a process gives up the processor before using up its time slice,
we keep it at the same priority level. The intent of this rule is simple: if an interactive job, for
example, is doing a lot of I/O (say by waiting for user input from the keyboard or mouse), it will
relinquish the CPU before its time slice is complete; in such case, we don’t wish to penalize
the job and thus simply keep it at the same level. Figure 8.4 shows an example of how this
works, with an interactive job B (shown in gray) that needs the CPU only for 1 ms before
performing an I/O competing for the CPU with a long-running batch job A (shown in black).
The MLFQ approach keeps B at the highest priority because B keeps releasing the CPU; if B
is an interactive job, MLFQ further achieves its goal of running interactive jobs quickly.”

What happens when we consider Rule 5 (aging) as well?

 “In this scenario, we just show the behavior of a long-running job when competing for the
CPU with two short-running interactive jobs. Two graphs are shown in Figure 8.5. On the left,
there is no priority boost, and thus the long-running job gets starved once the two short jobs
arrive; on the right, there is a priority boost every 50 ms (which is likely too small of a value,
but used here for the example), and thus we at least guarantee that the long-running job will
make some progress, getting boosted to the highest priority every 50 ms and thus getting to
run periodically.”

In Rule 5, we mention a time period S. How long should this time period be? A longer time
period works best for shorter, high-priority processes, where a shorter time period works best for
longer, lower-priority processes. There’s not really a clear-cut answer to what S should be. From
3EP:
“Of course, the addition of the time period S leads to the obvious question: what should S be
set to? John Ousterhout, a well-regarded systems researcher [O11], used to call such values
in systems voo-doo constants, because they seemed to require some form of black magic to
set them correctly. Unfortunately, S has that flavor. If it is set too high, long-running jobs could
starve; too low, and interactive jobs may not get a proper share of the CPU.”
Another thing that must be considered is how many different priority levels should be
implemented. This is again subjective and a matter of design.

More on A4: For a3 we made a syscall with no argument. How do we handle arguments in a
system call? Examining user.h, we can see that there are syscalls that have arguments, such as
exec. But at a kernel level, these arguments are not provided (see syscall.c, all of the functions
are void). So how do we obtain these arguments? They are contained within the user stack for
the program. So we need to access this in order to obtain our arguments for set(). Upon a trap(),
the stack pointer (esp) for the user process is saved to the kernel stack. How do we access
this? Observe argint in syscall.c.
This function obtains an argument from the trapframe of the currently running process (it uses
fetchint() to do so, also in syscall.c). To see examples of a call to argint, see sysproc.c and
sysfile.c.

LEC 18 03/14/2023

On memory: Recall mem.c , which demonstrates the virtualization of memory. Why is memory
set up in this way?

Time sharing? → Using CPU scheduling and multi-programming to provide each user with a
small portion of a shared computer at once.

One representation of time sharing, from 3EP Ch 13:

“One way to implement time sharing would be to run one process for a short while, giving it
full access to all memory (Figure 13.1), then stop it, save all of its state to some kind of disk
(including all of physical memory), load some other process’s state, run it for a while, and thus
implement some kind of crude sharing of the machine [M+63].”

This method of implementing time sharing is quite slow, however. So, in modern operating
systems, each process is allotted a share of the memory, as in the diagram below.
What difficulties emerge with this model? → The address space (that is, the block of
memory allocated for each process) of each process must be tracked and
maintained. Protection is also a matter of concern, as we do not want processes
accessing the address space of a different process.

Now let’s examine more closely an example of a process’ address space.

Code and data are stored at the “top” or beginning of the address space, since their sizes are
static; the heap and stack are placed at separate ends, so they both can be expanded toward
the middle of the address space. (For a more detailed description, see 3EP Ch 13). Also
observe a similar diagram from the xv6 text:

Effectively, this model achieves the same thing as the 3EP model. Note however, that some of
the positions of various items in memory are different (ie. OS at the end of address space, heap
and stack positions are swapped). In referencing how xv6 address space operates, you should
reference the xv6 book, not 3EP.

Address space? → Physical memory that is abstracted to allow for ease of use. The
running program’s view of memory in the system.

This is detailed in Ch 15 of 3EP.

Given a function:
void f() {
...
int x = 3000;
x = x + 3;
...
}

This code will be converted to assembly code by the compiler. The assembly conversion of this
code looks something like this:
128: movl 0x0(%ebx), %eax ;load 0+ebx into eax
132: addl $0x03, %eax ;add 3 to eax register
 135: movl %eax, 0x0(%ebx) ;store eax back to mem

What memory accesses are done to achieve this process? → Assume that the location of x
in the process’ stack is at 15KB (as in the diagram below).
• Fetch instruction at address 128
• Execute this instruction (load from address 15 KB)
• Fetch instruction at address 132
• Execute this instruction (ie. do addition; no memory reference)
• Fetch the instruction at address 135
• Execute this instruction (store to address 15 KB)
This means that there are 6 memory accesses done in order to complete the reassignment of x.

So, with respect to the process’ address space, the memory would look something like this:

The process, however, will not actually be stored at the position of 0kb in memory (just at 0kb
from the process’ perspective). How do we map this process’ address space?

1. Software Solution (Static Relocation)

This solution involves a piece of software called a loader, which takes an executable that is
about to be run and rewrites its addresses to the desired offset in physical memory. This is a
dated solution to the address mapping problem, and it has many drawbacks; it makes protection
and relocation of processes difficult. For more see 3EP Ch 15, pg 6.
 2. Dynamic Relocation (Hardware Solution)
In this solution, each CPU makes use of two registers: A base register and a bounds register.
The base register represents the beginning of a virtual address space, while the bounds register
represents its end. The physical address of something in a process’ memory will be equal to the
value of the base register + the virtual address. The bounds register is used in order to achieve
protection; if a process tries to access memory beyond its bounds, then the CPU will raise an
exception.

Suppose we have an address space 4kb in size, loaded at physical address 16kb. The
addresses will be translated as such:

How do we get 19384? → 16kb + 3000. 16 kb=16 ×210 =16 ×1024=16384.

How does the OS track which parts of the memory are free for use? → A data structure
called the free list. This is a list of the ranges in physical memory which are not in
use.

For a general summary of the requirements of dynamic relocation:

What happens upon a context switch? → There is only one base/bounds pair for a CPU.
So, upon a context switch, the base/bounds of the context being switched from
must be saved, and the base/bounds of the context being switched to must be
restored. These bases/boundses are saved in the PCB.

More on assignment 4: Consider argint in syscall.c.

This function obtains an argument from the trapframe of the currently running process (it uses
fetchint() to do so, also in syscall.c). Essentially, it fetches an argument from outside the kernel
when in kernel mode. An example of a call to argint is in sysproc.c, in the implementation of
sys_sleep().

Assignment 4: Some Tips

For this assignment, we need to implement priority scheduling (xv6 already uses a round robin
scheduling model). I used my Assignment 3 as a base, as we need to use pstate for this
assignment. If you didn’t finish Assignment 3, you can either see my notes above on how to
complete it, or message me on Discord and I’ll help you out.

The first thing we need to do is assign every single process a priority. We need a variable for
each process that tracks it. We also need to assign each process a default priority when it is first
allocated (upon allocproc()), and reset its priority to that default priority when it is cleaned up
(upon wait()). To achieve these things, you’ll need to edit proc.h and proc.c.

Next we need to implement set(). We have already implemented a system call in A3 for pstate,
so the steps for doing this are similar. That is to say, we need to edit: defs.h, proc.c, syscall.c,
syscall.h, sysproc.c, user.h, usys.s. Set differs from pstate in that it needs to take arguments, so
the function headers in these files will be different. On the implementation side, providing
arguments to set() involves doing something in sysproc.c that we didn’t do for A3. In previous
lectures we were told to compare with the implemented of sys_sleep and sleep in sysproc.c and
proc.c specifically, but I personally found looking at sys_exec and exec (in sysfile.c and exec.c
respectively) a little closer to what we’re implementing (exec has 2 arguments, the call to exec
in sys_exec passes in these 2 arguments). Look at both, and look at argint in syscall.c to work
out how to pass in the arguments. Also, remember that these arguments are passed in from the
command line, so you’ll need to implement that in the set.c program as well.

We also need to implement the scheduling itself. For this, we just need to ensure that the
process in the process table with the highest priority is selected to run. We can see in the
scheduler (in proc.c) where the runnable processes are looped through to select a process to
run, so this is where we should find the process with the highest priority and select it.

Finally, we need to write a tester program. This should be fairly trivial, just try to make a
program that runs for a very long time without calling sleep() (for example, looping a very high
number of times). Remember that both the tester and set are user programs and will need to be
added to the Makefile. Note: If you’re using WSL to test you might have some difficulty, seeing
as WSL will only virtualize 1 CPU for use. If you want to test your scheduling, try running on the
school servers.

LEC 19 03/16/2023

More on address spaces/memory virtualization today. We spent most of our time on 3EP Ch 16.

Virtual address space on left, physical address on right. The virtual address space is mapped
with aid of a base register and a bounds register.

What if we have a program that takes a small amount of space? Standardly, a 32-bit address
space is used; this works out to 4GB of address space for a single process. If a program is 5MB
in size, then a large amount of space may be wasted. How do we circumvent this?
We can assign the size of the address space dynamically. This sizing is called segmentation. It
involves having a base and bounds for each portion of an address space; so a base and bounds
for the code, a base and bounds for the heap, and a base and bounds for the stack. This allows
the OS to map each part of an address space to a different spot in physical memory, and makes
it easier to avoid having excessive space allocated to a single process. See this diagram from
3EP Ch 16:

Its bases and bounds for each segment of the address space will be:

Note: Size here is the same as bounds, since a segment will extend to the end of its size.

Consider: The address space defined as below, and its physical representation as defined in
Fig. 16.2 above.
How do we reference virtual addresses in these segments?
1. Reference address 100 in code segment: 32KB + 100
This calculation is simply the address + the code segment’s base.
2. Reference address 4200 in heap segment: 34KB + (4200 - 4KB)
This calculation is the heap segment’s base + the virtual address - the heap’s offset (see Fig
16.1, in which it is located at 4KB.)

Why is this? → It’s due to how the segments are mapped separately in physical
memory, while being mapped sequentially in the virtual representation. We know
that address 4200 in the virtual address space is contained in the heap. But to find
where it is located physically, since the heap is separated from the rest of the
segments of the virtual address space physically, we need to consider where this
address is relative to the heap itself. In the above diagram, the heap starts at 4KB.
So, the address 4200 is 4200 - 4KB = 104 offset from the beginning of the heap.
The physical location will be equal to the heap’s physical location + this offset.

3. Reference address at 15KB in stack segment: 28KB - (16KB - 15KB)

In considering this, we need to consider in which direction that the stack grows. Since the stack
grows in the negative direction, we subtract from the base rather than adding to it.
Why is this? → Again recall the previous example, in which we had to calculate the
offset from the beginning of the heap. This time we do the same for the stack. There
is one key difference here, however; the stack grows negatively. So the value at
15KB in the virtual address space will be different relative to just the stack. The
stack grows from 16KB, and the address 15KB is distanced 1KB from the stack’s
beginning. The stack also grows negatively in its physical representation, which
begins at 28KB. So, the “distance” of this address will be 1KB from the stack’s
beginning, counted negatively; it will be located at 27KB.

An address space is represented by a segment register. This register has a set amount of bits,
which defines the length of the address space. For example, a 32-bit register will map to a 4GB
address space (232 possible address values). So, considering a specific segment register value,
how do we obtain what segment and offset in said segment that this value refers to?

Consider our example above. Since we have a virtual address space size of 16KB, we will be
using a 14-bit segment register (214=16 KB ). We have 3 segments (practically, we can have
more; eg. a data segment), and therefore we will let the first 2 bits in the register represent the
segment (we need at least 3 possible different values; we need 2 bits to allow for this). See an
example of the 14-bit array of values (address) below:

How do we reference various virtual addresses with this segment register? Consider the virtual
address 100 as before. The segment register representation would be:
00 0000 0110 0100

00 here represents the segment number, where 0000 0110 0100 represents the offset. (000
0110 0100 in binary = 100).

Now what if we consider something contained within the heap segment? Recall example 4200
from last time.
01 0000 0100 1000

Again, the first two bits here, that is, 01, where the offset is 0000 0100 0100. Calculating the
address involves adding the first two bits to the offset.

More on A4: A variable needs to be introduced to the kernel in order to set the priority. This
goes into the PCB. We need to set a default priority and do cleanup later on. Where do we put
this? (allocproc()). This is where an unused PCB is found for a new process being created. We
also need to reset the priority upon cleanup. This is done by the parent in wait(). You actually
don’t need to do this but your mark will be reduced if you don’t.
LEC 20 03/21/2023
Why do we introduce segmentation? → To optimize space. For more detail, see the
above lecture. Each segment of a process’ PCB has their own base and bounds, and
are stored at their own location in memory. Each process has a variable size.

This segmentation we discussed, however, is not how space is mapped in a standard laptop.
What improvements need to be made on this model?

From Ch. 16 3EP:

“The last, and perhaps most important, issue is managing free space in physical memory.
When a new address space is created, the OS has to be able to find space in physical
memory for its segments. Previously, we assumed that each address space was the same
size, and thus physical memory could be thought of as a bunch of slots where processes
would fit in. Now, we have a number of segments per process, and each segment might be a
different size. The general problem that arises is that physical memory quickly becomes full of
little holes of free space, making it difficult to allocate new segments, or to grow existing ones.
We call this problem external fragmentation [R69]; see Figure 16.6 (left).”

We solve this problem of free space, or external fragmentation, by compaction.

Compaction? → Rearrangement of data segments so that memory is used

contiguously; that is to say, there are little gaps/open spaces between memory that
is in use. See the diagram below. Compaction comes with the setback of being
rather expensive. Why? → Rearrangement involves copying segments over to a
different location, which is a lengthy operation.
As such, compaction in this way is not standardly used in operating systems.

How do we achieve compaction, but without the expensive rearrangement costs? → Paging.
Divide a process’ address space into fixed-sized units, called pages. This way, memory can be
viewed as an array of slots of equal size, or page frames. Note that larger portions of data can
use multiple pages in memory. This is the approach used in real operating systems.

Observe below a diagram from 3EP Ch 18, where a 64 byte address space is split into pages
16 bytes in size.

How does address translation work in this model? → Consider an operation:

movl 21 %eax
Also consider the address space as defined above; that is to say, a 64-byte address space. This
means that the virtual address will be 6 bits in length, as 26=64. Also note that the page size is
16 bytes, and 64/16 = 4. Therefore, we need 4 virtual page numbers, or VPNs. So, to
represent the page number, we will need 2 bits (22=4 ). Now, converting 21 to binary, we get:
01 0101. The first two bits here are the virtual page number, and the following 4 are the offset.

So, 21 would be located at page 1 of the address space, at offset 5. Note that page 1 does not
necessarily correlate to the first page frame in physical memory; this is only the virtual page
address.

What would the physical address of this virtual address be? → Consider physical memory as
defined in the diagram below.

As mentioned previously, this address is contained in page 1 of the address space, offset 5
bytes from the beginning of this address space (or AS for short). From the diagram above, we
can see that page 1 of the AS has been mapped to page frame 7, which is located at 112 bytes
in memory. Since our data is offset 5 bytes from this page 1, it would be located offset 5 bytes
from page frame 7 in physical memory; so its position in memory would be at 117 bytes. Note
that our physical address is 7 bits in length (27=128 ; we have 128 bytes of memory in the
diagram above). Our physical address will be 117 in binary, or 111 0101. In particular note that
the offset portion of the physical address is the same as that of the virtual address.
One problem that occurs with page tables is that, in contrast with maintaining a base and
bounds as with segmentation, page tables are quite large. Considering a 32-bit address space
with pages 4KB in size: The virtual page numbers will be 20 bits in length, where the offsets will
be 12. This means that for each translation from VPN to physical address, 220 translations are
required, per-process. This quickly consumes memory; we would need 4MB for each page table
in this case, assuming that 4 bytes of memory are needed for a single page table entry
20
( 4 ×2 =4 MB). If you were to run 100 processes under this model, you would use 400MB on
address translations alone. To avoid this cost, instead of being stored in hardware, the page
tables for each process are stored in their own memory.

One possible representation of a page table is by an array (which maps virtual addresses to
physical addresses). This representation is called a linear page table. The array is indexed by
virtual page number; the page table entries contain the physical frame number. See below (note
that physical frame number is abbreviated to PFN):

Note also in the diagram that there are various other bits labeled.
What are their functions? → A present bit (P; bit 0) indicates whether the page is on
physical memory or on disk, the read/write (R/W; bit 1) indicates whether a page
can be written to, a user supervisor bit (U/S; bit 2) indicates whether or not a page
can be accessed by a user process, an access bit (A; bit 5) that indicates whether or
not a page has been accessed previously, a dirty bit (D; bit 6) that indicates
whether the page has been modified previously, and some bits for data relating to
hardware caching (G, PAT, PCD, PWT).

Recall the scheduler function in proc.c, which contains the scheduler:

void
 scheduler(void)
{
...
for(;;){
...
acquire(&[Link]);
for(p = [Link]; p < &[Link][NPROC]; p++){
...
switchuvm(p);
p->state = RUNNING;

swtch(&(c->scheduler), p->context);
switchkvm();
...
}
...
}
}

In particular note switchuvm(), which we ignored previously. This call handles changing of the
page table of the process. Later, switchkvm() changes the page table to that of the scheduler
(?).

Consider again:
movl 21 %eax
How many memory accesses do we need to achieve this? → The instruction must be
fetched, then the value from 21 must be loaded into eax. So…
- Memory must be accessed once to get the above instruction’s location
- Another access to access the instruction itself
- Another access to page table entry (to translate 21 to physical address)
- Another access in order to fetch data from physical address

Wow, that’s a lot of memory accesses. If only there was a way to simplify this somehow.

Next we will consider Chapter 19, which concerns translation lookaside buffers, or in plain
terms, hardware caching. (We didn’t end up doing this.)

LEC 21 03/23/2023

Last lecture we discussed page tables. Consider a 32 bit address space and a 4KB page size.
How large is the page table (in terms of bytes?) → 232 bytes is the size of the address space.
The page size is 22 ×210=212. (Note: 1 KB = 210bytes.) So the page table is 232 /212=220 bytes in
size. To find the size of the page table, divide the address space size by the page size. We
have 220 pages, and therefore 220entries in the page table; multiply this by a size of 4 bytes for
4MB.

This is a rather large size for a page table.

How do we reduce this? → One method would be to increase the page size. Take the
previous 32 bit address space, but with a page size of 16KB (16KB = 24 × 210 bytes).
Then the page size will be 232 /214=218. But doing this is antithetical to the purpose of introducing
a page table; this will cause internal fragmentation, that is to say, many pages will contain
wasted space due to being too large. Suppose we have a process with a virtual/address space
sized 8 pages. The first page is allocated to the code, the second for the heap, and the last two
pages for the stack. Only 4 pages have been mapped, yet there are 8 pages in the virtual
space. This will result in wasted space in the page table.

So increasing the page size is not a good approach. Consider a different strategy; what if we
combined the approaches of paging and segmentation? We can track parts of a page table by
their base and bounds, similarly to how the sizes of segments were tracked previously. Instead
of a page table, we have segments of a page table (for code, heap, and stack, among other
things).

This also is not a perfect solution. The variable sized block results in external fragmentation.

External vs Internal fragmentation? → External fragmentation occurs when free space is

split into fragments, and there is not enough space left to store something
contiguously (ie. all in one continuous block of space). Internal fragmentation occurs
when blocks of free space allocated are too large (larger than what they are being
allocated for), and therefore a large amount of space goes unused. The former is
often a result of dividing space into variable-sized blocks, whereas the latter is a
common result of dividing space into fixed-size blocks.

So, we use a fixed size block. Consider a page table. It has one page in use and another page
that is not in use. So the mapping to the entirety of the page in use will be saved, whereas there
will be no mapping assigned to the page not in use. Recall that previously we used a linear
page table; this approach instead uses a multi-level page table, which is similar in structure to a
tree.

To see a representation of a multi-level page table, observe 3EP Ch 20 below:

The page directory tracks valid pages, and only those pages are allocated memory. The linear
page table results in much more wasted space, as you can see in the diagram above.

How do we determine the size of a page table directory? → Consider a 14-bit address
space. Our total size is 214 bytes then, or 16KB. Also consider a page size of 64 bytes. Our
number of entries for a linear page table is 214 /64=214 /26=2 8 entries; assuming an entry is 4
bytes in size, the page table size is 1KB. But this is for a linear page table. What about for a
multi-level page table-- for a page table directory? We have a 1KB size page table, and our
pages are 64 bytes in size. So, the page table itself can be divided into 1KB = 1024 bytes / 64
bytes = 16 pages (each page can hold 16 page table entries). We have 16 pages, and 256 total
page entries. The page directory needs 1 entry per page table, so 16 entries. 16 entries in the
page directory can be represented by 4 bits (as 24 = 16) so:
- The first 4 bits of an address will be the page directory number
- The next 4 bits will be the page table index
- The final 6 bits will be the offset.

Assignment 6: Some Tips

In this assignment we have to do a number of calculations involving page table addressing.
We’ve gone over this a fair amount in class, particularly in the last lecture. Page table
addressing is also covered in 3EP Ch 20. Also, a good video on paging:
[Link]

As we’re working with space as well, this assignment involves a good amount of conversion
between data. For this assignment, note that 1024 bytes = 1KB, 1024 KB = 1MB, etc; we are
using the base-2 representations of bytes/kilobytes/megabytes/gigabytes as opposed to the
decimal representations. Because we are converting between the base-2 representations, every
 unit can be represented neatly by a power of 2. For example: 1 KB = 1024 = 210 bytes (our
smallest unit in this assignment). In particular, it’s helpful to remember that:
10 20 10 30 20 10
2 bytes = 1KB, 2 bytes = 2 KB = 1MB, and 2 bytes = 2 KB = 2 MB = 1GB. The numbers
do get pretty large so you probably are going to want to use a long unsigned int.

Note also that in this assignment 1 bit in the memory address refers to 1 byte of memory, and
that our page table entries are 4 bytes in size (to be confirmed, but the calculations line up with
this value).

There are also a number of values to calculate for this assignment. We’ve discussed them in
classes and in the text, but I think it’s nice to have them all in one place for this.
Number of Pages for a Given Address Space = (¿ Address Space)/(¿ Single Page)

Number of Page Table Entries = Number of Pages for a Given Address Space

¿ Page Table = Number of Page Table Entries × Page Table Entry ¿ ¿

Number of Bits for VPN = lo g 2( Number of Page Table Entries )

Number of Bits for Offset = lo g 2(Page ¿ Bytes)

OR
Total Number of Bits−Number of bits for VPN
Number of Page Table Entries∈a Page Table = ¿ a Page /¿ a Page Table Entry

¿ Page Table = Total Number of Pages × ¿ a Page Table Entry

Number of Pages∈a Page Table = ¿ Page Table/¿ a Page

Number of Bits for Page Directory = lo g 2( Number of Pages ∈a Page Table)

Number of Bits for Page Table Index = lo g 2(Number of Page Table Entries ∈a PageTable )
OR
Number of Bits for VPN −Number of Bits for Page Directory
VPN of a Given Address = First (Number of Bits for VPN )bits of the address

Page Offset of a Given Address = Last (Number of Bits for Offset )bits of the address

Page Directory Index of a Given Address = First (Number of Bits for Page Directory)bits of the address

Page Table Index of a Given Address = The first (Number of Bits for Page Table Index)bits of the address
AFTER
The first (Number of Bits for Page Directory)bits of the address
There, I basically just did the assignment for you. You’re welcome.
LEC 22 03/28/2023

Next lecture will be on concurrency, today will be on devices (Ch 36, 3EP).

In this model the graphics card is relatively distant from the CPU, so using it is a little slow.
Below is a more modern model.
So, we have a number of devices involved in our system. What interfaces do these devices run,
exactly? Next we examine the structure of a generic device.

Each device has 3 different registers. The status register represents whether the device is busy
or not, among other possible device states. The contents of the command register represent a
specific task that a device is to perform. Finally, the data register is used to either pass data to
or get data from the device.

What happens when the OS needs the device to do something? → First, it polls the device; it
checks the device’s status repeatedly until it is available/ready to be used. But polling is not
always efficient; recall the concept of interrupts. This alternative to polling entails that the
device raise an interrupt when it is finished its previously assigned task, when it is once again
available for use. The OS handles the interrupt and receives data from the device, then
continues with whatever process required use of the device. This interrupt-based model allows
for overlap.
In the above diagram, process 1 runs until it needs to make use of the disk. While process 1
makes use of the disk, and the OS awaits an interrupt, it runs process 2. Once process 1 is
done making use of the disk the disk issues an interrupt, and the OS returns to running process
1 again. Compare with a polling-based approach:

While process 1 makes use of the disk, the OS is constantly polling to see when it finishes. So
the OS’s time is wasted, as it could overlap and run a different process while process 1
performs its disk operation.

Another issue that arises in making use of devices (specifically I/O devices) is the amount of
time spent to transfer large amounts of data. Observe the diagram below:

“In the timeline, Process 1 is running and then wishes to write some data to the disk. It then
initiates the I/O, which must copy the data from memory to the device explicitly, one word at a
time (marked c in the diagram). When the copy is complete, the I/O begins on the disk and
the CPU can finally be used for something else.”

In order to resolve this we make use of DMA (Direct Memory Access). This involves making
use of a DMA engine, which is a specialized device that facilitates memory transfer.

“DMA works as follows. To transfer data to the device, for example, the OS would program
the DMA engine by telling it where the data lives in memory, how much data to copy, and
which device to send it to. At that point, the OS is done with the transfer and can proceed with
other work. When the DMA is complete, the DMA controller raises an interrupt, and the OS
thus knows the transfer is complete.”

As a result, in the above diagram, the DMA engine handles the copying, so the CPU can run
another process.
Note that also interrupts are not always the optimal way of handling things. There are also
situations in which polling is advantageous; particularly in which there are a large number of
jobs to be handled.
How does the hardware communicate with the device? → An older method of doing this is
through explicit I/O instructions. This involves the OS directly sending data to device
registers. Compare this with memory mapped I/O, in which the hardware maps parts of its
memory to specific registers, which it can read/write to as desired. Then the hardware routs
these changes to the device itself.

What is a driver? → A driver is a piece of software; it is kernel code that is contained in the OS
that is used to interface/function with a specific device. It is unique to a particular device. It can
be thought of as a translator between the device and the OS.

We then move on to Ch 37 of 3EP. This chapter discusses disk drives. Observe a basic, single-
track disk drive.

The track is the part of the disk on which data is encoded. Most disks contain many tracks on
their surface unlike in the above example. The disk head does the actual reading from/writing to
the disk, whereas the arm is used to position the head at a specific portion of/track on the disk.
Observe another example, this time with 3 tracks..

Say we wish to access disk location 11; then the arm must move to the outermost track (this is
called seeking) and the track must rotate so that the head is positioned above 11’s location.

What other parameters do disks have?

Observe the diagram above. RPM indicates the rotations per minute of a disk; more rotations
facilitate quicker access. The platters are the actual, physical spinning discs in the disk.

Protocols for disk scheduling also exist. The disk scheduler examines disk requests and
decides which ones to schedule first. One way in which this differs from process scheduling is
that the length of time that a single job takes is often known. One example of a disk scheduling
protocol is SSTF or shortest seek time first, in which the OS selects the first job according to
which one has the shortest seek time; that is to say, it selects the job that involves accessing
the location that is closest on the disk in terms of seeking time. That is to say, the OS chooses
to perform an operation on the closest track first.

However, this model entails starvation in the same manner we discussed in previous lectures
about scheduling. The scheduling will prefer staying on a single track rather than moving to
perform accesses that may be required for other jobs on other tracks of the disk. In order to
circumvent this, the arm can sweep (or move across) the disk over time in order to ensure that it
distributes its time evenly across different tracks.

Another protocol for disk scheduling is SPTF, or shortest positioning time first. Which selects
the job with the shortest amount of time to reach its access position (inclusive of both the time it
takes to seek and spin the disk to the desired location).

The disk scheduling can be performed by both the disk and the OS; most often in a modern
design it is performed by the disk itself as it has better knowledge of its own.

Then we went through another page table example.

Take for example, a 14-bit address space and a 64 byte page size. We will also assume that a
page table entry is sized at 4 bytes.

For a linear page table: We have 214 /26=2 8 pages, and 28 page table entries in total. This also
means that we have 26 bits for the offset. The size of the page table is equal to 4 ×28=210 bytes,
or the size of a single page table entry times the number of entries.
What if we have a multi-level page table? We would divide the page table into pages in this
case. Each entry is 4 bytes. Also, our page size is 64 bytes. So, we can contain 64 /4=16
pages in a page. We also have 28 pages; dividing this by our pages-per-page value of 16, we
get 24 . So for the number of pages in the page table directory, we have 24 pages; each of those
pages indexes 24 pages, for a total of 28 pages. This also means that the first 4 bits of the VPN
(and the physical address) will represent the location in the page directory, while the following 4
will represent the page number in a single page of the directory.

LEC 23 03/30/2023

Today we discussed locking. Suppose we have 3 job requests for the disk, and we select a job
using a disk scheduling policy. Let’s say we have a CPU0 and CPU1; then each one can
request a job that requires disk scheduling. Say CPU0’s process A wants to read something
from the disk, and CPU1’s process B wants to read something different from the disk. Say these
requests are stored in a list defined as such:
struct list {
int data;
struct list *next;
}
struct list *list = 0;

And a function insert defined as:

void insert(int data) {
struct list *s;
l = malloc(sizeof(*s));
l → data = data;
l → next = list;
list = l;
}

What happens if both CPU1 and CPU0 call insert? → The main issue here occurs at the
following line of code in insert():
l → next = list;
If both CPUS try to call and run this function at the same time, this line of code will be run first
for CPU0 then for CPU1. So both list elements will have the same next node, which is not good.
Code like this is a common occurrence: Take allocproc() for example. allocproc() contains a
line:
p → pid = nextpid++;
There are 3 steps to the operation above:
a. Load value of x from mem
b. Add
c. Store value of x to mem
In this example, x is comparable to p → pid.
CPU0 does step a, CPU1 does step a, CPU0 does step b, CPU1 does step b, CPU0 does step
c, then CPU1 does step c. Both will attempt to store the value in step c to the same location, but
each will have a different value, so a problem will occur.

We can prevent this by considering the operations a, b, and c as one atomic action; that is to
say, a, b, and c must be done together.

Note that the steps may not necessarily be run in the order as described above. Different orders
can still cause issues (and others may not, but the point here is that we would like to avoid any
errors in this critical section a, b, c of our code).

We resolve this through locking.

How do we implement locking? → In the block of code we wish to keep atomic, we call
acquire(&lockaddress) before the block of code we’d like to keep atomic, then
release(&lockaddress) after the block of code we’d like to keep atomic. See the example below
for the insert() function from the xv6 textbook:

The call to acquire() essentially checks if the passed-in flag is locked or unlocked. Observe the
code below, along with its explanation from the xv6 text:

“Xv6 has two types of locks: spin-locks and sleep-locks. We’ll start with spin-locks. Xv6
represents a spin-lock as a struct spinlock (1501). The important field in the structure is
locked, a word that is zero when the lock is available and non-zero when it is held. Logically,
xv6 should acquire a lock by executing code like the above code.”

With the above code, however, problems can still arise.

“Unfortunately, this implementation does not guarantee mutual exclusion on a multiprocessor.
It could happen that two CPUs simultaneously reach line 25, see that lk- >locked is zero, and
 then both grab the lock by executing line 26. At this point, two different CPUs hold the lock,
which violates the mutual exclusion property. Rather than helping us avoid race conditions,
this implementation of acquire has its own race condition. The problem here is that lines 25
and 26 executed as separate actions. In order for the routine above to be correct, lines 25
and 26 must execute in one atomic (i.e., indivisible) step.”
(From the xv6 text)

Inside the actual implementation of spinlock in xv6 (spinlock.c) there is an instruction called
xchg.
“To execute those two lines atomically, xv6 relies on a special x86 instruction, xchg (0569). In
one atomic operation, xchg swaps a word in memory with the contents of a register. The
function acquire (1574) repeats this xchg instruction in a loop; each iteration atomically reads
lk->locked and sets it to 1 (1581). If the lock is already held, lk->locked will already be 1, so
the xchg returns 1 and the loop continues. If the xchg returns 0, however, acquire has
successfully acquired the lock—locked was 0 and is now 1—so the loop can stop. Once the
lock is acquired, acquire records, for debugging, the CPU and stack trace that acquired the
lock. If a process forgets to release a lock, this information can help to identify the culprit.
These debugging fields are protected by the lock and must only be edited while holding the
lock.”

LEC 24 04/04/2023

More on locking today.

Inside the handler code, there are cases where a lock must be acquired, eg. in the handling of a
timer event. In the code for a timer event, there is a line of code:
tick++;
In the case that 2 different processes make use of that variable at the same time, there are
problems that may be encountered. Thus a lock must be used here.

But there’s another problem that may occur. Say that a process A acquire()s a lock in its
running, call this lock L1. Then process B acquire()s a lock L2 in its running. Then, A needs to
acquire() L2 to proceed before release()ing L1, and B needs to acquire() L1 to proceed before
release()ing L2; this results in a deadlock. The process will block indefinitely as they are both
awaiting each other’s locks to release. In order to avoid this, the order in which locks are
acquired must be specified. From the xv6 text ch 4:
“If a code path through the kernel must hold several locks at the same time, it is important that
all code paths acquire the locks in the same order. If they don’t, there is a risk of deadlock.
Let’s say two code paths in xv6 need locks A and B, but code path 1 acquires locks in the
order A then B, and the other path acquires them in the order B then A. This situation can
result in a deadlock if two threads execute the code paths concurrently. Suppose thread T1
executes code path 1 and acquires lock A, and thread T2 executes code path 2 and acquires
lock B. Next T1 will try to acquire lock B, and T2 will try to acquire lock A. Both acquires will
block indefinitely, because in both cases the other thread holds the needed lock, and won’t
 release it until its acquire returns. To avoid such deadlocks, all code paths must acquire locks
in the same order. The need for a global lock acquisition order means that locks are
effectively part of each function’s specification: callers must invoke functions in a way that
causes locks to be acquired in the agreed-on order.”
Now that we have introduced the concept of deadlocking, we can address how deadlocking can
apply to interrupts specifically as in the above tick++ operation.

Suppose you have a CPU0 with a job list for the disk, with a J1, J2, J3, a J0 currently working
on the disk, and a process A currently working on CPU0. A needs to perform a read() operation.
This calls a trap, and adds this job to the disk job queue. A lock is needed in this scenario (it can
be accessed by multiple CPUs); call this lock L. A at some point will acquire() the lock, and be
added to the list. Suppose that at this point, the job J0 finishes on this disk, and raises an
interrupt. The code for an interrupt also involves accessing the job list (in order to select the next
job in the queue), and therefore also needs to acquire the lock L; but A has already acquired
this lock. This also will result in a deadlock, because the interrupt needs to finish in order for A
to release() its lock L. (The kernel code for A is stopped to handle the interrupt first). Another
better explanation from the xv6 text ch 4:
“Interrupts can cause concurrency even on a single processor: if interrupts are enabled,
kernel code can be stopped at any moment to run an interrupt handler instead. Suppose
iderw held the idelock and then got interrupted to run ideintr. Ideintr would try to lock idelock,
see it was held, and wait for it to be released. In this situation, idelock will never be released
—only iderw can release it, and iderw will not continue running until ideintr returns—so the
processor, and eventually the whole system, will deadlock.”

*Note here that iderw is not an interrupt in this case, where indeintr is an interrupt. iderw is
waiting on the interrupt ideintr, which never returns because it is waiting on the lock acquired
in iderw.

She indicates that we should read ch 4 of the xv6 text on locking. This chapter includes the race
conditions discussed in previous lectures and the deadlocking concepts discussed in this
lecture.

Race condition? → See the previous lecture. A race condition is, by definition in the xv6 text,
an situation in which memory is accessed concurrently by more than 1 process, and at least 1 of
these operations that accesses memory is a write. Essentially, it is code that can go wrong
dependent on what process reaches that line of code first, when 2 processes are running that
code; the “winner of the race” to that line of code is the condition on which that code is
successfully run.

What is a sleep lock? → Sometimes locks need to be acquire()d and held for a long time, for
example, for file system operations. Sleep locks are used to achieve this. They are an
alternative to spinlocks. They allow for a lock to be held while the CPU that acquired a lock has
been yield()ed (while the CPU is made available for another process to use).
EXAM FORMAT: Similar to the midterm. The final is cumulative, and includes all content from
the midterm as well as content after the midterm. Also there probably won’t be 100 questions on
it?

Then, we looked at this cool page table diagram from the xv6 text, ch 2.

It’s a nice picture, right?

Anyway, let’s go over another page table example, for a 32 bit address space.
The last 12 bits of the address are for the offset. This means that the size of a page is
12 10 2
2 =2 bytes× 2 =4 KB. Then, for the index of the page table, we have 20 bits (10 for the page
directory index, 10 for the page table index). So there are 220 pages. In a linear page table this
would be the extent of the calculations. To get the number of page table entries in a single
page, recall: You take the size of a single page, then divide it by the size of a page table entry.
As always, assume that the entry size is 4 bytes. Divide the size of a page by this entry size.
Since we calculated the size of a page as 212 bytes previously: we divide this by the entry size,
for 212 /4=212 /22=210entries. So the number of page table entries per page table is 210. We also
have 220 pages in total. So, to index each of these page tables, we need a unique index for each
page table, such that each page table has 210 pages; we need enough page tables for 220
pages. Then, we divide the total number of pages 220 by the number of pages per page table 210
, for 210 page tables in total. So there are 210 entries in the page directory. To find the size of
either of these, recall that a page table entry is 4 bytes in size. Since both a single page table
and the page directory have 210 page entries, they will each take up
10 10 2
2 × 4 bytes=2 ×2 bytes=4 KB.
As an aside, a useful method for converting from bytes to kilobytes, and any greater
denominations of the bytes metric: Recall that 210 bytes is 1KB. To easily convert from base-2
exponent values of bytes (which we will almost always be using since we are using bits to
represent our space) to KB, simply take the exponent, subtract 10, and put 2 to the power of
that value. For converting from KB to bytes, do the opposite; put the value in terms of a power of
2, then add 10 to the exponent.

Extra Sources:
OSLab Slides with videos: [Link]
For some the above link isn’t working. You can access the YT channel for the videos made from
the slides above here: [Link]
If you want just the slides, I’ve reuploaded some of them here:
[Link]
OSTEP Slides: [Link]
G4G resource (linked is a makefile edit tutorial, but there’s more if you scroll down):
[Link]
JavaTPoint resource (Not entirely relevant to xv6, but good for concepts and has a lot of
examples/diagrams): [Link]
Review by Justin: [Link] video link,
[Link]
edit?usp=sharing document link