jsos

commit 80110caa277bc744906701f4486a36cb4abdfa70
parent f4e395ea5ea5a0951ba281dcbaf02f0eba382989
Author: Jul <jul@9o.is>
Date:   Sat,  1 Dec 2012 00:35:33 -0500

Implemented working priority scheduling, nonworking host hdd and file system os driver.

Diffstat:
M
index.html
 | 
6
+++++-
M
scripts/host/control.js
 | 
2
++
M
scripts/host/cpu.js
 | 
7
-------
A
scripts/host/disk.js
 | 
113
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
scripts/os/deviceDriverFilesystem.js
 | 
101
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
scripts/os/kernel.js
 | 
12
++++++++----
M
scripts/os/memoryManager.js
 | 
7
++++---
M
scripts/os/pcb.js
 | 
3
++-
A
scripts/os/priorityQueue.js
 | 
167
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
scripts/os/scheduler.js
 | 
6
+++---
M
scripts/os/shell.js
 | 
49
+++++++++++++++++++++++++++++++++++++++----------

11 files changed, 444 insertions(+), 29 deletions(-)
diff --git a/index.html b/index.html
@@ -21,6 +21,7 @@
    <script type="text/javascript" src="scripts/host/devices.js"></script>
    <script type="text/javascript" src="scripts/host/cpu.js"></script>
    <script type="text/javascript" src="scripts/host/memory.js"></script>
+   <script type="text/javascript" src="scripts/host/disk.js"></script>
 
    <!-- Virtual OS Routines: Make sure Kernel code is last, since it needs those above it. -->
    <script type="text/javascript" src="scripts/os/interrupt.js"></script>
@@ -28,7 +29,9 @@
    <script type="text/javascript" src="scripts/os/console.js"></script>	
    <script type="text/javascript" src="scripts/os/deviceDriver.js"></script>
    <script type="text/javascript" src="scripts/os/deviceDriverKeyboard.js"></script>
+   <script type="text/javascript" src="scripts/os/deviceDriverFilesystem.js"></script>
    <script type="text/javascript" src="scripts/os/queue.js"></script>
+   <script type="text/javascript" src="scripts/os/priorityQueue.js"></script>
    <!--<script type="text/javascript" src="scripts/os/stack.js"></script>-->
    <script type="text/javascript" src="scripts/os/shell.js"></script>
    <script type="text/javascript" src="scripts/os/kernel.js"></script>
@@ -64,7 +67,7 @@
     </div>
     <div class="fourcol" id="processes">
       <h4>Processes</h4>
-      <table cellspacing="10" id="processesTable">
+      <table cellspacing="7" id="processesTable">
         <tr>
           <th>pid</th>
           <th>state</th>
@@ -75,6 +78,7 @@
           <th>X</th>
           <th>Y</th>
           <th>Z</th>
+          <th>P</th>
         </tr>
       </table>
     </div>
diff --git a/scripts/host/control.js b/scripts/host/control.js
@@ -61,8 +61,10 @@ function simBtnStartOS_click(btn) {
     
   _CPU = new cpu();
   _Memory = new memory(TOTAL_MEMORY);
+  _Disk = new disk();
   _CPU.init();
   _Memory.init();
+  _Disk = new disk();
   hardwareClockID = setInterval(simClockPulse, CPU_CLOCK_INTERVAL);
   krnBootstrap();
 }
diff --git a/scripts/host/cpu.js b/scripts/host/cpu.js
@@ -123,13 +123,6 @@ function cpu() {
         break;
 
     }
