home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / toy_os / part01 next >
Internet Message Format  |  1994-09-05  |  61KB
  1. From: oleg@ponder.csci.unt.edu (Kiselyov Oleg)
  2. Newsgroups: comp.sources.misc
  3. Subject: v44i053:  toy_os - yet another OS & hardware emulator, in full C++, Part01/04
  4. Date: 5 Sep 1994 13:18:36 -0500
  5. Organization: University of North Texas
  6. Sender: kent@sparky.sterling.com
  7. Approved: kent@sparky.sterling.com
  8. Message-ID: <csm-v44i053=toy_os.131819@sparky.sterling.com>
  9. Reply-To: oleg@ponder.csci.unt.edu, oleg@unt.edu
  10. Summary: UNIX-like OS running on emulated hardware, in full C++ (cf nachos)
  11. Keywords: Operating System, C++, hardware emulation, nachos
  12. X-Md4-Signature: f79c19cdaeb98dd4979dd7768407678f
  13.  
  14. Submitted-by: oleg@ponder.csci.unt.edu (Kiselyov Oleg)
  15. Posting-number: Volume 44, Issue 53
  16. Archive-name: toy_os/part01
  17. Environment: GNU C++ 2.2
  18.  
  19. Highlights: UNIX-like OS kernel with semaphores, virtual memory and
  20. asynchronous I/O, hardware emulator, "bus" paradigm for both OS and
  21. hardware (classes), extensibility to multi-processor architecture, C++
  22. in full grace.
  23.  
  24. This is yet another UNIX-like (maybe not so toy) operating system,
  25. which operates on the emulated hardware. It was an (extended) class
  26. project, so I wasn't at liberty to choose architecture, the
  27. instruction set, and system calls to implement.
  28.  
  29. The operating system supports a minimal set of multiprocessing system
  30. calls like fork, wait, P and V semaphore operations, and I/O
  31. initiation.  Process scheduling is round-robin with fixed time
  32. quants. A memory manager handles page faults and provides address
  33. translation (for channel instructions), page locking/unlocking, page
  34. reservation, etc.  common memory services. Two different page
  35. replacement strategies were implemented and compared: "swap out" and
  36. "local LRU" (with working set quotas like those in VAX/VMS). I ran a
  37. suite of test "jobs" and compared the number of page faults,
  38. etc. There is a report as to how the two strategies fare (it wasn't
  39. actually a part of the class project, I did it just for the heck of
  40. it). The I/O is asynchronous, that is, an I/O processor (channel) runs
  41. concurrently with the main CPU, there can be several active i/o
  42. requests, and many more may be submitted simultaneously. There are
  43. extensive recording facilities, which print the status of the system
  44. and different units as the system runs.  I have a few full traces of
  45. system runs, but they're too big (and too monotonous) to include in
  46. the submission, please mail me if interested.  Sorry, it's only the
  47. kernel stuff, there is no file system (it wasn't a project requirement -:)
  48.  
  49. The hardware looks suspiciously like IBM/370, though with pure page
  50. virtual memory (not page-segmented), but with several "I/O channels"
  51. that understand their own set of "channel commands" and run
  52. asynchronously with the main CPU. See references below for history of
  53. the project. The hardware emulator is made of classes Memory,
  54. MemoryManagementUnit (to handle the virtual memory), CPU, IOBus,
  55. IOChannel, and devices LinePrinter, CardReader (so quaint -:), and the
  56. HardDisk. The entire project makes a great deal of use of a "bus
  57. architecture" paradigm. Say, on the hardware side, there is a class
  58. "Computer" that holds all units and gives necessary references from
  59. one unit to another at the "construction time". This format makes it a
  60. snap to have a computer with two CPUs "connected" to a single memory
  61. bank, two CPUs with two memory banks, etc.
  62.  
  63. BTW, there is a class Context that holds all CPU registers and other
  64. control info. The class CPU is based on Context, so is a class PCB
  65. (Process Control Block). So, it makes saving/restoring of the CPU
  66. context during a process switch look as a simple assignment.
  67.  
  68. As OS was designed, some (elementary) basic classes have
  69. "precipitated".  One of the fundamental classes is BasicQueue, that
  70. provides _asynchronous_ access to a double-linked list of
  71. QueueLink's. The class lets one do simple searches on id or key (two
  72. int properties of QueueLink), add or delete elements, performing
  73. locking where necessary: it's assumed that several threads may want to
  74. operate a queue "simultaneously".  Other OS classes, like PCB or
  75. Semaphore, are based on QueueLink, so it lets one right upfront queue
  76. PCBs and access them simultaneously.
  77.  
  78. Operating System classes are built upon the hardware classes,
  79. moreover, they mirror the hardware classes.  Say, MemoryManager is
  80. based on Memory, CPUManager is based on the CPU (as well as on
  81. ProcessTable, etc), IOChannelManager is based on the IOChannel. So,
  82. the OS is considered and designed as an "extension" of the
  83. hardware. The class OperatingSystem is based on the class Computer.
  84. It holds all managers and provides for their mutual references, so
  85. it's kind of "software bus". BTW, OperatingSystem is the *only* object
  86. created (in the module bootstrap). All other components are
  87. "physically" parts of the OperatingSystem object and know of each other
  88. through the "bus".
  89.  
  90. Unlike nachos, I used C++ in its full, with very multiple
  91. inheritance (sometimes to the point of breaking the compiler), static
  92. classes, virtual classes, operator/function overloads, etc. That's was
  93. the whole point actually, I bet (literally) that all specific C++
  94. features are very useful in designing the OS. The code is _well_
  95. commented!  I tried to make the OS as fool-proof as possible, so as to
  96. minimize the probability of a misbehaved/malicious process crashing
  97. the OS or seriously affecting other processes.
  98.  
  99. The submission consists of a README file (you're reading it
  100. now), and quite a few source code files. File OS.dr lists all of them
  101. and tells briefly what they're for.
  102.  
  103. I did this project two years ago, so now I would've done a few
  104. things differently. Besides, I spent only 3 weeks (though pretty tough
  105. 3 weeks) implementing the software and "hardware". I even repeated my
  106. personal record of 2,000 lines of *working* C++ code per week.
  107. Anyway, I guess I proved, at least to myself, that C++ in its full
  108. grace is quite useful (and efficient) for the OS design. Actually, I
  109. personally have always taken it for granted, but I was surprised to
  110. come across some people thinking otherwise. As to the OS development,
  111. well, I still have hankering for it. So if something in this project
  112. turns out to be useful in any respect, but some changes/rework seems
  113. necessary, well, I can do it (not overnight, of course, but I'll try -:)
  114.  
  115. References & Credits: The code for vm_unt was originally written in
  116. Modula (called vm_537) at University of Wisconsin-Madison by Raphael
  117. Finkel. The program is adopted into C by Cui-Qing Yang at University
  118. of North Texas.  However, I don't use even a shred of this code, my
  119. implementation is made completely from scratch.  Yet it was mandatory
  120. to implement the same system call format and functionality as in that
  121. system. Sorry, but I had no choice in that.
  122.  
  123. The OS code is using a C thread library: "The Toy Operating System" by
  124. Robert S. Fabry, Computer Science Division, Dept. of Electrical
  125. Engineering and Computer Sciences, University of California, Berkeley
  126. Well, I myself was thinking something along these lines, and even
  127. started to implement my own threads. But then I came across this
  128. library and gave up on mine (hey, it was a class project, time was
  129. kind of tight). Anyway, if somebody wants to try VM UNT and can't get
  130. hold of this threads library, I solemnly promise to implement my ideas
  131. then (and I'll do it in C++).
  132.  
  133. I'm not a frequent reader of this newsgroup, please mail me at
  134. oleg@ponder.csci.unt.edu or oleg@unt.edu should you want to comment.
  135.  
  136. ---------
  137. #! /bin/sh
  138. # This is a shell archive.  Remove anything before this line, then feed it
  139. # into a shell via "sh file" or similar.  To overwrite existing files,
  140. # type "sh file -c".
  141. # Contents:  README c++l cpu.cc cpu_manager.cc mem_manager.cc
  142. # Wrapped by kent@sparky on Mon Sep  5 13:12:54 1994
  143. PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin:$PATH ; export PATH
  144. echo If this archive is complete, you will see the following message:
  145. echo '          "shar: End of archive 1 (of 4)."'
  146. if test -f 'README' -a "${1}" != "-c" ; then 
  147.   echo shar: Will not clobber existing file \"'README'\"
  148. else
  149.   echo shar: Extracting \"'README'\" \(6680 characters\)
  150.   sed "s/^X//" >'README' <<'END_OF_FILE'
  151. XHighlights: UNIX-like OS kernel with semaphores, virtual memory and
  152. Xasynchronous I/O, hardware emulator, "bus" paradigm for both OS and
  153. Xhardware (classes), extensibility to multi-processor architecture, C++
  154. Xin full grace.
  155. X
  156. XThis is yet another UNIX-like (maybe not so toy) operating system,
  157. Xwhich operates on the emulated hardware. It was an (extended) class
  158. Xproject, so I wasn't at liberty to choose architecture, the
  159. Xinstruction set, and system calls to implement.
  160. X
  161. XThe operating system supports a minimal set of multiprocessing system
  162. Xcalls like fork, wait, P and V semaphore operations, and I/O
  163. Xinitiation.  Process scheduling is round-robin with fixed time
  164. Xquants. A memory manager handles page faults and provides address
  165. Xtranslation (for channel instructions), page locking/unlocking, page
  166. Xreservation, etc.  common memory services. Two different page
  167. Xreplacement strategies were implemented and compared: "swap out" and
  168. X"local LRU" (with working set quotas like those in VAX/VMS). I ran a
  169. Xsuite of test "jobs" and compared the number of page faults,
  170. Xetc. There is a report as to how the two strategies fare (it wasn't
  171. Xactually a part of the class project, I did it just for the heck of
  172. Xit). The I/O is asynchronous, that is, an I/O processor (channel) runs
  173. Xconcurrently with the main CPU, there can be several active i/o
  174. Xrequests, and many more may be submitted simultaneously. There are
  175. Xextensive recording facilities, which print the status of the system
  176. Xand different units as the system runs.  I have a few full traces of
  177. Xsystem runs, but they're too big (and too monotonous) to include in
  178. Xthe submission, please mail me if interested.  Sorry, it's only the
  179. Xkernel stuff, there is no file system (it wasn't a project requirement
  180. X-:)
  181. X
  182. XThe hardware looks suspiciously like IBM/370, though with pure page
  183. Xvirtual memory (not page-segmented), but with several "I/O channels"
  184. Xthat understand their own set of "channel commands" and run
  185. Xasynchronously with the main CPU. See references below for history of
  186. Xthe project. The hardware emulator is made of classes Memory,
  187. XMemoryManagementUnit (to handle the virtual memory), CPU, IOBus,
  188. XIOChannel, and devices LinePrinter, CardReader (so quaint -:), and the
  189. XHardDisk. The entire project makes a great deal of use of a "bus
  190. Xarchitecture" paradigm. Say, on the hardware side, there is a class
  191. X"Computer" that holds all units and gives necessary references from
  192. Xone unit to another at the "construction time". This format makes it a
  193. Xsnap to have a computer with two CPUs "connected" to a single memory
  194. Xbank, two CPUs with two memory banks, etc.
  195. X
  196. XBTW, there is a class Context that holds all CPU registers and other
  197. Xcontrol info. The class CPU is based on Context, so is a class PCB
  198. X(Process Control Block). So, it makes saving/restoring of the CPU
  199. Xcontext during a process switch look as a simple assignment.
  200. X
  201. XAs OS was designed, some (elementary) basic classes have
  202. X"precipitated".  One of the fundamental classes is BasicQueue, that
  203. Xprovides _asynchronous_ access to a double-linked list of
  204. XQueueLink's. The class lets one do simple searches on id or key (two
  205. Xint properties of QueueLink), add or delete elements, performing
  206. Xlocking where necessary: it's assumed that several threads may want to
  207. Xoperate a queue "simultaneously".  Other OS classes, like PCB or
  208. XSemaphore, are based on QueueLink, so it lets one right upfront queue
  209. XPCBs and access them simultaneously.
  210. X
  211. XOperating System classes are built upon the hardware classes,
  212. Xmoreover, they mirror the hardware classes.  Say, MemoryManager is
  213. Xbased on Memory, CPUManager is based on the CPU (as well as on
  214. XProcessTable, etc), IOChannelManager is based on the IOChannel. So,
  215. Xthe OS is considered and designed as an "extension" of the
  216. Xhardware. The class OperatingSystem is based on the class Computer.
  217. XIt holds all managers and provides for their mutual references, so
  218. Xit's kind of "software bus". BTW, OperatingSystem is the *only* object
  219. Xcreated (in the module bootstrap). All other components are
  220. X"physically" parts of the OperatingSystem object and know of each other
  221. Xthrough the "bus".
  222. X
  223. X    Unlike nachos, I used C++ in its full, with very multiple
  224. Xinheritance (sometimes to the point of breaking the compiler), static
  225. Xclasses, virtual classes, operator/function overloads, etc. That's was
  226. Xthe whole point actually, I bet (literally) that all specific C++
  227. Xfeatures are very useful in designing the OS. The code is _well_
  228. Xcommented!  I tried to make the OS as fool-proof as possible, so as to
  229. Xminimize the probability of a misbehaved/malicious process crashing
  230. Xthe OS or seriously affecting other processes.
  231. X
  232. X    The submission consists of a README file (you're reading it
  233. Xnow), and quite a few source code files. File OS.dr lists all of them
  234. Xand tells briefly what they're for.
  235. X
  236. X    I did this project two years ago, so now I would've done a few
  237. Xthings differently. Besides, I spent only 3 weeks (though pretty tough
  238. X3 weeks) implementing the software and "hardware". I even repeated my
  239. Xpersonal record of 2,000 lines of *working* C++ code per week.
  240. XAnyway, I guess I proved, at least to myself, that C++ in its full
  241. Xgrace is quite useful (and efficient) for the OS design. Actually, I
  242. Xpersonally have always taken it for granted, but I was surprised to
  243. Xcome across some people thinking otherwise. As to the OS development,
  244. Xwell, I still have hankering for it. So if something in this project
  245. Xturns out to be useful in any respect, but some changes/rework seems
  246. Xnecessary, well, I can do it (not overnight, of course, but I'll try
  247. X-:)
  248. X
  249. XReferences & Credits: The code for vm_unt was originally written in
  250. XModula (called vm_537) at University of Wisconsin-Madison by Raphael
  251. XFinkel. The program is adopted into C by Cui-Qing Yang at University
  252. Xof North Texas.  However, I don't use even a shred of this code, my
  253. Ximplementation is made completely from scratch.  Yet it was mandatory
  254. Xto implement the same system call format and functionality as in that
  255. Xsystem. Sorry, but I had no choice in that.
  256. X
  257. XThe OS code is using a C thread library: "The Toy Operating System" by
  258. XRobert S. Fabry, Computer Science Division, Dept. of Electrical
  259. XEngineering and Computer Sciences, University of California, Berkeley
  260. XWell, I myself was thinking something along these lines, and even
  261. Xstarted to implement my own threads. But then I came across this
  262. Xlibrary and gave up on mine (hey, it was a class project, time was
  263. Xkind of tight). Anyway, if somebody wants to try VM UNT and can't get
  264. Xhold of this threads library, I solemnly promise to implement my ideas
  265. Xthen (and I'll do it in C++).
  266. X
  267. XShould you want to comment, please mail me at oleg@ponder.csci.unt.edu
  268. Xor oleg@unt.edu. I'd appreciate that!
  269. END_OF_FILE
  270.   if test 6680 -ne `wc -c <'README'`; then
  271.     echo shar: \"'README'\" unpacked with wrong size!
  272.   fi
  273.   # end of 'README'
  274. fi
  275. if test -f 'c++l' -a "${1}" != "-c" ; then 
  276.   echo shar: Will not clobber existing file \"'c++l'\"
  277. else
  278.   echo shar: Extracting \"'c++l'\" \(313 characters\)
  279.   sed "s/^X//" >'c++l' <<'END_OF_FILE'
  280. X#!/bin/csh
  281. X#    GNU C++ linking
  282. X/usr/local/bin/gcc -O -pipe -W -Wall -Wpointer-arith -Wenum-clash -Woverloaded-virtual \
  283. X-Wstrict-prototypes -Wmissing-prototypes \
  284. X-finline-functions  -fforce-mem -funsigned-char \
  285. X-fforce-addr -fomit-frame-pointer \
  286. X-L{$HOME}/croot/c++serv \
  287. X$* -lserv -liostream -liberty -lg++ -lm
  288. END_OF_FILE
  289.   if test 313 -ne `wc -c <'c++l'`; then
  290.     echo shar: \"'c++l'\" unpacked with wrong size!
  291.   fi
  292.   # end of 'c++l'
  293. fi
  294. if test -f 'cpu.cc' -a "${1}" != "-c" ; then 
  295.   echo shar: Will not clobber existing file \"'cpu.cc'\"
  296. else
  297.   echo shar: Extracting \"'cpu.cc'\" \(7459 characters\)
  298.   sed "s/^X//" >'cpu.cc' <<'END_OF_FILE'
  299. X// This may look like C code, but it is really -*- C++ -*-
  300. X/*
  301. X ************************************************************************
  302. X *
  303. X *               UNT Virtual Machine
  304. X *             Central Processing Unit
  305. X *
  306. X * The present file implemements a central processing unit, i.e. emulates
  307. X * all the operations the "regular" CPU would perform.
  308. X * Once started, the CPU runs until it gets stopped or trap occures. In
  309. X * the latter case, 'trap_signal' is raised so the trap handler can
  310. X * wake up and handle the trap. The trap handler is not a part of CPU,
  311. X * though, and runs as a separate thread within the "hardware".
  312. X *
  313. X ************************************************************************
  314. X */
  315. X
  316. X#pragma implementation
  317. X#include "hardware.h"
  318. X#include "myenv.h"
  319. X#include <std.h>
  320. X
  321. X/*
  322. X *------------------------------------------------------------------------
  323. X *                  Initialization
  324. X */
  325. X
  326. Xint _ebx_save;                // newproc() spoils %ebx on the
  327. X                    // second return. So we have to
  328. X                    // save it.
  329. X
  330. XCentralProcessingUnit::CentralProcessingUnit(Memory& _memory)
  331. X    : MemoryManagementUnit(_memory),
  332. X      stopped("CPU operation",0),
  333. X      trap_signal("CPU trap",0)
  334. X{
  335. X  pc = 0;
  336. X  clock = -1;
  337. X  trap_code = NONE;
  338. X
  339. X//  message("\ntrap_signal ptr %x, val =%x",&trap_signal,*(int *)&trap_signal);
  340. X  asm("movl %ebx,__ebx_save");        // Saving %ebx. It's a shame we need
  341. X                    // to resort to such a kludge!
  342. X  if( !newproc("CPU process",1) )
  343. X  {                    // This is a main CPU process
  344. X    for(;;)
  345. X    {
  346. X      stopped--;            // Wait until can run again
  347. X      if( execute_instruction() )
  348. X    stopped++;            // If everything was fine, keep going
  349. X      else
  350. X    trap_signal++;
  351. X    }
  352. X  }
  353. X
  354. X  asm("movl __ebx_save,%ebx");        // Restore %ebx. I wish I didn't
  355. X                    // have to do this!
  356. X//  message("\ntrap_signal ptr %x, val =%x",&trap_signal,*(int *)&trap_signal);
  357. X}
  358. X
  359. X/*
  360. X *------------------------------------------------------------------------
  361. X *              Starting and stopping the CPU
  362. X */
  363. X
  364. Xvoid CentralProcessingUnit::start(void)
  365. X{
  366. X  if( !is_running() )
  367. X    single_message("CPU: has been stopped, starting..."),
  368. X    stopped++;
  369. X  else
  370. X    single_message("CPU: already running");
  371. X}
  372. X
  373. Xvoid CentralProcessingUnit::stop(void)
  374. X{
  375. X  if( is_running() )
  376. X    single_message("CPU: has been running, stopping..."),
  377. X    stopped--;
  378. X  else
  379. X    single_message("CPU: already stopped");
  380. X}
  381. X
  382. X/*
  383. X *------------------------------------------------------------------------
  384. X *           Emulates a single CPU operation
  385. X *       Fetch an instruction at current pc and execute it
  386. X * Returns 0 if trap or other interrupt has occurred that makes continuation
  387. X * useless. Otherwise returns 1.
  388. X * Note, that pc always points to the instruction following the one
  389. X * which has been executed or which has caused the interrupt.
  390. X *
  391. X */
  392. X
  393. Xint CentralProcessingUnit::execute_instruction(void)
  394. X{
  395. X  trap_code = NONE;
  396. X
  397. X  if( clock == 0 )            // Handle the clock and generate
  398. X  {                    // interrupt if necessary
  399. X    trap_code = CLOCKINT;        // (Clock is to turn negative)
  400. X    --clock;
  401. X    return 0;
  402. X  }
  403. X  else if( clock > 0 )
  404. X    --clock;
  405. X
  406. X  inst_length = 0;                // Fetch and examine the
  407. X  pc++; inst_length++;                // 1st word of the instruction
  408. X  if( *(Word *)&iword1 = fetch(pc-1), got_fault() )
  409. X  {
  410. X    trap_code = MEMORY;
  411. X    pc -= inst_length;                // Set pc to repeat the 
  412. X    return 0;                    // operation after recovery
  413. X  }
  414. X  opcode = (OpCodes)iword1.opcode;
  415. X  Word& reg_a = (*this)[iword1.areg];
  416. X  Word  reg_b = (*this)[iword1.breg];
  417. X  EA = 0;
  418. X  if( opcode >= TWO_WORD )
  419. X  {                    // Fetch the second word of instruction
  420. X    ++pc, ++inst_length;
  421. X    if( *(Word *)&iword2 = fetch(pc-1), got_fault() )
  422. X    {
  423. X      trap_code = MEMORY;
  424. X      pc -= inst_length;            // Set pc to repeat the 
  425. X      return 0;                    // operation after recovery
  426. X    }
  427. X    EA = iword2.ea;
  428. X                    // Fetch the indirect address
  429. X    if( iword2.indirect && (EA = get(EA), got_fault() ) )
  430. X    {
  431. X      trap_code = MEMORY;
  432. X      pc -= inst_length;            // Set pc to repeat the 
  433. X      return 0;                    // operation after recovery
  434. X    }
  435. X    if( iword1.breg != 0 )        // Add the index to the address
  436. X      EA += reg_b;
  437. X  }
  438. X
  439. X                // Print the trace info
  440. X  begin_printing();
  441. X  message("\nCPU: Executing instruction");
  442. X  message("\n  PC  Clock Opcode Areg Breg  R(Areg) R(Breg) SvcOp Ind   EA"
  443. X      "  C(EA)"
  444. X      "\n%4ob %3d    %2d    %2d   %2d    %06o  %06o",
  445. X      pc-inst_length,clock,opcode,iword1.areg,iword1.breg,
  446. X      reg_a,reg_b);
  447. X  if( opcode >= TWO_WORD )
  448. X    message("    %2d   %1d %4ob %06o",iword2.svcop,iword2.indirect,EA,
  449. X        get(EA)), clear_error();    // Clear possible error due to get()
  450. X  message("\n");
  451. X  end_printing();
  452. X
  453. X                // Interpret the instruction
  454. X  switch( opcode )
  455. X  {
  456. X    case HALT:
  457. X         trap_code = ILLEGOP;
  458. X     return 0;
  459. X
  460. X    case DUMP:
  461. X     Context::dump();
  462. X     dump_phys_memory(reg_a,reg_b);
  463. X     break;
  464. X
  465. X    case LOADR:
  466. X     reg_a = reg_b;
  467. X     break;
  468. X
  469. X    case ADD:
  470. X         reg_a += reg_b;
  471. X     break;
  472. X
  473. X    case SUBT:
  474. X         reg_a -= reg_b;
  475. X     break;
  476. X
  477. X    case MULT:
  478. X         reg_a *= reg_b;
  479. X     break;
  480. X
  481. X    case DIV:
  482. X     if( reg_b != 0 )
  483. X       reg_a /= reg_b;
  484. X     break;
  485. X
  486. X    case AND:
  487. X         reg_a &= reg_b;
  488. X     break;
  489. X
  490. X    case OR:
  491. X         reg_a |= reg_b;
  492. X     break;
  493. X
  494. X    case XOR:
  495. X         reg_a ^= reg_b;
  496. X     break;
  497. X
  498. X    case SHIFTL:
  499. X         reg_a <<= reg_b;
  500. X     break;
  501. X
  502. X    case SHIFTR:
  503. X         reg_a >>= reg_b;
  504. X     break;
  505. X
  506. X    case NOP:
  507. X     break;
  508. X
  509. X    case IOPR:
  510. X         trap_code = ILLEGOP;
  511. X     return 0;
  512. X
  513. X    case LOAD:
  514. X     register Word ea_cont = get(EA);
  515. X     if( got_fault() )
  516. X     {
  517. X       trap_code = MEMORY;
  518. X       pc -= inst_length;            // Set pc to repeat the 
  519. X       return 0;                // operation after recovery
  520. X     }
  521. X     reg_a = ea_cont;
  522. X     break;
  523. X
  524. X    case LOADI:
  525. X     reg_a = EA;
  526. X     break;
  527. X
  528. X    case STORE:
  529. X     if( put(EA,reg_a), got_fault() )
  530. X     {
  531. X       trap_code = MEMORY;
  532. X       pc -= inst_length;            // Set pc to repeat the 
  533. X       return 0;                // operation after recovery
  534. X     }
  535. X     break;
  536. X
  537. X    case BR:
  538. X     pc = EA;
  539. X     break;
  540. X
  541. X    case BRNEG:
  542. X     if( reg_a < 0 )
  543. X       pc = EA;
  544. X     break;
  545. X
  546. X    case BRZERO:
  547. X     if( reg_a == 0 )
  548. X       pc = EA;
  549. X     break;
  550. X
  551. X    case BRPOS:
  552. X     if( reg_a > 0 )
  553. X       pc = EA;
  554. X     break;
  555. X
  556. X    case BRSUBR:
  557. X     reg_a = pc;
  558. X     pc = EA;
  559. X     break;
  560. X
  561. X    case READ:
  562. X    case WRITE:
  563. X         trap_code = ILLEGOP;
  564. X     return 0;
  565. X
  566. X    case SVC:
  567. X     svcop = iword2.svcop;
  568. X         trap_code = SVCCALL;
  569. X     return 0;
  570. X
  571. X    default:
  572. X         trap_code = ILLEGOP;
  573. X     return 0;
  574. X  }
  575. X  return 1;
  576. X}
  577. X
  578. X
  579. X/*
  580. X *------------------------------------------------------------------------
  581. X *                Dump the context
  582. X */
  583. X
  584. Xvoid CentralProcessingUnit::dump(void) const
  585. X{
  586. X  Context::dump();
  587. X  MemoryManagementUnit::dump();
  588. X}
  589. X
  590. Xvoid Context::dump(void) const
  591. X{
  592. X  register int i;
  593. X  message("\n\t\t\tContext Dump\n");
  594. X  message("\n   R0     R1     R2     R3     R4     R5     R6     R7\n");
  595. X  for(i=0; i<=7; i++)
  596. X    message(" %06o",Registers[i]);
  597. X  message("\n\n   R8     R9     R10    R11   R12    R13    R14    R15\n");
  598. X  for(i=8; i<=15; i++)
  599. X    message(" %06o",Registers[i]);
  600. X  message("\n\nPC = %06o\n\n",pc);
  601. X}
  602. X
  603. X/*
  604. X *------------------------------------------------------------------------
  605. X *             Processor context functions
  606. X */
  607. X
  608. X                // Clean up the context at the very beginning
  609. XContext::Context(void)
  610. X{
  611. X  memset(Registers,0,sizeof(Registers));
  612. X  pc = 0;
  613. X}
  614. X
  615. X                // Get ref to a given register
  616. XWord& Context::operator [] (const int reg_number)
  617. X{
  618. X  assure( reg_number >= 0 && reg_number <= 15, "Bad register no" );
  619. X  return Registers[reg_number];
  620. X}
  621. X
  622. X                // Copy the context from another one
  623. Xvoid Context::copy_context(const Context& a_context)
  624. X{
  625. X  memcpy(this,&a_context,sizeof(Context));
  626. X}
  627. X
  628. X
  629. END_OF_FILE
  630.   if test 7459 -ne `wc -c <'cpu.cc'`; then
  631.     echo shar: \"'cpu.cc'\" unpacked with wrong size!
  632.   fi
  633.   # end of 'cpu.cc'
  634. fi
  635. if test -f 'cpu_manager.cc' -a "${1}" != "-c" ; then 
  636.   echo shar: Will not clobber existing file \"'cpu_manager.cc'\"
  637. else
  638.   echo shar: Extracting \"'cpu_manager.cc'\" \(18467 characters\)
  639.   sed "s/^X//" >'cpu_manager.cc' <<'END_OF_FILE'
  640. X// This may look like C code, but it is really -*- C++ -*-
  641. X/*
  642. X ************************************************************************
  643. X *
  644. X *               UNT Virtual Machine
  645. X *
  646. X *         This is the core of the operating system
  647. X *
  648. X * The functions defined in the present file are executed within the
  649. X * TRAP-handler thread that gets control if CPU raised the trap signal.
  650. X * While CPU is stopped during the trap handling, the trap thread
  651. X * handles traps and system requests (SVC traps) and performs all the
  652. X * high level process scheduling.
  653. X *
  654. X ************************************************************************
  655. X */
  656. X
  657. X#pragma implementation "cpu_manager.h"
  658. X#include "cpu_manager.h"
  659. X#include "io_manager.h"
  660. X#include "myenv.h"
  661. X
  662. X/*
  663. X *------------------------------------------------------------------------
  664. X *            Initializing the operating system
  665. X */
  666. X
  667. XCPUManager::CPUManager(CentralProcessingUnit& _CPU,
  668. X               MemoryManager& _mem_manager,IOManager& _io_manager)
  669. X    : CPU(_CPU),
  670. X      memory_manager(_mem_manager),
  671. X      io_manager(_io_manager),
  672. X      Halt("Computer halt",0),
  673. X      ProcessTable(20)
  674. X{
  675. X  semas = new SemaphoreTable(20);
  676. X  running_pcb = 0;
  677. X  if( !newproc("TRAP handling",1) )
  678. X  {                    // This is a CPU trap handler
  679. X    for(;;)
  680. X    {
  681. X      CPU.wait_for_trap();        // Wait for the trap
  682. X      if( trap_handler(CPU.q_trap_code()) == DISPATCH )
  683. X    dispatch();
  684. X      CPU.start();
  685. X    }
  686. X  }
  687. X}
  688. X
  689. X
  690. X                // Load a program from the drum and run it
  691. Xvoid CPUManager::commence(void)
  692. X{
  693. X  int no_programs = memory_manager.q_no_programs();
  694. X  console("There are %d programs on the drum to run",no_programs);
  695. X  register int i;
  696. X  for(i=0; i<no_programs; i++)
  697. X  {
  698. X    PCB& pcb = (*this)[new_pid()];
  699. X    pcb.brand_new();
  700. X    pcb.pc = memory_manager.load_program(pcb,i);
  701. X    readyPCBs.append(pcb);
  702. X  }
  703. X  dispatch();
  704. X  CPU.start();
  705. X}
  706. X
  707. X/*
  708. X *------------------------------------------------------------------------
  709. X *                TRAP handler
  710. X */
  711. X
  712. XHANDLER_STATUS
  713. XCPUManager::trap_handler(const CentralProcessingUnit::TRAPCODE trap_code)
  714. X{
  715. X  save_context();            // Save the CPU context anyway
  716. X  switch(trap_code)
  717. X  {
  718. X    case CentralProcessingUnit::ILLEGOP:
  719. X         if( CPU.q_opcode() == HALT )
  720. X       console("Current process has terminated normally (by HALT)");
  721. X     else if( CPU.q_opcode() == READ || CPU.q_opcode() == WRITE )
  722. X       return initiate_IO(CPU.q_opcode(),CPU.q_EA());
  723. X     else
  724. X       console("Illegal operation (dec code %d)",CPU.q_opcode());
  725. X     return terminate();
  726. X    
  727. X    case CentralProcessingUnit::SVCCALL:
  728. X     return svc_handler((SVCCODE)CPU.q_svcop());
  729. X
  730. X    case CentralProcessingUnit::CLOCKINT:
  731. X     single_message("Clock Interrupt");
  732. X     if( readyPCBs.is_empty() )
  733. X       return RESUME;        // We've got only a single process
  734. X     readyPCBs.append(*running_pcb);
  735. X     return DISPATCH;        // Else pick up smth else
  736. X
  737. X    case CentralProcessingUnit::MEMORY:
  738. X     return mfault_handler(CPU.what_fault());
  739. X
  740. X    default:
  741. X         _error("FATAL: Trap handler has been entered with illegal "
  742. X        "trap code %d",trap_code);
  743. X  }
  744. X  return DISPATCH;
  745. X}
  746. X
  747. X/*
  748. X *------------------------------------------------------------------------
  749. X *                SVC Handler
  750. X */
  751. X
  752. XHANDLER_STATUS CPUManager::svc_handler(const SVCCODE svc_code)
  753. X{
  754. X  single_message("SVC interrupt %d",svc_code);
  755. X  switch(svc_code)
  756. X  {
  757. X    case DUMP_STATUS:            // Dump the OS status
  758. X         dump();
  759. X         return RESUME;
  760. X    
  761. X    case FORK:                // Fork a process.
  762. X                    // reg_a := PID of a kid or parent
  763. X     return fork(CPU.q_RegA(),CPU.q_EA());    // EA = start address of a kid
  764. X
  765. X    case WAIT_KIDS:            // Wait for kid processes to terminate
  766. X     return wait_for_kids();
  767. X
  768. X    case SEMINIT:            // Create a semaphor for a process
  769. X         return create_semaphore(CPU.q_RegA(),CPU.q_EA());
  770. X
  771. X    case SEM_P:                // P-operation on semaphore
  772. X     return semaphore_p((SID)CPU[CPU.q_RegA()]);
  773. X
  774. X    case SEM_V:                // V-operation on semaphore
  775. X     return semaphore_v((SID)CPU[CPU.q_RegA()]);
  776. X
  777. X    case KILL:                // Try to kill the process
  778. X     return shoot((PID)CPU[CPU.q_RegA()]);
  779. X
  780. X    default:
  781. X         console("Illegal SVC call %d, program is being tossed out",
  782. X         svc_code);
  783. X     return terminate();
  784. X  }
  785. X  return DISPATCH;
  786. X}
  787. X
  788. X/*
  789. X *------------------------------------------------------------------------
  790. X *          Elementary process scheduling functions
  791. X */
  792. X
  793. X                // Prepare the process for running
  794. X                // on the CPU
  795. Xvoid CPUManager::prepare_for_running(void)
  796. X{
  797. X  assert( running_pcb != 0 );
  798. X  assert( !CPU.is_running() );
  799. X  (*running_pcb).load_context(CPU);
  800. X  CPU.clock = Time_quant;
  801. X}
  802. X
  803. X                // Save the status of the currently
  804. X                // running process as the process is
  805. X                // going to lose the CPU control
  806. Xvoid CPUManager::save_context(void)
  807. X{
  808. X  assert( running_pcb != 0 );
  809. X  assert( !CPU.is_running() );
  810. X  (*running_pcb).save_context(CPU);
  811. X}
  812. X
  813. X                // Terminate the currently running process
  814. XHANDLER_STATUS CPUManager::terminate(void)
  815. X{
  816. X  console("Terminating the process PID %d",running_pcb->id);
  817. X  (*running_pcb).dump();
  818. X  kill(*running_pcb);
  819. X  return DISPATCH;            // Pick up a new process to run
  820. X}
  821. X
  822. X                // Pick up a new process to run and make
  823. X                // it current
  824. Xvoid CPUManager::dispatch(void)
  825. X{
  826. X  if( q_all_free() )            // Check if all processes are trough
  827. X    Halt++;                
  828. X  running_pcb = &(*this)[readyPCBs.get_from_head()->id]; // Implies waiting
  829. X  single_message("Dispatchung process %d...",running_pcb->id);
  830. X  prepare_for_running();
  831. X}
  832. X
  833. X/*
  834. X *------------------------------------------------------------------------
  835. X *              Dump whatever goes on in the system
  836. X */
  837. X
  838. Xvoid CPUManager::dump(void)
  839. X{
  840. X  begin_printing();
  841. X  message("\n%s\n\n\t\t\tOperating System Status\n",_Minuses);
  842. X  message("\nCurrent process\n");
  843. X  (*running_pcb).dump();
  844. X  ProcessTable::dump();
  845. X  (*semas).dump();
  846. X  memory_manager.dump_status();
  847. X  io_manager.dump();
  848. X  end_printing();
  849. X}
  850. X
  851. X/*
  852. X *------------------------------------------------------------------------
  853. X *               Making new processes
  854. X */
  855. X
  856. X                // Create a child process at EA of
  857. X                // the currently running process
  858. X                // Put PID of the son into the parent rega,
  859. X                // and PID of the parent into the son rega
  860. XHANDLER_STATUS CPUManager::fork(const int rega,Address EA)
  861. X{
  862. X  assert( running_pcb != 0 );
  863. X  if( running_pcb -> lchild != NIL_pid && running_pcb -> rchild != NIL_pid )
  864. X  {
  865. X    console("ABEND: attempt to create the 3d child");
  866. X    return terminate();
  867. X  }
  868. X
  869. X  PID son_id = new_pid();
  870. X  if( son_id == NIL_pid )
  871. X  {
  872. X    console("ABEND: can't create a process - too many are running");
  873. X    return terminate();
  874. X  }
  875. X
  876. X  PCB& son_pcb = (*this)[son_id];
  877. X  PCB& dad_pcb = *running_pcb;
  878. X  single_message("Creating a child %d for a parent %d",son_pcb.id,dad_pcb.id);
  879. X
  880. X  son_pcb.fork_from_dad(dad_pcb);
  881. X  son_pcb[rega] = dad_pcb.id;
  882. X  son_pcb.pc    = EA;
  883. X
  884. X  dad_pcb[rega] = son_pcb.id;
  885. X
  886. X  if( !memory_manager.fork_son((MMContext&)son_pcb,(const MMContext&)dad_pcb) )
  887. X  {                    // If some problem occurred during  
  888. X    kill(son_pcb);            // memory allocation for the son
  889. X    return RESUME;
  890. X  }
  891. X  
  892. X  readyPCBs.append(dad_pcb);
  893. X  readyPCBs.append(son_pcb);
  894. X  return DISPATCH;
  895. X}
  896. X
  897. X                // Wait until all the kids of the
  898. X                // running process are through.
  899. X                // Return RESUME if the running process
  900. X                // has got no kids.
  901. XHANDLER_STATUS CPUManager::wait_for_kids(void)
  902. X{
  903. X  assert( running_pcb != 0 );
  904. X  if( running_pcb->lchild == NIL_pid && running_pcb->rchild == NIL_pid )
  905. X    return RESUME;                // No kids
  906. X  running_pcb->status = PCB::Wait_for_kids;    // The PCB remains unqueued
  907. X  return DISPATCH;
  908. X}
  909. X
  910. X                // Try to kill the process
  911. XHANDLER_STATUS CPUManager::shoot(const PID pid)
  912. X{
  913. X  single_message("An attempt to shoot a process %d",pid);
  914. X  if( pid == running_pcb->id )
  915. X  {
  916. X    console("The current process %d shot himself",pid);
  917. X    return terminate();
  918. X  }
  919. X
  920. X  if( pid == NIL_pid )
  921. X  {
  922. X    console("An attempt to kill a nonexistent process");
  923. X    return terminate();
  924. X  }
  925. X
  926. X  if( pid != running_pcb->lchild && pid != running_pcb->rchild )
  927. X  {
  928. X    console("Process %d has no right to shoot %d",running_pcb->id,pid);
  929. X    return terminate();
  930. X  }
  931. X
  932. X  PCB& victim = (*this)[pid];
  933. X  if( victim.status == PCB::Doing_io )
  934. X    victim.status = PCB::Shall_die;
  935. X
  936. X  kill(victim);
  937. X  return RESUME;
  938. X}
  939. X
  940. X/*
  941. X *------------------------------------------------------------------------
  942. X *                Kill the process
  943. X * The program performs the clean-up and releases all the resources
  944. X * that process occupied.
  945. X *     - Kids are terminated
  946. X *     - Parent is notified and turned ready if has been waiting
  947. X *     - Owned semaphores are destroyed and all the processes being 
  948. X *      waiting on it are terminated
  949. X *     - the process is purged of all semaphore waiting lists if
  950. X *      it has been waiting on P operation
  951. X *    - dispose of the memory of the deseased process
  952. X */
  953. X
  954. Xvoid CPUManager::kill(PCB& pcb)
  955. X{
  956. X  assert(pcb.status != PCB::Dead);
  957. X
  958. X  readyPCBs.purge_id(pcb.id);        // Purge from the ready queue
  959. X                    // (if any)
  960. X  if( pcb.lchild != NIL_pid )
  961. X    kill((*this)[pcb.lchild]);
  962. X
  963. X  if( pcb.rchild != NIL_pid )
  964. X    kill((*this)[pcb.rchild]);
  965. X
  966. X  if( pcb.parent != NIL_pid )
  967. X  {
  968. X    PCB& dad_pcb = (*this)[pcb.parent];
  969. X    if( dad_pcb.lchild == pcb.id )
  970. X      dad_pcb.lchild = NIL_pid;
  971. X    else if( dad_pcb.rchild == pcb.id )
  972. X      dad_pcb.rchild = NIL_pid;
  973. X    else
  974. X      _error("FATAL: parent doesn't know of his son");
  975. X
  976. X                // If dad has been waiting for kids, it may go
  977. X    if( dad_pcb.lchild == NIL_pid && dad_pcb.rchild == NIL_pid &&
  978. X       dad_pcb.status == PCB::Wait_for_kids )
  979. X      dad_pcb.status = PCB::Ok,
  980. X      readyPCBs.append(dad_pcb);
  981. X    pcb.parent = NIL_pid;
  982. X  }
  983. X
  984. X                    // Release all owned semaphores
  985. X  SID sid;
  986. X  while( (sid = (*semas).owned_by(pcb.id)) != NIL_sid )
  987. X  {
  988. X    (*semas).dispose(sid);
  989. X  }
  990. X
  991. X  if( pcb.status == PCB::Wait_on_sema )
  992. X    (*semas).purge(pcb.id);
  993. X
  994. X  memory_manager.dispose((MMContext&)pcb);
  995. X  dispose(pcb.id);
  996. X}
  997. X
  998. X/*
  999. X *------------------------------------------------------------------------
  1000. X *            Processes and Semaphores
  1001. X */
  1002. X                // Create a new semaphore with initial value EA
  1003. X                // Put SID in rega
  1004. X                // Return RESUME if everything is fine
  1005. XHANDLER_STATUS CPUManager::create_semaphore(const int rega,Address EA)
  1006. X{
  1007. X  assert( running_pcb != 0 );
  1008. X
  1009. X  SID semid = (*semas).new_semaphore(EA,running_pcb->id);
  1010. X  if( semid == NIL_sid )
  1011. X  {
  1012. X    console("ABEND: Can't create a semaphore - too many are in use");
  1013. X    return terminate();
  1014. X  }
  1015. X
  1016. X  single_message("Semaphore %d (in_value %d) has been allocated for PID %d",
  1017. X         semid,EA,running_pcb->id);
  1018. X
  1019. X  CPU[rega] = semid;
  1020. X  return RESUME;
  1021. X}
  1022. X
  1023. X                // Check to see that the Sema is valid
  1024. X                // to perform P or V operation on.
  1025. X                // It should be active and belong to
  1026. X                // the running process or its ancestor
  1027. XSema * CPUManager::valid_semaphore(const SID sid)
  1028. X{
  1029. X  if( !(*semas).is_active(sid) )
  1030. X    return 0;
  1031. X  Sema& sem = (*semas)[sid];
  1032. X  PID owner = sem.q_owner();            // Check ownership
  1033. X  PID id    = running_pcb->id;            // through the chain of
  1034. X  for(; id != NIL_pid; id = (*this)[id].parent)    // ancestorship
  1035. X    if( id == owner )
  1036. X      return &sem;
  1037. X  return 0;
  1038. X}
  1039. X
  1040. X                // Semaphore P-operation
  1041. X                // Return RESUME if the process is to
  1042. X                // be resumed
  1043. XHANDLER_STATUS CPUManager::semaphore_p(const SID sid)
  1044. X{
  1045. X  single_message("\nP-operation on semaphore %d",sid);
  1046. X  assert( running_pcb != 0 );
  1047. X  Sema * semp;
  1048. X  if( (semp = valid_semaphore(sid)) == 0 )
  1049. X  {
  1050. X    console("Semaphore %d may not be used by process %d",sid,
  1051. X        running_pcb->id);
  1052. X    return terminate();
  1053. X  }
  1054. X
  1055. X  if( !(*semp).p(*running_pcb) )
  1056. X  {                    // Suspend the current process
  1057. X    single_message("Process %d should wait on semaphore %d",
  1058. X           running_pcb->id,sid);
  1059. X    running_pcb->status = PCB::Wait_on_sema;
  1060. X    return DISPATCH;
  1061. X  }  
  1062. X
  1063. X  return RESUME;
  1064. X}
  1065. X
  1066. X
  1067. X                // Semaphore V-operation
  1068. X                // Return RESUME if the process is to
  1069. X                // be resumed
  1070. XHANDLER_STATUS CPUManager::semaphore_v(const SID sid)
  1071. X{
  1072. X  single_message("V-operation on semaphore %d",sid);
  1073. X  assert( running_pcb != 0 );
  1074. X  Sema * semp;
  1075. X  if( (semp = valid_semaphore(sid)) == 0 )
  1076. X  {
  1077. X    console("Semaphore %d may not be used by process %d",sid,
  1078. X        running_pcb->id);
  1079. X    return terminate();
  1080. X  }
  1081. X
  1082. X  PID pid_to_wake;
  1083. X  if( (pid_to_wake = (*semp).v()) != NIL_pid )
  1084. X  {                    // Wake up pid_to_wake
  1085. X    single_message("Process %d is being woken up",pid_to_wake);
  1086. X    PCB& pcb_to_wake = (*this)[pid_to_wake];
  1087. X    pcb_to_wake.status = PCB::Ok;
  1088. X    readyPCBs.append(pcb_to_wake);
  1089. X  }  
  1090. X
  1091. X  return RESUME;
  1092. X}
  1093. X
  1094. X/*
  1095. X *------------------------------------------------------------------------
  1096. X *            Preliminary Memory Fault Handling
  1097. X * Advance memory handling is done by the MemoryManager
  1098. X */
  1099. X
  1100. XHANDLER_STATUS CPUManager::mfault_handler
  1101. X    (const MemoryManagementUnit::MemoryFault code)
  1102. X{
  1103. X  MMUContext::VirtualMemoryAddr culprit_VA = CPU.q_current_VA();
  1104. X
  1105. X  switch(code)
  1106. X  {
  1107. X    case MemoryManagementUnit::OutofRange:
  1108. X         console("ABEND: Virtual address %o is out of range",culprit_VA);
  1109. X     return terminate();
  1110. X
  1111. X    case MemoryManagementUnit::WrongPageTable:
  1112. X         console("ABEND: Page table has wrong format for VA %o",culprit_VA);
  1113. X     return terminate();
  1114. X
  1115. X    case MemoryManagementUnit::WrongVPageNo:
  1116. X         console("ABEND: Wrong virtual page number in VA %o",culprit_VA);
  1117. X     return terminate();
  1118. X
  1119. X    case MemoryManagementUnit::PageInvalidated:
  1120. X     break;                    // Try to handle that
  1121. X
  1122. X    case MemoryManagementUnit::NoAccess:
  1123. X         console("ABEND: Access to the virtual page denied, VA %o",culprit_VA);
  1124. X     return terminate();
  1125. X
  1126. X    case MemoryManagementUnit::ReadOnly:
  1127. X         console("ABEND: May not write to a read-only page, VA %o",culprit_VA);
  1128. X     return terminate();
  1129. X
  1130. X    case MemoryManagementUnit::ExecOnly:
  1131. X         console("ABEND: EXEConly page may only be fetched, VA %o",culprit_VA);
  1132. X     return terminate();
  1133. X
  1134. X    default:
  1135. X     _error("FATAL: unknown memory fault %d, cannot handle",code);
  1136. X  }
  1137. X
  1138. X  single_message("Missing the page at VA %6o",*(Address*)&culprit_VA);
  1139. X
  1140. X                    // We've access to the page not in
  1141. X                    // the physical memory. Try to bring
  1142. X                    // it to there
  1143. X  enum {Begin, Blocked, Ready} swap_status = Begin;
  1144. X  for(;;)
  1145. X    switch(memory_manager.load_the_page((MMContext&)*running_pcb,culprit_VA))
  1146. X    {
  1147. X      case MemoryManager::Ok:
  1148. X           CPU.clear_error();
  1149. X           (*running_pcb).load_context(CPU);
  1150. X           return RESUME;
  1151. X
  1152. X      case MemoryManager::PhysMemoryExhausted:
  1153. X       message("\nMemory exhausted: ");
  1154. X       PID victim_pid;
  1155. X       switch(swap_status)
  1156. X       {
  1157. X         case Begin:
  1158. X              start_scan();
  1159. X          swap_status = Blocked;
  1160. X
  1161. X         case Blocked:
  1162. X          if( (victim_pid = next_pcb(ProcessTable::Blocked)) 
  1163. X              != NIL_pid )
  1164. X          {
  1165. X            PCB& pcb = (*this)[victim_pid];
  1166. X            message("Blocked PID %d is to be swapped out",victim_pid);
  1167. X            memory_manager.swap_out((MMContext&)pcb);
  1168. X            continue;
  1169. X          }
  1170. X              start_scan();
  1171. X          swap_status = Ready;
  1172. X          
  1173. X         case Ready:
  1174. X          if( (victim_pid = next_pcb(ProcessTable::Ready))
  1175. X              != NIL_pid )
  1176. X          {
  1177. X            if( victim_pid == running_pcb->id )
  1178. X              continue;
  1179. X            PCB& pcb = (*this)[victim_pid];
  1180. X            message("Ready PID %d is to be swapped out",victim_pid);
  1181. X            memory_manager.swap_out((MMContext&)pcb);
  1182. X            continue;
  1183. X          }
  1184. X          console("We've tried hard enough, but there is no "
  1185. X              "free physical memory");
  1186. X          return terminate();
  1187. X       }
  1188. X       break;
  1189. X
  1190. X      case MemoryManager::LethalFault:
  1191. X       return terminate();
  1192. X    }
  1193. X}
  1194. X
  1195. X/*
  1196. X *------------------------------------------------------------------------
  1197. X *    The following utilities help handle the parameter block
  1198. X * the process has prepared in the memory
  1199. X * They operate in the current process virtual memory. Page table is
  1200. X * assumed to be loaded.
  1201. X * The program return FALSE if some problem occured. Usually it is the
  1202. X * reason for process termination.
  1203. X */
  1204. X
  1205. X                // Read a word from the (virtual)
  1206. X                // address space of a current process
  1207. Xint CPUManager::read_word(const Address va, Word& dest)
  1208. X{
  1209. X  if( dest = CPU.get(va), CPU.got_fault() )
  1210. X    if( mfault_handler(CPU.what_fault()) != RESUME )
  1211. X      return 0;                // Incorrectable memory fault
  1212. X
  1213. X  if( dest = CPU.get(va), CPU.got_fault() )
  1214. X    return 0;                // Second fault - also bad
  1215. X  return 1;
  1216. X}
  1217. X
  1218. X                // Write a word to the (virtual)
  1219. X                // address space of a current process
  1220. Xint CPUManager::write_word(const Address va, Word src)
  1221. X{
  1222. X  if( CPU.put(va,src), CPU.got_fault() )
  1223. X    if( mfault_handler(CPU.what_fault()) != RESUME )
  1224. X      return 0;                // Incorrectable memory fault
  1225. X
  1226. X  if( CPU.put(va,src), CPU.got_fault() )
  1227. X    return 0;                // Second fault - also bad
  1228. X  return 1;
  1229. X}
  1230. X                // Lock the page of the current process
  1231. X                // at the specified VA
  1232. Xint CPUManager::lock_page(Address va)
  1233. X{
  1234. X                    // First, try to read this address
  1235. X                    // and load the page if necessary
  1236. X  if( CPU.get(va), CPU.got_fault() )
  1237. X    if( CPU.what_fault() != MemoryManagementUnit::PageInvalidated || 
  1238. X        mfault_handler(CPU.what_fault()) != RESUME )
  1239. X      return 0;                // Incorrectable memory fault
  1240. X  return memory_manager.lock_loaded_page((MMContext&)*running_pcb,va);
  1241. X}
  1242. X
  1243. X                // Unlock the page of a given process
  1244. X                // at the specified VA
  1245. Xvoid CPUManager::unlock_page(const PID pid,Address va)
  1246. X{
  1247. X  memory_manager.unlock_page((MMContext&)(*this)[pid],va);
  1248. X}
  1249. X
  1250. X                // Translate the virtual address to physical
  1251. X                // one using the translation tables of the
  1252. X                // running process
  1253. X                // running process. The page has to be loaded
  1254. X                // Returns 0 if fails
  1255. XAddress CPUManager::translate_va(Address va)
  1256. X{
  1257. X  return memory_manager.translate_va((MMContext&)*running_pcb,va);
  1258. X}
  1259. X
  1260. X                // Read/write a word from/to the 
  1261. X                // PHYSICAL address space
  1262. X                // Error is fatal
  1263. Xvoid CPUManager::read_word_phys_memory(const Address ra, Word& dest)
  1264. X{
  1265. X  Memory::MemoryAnswer ans = CPU.memory[ra];
  1266. X  if( ans.out_of_range )
  1267. X    _error("CPU reading phys memory failed at %o",ra);
  1268. X  dest = ans.contents;
  1269. X}
  1270. X
  1271. Xvoid CPUManager::write_word_phys_memory(const Address ra, Word src)
  1272. X{
  1273. X  Memory::MemoryAnswer ans = CPU.memory[ra];
  1274. X  if( ans.out_of_range )
  1275. X    _error("CPU writing phys memory failed at %o",ra);
  1276. X  ans.contents = src;
  1277. X}
  1278. X
  1279. X/*
  1280. X *------------------------------------------------------------------------
  1281. X *            Initiate the Input/Output
  1282. X * The following program performs only preliminary I/O initiation
  1283. X */
  1284. X
  1285. XHANDLER_STATUS CPUManager::initiate_IO(const OpCodes opcode,Address IO_params)
  1286. X{
  1287. X  single_message("Processing I/O parameters");
  1288. X  if( !io_manager.submit_request(running_pcb->id,opcode,IO_params) )
  1289. X    return terminate();
  1290. X  running_pcb->status = PCB::Doing_io;
  1291. X  return DISPATCH;
  1292. X}
  1293. X
  1294. X                // Post the completion of the I/O request
  1295. Xvoid CPUManager::io_request_completed(const PID pid)
  1296. X{
  1297. X  PCB& pcb = (*this)[pid];
  1298. X  assert( pcb.status == PCB::Doing_io );
  1299. X  pcb.status = PCB::Ok;
  1300. X  readyPCBs.append(pcb);
  1301. X}
  1302. END_OF_FILE
  1303.   if test 18467 -ne `wc -c <'cpu_manager.cc'`; then
  1304.     echo shar: \"'cpu_manager.cc'\" unpacked with wrong size!
  1305.   fi
  1306.   # end of 'cpu_manager.cc'
  1307. fi
  1308. if test -f 'mem_manager.cc' -a "${1}" != "-c" ; then 
  1309.   echo shar: Will not clobber existing file \"'mem_manager.cc'\"
  1310. else
  1311.   echo shar: Extracting \"'mem_manager.cc'\" \(16274 characters\)
  1312.   sed "s/^X//" >'mem_manager.cc' <<'END_OF_FILE'
  1313. X// This may look like C code, but it is really -*- C++ -*-
  1314. X/*
  1315. X ************************************************************************
  1316. X *
  1317. X *               UNT Virtual Machine
  1318. X *
  1319. X *             High Level Virtual Memory Manager
  1320. X *
  1321. X * This is a high-level extension of the memory unit, and uses paging to
  1322. X * manage memory requests of processes.
  1323. X * Page selection is on demand, that's the page isn't loaded until it is 
  1324. X * missed by the CPU to complete the execution of an instruction.
  1325. X *
  1326. X * The present version supports the working set concept and an approximate
  1327. X * LRU page replacement strategy. Working set of a process is a set of
  1328. X * all pages that are currently referenced (mapped, i.e. loaded into
  1329. X * the physical memory) by the process. In other words, it is the set of
  1330. X * pages the process is working with. Working set quota limits the number
  1331. X * of the pages the process is allowed to have mapped. If the working set
  1332. X * is filled up to the quota, yet the process needs (demands) one more page,
  1333. X * one page of the working set should be unreferenced (and swapped out if
  1334. X * it has been modified) before the request to map new page is served. 
  1335. X * To decide which page to unmap, an approximate LRU page replacement
  1336. X * strategy is used. 
  1337. X * It means, the algorithm will try to find the least recently used page
  1338. X * of the working set and push it out. To figure out which page has been
  1339. X * used least recently, the memory context of the process keeps a time-since-
  1340. X * last-access count of the page usage. When the process gets control
  1341. X * of the CPU and its page table gets loaded into the hardware, was_ref
  1342. X * bit of every page is dropped. When the CPU accesses memory, the memory
  1343. X * hardware sets the was_ref bit of the accessed page. When the process
  1344. X * loses control of the CPU (because it runs into the blocking condition,
  1345. X * or because it exhausted its time slice), the time-since-last-access
  1346. X * count for all the pages that haven't been accessed during that
  1347. X * process run is incremented. Therefore, the larger the count, the
  1348. X * least recently the page has been accessed (used). Note, since 
  1349. X * process switchings out occure non-uniformly (the process loses
  1350. X * the CPU control not only because of the time click, but also because
  1351. X * of blocking), the LRU count is only approximately correct. Yet,
  1352. X * interrupts in the real system occur quite regularly, so this
  1353. X * approximation seems fairly accurate.
  1354. X *
  1355. X ************************************************************************
  1356. X */
  1357. X
  1358. X#pragma implementation
  1359. X#include "mem_manager.h"
  1360. X
  1361. X#include "myenv.h"
  1362. X#include <std.h>
  1363. X
  1364. XMemoryManager::MemoryManager(Memory& _physical_memory)
  1365. X    : physical_memory(_physical_memory),
  1366. X      virtual_space(_physical_memory,(Memory::hiaddr+1)/Memory::pagesize,
  1367. X            Memory::no_drum_sectors)
  1368. X{
  1369. X  no_programs = 0;
  1370. X}
  1371. X
  1372. X
  1373. X                // Read the drum header and tell the
  1374. X                // number of programs on the drum
  1375. Xint MemoryManager::q_no_programs(void)
  1376. X{
  1377. X  virtual_space.declare_page_private(0);
  1378. X  physical_memory.drum_read(0,PageFrameTable::sys_page_frame);
  1379. X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
  1380. X  register Address curr_address = base_address;
  1381. X  no_programs = physical_memory[curr_address++].contents;
  1382. X  assert( no_programs > 0 && no_programs <= max_no_programs );
  1383. X  register int i;
  1384. X  for(i=0; i<no_programs; i++)
  1385. X    prog_descriptors[i].pc = physical_memory[curr_address++].contents,
  1386. X    prog_descriptors[i].mem_map = physical_memory[curr_address++].contents;
  1387. X
  1388. X  return no_programs;
  1389. X}
  1390. X
  1391. X
  1392. Xvoid MemoryManager::dump_status(void) const
  1393. X{
  1394. X  virtual_space.dump_status();
  1395. X}
  1396. X
  1397. X/*
  1398. X *------------------------------------------------------------------------
  1399. X *               Servicing memory requests of a process
  1400. X */
  1401. X
  1402. X                // Initializing all areas
  1403. XMMContext::MMContext(void)
  1404. X{
  1405. X  register int i;
  1406. X  for(i=0; i<process_virtual_space; i++)
  1407. X    vm_map[i] = NIL_vpn;
  1408. X  memset(page_table,0,sizeof(page_table));
  1409. X  memset(time_since_last_ref,0,sizeof(time_since_last_ref));
  1410. X  no_mapped_pages = 0;
  1411. X  no_page_faults = 0;
  1412. X}
  1413. X
  1414. X                // Given vm_map, map of the process virtual
  1415. X                // space, construct the page table
  1416. Xvoid MMContext::build_page_table(const VirtualPageTable& virtual_space)
  1417. X{
  1418. X  register int i;
  1419. X  for(i=0; i<process_virtual_space; i++)
  1420. X  {
  1421. X    PageTableEntry& pte = page_table[i];
  1422. X    pte.valid = pte.was_ref = pte.was_written = 0;
  1423. X    if( vm_map[i] == NIL_vpn )        // The page hasn't been allocated
  1424. X      pte.any_access = pte.read_only = pte.exec_only = 0;
  1425. X    else
  1426. X    {
  1427. X      pte.any_access = 1;        // The page has been allocated
  1428. X      const VirtualPage& vp = virtual_space[vm_map[i]];
  1429. X      pte.exec_only = vp.q_data_page() ? 0 : 1;
  1430. X      if( vp.page_frame != NIL_pfn)
  1431. X    pte.phys_page_no = vp.page_frame,// The page is mapped
  1432. X    pte.valid = 1;
  1433. X    }
  1434. X  }
  1435. X}
  1436. X
  1437. X
  1438. X                // Load the context to the MMU
  1439. X                // Note, the referenced bit for every page
  1440. X                // in the page table is cleared to
  1441. X                // find out which pages are going to be
  1442. X                // accessed during the time the process
  1443. X                // is running on CPU
  1444. Xvoid MMContext::load_MMU(MemoryManagementUnit& mmu)
  1445. X{
  1446. X  memcpy((MMUContext *)&mmu,this,sizeof(MMUContext));
  1447. X                    // Load the page table
  1448. X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
  1449. X  assert( page_table_len <= process_virtual_space );
  1450. X  assert( page_table_len <= Memory::pagesize );
  1451. X
  1452. X  register int i;
  1453. X  for(i=0; i<page_table_len; i++)
  1454. X  {
  1455. X    PageTableEntry& pte = page_table[i];
  1456. X    pte.was_ref = 0;            // Clear the ref bit
  1457. X    *(PageTableEntry *)&(mmu.memory[base_address+i].contents) = pte;
  1458. X  }
  1459. X  mmu.clear_error();
  1460. X}
  1461. X
  1462. X                // Save the MMU context
  1463. X                // Was_written/was_referenced fields in the
  1464. X                // page_table might have been changed. This
  1465. X                // needs to be saved. The referenced bit 
  1466. X                // is used to find out which pages have been
  1467. X                // actually accessed, and to increment counter
  1468. X                // for the pages that haven't been used
  1469. Xvoid MMContext::save_MMU(const MemoryManagementUnit& mmu)
  1470. X{
  1471. X                    // Save the page table
  1472. X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
  1473. X  assert( page_table_len <= process_virtual_space );
  1474. X  assert( page_table_len <= Memory::pagesize );
  1475. X
  1476. X  register int i;
  1477. X  for(i=0; i<page_table_len; i++)
  1478. X  {
  1479. X    const PageTableEntry& pte =
  1480. X      *(PageTableEntry *)&(mmu.memory[base_address+i].contents);
  1481. X    if( pte.valid && !pte.was_ref )
  1482. X      time_since_last_ref[i]++;
  1483. X    page_table[i] = pte;
  1484. X  }
  1485. X}
  1486. X
  1487. X                // Dump whatever's in there
  1488. Xvoid MMContext::dump(void) const
  1489. X{
  1490. X  if( !enabled_address_translation )
  1491. X  {
  1492. X    message("\nVirtual memory is disabled for this process\n");
  1493. X    return;
  1494. X  }
  1495. X
  1496. X  message("\nProcess virtual space is %d pages long",page_table_len);
  1497. X  message("\nWorking set size %d, working set quota %d\n",no_mapped_pages,
  1498. X      working_set_quota);
  1499. X  message("\nAddress range\tAccess\tMapped to   Drum sector"
  1500. X      "\tWritten\tReferenced LRU time\n");
  1501. X  register int i;
  1502. X  for(i=0; i<page_table_len; i++)
  1503. X  {
  1504. X    const PageTableEntry& pte = page_table[i];
  1505. X    if( !(pte.any_access || pte.read_only || pte.exec_only) )
  1506. X      continue;                    // Page isn't allocated
  1507. X    message("%06o-%06o \t %s\t",Memory::pagesize*i,Memory::pagesize*(i+1)-1,
  1508. X        pte.exec_only ? "Exec" : pte.read_only ? "Read" : "Any");
  1509. X    if( pte.valid )
  1510. X      message("%06o  ",pte.phys_page_no*Memory::pagesize);
  1511. X    else
  1512. X      message("Not Mapped ");
  1513. X    message("\t%d\t   %s\t    %s",vm_map[i],pte.was_written ? "Y" : "N",
  1514. X        pte.was_ref ? "Y" : "N");
  1515. X    if( pte.valid )
  1516. X      message("         %d\n",time_since_last_ref[i]);
  1517. X    else
  1518. X      message("\n");
  1519. X  }
  1520. X  message("\nProcess has %d page faults\n\n",no_page_faults);
  1521. X}
  1522. X
  1523. X                    // Load program and return starting PC
  1524. XAddress MemoryManager::load_program
  1525. X    (MMContext& context,const unsigned int prog_no)
  1526. X{
  1527. X  assure(prog_no < (unsigned)no_programs, 
  1528. X     "FATAL: an attempt to load nonexistent program");
  1529. X  ProgDescr& prog_descr = prog_descriptors[prog_no];
  1530. X                    // Read the memory map from the drum
  1531. X  virtual_space.declare_page_private((VPN)prog_descr.mem_map);
  1532. X  physical_memory.drum_read((VPN)prog_descr.mem_map,
  1533. X                PageFrameTable::sys_page_frame);
  1534. X                    // Set up the vm_map and page_table
  1535. X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
  1536. X  register int i;
  1537. X  for(i=0; i<MMContext::process_virtual_space; i++)
  1538. X  {
  1539. X    assert( i < Memory::pagesize );
  1540. X    int drum_sector_no = physical_memory[base_address+i].contents;
  1541. X    if( drum_sector_no == -1 )
  1542. X      context.vm_map[i] = NIL_vpn;
  1543. X    else
  1544. X    {
  1545. X      virtual_space.declare_page_private((VPN)drum_sector_no);
  1546. X      if( !is_text_segment(i) )
  1547. X    virtual_space[(VPN)drum_sector_no].declare_data_page();
  1548. X      context.vm_map[i] = drum_sector_no;
  1549. X    }
  1550. X  }
  1551. X
  1552. X  context.build_page_table(virtual_space);
  1553. X  context.no_page_faults = 0;
  1554. X  context.no_mapped_pages = 0;
  1555. X  memset(context.time_since_last_ref,0,sizeof(context.time_since_last_ref));
  1556. X
  1557. X  context.page_table_addr = PageFrameTable::sys_page_frame*Memory::pagesize;
  1558. X  context.page_table_len  = MMContext::process_virtual_space;
  1559. X  context.enabled_address_translation = 1;
  1560. X
  1561. X  return prog_descr.pc;
  1562. X}
  1563. X
  1564. X                // Take care of son's virtual space
  1565. X                // Return FALSE if we've got some problem
  1566. Xint MemoryManager::fork_son
  1567. X    (MMContext& son_context,const MMContext& dad_context)
  1568. X{
  1569. X                    // Check is everything's in real memory
  1570. X  if( !dad_context.enabled_address_translation )
  1571. X  {
  1572. X    son_context.enabled_address_translation = 0;
  1573. X    return 1;
  1574. X  }
  1575. X                      // Set up the vm_map
  1576. X  register int i;
  1577. X  son_context.no_mapped_pages = 0;
  1578. X  for(i=0; i<MMContext::process_virtual_space; i++)
  1579. X  {
  1580. X    VPN dad_vpn = dad_context.vm_map[i];
  1581. X    if( dad_vpn == NIL_vpn )
  1582. X    {
  1583. X      son_context.vm_map[i] = NIL_vpn;
  1584. X      continue;
  1585. X    }
  1586. X
  1587. X    const VirtualPage& dad_vp = virtual_space[dad_vpn];
  1588. X    if( !dad_vp.q_data_page() )
  1589. X    {                    // Code text page, to be shared
  1590. X      virtual_space.allocate(dad_vpn);
  1591. X      son_context.vm_map[i] = dad_vpn;
  1592. X      if( dad_vp.is_mapped() )        // Son would also refer to the
  1593. X    virtual_space.reference(dad_vpn),    // dad's mapped pages
  1594. X        son_context.no_mapped_pages++;
  1595. X      continue;
  1596. X    }
  1597. X
  1598. X    VPN son_vpn = virtual_space.allocate();
  1599. X    if( son_vpn == NIL_vpn )
  1600. X    {
  1601. X      console("No virtual space for the son process. It has to be killed");
  1602. X      return 0;
  1603. X    }
  1604. X
  1605. X    son_context.vm_map[i] = son_vpn;
  1606. X    virtual_space[son_vpn].declare_data_page();
  1607. X    virtual_space.copy(son_vpn,dad_vpn);
  1608. X  }
  1609. X
  1610. X  son_context.build_page_table(virtual_space);
  1611. X  son_context.no_page_faults = 0;
  1612. X  memset(son_context.time_since_last_ref,0,
  1613. X     sizeof(son_context.time_since_last_ref));
  1614. X
  1615. X  son_context.page_table_addr = 
  1616. X    PageFrameTable::sys_page_frame*Memory::pagesize;
  1617. X  son_context.page_table_len  = MMContext::process_virtual_space;
  1618. X  son_context.enabled_address_translation = 1;
  1619. X
  1620. X  return 1;
  1621. X}
  1622. X
  1623. X                // Serve the request to bring a virtual page
  1624. X                // into the real memory
  1625. XMemoryManager::MMAnswer MemoryManager::load_the_page
  1626. X    (MMContext& context,MMUContext::VirtualMemoryAddr culprit_VA)
  1627. X{
  1628. X  unsigned int page_no = culprit_VA.page_no;
  1629. X  assert( page_no < (unsigned)context.page_table_len );
  1630. X  VPN vpn = context.vm_map[page_no];
  1631. X
  1632. X  if( context.no_mapped_pages >= context.working_set_quota )
  1633. X    replace_LRU_page(context);
  1634. X
  1635. X  PFN pfn = virtual_space.reference(vpn);
  1636. X  if( pfn == NIL_pfn )
  1637. X    return PhysMemoryExhausted;
  1638. X  context.no_mapped_pages++;
  1639. X  VirtualPage& vp = virtual_space[context.vm_map[page_no]];
  1640. X  
  1641. X  if( !vp.is_shared_mapped() )
  1642. X    context.no_page_faults++;        // The page has been physically loaded
  1643. X  else                    // The page might have been loaded by
  1644. X    if( vp.q_data_page() )        // siblings (if it's shared)
  1645. X      _error("Non-shared data page %d turns out to be loaded into frame %d",
  1646. X         vp.id,vp.page_frame);
  1647. X
  1648. X  MMUContext::PageTableEntry& pte = context.page_table[page_no];
  1649. X  pte.phys_page_no = vp.page_frame;
  1650. X  pte.valid = 1;
  1651. X  context.time_since_last_ref[page_no] = 0;
  1652. X  return Ok;
  1653. X}
  1654. X
  1655. X                    // Release the virtual memory
  1656. X                    // occupied by the process
  1657. Xvoid MemoryManager::dispose(MMContext& context)
  1658. X{
  1659. X  if( !context.enabled_address_translation )
  1660. X    return;                // No virtual memory was occupied
  1661. X  register int i;
  1662. X  for(i=0; i<MMContext::process_virtual_space; i++)
  1663. X  {
  1664. X    VPN vpn = context.vm_map[i];
  1665. X    if( vpn == NIL_vpn )
  1666. X      continue;
  1667. X    MMUContext::PageTableEntry& pte = context.page_table[i];
  1668. X    if( pte.valid )
  1669. X      virtual_space.unreference(vpn,0),
  1670. X      context.no_mapped_pages--;
  1671. X    virtual_space.dispose(vpn);
  1672. X    context.vm_map[i] = NIL_vpn;
  1673. X  }
  1674. X  assert(context.no_mapped_pages == 0);
  1675. X  memset(context.time_since_last_ref,0,sizeof(context.time_since_last_ref));
  1676. X  context.no_page_faults = 0;
  1677. X  context.page_table_addr = 0;
  1678. X  context.page_table_len  = 0;
  1679. X  context.enabled_address_translation = 0;
  1680. X}
  1681. X
  1682. X                // Swap out a victim - forcibly deprive it
  1683. X                // of mapped pages
  1684. X                // Return 0 if no page frame was released
  1685. X                // Swapping goals were not achieved
  1686. Xint MemoryManager::swap_out(MMContext& context)
  1687. X{
  1688. X  message("\nSwapping out...");
  1689. X  if( !context.enabled_address_translation )
  1690. X    return 0;                // No virtual memory was occupied
  1691. X  register int i;
  1692. X  int swapped_something = 0;
  1693. X  for(i=0; i<MMContext::process_virtual_space; i++)
  1694. X  {
  1695. X    VPN vpn = context.vm_map[i];
  1696. X    if( vpn == NIL_vpn )
  1697. X      continue;
  1698. X    VirtualPage& vp = virtual_space[vpn];
  1699. X    MMUContext::PageTableEntry& pte = context.page_table[i];
  1700. X    if( !pte.valid )            // The page wasn't accessed by us yet
  1701. X      continue;                // (if it was allocated at all)
  1702. X    assert( pte.phys_page_no == vp.page_frame );
  1703. X    virtual_space.unreference(vpn,pte.was_written);
  1704. X    context.no_mapped_pages--;
  1705. X    pte.valid = 0;
  1706. X    pte.was_ref = pte.was_written = 0;
  1707. X    swapped_something = 1;
  1708. X  }
  1709. X  assert(context.no_mapped_pages == 0);
  1710. X  return swapped_something;
  1711. X}
  1712. X
  1713. X                // Run the LRU page replacement strategy 
  1714. X                // to find out the least referenced page
  1715. X                // and push it out
  1716. Xvoid MemoryManager::replace_LRU_page(MMContext& context)
  1717. X{
  1718. X  int max_counter = -1;
  1719. X  int page_victim = -1;
  1720. X  register int i;
  1721. X  for(i=0; i<MMContext::process_virtual_space; i++)
  1722. X    if(context.page_table[i].valid &&
  1723. X       context.time_since_last_ref[i] > max_counter)
  1724. X      max_counter = context.time_since_last_ref[i],
  1725. X      page_victim = i;
  1726. X
  1727. X  assert( page_victim >= 0 );
  1728. X  VPN vpn = context.vm_map[page_victim];
  1729. X  message("\nFound LRU page %d, time since last used %d",vpn,max_counter);
  1730. X
  1731. X  MMUContext::PageTableEntry& pte = context.page_table[page_victim];
  1732. X  assert( pte.valid );
  1733. X  virtual_space.unreference(vpn,pte.was_written);
  1734. X  context.no_mapped_pages--;
  1735. X  pte.valid = 0;
  1736. X  pte.was_ref = pte.was_written = 0;
  1737. X}
  1738. X
  1739. X                // Lock the page that contains the
  1740. X                // specified virtual address. The page
  1741. X                // should be already mapped
  1742. X                // Return FALSE if failed
  1743. Xint MemoryManager::lock_loaded_page(MMContext& context,const Address addr)
  1744. X{
  1745. X  if( !context.enabled_address_translation )
  1746. X    return 0;                // Virtual memory is disabled
  1747. X  
  1748. X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
  1749. X  unsigned int page_no = va.page_no;
  1750. X  assert( page_no < (unsigned)context.page_table_len );
  1751. X  VPN vpn = context.vm_map[page_no];
  1752. X
  1753. X  virtual_space.lock(vpn);
  1754. X  return 1;
  1755. X}
  1756. X
  1757. X                // Unlock the page that contains the
  1758. X                // specified virtual address. The page
  1759. X                // should be already mapped & locked
  1760. Xvoid MemoryManager::unlock_page(MMContext& context,const Address addr)
  1761. X{
  1762. X  assert( context.enabled_address_translation );
  1763. X  
  1764. X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
  1765. X  unsigned int page_no = va.page_no;
  1766. X  assert( page_no < (unsigned)context.page_table_len );
  1767. X  VPN vpn = context.vm_map[page_no];
  1768. X
  1769. X  virtual_space.unlock(vpn);
  1770. X}
  1771. X
  1772. X                // Translate the virtual address to physical
  1773. X                // one. The page has to be loaded.
  1774. X                // Returns 0 if fails
  1775. XAddress MemoryManager::translate_va(MMContext& context,const Address addr)
  1776. X{
  1777. X  if( !context.enabled_address_translation )
  1778. X    return addr;                // Virtual memory is disabled
  1779. X  
  1780. X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
  1781. X  unsigned int page_no = va.page_no;
  1782. X  if( page_no >= (unsigned)context.page_table_len )
  1783. X    return 0;                    // Out of range
  1784. X  const MMUContext::PageTableEntry& pte = context.page_table[page_no];
  1785. X  if( !pte.any_access )
  1786. X    return 0;                    // No access
  1787. X  if( !pte.valid )
  1788. X    return 0;                    // Not mapped
  1789. X  va.page_no = pte.phys_page_no;
  1790. X
  1791. X  return *(Address *)&va;
  1792. X}
  1793. END_OF_FILE
  1794.   if test 16274 -ne `wc -c <'mem_manager.cc'`; then
  1795.     echo shar: \"'mem_manager.cc'\" unpacked with wrong size!
  1796.   fi
  1797.   # end of 'mem_manager.cc'
  1798. fi
  1799. echo shar: End of archive 1 \(of 4\).
  1800. cp /dev/null ark1isdone
  1801. MISSING=""
  1802. for I in 1 2 3 4 ; do
  1803.     if test ! -f ark${I}isdone ; then
  1804.     MISSING="${MISSING} ${I}"
  1805.     fi
  1806. done
  1807. if test "${MISSING}" = "" ; then
  1808.     echo You have unpacked all 4 archives.
  1809.     rm -f ark[1-9]isdone
  1810. else
  1811.     echo You still must unpack the following archives:
  1812.     echo "        " ${MISSING}
  1813. fi
  1814. exit 0
  1815. exit 0 # Just in case...
  1816.