home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume44 / toy_os / part03 / mem_manager.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-05  |  8.5 KB  |  268 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *               UNT Virtual Machine
  6.  *
  7.  *           Real, Virtual and Swap memory manager
  8.  *                  Data structures
  9.  *
  10.  * The concept of the working set is now supported. See mem_manager.cc
  11.  * for details.
  12.  *
  13.  ************************************************************************
  14.  */
  15.  
  16. #ifndef _mem_manager_h
  17. #define _mem_manager_h 1
  18. #pragma interface
  19.  
  20. #include "hardware.h"
  21. #include "sysqueues.h"
  22.  
  23. /*
  24.  *------------------------------------------------------------------------
  25.  *            Managing pages of physical memory
  26.  */
  27.  
  28. typedef unsigned short PFN;        // Page Frame No 
  29. const PFN NIL_pfn = (unsigned)(-1);
  30.  
  31. class PageFrameTable;
  32.  
  33.                 // Note, QueueLink.id is the page frame no
  34. class PageFrame : public QueueLink
  35. {
  36.   friend class PageFrameTable;
  37.  
  38. public:
  39.   PageFrame(void); 
  40.   ~PageFrame(void) {}
  41. };
  42.  
  43. class PageFrameTable
  44. {
  45.   const int no_page_frames;
  46.   PageFrame * page_frames;
  47.   
  48.   BasicQueue freePFs;
  49.  
  50. public:
  51.   const int sys_page_frame = 0;        // Permanently allocated to OS
  52.  
  53.   PageFrameTable(const int no_phys_pages);
  54.   ~PageFrameTable(void) {}
  55.  
  56.                 // Get a Page Frame given its no
  57.   PageFrame& operator [] (const PFN pfn) const;
  58.   PFN allocate(void);        // Allocate a new physical page, return NIL
  59.                 // if no physical page is available
  60.   void dispose(const PFN pfn);    // Dispose of a given page
  61.   void dump_status(void) const;    // Print info about physical memory allocation
  62. };
  63.  
  64. /*
  65.  *------------------------------------------------------------------------
  66.  *            Managing pages of virtual memory
  67.  * Virtual space of the system is essentially the collection of drum sectors
  68.  * (pages). Therefore, virtual page number is exactly the drum sector
  69.  * number. A virtual page may be free or allocated (to one or several
  70.  * processes if it is a code page shared between the processes), may exist
  71.  * only on the drum or loaded to the physical memory into some page frame.
  72.  * If the page is shared between several processes, it might be mapped
  73.  * (actually referenced or accessed) by all or only several of them.
  74.  * Virtual pages of the program images that were inserted on the drum
  75.  * by the linker (task builder) are declared private, in that they are
  76.  * never put into the free list (even if the process that uses them is
  77.  * over), i.e. the contents of the private page is preserved. It implies
  78.  * the same drum file can be used in different runs of VM UNT.
  79.  * The mapped page may be locked, it means the page remains mapped until
  80.  * it is unlocked explicitly; this feature is used primarily to make sure
  81.  * that the pages needed for I/O would would not suddenly get swapped
  82.  * in the middle of I/O. Locking is implemented as increasing the reference
  83.  * counter and setting the 'locked_page' bit. Note that the locked page
  84.  * may be locked again (without any effect, though).
  85.  *
  86.  */
  87.  
  88. typedef unsigned short VPN;        // (Virtual) Page No 
  89. const VPN NIL_vpn = (unsigned)(-1);
  90.  
  91. class VirtualPageTable;
  92.  
  93.                 // Note, QueueLink.id is the VPN
  94. class VirtualPage : public QueueLink
  95. {
  96.   friend class VirtualPageTable;
  97.   
  98.   short own_count;            // How many processes own this page
  99.   short ref_count;            // How many processes are actually
  100.                     // using, i.e. accessing this page
  101.   unsigned char 
  102.       private_page  : 1,        // TRUE means the page belongs to
  103.                     // the exec image and is not to be
  104.                     // overwritten or disposed
  105.       data_page     : 1,        // 1 - data page, 0 - code page
  106.       locked_page   : 1;
  107.  
  108. public:
  109.   PFN   page_frame;            // Page frame the page is mapped to
  110.  
  111.   VirtualPage(void);
  112.   ~VirtualPage(void) {}
  113.   int q_data_page(void)    const        { return data_page; }
  114.   void declare_data_page(void)        { data_page = 1; }
  115.   int is_shared(void) const        { return own_count > 1; }
  116.   int is_shared_mapped(void) const    { return ref_count > 1; }
  117.   int is_mapped(void) const        { return ref_count > 0; }
  118.   int is_locked(void) const        { return locked_page;   }
  119. };
  120.  
  121. class VirtualPageTable
  122. {
  123.   const int no_pages;
  124.   VirtualPage * pages;
  125.   BasicQueue freeVPs;
  126.   PageFrameTable page_frames;
  127.   Memory& physical_memory;
  128.   int no_locked_pages;
  129.  
  130. public:
  131.  
  132.   VirtualPageTable(Memory& _physical_memory,
  133.            const int no_phys_pages,const int no_virtual_pages);
  134.   ~VirtualPageTable(void) {}
  135.  
  136.                 // Get a Virtual Page given its no
  137.   VirtualPage& operator [] (const VPN vpn) const;
  138.                 // Allocate a new virtual page, return NIL
  139.                 // if no page is available
  140.   VPN allocate(void);
  141.   VirtualPage& allocate(VPN desired_vpn);
  142.   void declare_page_private(VPN vpn);
  143.   void copy(const VPN to, const VPN from);
  144.   void dispose(const VPN vpn);    // Dispose of a given page
  145.   void dump_status(void) const;    // Print info about virtual memory allocation
  146.   PFN reference(const VPN vpn); // The page is being demanded, reference it
  147.                 // The page is to be swapped out, unreference
  148.                 // and swap it out if needed
  149.   void unreference(const VPN vpn,const int to_write);
  150.   void lock(const VPN vpn);    // Lock the mapped page
  151.   void unlock(const VPN vpn);    // Unlock the mapped page
  152.  
  153.                 // Reserve the physical page for the system
  154.                 // Returns the physical address it starts
  155.   Address reserve_physical_page();
  156. };
  157.  
  158. /*
  159.  *------------------------------------------------------------------------
  160.  *              Memory manager itself
  161.  */
  162.  
  163. class MemoryManager;
  164.  
  165.                 // OS Memory manangement context of a process
  166. class MMContext : public MMUContext
  167. {
  168.   friend class MemoryManager;
  169.   const int process_virtual_space = 32;    // in pages
  170.   short no_mapped_pages;        // Current size of the working set
  171.   const short working_set_quota = 14;    // Max no. of mapped pages allowed
  172.   VPN vm_map[process_virtual_space];    // Process virtual space
  173.   PageTableEntry page_table[process_virtual_space];
  174.   short time_since_last_ref[process_virtual_space];    // for each page
  175.   long no_page_faults;
  176.  
  177.                 // Given vm_map, map of the process virtual
  178.                 // space, construct the page table
  179.   void build_page_table(const VirtualPageTable& virtual_space);
  180.  
  181. public:
  182.   MMContext(void);
  183.   virtual ~MMContext(void) {}
  184.  
  185.   void load_MMU(MemoryManagementUnit& mmu);    // Load and save the hardware
  186.   void save_MMU(const MemoryManagementUnit& mmu);// (MMU) context
  187.   void dump(void) const;        // Dump whatever's in the context
  188. };
  189.  
  190. class MemoryManager : public DiagnosticPanel
  191. {
  192.   Memory&        physical_memory;
  193.   VirtualPageTable virtual_space;
  194.  
  195.   short no_programs;            // No of programs on the drum. 
  196.   const short max_no_programs = 14;
  197.   struct ProgDescr { Address pc; Word mem_map; }
  198.       prog_descriptors[max_no_programs];
  199.  
  200.                     // Simple rule to partition the
  201.                     // virtual space of the program
  202.                     // into the data and code space
  203.   int is_text_segment(const int page_no) const { return page_no <= 15; }
  204.  
  205. public:
  206.   MemoryManager(Memory& _physical_memory);
  207.   ~MemoryManager(void) {}
  208.  
  209.   int q_no_programs(void);        // Read the drum header and tell the
  210.                     // number of programs on the drum
  211.  
  212.   void dump_status(void) const;        // Tell what's going on with memory
  213.  
  214.                     // Load program and return starting PC
  215.   Address load_program(MMContext& context,const unsigned int prog_no);
  216.  
  217.                     // Take care of son's virtual space
  218.                     // Return FALSE if some problem
  219.                     // occurred
  220.   int fork_son(MMContext& son_context,const MMContext& dad_context);
  221.  
  222.                     // Load the virtual page from the
  223.                     // drum and establish mapping to
  224.                     // a physical page
  225.   enum MMAnswer {Ok, PhysMemoryExhausted, LethalFault };
  226.   MMAnswer load_the_page(MMContext& context,
  227.              MMUContext::VirtualMemoryAddr culprit_VA);
  228.  
  229.                     // Release the virtual memory
  230.                     // occupied by the process
  231.   void dispose(MMContext& context);
  232.  
  233.                     // Swap out a victim - forcibly
  234.                     // deprive it of the mapped pages
  235.                     // Return 0 if no page frame was
  236.                     // released (unsuccessful swapping)
  237.   int swap_out(MMContext& context);
  238.  
  239.                     // Run the LRU page replacement
  240.                     // strategy to find out the least
  241.                     // referenced page and push it out
  242.   void replace_LRU_page(MMContext& context);
  243.  
  244.                     // Lock the page that contains the
  245.                     // specified virtual address. The page
  246.                     // should be already mapped
  247.                     // Return FALSE if failed
  248.   int lock_loaded_page(MMContext& context,const Address addr);
  249.  
  250.                     // Unlock the page that contains the
  251.                     // specified virtual address. The page
  252.                     // should be already mapped & locked
  253.   void unlock_page(MMContext& context,const Address addr);
  254.  
  255.                     // Translate the virtual address to
  256.                     // physical one. The page has to be
  257.                     // loaded. Returns 0 if fails
  258.   Address translate_va(MMContext& context,const Address addr);
  259.  
  260.                     // Reserve the physical page for the
  261.                     // system. Returns the physical
  262.                     // address where it starts
  263.   Address reserve_physical_page()
  264.       { return virtual_space.reserve_physical_page(); }
  265. };
  266.  
  267. #endif
  268.