-console.log(
-"PID: "+_KernelCPUScheduler.running.PID+
-" PC: "+pad(this.PC.toString(16),2)+
-" AC: "+pad(this.ACC.toString(16),2)+
-" X: "+pad(this.X.toString(16),2)+
-" Y: "+pad(this.Y.toString(16),2)+
-" Z: "+this.Z);
   }
 
   /* 
diff --git a/scripts/host/disk.js b/scripts/host/disk.js
@@ -0,0 +1,113 @@
+/* ------------  
+   disk.js
+
+   Requires global.js.
+   
+   Routines for the host CPU simulation, NOT for the OS itself.  
+   In this manner, it's A LITTLE BIT like a hypervisor,
+   in that the Document envorinment inside a browser is the "bare metal" (so to speak) for which we write code
+   that hosts our client OS. But that analogy only goes so far, and the lines are blurred, because we are using
+   JavaScript in both the host and client environments.
+
+   This code references page numbers in the text book: 
+   Operating System Concepts 8th editiion by Silberschatz, Galvin, and Gagne.  ISBN 978-0-470-12872-5
+   ------------ */
+
+/* 
+ * The disk stores data.
+ *
+ * Total storage available is 16,384 bytes with 
+ * 4 tracks with 8 sectors with 4 blocks with 64 bytes.
+ */
+function disk() {
+  var TRACKS = 4;
+  var SECTORS = 8;
+  var BLOCKS = 8;
+  var BYTES = 64;
+
+  var init = function() {
+    // TODO do I need this?
+  };
+
+  /*
+   * Reads a single byte from a byte.
+   */
+  var readByte = function(tsb,byte) {
+    if(invalidDiskByte(byte)) 
+      return; //TODO throw bsod?
+    return read(tsb).substring(byte, byte+1);
+  }
+
+  /*
+   * Reads data from a block.
+   */
+  var read = function(tsb) {
+    return sessionStorage.getItem(tsb.toString());
+  };
+
+  /*
+   * Writes a single byte into a block.
+   */
+  var writeByte = function(tsb, byte, data) {
+    if(invalidDiskByte(byte) || invalidDiskData(data)) 
+      return; //TODO throw bsod?
+
+    var read = read(tsb);
+    var input = read.substring(0, byte) + data + 
+        read.substring(byte+1, read.length);
+    write(tsb, input);
+  };
+
+  /*
+   * Writes a sequence of bytes into a block and returns
+   * any data that didn't fit.
+   */ 
+  var write = function(tsb, data) {
+    data = data.toString();
+    
+    function writeData(data) {
+      sessionStorage.setItem(tsb.toString(), data);
+    }
+
+    if(data.length > BYTES) {
+      writeData(data.substring(0, BYTES));
+      return data.substring(BYTES, data.length);
+    } else {
+      writeData(data.substring(0, BYTES));
+      return undefined;
+    }
+  };
+
+  /*
+   * Checks if byte is a valid location in storage.
+   */
+  var invalidDiskByte = function(byte) {
+    return !isByte(byte) || byte >= BYTES;
+  }
+
+  /*
+   * Checks if data is valid and can be stored.
+   */
+  var invalidDiskData = function(data) {
+    data = data.toString();
+    for(i=0; i<data.length; i++)
+      if(!isByte(data[i])) return false;
+    return true;
+  }
+};
+
+/*
+ * Holds a track, sector, block value.
+ */
+function tsb(t,s,b) {
+  var track = t.toString();
+  var sector = s.toString();
+  var block = b.toString();
+
+  var toString = function() {
+    return 
+      track.toString() + 
+      sector.toString() + 
+      block.toString();
+  }
+};
diff --git a/scripts/os/deviceDriverFilesystem.js b/scripts/os/deviceDriverFilesystem.js
@@ -0,0 +1,101 @@
+/* ----------------------------------
+   DeviceDriverFilesystem.js
+   
+   Requires deviceDriver.js
+   
+   The Kernel Filesystem Device Driver.
+
+
+   Encoding format for each block:
+   status , track , sector , block
+
+   total: 4 bytes
+   data: 60 bytes
+
+   Status represents type and availability flag bits:
+   
+   One Byte
+   -----------------------------------
+   |X|X|X|X|X|X| type | availability |
+   -----------------------------------
+ 
+   ---------------------------------- */
+
+DeviceDriverFilesystem.prototype = new DeviceDriver;  // "Inherit" from prototype
+
+function DeviceDriverFilesystem() {
+
+  /* Max number of first status bit for each block. */
+  var STATUS_BIT_SIZE = 4;
+
+  /* 
+   * Maps existing directory names to disk location by TSB. 
+   */
+  var directory = {};
+
+  // TODO var is hidden scope but not rest?
+  this.driverEntry = function() {
+    this.status = "loaded";
+  };
+  
+  var isr = function() {
+    //TODO
+  };
+  
+  /*
+   * Formats entire filesystem by overriding directories.
+   */
+  var format = function() {
+    var data = pad("0", _Disk.BYTES);
+    for(i=0; i<directories.length; i++) {
+      //_Disk.write(directories[i])
+      
+    }
+  };
+
+  /*
+   * Get the availability status (to read and/or 
+   * write) of the block.
+   * If true, block is available, else it's occupied.
+   */
+  var availablity = function(data) {
+    var byte = data.substring(0,1);
+    var bit = byte.toString(2).substring(7,8);
+    return bit == 1 ? true : false;
+  };
+
+  /*
+   * Get the type (if file or directory) of the block.
+   * If true, it's a file, else it's a directory.
+   */
+  var type = function krnFsType(data) {
+    var byte = data.substring(0,1);
+    var bit = byte.toString(2).substring(6,7);
+    return bit == 1 ? true : false;
+  };
+
+  /*
+   * Get the next block if the data in this block 
+   * continues to the next.
+   */
+  var next = function(data) {
+    var track = data.substring(1,2);
+    var sector = data.substring(2,3);
+    var block = data.substring(3,4);
+
+    if(track==0 && sector==0 && block==0)
+      return undefined;
+    return new tsb(track, sector, block);
+  };
+};
+
+function krnFsDispatch(params) {
+  
+}
+
+
+
+
+
+
+
diff --git a/scripts/os/kernel.js b/scripts/os/kernel.js
@@ -26,7 +26,7 @@ function krnBootstrap()      // Page 8.
     _KernelBuffers = new Array();         // Buffers... for the kernel.
     _KernelInputQueue = new Queue();      // Where device input lands before being processed out somewhere.
     _KernelMemoryManager = new MemoryManager();
