COMP3361 Operating Systems I Mid-­term Review and Study Guide Basic Concepts:
What is an operating system?
A program that acts as an intermediary between a user of a computer and the computer hardware - basic functions?
1.) OS is a resource allocator
2.) manages all resources
3.) decides between conflicting requests for efficient and fair resource use
4.) OS is a control program
5.) controls execution of programs to prevent errors and improper use of the computer
6.) a program running at all times on the computer, usually called the kernel
7.)everything else is either a
a.) system program: associated with the OS but not part of the kernel
b.) application program: not associated with the OS

user/kernel modes of operation?
1.) The operating system must ensure correct operation of the computer system. To prevent user programs from interfering with the proper operation of the system, the hardware has two modes: user mode and kernel mode. Various instructions (such as I/0 instructions and halt instructions) are privileged and can be executed only in kernel mode.
2.) Kernel Mode
In Kernel mode, the executing code has complete and unrestricted access to the underlying hardware. It can execute any CPU instruction and reference any memory address. Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system. Crashes in kernel mode are catastrophic; they will halt the entire PC. 3.) User Mode
In User mode, the executing code has no ability to directly access hardware or reference memory. Code running in user mode must delegate to system APIs to access hardware or memory. Due to the protection afforded by this sort of isolation, crashes in user mode are always recoverable. Most of the code running on your computer will execute in user mode.

-services it provides?
1.) CPU moves data from/to main memory to/from local buffers
2.) I/O is from the device to local buffer of controller
3.) Helpful to user a. Error detection, accounting , resource allocation, user interface, program execution, file system manipulation, protection and security

Q.) When you execute a system call mode changes from user mode to kernel mode, know the difference

Interrupts 1.) An interrupt transfers control to the interrupt service routine through the interrupt vector table, which contains the addresses of all the service routines 2.) Interrupt architecture must save the address of the interrupted instruction 3.) Incoming interrupts are disabled while another interrupt is being processed to prevent a lost interrupt 4.) An operating system is interrupt driven 5.) What happens? a. The OS preserves the state of the CPU by storing registers and the program counter b. The interrupt service routine is executed c. On completion, the CPU resumes the interrupted computation
Multiprogramming
1.) The objective of multiprogramming is to have some process rum1ing at all times, to maximize CPU utilization. 2.) One job is selected and run via job scheduling 3.) When it has to wait (e.g. for I/O), OS switches to another job
Multitasking-time quantum 1.) Timesharing (multitasking) is a logical extension of multiprogramming 2.) CPU switches jobs so frequently that users can interact with each job while it is running 3.) Response time should be < 1 second 4.) Each user has at least one program executing in memory 5.) If several jobs are ready to run at the same time, you need CPU scheduling 6.) If processes don’t fit in memory, swapping moves them in and out to run 7.) Virtual memory allows execution of processes not completely residing in memory
Multiprocessor-
1.) increased throughput 2.) economy of scale 3.) increased reliability – graceful degradation or fault tolerant 4.) Two Types: a. asymmetric multiprocessing -This asymmetric multiprocessing is simple because only one processor accesses the system data structures, reducing the need for data sharing. b. symmetric multiprocessing-where each processor is self-scheduling. All processes may be in a common ready queue, or each processor may have its own private queue of ready processes

What is a system call?
1.) System calls provide the means for a user program to ask the operating system to perform tasks reserved for the operating system on the user programs behalf;
2.) How are parameters passed during a system call.
a. simplest: pass the parameters in registers may have more parameters than registers (not good if you have a chunk of code)
b. parameters stored in a block, or table, in memory, and address of block passed as a parameter in a register .approach taken by Linux and Solaris
c. parameters placed, or pushed, onto the stack by the program and popped off the stack by the operating system
3.) Block and stack methods do not limit the number or length of parameters being passed

