# Operating System and Virtual Memory
###### tags: `Computer Architecture`

## Operating System Introduction
* What is an Operating System?
* Operating Systems control how software applications access and use hardware on your computer. They provide a general interface for common actions and allow software to run without knowledge of the machine it lives on.
> * 簡單來說，如果我今天寫一支簡單的程式，我不希望我要了解這個硬體的讀寫以及硬體的應用。我也不希望我寫一支程式他只能在一個機器上跑像是只能運行在macbook 2016不能運行在其他的mac上面。
> * 作業系統就是解決了這種硬體上的問題，給與一個固定的框架，避免程式需要為每一個機器進行適配
* What does the OS do?
* One of the first things that runs when your computer starts(right after firmware/bootloader)
* Loads, runs and manages programs:
* multiple programs at the same time (time-sharing)
* isolate programs from each other (isolation)
> * 這很重要，如果沒有隔離每個程式的話，可能有安全性的問題
> * 例如瀏覽器可以得到你的密碼
* multiplex resources between applications (e.q. deveices)
> 如果很多應用程式都需要同一個硬體協助，作業系統會負責協調
* Services: File system, Network Stack
* Finds and Controls all the devices in the machine in a general way


> 分層三種階層是為了安全，避免一般的程式亂動暫存器引起不必要的危險
## OS Boot Sequence and Operating
* What Happens at boot?
* When the computer weitches on, the CPU executes instructions from some start address (stored in Flash ROM)
1. BIOS: Find a storage device and load first sector(block of data)
2. Bootloader: Load the OS kernel from disk into a location in memory and jump into it
3. OS Boot: Initialize services, drives...
4. Init: Launch anapplication that waits for input in loop
> 開始處理軟體
* Launching Applications
* Applications are called "processes" in most OSs.
* Created by another process calling into an OS routine
* Depends on OS, but linux uses `fork` to create a new process, and `execve` to load application
* Loads executable file from disk and puts instructions & data into memory, prepare stack and heap.
* Set `argc` and `argv`, jump into the main function
* Supervisor Mode
* If something goes wrong in an application, it can crash the entire machine
* Thus, the OS may to enforce resource constraints to applications
* To protect the OS from the application, CPUs have a <font color=red>supervisor</font> mode bit
* You can only access a subset of instructions and memory when not in supervisor mode
* You can change out of supervisor mode using a speciial instruction, but not into it(unless thiere is an interrupt)
* Syscalls
* How to switch back to OS? OS set timer interrupt, when interrupts trigger, drop into supervise mode
* What if we want to call into an OS routine?
* ex: to read a file, launch a new process, send data, etc.
* Need to perform a <font color=red>syscall</font>: set up function arguments in registers, and them raise <font color=red>software interrupt</font>
* OS will perform the operation and return to user mode
* This way, the OS can mediate access to all resources, including devices, the CPU itself, etc.
## Multiprogramming and time-sharing
* Multiprogramming
* OS runs multiple applications at the same time
* But not really at the same time unless have a core per process
* Switches between processes very quickly. This is called a "context switch"
* Deciding what process to run is called <font color=red>scheduling</font>
* Programs can be scheduled in a variety of ways
* Most/least resources needed, "fastest" to run, most important...

:::warning
以下為Context Swtich示意圖
> 兩個任務A和B

> 執行A，將A放入記憶體

> 執行B，將A的刪除
> 等等，這樣對嗎?
> 為了執行新的任務把舊的刪掉了，那如果之後又要執行A不就又要再讀一次

> 因此放到新的區間才是最佳解

> 現在有新的任務C，C使用的記憶體大小比B還要小

> B執行完之後， 要把D塞進去
> D可以進入一整塊空白的空間嗎?只要把C移走就好了，嘿嘿嘿

> 你把指標移走了，執行C的時候會出事，雖然D很爽

解決方法: 虛擬記憶體(Virtual Memory)
:::

* Protection, Translation, Paging
* Supervisor mode deos not fully isolate applications from each other or from the OS
* Application could overwrite another application's memory
* Remember the linker in CALL: Application assumes that code is in certain location. How to prevent overlaps?
* May want to address more memory than we actually have
* for sparse data structure
* Solution: Virtual Memory. Give each process the illusion of a full memory address space that it has complete to itself

* Two Memory
* From here on out, we'll be working with two different memory spaces:
* Virtual Memory(VM): A large space that a process believe it, and only it has access to
* Physical Memory(PM): The limited RAM space your computer must share among all processes and processors
* Goals:
* Process/Program isolation
* Make translation from infinite to finite seamless, or not noticeable to the program
* Translate between VM, PM addresses


