cs 230

in vm, are pages not in physical memory considered unallocated

no, allocated pages can be stored on disk as uncached pages

virtual memory organization

N contiguous bytes (virtual memory page size)

physical memory page size

P contiguous bytes (physical memory page size)

what do modern general purpose computers use to access data in memory

they use virtual addressing, mmu helps translate between physical and virtual addresses

virtual memory definition

interaction of hardware exceptions, hardware address translation, main memory, disk files, and kernel

virtual memory capabilities

• uses main memory as a cache

• provides large uniform address space

• protects process address space

what happens when a page fault occurs

OS kernel executes page swapping or page allocation

what does page table entry consist of

valid bit and n-bit address field

what does a page table map

it maps virtual addresses to physical addresses

if a page table maps to physical addresses, where may these physical addresses be

• main memory

• in the disk

what does valid bit in a PTE indicate

that the virtual page is RAM (physical memory)

VM operations when there is a “hit” in physical memory

• processor generates VA and sends to MMU

• MMU generates PTE address and requests it from the cache/main memory

• cache/main memory returns PTE to the MMU

• MMU constructs the PA and sends it to cache/main memory

• cache/main memory returns the requested data to the processor

VM operations when there is a “miss” in physical memory

• processor generates VA and sends to MMU

• MMU generates the PTE address and requests it from cache/main memory

• cache/main memory returns the PTE to the MMU

• valid bit is 0, triggers exception, CPU transfers control to fault handler

• fault handler pages in new page and updates PTE in memory

• Fault handler returns to process and restarts offending instruction

interrupt

signal from i/o device, returns to next instruction

(recoverable)

trap

system call, returns to next instruction (recoverable)

fault

page fault, re-executes current instruction
(potentially recoverable)

abort

divide by 0, (non-recoverable)

hardware level

signal from i/o device

operating system

context switch between processes

user

processes can send signals to other processes (ctrl-z from command line)

system call to return process ID of the parent process of the process executing the call

getppid()

what is status code passes to exit system call anded with octal value 0377

to support 16 bit systems

process

combination of machine state and memory state managed by the OS in an internal data structure

what state is a process in if it’s currently waiting to be executed on the CPU

running state

what happens to the relationships when processes are created and terminated

the OS maintains relationship between parent and child in a tree data structure

if a “fork” system call is successful what happens

called once returns twice

how many times must wait() system call be used to reap x children

it must be called x times

how many zombie child processes can P have if there is one running child process when P is terminated

N-1

if a execve system call is successful what happens

it’s called once and it never returns

what system calls are most important to write a shell like bash

fork and execve

what should a process do to block an incoming signal

set the corresponding signal bit in the signal mask associated with the process

0 means

read end

1 means

write end

what happens if a pipe is full and the process wants to write more data

the pipe blocks the write until more space opens up in the buffer

what happens if we don’t close the read file descriptor of the writing process

the writing process will never receive SIGPIPE signal even though the reading process has terminated

IPC

inter-process communication

if a process makes an illegal memory reference what does the operating system send

a sigsegv signal

what should child 1 and child 2 do if child 1 wants to send messages to child 2 using a pipe

child 1 should close its read file descriptor, and child 2 should close its write file descriptor

pending signal set/vector bit

tells you if signal have occurred at least once
* does not tell you how many times a signal has occurred

what happens if you read from a pipe or FIFO file without any processes writing to them

read returns end of file

process properties

• represents an entire program

• high overhead

• coarse-grained parallelism

high overhead

occurs if creating and destroying processes, context switching, synchronizing, and communication costs are very high

coarse grained parallelism

each parallel task does a lot of independent work before communicating to other processes

thread properties

• allocated within a process

• sequence of instructions

• lower overhead

• represent small chunks of code (like functions)

• fine grained parallelism

allocated within a process

threads are created within an existing process, thread cannot exist without a process

fine grained parallelism

• each parallel task does a small amount of work before synchronization

• smaller tasks with more coordination between threads