Structure of an OS: 1.) Simple:Most functionality, least space a. interfaces and levels of functionality are not well separated b. application programs can directly write to the display or disk drives 2.) Layered: only uses services provided by inside layer c. The operating system is divided into a number of layers (levels), each built on top of lower layers d. The bottom layer (layer 0) is the hardware; the highest (layer N) is the user interface e. With modularity, layers are selected such that each uses functions (operations) and services of only lower-level layers f. Tends to be less efficient, difficult to distinguish layers 3.) Modular: launch modules only when you need them similarities and differences g. each core component is separate h. each talks to the others over known interfaces i. each is loadable as needed within the kernel j. Similar to layers, but more flexible

 Protection – any mechanism for controlling access of processes or users to resources defined by the OS
 Security – defense of the system against internal and external attacks

Processes and Threads:
What is a process, 1.) A process is a program in execution, MORE DATA associated with it then a program a. Processes are either i. I/O bound: spends more time doing I/O than computations ii. CPU bound: spends more time doing computations; generates I/O requests infrequently 2.) A process also includes b. a program counter c. a stack d. a data section e. often a heap
States of a process and their transitions N R W R T-Never Run While Reading Television 1.) A process changes state as it executes a. new: the process is being created b. running: instructions are being executed c. waiting: the process is waiting for some event to occur d. ready: the process is waiting to be assigned to a processor e. terminated: the process has finished execution 2.) One running per CPU; many ready and waiting 1.) comes in-> ready, 2.) assigned to processor->running state, 3.) i/o->waiting state (has to be running to go to waiting)

Process control block and context switch -??? 1.) The operating systems maintains all information related to a process in a data structure called the Process Control Block 2.) Context Switch-time dependent on hardware, pure overhead a. state save: save the context of the currently running process b. state restore: load the context of the new process
Process scheduling queues; 1.) Job queue: set of all processes in the system , processes on disk 2.) Ready queue: set of all processes residing in memory, ready and waiting to be executed , set of programs that can run, only a part is taken into memory 3.) Device queue: set of processes waiting for an I/O device
SCHEDULERS
1.) Long-term scheduler: selects which processes should be brought into the ready queue (bring in a mix of i/o bound and cpu bound) a. Controls the degree of multiprogramming, takes longer 2.) Short-term scheduler: picks from ready queue, allocates processor b. Invoked very frequently!! 3.) Mid-term scheduler: processes can be sent back to the job queue, (oops we brought in a ton of cpu bound proccesses, send some of these back, bring in some others

scheduler
--‐
understand which type operates on which queue
fork() and wait(); 1.) return values, 2.) resource sharing between parent and child processes
Interprocess communication: 1.) shared memory model vs message passing model(what is the difference between the two and why is one better/worse than the other); (data is sent to kernel, set buffers to MAILBOXES, buffer maintained by kernel 2.) shared memory: a region of memory is shared by the cooperating processes 3.)  message passing: messages are exchanged between the cooperating processes

Pipes 1.) ordinary :have a buffer a. Ordinary pipes allow communication in standard producer-consumer style (with buffer) b.  Producer writes to one end the write-end or 1-end of the pipe c.  Consumer reads from the other end the read-end or 0-end of the pipe d.  Uni-directional e.  Requires parent-child relationship between communicating processes 2.) named pipes- f. filesystem persistant, -they persist even if the program that created it was terminated g. No parent-child process needed

pipe, send to kernel, can send to another machine on network

Threads vs. processes
User--‐level: User-level threads: threads created by you using some threading API (e.g. by using NPTL) 3.) kernel--‐level threads; threads created by the kernel to provide services (e.g. system call handling) to applications h. the OS schedules these threads just like processes 4.) what is the meaning of mapping one to the other; various mapping models

CPU
Scheduling:
Preemptive: process kicked out of CPU
Non--‐preemptive: if a process gives up the processor on its own scheduling
Schedulers:
1.) FCFS 2.) SJF: garuntees minimum average wait time 3.) Shortest Remaining Time: 4.) Priority 5.) First, 6.) RR=increase time quantum to infinity, we have FCFC 7.)