## Introduction to Virtual Memory
* Virtual Memory Goals
* Allow multiple processors to simultaneously occupy memory and provide <font color=red>protection</font>
* Don't let programs read/write each other's memory
> 不要讓程式用到其他程式的記憶體
* Give each program the ==illusion== that it has its own ==private address space==
* Suppose code starts at address 0x00400000, then different processes each think their code resides at that same address
* Each program must have a different view of memory
* Segmented Memory
* Divide RAM into segments with a "base" and "bound"
* ==Each program access to its segment only==
* Program has a virtual address range 0x0....0 to 0xFF....
* To get location of data in segment(physical address), add to base value

> 設定程式可以使用記憶體的上下限

> 只有在Supervise Mode的時候才可以存取Bound Register和Base Register

> Pipeline對於Program Counter也需要新增安全機制

* Base and Bound: Problems
* What if we need more space than our segment allows?
* Increase Segment? Wjat if no more RAM?
* Use Disk? How do we decide what data to move in or out?
* What if we require 500MB of space, but RAM is fragmented, so there isn't a contiguous chunk available?

### Paged Memory
* Instead of having segments of various sizes, let's divide physical memory and virtual memory into equal units called page
* Pages are all the same size, regardless of program, and RAM is an integer multiple of pages
* Page size is the same in both virtual and physical memory
* What does our memory layout look like now?
:::warning
> 一個程式而已全部都是我的

> 兩個程式都占用了很多Pages
* Each program has access to one or more pages
* Pages do not have to be contiguous, or next to each other. Pages are not organised by program

:::
* How do we continue to enforce protection? How do we find a piece of data given our virtual address between 0x0..0 and 0xF...FE?
* Page Protection: Page Tables
* Per program, maintain a list (or table) of pages in physical memory that they own
* For each page, note the data it contains
* Sufficient to just noe virtual page number! This will tell us the range of addresses
* Just like base and Bound: use this table to translate addresses so programs cannot reach physical addresses outside of their assigned range

* Modern Virtual Memory Systems
* Protection
* Several programs, each with their private address space and one or more shared address spaces
* Demand Paging
* Provide the ability to run programs larger than the primary memory
* Hide differences in machine configuration
# Lecture 19, Virtual Memory
###### tags: `Computer Architecture`

## Review: Virtual Memory
* Virtual Memory
* Provides Program with illusions(錯覺) of a very large main memory
* Working set of "pages" reside in main memory, others reside on disk
* Allows OS to share memory and protect programs from each other
* Each process thicks it has all the memory to itself
* Address Space
* Address Space = set of addresses for all available memory locations
* Now, two kinds of memory addresses:
* Virtual Address Space
* Set of addresses that the user program knows about
* Physical Address Space
* Set of addresses that map to actual locations in memory
* Hidden from user applications
* Memory manager maps between these two address spaces
* Virtual Addresses and Physical Addresses
==Memery Manager maps virtual to physical addresses==

* Virtual to Physical Address Translation
* Each Program operates in its own virtual address space, ==ONLY PROGRAM RUNNUNG==
* Each process is protected from the other
* OS can decide where each goes in memory
* Hardware gives virtual &rarr; physical mapping
* Virtual Memory and Physical Memory
* Programs use Virtual Addresses(Vas)
* Space of all virtual addresses called cirtual memory(VM)
* Divided into pages index by virtual page number(VPN)
* Main Memory indexed by Physical Addresses(PAs)
* Space of all physical addresses called physical memory(PM)
* Divided into pages indexed by physical page number(RPN)
:::warning

Each process has its own virtual memory, but all processes must share physical memory


Page in Physical Memory Correspond to pages in virtual memory

Each process has a table mapping its physical/virtual pages


When a process needs more data, the LRU page is removed from Physical Memory(PM) and replace with a new page from disk

The valid bit is 0
:::

## Virtual Memory and Page Tables
* Address Translation
* Given a request for an address we have to locate the data in physical memory
* The process of converting a virtual address to a physical address is called address translation
* Virtual Address can be broken into parts: we;ii call the two parts the page number and the offset
* We can calculate the size of these fields like we did with caches:
* Size of Address = log_2(Virtual Memory Size)
* Size of Offset = log_2(Page Size)
* Size of VPN = log_2(number of virtual pages)
* Size of Address = log_2(Physical Memory Size)
* Size of Offset = log_2(Page Size)
* Size of PPN = log_2(number of Physical Pages)
* Page Table Entry Format
* Contains wither PPN or indication not in main memory
* Dirty = Page has been modified recently
* Valid = Valid Page table entry
* 1 &rarr; Virtual Page is in Physical Memory
* 0 &rarr; OS needs to fetch page from disk PAGE FAULT
* Access Rights checked on every access to see if allowed(Provides Protection)
* Read, Write, Executable: Can fetch instructions from page
* Protection Fault
:::info
1. 利用Index找到Virtual Page Number
2. 先利用Valid Bit和Access Rights來進行驗證可否有存取記憶體
3. 結合PPN和Offset
4. Page Address to Access memory
:::
* Protection Between Process
* With a bare system, addresses issued with loads/stores real physical addresses
* This mean any program can issue any address, therefore can access any part of memory, even areas which it doesn't own
* Example: the OS data structures
* How does having a page table isolate and protect processes?
* In order create a physical address from a virtual one, we have to convert our page number(VPN &rarr; PPN)
* To do this, we look up a mapping for the VPN in our page table
* We can only find mapings for pages we own
* All ither mappings are invalid or blank
* Therefore, we cannot construct physical addresses we do not have access to

