CSCE3600 - Final Flashcards
groups sequences of tokens from from the lexical analysis phase into phrases
syntax analyzer or parser
obtain tokens from lexical analyzer
syntax analyzer or parser
determine the statement class
syntax analyzer or parser
group tokens into statements
syntax analyzer or parser
construct hierarchical structures called parse trees
syntax analyzer or parser
takes input from the syntax analysis phase
semantic analysis
takes input in form of parse tree and symbol table
semantic analysis
determine if input has a well defined meaning
semantic analysis
concerned with type checking and type coercion based on type rules
semantic analysis
scans code from left-to-right, character-by-character, and groups into lexemes
lexical analyzer or scanner
outputs a sequence of tokens to the syntax analyzer
lexical analyzer or scanner
works in a uniprocessor environment only
interrupt
generates a piece of data, put it into the buffer and start again
producer
consuming the data (remove from buffer) one piece at a time
consumer
try not to add data into the buffer if it’s full
producer problem
try not to remove data from empty buffer
consumer problem
int flag[2] = {FALSE, FALSE};
int turn = 0;
flag[i] = true;
turn = 1 - i;
while (flag[1 - i] && turn == 1 - i;
CSi;
flag[i] = FALSE;peterson’s algorithm
cannot affect or be affected by the execution of another process
independent process
can affect or be affected by other processes executing in the system
cooperating process
each process waiting for a message from the other process
deadlock
two processes sending messages to each other while another process waits for a message
starvation
what does atomic operation mean
non-interruptible
three solutions to the critical-section problem
mutual exclusion, progress, and bounded waiting
also called mutex locks
binary semaphores
more restrictive version of semaphores that may take on a value of 0 or 1
binary semaphore
used to write to a memory location and return its old value as a single atomic operation
test-and-set()
only process that may enter critical section is one that finds shared variable set to 0; when done, resets shared variable to 0
test-and-set()
refers to mutual exchanging of values of the variables
swap()
exchanges contents of register with that of memory location
swap()
when two or more processes try to use the same resource at the same time
race condition
race conditions need
concurrency, shared object, change state
a lock that causes a process/thread trying to acquire it to simply wait in a loop while repeatedly checking if the lock is available
spinlock
where shared data is accessed
critical section
ensure that when one process is executing in its critical section, no other process is allowed to execute
critical section problem
if a page’s reference bit is set to 1
set its reference bit to zero and skip it
if a pages reference bit is set to 0
select this page for replacement
second chance clock algorithm always starts the search ___
from where the last search left off
ordered list of pages accessed as process executes
reference string
if page size is 100 what are the reference string of:
123, 215, 600, 1234, 76, 96
1, 2, 6, 12, 0, 0
holds virtual address to physical address
page table
memory is partitioned into chunks called
pages
the oldest page in physical memory is the one selected for replacement
First-in First-out
replace the page that will not be referenced for the longest time
belady’s min
replace the page in memory that has not been accessed for the longest time
least recently used
does not consider page usage
first-in first-out
page that has been written to
dirty page
before a dirty page can be replaced it must
be written to disk
effective access time formula
( 1 - p ) * ( memory access time ) + p * ( page fault overhead )
components that make up page fault overhead
fault service time, read page time, restart process time
total memory space exists to satisfy a request, but it is not contiguous
external fragmentation
allocated memory may be slightly larger than requested memory
internal fragmentation
reduce external fragmentation
compaction
shuffle memory contents to place all free memory together in one large block
compaction
each whole list; choose block that comes closest to matching the needs of allocation
best fit
scan the list for the first block that comes closes to matching the needs of allocation
first fit
choose block that worst matches the request
worst fit
scan the list for first block that comes closest to matching the needs of allocation
next fit
