Things to Know 1 Midterm 2

What is the formula for average memory access time? What about total cycles used?

Avg = hitTime + missRate * missPenalty

total = hitTime * accesses + missPenalty * misses

What is access / memory latency?

How many machine cycles it takes to access data

What is the L1 cache usually broken down into? What do the other caches usually do? What is L0?

I cache (instructions), D cache (data)

Remember both (shared)

Registers

What is temporal locality? What is good/high vs bad/low?

Describes pattern in time; how frequently program uses same data

Good/high → same data used over and over in short period

Bad/low → data used once or rarely

What is spatial locality? What is good/high vs bad/low?

Describes pattern in space; accessing data near other recently accessed data

Good/high → access nearby data many times

Bad/low → jumps around addresses ignoring lots of data

What is the complement of hit rate and how can you use it to calculate hit rate?

hitRate = 1 - missRate

How is a cache generally organized?

S sets, E lines per set, B = bytes per cache block

How is the address of some data laid out?

First t bits = tag, next s bits = set index, last b bits = block offset

What is considered a cache hit?

That set has that tag AND it’s valid

What is a direct mapped cache?

1 line per set

What does E-way set associative cache mean?

E lines per set

What is a write hit? What are the 2 subsequent actions possible?

Writing a value that’s already in the cache

1. Write through: write to cache and memory at same time

2. Write back: defer write to memory until line is replaced

What is a write miss? What are the 2 subsequent actions possible?

Writing a value that’s no longer in the cache

1. Write allocate: fetch value from memory and pull up through cache hierarchy, then write back

2. No write allocate: write directly to memory

What are the 3 abstractions provided by the kernel?

1. Processes (abstraction for processor)

2. Virtual memory (abstraction for main memory)

3. Files (abstraction for I/O devices)

What exactly is a process and what does it know and do? What is the kernel’s scope?

Instance of running program; knows only of itself and possibly talks to other processes with IPC

Knows everything and controls everything

Do system calls or library functions reset errno to 0?

NO

What is a file descriptor (FD) and how many does each process have?

Non negative integer referring to an open file (used with all types of open files)

Each process has own set of FDs

What are the 3 always open FDs?

0 → stdin = STDIN_FILENO

1 → stdout = STDOUT_FILENO

2 → stderr = STDERR_FILENO

Explain “int fd3 = open(pathName, flags, mode);”

pathName = file’s name

flags = read, write, or both

mode = permissions for a new file (optional)

Success → return lowest unused FD, err → return -1

Explain “ssize_t numread = read(fd, buffer, count);”

Stores at most count bytes and stores them in buffer

Returns num bytes actually read

Explain “ssize_t write (fd, buffer, count);”

Writes up to count bytes from buffer into open file

Returns num bytes actually read

Explain “off_t lseek(int fd, off_t offset, int whence);” (return val, args, whence)

Success → return new offset, err → return -1

offset = num bytes to move

whence = point from where offset interpreted

1. SEEK_SET: beginning

2. SEEK_CUR: current position

3. SEEK_END: end

END and CUR can take negative offset, SET must be non-negative

How is main memory organized (RAM)?

M contiguous 1 byte cells (each has physical address, PA)

0 indexed

Partitioned into blocks called physical pages

How is virtual memory (VM) organized?

N contiguous 1 byte cells stored on disk

Partitioned into blocks called virtual pages

What is the page table? How is it organized? What do PTEs consist of?

Way for VM to find page if cached or find on disk if miss, cache it, and handle eviction

Array of PTEs (page table entries) each point to physical address (in RAM)

Valid bit + n bit address field

What is a page fault in address translation?

Page isn’t cached in RAM

What is paging/swapping/page allocation?

After page fault, OS does this to put needed page in RAM

What is a virtual address composed of?

VPN + VPO

Virtual page number + Virtual page offset

VPN = index into page table → VPN # bits = log base 2 (# of PTEs)

# bits for VA = log base 16 (# VAs)

How do you generate the physical address of a virtual address?

PPN + VPO

Physical page number + Virtual page offset

What do the page table entries of the page table hold?

Valid bit + PPN (Physical Page Number bits)