## Translation Lookaside Buffer (TLB)
* Example

* Where should Page Tables Reside?
* Keep Page Tabels in the main memory
* How can we find the page table in memory if the main page table is how we learn Physical addresses?
* Page Table Register: Stores Physical Address of current Page Table
## Virtual Memory Performance
* Fetching Data on a memory read
*
* Performance Metrics
* VM Performance also uses Hit/Miss Rates and Miss Penalties
* TLM Miss Rate: Fraction of TLB accesses that result in a TLB miss
* Page Table Miss Rate: Fraction of PT accesses that result in a page fault
* Cacheing performance definitions remain the same
* Somewhat independent, as TLB will always pass PA to cache regardless of TLB hit or miss
* Virtual Memory is the level of the memory hierarchiy that sits below main memory
* TLB comes before cache, but affects transfer of data from disk to main memory
* Previously we assumed main memory was lowest level, now we just have to account for lowest level, now we just have to account for disk accesses
* Same CPI, AMAT equations apply, but now treat main memory like a mid-level cache

:::info
Virtual Memory Wrap-up:

Paged-Based Virtual Memory Machine
:::
## MIT 6.004 Lecture 19, Operating System

> 之前我們上道的計算機結構都是使用單程式對一個機器，然而現實中並不是如此，我們有一個機器但是我們想要他跑多個程式。因此我們需要作業系統將它作為硬體資源調度的控制器，而軟體和作業系統間的介面就是ABI

> Programm = Code
> Process = Executing the Program = Program + State

> 作業系統存在的三個意義：確保程式間的獨立性避免程式間的資料互相調用、給予一個介面使得程式可以方便編寫及使用、硬體資源調度

接下來的課程都是圍繞著以下三個概念作延伸
### Independent
> OS 給予了不同程式不同的記憶體區間，彼此互不干擾。

### Scheduling
> 每個程式佔用CPU的時間，不可以因為一個程式一直佔用CPU導致其他程式不能運作

### System Calls
> 利用System Call來完成軟體對硬體的指令

### Virtual Machine
> 不是真的在硬體上執行，是在模擬硬體執行的樣子

> 這裡共有五個VM，這些是不同的虛擬機，像是RISCV, x86這兩種屬於硬體的虛擬機，用來模擬硬體；Win/Linux/Mac是屬於介面的虛擬機；Python Lacnguage屬於程式語言的虛擬機

> 虛擬機可以全部用軟體執行但是會有效能損失，但是仍舊很好用，因為如果我們要開法作業系統核心時，虛擬機是一個非常好用的軟體，不會有軟體突然爆掉的風險

### OS
* Two different mode of execution: user and supervisor
* OS kernel runs in supervisor mode
* All other processes run in user mode
* ==Priviledged instructions and registers== that are only available in supervisor mode
* ==Interrupts and extensions== to safely transition from user to supervisor mode
* Why Exceptions?
* Actually, we classify them between asynchronous events and synchronous events
* Exceptions refer to synchronous events, generated by the processor itself(ex:illegal instruction, divide-by-0, illegal memory address and system call)
* Interrupt refer to astnchronous events, generated by IO devices(ex: keyboard, clock...)
* Handling Exceptions
* When the exception happens, the processor:
* Stops the current process at instruction I(i), completing all the instructions up to I(i-1)
* Saves the PC of instruction I(i) and the return for the exception in special register
* Enable supervisor mode, disables interrupts and transfer control to a pre-specified exception handler PC
* After the OS kernel handles the exception, it returns control to the process at instruction I(i)
* If the exception is due to an illegal operation by the program that connot be fixed, Absort the process
* ==Virtual memory== to provide private address spaces and abstract the storage resources of the machine
* These ISA(Instruction Set Architecture) work only if hardware and software agree on a common set of conventions
### Case Study
1. CPU Scheduling

3. Emulating Instructions
> 在RV32I的機器上執行RV32IM的指令集會發生什麼事呢？

> 這邊如果遇到`mul`指令集時，機器看不懂就給作業系統看，作業系統會將指令給仿真器(Emulator)看，估計出他是乘法的指令後執行，執行完之後將控制權交回給`Process 1`
> 這樣程式碼會以為我在RV32IM的機器上執行，其實不是，但是這樣很慢，不如直接使用電路做乘法

