CS503 OS HW1 Notes

Compiling and running XINU

After making changes,

cd xinu-fall2017/compile
make clean
make rebuild
make

You can edit remote files on your laptop’s Emacs using Tramp:

/ssh:yourusername@xinu21.cs.purdue.edu:/homes/yourusername/

To run on the backend:

cd ~/xinu-fall2017/compile
cs-console
<C-space>
g (download default image - xinu - and powercycle backend)

Test: Check if you can recompile and reload the xinu without logging off the backend.

Observation: Yes you can! Simply keep the backend connection open while you edit and recompile to your heart’s content. When you’re done, press and g to powercycle.

XINU Explorations

find . -type f -name "*.c" | wc -l

227

find . -type f -name "*.c" | xargs wc -l

...

21868 total

Hmm… That seems pretty small.

Understanding XINU

system/initialize.c: TODO

system/resched.c:

It just looks for the highest priority process and schedules it.

ready

ready() inserts the process into readylist and then reschedules.

Startup

nulluser() sets up the system and then creates the startup() process. After that, nulluser just runs in an infinite loop.

main

pid seems to be 3. How?

When I create a shell, pid 2 seems to be rdsproc. It’s created when initializing devices in sysinit(), which is called by nulluser.

sleepms

It inserts itself in the sleep queue, sets state as sleep, and calls resched.

sleepq - delta list

sleepq is stored as a delta list, where each entry has its key as its delay from its previous entry. The benefit is that you can propagate changes cheaply. So, if you have three processes that need to be woken up in 3, 4, and 6 ms respectively, you will store it as 3, 1, 2. Then, upon each clock tick, you will decrement the first entry alone. And when the first element reaches 0, you can remove it and any elements after it that have 0 (recursively).

clkhandler

It’s called by clkdisp after disabling interrupts. So, when it calls resched, the process won’t get preempted.

ctxsw

I think it restores the interrupt mask (that may have been disabled by clkdisp when calling clkhandler).

resched_cntl

Need to disable interrupts before calling resched or resched_cntl. Otherwise, you may get preempted and rescheduled in the middle of your resched call.

preempt

Assertion that worked (for my test case): processticks == QUANTUM (used full time slice) or processticks = QUANTUM - preempt (voluntarily gave up CPU).

Approach: Rapid Prototyping

Hypothesis: Add one feature at a time, in line with rapid prototyping. You’d have to release - aka run tests - after every feature.

Question: What tests?

Hypothesis: Minimum test - The kernel should type-check, compile, and boot up fine.

Hypothesis: Sufficient test - the ratio of process times for the proportional share scheduler should be in proportion to their priorities. (Add debug code to the scheduler function.)

Observation: This is an integration test, not a unit test. Expensive.

Approach: Documentation and Assertions

Hypothesis: Document each function -> categorize XINU appropriately.

Hypothesis: Use assertions -> can unit test your code.

HW1 - Understanding the Instructions

XINU default scheduling invariant - current process is always the highest process one (round-robin among the processes with the high priority).

resched - pick one group using the aging scheduler, then pick a process from that group.

Aging scheduler - Default priority - 10. Changed via chgprio(). During each resched call, set the group priority of the current process’ group to its initial priority. Increment priority of each group by its count in the ready list (excluding the null process). Pick the group with highest priority. In a tie, pick proportional share scheduler. If no processes in one group, pick the other.

Aging scheduler in words - update group priorities, return next group.

Overall scheduler in words - update current process priority; get next group; if invalid group, schedule null (it will be the only thing in readylist); update process with highest priority; switch to it (if needed).

Proportional share scheduler in words - get best propsched guy in readylist; if none such or if current process is better (and in propsched), resched current process; else, evict current process; get quantum for best process; schedule best process;

TS scheduler in words - get best tssched guy in readylist; if none such or if current process is better (and in tssched), resched current process; else, evict current process; get quantum for best process; schedule best process.

Proportional share scheduler - Initial Pi for each process = 0. When a rescheduling occurs, Pi of currently running process = Pi + (t * 100 / Ri). Process scheduled for the first time or after blocking, Pi = max(Pi, T). T is the number of ticks since the start of the system.

Scheduled after blocking: resume a process that is suspended (by default, the only time this happens is when you create() a process) - this calls ready anyway; ready a sleeping process;

Need to find process with minimum priority within proportional share group. For that, we need the “first key” in the PS ready list to compare against the current process.

TS scheduler - classify as CPU-bound or IO-bound. preempt <= 0 => CPU-bound. Set priority and per-process quantum as per dispatch table.

Test: Both types of processes - set QUANTUM to a high value so that PS has a chance.

Course Questions

What if you pass in a stack size to create() that is too small?

