Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
155 Cards in this Set
- Front
- Back
- 3rd side (hint)
What is an Operating System? |
An operating system (OS) is software,consisting of programs and data, that runs on computers and manages computer hardware |
|
|
What resources the OS manages? |
Central Processing Unit (CPU) |
|
|
What are the objectives when the OS manages the computer system resources? |
Efficiency and Fairness |
|
|
OS provides a set of common services which are |
System calls (interface to programmer) |
|
|
abstraction layer |
provides a universal interface to the hardware |
|
|
Kernel
|
resource management
Processor, Memory, and I/O |
|
|
Moore’s Law |
# of transistors on a |
|
|
Charles Babbage
|
Difference Engine |
|
|
Exception |
An unscheduled event that disrupts program |
|
|
Interrupt |
An unscheduled event that disrupts program |
|
|
Process |
an instance of a program executing on a
CPU § Different from a program |
|
|
Process Management 5
|
Creating and deleting processes
Suspending and resuming processes Providing mechanisms for communication Providing mechanisms for synchronization scheduling processes |
|
|
5 Parts of a Computer System |
Processor(1: Control Path,2: Data Path) |
|
|
Who created the first electronic computer (around WWII) that had a general purpose and was operational? |
John Presper Eckert/John Mauchly (UPenn) |
|
|
First electronic general purpose computer Used by the military to compute artillery firing tables & which data entered on punch cards |
ENIAC (Electronic Numerical Integrator and Calculator) |
|
|
Who developed the the idea of storing the program in memory along with the data (Stored program concept)? |
John von Neumann |
|
|
Functionality of a batch monitor |
Load program, run, print results |
|
|
Name of the first real commercial computer, 48 were built & that correctly predicted the outcome of the 1952 presidential election
|
UNIVAC (Universal Automatic Computer) [Remington-Rand] |
|
|
Which company and in what year implemented the use of the microprocessor (computer on a single IC)? |
Two companies: § Intel Corporation (est. 1968) |
|
|
Which computers were the first ones to be called microcomputers (since they used microprocessors)? |
Altair 8800 (1975) Apple I (1976) |
|
|
First personal computers that had: - GUI - LAN |
Xerox Alto in 1973 (non-commercial) Apple II in 1977 |
|
|
First packet switching network funded
|
ARPANET (later became the Internet)
|
|
|
Which university became the first node in 1969 |
UCLA |
|
|
Cloud computing |
Most of the processing is done on a compute server in the network somewhere Most of the storage is on a file server in the network somewhere |
|
|
Why allow cooperating processes/threads?
|
§ Speedup – overlap I/O and Computation, take |
|
|
Why are cooperating processes important? |
Need to ensure correct operation with concurrent processes/threads |
|
|
why can Cooperating processes affect each other’s execution? |
They share a logical address space or share data through files and messages |
|
|
Why can Concurrent access to shared data result in intermittent incorrect behavior? |
Because the outcome may be affected by concurrency or interleaving of the execution
|
|
|
Independent processes |
Scheduling order does not affect operation |
|
|
Cooperating processes/threads |
Shared state between threads, scheduling order can affect operation without proper synchronization among processes/threads |
|
|
Race Condition
|
When several processes access and manipulate the same data concurrently and the outcome of the execution depends on the order in which the access takes place |
|
|
What should happen to ensure correct operation in certain code sequences? |
They should be uninterruptable and/or should |
|
|
Why are race conditions bad?
|
Race conditions lead to non–deterministic behavior
|
|
|
How can race conditions be avoided?
|
Ensure that only one of process
can manipulate shared data at a time |
|
|
Mutual Exclusion |
Ensuring that only one thread does a particular thing at a time |
|
|
Critical Section |
Piece of code that only one thread can execute at once. Only one thread at a time will get into this section of code. |
|
|
What requirements should be satisfied by a solution to the critical section problem? |
Mutual Exclusion |
|
|
Bounded waiting (avoid starvation) |
There must exist a bound on the number of times other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before it is allowed to |
|
|
Peterson’s Algorithm |
Use a turn variable to signal whose turn it is to enter the critical section as well as a flag per process that indicates whether a process wants to enter its critical section |
|
|
Locking mechanism to
ensure mutual exclusion |
Disabling Interrupts |
|
|
Problems with disabling interrupts |
§ Does not guarantee mutual exclusion for multiprocessor systems (disabling interrupts across multiprocessors is expensive; message passing) |
|
|
Lock Variables |
Use a variable to lock access to critical section Need hardware support to guarantee an update to a lock variable cannot be interrupted |
|
|
Problems with Lock variables approach
|
•Busy waiting is employed |
|
|
Problems with Busy Waiting |
• Very inefficient because waiting process consumes CPU cycles (depends on time to unlock, if short then busy wait is preferable to waiting with a context switch) |
|
|
§ Priority Inversion for Strict Priority Scheduler |
• If busy–waiting thread has higher priority than |
|
|
Semaphores
|
Integer that is accessed through two atomic operations |
|
|
Problems with semaphores
|
§ A process will busy wait or spin waiting for the semaphore (this type of semaphore is also referred to as a spinlock) |
|
|
Binary semaphore |
only two values (0, 1) |
|
|
Counting semaphore
|
Used when there are a finite number of instances of some resource |
|
|
How can busy waiting be fixed? |
Changing implementation of |
|
|
Process Scheduling
|
Since processes are queued as they wait on a semaphore, method to determine the next process that can be employed |
|
|
Priority Inheritance |
Allow a process to inherit the priority of a higher priority process that is |
|
|
Priority Inversion |
A lower priority process M, is able to affect the |
|
|
Deadlock
|
A set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set |
|
|
What four necessary conditions that must hold simultaneously for a deadlock to occur
|
Mutual Exclusion,Hold and Wait,No Preemption,Circular Wait |
|
|
Mutual Exclusion
|
a resource must be non–sharable and therefore require mutual exclusion |
|
|
Hold and Wait
|
a process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes |
|
|
No Preemption |
resources cannot be preempted |
|
|
Circular Wait
|
a set of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, Pn–1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0 |
|
|
Safe state
|
deadlock impossible (no cycles)
|
|
|
Unsafe state
|
deadlock possible (cycles) |
|
|
Preemption
|
temporarily interrupting a task being carried out by a computer system(interrupt) |
|
|
Bankers Algorithm |
when a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time. |
|
|
How does Interrupt Request Line work? |
§ Sensed after executing every instruction |
|
|
Interrupt that can be disabled |
Maskable Interrupt
|
|
|
Interrupt that cannot be disabled |
Non–Maskable Interrupt (NMI) |
|
|
What does interrupt controller do?
|
Handles prioritizing and disabling interrupts |
|
|
What does the Interrupt ID from the interrupt |
The interrupt handler that is invoked |
|
|
What do multiple interrupt causes? |
It may share a single interrupt ID and corresponding handler |
|
|
When does a process switch occur?
|
• A process voluntarily yields the CPU by waiting for an event |
|
|
Scheduling Algorithm Goals
|
• Maximize CPU Utilization (match ready process with an idle CPU and minimize context switch overhead) |
|
|
What does a process consist of?
|
Alternating State 1: CPU burst & State 2: I/O burst |
|
|
How would the scheduling algorithm will schedule individual CPU bursts of a process?
|
• CPU bursts are the jobs to be scheduled |
|
|
In which case would the process scheduler will not interrupt a CPU burst?
|
In the Non–preemptive case
|
|
|
What the 3 Components of the Scheduling Model? |
α – Machine Environment (Single or Multiple) |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/50/23/9435023_m.png |
|
Minimize the sum of completion times |
Non–preemptive single CPU |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/51/61/9435161_m.png |
|
SPT Preemptive version
|
•Only scheduling processes that are in the ready queue at the same time are considered |
|
|
CPU Burst Length Forecasting
|
The next CPU burst length of a process must be |
|
|
Priority Scheduling
|
• CPU bursts could be scheduled by priority |
|
|
What problem arises when using priority scheduling?
|
Starvation –––>A CPU burst with low priority could be indefinitely postponed by higher priority |
|
|
How can starvation be prevented? (2 ways)
|
• Perform priority scheduling on processes in the ready queue, no newly arriving higher priority process can be scheduled before an already scheduled low priority process |
|
|
Which scheduling can be implemented with a particular time quantum to place an upper bound on response time? |
Round Robin |
|
|
What does the time quantum effects? |
The upper bound on response time and the CPU utilization |
|
|
Small upper bound on response |
Small time quantum |
|
|
large upper bound on response |
Large time quantum |
|
|
How should the time quantum be adjusted? |
Time quantum should be adjusted to the number of processes in the ready queue (to maintain fixed upper bound on response time) |
|
|
Multi–level Feedback Queue |
§ Many real operating systems maintain multi–level queues
§ Each level has its own scheduling policy § Processes can be moved from one queue to another |
|
|
Asymmetric Multiprocessing |
One processor is designated as master and handles all scheduling |
|
|
Symmetric Multiprocessing (SMP)
|
• Each processor schedules itself |
|
|
Processor Affinity |
Processes are scheduled on the processor that they are initially assigned to |
|
|
What is the importance of load balancing? |
To increase utilization of the multiple processors |
|
|
Describe load balancing |
Processes should be moved from highly loaded |
|
|
Distributed Applications |
Applications that communicate and coordinate their actions by exchanging messages |
|
|
Client – Server |
Kind of distributed application in which: § Client starts communication with server |
|
|
Peer–to–peer |
Kind of distributed application in which: •Unstructured |
|
|
Hybrid
|
Kind of distributed application in which: |
|
|
Divide and conquer approach
|
Approach used to deal with the very hostile and complex internet environment (Different transmission mediums, Different devices, Faulty systems (Noise) & Malicious entities) |
|
|
Name the 5 network protocol layers |
Application |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/28/51/9432851_m.png |
|
Physical Layer |
Layer that: • Codifies bits into signals (symbols) |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/29/05/9432905_m.png |
|
Link Layer
|
Layer that handles: |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/29/20/9432920_m.png |
|
Time division multiplexing
|
• A single user is allowed to transmit at a time |
|
|
Frequency division multiplexing |
Each user is allocated part of the available bandwidth |
|
|
Network layer
|
Layer that handles: |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/29/77/9432977_m.png |
|
Transport layer |
Layer that handles: |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/33/31/9433331_m.png |
|
Application Layer |
Layer that handles: |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/33/55/9433355_m.png |
|
Sockets (Port numbers are used to address applications ) |
Abstract entity that represents a connection between two transport layer devices |
|
|
Well known port numbers |
HTTP – 80 Telnet – 23 |
|
|
Berkeley Sockets Interface |
Standard Application Programming Interface (API) for sending messages over a networkGeneric API, not specific to Internet or TCP/IP Implemented by many operating systems |
//fce-study.netdna-ssl.com/2/images/upload-flashcards/43/33/82/9433382_m.png |
|
Stream sockets (TCP) |
TCP/IP socket type that: |
|
|
Datagram sockets (UDP) |
TCP/IP socket type that: § best effort service |
|
|
Given n processes, how many different schedules are possible? |
f(n)= n! |
|
|
Assume i consecutive fork() statements. Express # processes as function of i |
2^i processes |
|
|
Actions taken by kernel to context switch between 2 processes |
1) OS saves state of currently executing process(ie CPU registers including program counter) 2) OS selects next process to execute 3) OS restores state of next process to execute (ie CPU registers including program counter) |
|
|
Which of the following components of program state are shared across threads in multithreaded process? |
a) Heap memory b) Global variables |
|
|
Multiprogramming |
A process yields the CPU when it waits for I/O or terminates. |
|
|
Multitasking
|
A process yields the CPU in addition to the circumstances for multiprogramming when its time quantum expires
|
|
|
Difference between multiprogramming and multitasking |
Multiprogramming in intended to always keep CPU busy. Multitasking is also intended to time share the CPU among all processes. |
|
|
Five major activities of an OS with regard to process management |
1) Creating/ delete processes 2) Suspending/resuming processes 3) Scheduling processes 4) Providing mechanisms for process communication 5) Providing mechanisms for process synchornization |
|
|
Purpose of interrupts |
Interrupt the processor to handle some event, such as completion of an I/O request |
|
|
Difference between interrupt and trap? |
Trap is internally generated. Interrupt is externally generated by a pin on the CPU |
|
|
Can exception be generated intentionally by a user program? |
Yes. A process will have an instruction for this purpose. |
|
|
What is a process? |
§ A job § Unit of computational work § Independent fetch/decode/execute cycle § An executing instance of a program § A single stream of execution in its own address space § Heavyweight process |
|
|
What is a program? |
A set of instructions a computer can interpret and execute |
|
|
What the the 5 process states? |
§ New § Ready § Running § Waiting § Terminated |
|
|
Elements of process control block
|
§ Process state – state of the process
§ Process number § Program counter § CPU registers § Memory mgmt information § I/O informationfUni-programming |
|
|
Uni-programming |
One process at a time, no concurrency |
|
|
Multiprogramming |
The goal is to keep the CPU busy while processes are waiting for I/O (i.e., maximize CPU utilization) |
|
|
Multitasking |
The goal is to maintain interactivity § Time sharing à like Time Division Multiplexing in Communication |
|
|
Time Sharing |
With multitasking, we can share a CPU in a computer system |
|
|
What is process scheduling? |
§ A process can run for no longer than the scheduling time “quantum” |
|
|
What happens with quantum is too small? |
Process switching overhead becomes significant |
|
|
What happens with quantum is too large? |
Interactivity suffers |
|
|
What does the ready queue consists of? |
Processes that are in memory and are immediately ready to use the CPU |
|
|
Steps for process creation/termination? |
§ Create a new process – fork() § Execute a new program – exec() § Wait for a process to terminate – wait() § Terminate a process – exit() |
|
|
When does a process become a zombie? |
When a process terminates on UNIX systems |
|
|
What happens when a process becomes a zombie? |
§ All memory is deallocated § PCB remains so that the parent process can read the exit status |
|
|
What happens when a parent process calls wait() to read a child’s exit status? |
The child is laid to rest |
|
|
Whats an orphan process? |
one whose parent is terminated first. [Note: orphans are adopted by the init process that will lay them to rest ] |
|
|
What are the challenges of multicore programming? |
§ Dividing activities § Load balancing § Data splitting/dependency § Debugging |
|
|
What is a thread? |
§ A basic unit of CPU utilization (own PC, stack and registers) § Shares with other threads (code section, static data and heap sections, I/O resources ) § lightweight process |
|
|
What are the benefits of threads? |
§ Less overhead to create compared to a process § Shares data with other threads in the same process § Multi-threading is the best way to parallelize a single program execution |
|
|
What manages user threads? |
thread library |
|
|
What manages kernel threads? |
the OS |
|
|
What is a Pthread? |
POSIX standard defining an API for thread creation and implementation |
|
|
Are threads and processes synonymous in which OS? |
Linux |
|
|
What is an issue with threads? |
If a thread calls fork() should all threads be duplicated or is the new process single threaded. |
|
|
When does process work independently? |
To perform some task |
|
|
When do processes can cooperate with other processes? |
To complete some task |
|
|
What do Cooperating processes need? |
A method to communicate |
|
|
Why do threads share memory by default? |
So it is easy for them to communicate for cooperation |
|
|
What are the two methods of inter-Process communication? |
§ Message passing § Shared memory |
|
|
What are the advantages of shared memory IPC? |
§low overhead means high speed § no OS interaction, once shared memory is initialized |
|
|
What are the disadvantages of shared memory IPC? |
complex implementation for inter-computer communication |
|
|
What is Shared Memory IPC? |
A portion of memory is set aside to be shared by multiple processes |
|
|
What is message passing IPC? |
§ Alternative to shared memory § Communication by passing messages § send() § receive() |
|