-    _KernelReadyQueue = new Queue();      // the ready queue for waiting processes to execute.
+    _KernelReadyQueue = PriorityQueue({low: true});   // the ready queue for waiting processes to execute.
     _KernelCPUScheduler = new scheduler();
     
     // Initialize standard input and output to the _Console.
@@ -39,6 +39,12 @@ function krnBootstrap()      // Page 8.
     krnKeyboardDriver.driverEntry();                    // Call the driverEntry() initialization routine.
     krnTrace(krnKeyboardDriver.status);
 
+    // Load the Filesystem Device Driver
+    krnTrace("Loading the filesystem device driver.");
+    krnFilesystemDriver = new DeviceDriverFilesystem();
+    krnFilesystemDriver.driverEntry();
+    krnTrace(krnFilesystemDriver.status);
+
     // 
     // ... more?
     //
@@ -179,8 +185,6 @@ function krnSystemCall(operator) {
       _KernelCPUScheduler.
           running.setState(PCB_STATE_TERMINATED);
       _KernelCPUScheduler.completedProcesses++;
-      _Console.advanceLine();
-      _OsShell.putPrompt();
       break;
 
     // normal system call
@@ -205,7 +209,7 @@ function krnSystemCall(operator) {
       var old = _KernelCPUScheduler.running;
       krnTrace("Removing PID "+old.PID+" by context switch.");
       old.setState(PCB_STATE_READY);
-      _KernelReadyQueue.enqueue(old);
+      _KernelReadyQueue.push(old, old.priority);
       _KernelCPUScheduler.running = undefined;
       MODE = 0;
       break;
diff --git a/scripts/os/memoryManager.js b/scripts/os/memoryManager.js
@@ -8,14 +8,14 @@ function MemoryManager() {
    * Loads a hex program into memory.
    * @param hex an array of bytes
    */
-  this.load = function(hex) {
+  this.load = function(hex, priority) {
     var pid = this.getAvailablePage();
     if(pid < 0) return pid;
 
     var bytes = this.hex2Dec(hex);
     var base = pid * MAX_MEMORY_PROGRAM;
     var limit = (pid+1) * MAX_MEMORY_PROGRAM - 1;
-    var process = new pcb(pid, PCB_STATE_RESIDENT, base, limit, base);
+    var process = new pcb(pid, PCB_STATE_RESIDENT, base, limit, base, priority);
     this.processes[pid] = process;
     _Memory.allocateBytes(bytes, base);
 
@@ -55,7 +55,7 @@ function MemoryManager() {
     var html = 
           '<tr><th>pid</th><th>state</th><th>base</th>' +
           '<th>limit</th><th>PC</th><th>ACC</th><th>X</th>' +
-          '<th>Y</th><th>Z</th></tr>';
+          '<th>Y</th><th>Z</th><th>P</th></tr>';
     for(var i=0; i<this.processes.length; i++) {
       var p = this.processes[i];
       html += '<tr>';
@@ -68,6 +68,7 @@ function MemoryManager() {
       html += '<td>'+pad(p.X.toString(16),2).toUpperCase()+'</td>';
       html += '<td>'+pad(p.Y.toString(16),2).toUpperCase()+'</td>';
       html += '<td>'+p.Z.toString(16)+'</td>';
+      html += '<td>'+p.priority.toString(16)+'</td>';
       html += '</tr>';
     }  
     div.innerHTML = html;
diff --git a/scripts/os/pcb.js b/scripts/os/pcb.js
@@ -1,7 +1,7 @@
 /*
  * Process Control Block
  */
-function pcb(pid, state, base, limit, pc) {
+function pcb(pid, state, base, limit, pc, priority) {
   this.PID = pid;
   this.state = state;
   this.base = base;
@@ -11,6 +11,7 @@ function pcb(pid, state, base, limit, pc) {
   this.X = 0;
   this.Y = 0;
   this.Z = 0;
+  this.priority = priority;
     
   /*
    * Updates process control block values.
diff --git a/scripts/os/priorityQueue.js b/scripts/os/priorityQueue.js
@@ -0,0 +1,167 @@
+/*
+ * https://github.com/STRd6/PriorityQueue.js/blob/master/src/priority_queue.js
+ *
+ * Modified by Julio Enrique Cabrera:
+ * - Added unix time to break priority ties. 
+ * - Only sorts when OS has priority enabled.
+ */
+(function() {
+  /**
+   * @private
+   */
+  var prioritySortLow = function(a, b) {
+    var value = b.priority - a.priority;
+    
+    if(value == 0)
+      value = prioritySortDate(a,b);
+    return value;
+  };
+
+  /**
+   * @private
+   */
+  var prioritySortHigh = function(a, b) {
+    var value = a.priority - b.priority;
+    
+    if(value == 0)
+      value = prioritySortDate(a,b);
+    return value;
+  };
+
+  /**
+   * @private
+   */
+  var prioritySortDate = function(a, b) {
+    return b.date - a.date;
+  };
+
+  /*global PriorityQueue */
+  /**
+   * @constructor
+   * @class PriorityQueue manages a queue of elements with priorities. Default
+   * is highest priority first.
+   *
+   * @param [options] If low is set to true returns lowest first.
+   */
+  PriorityQueue = function(options) {
+    var contents = [];
+
+    var sorted = false;
+    var sortStyle;
+
+    if(options && options.low) {
+      sortStyle = prioritySortLow;
+    } else {
+      sortStyle = prioritySortHigh;
+    }
+
+    /**
+     * @private
+     */
+    var sort = function() {
+      contents.sort(sortStyle);
+      sorted = true;
+    };
+
+    /**
+     * @private
+     * Requires: global.js (in juliOS) 
+     */
+    var priority = function() {
+      return CPU_STATE == CPU_STATE_PRIORITY.name;
+    };
+
+    var self = {
+      /**
+       * Removes and returns the next element in the queue.
+       * @member PriorityQueue
+       * @return The next element in the queue. If the queue is empty returns
+       * undefined.
+       *
+       * @see PrioirtyQueue#top
+       */
+      pop: function() {
+        if(!sorted && priority) {
+          sort();
+        }
+
+        var element = contents.pop();
+
+        if(element) {
+          return element.object;
+        } else {
+          return undefined;
+        }
+      },
+
+      /**
+       * Returns but does not remove the next element in the queue.
+       * @member PriorityQueue
+       * @return The next element in the queue. If the queue is empty returns
+       * undefined.
+       *
+       * @see PriorityQueue#pop
+       */
+      top: function() {
+        if(!sorted && priority) {
+          sort();
+        }
+
+        var element = contents[contents.length - 1];
+
+        if(element) {
+          return element.object;
+        } else {
+          return undefined;
+        }
+      },
+
+      /**
+       * @member PriorityQueue
+       * @param object The object to check the queue for.
+       * @returns true if the object is in the queue, false otherwise.
+       */
+      includes: function(object) {
+        for(var i = contents.length - 1; i >= 0; i--) {
+          if(contents[i].object === object) {
+            return true;
+          }
+        }
+
+        return false;
+      },
+
+      /**
+       * @member PriorityQueue
+       * @returns the current number of elements in the queue.
+       */
+      size: function() {
+        return contents.length;
+      },
+
+      /**
+       * @member PriorityQueue
+       * @returns true if the queue is empty, false otherwise.
+       */
+      empty: function() {
+        return contents.length === 0;
+      },
+
+      /**
+       * @member PriorityQueue
+       * @param object The object to be pushed onto the queue.
+       * @param priority The priority of the object.
+       */
+      push: function(object, priority) {
+        contents.push({
+          object: object, 
+          priority: priority, 
+          date: new Date().getTime()
+        });
+        sorted = false;
+      }
+    };
+
+    return self;
+  };
+})();
diff --git a/scripts/os/scheduler.js b/scripts/os/scheduler.js
@@ -26,9 +26,9 @@ function scheduler() {
 
     // if ready queue is not empty, dequeue
     if(this.processTerminated()) { 
-      var p = _KernelReadyQueue.dequeue();
+      var p = _KernelReadyQueue.pop();
       while(p.state == PCB_STATE_TERMINATED)
-        p = _KernelReadyQueue.dequeue();
+        p = _KernelReadyQueue.pop();
       this.setRunningProcess(p);
       krnTrace("Adding PID "+p.PID+" by context switch.");
     }
@@ -70,7 +70,7 @@ function scheduler() {
    */
   this.ready = function() {
     this.output();
-    return (!this.processTerminated() || _KernelReadyQueue.getSize() > 0);
+    return (!this.processTerminated() || _KernelReadyQueue.size() > 0);
   }
 
   /*
diff --git a/scripts/os/shell.js b/scripts/os/shell.js
@@ -547,23 +547,48 @@ function shellStatus(args)
  * Loads a program into a memory so it becomes a process.
  */
 function shellLoad(args)  {
-  var hex = trim(document.getElementById(TA_PROGRAM_INPUT).value.replace(/\n/g, " "));
+
+  function getPriority() {
+    var priority = args[0];
+    if(priority == undefined || 
+       !isInt(priority) || 
+       CPU_STATE != CPU_STATE_PRIORITY.name) { 
+
+      if(CPU_STATE != CPU_STATE_PRIORITY.name &&
+         priority != undefined && 
+         isInt(priority)) {
+        _StdOut.putText("Scheduler not set to Priority.");
+        _Console.advanceLine();
+      }
+
+      return 5;
+    } else 
+      return priority;
+  }
+
+  var hex = trim(document.getElementById(TA_PROGRAM_INPUT).
+      value.replace(/\n/g, " "));
+
   if(isValidHex(hex)) { // in utils.js
     var bytes = hex.split(" ");
     if(bytes.length > 1) {
       if (bytes.length <= MAX_MEMORY_PROGRAM) {
         // pass the hex to kernel's memory manager
-        var pid = _KernelMemoryManager.load(bytes);
+        var priority = getPriority();
+        var pid = _KernelMemoryManager.load(bytes, priority);
         if(pid < 0)
           _StdOut.putText("There is no memory available.");
         else 
-          _StdOut.putText("Your program has been successfully loaded with PID: " + pid);
+          _StdOut.putText("Your program has been "+
+              "successfully loaded with PID: " + pid);
       } else {
-        _StdOut.putText("Program is too large. Must be less than "+MAX_MEMORY_PROGRAM+" bytes.");
+        _StdOut.putText("Program is too large. Must be"+
+            " less than "+MAX_MEMORY_PROGRAM+" bytes.");
       }
     } else _StdOut.putText("Input Program textarea is empty."); 
   } else {
-    _StdOut.putText("Invalid program. Make sure it's properly formatted hex.");
+    _StdOut.putText("Invalid program. Make sure it's"+
+        " properly formatted hex.");
   }
 }
 
@@ -582,7 +607,7 @@ function shellRun(args)  {
       if(process.state != PCB_STATE_RESIDENT)
         _StdOut.putText("Process cannot run.");
       else {
-        _KernelReadyQueue.enqueue(process);
+        _KernelReadyQueue.push(process, process.priority);
         process.setState(PCB_STATE_READY);
       }
     }
@@ -597,12 +622,12 @@ function shellRunAll(args) {
   var ran = 0;
   for(var i=0; i<ps.length; i++) {
     if(ps[i].state == PCB_STATE_RESIDENT) {
-      _KernelReadyQueue.enqueue(ps[i]);
+      _KernelReadyQueue.push(ps[i], ps[i].priority);
       ps[i].setState(PCB_STATE_READY);
       ran++;
     }
   }
-  _StdOut.putText("Running "+ran+" processes in total.");
+  _StdOut.putText("Running "+ran+" processes.");
 }
 
 /*
@@ -716,8 +741,12 @@ function shellLs(args) {
  */
 function shellSetcpu(args) {
   function setScheduler(schedule) {
-    CPU_STATE = schedule;
-    _StdOut.putText("CPU Scheduler set to "+schedule);
+    var running = _KernelCPUScheduler.running;
+    if(!running || running.state != PCB_STATE_RUNNING) {
+      CPU_STATE = schedule;
+      _StdOut.putText("CPU Scheduler set to "+schedule);
+    } else
+      _StdOut.putText("CPU Scheduler is running.");
   }
 
   var scheduling = args[0];