Do we have to disable interrupts when dealing with procent?

kputc - maybe enable interrupts anyway? What if somebody else calls kputc?

HW1

Hypothesis: sendA, sendB with priority 20 each - You switch from A to B, but not because A was eligible, but rather because it gave up the processor (probably for I/O). Ditto for B to main. However, main is pushed out because it used up its time quantum.

Observation: sendA, sendB with priority 25 each - again, main comes up only because A and B get blocked.

Hypothesis: I’m not thinking of the type signature. That is: what question do I want to answer right now?

Question: Does main create A and B and then give up control later, or does A take up control right away and then give it to B only when finished?

Observation: I want labels (“main finishes first and then gives way to the new processes”), not raw data.

Observation: main creates A and switches immediately (by design, I think). A blocks. main then creates and switches to B.

Question: Can a process keep hogging the CPU?

Observation: main creates A. A never gives up.

Observation: Infinite loop - no resched messages.

Hypothesis: So, A never even called resched. [wrong]

Question: Is resched called when A is in the infinite loop? Is preempt doing anything?

Observation: Yes. Over and over. There simply is nothing that is even equal in priority to A in the readylist.

Observation: Same priority - A and B and main go round and round.

Corollary: That explains why my loop of processes actually led to sequential execution. Each one was the only king during its execution.

Observation: main - when it resumes a process, it inadvertently calls resched, so it has to wait its turn before it can resume the next process.

Observation: If the processes have priority 15, they never get executed.

Observation: Processes with priority 20, main goes down to 15 after creating them - they go round-robin.

Observation: division by zero - because procrate was zero for the default processes.

Observation: Negative priorities because I used INT_MAX instead of SHRT_MAX.

Observation: Still, priority becomes negative for everybody.

Observation: Delta seems to be around 9420 for each process.

Hypothesis: Process ticks aren’t reset when they’re rescheduled.

Observation: Initial priority is 15 and quickly goes down to zero.

Hypothesis: Setting the initial priority in create() will fix things.

Observation: main - when relinquishing the processor, its process ticks counter isn’t reset.

Observation: new process - stays in the processor => not rescheduled; need to reset ticks here too.

Observation: Delta seems reasonable now.

Observation: Starting priority is actually still 15, because I’m calling propsched_initialize_prio() before create sets the initial priority.

Observation: Starting priority is correct. main gets kind of starved because 4 and 5 lose priority very slowly.

Observation: My benchmark isn’t working well. Processes are not all up at the same time.

Hypothesis: Why not try a different kind of benchmark?

Observation: main’s initial rate is 1, so that reduces its priority a lot in the first few rounds.

Observation: Ticks aren’t the total ticks.

Observation: Total ticks! So, my processtotalticks change probably did the trick.

Observation: Unexpected output - percentage rate gave the same output as same rate.

Observation: Wow. That was for the dumbest reason ever. I had never used the get_rate function!

Observation: Trying to see the percentage of process ticks during the benchmark. Failing badly. Taking a lot of time too.

Observation: I documented each function in Servo. Haven’t done that for XINU.

Observation: Confusing debug output - one of main’s update priority debug sets are split for some reason.

Observation: main gets preempted in the middle of stopping deferral.

Observation: main and the processes get to print one line before they get preempted!

Observation: However, resched itself doesn’t get preempted. Prints line after line!

Observation: One call to kprintf seems to take a time slice (2ms).

Observation: Wow. All because I didn’t disable interrupts before calling resched_cntl. 2.5 hours gone, just for that one lesson.

Observation: After implementing PS for a returning blocked process - main runs and sleeps, process 4 runs, but nothing else does.

Observation: Didn’t even call print_readylist.

Observation: Called propsched_set_prio_after_blocking after inserting into the readylist (on the key of the old priority).

Observation: Seems to work.

Observation: Calling newqueue() seems to cause a problem.

Observation: NQENT is the problem!

Observation: Fucked up a get max element in linked list because I didn’t update the curr pointer. Infinite loop.

Lesson: Clean and build when you change header files or #defines.

HW2

Understanding the Instructions: Interface for Every Function

In a separate shellutils.c and piputils.c file:

shell - interpret command: bunch of tokens -> Maybe tokens for processes in pipe order

shell - make processes: tokens for processes in pipe order -> Maybe processes in pipe order

piputil - pipe together a bunch of processes: processes in pipe order -> Maybe processes piped together

syscall - set stdout for process: process, stdout file descriptor -> Maybe set stdout

syscall - set stdin for process: process, stdin file descriptor -> Maybe set stdin

shell - clean up a command: kill all processes and their pipes -> Maybe ok.

