-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathCS503-OS-notes.html
365 lines (349 loc) · 28.4 KB
/
CS503-OS-notes.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<link rel="icon" type="image/png" href="./images/favicon-32x32.png" sizes="32x32" />
<link rel="icon" type="image/png" href="./images/favicon-16x16.png" sizes="16x16" />
<title>CS503 OS HW1 Notes - SPK's Rationality Essays</title>
<link rel="stylesheet" type="text/css" href="./css/default.css" />
<link rel="stylesheet" type="text/css" href="./css/highlight.css" />
<!-- <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script> -->
<!-- <script type="text/javascript" src="/js/header-links.js"></script> -->
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link href="atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM/RSS Feed" />
<!-- Google Analytics stuff -->
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-DEWF2J5BG8"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-DEWF2J5BG8');
</script>
<script type="text/javascript" src="https://fast.fonts.net/jsapi/f7f47a40-b25b-44ee-9f9c-cfdfc8bb2741.js"></script>
</head>
<body>
<div id="header">
<div id="logo">
<a href="./">SPK's Rationality Essays</a>
</div>
<div id="navigation">
<a href="./">Home</a>
<a href="./notes.html">Notes</a>
<!-- <a href="/about.html">About</a> -->
<a href="./archive.html">Archive</a>
<a href="./atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM/RSS Feed">RSS</a>
</div>
</div>
<div id="content">
<h1 id="post-title">CS503 OS HW1 Notes</h1>
<!-- <center><img src="https://fbcdn-sphotos-d-a.akamaihd.net/hphotos-ak-prn1/t31.0-8/p600x600/10257116_10202295769100492_2438594605053717342_o.jpg" height="400" width="300" class="sujeet-pic" alt="Sujeet pic" /></center> -->
<h1 id="compiling-and-running-xinu">Compiling and running XINU</h1>
<p>After making changes,</p>
<pre><code>cd xinu-fall2017/compile
make clean
make rebuild
make</code></pre>
<p>You can edit remote files on your laptop’s Emacs using Tramp:</p>
<pre><code>/ssh:[email protected]:/homes/yourusername/</code></pre>
<p>To run on the backend:</p>
<pre><code>cd ~/xinu-fall2017/compile
cs-console
<C-space>
g (download default image - xinu - and powercycle backend)</code></pre>
<p>Test: Check if you can recompile and reload the xinu without logging off the backend.</p>
<p>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 <C-space> and g to powercycle.</p>
<h1 id="xinu-explorations">XINU Explorations</h1>
<pre><code>find . -type f -name "*.c" | wc -l
227
find . -type f -name "*.c" | xargs wc -l
...
21868 total</code></pre>
<p>Hmm… That seems pretty small.</p>
<h1 id="tags">TAGS</h1>
<p>Create tags using</p>
<pre><code>find . -name "*.[chS]" -print | etags -</code></pre>
<h1 id="understanding-xinu">Understanding XINU</h1>
<p>system/initialize.c: TODO</p>
<p>system/resched.c:</p>
<p>It just looks for the highest priority process and schedules it.</p>
<h2 id="ready">ready</h2>
<p>ready() inserts the process into readylist and then reschedules.</p>
<h2 id="startup">Startup</h2>
<p>nulluser() sets up the system and then creates the startup() process. After that, nulluser just runs in an infinite loop.</p>
<h2 id="main">main</h2>
<p>pid seems to be 3. How?</p>
<p>When I create a shell, pid 2 seems to be <code>rdsproc</code>. It’s created when initializing devices in sysinit(), which is called by nulluser.</p>
<h2 id="sleepms">sleepms</h2>
<p>It inserts itself in the sleep queue, sets state as sleep, and calls resched.</p>
<h2 id="sleepq---delta-list">sleepq - delta list</h2>
<p>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).</p>
<h2 id="clkhandler">clkhandler</h2>
<p>It’s called by clkdisp after disabling interrupts. So, when it calls resched, the process won’t get preempted.</p>
<h2 id="ctxsw">ctxsw</h2>
<p>I think it restores the interrupt mask (that may have been disabled by clkdisp when calling clkhandler).</p>
<h2 id="resched_cntl">resched_cntl</h2>
<p>Need to disable interrupts before calling resched or resched_cntl. Otherwise, you may get preempted and rescheduled in the middle of your resched call.</p>
<h2 id="preempt">preempt</h2>
<p>Assertion that worked (for my test case): processticks == QUANTUM (used full time slice) or processticks = QUANTUM - preempt (voluntarily gave up CPU).</p>
<h1 id="approach-rapid-prototyping">Approach: Rapid Prototyping</h1>
<p>Hypothesis: Add one feature at a time, in line with rapid prototyping. You’d have to release - aka run tests - after every feature.</p>
<p>Question: What tests?</p>
<p>Hypothesis: Minimum test - The kernel should type-check, compile, and boot up fine.</p>
<p>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.)</p>
<p>Observation: This is an integration test, not a unit test. Expensive.</p>
<h1 id="approach-documentation-and-assertions">Approach: Documentation and Assertions</h1>
<p>Hypothesis: Document each function -> categorize XINU appropriately.</p>
<p>Hypothesis: Use assertions -> can unit test your code.</p>
<h1 id="hw1---understanding-the-instructions">HW1 - Understanding the Instructions</h1>
<p>XINU default scheduling invariant - current process is always the highest process one (round-robin among the processes with the high priority).</p>
<p>resched - pick one group using the aging scheduler, then pick a process from that group.</p>
<p>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.</p>
<p>Aging scheduler in words - update group priorities, return next group.</p>
<p>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).</p>
<p>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;</p>
<p>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.</p>
<hr />
<p>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.</p>
<p>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;</p>
<p>Need to find process with minimum priority <em>within</em> proportional share group. For that, we need the “first key” in the PS ready list to compare against the current process.</p>
<p>TS scheduler - classify as CPU-bound or IO-bound. preempt <= 0 => CPU-bound. Set priority and per-process quantum as per dispatch table.</p>
<p>Test: Both types of processes - set QUANTUM to a high value so that PS has a chance.</p>
<h1 id="course-questions">Course Questions</h1>
<p>What if you pass in a stack size to create() that is too small?</p>
<p>Do we have to disable interrupts when dealing with procent?</p>
<p>kputc - maybe enable interrupts anyway? What if somebody else calls kputc?</p>
<h1 id="hw1">HW1</h1>
<p>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.</p>
<p>Observation: sendA, sendB with priority 25 each - again, main comes up only because A and B get blocked.</p>
<p><strong>Hypothesis</strong>: I’m not thinking of the type signature. That is: what question do I want to answer right now?</p>
<p>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?</p>
<p>Observation: I want labels (“main finishes first and then gives way to the new processes”), not raw data.</p>
<p><strong>Observation</strong>: main creates A and switches immediately (by design, I think). A blocks. main then creates and switches to B.</p>
<p>Question: Can a process keep hogging the CPU?</p>
<p>Observation: main creates A. A never gives up.</p>
<p>Observation: Infinite loop - no resched messages.</p>
<p>Hypothesis: So, A never even called resched. [wrong]</p>
<p>Question: Is resched called when A is in the infinite loop? Is preempt doing anything?</p>
<p>Observation: Yes. Over and over. There simply is nothing that is even equal in priority to A in the readylist.</p>
<p>Observation: Same priority - A and B and main go round and round.</p>
<p>Corollary: That explains why my loop of processes actually led to sequential execution. Each one was the only king during its execution.</p>
<p>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.</p>
<p>Observation: If the processes have priority 15, they never get executed.</p>
<p>Observation: Processes with priority 20, main goes down to 15 after creating them - they go round-robin.</p>
<p>Observation: division by zero - because procrate was zero for the default processes.</p>
<p>Observation: Negative priorities because I used INT_MAX instead of <code>SHRT_MAX</code>.</p>
<p>Observation: Still, priority becomes negative for everybody.</p>
<p>Observation: Delta seems to be around 9420 for each process.</p>
<p>Hypothesis: Process ticks aren’t reset when they’re rescheduled.</p>
<p>Observation: Initial priority is 15 and quickly goes down to zero.</p>
<p>Hypothesis: Setting the initial priority in create() will fix things.</p>
<p>Observation: main - when relinquishing the processor, its process ticks counter isn’t reset.</p>
<p>Observation: new process - stays in the processor => not rescheduled; need to reset ticks here too.</p>
<p>Observation: Delta seems reasonable now.</p>
<p>Observation: Starting priority is actually still 15, because I’m calling <code>propsched_initialize_prio()</code> before create sets the initial priority.</p>
<p>Observation: Starting priority is correct. main gets kind of starved because 4 and 5 lose priority very slowly.</p>
<p>Observation: My benchmark isn’t working well. Processes are not all up at the same time.</p>
<p>Hypothesis: Why not try a different kind of benchmark?</p>
<p>Observation: main’s initial rate is 1, so that reduces its priority a lot in the first few rounds.</p>
<p>Observation: Ticks aren’t the total ticks.</p>
<p>Observation: Total ticks! So, my processtotalticks change probably did the trick.</p>
<p>Observation: Unexpected output - percentage rate gave the same output as same rate.</p>
<p>Observation: Wow. That was for the dumbest reason ever. I had never used the get_rate function!</p>
<p>Observation: Trying to see the percentage of process ticks during the benchmark. Failing badly. Taking a lot of time too.</p>
<p>Observation: I documented each function in Servo. Haven’t done that for XINU.</p>
<p>Observation: Confusing debug output - one of main’s update priority debug sets are split for some reason.</p>
<p>Observation: main gets preempted in the middle of stopping deferral.</p>
<p>Observation: main and the processes get to print one line before they get preempted!</p>
<p>Observation: However, resched itself doesn’t get preempted. Prints line after line!</p>
<p>Observation: One call to kprintf seems to take a time slice (2ms).</p>
<p>Observation: Wow. All because I didn’t disable interrupts before calling resched_cntl. 2.5 hours gone, just for that one lesson.</p>
<p>Observation: After implementing PS for a returning blocked process - main runs and sleeps, process 4 runs, but nothing else does.</p>
<p>Observation: Didn’t even call print_readylist.</p>
<p>Observation: Called <code>propsched_set_prio_after_blocking</code> <em>after</em> inserting into the readylist (on the key of the old priority).</p>
<p>Observation: Seems to work.</p>
<p>Observation: Calling newqueue() seems to cause a problem.</p>
<p>Observation: NQENT is the problem!</p>
<p>Observation: Fucked up a get max element in linked list because I didn’t update the curr pointer. Infinite loop.</p>
<p>Lesson: Clean and build when you change header files or <code>#define</code>s.</p>
<h1 id="hw2">HW2</h1>
<h2 id="understanding-the-instructions-interface-for-every-function">Understanding the Instructions: Interface for Every Function</h2>
<p>In a separate shellutils.c and piputils.c file:</p>
<p>shell - interpret command: bunch of tokens -> Maybe tokens for processes in pipe order</p>
<p>shell - make processes: tokens for processes in pipe order -> Maybe processes in pipe order</p>
<p>piputil - pipe together a bunch of processes: processes in pipe order -> Maybe processes piped together</p>
<p>syscall - set stdout for process: process, stdout file descriptor -> Maybe set stdout</p>
<p>syscall - set stdin for process: process, stdin file descriptor -> Maybe set stdin</p>
<p>shell - clean up a command: kill all processes and their pipes -> Maybe ok.</p>
<p>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</p>
<p>Refactor shell to make it use the above interface even for non-pipe commands. Make sure it works for the default case.</p>
<hr />
<p>pipinit: pipid [, Maybe pipe_t] -> initialized pipe</p>
<p>pipglobalinit: globals {table} -> initialized globals {table with everything set to free}</p>
<p>pipcreate: () [table] -> Maybe did32, owner (then pipinit that pipe); table should have an active pipe at did32</p>
<p>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.</p>
<p>pipconnect: pipe [, pipe struct], writer, reader -> Maybe A and B piped; reader and writer should not be the same</p>
<p>pipdisconnect: pipe [, table, pipe struct] -> Maybe ok (call set stdout with console);</p>
<p>pipputc: pipe [, pipe struct], char -> Blocking ok</p>
<p>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;</p>
<p><strong>TODO</strong>: Question: pipwrite - suppose reader doesn’t accept any more characters - return SYSERR or number of characters written?</p>
<p>pipgetc: pipe [, pipe struct] -> Blocking (character or SYSERR)</p>
<p>pipread: pipe [, pipe struct], buf, length -> Blocking (number of bytes read or SYSERR)</p>
<p><strong>TODO</strong>: 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?</p>
<p>kill: process [, pipe struct] -> delete pipes that you own; disconnect from any pipes (and disconnect the other process too)</p>
<hr />
<p>Question: How to go for refactor-red-green-refactor?</p>
<p><strong>Hypothesis</strong>: 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.</p>
<p>Test the different states of the pipe, producer, consumer, and owner (such as current, ready, sleeping, waiting, or free).</p>
<h2 id="implementation">Implementation</h2>
<p><strong>Hypothesis</strong>: Assert preconditions and postconditions. Argument testing - null, etc.</p>
<h2 id="information-from-interpreter">Information from Interpreter</h2>
<p>Observation: Added the pip32 <-> did32 utility functions</p>
<p>Observation: Don’t know which functions will call pipreset. Confused about how it should really behave.</p>
<p>Hypothesis: Go with separate functions and then merge them during refactor.</p>
<p>Observation: I don’t have any tests right now, red or green.</p>
<p>Hypothesis: Test all branches of your function.</p>
<p>Observation: <strong>RED</strong>! I hadn’t even run my test function.</p>
<p>Hypothesis: Unit tests (that failed and now pass) tell you that you’re making progress.</p>
<p><strong>Observation</strong>: I couldn’t run multiple tests on pipes because I hadn’t implemented pipdelete.</p>
<p>Observation: Bug - pipcreate returned did not pipid.</p>
<p>Observation: Ditto for pipinit.</p>
<p>Hypothesis: Need to add assertions everywhere I receive pipid. (You can say that again.)</p>
<p>Observation: pipdelete test passes without any implementation! Colour me shocked!</p>
<p><strong>Hypothesis</strong>: 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.</p>
<p>Hypothesis: Bug due to did32 vs pipid32 <- my confusion about the two types.</p>
<p>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.</p>
<p>Observation: All my time so far was spent debugging because of a simple type confusion.</p>
<p><strong>Observation</strong>: Always, always, always make a test fail before you make it pass.</p>
<h1 id="os-hw3">OS HW3</h1>
<h2 id="problem-statement">Problem Statement</h2>
<p>Overview</p>
<p><strong>TODO</strong>: Read Intel manual volume 3, chapters 2-5</p>
<h3 id="virtual-memory-services">Virtual Memory Services</h3>
<p>heap: tell whether an address is valid or not; freelist and so on.</p>
<p>private heap. dummy heap.</p>
<p>vcreate: process must have a private heap with hsize pages.</p>
<p>vgetmem: given a private heap, ask for memory -> get it.</p>
<p>vfreemem: given a private heap, free memory -> free it up.</p>
<p>srpolicy: set page replacement function.</p>
<h3 id="prototypes">Prototypes?</h3>
<p><strong>TODO</strong>: prototypes.h</p>
<h3 id="handling-error-code-on-page-fault">Handling error code on page fault</h3>
<p>https://piazza.com/class/j6dtteb9lor25u?cid=185</p>
<h3 id="memory-addressing">Memory Addressing</h3>
<p>http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf http://wiki.osdev.org/Paging http://wiki.osdev.org/Setting_Up_Paging</p>
<h2 id="assembly">Assembly</h2>
<p>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 - <code>g_esp</code> vs <code>sp</code>.)</p>
<h2 id="page-fault-handler">Page Fault Handler</h2>
<p>Question: How to get the faulted address?</p>
<p>(Answer: CR2)</p>
<p>Might need semaphores to deal with context-switching</p>
<p>https://piazza.com/class/j6dtteb9lor25u?cid=201</p>
<p>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.</p>
<p>Check whether address is valid:</p>
<blockquote>
<p>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.</p>
</blockquote>
<h2 id="context-switching">Context-Switching</h2>
<p><strong>Important</strong>: Flush the TLB upon context-switch.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>When you context-switch, you don’t need to clear TLB?</p>
<p>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.)</p>
<h2 id="killing-the-process">Killing the Process</h2>
<p>When killing it, don’t write back frames. Just free them.</p>
<h2 id="outline">Outline</h2>
<p>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.)</p>
<h3 id="run-through-with-one-concrete-example">Run through with one concrete example</h3>
<p><strong>Hypothesis</strong>: Any page in your virtual heap - exists in your allocated backing store (and if marked as present, exists in a frame as well).</p>
<p>Any page in the first 1024 pages - exists in memory.</p>
<p>Any page in the other global page tables - exists in frames (but not in the backing store).</p>
<p>Hypothesis: memlist is from the end of XINU to the 1024th page.</p>
<p>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.)</p>
<hr />
<p>NFRAMES = 3072</p>
<p>You want to read from some address in your private heap. (You’ve already used vgetmem to allocate the memory.).</p>
<p>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.</p>
<p>There will always be a free frame available, so no problems.</p>
<p>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.</p>
<p>Test: Context-switch to see if that works. Again, access different pages in that process’ separate heap.</p>
<p>Test: Implement the heap with memlist.</p>
<hr />
<p>NFRAMES = 50</p>
<p>You want to read from some address in your private heap. (You’ve already used vgetmem to allocate the memory.).</p>
<p>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.</p>
<p>Test: Free frame available - same as before.</p>
<p>Test: Free frame not available - have to replace a page. Implement the backing store stuff.</p>
<h2 id="backing-store">Backing store</h2>
<p>Allocate backing stores in vcreate. To use the backing store, open, read or write, close.</p>
<p><strong>TODO</strong>: Bug - it doesn’t print everything in the compilation buffer, but does so when I pipe it into grep or a file.</p>
<h2 id="heap">Heap</h2>
<p>Test: access page beyond virtual memory - should fail.</p>
<h2 id="vcreate">vcreate</h2>
<p>Initialize heap and page directory</p>
<p><strong>TODO</strong>: 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.</p>
<h2 id="frame-allocator">Frame Allocator</h2>
<p>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</p>
<h2 id="vgetmem">vgetmem</h2>
<p>get memory from heap</p>
<p>Test: two processes write at the same address, no conflict.</p>
<h2 id="implementation-plan">Implementation Plan</h2>
<p><strong>TODO</strong>: Use FRAME0.</p>
<p><strong>Hypothesis</strong>: Assert preconditions and postconditions. Argument testing - null, etc. Also, have a unit test for each branch.</p>
<p>Test: [Done] No heap, no virtual memory stuff, no backing store. Extend the null process’ page directory.</p>
<p>Test: [Done] access different pages.</p>
<p>Test: [Done] per-process page directory. context-switch. context-switch when accessing the same memory addresses.</p>
<p>[Done] Keeps rebooting when I load the new page directory.</p>
<p>Test: [Done] heap. check for valid address.</p>
<p>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?)</p>
<p>Test: [Done] Run the official test - page fault handling.</p>
<p>Test: [Done] refactor - frame list.</p>
<p>Test: [Done] ask for more frames than NFRAMES. should obtain a free frame.</p>
<p>Test: [Done] one page when there’s no free frame.</p>
<p>Test: [Done] dirty page; access 50 more pages; check if the old value is still there.</p>
<p>Test: [Done] Implement backing store.</p>
<p>Test: [Done] process being killed.</p>
<p>Test: [Done] Run the official test - page replacement. Works on Galileo.</p>
<p>Test: [Done] Hooks.</p>
<p>Test: [Done] page replacement policy.</p>
<p>Test: [Done] Semaphores. Run official test with several processes (semaphores). Both page fault-handling and replacement.</p>
<p>Test: [Done] Run official tests on Galileo.</p>
<p>Test: [Done] I don’t evict pd or pt. Test whether the reference count thing matters.</p>
<p><strong>Important</strong>: 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.</p>
<h2 id="tests">Tests</h2>
<p>4 processes, 2 backing stores each - all running the page policy tests</p>
<p>1 process, 8 backing stores</p>
<p>6 processes.</p>
<p>Test cases: NFRAME [50, 3072]; PAGE_ALLOCATION [0, 1]</p>
<h2 id="questions">Questions</h2>
<p>Question: resched - load page directory before or after context switch?</p>
<div class="info">Created: September 9, 2017</div>
<div class="info">Last modified: December 10, 2017</div>
<div class="info">Status: in-progress notes</div>
<div class="info"><b>Tags</b>: notes, os</div>
<br />
<div id="disqus_thread"></div>
<script type="text/javascript">
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'spkrationalitytrainingground'; // required: replace example with your forum shortname
var disqus_identifier = '/CS503-OS-notes.html';
var disqus_title = 'CS503 OS HW1 Notes';
/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<script type="text/javascript" src="https://fast.fonts.net/jsapi/f7f47a40-b25b-44ee-9f9c-cfdfc8bb2741.js"></script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
</div>
<div id="footer">
Site proudly generated by
<a href="http://jaspervdj.be/hakyll">Hakyll</a>
</div>
</body>
</html>