Final practice exam Flashcards
What does the comma operator do?
- sequences two expressions
- value is the result of the righthand expression
- treated as a single expression by the compiler
What are enumerated types?
-syntax: enum tag { values } vars ;
-each ‘value’ is an identifier - use them in expressions
-internally, represented as integers
- by default, first ‘value’ represented as 0
- subsequent ‘values’ have previous - entry’s representation + 1
- can override: name = integer
- sequence defines an ordering relationship between the ‘values’
What are qualifiers?
- optimization hints to the compiler
What are the forms of qualifiers?
register: keep this variable in a register if possible
volatile: variable’s contents may change between compiled statements
restrict: guarantee that *ptr is the only reference to something in this scope
What is the syntax for a macro with a parameter?
define name(params) value
What is a macro with a parameter?
each occurrence of a formal parameter in value is replaced by its actual parameter during macro expansion
What are the special uses of parameters
param: replaced by a string literal containing the actual parameter
##: creates a symbol during expansion
what is #error text?
generates a compilation error whose message includes text
What is #pragma text?
- invokes a compiler-specific action
- syntax and meaning of text are implementation-dependent
- inherently non-portable!
What are some optimization tools?
- profilers (e.g., gprof): analyze program behavior, determine number of calls to each function and total time spent in each function
- code coverage (e.g., gcov): determine whether or not all code in a program can be reached
What is none as inefficient code?
- excess code inside loop bodies (“loop invariants”)
- unnecessary computation
- common subexpressions
What is the big O notation for the search of unordered list?
O(n)
What is the big O notation for the search of a ordered list?
O(n/2)
What is the big O notation for a binary search tree?
O(logn)
What is the big O notation for a hash table?
O(1)
What is inefficient memory accessing?
primarily on large data sets in memory
What are things that affect performance?
- efficiency of code produced by the compiler
- efficiency of algorithms
- redundant/unnecessary/useless code
- data layout and access
How to measure of some aspect of program behavior
- CPU time used, “user” time, i/o operations, etc.
- what matters depends on your point of view
What are the attributes in protection?
- things in the file system have these
- ownership (UID, GID)
- permission bits (read, write, execute)
- interpretation of permissions for files vs. directories
What is ownership in protection?
- user id (UID), group id (GID)
- each process has both IDs
- OS uses these IDs to determine access rights
How does altering ownership and accessing right in protection work?
- “set” bits (set uid, set gid, sticky bit)
- allow users to run programs with different UIDs/GIDs
- ID variations:
-real UID/GID: who is actually running the program
-effective UID/GID: determine access rights to files (etc.)
-saved UID/GID: “backup” of real UID/GID
What is protection?
- OS as a collection of objects
- characteristics of objects
- Principle of Least Privilege
What are the concepts of security?
- threats, attacks, intruders
- goals: confidentiality, integrity, availability
What is philosophy in security?
concept that protection is neccessary
What is policy in security?
A set of rules (who can use what)
What is mechanism in security?
How policy is enforced.
What are naive flaws?
Buffer overflow
What are examples of program flaws that are major sources of errors?
Apple SSL coding flaw
auth_overflow3 attack example
Morris Worm (1988)
other variations (trojan horses, time bombs, trapdoors)
What are pipes?
Connection between two file descriptors.
What does this do and mean? int pipe(int fd[2])
allocates two file descriptors.
data written into fd[1] can be read from fd[0]
How can file descriptors be moved to other file descriptor numbers?
Typically stdin and stdout.
int dup( fd );
int dup2( oldfd, newfd );
What are the concepts of OS: Scheduling?
- goal: ensure that CPU time is used productively
- scheduling: determining the order of execution of processes
- dispatching: actually giving the CPU to a process
What is the process behavior of OS: Scheduling?
- process state transitions
- bursts - cpu vs. i/o
- typical distribution of burst length
What are the process queues of scheduling?
OS uses queues to keep track of all processes
- ready queue: all processes which are able to execute
- device queues: processes which are blocked waiting for i/o
- sleep queue: processes which are blocked waiting for time to pass
etc.
What does a context switch in scheduling do?
- save CPU contents (process context) for currently-executing process
- select a new “current” process
- restore context for the “current” process
What are the categories of schedulers?
Non-preemptive, voluntary yield, preemptive
What do non-preemptive schedulers do?
- behavior: never take the CPU away from a process
- examples: FIFO, Shortest Job First
- “run to completion” - once dispatched, job goes until it finishes
- acceptable for batch processing, not really usable for interactive computing
What do voluntary yield schedulers do?
- behavior: no preemption
- processes can “give up” the CPU to allow others to run
What do preemptive schedulers do?
- behavior: can “preempt” a process and give CPU to another process
- examples: Round Robin, Multilevel Queue, Multilevel Feedback Queue
- each process executes for a short time, then is preempted
- over time, all processes get to execute and make progress
What is quantum in scheduling?
- a.k.a. “time slice”
- length of time a process is allowed to execute before being preempted
- critical to preemptive scheduling
What are variations in scheduling?
Priorities and quantum length
What are the priorities in variations?
- indicate relative “importance” of processes
- origin: internal (calculated by OS), external (requested by user)
- duration: static (assigned when process arrives), dynamic (can change during process lifetime)
What is quantum length in scheduling?
- determined by OS/scheduler
- can be identical for all processes, or different based on process type
- duration: static (assigned when process arrives), dynamic (can change during process lifetime)
What are the concepts in processes?
- states
new, ready, running, blocked, terminated, zombie, etc. - attributes (owner, PID, GID, etc.)
- management by the OS
- address spaces
What are address spaces in processes?
They are virtual and physical spaces.
Parts of process address space.
- text,data,bss,heap,stack
How to create a process?
pid_t fork( void ); system call
returns -1 on error
on success, now have two instances of the process
return value in child (new process): 0
return value in parent (original process): PID of the child
child inherits open i/o connections from parent
allows intermixing of i/o from both processes
can get unexpected results (e.g., stdio buffering example)
How do you terminate a process?
terminating process produces an exit status
status must be collected by the parent
pid_t wait( int *status );
pid_t waitpid( pid_t pid, int *status, int options);
if parent doesn’t collect the status
terminated process becomes a zombie
stays in the system, occupying a process table slot
if parent has already exited, child is “re-parented” to the init process (typ., PID 1)
need for _exit() syscall (vs. exit())
How do you execute other programs using processes?
- exec family of system calls
- replace the memory image of the process with a different program
- many variants - most common two:
- int execv( const char *path, char * const argv[] );
- int execvp( const char *name, char * const argv[] );
What is a thread?
A lightweight process. Provides the ability to perform concurrent operations within a single process context.
What are the concepts of threads?
- Threads execute inside a process context
- all thread share code, global data areas, system resources (e.g., open files)
- each thread has its own stack, CPU context (register contents), may have private data areas
What are the potential issues of threads?
- shared global data may lead to race conditions
- result can be inaccurate/incomplete computation
- concept: thread-safe code
What are POSIX threads?
- standardized thread model, usable on many (most?) systems
- each thread identified by a pthread_t (thread ID)
What does it mean when a thread is joinable?
-At termination, they stay in system until joined by another thread
- Threads can be detached aka non-joinable.
What does it mean if a threads are in a cancellability state?
cancellation === termination
by default: enabled-thread can be cancelled by another thread
detached threads cant be cancelled
What are the POSIX thread functions?
int pthread_create( pthread_t *id, const pthread_attr_t *attributes,
void (start_routine)(void *), void *arg );
void pthread_exit( void *retval );
int pthread_join( pthread_t id, void **retval );
int pthread_detach( pthread_t id );
int pthread_cancel( pthread_t id );
What are the primary problems between threads?
- critical resource: shared resource (e.g., variable)
- critical section (C.S.): section of code using a critical resource
- don’t want two or more threads in C.S. on same resource at the same time
- interleaved execution can result in incorrect update/use of the shared resource
- example: shared account balance, debit and credit threads
- want operations on shared resources to be atomic (indivisible)
- need a “locking” mechanism
What are mutexes?
- “locking” mechanism
- provide mutual exclusion (mutex)
What is the usage of mutexes?
- thread attempts to lock the mutex before entering C.S. (entry guard)
- after obtaining lock, thread executes C.S.
- upon leaving C.S., thread unlocks the mutex (exit guard)
What happens if two or more threads attempt to lock mutex simultaneously?
- one thread “gets” the lock, the others are suspended
- “winning” thread enters its C.S.
- when this thread leaves its C.S., it unlocks the mutex
- one of the suspended threads is awakened, the mutex is re-locked, and the awakened thread now enters its C.S.
What are the mutex functions?
- int pthread_mutex_init( pthread_mutex_t *mutex,
const pthread_mutexattr_t *attributes ); - int pthread_mutex_lock( pthread_mutex_t *mutex );
- int pthread_mutex_unlock( pthread_mutex_t *mutex );
Static global variables are stored in the _____ memory segment
DATA
Static local variables are stored in _____ memory segment.
DATA
Stack frames are stored in the _______ memory segment.
STACK
Dynamic memory uses the ______ memory segment. If the code loses the _______ that holds its heap address, then there will be a memory leak.
HEAP, POINTER
Memory allocated by calloc is stored in the _____ memory segment.
HEAP
The instructions of the compiled code are stored in the _____ memory segment.
TEXT
The C language is said to pass arrays by _______ because you can change the array’s contents, but it is really pass by _____.
REFERENCE, VALUE
________ is used to increase efficiency while doing IO operations by reducing the number of read and write operations.
BUFFERING
A _____ region is a section of code that multiple threads should not access at the same time.
CRITICAL
A ______ is used to stop multiple threads from accessing the same section of code at the same time
MUTEX
What do you write to use a particular C standard to control compilation?
-std
What do you write to turn on all optional warnings?
-Wall
What do you write to compile or assemble source files, but not link?
-c
What do you write to place linking output in a specifically-names executable file?
-o
What do you write to compile with additional information for debugging?
-ggdb
What does “The language C provides no support for the data type “string” “ mean?
String in C is represented as an array of characters with a terminating NULL character ‘\0’
What are the following steps of the program translation?
Preprocessing, Compilation, Assembling, Linking, Loading
In which step does lexical and syntax analysis occur?
Compilation
(T or F) The preprocessor checks the syntax of the C source code.
FALSE, Compiler
Write a preprocessor macro to determine if a signed integer is negative.
define NEGATIVE (x) if(x<0)
What is a fork?
Is a system call that is used for process creation. When a program calls fork(), the operating system creates a new process that is a copy of the calling (parent) process. The newly created process is referred to as the child process, and the original process is referred to as the parent process.
How many processes does the following code create?
for(int i = 0; i < 5; i++){
fork();
}
- Because a fork creates copies. So think 2^n.
Given the following struct (assume struct prof has already been defined):
Struct course{
int num_students;
char * name;
short building_num;
struct prof * professor;
short room_num;
}
a. What is the result of sizeof(struct course)?
b. Rewrite struct course to minimize the space it requires. What is its new size?
a) 40.
b) Struct
Char *
Int
Short
Short
24