Test: overall - command with no pipes (see if you can programmatically run this from main); one pipe between different types of commands (producer blocks, consumer blocks, both block, some die or sleep or don’t get scheduled); multiple pipes

Refactor shell to make it use the above interface even for non-pipe commands. Make sure it works for the default case.

pipinit: pipid [, Maybe pipe_t] -> initialized pipe

pipglobalinit: globals {table} -> initialized globals {table with everything set to free}

pipcreate: () [table] -> Maybe did32, owner (then pipinit that pipe); table should have an active pipe at did32

pipdelete: pipe [, table] -> ok; reset pipe state (maybe via pipinit or some pipreset they both call that clears the buffer and resets semaphores, etc.); check for owner; basically pipdisconnect.

pipconnect: pipe [, pipe struct], writer, reader -> Maybe A and B piped; reader and writer should not be the same

pipdisconnect: pipe [, table, pipe struct] -> Maybe ok (call set stdout with console);

pipputc: pipe [, pipe struct], char -> Blocking ok

pipwrite: pipe [, pipe struct], buf, length -> Blocking (number of characters or SYSERR); if pipe not in connected state or if this is not writer, return SYSERR; full -> block; some space -> write and block;

TODO: Question: pipwrite - suppose reader doesn’t accept any more characters - return SYSERR or number of characters written?

pipgetc: pipe [, pipe struct] -> Blocking (character or SYSERR)

pipread: pipe [, pipe struct], buf, length -> Blocking (number of bytes read or SYSERR)

TODO: Question: pipread - if no data, block; if only some data, read some bytes and block; if writer stops writing, return number of bytes read or SYSERR?

kill: process [, pipe struct] -> delete pipes that you own; disconnect from any pipes (and disconnect the other process too)

Question: How to go for refactor-red-green-refactor?

Hypothesis: Get an interface for each function and then minimize it. Be strict - don’t touch anything outside the interface. Then test your implementation against it.

Test the different states of the pipe, producer, consumer, and owner (such as current, ready, sleeping, waiting, or free).

Implementation

Hypothesis: Assert preconditions and postconditions. Argument testing - null, etc.

Information from Interpreter

Observation: Added the pip32 <-> did32 utility functions

Observation: Don’t know which functions will call pipreset. Confused about how it should really behave.

Hypothesis: Go with separate functions and then merge them during refactor.

Observation: I don’t have any tests right now, red or green.

Hypothesis: Test all branches of your function.

Observation: RED! I hadn’t even run my test function.

Hypothesis: Unit tests (that failed and now pass) tell you that you’re making progress.

Observation: I couldn’t run multiple tests on pipes because I hadn’t implemented pipdelete.

Observation: Bug - pipcreate returned did not pipid.

Observation: Ditto for pipinit.

Hypothesis: Need to add assertions everywhere I receive pipid. (You can say that again.)

Observation: pipdelete test passes without any implementation! Colour me shocked!

Hypothesis: When refactoring before adding a feature, I need to assert preconditions and postconditions (or add unit tests) for everything the feature changes. Worst case, I need to catch those after adding the feature.

Hypothesis: Bug due to did32 vs pipid32 <- my confusion about the two types.

Hypothesis: That feels like duplication of code. Wait. It is! Why do you have two different types for the same value! One should be a view of the other - a simple function somewhere.

Observation: All my time so far was spent debugging because of a simple type confusion.

Observation: Always, always, always make a test fail before you make it pass.

OS HW3

Problem Statement

Overview

TODO: Read Intel manual volume 3, chapters 2-5

Virtual Memory Services

heap: tell whether an address is valid or not; freelist and so on.

private heap. dummy heap.

vcreate: process must have a private heap with hsize pages.

vgetmem: given a private heap, ask for memory -> get it.

vfreemem: given a private heap, free memory -> free it up.

srpolicy: set page replacement function.

Prototypes?

TODO: prototypes.h

Handling error code on page fault

https://piazza.com/class/j6dtteb9lor25u?cid=185

Memory Addressing

http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf http://wiki.osdev.org/Paging http://wiki.osdev.org/Setting_Up_Paging

Assembly

Have to store the value in a global variable and then copy from that global variable to a local variable. (See stacktrace.c for an example - g_esp vs sp.)

Page Fault Handler

Question: How to get the faulted address?

(Answer: CR2)

Might need semaphores to deal with context-switching

https://piazza.com/class/j6dtteb9lor25u?cid=201

Need it because you will switch to rdsproc and block on calls to the backing store and another process may page fault as well. So, wait on a semaphore at the beginning and signal at the end.

Check whether address is valid:

You need to check if it’s within the virtual heap. You already mentioned the starting page number of the virtual heap (so translate that into an address), so there’s your lower bound. You know at vcreate how large your virtual heap is, so you can calculate the upper bound using hsize.

