1 of 64

Operating Systems, Virtual Memory Intro

Instructor: Morgan Rae Reschenberg

2 of 64

Agenda

OS Intro
Administrivia
OS Boot Sequence and Operation
Multiprogramming/time-sharing
Introduction to Virtual Memory

CS61C Su18 - Lecture 22

2

7/30/2018

3 of 64

CS61C so far…

CS61C Su18 - Lecture 22

3

7/30/2018

CPU

Caches

Memory

RISC-V Assembly

C Programs

�#include <stdlib.h>

int fib(int n) {

return� fib(n-1) +� fib(n-2);

}

.foo

lw t0, 4(s0)

addi t1, t0, 3

beq t1, t2, foo�nop

Project 1

Project 2

Labs

Project 3

4 of 64

But wait…

When we run Venus, it only executes one program and then stops.
When I switch on my computer, I have many programs:

CS61C Su18 - Lecture 22

4

7/30/2018

Yes, but that’s just software! The Operating System (OS)

5 of 64

Well, “just software”

The biggest piece of software on your machine?
How many lines of code? These are guesstimates:

CS61C Su18 - Lecture 22

5

7/30/2018

84 million lines of code!

6 of 64

What is an operating system?

6

Computer Hardware

(CPU, SSD/HD, RAM, …)

Operating System

Applications

(“Software”)

Operating systems control how software applications access and use hardware on your computer. They provide a general interface for common actions (ex. reading/writing disk) and allow software to run without knowledge of the machine it lives on!

7 of 64

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.g., devices)

Services: File System, Network stack, etc.
Finds and controls all the devices in the machine in a general way (using “device drivers”)

CS61C Su18 - Lecture 22

7

7/30/2018

8 of 64

What is an operating system?

8

9 of 64

Have we always had OS?

Operating “systems” used to just be “operators”; these were people, usually women!

9

As late as the 1960s many people perceived computer programming as a natural career choice for savvy young women. Even the trend-spotters at Cosmopolitan Magazine urged their fashionable female readership to consider careers in programming. In an article titled “The Computer Girls,” the magazine described the field as offering better job opportunities for women than many other professional careers. As computer scientist Dr. Grace Hopper told a reporter, programming was “just like planning a dinner. You have to plan ahead and schedule everything so that it’s ready when you need it…. Women are ‘naturals’ at computer programming.” James Adams, the director of education for the Association for Computing Machinery, agreed: “I don’t know of any other field, outside of teaching, where there’s as much opportunity for a woman.”

10 of 64

What’s “different” about various OS?

Different experience for the user

Organisation, appearance, etc.

Different interfaces for applications

Windows software won’t run on Mac OS!

Different levels of licensing, availability, hardware support

Linux is open source
MacOS can only run on Mac machines (sorta…)
Windows can be purchased independently of a Microsoft computer

10

11 of 64

Unix based, or … not

In CS we often prefer systems that are “Unix-based” but what does that mean?

Unix was developed in AT&T’s Bell Labs back in the mid-to-late 1960’s.
Built modularly, strong file system core
MacOS, Linux descended from this! Berkeley (BSD) played a part!

Windows developed independently of this unix craze!

11

12 of 64

Agenda

OS Intro
Administrivia
OS Boot Sequence and Operation
Multiprogramming/time-sharing
Introduction to Virtual Memory

CS61C Su18 - Lecture 22

12

7/30/2018

13 of 64

Administrivia

Project 4 released! Due: Friday, August 9th

Project party: Wednesday (7th) 6:30-8:30 in Cory 540AB
NOTE: You do //not// have control over when the autograder runs! Start early so we can test your code before the deadline!

Guerrilla session this Thursday, 7p @ 540AB Cory

Start reviewing for the final, please attend!

MT2 grades will be released soon :)

CS61C Su18 - Lecture 22

13

7/30/2018

14 of 64

Agenda

OS Intro
Administrivia
OS Boot Sequence and Operation
Multiprogramming/time-sharing
Introduction to Virtual Memory

CS61C Su18 - Lecture 22

14

7/30/2018

15 of 64

