OS22-CrisologoMinichelli

Project C1 made by Minichelli and Crisologo for the OS Course at PoliTO

SYS161

To be done..

Memory Organization of SYS161

The memory organization of SYS161 can be found in the include file vm.h.

The address bus has a width of 32bit, thus giving an ideal address space of 4GB.

In reality, the physical memory is much lower, and it composed of a physical ram, which size can be set in the config file "sys161.conf" in the "/root" directory. By now this project is configured to have 512kB of RAM.

• kuseg
  • 0x00000000 - 0x7fffffff (user, tlb-mapped).
  • Those addresses should only be used in the user-mode.
  • When trying to read or write in this address space, the TLB-Hardware mechanism kicks in. There is the need to map those addresses to the physical memory.
  • This address space can be used to virtualize memory and load programs which have a size higher than the real physical memory.
• kseg0
  • 0x80000000 - 0x9fffffff (kernel, unmapped, cached).
  • We can find the physical RAM in this address space.
  • MIPS_KSEG0 = 0x80000000.
  • Physical RAM starts from 0x80000000 to size_t lastpaddr+MIPS_KSEG0, which can be retreived by using the function size_t mainbus_ramsize().
  • The physical RAM taken by the kernel during startup starts from 0x80000000 to vaddr_t firstfree (set by start.S).
• kseg1
  • We are not talking about this by now.
• kseg2
  • We are not talking about this by now.

Project Description

Project c1: Virtual Memory with Demand Paging (PAGING)

Virtual Memory is the separation of the user logical memory from physical memory. Virtual memory can be implemented via:

• Demand paging
• Demand segmentation

First implementation of a VM

The virtual address space starts at 0x00000000 and ends at 0x7fffffff. This means that every program can access up to 2GB of virtual memory.

This virtual address space is divided in pages, in this case 2^19 = 524288 pages, as 12 bits are used for the offset addressing in a page.

A program can be load in the virtual memory address space through the use of the function call runprogram(...), which calls the function loadelf(...).

When loading a program in the memory, we need to divide the virtual memory in those 4 section:

• Code segment
• Data segment
• Stack segment

The maximum number of page for each SEGMENT is determined by (in the include file page.h):

#define MAX_PAGES_PER_PROCESS 78
#define MAX_CODE_SEGMENT_PAGES 4
#define MAX_DATA_SEGMENT_PAGES 70
#define MAX_STACK_SEGMENT_PAGES 4

#define MAX_PAGES_ALLOC 10

If a program requires more pages for one or more segment, those segment are not loaded in the physical memory during the first loading.

Address generated by CPU is divided into:

• Page number (p):
• Page offset (d):

In our case, m = 31, n = 12, m-n = 19.

As the PAGE SIZE is actually equal to 4096 bit, the last 12 bit of the virtual address space rappresent the OFFSET.

The remaining 19 bit rappresent the page number. This means that we can address up to 524288 pages (2^19).

For this reason, the Page Table should allow at least 524288 entries for each address space. But, if each entry occupies 10B, this would means use 5MB of space for the page table for each process.

One solution can be:

• Store in the physical disk a full page table with 2^19 entries.
• Store at the top of the RAM memory a smaller page table, with 512kb/4kb = 128 entries = 128 pages.

Usually, an address space is defined for each process.

Demand Paging

To be done..

TLB - Translation look-aside buffers (TLBs)

Also called associative memory.

New TLB Implementation

To be done..

TLB Replacement policy

To be done..

runprogram

In order to start a program, the int runprogram(*char progname) function is called. In the os161 implementation, the function follow the following state flow:

flowchart  TD  
A["runprogram(char *progname)"]  -->  B["vfs_open(progname)"]  
B  --> C[as_create]  
C  -- "as = kmalloc()" -->  D["load_elf(v, &entrypoint, 0, 0)"]
D -- "Code Segment" --> E1["as_define_region()"]
D -- "Data Segment" --> E2["as_define_region()"]
E1 -- "Code Size > MAX_CODE_SIZE" --> F1["Demand paging activated"]
E1 -- "Code Size < MAX_CODE_SIZE" --> F2["Demand paging not activated"]
E2 -- "Data Size > MAX_CODE_SIZE" --> F1a["Demand paging activated"]
E2 -- "Data Size < MAX_CODE_SIZE" --> F2a["Demand paging not activated"]
F1 -- "as_npages_code_loaded \n= MAX_CODE_SIZE" --> F3
F2 -- "as_npages_code_loaded \n= segment_size" --> F3["Alloc pages"]
%% 64 = MAX_PAGES_PER_PROCESS
%% 16 = MAX_STACK_SEGMENT_PAGES
F1a -- "as_npages_data_loaded \n= 64 - as_npages_code_loaded - 16" --> F3
F2a -- "as_npages_data_loaded \n= segment_size" --> F3
F3 -- "as_prepare_load()" --> F4["Alloc 1 page for stack"]

Loading

Round Robin Scheduling

For this project, a Round-Robin (RR) like algorith is used to schedule the upcoming processes.

This algorithm is based on the time-sharing technique, giving for each job a time-slot also called time quantum.

Test

Test	Commento
km1	OK
km2	OK
huge	OK
matmult	OK
sort	??
ctest	??
bigexec	??

Dumbvm

Dumbvm is the embedded Virtual Memory Managment of the OS161. One of the goal of this project is to replace this architecture with a new virtual-memory system that relaxes some (not all) of dumbvs's limitations.

Snippets used during coding

While using VSCode, just press Ctrl+Shitf+V in order to display the Markdown Preview of the opened .md file.

How to debug with visual studio?

cd /home/francesco/os161/root
sys161 -w kernel

Then in VSCode, just press F5.

Error debugger messages

sys161: trace: software-requested debugger stop

If you read this message in the console probably there is a problem with spinlock (a function is taking to long to execute)

sys161: disk: slot 2: LHD0.img: Locked by another process

If you read this message in the console while trying to execute sys161, execute:

sudo kill -9 $(lsof -t LHD0.img)