Operating Systems 2017F Lecture 9 - Revision history

Rquaium: /* Additional Notes */

2017-10-06T20:01:02Z

Additional Notes

← Older revision		Revision as of 20:01, 6 October 2017
Line 176:		Line 176:
	== Additional Notes ==		== Additional Notes ==

	~~Admin stuff~~
	~~Assignment extended until Thursday~~
	~~Next week no tutorial~~
	~~Midterm Nov 7~~
	~~Assignment 2 up next week and Assignment 1 due soon~~

	~~Notes~~
	Mmap		Mmap
	-----------------		-----------------
Line 299:		Line 292:

	We use page table (It's similar to a tree)		We use page table (It's similar to a tree)

	~~### ### ### ###~~
	~~**** ** ** ****~~

	A page is 4k		A page is 4k

Rquaium: /* Notes */

2017-10-06T19:59:56Z

Notes

Show changes

Soma: /* Video & Audio */

2017-10-05T19:31:49Z

Video & Audio

← Older revision		Revision as of 19:31, 5 October 2017
Line 1:		Line 1:
	==Video & Audio==		==Video & Audio==

	Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.~~mp4~~ available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.		Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.m4a available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.

	==Notes==		==Notes==

Soma: /* Video & Audio */

2017-10-05T19:29:43Z

Video & Audio

← Older revision		Revision as of 19:29, 5 October 2017
Line 1:		Line 1:
	==Video & Audio==		==Video & Audio==

	Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.~~m4a~~ is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.~~m4a~~ available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.		Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.mp4 available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.

	==Notes==		==Notes==

Soma: /* Video & Audio */

2017-10-05T19:29:17Z

Video & Audio

← Older revision		Revision as of 19:29, 5 October 2017
Line 1:		Line 1:
	==Video & Audio==		==Video & Audio==

	Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.~~mp4~~ is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.~~mp4~~ available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.		Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.m4a is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.m4a available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.

	==Notes==		==Notes==

Soma: Created page with "==Video & Audio== Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now..."

2017-10-05T19:25:34Z

Created page with "==Video & Audio== Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now..."

New page

==Video & Audio==

Video from the lecture given on October 5, 2017 [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-video.mp4 is now available]. Unfortunately this file does not have audio; however, the audio is [http://homeostasis.scs.carleton.ca/~soma/os-2017f/lectures/comp3000-2017f-lec09-05Oct2017-audio.mp4 available separately]. If someone feels like combining the files let me know, I'll upload the combined version here.

==Notes==

===In-Class===

<pre>
Lecture 9
---------

virtual memory

every process gets its own "memory map"
- its own range of addresses
- address 2000 is different in each process, for example

However, RAM is accessed by addresses
- every byte of RAM has a unique address

RAM is accessed using physical addresses
Processes access memory using virtual addresses

Need a mechanism to translate virtual to physical addresses
*on every memory access by a process* (code and data)

Virtual address 2000 for PID 4512 -> physical address 512241
- mapping has to be fast, because this limits speed of all computation

Mapping is accomplished at runtime by hardware, using information provided by the operating system (kernel)

When the CPU (core) switches from running one process to the next, the mappings must get updated

What if a virtual address has no corresponding physical address (for that process)?
-> you get a segfault or similar error

mmap is one tool for manipulating the virtual memory map of a process
-> virtual address range corresponds to contents of a file, not physical RAM
-> but you can also use it to get RAM

Why not just make all virtual addresses correspond to some physical RAM address?
- revoke access
- not nearly enough RAM to do this, even if you pretend disk is RAM

Memory allocation
-----------------
memory allocator challenges
- need contiguous address ranges for parts of data structures
(arrays)
- you can't move a data structure once it has been allocated (easily)
- pointers become invalid
- programs allocate and free memory all the time
- some will have long lifetimes, some short

"-" not allocated
"*" allocated

----*****----*****------*********----

want to allocate *********
room for number of "slots", but not contiguously

- this problem is known as "fragmentation"
- arises when you have variable-sized allocations

- solution is to use fixed-sized allocations
- but now you waste storage
(that's a "fragmentation" too)

- internal fragmentation: space you waste in an allocation
(using a 4K file for a 1 byte of data)

- external fragmentation: the example above

- normally we choose internal fragmentation over external fragmentation
- so all low-level allocations are in fixed-sized units *that
can be placed anywhere*
- how to keep this from limiting the size of arrays?
"virtualizing" the indexing (addresses)

With both disk and memory, low-level storage is allocated in fixed-sized chunks. In memory, called a page. On disk, a block

sizes are always a power of 2
- because indexes have to be stored in a fixed number of bits
- this is why we use hexadecimal or octal, not decimal, to refer to memory
indexes (addresses)

Each hexadecimal digit maps to 4 bits
Each octal digit maps to 3 bits
Decimal digits map to less than 4 bits

memory indexes are in bits, so use something that is convenient for bits

-*---***
01234567 <-- "physical"

0->0
1->4 virtual to physical mapping
2->2 must consult on every memory (array) access
3->3 accelerate this with hardware!

----****
01234567 <-- "virtual"

array is range 0-3
so when we do a[1] in virtual land, we get the contents of 4

process virtual addresses are contiguous, physical memory storage isn't.
- at the boundary of allocation

A table for mapping every byte in memory to another byte would be very big

Typically table maps 4K or more at a time (power of 2)

32-bit addresses
allocate in 4K units (pages)
- 12 bits of address

no contiguous storage in physical memory for anything larger than 4K.

fragmentation in upper 20 bits,

8 bits, 2^8 is 256
2^12 = 4096, which is 4K

upper 20 bits: where to put the page
lower 12 bits: where in the page

I need a data structure that can map 20 bits to 20 bits
with this, I map the upper 20 bits and copy the lower 12 bits
(from virtual to physical)

lower 12 bits is a page offset
upper 20 bits is the page number

page->frame mapping
(frames are RAM, pages are virtual)

I have to store the page to frame mapping inside pages
- and I can't have them be contiguous

This data structure is known as a page table, but really it is a tree

### ### ### ###
****** ****** ****** ******

how many mappings can you fit in a page?

a page is 4K
every address is 32 bits (4 bytes)
fit 1024 "pointers" into a page
- that 10 bits

if I only had 4 megabytes of memory, I just need a page table that can
fit in one page

If I want more, I have a page that points to pages

1 page: 1024 pointers each referring to a page
up to 1024 (2^10) pages: each of those pages has 1024 pointers
up to 1048576 (2^20) pages: each of those has 4096 bytes of data

need 10 bits for offset in page directory
10 bits for offset in page table
12 bits for offset in data page
32 bits total
</pre>