What happens at boot?

When the computer switches on, it does the same as Venus: the CPU executes instructions from some start address (stored in Flash ROM)

CS61C Su18 - Lecture 22

15

7/30/2018

1. BIOS: Find a storage�device and load first sector (block of data)

2. Bootloader (stored on, e.g., disk): Load the OS kernel from disk into a location in memory and jump into it.

3. OS Boot: Initialize services, drivers, etc.

4. Init: Launch an application that waits for input in loop (e.g., Terminal/Desktop/...

16 of 64

Launching Applications

Applications are called “processes” in most OSs.
Created by another process calling into an OS routine (using a “syscall”, more details later).

Depends on OS, but Linux uses fork (see OpenMP threads) to create a new process, and execve to load application.

Loads executable file from disk (using the file system service) and puts instructions & data into memory (.text, .data sections), prepare stack and heap.
Set argc and argv, jump into the main function.

CS61C Su18 - Lecture 22

16

7/30/2018

17 of 64

Supervisor Mode

If something goes wrong in an application, it can crash the entire machine. What about malware, etc.?
The OS may need to enforce resource constraints to applications (e.g., access to devices).
To protect the OS from the application, CPUs have a supervisor mode bit (also need isolation, more later).

You can only access a subset of instructions and (physical) memory when not in supervisor mode (user mode).
You can change out of supervisor mode using a special instruction, but not into it (unless there is an interrupt).

CS61C Su18 - Lecture 22

17

7/30/2018

18 of 64

What is an operating system?

18

19 of 64

Syscalls

How to switch back to OS? OS sets timer interrupt, when interrupts trigger, drop into supervisor mode.
What if we want to call into an OS routine? (e.g., to read a file, launch a new process, send data, etc.)

Need to perform a syscall: set up function arguments in registers, and then raise software interrupt
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.

CS61C Su18 - Lecture 22

19

7/30/2018

20 of 64

Syscalls in Venus

Venus provides many simple syscalls using the ecall RISC-V instruction
How to issue a syscall?

Place the syscall number in a0
Place arguments to the syscall in the a1 register
Issue the ecall instruction

This is how your RISC-V code has been able to produce output all along
ecall details depend on the ABI (Application Binary Interface)

CS61C Su18 - Lecture 22

20

7/30/2018

21 of 64

Example Syscall

Let’s say we want to print an integer stored in s3:

Print integer is syscall #1

li a0, 1

add a1, s3, x0

ecall

CS61C Su18 - Lecture 22

21

7/30/2018

22 of 64

Venus’s Environmental Calls

CS61C Su18 - Lecture 22

22

7/30/2018

23 of 64

Agenda

OS Intro
Administrivia
OS Boot Sequence and Operation
Multiprogramming/time-sharing
Introduction to Virtual Memory

CS61C Su18 - Lecture 22

23

7/30/2018

24 of 64

Multiprogramming

OS runs multiple applications at the same time.
But not really (unless have a core per process)
Switches between processes very quickly. This is called a “context switch”.
Deciding what process to run is called scheduling.

Programs can be scheduled in a variety of ways!
Most/least resources needed, “fastest” to run, most important, etc.

CS61C Su18 - Lecture 22

24

7/30/2018

25 of 64

User mode: multiple applications

25

CPU

RAM

Process A

Process B

26 of 64

User mode: multiple applications

26

CPU

RAM

Process A

Process B

27 of 64

User mode: multiple applications

27

CPU

RAM

Process A

Process B

Process A

28 of 64

User mode: multiple applications

28

CPU

RAM

Process A

Process B

Process A

SWITCH

29 of 64

User mode: multiple applications

29

CPU

RAM

Process A

Process B

Process A

Process B

Wait… that shouldn’t happen!

30 of 64

User mode: multiple applications

30

CPU

RAM

Process A

Process B

Process A

Process B

Please give me Process A’s data! I am evil!

31 of 64

User mode: multiple applications

31

CPU

RAM

Process A

Process B

Process A

Process B

Process C

32 of 64

User mode: multiple applications

32

CPU

RAM

Process A

Process C

Process D

Hmm… There’s enough space, but not all together!

33 of 64

User mode: multiple applications

33

CPU

RAM

Process A

Process C

Process D

There we go!

34 of 64

User mode: multiple applications

34

CPU

RAM

Process A

Process C

Process D

Wait… This isn’t my data?

35 of 64

Protection, Translation, Paging

Supervisor mode does 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 (e.g., for sparse data structures).

Solution: Virtual Memory. Give each process the illusion of a full memory address space that it has completely to itself.

CS61C Su18 - Lecture 22

35

7/30/2018

36 of 64

CS61C Su18 - Lecture 4

36

6/21/2018

BREAK

37 of 64

Protection, Translation, Paging

Supervisor mode does 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 (e.g., for sparse data structures).

Solution: Virtual Memory. Give each process the illusion of a full memory address space that it has completely to itself.

CS61C Su18 - Lecture 22

37

7/30/2018

38 of 64

Virtual Memory

From here on out, we’ll be working with two different memory spaces:

Virtual Memory (VM): A large (~infinite) space that a process believes it, and only it, has access to
Physical Memory (PM): The limited RAM space your computer must share among all processors

Goals:

Process/program isolation
Make transition from infinite to finite seamless, or not noticeable to the program
Translate between VM, PM addresses

38

39 of 64

Virtual: The Illusion!

39

CPU

RAM

Process A

I am the ONLY PROCESS accessing memory, and I don’t have to share it with anyone!

40 of 64

Physical: The Reality!

40

CPU

RAM

Process A

Process B

Process A

Process B

Process C

DISK

41 of 64

Adding Disks to Hierarchy

Use VM as a mechanism to “connect” memory and disk in the memory hierarchy

CS61C Su18 - Lecture 22

41

7/30/2018

42 of 64

Memory Hierarchy

CS61C Su18 - Lecture 22

42

7/30/2018

Regs

L2 Cache

Memory

Disk

Tape

Instr Operands

Blocks

Pages

Files

Upper Level

Lower Level

Faster

Larger

L1 Cache

Blocks

Now:

Virtual�Memory

Earlier:�Caches

43 of 64

Agenda

OS Intro
Administrivia
OS Boot Sequence and Operation
Multiprogramming/time-sharing
Introduction to Virtual Memory

CS61C Su18 - Lecture 22

43

7/30/2018

44 of 64

Virtual Memory Goals

Allow multiple processes to simultaneously occupy memory and provide protection: 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

CS61C Su18 - Lecture 22

44

7/30/2018

45 of 64

Segmented Memory

Divide RAM into segments with a “base” and “bound”

Each program has access to its segment only!

Program has a virtual address range 0x0...0 - 0xF...FE

To get location of data in segment (physical address), add to base value!

45

46 of 64

Segmented Memory

46

CPU

Process A

Process B

Process A

Process B

baseA

boundA

baseB

boundB

47 of 64

Simple Base and Bound Translation

CS61C Su18 - Lecture 22

47

7/30/2018

Load X

Program

Address Space

Bound

Register

Bounds

Violation?

Physical Memory

current

segment

Base

Register

+

Physical

Address

Logical

Address

Base and bounds registers are visible/accessible only when processor is running in supervisor mode

Base Physical Address

Segment Length

≤

48 of 64

Where have we seen segments before?

Stack, Heap, Static, Code, etc. !

Base & bound model was used to keep segments independent of each other on earlier machines; still used in some memory models (x86) today!

48

49 of 64

“Bare” 5-Stage Pipeline

In a bare machine, the only kind of address is a physical address

CS61C Su18 - Lecture 22

49

7/30/2018

PC

Inst. Cache

D

Decode

E

M

Data Cache

W

+

Main Memory (DRAM)

Memory Controller

Physical Address

50 of 64

Base and Bound Machine

CS61C Su18 - Lecture 22

50

7/30/2018

PC

Inst. Cache

D

Decode

E

M

Data Cache

W

+

Main Memory (DRAM)

Memory Controller

Physical Address

Data Bound Register

Data Base Register

≤

+

Logical Address

Bounds Violation?

Physical Address

Prog. Bound Register

Program Base Register

≤

+

Logical Address

Bounds Violation?

51 of 64

Base & Bound: Problems!

What if we need more space than our segment allows?

Increase segment? What if no more RAM?

Use disk? How do we decide what data to move in or out? How much data?

What if we require 500MB of space, but RAM is fragmented, so there isn’t a contiguous chunk available?

How can we fix this?

51

52 of 64

Talk with your neighbours!

How can we fix our problems with base & bound? is there a better scheme?

Must provide protection b/t processes

Programs can only find/access their own data

Must be able to work with more data than RAM can hold

Swap to and from disk

Must not fragment memory in an unusable way

If need 500MB, and have 500MB available overall, should be usable

52

53 of 64

Paged Memory!

Instead of having segments of various sizes, let’s divide physical memory and virtual memory into equal units called pages!

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?

53

54 of 64

Virtual: The Illusion!

54

CPU

RAM

Process A

I am the ONLY PROCESS accessing memory, and I don’t have to share it with anyone!

0

1

2

3

4

5

6

7

8

9

10

55 of 64

Physical: Paged Memory

55

CPU

Process A

Process B

Process A

Process B

Process A

Process B

Process A

0

�1

2

3

4

5

6

Physical Memory (RAM)

Shared

56 of 64

Paged Memory!

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?

56

57 of 64

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 note 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!

57

58 of 64

58

CPU

Process A

Process B

Process A

Process B

Process A

Process B

Process A

0

�1

2

3

4

5

6

Physical Memory (RAM)

Shared

VPN	PPN	Valid?
0
1
2
3
4
5
6
7
8

59 of 64

59

CPU

Process A

Process B

Process A

Process B

Process A

Process B

Process A

0

�1

2

3

4

5

6

Physical Memory (RAM)

Shared

Virtual Memory

(Process B Only!)

0

�1

2

3

4

5

6

7

8

Process B

VPN	PPN	Valid?
0	2	1
1
2
3	6	1
4
5
6
7	4	1
8

60 of 64

60

CPU

Process A

Process B

Process A

Process B

Process A

Process B

Process A

0

�1

2

3

4

5

6

Physical Memory (RAM)

Shared

Virtual Memory

(Process B Only!)

0

�1

2

3

4

5

6

7

8

Process B

VPN	PPN	Valid?
0	2	1
1	X	0
2	X	0
3	6	1
4	X	0
5	X	0
6	X	0
7	4	1
8	X	0

61 of 64

iClicker!

You have a machine with 4 pages of Physical Memory and 8 pages of Virtual Memory.
How many rows are there in one page table? What is the maximum number of valid entries a page table can have?�
4 rows, 4 valid
8 rows, 4 valid
8 rows, 8 valid
12 rows, 4 valid
12 rows, 8 valid

61

62 of 64

Modern Virtual Memory Systems� Illusion of a large, private, uniform store

CS61C Su18 - Lecture 22

62

7/30/2018

Protection

several programs, each with their private address space and one or more shared address spaces

Demand Paging

Provides the ability to run programs larger than the primary memory

Hides differences in machine configurations

The price is address translation on

each memory reference

OS

prog_i

Primary

Memory

Swapping

Store

VA

PA

mapping

TLB

63 of 64

Virtual Memory Goals

Next level in the memory hierarchy:

Provides program with illusion of a very large main memory:
Working set of “pages” reside in main memory - others reside on disk.

Also allows OS to share memory, protect programs from each other
Today, more important for protection vs. just another level of memory hierarchy
Each process thinks it has all the memory to itself
(Historically, it predates caches)

CS61C Su18 - Lecture 22

63

7/30/2018

64 of 64

Summary

The role of the Operating System

Booting a computer: BIOS, bootloader, OS boot, initialization

Base and bounds for multiple processes

Simple, but doesn’t give us everything we want

Virtual memory bridges memory and disk

Provides illusion of independent address spaces to processes and protects them from each other

CS61C Su18 - Lecture 22

64

7/30/2018