Emulator Assignment part 3

You need to have Virtual Memory working BEFORE doing this part.

I would also suggest you allow comments in assembly language programs, it is very easy, and makes programs almost understandable. The scheme I use is to ignore everything after a semicolon ';' on any line of input.

Add Time-Sharing and Multiple Processes

First, a small addition that will make the rest a lot more convenient: Add a few new CPU registers. At the moment, you just have the PC and ACC; the PC isn't available for general purpose use, and the accumulator isn't quite enough on its own. Add at least two new registers (I'll call them B and C). Instructions that already exist will ignore these new registers.
To make the new registers usable, you need to add at least two new instructions: Just as there is a STORE instruction to copy the accumulator into a memory location, and a LOAD instruction to copy a memory location into the accumulator, we will now have a STORR instruction to copy the accumulator into a register, and a LOADR instruction to copy the contents of a register into the accumulator.
The operands of these instructions should be simple code numbers, 2 for register B, 3 for register C, etc. So to get the contents of register C into the accumulator, a program would use the instruction "LOADR 3"; to store the number 1234 in register B, a program would use the instruction sequence "LOADC 1234", "STORR 2".
These new registers will provide a useful place for putting information (i.e. parameters) that needs to be passed to system functions.
Add support for more than one process to be running at the same time. This requires a few simple-ish steps:
- Every process will need its own Page Table and somewhere to store the values of the CPU registers (PC, ACC, B, C) when it is not its turn to run. For realism, this should be in your emulated memory, not just another array of structs directly manipulated by your emulator.
- Your assembler should not start assembling instructions into virtual address 0; there should be a reasonable gap before the program starts. A good idea would be to make the gap a whole page (i.e. first instruction gets stored in memory location 512), then you have a whole page of memory (virtual page 0) available for other uses.
- Virtual Page Zero should be where each process stores its essential information (PC, ACC, B, C, Page Table) when it is not actively running. That means that there are only 508 ints for the Page Table, and as each P.T. entry requires 2 ints (VPN and PPN), your processes are limited to a maximum of 254 pages, but that is plenty for a small emulator.
- So write a function that can be used to save a process' state in its own virtual page zero when its turn on the CPU expires, and another function to restore its state from that page when a process gets its turn again. It is perfectly reasonable (but not required) to leave the Page Table in virtual page zero all the time (i.e. the Page Table for each process really is entries 4 to 511 of page 0), but CPU registers must be copied in and out.
- You need a way of finding each process. This is the Process Table. It doesn't need to contain much at all. In fact for each process you only need two pieces of information: A unique name so that it can be identified without confusion (perhaps just an integer, incremented each time a new process is created), and how to find it. As everything about a process is now stored in its virtual page zero, that means you just need to record where that page is (i.e. which physical page). So, the process table is a small array (size = maximum number of processes that can exist at the same time) containing Process ID numbers and Physical Addresses of Virtual Page Zeros for each existant process.
Add a new instruction for creating a new process. I suggest making it reflect the unix function: "FORK addr": create a new process exactly identical to the current one, except that its PC is equal to "addr". On executing the fork instruction (which really corresponds to an operating system function call, not a machine instruction), you should create a new process (i.e. find a free space in the process table), and make it identical to the current one. Do not just copy its page table: you don't want the new process to be using the same physical memory. For every page in the page table, find a new page of physical memory, copy the contents of the page into it, and use the copy of the page in the new process' page table.
Add Time Sharing. Every time you start executing a program, set a counter to a smallish random number. This is the number of instructions that the current process can execute before its turn expires. Decrement the counter on executing each instruction. If and when the counter reaches zero, swap processes. The current process is put to sleep (its state saved in its own virtual page zero), and the next process in the process table is restored (remember to reset the counter to another random number). Remember to invalidate all the entries in the Hardware Address Translator whenever processes are switched.
Add a new instruction for terminating a process. Again, this really emulates an OS call, not a machine instruction. "EXIT": the current process is terminated. Return all of its physical pages to the system for re-use, remove its entry from the Process Table, restore and start running the next process from the table.
When you reach this stage, make sure it works. Write a simple program that involves more than one process (they don't need to work together in any practical way, because we haven't got any communication mechanisms yet, so they can't). Make sure that when you run it, you really do get both processes running.
Finally! (nearly) Add the ability to communicate, through shared memory. I suggest taking this in two steps. First add a new instruction that asks the (emulated) operating system to allocate a new page of physical memory and add it to the page table with a particular Virtual Page Number. To use this instruction, first store the desired virtual page number in register B (at last we see why those registers were wanted), then execute the "PRMAP" (PRivate Memory Allocate Page) instruction. This is easy to do, and easy to test: Write a small program that attempts to use a memory address that is not allocated to it. For example "LOADC 1", "STORE 5120"; this program attempts to use Virtual Page 10, which should be an error for a small program. Make sure an error really is signalled. Then put the instructions required to allocate that page before those two instructions: "LOADC 10", "STORR 2", "PRMAP", "LOADC 1", "STORE 5120". This program should now run without error, and work.

Now for communications, add a similar instruction that asks for a shared page of memory to be allocated. Shared pages need to be ientified by some unique code number: if two processes request a shared page using the same code number, they should get the same page; if a third process requests a shared page with a different code number, it should get a different page. This is necessary to allow different groups of processes to communicate privately. To use the instruction, first load the desired virtual page number into register B as before, then load the unique identifier code into register C, then execute the "SHMAP" (SHared Memory Allocate Page) instruction.

You will need a special (small) table of shared memory pages that have been allocated. For each shared memory allocation you need to record three things: the unique code number so that the entry can be found if the same page is requested by another process; the physical page that was allocated; the number of processes that page has been given to. When a SHMAP instruction is executed, search the table for a matching code number. If found, use the same physical page (that's how it becomes shared) and increment the count of uses. If the code is not found in the table, find a new physical page, and use it for the allocation (fill it with zeros, this is your only chance to initialise it), and record it in a new table entry (with count = 1). When a process is terminated, not all shared pages should be returned to the system for re-use. When a process that has a shared page terminates, reduce the count for that page in the special table. Only if the count reaches zero should the page be recycled and the table entry removed.
HINT for easier testing: add a special "SLEEP" instruction. If a number is stored in the accumulator, the sleep instruction should delay for that many instruction execution cycles. Here is a simple way to make the SLEEP instruction work: If (ACC<=0) do nothing (move on to the next instruction); Otherwise, subtract one from ACC, and subtract one from PC. Subtracting one from the PC makes sure that the same SLEEP instruction is executed over and over again until the accumulator is zero.

Once you have mutliple processes working properly, a sensible emulator will not really allow the sleep instruction to execute in a tight little loop like that, it will simply make the current process lose its turn on the CPU instead.
Here is a sample of a program that would demonstrate shared memory working.
The main program simply starts two processes then exits:
```
        FORK   PRO1
        FORK   PRO2
        EXIT
```
Process One allocates a page of shared memory as virtual page 10 (which will contain all zeros to start with); it then goes into a little loop waiting until the first int in that page (virtual address 5120) is not zero any more (this can only happen if another process modifies it), at which point it prints 999 and stops.
```
PRO1:
        LOADC  10
        STORR  2
        LOADC  237535
        STORR  3
        SHMAP
LOOP1:
        LOAD   5120
        CMPC   0
        JZER   LOOP1
        LOADC  999
        OUTD
        EXIT
```
Process Two allocates the same shared page, but as virtual page 5, it then goes into a countdown loop in which the accumulator starts at 15 and counts down to 1, printing each number as it is reached. When the accumulator is equal to 10, it sets the first int of the shared page (virtual address 2560) to 1, as a signal to the other process. To avoid using a temporary variable in memory, the loop control variable (15..1) is kept safe in register B.
```
PRO2:
        LOADC  5
        STORR  2
        LOADC  237535
        STORR  3
        SHMAP

        LOADC  15   ; set ACC and B to 15
        STORR  2
LOOP2:
        JZER   END  ; when zero its all over

        OUTD
        CMPC   10
        JZER   SIG  ; when ACC=10 send the signal
CONT:
        LOADR  2    ; restore ACC from B, CMPC ruined it
        SUBC   1
        STORR  2    ; decrement before looping
        JUMP   LOOP2

SIG:
        LOADC  1
        STORE  2560 ; send the signal
        LOADR  2    ; restore ACC from B
        JUMP   CONT ; continue as usual

END:
        EXIT
```
To make communications workable, you'll need some Semaphore Operations. One very simple instruction will do the job: "TAS mem" executes the atomic test-and-set operationon memory location 'mem' (obviously, to do any good, mem should be in a shared physical page). The result of executing this instruction should be that the accumulator contains the original value from the memory location, and that memory location gets incremented.

With this, the P and V operations are easy to implement, as you will find out when you implement them.
Write some programs that communicate successfully when run on your emulator.