Estimating burst time: Method of “exponential averaging”, further out the prediction is, put let weight on that (recent burst has more weight)

Scheduling criteria, how are they affected by different schedulers 1.) CPU utilization a. percentage of real time where CPU was serving a process 2.) Throughput b. number of processes that are completed per unit time 3.) Turnaround time c. amount of time to finish a process 4.) Waiting time d. total time spent by a process in the ready queue 5.) Response time e. time from process submission until the first response is produced

How do you compute CPU utilization? -add time in for context switches, find ratio (look for pattern)

Multilevel and multiprocessor scheduling -multilevel: put processes in multiple queues, each queue has own policy, then there is a policy to choose queue, promotion or demotion, may move between queues -multiprocessor, may want to stay at one processor so the cache is always valid -hard affinity, soft affinity

Process Synchronization:
Race condition and critical section; solution requirements 1.) Race condition :several processes access and manipulate the same data concurrently 2.) outcome of the execution depends on the particular order of access 3.) Solution Requirements: a. Mutual exclusion: if process Pi is executing in its critical section, then no other process can be executing in its critical section b. Progress : the decision about which process will enter its critical section next cannot be postponed indefinitely, and current processes in their remainder sections cannot participate c. Bounded wait: there should be a limit on how many other processes will first gain access

Peterson’s solution: 1.) assumption in the solution 2.) load&store have to be atomic (cannot be interrupted)
Synchronization using 1.) Test&Set :what they do, how they are satisfying the requirements a. Sets to true and returns original value b. NO BOUNDED WAIT, mutual exclusion, yes SWAP :what they do, how they are satisfying the requirements

Semaphores: binary and counting, what does wait()-busywait, (<=0)
-w/o busywait associate a queue with the semaphore, decrement if(<0) block the process signal()-busywait(i++) --w/o busywait increment and unblock
1.) A simple way to understand wait() and signal() operations is: * wait(): Decrements the value of semaphore variable by 1. If the value becomes negative, the process executing wait() is blocked, i.e., added to the semaphore's queue. * signal(): Increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

Solve classical synchronization problems
What is a monitor, condition variables 1.) Monitor: A monitor type is an ADT which presents a set of programmer-defined operations that are provided mutual exclusion within the monitor. The monitor type also contains the declaration of variables whose values define the state of an instance of that type, along with the bodies procedures or functions that operate on those variables. 2.) Condition Variable: A condition variable provides a method by which a procedure can block its execution until it is signaled to continue. The only operations that can be invoked on a condition variable are wait () and signal(). The operation
x. wait(); means that the process invoking this operation is suspended until another process invokes
x. signal();
The x. signal() operation resumes exactly one suspended process. If no process is suspended, then the signal() operation has no effect; that is, the state of x is the same as if the operation had never been executed

Deadlocks:
What is a deadlock, what conditions are required for a deadlock to occur? 1.) Mutual Exclusion 2.) Hold And Wait 3.) Non-preemption 4.) Cycles

Resource--‐allocation graphs, when is a cycle a deadlock? -When we are dealing with single instances
Deadlock prevention: how are each of the deadlock conditions handled? 1.) Mutual Exclusion- to prevent this, we share resources 2.) Hold & Wait- to prevent this, we require a process to release its resources before gaining new ones. Must guarantee that whenever a process requests a resource, it does not hold any other resources 3.) Non-premption: if a process requests a resource that cannot be immediately given to it, it must give up all of its resources and not start until they (and the ones requested) are returned. 4.) Circular Wait: – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
Deadlock avoidance: safe/unsafe state, detecting them in the presence of single/multi instance resource types
--‐ Banker’s algorithm: data structures, finding out if a state is safe, determining if a request should be granted
Detection with single/multiple instance resource types
--‐ using wait--‐for graphs
--‐ using the detection algorithm