程序代写

Virtual Memory
15-213: Introduc0on to Computer Systems Recita0on 10: Nov. 2, 2015

Copyright By PowCoder代写 加微信 powcoder

¢ Shell Lab FAQs and I/O
¢ Malloc Lab Preview
¢ Virtual Memory Concepts
¢ Address TranslaCon § Basic
§ MulClevel

¢ Shell Lab is due Tuesday (tomorrow), 11:59 p.m.
¢ Malloc Lab is out Tuesday (tomorrow), 11:59 p.m. § Due Thursday, Nov. 19
§ Start early!!
§ “The total 0me you spend designing and debugging can easily eclipse the 0me you spend coding.”

Shell Lab FAQ
¢ “The traces behave differently from command-line input!”
§ Some people are confused to find /bin/echo on their jobs list aPer running some trace files.
§ Some traces (e.g. trace05) print what they’re running before they run them. They do this by using /bin/echo.
§ So if you see a mysterious /bin/echo show up on your jobs list, you shouldn’t wonder why it got on your jobs list, you should wonder why it never got deleted.
§ Moral of the story: open the trace file and see what it does!

Shell Lab FAQ ¢ Sigsuspend???
§ You can only use waitpid() once, but there are probably two places you probably need to reap children (one for foreground jobs, one for background jobs).
§ Tempta0on: use waitpid() for background jobs; use sleep() or a 0ght loop (i.e., while(1) {}).
§ Correct solu0on: use sigsuspend to block your process un0l a signal arrives.
¢ int sigsuspend(const sigset_t *mask)
§ Temporarily replaces the process’s signal mask with mask, which
should be the signals you don’t want to be interrupted by.
§ sigsuspend will return aPer an unblocked signal is received and its handler run. When it returns, it automa0cally reverts the process signal mask to its old value.