Context-Switching

Important: Flush the TLB upon context-switch.

As we switch context between processes, we must also switch between memory spaces. This is accomplished by updating the PDBR register with every context switch. This register must always point to a valid page directory that is in RAM at a page boundary.

When you context-switch, you don’t need to clear TLB?

When switching to a non-virtual process, set pdbr to the null process’ page directory. (Or just that process’ page directory, which will point to the same 5 global page tables.)

Killing the Process

When killing it, don’t write back frames. Just free them.

Outline

Question: What if nframes is 50? Does that mean that addresses in page 2000 will not be accessible even though they are part of the global table and marked as present? (That page will be handled like any other virtual memory page.)

Run through with one concrete example

Hypothesis: Any page in your virtual heap - exists in your allocated backing store (and if marked as present, exists in a frame as well).

Any page in the first 1024 pages - exists in memory.

Any page in the other global page tables - exists in frames (but not in the backing store).

Hypothesis: memlist is from the end of XINU to the 1024th page.

Question: Should the global page tables be in a frame or somewhere else? How to prevent them from being replaced? (For now, I will assume yes.)

NFRAMES = 3072

You want to read from some address in your private heap. (You’ve already used vgetmem to allocate the memory.).

First, there will be a page fault because you’ve never accessed that page before. So, you will allocate one frame for the page table and then one frame for the page itself. And then copy that page from the backing store.

There will always be a free frame available, so no problems.

Test: Just have a dummy heap that simply marks an address space as valid. vgetmem need not have any effect. Test whether you can access different pages in your heap without trouble. Also have a dummy backing store that simply returns the frame as such.

Test: Context-switch to see if that works. Again, access different pages in that process’ separate heap.

Test: Implement the heap with memlist.

NFRAMES = 50

You want to read from some address in your private heap. (You’ve already used vgetmem to allocate the memory.).

Test: Free frame available - same as before.

Test: Free frame not available - have to replace a page. Implement the backing store stuff.

Backing store

Allocate backing stores in vcreate. To use the backing store, open, read or write, close.

TODO: Bug - it doesn’t print everything in the compilation buffer, but does so when I pipe it into grep or a file.

Heap

Test: access page beyond virtual memory - should fail.

vcreate

Initialize heap and page directory

TODO: If you allocate next in vcreate, you will try to allocate new virtual memory (page) of the process you call vcreate instead of the process created by vcreate. You may avoid doing this by allocating next in vgetmem.

Frame Allocator

use this for the global page tables and directory? create_global_page_directory(pid) ?? create_global_page_table(pid) ?? create_page_directory(pid) create_page_table(pid) get free frame bring in faulted page pick a page to replace

vgetmem

get memory from heap

Test: two processes write at the same address, no conflict.

Implementation Plan

TODO: Use FRAME0.

Hypothesis: Assert preconditions and postconditions. Argument testing - null, etc. Also, have a unit test for each branch.

Test: [Done] No heap, no virtual memory stuff, no backing store. Extend the null process’ page directory.

Test: [Done] access different pages.

Test: [Done] per-process page directory. context-switch. context-switch when accessing the same memory addresses.

[Done] Keeps rebooting when I load the new page directory.

Test: [Done] heap. check for valid address.

Test: [Done] non-virtual process page directories must point to nullproc page directory. (Or just check for valid heap address so that they don’t go past the first four page tables?)

Test: [Done] Run the official test - page fault handling.

Test: [Done] refactor - frame list.

Test: [Done] ask for more frames than NFRAMES. should obtain a free frame.

Test: [Done] one page when there’s no free frame.

Test: [Done] dirty page; access 50 more pages; check if the old value is still there.

Test: [Done] Implement backing store.

Test: [Done] process being killed.

Test: [Done] Run the official test - page replacement. Works on Galileo.

Test: [Done] Hooks.

Test: [Done] page replacement policy.

Test: [Done] Semaphores. Run official test with several processes (semaphores). Both page fault-handling and replacement.

Test: [Done] Run official tests on Galileo.

Test: [Done] I don’t evict pd or pt. Test whether the reference count thing matters.

Important: Massive bug because Galileo runs rdsproc (or something) that takes up a lot of the stack and thus gives SYSERR when later processes ask for stack.

Tests

4 processes, 2 backing stores each - all running the page policy tests

1 process, 8 backing stores

6 processes.

Test cases: NFRAME [50, 3072]; PAGE_ALLOCATION [0, 1]

Questions

Question: resched - load page directory before or after context switch?

Created: September 9, 2017

Last modified: December 10, 2017

Status: in-progress notes

Tags: notes, os