List view
Concurrency on the VM
Overdue by 4 year(s)•Due by July 6, 2021•2/2 issues closed# Phase 5 Add a process scheduler to the Virtual Machine. There needs to be: 1. a way to interrupt the current process execution on the CPU after some time; 2. a way to save a process's current state, which will lose the CPU. This saved state needs to contain everything needed to resume the process at a later date. This state must be saved on the PCB; 3. a process queue, containing processes that are ready to be resumed; 4. a process choosing routine, to get a process from the ready queue; 5. a routine to restore a process's state and resume its execution. More details follow. ## Process stopper clock There is an independent hardware clock in real systems that interrupts the CPU after some time has passed. This interruption triggers clock handling routines which, among other functions, checks if the currently running process should be swapped with another. Our system implements this clock as a CPU instruction counter. For every $n$ instructions, this interruption is queued ($n$ can be $5$). ## How it should work Create a new system interruption and its handler routine. This routine will save the current CPU state on the PCB of the currently running process. **There needs to be a notion of which processes are *running* and which processes are *ready*.** When a process leaves the CPU, it goes from *running* to the end of the *ready* queue. The next process to be executed is the one on the first index of the *ready* queue. The process is set to be *running* and its state (its program counter and registers) is resumed. ## Tests Load many processes on the memory. These processes are all stopped, waiting at the *ready* queue. Then call the process scheduler to start the first enqueued process. This should demonstrate the cycle specified [here](#how-it-should-work).
Overdue by 5 year(s)•Due by May 6, 2021•9/9 issues closed# Phase Four - [Phase Four](#phase-four) - [General additions](#general-additions) - [Memory Manager](#memory-manager) - [Allocation](#allocation) - [Deallocation](#deallocation) - [Interface](#interface) - [Internal data](#internal-data) - [Process management](#process-management) - [Representation](#representation) - [Execution](#execution) - [Tests](#tests) Comply with the fourth phase of the project. This phase consists of adding support for multiple processes running on the system and hosting more than one program in memory. However, a process will run in its entirety before another one can start - meaning that there will be no context switching for now. ---- Implement a MM (memory manager) and represent processes using PCBs (process control blocks). ## General additions The MM implements memory paging, where each page can store 16 words. Base project specification: the memory stores 1024 words, meaning that we will have 64 frames. In our case, the memory has a size of 4096 words, meaning that we will have 256 memory frames. ## Memory Manager The memory manager has several features, which are: allocation, deallocation, an interface, and some internal data. ### Allocation Given an allocation request for a given number of words, the manager must check if the allocation is possible (if there is enough space in the memory). If there is enough space, return a collection of the allotted frames as an array of indexes. ### Deallocation Given an array containing a process' allocated frames, mark these frames as free. ### Interface The manager must have a straightforward interface containing two methods: `allocate` and `deallocate` like so: ```python def allocate(number_of_words: int) -> Array[int]: ... def deallocate(frames: Array[int]) -> None: ... ``` ### Internal data The memory manager will inherit from the current `IMemory` interface, adding its two new management methods and the necessary frame/page information. Each frame corresponds to an area in memory of size 16, and each frame index corresponds to the area `[index * 16; (index + 1) * 16 - 1)` in memory. For example: | Frame | Start | End | | :---: | :---: | :-: | | 0 | 0 | 15 | | 1 | 16 | 31 | | 2 | 32 | 47 | | 3 | 48 | 63 | | ... | ... | ... | ## Process management When a program is set to be executed (instantiated), it's loaded onto the memory as a **process**. If we call a program twice, two distinct processes should be created. Each process is identifiable by a unique, sequential ordinal value called a process identifier, henceforth referred to as PID. When creating a process, all necessary memory frames must be allocated. To do so, the **size of the program** is needed. It's assumed that this (size) information is provided to us along with the program's code. The memory manager tries to allocate all frames for the process and, on success, returns an array with the process's frame indexes. Building upon this concept, the process is loaded onto the memory to fill, sequentially, all its necessary memory frames in the order supplied by the returned indexes array. The indexes array is also, coincidentally, the process's page table. Example: > Consider a program with five pages, allocated at [2, 3, 8, 12, 10]. > Let's now assign that array to the process's page table: > ```python > self.page_table = [2, 3, 8, 12, 10] > ``` Let *p* be one of the process's pages, `page_table[p]` is the frame where the page `p` is allocated. It's important to note that the original programs do not change. The system simply abstracts the addressing structure. This is called logical addressing (as opposed to absolute addressing), where addresses are **relative to the process's memory**. ### Representation Because there are now multiple processes loaded onto the memory at once, there's a need to represent them properly. This is done with the process control block (PCB, for short) structure. The PCB contains all information relevant to the execution of a process. For now, the PCB contains a process's PID and its page table (to be able to find the code on the memory). The system has a list of processes that were created and loaded onto the memory. ### Execution To execute a process, its location needs to be known. This is achieved via its page table. Since a process's memory access operations use relative addresses, there's a need to translate them to absolute memory addresses. ```python # let A be the first address accessed: p = A // self.page_size # page index offset = A % self.page_size # address inside of the given page # so... self.page_table[p] # frame where page `p` is located self.page_table[p] * self.frame_size # start of the desired frame (self.page_table[p] * self.frame_size) + offset # absolute address # or: abs_addr = (self.page_table[A // self.page_size] * self.frame_size) + (A % self.page_size) # with this, we can build a translation function as follows: def translate(self, A: int) -> int: return (self.page_table[A // self.page_size] * self.frame_size) + (A % self.page_size) ``` There should also be a verification if the returned address is valid, generating an error or granting access. The page is valid if the process contains the index `p` in the page obtained with `A // self.page_size`. ## Tests There need to be clear demonstrations that the program can: 1. load more than one process in memory, 2. execute each process sequentially, from beginning to end, 3. nudge programs into not allocating neighboring memory frames. There is also a need to visualize the memory and existent PCBs.
No due date•17/17 issues closed