what is void *arg used for

passed as an argument to thread function start

how are threads and processes different

differ in sharing code and data/memory

processes: when fork is used, even though address space is copied, after that those properties become individual for both parent and child, so if there is a change to a global var by the parent, that doesn’t affect the child

threads read/write from the same memory address as long the threads exist

what happens after a thread calls pthread_create?

it resumes execution with the next statement after the call to pthread_create

what should a thread use to reap itself using pthread_detach

should call pthread_detach with its own thread ID retrieved by pthread_self()

if a thread exits what happens

it becomes a zombie thread until a peer thread calls pthread_join()

global variable

memory contains exactly one instance of these declared outside of a function

local variable

each thread stack has one instance of each local variable, for each time the function is being executed by that thread

local static variable

memory contains exactly one instance of these that are declared inside of a function

race condition

two or more threads access shared data and try changing it at the same time, don’t know which order the threads will attempt to access the shared data

sem_wait

decrements counter by 1, if ctr is already 0 then thread sleeps until another thread calls sem_post

sem_post

increment counter by 1, returns immediately

semaphore

synchronizes thread operations on share data to prevent race conditions

mutex

binary value used to ensure exclusive access to share data

execution status

tuple of the current instructions of each thread in a process

critical section

section of code w/ race condition

unsafe region

region in progress graph where 2+ states within are inside a critical section

progress graph

execution state space

trajectory

series of valid execution state transitions

what method is used to terminate a thread

pthread_exit()

internet protocol stack (top to bottom) w/ FTP, WIFI, IP, TCP

FTP → TCP → IP → WIFI

Domain Name System properties

• distributed database implemented in a hierarchy of many name servers

• takes a domain name, produces an IP address

• takes an IP address and produces a domain name

• value of struct hostent has IP address and hostname

IPv4 address

127.0.0.1

port 80

web server

port 21

FTP server

port 22

SSH

well-known ports

ports 0 through 1023

order of function calls for TCP/IP server listening for connections

socket(), bind(), listen(), accept(), send/recieve/read/write(), close()

order of function calls for TCP/IP client listening for connections

socket(), connect(), send/recieve/read/write(), close()

role of server vs role of client in establishing TCP connection

passive vs active

TCP vs UDP

TCP: provides reliable transport between sending/receiving process (like a conversation), used for client server model

UDP: provides faster data transfer but no retransmission, used for streaming servers/fast paced games

internet definition (nuts and bolts)

• collection of billions of computing devices, and packet switches interconnected by links

• a network of networks

protocol

the client server model, a conversation

application layer

supporting network applications

transport layer

transfer of data between one process and another process (usually on diff hosts)

network layer

delivery of datagrams from a source host to a dest host

link layer

transfer of data between neighboring network devices

physical layer

transfer of a bit into and out of a transmission media

encapsulation

taking data from layer above, adding header fields appropriate to layer, placing data in payload field of packet for that layer

protocol stack with HTTP, IP, Ethernet, TCP (top to bottom)

HTTP → TCP → IP → Ethernet

accept()

• blocking call that creates new socket with same type, address family, protocol as specified socket

• allocates a new file descriptor for created socket

• prevents caller from doing anything until blocking function returns control to it

size of IPv4 address

32 bits

sisze of IPv6 address

128 bits

SOCK_STREAM

reliable, 2-way, connection based, TCP

SOCK_DGRAM

unreliable, connectionless, UDP

fixed machines

used for specific purpose, cannot be reprogrammed for a different task just by programming, need re-design and re-wiring

general purpose machines

can change tasks with programmability, programs are stored in memory

ISA

Instruction set architecture, instruction API to a machine

instruction register

stores current instruction

instruction counter

stores address of next instruction, incremented automatically by machine

status register

stores info about result of last operation

signal generator

communicates w/ rest of the processor

decoder

reads the instruction and determines what signals to generate

execution unit

processor core

arithmetic logic unit (ALU)

performs calculations