Summary Flashcards
1
Q
Process context
A
Process context : the snapshotted state of a process, which includes its data,
memory utilization, and execution progress. The process context must be saved
when the OS wants to stop running a process, and it gets reloaded when the OS
resumes running the process.
2
Q
Virtual address
A
Virtual address: mapped to physical addresses using a data structure called a
“page table”. Creates a consistent format for the OS to manage the memory of all
processes. Includes the heap, stack, code segment, data segment, and kernel
space.
3
Q
Disk
A
Disk: magnetic or optical storage for data. Disk storage is slower than your main
memory storage, but is cheaper and stores data even when the computer is
turned off.
4
Q
File descriptors
A
File descriptors : used as handles to files by processes
○ STDIN : defaults to keyboard input
○ STDOUT : defaults to printing output on your monitor/terminal
5
Q
Context switch
A
Context switch: the OS switches the process being executed. Context switches
begin with a TRAP, which is a set of instructions that cause the computer to
transition from user mode to kernel mode. Next, the OS saves the current
process context in it’s PCB, loads in the context of the next process’s PCB,
resumes this next process, and transitions back to the user mode. Context
switching creates overhead.
6
Q
Multi-core
A
Multi-core : a system with multiple CPUs
7
Q
Process state
A
Process state: running, blocking, or ready. Each state has its own process
queue in the OS.
○ Running : instructions for this process are being executed by the CPU.
○ Blocked : process is waiting on I/O access, user input, or some other
condition that cannot be met immediately, but is required to continue
executing.
○ Ready : the process has all it needs to run and is waiting for CPU access.
8
Q
Preemption
A
Preemption : when a process becomes ready, immediately give it an opportunity
to run, regardless of any processes already running or processes ahead of it in
the ready queue.
9
Q
OS Scheduler
A
OS Scheduler: most OSes have a finite time-slice for which processes can run
before they are switched out. Larger time slices reduce the overhead of context
switching, however cause longer wait times for new processes that wish to run.
10
Q
Prioritization
A
Prioritization: a technique used in scheduling to ensure that urgent processes
gain “fast passes” to the CPUs. Different priority processes may be placed in
different priority queues. The priority level is an assigned number in a range of
possible values that depends on the OS.
11
Q
I/O
A
I/O : refers to any interactions between your computer and external devices, such
as keyboard, mouse, disks, printers, monitors. Linux assigns a unique file
descriptor to each external device.
12
Q
Bytestream abstraction
A
Bytestream abstraction: an abstraction in Linux, in which all data is sent to and
read from devices as a sequence of bytes
13
Q
Write()
A
Write() : accepts a file descriptor as an input. Returns the number of bytes written
to the location specified by the file descriptor. Variations and additional syntactic
information are specified in the man pages.
○ fwrite() : buffered write
14
Q
Read()
A
Read() : accepts a file descriptor as an input. Returns the number of bytes read
from the location specified by the file descriptor. Variations and additional
syntactic information are specified in the man pages.
○ fread() : buffered read
15
Q
Disk controller
A
Disk controller: A disk controller is the controller circuit that connects the CPU
with the actual hard disk. The controller typically runs firmware, which is software
written in low-level language that controllers actual hardware. The controller
interacts with the disk device drivers running in the operating system by
sending/receiving data to/from disk to applications.
16
Q
When Does Context Switching Occur?
A
(1) Currently running process makes a system call and is blocked
• Process is put on the blocked queue
• Scheduler picks up another process in ready queue to run
• (2) Currently running process terminates
• Scheduler picks up another process in ready queue to run
• (3) Hardware or software interrupt happens
• OS handles the interrupt and blocked processes may become ready
• Scheduler may choose to continue running current process of pick
another process to run
• (4) Current process used up its current “time
• Scheduler picks up another process in ready queue to run
17
Q
Typical
Scheduler Heuristics
A
• Each process runs for a fixed time slice (typically 100 msecmsec)
• Response times vs throughput tradeoffs
• Some processes have higher priority over others:
• Interactive applications that block frequently because of system calls
• User -defined priority (using “ nice ” command in Linux or task manager in
Windows)
• System daemons
• User has a higher priority over other users using the computer
18
Q
State Transitions for fork()
A
• fork()
• Clones the child process
• Both parent and child become ready
immediately
19
Q
State Transitions for exec()
A
exec()
• Open file, load (or map) contents to memory, reset context
• Process goes to ready state as soon as this happens
• Might block if opening or loading the file takes a while
20
Q
State Transitions for wait()
A
wait()
• If child is not running, put process in ready state
• If child is running, put process in blocked state
21
Q
State Transitions for exit()
A
exit()
• Terminate process and release resources
• If parent is blocked in wait(), change parent’s state to ready
22
Q
Example I/O System Calls
A
• Generic reads/writes to file descriptors
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);
• Variants
• Blocking vs non-blocking
• Buffered vs unbuffered
23
Q
Example I/O System Calls
A
Functionally equivalent calls
scanf(“%s”, buf)
fscanf(STDIN_FILENO, “%s”, buf)
read(STDIN_FILENO, buf, …)
System calls documented in section 2 and 3 of Man pages
Type “man 2 read” or “man 3 fread” for examples
24
Q
State Transitions for I/O System Calls
A
read()
• If error, put process in ready state
• If input is available, put process in ready state
• If no input is available, put process in blocked state
write()
• If error, put process in ready state
• If I/O channel is not available, put process in blocked state, otherwise put
process in ready state
25
Control registers
Control registers: Registers in the CPU that are used to store control
information on state of program execution, for example, the program counter and
stack pointer.
26
Data registers
Registers in the CPU that are used to store the intermediate
| data used when executing instructions.
27
System call
executed in kernel mode and thus requires a context switch.
Provide an interface for the user to interact with the OS and request functionality.
Each system call has a call number, which is used by the system call dispatcher
to lookup the code associated with the invoked system call.
28
Blocked queue
a process is placed on the blocked queue, maintained by the
OS, if it is waiting for some condition to be true before it is able to proceed in its
execution; one example is a process waiting for a response from an I/O device
that is not ready
29
TRAP call
a series of assembly instructions leading to he privilege bit being
flipped in the CPU to switch it from operating in user mode to kernel mode
30
CPU cache
CPU cache: stores copies the data that is frequently accessed by this processor
31
Disk operation
an operation requiring a response from the external disk
| memory
32
Interrupt
Interrupt: a notification to the OS for an event that requires servicing; the
interrupt may originate from a hardware device or software condition
33
Interrupt identifier
Interrupt identifier: used by the OS to map the interrupt notification to the
appropriate handler for the event
34
Disk device driver
Disk device driver: device drivers are used as an interface between the
hardware and software to allow the operating system to ignore the specific
details of the hardware component being used
35
Interrupt handler
Interrupt handler: A function that is run whenever a particular type of interrupt is
invoked and received by a process.
36
Segmentation faults (C programming)
Segmentation faults (C programming): a failure that occurs when the program
attempts to access a restricted portion or memory, or read/write illegally (e.g.
write to a read-only location of memory). This is a means of notifying the OS of
the illegal action, and results in memory protection for the machine.
37
Pointer (C programming)
Pointer (C programming): store the addresses or memory locations of variables
38
Dereferencing (C programming)
Dereferencing (C programming): use the address value from the pointer to
access the data in the memory location
39
Hardware Interrupts
Hardware Interrupts: interrupts that are generated at the hardware level,
typically in response to an external event such as a clock tick or completion of a
disk request.
40
Clock pulse
Clock pulse: All motherboards usually come with its own clock. Every clock tick
generates a pulse which is delivered to the operating system in order to advance
current time and invoke the scheduler.
41
Illegal instruction
Illegal instruction: A hardware instruction that is disallowed, for example, an
instruction that cannot be run due to lack of privileges or an instruction that
touches memory location that is not available to the current process.
42
Scheduler
Scheduler: a piece of software that resides in the scheduler that decides which
process to run next.
43
Interrupt Service Routine
Interrupt Service Routine: whenever a hardware interrupt arrives, it is delivered
to the operating system where there is a piece of software called the interrupt
service routine that decides how to handle the interrupt. This is analogous to the
signal handler.
44
Hardware interrupt ID
Hardware interrupt ID: a unique identifier assigned to each hardware interrupt.
The interrupt service handler uses this to decide how to handle the specific
interrupt.
45
Custom handlers
Custom handlers: signal handlers that provided in user space and is
customized by the application for handling the particular signal.
46
Default handlers
Default handlers: signal handlers that are default in the operating system.
47
Signal relaying
sending one signal from one process to another through the
| kernel.
48
Preemptible signal handlers
when a signal handler is running and a new
signal arrives, rather than complete running the signal, if the handler is
“preemptible”, it means we can stop the current handler and deal with the signal
first.
49
Signal blocking
a signal being buffered and delayed at the operating system
| and not delivered to the process until it is explicitly unblocked.
50
Multiprogramming
Run multiple applications at the same time, protecting
| them from one another and sharing the CPU between them
51
Hierarchical file system
Store data on disk persistently organized in a tree
| structure
52
Plug-and-play devices
Software that allows external devices (e.g. printers
| and scanners) to interact with applications
53
Virtual memory
Graphical User Interface
54
ENIAC
The Electronic Numerical Integrator and Computer (ENIAC) was the
first general-purpose electronic computer. ENIAC was developed at the
University of Pennsylvania
55
Punch cards
Pieces of stiff papers with holes in them, where the presence
and absence of holes is used to encode digital information about data or
programs
56
Resident Monitor
A piece of software that is a precursor to modern
operating systems. This software runs in memory and in the punch card era,
and was used to process one punch card at a time
57
Operating System (OS)
A piece of software that is layered between
applications and hardware, allowing multiple applications to share the same
physical machine resources and gain access to external devices
58
Time-Sharing
The ability to share one physical compute resource among
| multiple applications.
59
Multics
A time-sharing operating system developed by MIT, General Electric,
and Bell Labs for mainframes in the 60s
60
Compatible Time Sharing System (CTSS)
An operating system developed
| by MIT that shares similar time-sharing features as Multics
61
Linux
An open-source operating system commonly used on both home and
server machines. Linux is closely modelled after its predecessor Unix
62
Unix
A well-known operating system developed by Bell Labs that has many
of the features used in modern operating systems, such as time-sharing, a
Shell, and a hierarchical file system
63
MS-DOS
An early operating system developed for end-user computers by
Microsoft. MS-DOS introduced the command prompt interfaces seen in many
subsequent versions of Windows
64
Berkeley Standard Distribution (BSD)
A Unix distribution developed by the
University of California, Berkeley. It is most well-known for its pioneering
implementation of the TCP/IP protocol used over the internet today
65
Ubuntu
A popular distribution of Linux that is considered easy to install and
easily usable by the non-expert
66
Virtualization
A method for dividing up physical compute resources into
logical separate units usable by different users. The most common example is
running multiple operating systems that share one physical machine
67
Embedded Operating System
An operating system for small devices like
sensor networks, or specialized hardware used in airplanes, home
appliances, and other mobile devices
68
Vagrant
A software that automates the process of installation of virtual
machines
69
Virtual Machine
A piece of software that emulates a physical machine, but is
| actually an application running on an existing operating system
70
Host OS
T he operating system that runs on the actual hardware
71
Guest OS
The operating system that runs in the virtual machine
72
VirtualBox
An open-source software that enables us to run virtual machines
73
Code Repository
A service that stores multiple versions of code, either in
| the cloud or locally on a server machine
74
Version Control
The ability to manage and change across multiple versions
| of digital content, typically software
75
Git
An open-source popular version control software
76
Pull (from code repository/Git)
Getting a version of software from a code
| repository
77
Push (from code repository/Git)
Pushing locally committed software
| changes into a code repository
78
Merge (in Git repository)
Pulling in changes from a code repository and
combining the changes with local changes, before pushing the combined version back to the server. Merge can sometimes be done automatically if
there are no conflicting changes
79
Kernel
one of two core components of OSs (with the file system)
80
File management system
one of two core components of OSs (with the
kernel). All data in a computer is stored in the form of a file, and the OS helps
maintain the file sizes, names, locations, directory structures, and file access
rights
81
CPU
the Computer Processing Unit. Circuitry to execute program
| instructions
82
CPU cycle
the cycle performed by the CPU to read a program instruction,
execute it, and repeat
83
User mode
applications in user mode can only run instructions that affect its
own application. Executing functions in the application’s code
84
Kernel mode
allows privileged machine instructions to run. This mode is
| entered by flipping a bit on the CPU
85
Privileged machine instructions
have global effects on your whole
computer and external devices. Examples include (1) writing data to disks and
(2) running the logic that makes one application stop running, and instead
start running another application
86
Process
a program in execution. Because there are limited CPU cycles and
the OS needs to perform many tasks, the process concept allows OSs to
switch between executing different tasks
87
Process context
the snapshotted state of a process, which includes its data,
memory utilization, and execution progress. The process context must be
saved when the OS wants to stop running a process, and it gets reloaded
when the OS resumes running the process
88
Process management
a function of the OS kernel that manages applications
| using an abstraction called a process
89
Address space
the memory organization model for processes. Each process
has its own address space of five segments, including (1) Code, (2) Data, (3)
Heap, (4) Stack, and (5) Kernel space
90
Code
a segment of the process address space that is, by convention, stored
in the memory locations specified by the lowest addresses. Consists of the
instructions being executed for the process
91
Program counter
register value stored in the CPU. It points to the address of
the next instruction to execute in the Code segment
92
Data
a segment of the process address space that, by convention, is stored
in the memory locations just above the Code segment. Stores
statically-defined variables
93
Heap
a segment of the process address space that, by convention, is stored
in the memory locations just above the Data segment. Stores dynamically
allocated memory. Grows and shrinks at runtime during program execution,
for example using malloc() and free() system calls in C
94
Stack
a segment of the process address space that, by convention, is stored
in the memory locations just above the Heap segment. Stores temporary
values required during function calls and pops them off once the function
completes
95
Kernel space
a segment of the process address space that, by convention,
is stored in the memory locations just above the Stack segment. Reserved
space for the OS and privileged code
96
Process Identification Number (PID)
unique number assigned to each
| process by the OS
97
Process table
contains an array of process control blocks, and is maintained
by the OS
98
Process Control Block (PCB)
each PCB stores the context of a single
| process
99
Init process
the only process that exists when the OS is booted. All other
processes are child processes of init
100
Parent and child processes
processes are managed in a hierarchical
| structure. A parent process creates child processes
101
PPID
PID of the process’s parent
102
File descriptors
handles to open files used by processes
103
Copy-on-write
On the creation of a new process, the child shares the
parent’s memory address space until a modification is required. On a
modification, a distinct memory page is then created for the child
104
Fork()
system call that creates a new process and gives an integer return
value, which is used to differentiate between the child and parent processes
that are simultaneously running the same code after the call
105
Exec()
accepts a path name to a code file as an input, and allows the child to
execute this new piece of code
106
Wait()
allows a process to wait for another process to finish completing, to
give a signal, or to perform some other specified condition. The settings are
specified in the Linux man-pages
107
Exit()
terminates the process in which the exit() command is invoked
108
Process state
running, blocking, or ready
○ Running: instructions for this process are being executed by the CPU.
○ Blocked: process is waiting on I/O access, user input, or some other
condition required to continue executing.
○ Ready: the process has all it needs to run and is waiting for CPU
access.
109
Signals
software interrupts sent from process A to process B to
communicate an event that took place in process A. Process B can be set up
to watch for certain signals and respond accordingly, depending on the
application being run
110
Superuser
an account with special permissions on a machine. The exact
| permissions vary depending on the machine’s OS
111
Orphan process
process A is an orphan process if process A is the child of
| process B, B has terminated, but A is still running.
112
Zombie process
process A is a zombie process if process A is the child of
| process B, but B has not called wait on A
113
Daemon process
system-level processes that are started to run OS-specific
| management tasks
114
Shell
an interface allowing the user to enter OS commands
115
Redirection
modifying the location to which an input is taken from or an
output is sent for a given command; redirection operators are commutative,
meaning they can appear in swapped orders and produce the same result
○ “dup2” system call : implement redirection by passing in two file
descriptors (oldfd and newfd) and causing newfd to point to the file or
data structure that was pointed to by oldfd
○ http://man7.org/linux/man-pages/man2/dup.2.html
116
Standard input
the location where programs look for their inputs; for
programs initiated in command-line, this defaults to your terminal; Standard in
can be redirected, and child processes inherit standard in from their parent
process; the Standard in file descriptor is “0”
117
Standard output
the location where programs stream their outputs; for
programs initiated in command-line, this defaults to your terminal; Standard
out can be redirected, and child processes inherit standard out from their
parent process; the Standard out file descriptor is “1”
118
Pipes
a form of interprocess communication, providing a way to stream data
from one process to the other; pipes have a “write end” to which data gets
written by one process to be sent to another process, and a “read end” from
which the receiving process reads the incoming data
119
SIGPIPE
a signal generated when a process tries to write to a pipe whose
read end has been closed
120
Process pipelining
running multiple processes at the same time where the output
| of one process is used as input to another process
121
Half-duplex
data flows in one direction; pipes between two processes are in the half
duplex communication paradigm as data flows in one direction between the two
processes
122
FIFOs
these are similar to pipes; while pipes are temporary and unnamed
connections, FIFOs are files with names that allow two processes to communicate by
writing to the file
123
Process group
collection of processes that are established in a way such that you
can send (or block) a signal to the entire group at the same time; the processes in a
pipeline are in a single process group
124
PGID
process group ID
125
Session ID:
one instance of your login to your shell is a session, and all processes
launched in this session have the same session ID
126
SSH
a secure network protocol that allows a remote user to be authenticated to
login to a machine
127
Foreground process
there is always exactly one foreground process; this process
has access to interactive shell output (in the absence of explicit redirection) and
input, and receives all the terminal generated signals; the shell must wait on this
process before executing another process
128
Background processes
there can be any number of background processes; these
processes will allow the user to execute other programs and interact with the shell
without waiting
129
Job/terminal control
ability to manipulate multiple jobs from a single terminal and
also to allow us to toggle jobs between background and foreground
130
Synchronous waiting
a process waits finds out the outcome of another process by
| implementing a loop that constantly checks for a signal; “busy wait”
131
Asynchronous waiting
a process continues executing normally and when another
process has a signal to send, a generic SIGCHLD is sent to the executing process,
who handles the signal with a SIGCHLD signal handler
132
Open file descriptor table
contains all the files that have been opened by a
| process; stored in the PCB
133
Page table
contains all the mappings from virtual to physical address space;
a pointer to the page table is stored in the process PCB
134
Thread
created within a process; enables splitting an executing program into
multiple simultaneously or pseudo-simultaneously running tasks to keep the
CPU cores busy by having them run in parallel; each thread has its own
execution context, though the heap memory, static data segment, and code
segment of the virtual memory, as well as the open files, are shared with the
process
135
Thread table
stores the execution context of the threads, which includes the
thread processor registers, stack pointer, program counter, MMU, general
registers, and stack memory segments
136
Thread pool
where you pre-create a number of threads in the system, and
what you do is whenever a client comes in, you take one of the idle threads to
service the client; after the client request has been serviced, then the thread is
returned to the pool and it's available for servicing future clients
137
Thread affinity
CPU cores have caches and in multicore systems, if threads
keep getting run on the same core, then their data will be more likely to be
cached; thus, threads should always run on a specific core
138
User level threads
the thread library is located in user space; the OS does is
| not aware of the threads
139
Kernel level threads
the thread library is located in kernel space; each
| thread is handled and scheduled individually
140
Virtual dynamic shared objects
allows user space to handle certain kernel
space routines, to reduce the need for context switching; memory allocated in
user space
141
Concurrency control
managing the interleaved execution of multiple
| processes that access the same shared states, to produce the correct results
142
Race conditions
two or more threads or processes attempt to access and
update the same data at the same time; the result of a computation depends
on the exact timing of the multiple processes or threads being executed
143
Synchronization
implementing coordination between processes
○ Critical section: a portion of code that involves an access or
modification of shared state
○ Mutual exclusion : enforcing that only one process is in any given
critical section at a time
○ Progress : if no process is currently in the critical section, and at least
one process wants to enter it, some process will eventually be able to
enter
○ Bounded waiting : a process that is waiting in line to enter the critical
section will not be waiting indefinitely, and is guaranteed to have an
opportunity to enter
144
Busy-wait
a loop checking the same condition repeatedly; the process
busy-waiting cannot proceed until the condition becomes true; consumes
CPU resources inefficiently
145
Disabling interrupts
an overly powerful approach to implementing
synchronization that prevents the OS from performing all context switches,
which are caused by interrupts
146
Atomic statements
the compiler can translate such a statement to one line
| of assembly language, thus making this an uninterruptible statement
147
Deadlock
processes are waiting for each other, such that none of them can
proceed
148
Test-and-set lock
a hardware instruction that locks memory locations while
| they are being accessed by a process
149
Race condition
the system attempts to perform two or more operations at
the same time, but due to the underlying context switching and scheduling
implementations by the OS, the ordering of these operations is not
guaranteed. The result of the operations changes as a function of changes in
ordering.
150
Semaphore
a semaphore is a kernel object with an integer value. It supports
two operations, P and V, which modify the integer value.
○ P : One of the operations of a semaphore. If the semaphore’s value is
greater than zero, decrement. Otherwise, wait until the value is greater
than zero and then decrement. Sometimes it is also called wait.
○ V : One of the operations of a semaphore. Increment the value of the
semaphore. Sometimes it is also called signal or post.
○ Binary semaphore : a semaphore that saturates at an integer value of
1.
○ Counting semaphor e: a semaphore that saturates as an integer value
of N, for N greater than or equal to 1.
151
Waiting queue
processes or threads waiting to enter the critical section are
notified, or “woken up”, when the process currently using the critical section
exits. This strategy helps eliminate the need for busy waiting in the
semaphore implementation
152
Deadlock
two or more processes are waiting indefinitely for an event that
can be caused by only one of the waiting processes
153
Monitors
a high-level abstraction that provides a convenient and effective
mechanism for process synchronization. Only one process may be active
within the monitor at a time
154
Condition variables
a primitive with two functions, wait and signal.
○ Wait : a condition variable function called by a process that waits for a
condition to be true
○ Signal : a condition variable function that wakes up a process waiting
on the condition to be true
155
Deadlocks
suppose there is a finite set of resources and there are multiple
threads or processes requesting these resources. There is a deadlock if the
threads are waiting on resources held by other threads in a cycle such that none
of the threads in this cycle of dependencies will be able to proceed. The
conditions for deadlocks are as follows:
○ Mutual exclusion: resources held by one process cannot be
simultaneously used by another process
○ Resource preemption: when a process or thread acquires a particular
resource, it holds onto the resource until it releases it; other processes or
threads cannot steal the resource
○ Hold and wait: a process can accumulate resources and does not have
to grab all the resources that it needs at the same time
○ Circular waiting: circular chain of processes that are requesting
resources from each other
156
Mutual exclusion
resources held by one process cannot be
| simultaneously used by another process
157
Resource preemption
when a process or thread acquires a particular
resource, it holds onto the resource until it releases it; other processes or
threads cannot steal the resource
158
Hold and wait
a process can accumulate resources and does not have
| to grab all the resources that it needs at the same time
159
Circular waiting
circular chain of processes that are requesting
| resources from each other
160
Hierarchical allocation (deadlock prevention)
create a policy that determines
which processes can receive which resources by creating a hierarchy between
the resources or between the processes
161
Resource allocation graph (deadlock detection)
a RAG is a tool for deadlock
detection, because deadlock only occurs if the RAG has a cycle. To form the
RAG, there is a node for every process and a node for every resource. If a process P currently has resource R, then we form a directed edge from R to P. If
process P is requiring process R, then we form a directed edge from P to R.
162
Wait-for-graph (deadlock detection)
shows dependencies of processes or
threads that waiting on others. To form this graph, there is a node for each
process or thread, and there is a directed edge from Pi to Pj, if Pi is waiting on a
resource from Pj
163
Checkpointing
save the state (of a process) in case of a required rollback of
operations to the process
164
Safe-allocations (deadlock avoidance)
an allocation state is safe if there is a
sequential ordering of processes such that all the processes will be able to finish
executing
165
Banker’s Algorithm (deadlock avoidance)
given n processes and m
resources, the algorithm only grants resources to a process if it will result in a
safe allocation state
○ Req[i, j]: matrix representing the number of resources Rj requested by
process Pi
○ C[i, j]: matrix representing the amount of resource Rj currently held by
process Pi
○ M[i, j]: matrix representing the maximum number of resource Rj that a
process Pi will ever request
○ A[j] : vector representing the number of resource Rj that are currently free