## MIT 6.004 Lecture 20, Virtual Memory
### Operating System Review
> 上次上課講到作業系統的三個目標：程式獨立性、硬體資源調度及抽象畫介面並且介紹了作業系統分為兩個行為模式：使用者模式及監督者模式

### Virtual Memory
> 虛擬記憶體與快取很像，都是由小記憶體過渡到大記憶體。因此，如何調度這些記憶體就變得非常重要

Machine Code: `lw x1, 0x100(x11)`, Here `0x100` is Machine Code, and we need ti convert the machine code to the virtual address

> 每個程式在執行時會被分到一塊記憶體，這裡的記憶體是Virtual Address，而所謂Virtual並不是真的虛擬，而是在這塊記憶體的相對位置。在實體記憶體中，將會被分一塊記憶體，被分到的記憶體起點就是Segment Base，而Physiucal Address = Virtual Address + Segment Base。

> 這邊會將程式的程式碼和資料分在不同的記憶體區間，來保護自己的程式隨意調用記憶體

> * 現在的記憶體調用方式就是把整個程式需要的記憶體塞進記憶體空間中，而且要連續的塞。然而，這會導致程式產生許多的問題。首先，如果記憶體空間都很零碎，突然有一個巨大的程式需要大量的記憶體空間該如何配置？如果程式突然用了遞迴、動態陣列需要棧(Stack)、堆(Heap)額外取得記憶體該如何掉用？
> * 總結，直接把一個程式丟進連續記憶體空間是非常浪費且不切實際的，儘管一開始的配置很簡單，但是遇到突發狀況或是動態配置，這都非常難應對，因此下面會介紹新的方法進行記憶體配置。

> 既然連續記憶體會出問題，那就不要連續就好了嘛。這邊介紹的另外一種記憶體配置方法，將記憶體分成許多相等的空間，並且將程式也分成許多相等的空間，不將程式連續的放在一起，而是將程式分塊放，最後使用一個叫Page Table的方式調用記憶體。
> 而Virtual Table可以轉乘Physical Table，如下

> 每一個Virtual Address對應一個Page Table找到Physical Address

Paging versus Segmentation
| | Paging | Segentation |
| -------- | -------- | -------- |
| Framentation Issue | None | Has this issue |
| Physical Memory Usage| By Page Table| By Add a Base seg|
| Size of Converter| Very Large| Small|

Where we can save the Page Table?
1. Suppose Page Table Reside in Memory


> * 首先我們要先進入儲存Page Table的Page Table, 假設現在我們找到程式一，我們就可以找到程式一的Page Table，此時輸入Virtual Address就可以知道他的Physical Address，利用Offset就可以知道他的Word在哪裏
> * 這邊所有的線都是Physical Address不是Virtual Address 對Physical Address的轉換
* 幾個問題
1. How to reduce memory access overhead?
3. What if all the apges cannot fit in DRAM?

* 記憶體容量可能無法負荷所有程式，因此必須使用一些硬碟空間。
* 可以把記憶體想程式硬碟的快取
* Page Table Entry(PTE)包含
* 一個Resident Bit顯示資料在記憶體還是硬碟
* PPN: Physical Page Number
* DPN: Disk Page Number
* Page Table可以設定只從硬碟中存取資料
* 當一個程式開始的時候，所有程式碼和資料都在硬碟中，可以將他們帶入Page Table 當他們被存取的時候

Example:
D: Dirty Bit, W: Writeable Bit, R: Resident Bit
> 怎麼解題呢？我們需要將0x2C8解碼成Virtual Address, 首先我們要要將virtual address除以virtual page number和offset，這邊我們除完後得到virtual index = 0x2，因此直接查表得到對應的physical Number是0x4，offset是可以一一對應的，因此最終結果是0x4C8

Caching vs Demand Paging

Page Fault
> 若發生Paging Miss，他的懲罰項是硬體承受不起的，因此不如使用軟體優化。

* If the resident bit said that the data is in the disk, but it doesn't, there is a page miss, and OS will handle that
> 這邊簡述一下作業系統的做法。選則一個page取代，在硬碟中讀取資料取代目前的page，並且更新他的resident bit，最後將控制權交回程式，並且改寫他要存取的記憶體位置

:::info
總結一下如果page table放到記憶體中

我們需要一直在記憶體中找參考資料，也就是在記憶體從頭找到尾，這樣很沒效率，解決方法是將page table放到快取中，稱為Translation Lookaside Buffer(TLB)
:::

### Translation Lookaside Buffer(TLB)
> 使用物理記憶體進行虛擬位置翻譯的成本太高因此使用快取增加他的速度。而快取的tag bit就是virtual page number


Example:

## MIT 6.004 Lecture 21, Operating System: IO and System Calls