THE multiprogramming system

<h2 id="design">Design</h2>
<p>The design of the THE multiprogramming system is significant for its use of a <a href="/facts/Abstraction/p7l9eHGd">layered structure</a>, in which "higher" layers depend on "lower" layers only:
</p>
<ul><li>Layer 0 was responsible for the multiprogramming aspects of the operating system. It decided which process was allocated to the <a href="/facts/Central_processing_unit/Jxp1bqMV">central processing unit</a> (CPU), and accounted for processes that were blocked on <a href="/facts/Semaphore_(programming)/BrE1W4Je">semaphores</a>. It dealt with <a href="/facts/Interrupt/Mm6C4rpc">interrupts</a> and performed the <a href="/facts/Context_switch/N0oJQ6CC">context switches</a> when a process change was needed. This is the lowest level. In modern terms, this was the <a href="/facts/Scheduler/EVTapQ4a">scheduler</a>.</li>
<li>Layer 1 was concerned with <a href="/facts/Memory_management/vthLkUpz">allocating memory</a> to processes. In modern terms, this was the pager.</li>
<li>Layer 2 dealt with communication between the operating system and the <a href="/facts/System_console/FhWph34D">system console</a>.</li>
<li>Layer 3 managed all I/O between the devices attached to the computer. This included buffering information from the various devices.</li>
<li>Layer 4 consisted of <a href="/facts/User_space/0yIzMY8t">user programs</a>. There were 5 processes: in total, they handled the <a href="/facts/Compiler/WNfCDFJe">compiling</a>, <a href="/facts/Execution_(computing)/1fyfGMFm">executing</a>, and <a href="/facts/Printer_(computing)/PnDF2QuF">printing</a> of user programs. When finished, they <a href="/facts/Control_flow/2XTDfErC">passed control</a> back to the schedule <a href="/facts/Queue_(abstract_data_type)/hVPjPXus">queue</a>, which was <a href="/facts/Priority_queue/1uXVo4Uf">priority-based</a>, favoring recently started processes and ones that blocked because of I/O.</li>
<li>Layer 5 was the user; as Dijkstra notes, "not implemented by us".</li></ul>
<p>The constraint that higher layers can only depend on lower layers was imposed by the designers in order to make reasoning about the system (using quasi-<a href="/facts/Formal_methods/tw4FCWIb">formal methods</a>) more tractable, and also to facilitate building and testing the system incrementally. The layers were implemented in order, layer 0 first, with thorough testing of the abstractions provided by each layer in turn. This division of the <a href="/facts/Kernel_(operating_system)/uEj4U3Rz">kernel</a> into layers was similar in some ways to <a href="/facts/Multics/y7A5peyu">Multics</a>' later <a href="/facts/Protection_ring/27y4kjHs">ring-segmentation</a> model. Several subsequent operating systems have used layering to some extent, including <a href="/facts/Windows_NT/EtccWvxQ">Windows NT</a> and <a href="/facts/MacOS/Y93vVpTm">macOS</a>, although usually with fewer layers.
</p><p>The code of the system was written in <a href="/facts/Assembly_language/7XuV0cla">assembly language</a> for the Dutch <a href="/facts/Electrologica_X8/vhYt28ab">Electrologica X8</a> computer. This computer had a <a href="/facts/Word_(computer_architecture)/2e5umRaj">word</a> size of 27 bits, 48 <a href="/facts/Kiloword/2e5umRaj">kilowords</a> of <a href="/facts/Core_memory/4TFIXSNd">core memory</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> 512 kilowords of <a href="/facts/Drum_memory/yul0r8nG">drum memory</a> providing <a href="/facts/Cache_(computing)/gmJYN8wm">backing store</a> for the <a href="/facts/Cache_replacement_policies/LFW5UqPo">LRU cache algorithm</a>, paper tape readers, paper tape punches, plotters, and printers.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/RC_4000_Multiprogramming_System/VSH1DyQj">RC 4000 Multiprogramming System</a></li>
<li><a href="/facts/Ring_(computer_security)/27y4kjHs">Ring (computer security)</a></li>
<li><a href="/facts/Timeline_of_operating_systems/VUkt443G">Timeline of operating systems</a></li>
<li>Source code is available at <a href="http://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/k-1-pdf/k-1-C1063.6-source-THE-os.pdf">http://archive.computerhistory.org/resources/text/Knuth_Don_X4100/PDF_index/k-1-pdf/k-1-C1063.6-source-THE-os.pdf</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Dijkstra, Edsger W. The structure of the 'THE'-multiprogramming system (EWD-196) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription) (Jun 14, 1965) <a href="/wiki/Edsger_W._Dijkstra" target="_blank">/wiki/Edsger_W._Dijkstra</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Dijkstra, E.W. (1968), "The structure of the 'THE'-multiprogramming system", Communications of the ACM, 11 (5): 341–346, doi:10.1145/363095.363143, S2CID 2021311 <a href="/wiki/Edsger_W._Dijkstra" target="_blank">/wiki/Edsger_W._Dijkstra</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Silberschatz, Abraham; Peterson, James L. (May 1988), "13: Historical Perspective", Operating System Concepts, p. 512 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Silberschatz, Abraham; Peterson, James L. (May 1988), "13: Historical Perspective", Operating System Concepts, p. 512 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Silberschatz, Abraham; Peterson, James L. (May 1988), "13: Historical Perspective", Operating System Concepts, p. 512 <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Silberschatz, Abraham; Peterson, James L. (May 1988), "13: Historical Perspective", Operating System Concepts, p. 512 <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Silberschatz, Abraham; Peterson, James L. (May 1988), "13: Historical Perspective", Operating System Concepts, p. 512 <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
</ol>

THE multiprogramming system open-in-new

THE multiprogramming system