- Compilation
- Compiled and interpreted languages
- programs translated into machine code and executed by hardware
- interpreted code is read and executed by a software interpreter
- some languages can be both or hybrids (java/jvm)
- static types
- in static, you know what type each variable is
- in dynamic language, don’t know until program is running
- static language don’t run unless can compile / also faster bc don’t have to do type checks
- also save storage, assigns variable to an address and don’t have to store variable names in memory at runtime
- the compilation process
- preprocessing (e.g. drop in source code from elsewhere)
- parsing (builds abstract syntax tree)
- static checking (type checking)
- code generation (generates machine/byte code)
- linking (drop in code from libraries if used), optimization (figure out ways to do things more efficiently)
- object code
- not executable but can be linked into an executeable
- assembly code
- human readable form of machine code
- understanding errors
- can figure out where the process when wrong
- syntax errors from compiler, incorrect function use from linker, missing include from preprocessor, etc
- Processes
- Abstraction and virtualization
- abstraction is the simplified representation of something complicated
- virtualization is a kind of abstraction for creating a desirable illusion (e.g. a library connected to a system allowing for a bigger selection; the internet)
- Isolation
- change in one component doesn’t affect another
- OS isolates programs running concurrently with processes
- process contains text of program (seq of machine code), data (static and dynamic), state of any pending IO operations, hardware state
- OS separate with multitasking (can interrupt a running process and pick up anytime), virtual memory (make it seem like a process has own chunk of memory), device abstraction (os coordinates and maintains order instead of each process interacting with hardware directly)
- Virtual Memory
- A bit of information theory
- b bits can indicate one of 2^b values e.g. a byte can hold one of 256 values
- log2N to know how many bits you need
- Memory and storage
- when process is running, most data in main memory (usually RAM)
- Address spaces
- each byte in main memory is specified by an integer “physical address”
- most OS provide virtual memory so don’t have to deal with physical addresses
- 32-bit and 64-bit systems indicate size of registers / usually also size of virtual address
- virtual address space is 2^32 for 32-bit and 2^64 for 64-bit
- OS helps map virtual address to physical address
- processes generally can’t access data belonging to another process
- Memory segments
- data of process organized in 4 segments: (static machine language text, static segment containing variables, run time stack which holds parameters and local variable of a function, heap segment which store chunks of memory allocated at run time)
- text is at bottom (near 0), static segment is just above, stack is near top and expands down, heap is above static, and expands up
- global variables in static segment and local variables in stack
- addresses returned by malloc in heap
- Static local variables
- local static variables can be assigned to static segment instead of stack
- Address translation
- most processors have a memory management unit (MMU) that sits between CPU and main memory which quickly translates between physical and virtual addresses
- 1) the CPU generates a read/write when a program reads/writes
- 2) MMU splits VA into page number (chunk of memory 1-4KiB) and the offset
- 3) MMU looks up page number in page table and gets the corresponding physical page and uses offset to get PA
- 4) PA is passed to main memory and reads or writes to it
- page tables are sparse, many OS use multilevel page table
- OS can context switch but needs to make sure each process gets right page table
- Files and file systems
- Intro
- data can be persisted on HDD or SSD, but file system provides good abstraction
- Abstracts like a key value store (filename, contents) and file is a sequence of bytes
- files are byte-based and persistent storage is block-based (1-8Kib)
- during a read, os check if next char is in memory if not makes IO request to get next block
- during a write, 1) find file and make it if not exists and set position to 0. 2) write to memory / buffers 3) when closed, buffered data is written to disk
- Disk performance
- read / write from disk much slower, so os switches to other tasks while this is happening
- measures to fill gap between reading from memory and disk
- Block transfer, prefetching, Buffering (can write to disk at once), Caching (likely to use block again)
- some disks provide a cache that stores recently used blocks
- programmers usually don’t have to think about unless 1) really bad performance 2) when data is buffered
- Disk metadata
- files can be but don’t have to be stored in contiguous memory
- UNIX inodes (index node) contain meta data and can have pointers to other blocks
- Block allocation
- file system keeps track which blocks belong to each file:
- 1) allocate and free blocks quickly
- 2) minimal space overhead
- 3) minimal fragmentation
- 4) maximum contiguity
- requires trade-offs to maximize different factors
- Everything is a file?
- file abstraction is a stream of bytes abstraction
- also applicable to piping between files or network communication
- More bits and bytes
- Representing integers
- two’s complement easier to work with in hardware
- to make negative flip all bits and add 1
- the leftmost bit acts like a sign bit
- Bitwise operators
- & (AND): can use as mask to select and clear bits
- | (OR): can use to set values
- ^ (XOR): can use to toggle values
- Representing floating-point numbers
- In IEEE 32-bit standard, leftmost is the sign, next 8 are the exponent, and the last 23 bits are the cofficient (-1)^s * c * (2^q)
- Unions and memory errors
- can use to represent number that might be different types
- unions are error prone
- Memory management
- dynamic memory allocation in C
- malloc: takes integer size in bytes and returns pointer to newly allocated chunk of memory with given size
- calloc: like malloc but sets bytes in chunk to 0
- free: takes a pointer to previously allocated chunk and deallocates it
- realloc: takes a pointer and new size and copies over and frees old chunk
- memory errors
- 1) access chunk not allocated 2) try to access chunk thats been freed 3) free chunk not allocated 4) free same chunk more than once 5) realloc on chunk that was not allocated
- in large program, changes in one part can affect many other parts
- different parts of the program might refer to the same chunk / need good documentation
- trying to read from unallocated chunk can return odd values and cause odd errors
- writing to an unallocated chunk / might not find out until later or can mangle the data structures used to implement malloc and free
- should be disciplined about using API
- tradeoff between safe memory management and performance
- memory leaks
- allocate but never free
- usually fine if short bc os will clear, but bad if long-running
- can run out of physical memory / malloc will fail
- in virtual memory, can move another process’s page from memory to disk
- good practice to check malloc before using it
- implementation
- not all programs allocate data dynamically
- malloc does not depend on size of chunk but how many free chunks there are
- boundary tags provide information about size and state. free chunks are chained into a doubly-linked list
- boundary tags and free list pointers take up space, for small structures maybe better to use arrays
- allocating and freeing can cause fragmentation / wastes space and slows program
- Caching
- How programs run
- os creates process, loader copies the text to main memory and calls main
- program counter: contains address of next instruction
- instruction register: contains the machine code instruction of currently executing
- stack pointer: address of the stack frame for the current function w/ parameters and local vars
- general-purpose registers: holds data program is currently working with
- status register: info on current computation
- CPU fetches (instruction register), decodes (control unit) and executes
- instruction set types: load (memory to register), arithmetic/logic (operands), store (register to memory), jump/branch (changes program counter)
- transfer of data to and from memory would cause a memory bottle neck
- Cache performance
- cache is small fast memory on same chip as CPU
- faster if more cache hits / cache speed
- Locality
- blocks are loaded together
- programs tend to use the same data more than once “temporal locality”
- Measuring cache performance
- good cache performance if array is smaller
- Programming for cache performance
- usually implemented in hardware, but can take advantage if you understand
- traverse large array once
- traverse 2d array row-wise
- allocating nodes at once so contiguous
- recursive strategies like merge-sort breaks data into smaller pieces
- disadvantage of cache-aware algorithms is they are hardware-specific
- The memory hierarchy
- caches are fast bc they are small otherwise would be slower
- flash drives are fast but more expensive
- each level acts as a cache for the one below it
- Caching policy
- LRU or least recently used removes from the cache a block of data that has not been used recently
- Paging
- in systems with virtual memory the OS can move pages back and forth between memory and storage “paging” or “swapping”
- most processes don’t use all of their allocated memory
- the total memory allocated to all processes can exceed the size of physical memory
- when processes evict each other leads to trashing / slow
- Multitasking
- Intro
- kernel implements multi-tasking
- kernel’s job is to handle interrupts
- Hardware state
- handling interrupts requires cooperation between hardware and software
- hardware is responsible for saving program counter so kernel knows where to resume
- 1) when interrupt, hardware saves program counter and jumps to interrupt handler
- 2) interrupt handler stores program counter and the flag register in memory along with contents of any data registers
- 3) the interrupt handler runs code to handle the interrupt
- 4) restores contents of saved registers, and program counter
- context switching
- loads all registers relatively slow
- the process life cycle
- when process created OS allocates data structure that contains info called process control block PCB
- PCB keeps track of 1) running 2) ready, 3) blocked, 4) done
- state is transitioning from one to another
- scheduling
- scheduler tries to minimize response time
- a lot of computation is CPU bound
- a lot of network or disk is IO bound
- scheduler chooses based on priority
- I/O bound has higher priority
- long-running CPU-bound priority lower
- if blocks for a long time and then becomes ready, should get boost
- real-time scheduling
- modifications
- 1) provide richer api for controlling task priorities
- 2) modify scheduler to guarantee process with highest priority runs within a fixed amount of time
- 3) reorg interrupt handlers to guarantee max completion time
- 4) modify locks and other sync mechanisms to allow higher priority tasks to preempt lower prioirty tasks
- 5) choose an implementation of dynamic memory that guarantees a maximum completion time
- Threads
- Intro
- for a process, OS creates a new address space including the text segment, static segment, and heap
- also creates a new “thread of execution” which includes the program counter and other hardware state and run-time stack
- within a single process, threads share the same text segment, but different threads can run different parts of the code
- share the same static segment so threads can see changes to global variables
- threads have own stack and usually can’t access each other’s local variables
- Creating threads
- most popular threading standard used with C is POSIX Threads or Pthreads
- Joining threads
- when one thread wants to wait for another, it invokes pthread_join
- Synchronization errors
- threads can access the variable at different times resulting in threads having inconsistent versions
- can use mutex (mutual exclusion object) to lock while one thread accesses
- Condition variables
- The work queue
- threads can communicate with queues
- producers put data in and consumers pull data out
- queue should be threadsafe
- need to handle empty, full cases
- Condition variables
- may want certain things to block e.g. can’t push if full or can’t pop if empty
- Semaphores in C
- POSIX Semaphores
- data structure used to help threads work together without interfering with each other
Like this:
Like Loading...
ycnotes.com 