Shell Lab FAQ: sigsuspend example
int main() {
sigset_t waitmask, newmask, oldmask;
/* set waitmask with everything except SIGINT */
sigfillset(&waitmask);
sigdelset(&waitmask, SIGINT);
/* set newmask with only SIGINT */
sigemptyset(&newmask);
sigaddset(&newmask, SIGINT);
if (sigprocmask(SIG_BLOCK, &newmask, &oldmask) < 0) //oldmask now stores prev mask unix_error("SIG_BLOCK error"); /* CRITICAL REGION OF CODE (SIGINT blocked) */ /* pause, allowing ONLY SIGINT */ if (sigsuspend(&waitmask) != -1) unix_error("sigsuspend error"); /* RETURN FROM SIGSUSPEND (returns to signal state from before sigsuspend) */ /* Reset signal mask which unblocks SIGINT */ if (sigprocmask(SIG_SETMASK, &oldmask, NULL) < 0) unix_error("SIG_SETMASK error"); System Calls and Error Handling ¢ System Call Error Handling ¢ Always handle errors for every system call – #include
§ Failed system calls almost always return -1 § Global integer error number: errno
§ Ge\ng error descrip0on: strerror(errno)
¢ We deduct style points for not handling system call errors
¢ Do not lose style points here!
¢ Easy soluCon : Use wrappers from CSAPP website (Fork(),Execve(),Sigprocmask()…)

I/O Basics
¢ Four basic operaCons: § open
§ close § read § write
¢ What’s a file descriptor?
§ Returned by open.
§ int fd = open(“/path/to/file”, O_RDONLY);
§ fd is some posi0ve value or -1 to denote error
¢ Every process starts with 3 open file descriptors that can be accessed macros like STDOUT_FILENO
§ 0 – STDIN
§ 1 – STDOUT § 2 – STDERR

How the Unix Kernel Represents Open Files
Two descriptors referencing two disCnct open files. Descriptor 1 (stdout) points to terminal, and descriptor 4 points to open disk file
Descriptor table
[one table per process]
Open file table
[shared by all processes] File A (terminal)
v-node table
[shared by all processes]
File access
stdin fd0 stdout fd1 stderr fd2
File B (disk)
File access

File Sharing
Two disCnct descriptors sharing the same disk file through two disCnct open file table entries
§ E.g., Calling open twice with the same filename argument
Descriptor table
[one table per process]
Open file table
[shared by all processes] File A (disk)
v-node table
[shared by all processes]
File access
stdin fd0 stdout fd1 stderr fd2
File B (disk)

How Processes Share Files: fork
A child process inherits its parent’s open files
§ Note: situa0on unchanged by exec func0ons (use fcntl to change) Before fork call:
Descriptor table
[one table per process]
Open file table
[shared by all processes] File A (terminal)
v-node table
[shared by all processes]
File access
stdin fd0 stdout fd1 stderr fd2
File B (disk)
File access

How Processes Share Files: fork
¢ A child process inherits its parent’s open files
¢ A/er fork:
§ Child’s table same as parent’s, and +1 to each refcnt
Descriptor table
[one table per process] Parent
fd 0 fd 1 fd 2 fd 3 fd 4
Child fd 0
fd 1 fd 2 fd 3 fd 4
Open file table
[shared by all processes] File A (terminal)
v-node table
[shared by all processes]
File access
File B (disk)
File access

I/O RedirecCon
¢ QuesCon: How does a shell implement I/O redirecCon?
linux> ls > foo.txt
¢ Answer: By calling the dup2(oldfd, newfd) funcCon § Copies (per-process) descriptor table entry oldfd to entry newfd
Descriptor table
before dup2(4,1)
fd1 fd1 fd2 fd2
Descriptor table
a/er dup2(4,1)

I/O RedirecCon Example
¢ Step #1: open file to which stdout should be redirected § Happens in child execu0ng shell code, before exec
Descriptor table
[one table per process]
stdin fd0 stdout fd1 stderr fd2
Open file table
[shared by all processes] File A
v-node table
[shared by all processes]
File access
File access

I/O RedirecCon Example (cont.)
¢ Step #2: call dup2(4,1)
§ cause fd=1 (stdout) to refer to disk file pointed at by fd=4
Descriptor table
[one table per process]
stdin fd0 stdout fd1 stderr fd2
Open file table
[shared by all processes] File A
v-node table
[shared by all processes]
File access
File access

Malloc Lab Sneak Preview
¢ You will write your own dynamic storage allocator – i.e.,
your own malloc, free, realloc, calloc.
¢ This week in class, you will learn about different ways to keep track of free and allocated blocks of memory.
§ Implicit linked list of blocks.
§ Explicit linked list of free blocks.
§ Segregated lists of different size free blocks.
¢ Other design decisions:
§ How will you look for free blocks? (First fit, next fit, best fit…) § Should the linked lists be doubly linked?
§ When do you coalesce blocks?
¢ This is exactly what you’ll do in this lab, so pay lots of anenCon in class.J

Malloc Lab Sneak Preview
¢ If you haven’t been using version control so far, this is a good Cme to start.
¢ Workflow:
§ Implement indirect linked lists. Make sure it works.
§ Implement explicit linked lists. Make sure it s0ll works. § Implement segregated lists. Make sure it s0ll works.
§ You WILL break things and need to revert.
¢ Barebones guide to using git on the Shark Machines:
§ git init starts a local repository.
§ git add foo.c adds foo.c to that repository.
§ git commit -a –m ‘Describe changes here’ updates your repository with the current state of all files you’ve added.

¢ Shell Lab FAQs
¢ Malloc Lab Sneak Preview
¢ Virtual Memory Concepts
¢ Address TranslaCon § Basic
§ Mul0level

Virtual Memory Concepts
¢ We’ve been viewing memory as a linear array.
¢ But wait! If you’re running 5 processes with stacks at 0xC0000000, don’t their addresses conflict?
¢ Nope! Each process has its own address space.
0xC0000000
Memory invisible to user code
(stack pointer)
User stack (created at runCme)
0x40000000
0x08048000
Kernel virtual memory
Memory-mapped region for shared libraries
Loaded from the executable file
Run-Cme heap (created by malloc)
Read/write segment (.data, .bss)
Read-only segment (.init, .text, .rodata)

Virtual memory concepts
¢ We define a mapping from the virtual address used by the process to the actual physical address of the data in memory.
Image: hlp://en.wikipedia.org/wiki/ File:Virtual_address_space_and_p hysical_address_space_rela0onshi p.svg

Virtual memory concepts
This explains why two different processes can use the same address. It also lets them share data and protects their data from illegal accesses. Hooray for virtual memory!
Virtual Address Space for Process 1:
Address translaBon
Physical Address Space (DRAM)
(e.g., read-only library code)
Virtual Address Space for Process 2:

Virtual memory concepts
¢ Page table
§ Lets us look up the physical address corresponding to any virtual address. (Array of physical addresses, indexed by virtual address.)
¢ TLB (TranslaCon Lookaside Buffer)
§ A special 0ny cache just for page table entries.
§ Speeds up transla0on.
¢ MulC-level page tables
§ The address space is oPen sparse.
§ Use page directory to map large chunks of memory to a page table.
§ Mark large unmapped regions as non-present in page directory instead of storing page tables full of invalid entries.

¢ Shell Lab FAQs
¢ Malloc Lab Sneak Preview
¢ Virtual Memory Concepts
¢ Address TranslaCon § Basic
§ Mul0level

VM Address TranslaCon
¢ Virtual Address Space
§ V={0,1,…,N–1}
§ There are N possible virtual addresses. § Virtual addresses are n bits long; 2n = N.
¢ Physical Address Space
§ P={0,1,…,M–1}
§ There are M possible physical addresses. § Virtual addresses are m bits long; 2m = M.
¢ Memory is grouped into “pages.”
§ Page size is P bytes.
§ The address offset is p bytes; 2p = P.
§ Since the virtual offset (VPO) and physical offset (PPO) are the same, the offset doesn’t need to be translated.

VM Address TranslaCon
Virtual address
Page table
Page table base register (PTBR)
Virtual page number (VPN)
Virtual page offset (VPO)
Page table address for process
Physical page number (PPN)
Valid bit = 0: page not in memory (page fault)
Physical address
Physical page number (PPN)
Physical page offset (PPO)

VM Address TranslaCon
¢ Addressing
§ 14-bit virtual addresses § 12-bit physical address § Page size = 64 bytes
13 12 11 10 9 8 7 6 5 4 3 2 1 0 VPN VPO
Virtual Page Number Virtual Page Offset
11 10 9 8 7 6 5 4 3 2 1 0
Physical Page Number
Physical Page Offset

Example 1: Address TranslaCon
¢ Pages are 64 bytes. How many bits is the offset?
¢ Find 0x03D4.
13 12 11 10 9 8 7 6 5 4 3 2 1 0
¢ VPN: _____
¢ PPN: ______
¢ Physical address: ___________

Example 1: Address TranslaCon
¢ Pages are 64 bytes. How many bits is the offset? log2 64 = 6
¢ Find 0x03D4.
13 12 11 10 9 8 7 6 5 4 3 2 1 0
¢ VPN: _0_x__0_F 0x0D
¢ PPN: ______
¢ Physical address: ___0_x_0_3_5_4___

¢ Shell Lab FAQs
¢ Malloc Lab Sneak Preview
¢ Virtual Memory Concepts
¢ Address TranslaCon § Basic
§ Mul0level

VM Address TranslaCon with TLB
¢ That’s nice and simple, but it doubles memory usage. § One memory access to look in the page table.
§ One memory access of the actual memory we’re looking for.
¢ SoluCon:
§ Cache the most frequently used page table entries in the TLB.
§ To look up a virtual address in the TLB, split up the VPN (not the whole virtual address!) into a TLB index and a TLB tag.
Cache/ Memory

Example 2: Address TranslaCon with TLB
1 MB of virtual memory 4 KB page size
256 KB of physical memory TLB: 8 entries, 2-way set associa0ve
¢ How many bits are needed to represent the virtual address space?
¢ How many bits are needed to represent the physical address space?
¢ How many bits are needed to represent the offset?
¢ How many bits are needed to represent VPN?
¢ How many bits are in the TLB index?
¢ How many bits are in the TLB tag?

Example 2: Address TranslaCon with TLB
1 MB of virtual memory 4 KB page size
256 KB of physical memory TLB: 8 entries, 2-way set associa0ve
¢ How many bits are needed to represent the virtual address space? 20. (1 MB = 220 bytes.)
¢ How many bits are needed to represent the physical
address space?
¢ How many bits are needed to represent the offset?
12. (4 KB = 212 bytes.)
¢ How many bits are needed to represent VPN? 8. (20-12.)
¢ How many bits are in the TLB index? 2. (4 sets = 22 set bits.)
¢ How many bits are in the TLB tag? 6. (8-2.)
18. (256 KB = 218 bytes.)

Example 2a: Address TranslaCon with TLB
¢ Translate 0x14213, given the contents of TLB and the first 32 entries of the page table below. (All the numbers are in hexadecimal.)

Example 2a: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
TLB Hit! PPN: Offset:
Physical address:
VPN: TLBI: TLBT:

Example 2a: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN: 0x14 TLBI: 0x00 TLBT: 0x05
PPN: 0x13 Offset:0x213
Physical address:

Example 2b: Address TranslaCon with TLB
¢ Translate 0x1F213, given the contents of TLB and the first 32 entries of the page table below.

Example 2b: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN: TLBI: TLBT:

Example 2b: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Step 2: look it up in the page table.L
TLBT: 0x07

Example 2b: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN: 0x1F TLBI: 0x03 TLBT: 0x07
Page Table Hit PPN:
Physical address:

Example 2b: Address TranslaCon with TLB
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN: 0x1F TLBI: 0x03 TLBT: 0x07
Page Table Hit PPN: 0x15 Offset:0x213
Physical address:

¢ Shell Lab FAQs and I/O
¢ Malloc Lab Sneak Preview
¢ Virtual Memory Concepts
¢ Address TranslaCon § Basic
§ Mul0level

Address TranslaCon in Real Life
¢ MulC level page tables, with the first level oten called a “page directory”
¢ Use first part of the VPN to get to the right directory and then the next part to get the PPN
¢ K-level page table divides VPN into k parts

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com