https://xinu.cs.mu.edu/index.php?title=Assignment:_Heap_Memory&feed=atom&action=historyAssignment: Heap Memory - Revision history2024-03-29T11:42:27ZRevision history for this page on the wikiMediaWiki 1.34.2https://xinu.cs.mu.edu/index.php?title=Assignment:_Heap_Memory&diff=2943&oldid=prevAkoehler at 07:32, 12 December 20082008-12-12T07:32:26Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 07:32, 12 December 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Student Built Xinu]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Student Built Xinu]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>= <del class="diffchange diffchange-inline">Delta Queues </del>=</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>= <ins class="diffchange diffchange-inline">Heap Memory </ins>=</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>This assignment is a [[Xinu]] assignment allowing the student to <del class="diffchange diffchange-inline">grow a </del>more <del class="diffchange diffchange-inline">firm </del>understanding of how an operating system works. This assignment is part of the [[Student Built Xinu]] track for professors that are [[Teaching With Xinu]]. <del class="diffchange diffchange-inline"> Your </del>entire working directory containing your Xinu operating system will be submission for this assignment.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>This assignment is a [[Xinu]] assignment allowing the student to more <ins class="diffchange diffchange-inline">firmly </ins>understanding of how an operating system works. This assignment is part of the [[Student Built Xinu]] track for professors that are [[Teaching With Xinu]]. <ins class="diffchange diffchange-inline">The </ins>entire working directory containing your Xinu operating system will be submission for this assignment.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Preparation ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Preparation ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>First, make a fresh copy of your work thus far.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>First, make a fresh copy of your work thus far.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l8" >Line 8:</td>
<td colspan="2" class="diff-lineno">Line 8:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> tar xvzf <tar-ball location></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> tar xvzf <tar-ball location></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>You should now see the new project files in with your old files. Be certain to make clean before compiling for the first time.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>You should now see the new project files in with your old files. Be certain to make clean before compiling for the first time.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>== <del class="diffchange diffchange-inline">Sleep </del>==</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>== <ins class="diffchange diffchange-inline">Getmem and Freemem </ins>==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Modify </del><code><del class="diffchange diffchange-inline">system</del>/<del class="diffchange diffchange-inline">sleep</del>.<del class="diffchange diffchange-inline">c</del></code><del class="diffchange diffchange-inline">, </del><code>system/<del class="diffchange diffchange-inline">wakeup</del>.c</code><del class="diffchange diffchange-inline">, </del><code>system/<del class="diffchange diffchange-inline">insertd</del>.c</code><del class="diffchange diffchange-inline">, </del>and <code>system/<del class="diffchange diffchange-inline">clockintr</del>.c</code> to <del class="diffchange diffchange-inline">add </del>the <del class="diffchange diffchange-inline"><code>sleep()</code> system call to the operating system</del>. <del class="diffchange diffchange-inline">A process that calls <code>sleep</del>(<del class="diffchange diffchange-inline">n)</code> should enter </del>the <del class="diffchange diffchange-inline"><code>PRSLEEP</code> state for n clock ticks. A clock </del>"<del class="diffchange diffchange-inline">tick</del>" <del class="diffchange diffchange-inline">is one millisecond </del>in <del class="diffchange diffchange-inline">our current system. It corresponds to the raising of the timer interrupt request when interrupts are not disabled. When the clock interrupt handler detects that a process has slept for long enough, the <code>wakeup</code> function should move the process back to the ready list</del>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">The files </ins><code><ins class="diffchange diffchange-inline">include</ins>/<ins class="diffchange diffchange-inline">memory</ins>.<ins class="diffchange diffchange-inline">h</ins></code> <ins class="diffchange diffchange-inline">and </ins><code>system/<ins class="diffchange diffchange-inline">initialize</ins>.c</code> <ins class="diffchange diffchange-inline">define and initialize a free list of available memory blocks on the heap. Implement </ins><code>system/<ins class="diffchange diffchange-inline">getmem</ins>.c</code> and <code>system/<ins class="diffchange diffchange-inline">freemem</ins>.c</code> to <ins class="diffchange diffchange-inline">dole out blocks of requested memory and properly maintain </ins>the <ins class="diffchange diffchange-inline">free list. Use First Fit with simple compaction</ins>. (<ins class="diffchange diffchange-inline">Compaction is </ins>the "<ins class="diffchange diffchange-inline">stretch</ins>" <ins class="diffchange diffchange-inline">problem </ins>in <ins class="diffchange diffchange-inline">this assignment -- get everything else working first</ins>.<ins class="diffchange diffchange-inline">)</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">The appropriate data structure for maintaining a list of sleeping processes is a ''delta queue'', as described in lecture. Add a delta queue to the system by increasing </del>the <code><del class="diffchange diffchange-inline">QENT<</del>/<del class="diffchange diffchange-inline">code> constant in <code>include/queue</del>.<del class="diffchange diffchange-inline">h</del></code><del class="diffchange diffchange-inline">, declaring a queue called "sleepq" </del>in <code><del class="diffchange diffchange-inline">include</del>/<del class="diffchange diffchange-inline">clock</del>.<del class="diffchange diffchange-inline">h</del></code><del class="diffchange diffchange-inline">, and and defining and initializing </del><code><del class="diffchange diffchange-inline">sleepq</del></code> <del class="diffchange diffchange-inline">in </del><code>system/<del class="diffchange diffchange-inline">clockinit</del>.c</code><del class="diffchange diffchange-inline">. Make sure </del>to <del class="diffchange diffchange-inline">test your delta queue in isolation before testing the </del><code><del class="diffchange diffchange-inline">sleep</del>()</code> <del class="diffchange diffchange-inline">function</del>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Delete </ins>the <ins class="diffchange diffchange-inline">file </ins><code><ins class="diffchange diffchange-inline">system</ins>/<ins class="diffchange diffchange-inline">getstk</ins>.<ins class="diffchange diffchange-inline">c</ins></code> <ins class="diffchange diffchange-inline">and replace the lone call to this function </ins>in <code><ins class="diffchange diffchange-inline">system</ins>/<ins class="diffchange diffchange-inline">create</ins>.<ins class="diffchange diffchange-inline">c</ins></code> <ins class="diffchange diffchange-inline">with a proper call to </ins><code><ins class="diffchange diffchange-inline">getmem()</ins></code> <ins class="diffchange diffchange-inline">instead. Modify </ins><code>system/<ins class="diffchange diffchange-inline">kill</ins>.c</code> to <ins class="diffchange diffchange-inline">call </ins><code><ins class="diffchange diffchange-inline">freemem</ins>()</code> <ins class="diffchange diffchange-inline">to deallocate a process stack when a process dies</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Grading ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Grading ==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Project credit will be <del class="diffchange diffchange-inline">weighted </del>evenly between <del class="diffchange diffchange-inline">delta queue maintenance</del>, <del class="diffchange diffchange-inline">sleeping</del>, and <del class="diffchange diffchange-inline">waking processes</del>. By now, you should be aware that rigorous testing is the key to success in these projects. Our test cases will include at least:</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Project credit will be <ins class="diffchange diffchange-inline">divvied up </ins>evenly between <ins class="diffchange diffchange-inline">getting memory</ins>, <ins class="diffchange diffchange-inline">freeing memory</ins>, and <ins class="diffchange diffchange-inline">compaction</ins>. By now, you should be aware that rigorous testing is the key to success in these projects. Our test cases will include at least:</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* <del class="diffchange diffchange-inline">Checking </del>your <del class="diffchange diffchange-inline">delta queue insert function with </del>a variety of <del class="diffchange diffchange-inline">parameters</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins class="diffchange diffchange-inline">Verifying that </ins>your <ins class="diffchange diffchange-inline"><code>getmem()</code> and <code>freemem()</code> functions operate correctly over </ins>a variety of <ins class="diffchange diffchange-inline">request sizes</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Checking your <del class="diffchange diffchange-inline">sleeping </del>and <del class="diffchange diffchange-inline">waking functions independently and in concert</del>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Checking your <ins class="diffchange diffchange-inline">memory free list under a wide variety of conditions; if you are not writing a helper function to print out your free list, you are probably not serious about understanding what your system is doing</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Allocating </ins>and <ins class="diffchange diffchange-inline">freeing as much memory as possible, (How can you tell whether you have a memory leak?)</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Verifying that your <code>freemem()</code> compaction works</ins>.</div></td></tr>
</table>Akoehlerhttps://xinu.cs.mu.edu/index.php?title=Assignment:_Heap_Memory&diff=2942&oldid=prevAkoehler: New page: Category:Student Built Xinu = Delta Queues = This assignment is a Xinu assignment allowing the student to grow a more firm understanding of how an operating system works. This assi...2008-12-12T07:31:40Z<p>New page: <a href="/index.php?title=Category:Student_Built_Xinu&action=edit&redlink=1" class="new" title="Category:Student Built Xinu (page does not exist)">Category:Student Built Xinu</a> = Delta Queues = This assignment is a <a href="/index.php/Xinu" title="Xinu">Xinu</a> assignment allowing the student to grow a more firm understanding of how an operating system works. This assi...</p>
<p><b>New page</b></p><div>[[Category:Student Built Xinu]]<br />
= Delta Queues =<br />
This assignment is a [[Xinu]] assignment allowing the student to grow a more firm understanding of how an operating system works. This assignment is part of the [[Student Built Xinu]] track for professors that are [[Teaching With Xinu]]. Your entire working directory containing your Xinu operating system will be submission for this assignment.<br />
== Preparation ==<br />
First, make a fresh copy of your work thus far.<br />
cp -R <old Xinu directory> <new Xinu directory><br />
Untar the new project files on top of this new directory:<br />
tar xvzf <tar-ball location><br />
You should now see the new project files in with your old files. Be certain to make clean before compiling for the first time.<br />
== Sleep ==<br />
Modify <code>system/sleep.c</code>, <code>system/wakeup.c</code>, <code>system/insertd.c</code>, and <code>system/clockintr.c</code> to add the <code>sleep()</code> system call to the operating system. A process that calls <code>sleep(n)</code> should enter the <code>PRSLEEP</code> state for n clock ticks. A clock "tick" is one millisecond in our current system. It corresponds to the raising of the timer interrupt request when interrupts are not disabled. When the clock interrupt handler detects that a process has slept for long enough, the <code>wakeup</code> function should move the process back to the ready list.<br />
<br />
The appropriate data structure for maintaining a list of sleeping processes is a ''delta queue'', as described in lecture. Add a delta queue to the system by increasing the <code>QENT</code> constant in <code>include/queue.h</code>, declaring a queue called "sleepq" in <code>include/clock.h</code>, and and defining and initializing <code>sleepq</code> in <code>system/clockinit.c</code>. Make sure to test your delta queue in isolation before testing the <code>sleep()</code> function.<br />
== Grading ==<br />
Project credit will be weighted evenly between delta queue maintenance, sleeping, and waking processes. By now, you should be aware that rigorous testing is the key to success in these projects. Our test cases will include at least:<br />
* Checking your delta queue insert function with a variety of parameters<br />
* Checking your sleeping and waking functions independently and in concert.</div>Akoehler