1
Q
the process model
A
Allows the OS to simplify:
- Resource allocation
- Resource accounting
- Resource limiting
OS maintains information on the resources and the internal state of every single process in the system
2
Q
processes in the process model
A
- single process counter
- each process in unique location
- CPU switches back and forth from process to process
- Each process has own flow of control (own logical program counter)
- Each time we switch processes, we save the program counter of first process and restore the program counter of the
second - all processes make progress, but only one is active at any given time
3
Q
concurrent processes
A
- The CPU can be allocated in turns to different processes
- OS normally offers no timing or ordering guarantees
4
Q
process hierarchies
A
- 1 init process
- parent can create many child processes
- tree structure with process groups
- child can have some or all resources from the parent
5
Q
parent -> child (address space)
A
- the child is a duplicate of the parent ⇒ it has the same data as the parent
- the child has a new program loaded into it
6
Q
Four principal events that cause processes to be created
A
- System initialisation
- Execution of a process creation system call by a running process
- A user request to create a new process
- Initiation of a batch job
7
Q
process termination
A
all the resources are deallocated after termination
8
Q
a parent may terminate its child because
A
- the child has exceeded its usage of the resources it has allocated
- parent needs to know the state of the children → uses some mechanism
- the task is no longer required
- the parent is terminated itself (in some os)
9
Q
typical conditions which terminate a process:
A
- Normal exit (voluntary)
- Error exit (voluntary)
- Fatal error (involuntary)
- Killed by another process (involuntary)
- only parent can kill the child process
10
Q
information associated with a process
A
ID (PID), User (UID), Group (GID)
memory address space
hardware registers (e.g. pc)
open files
signals
11
Q
Where is information associated with a process stored?
A
in the operating system’s Process Table
12
Q
PCB
A
process control block, consist of:
- process ID
- process state
- process number
- program counter
- registers (CPU registers)
- CPU scheduling information
- memory limits - memory management information
- list of open file
- accounting information
- I/O information
13
Q
process states
A
- Running (actually using the CPU at that instant)
- Ready (runnable; temporarily stopped to let another
process run) - Blocked (unable to run until some external event
happens)
14
Q
process blocks for input
A
running -> blocked
15
Q
scheduler picks another process
A
running -> ready
16
Q
scheduler picks this process
A
ready -> running
17
Q
input becomes available
A
blocked -> running
18
Q
Which layer handles interrupts and scheduling
A
the lowest layer of a process-structured operating system
19
Q
scheduling queues
A
- job queue: all processes in the system
- ready queue: processes in the main memory and waiting for the CPU
job -> ready ->CPU
20
Q
context switches
A
state save
state restore
21
Q
Why is context switch time pure overhead?
A
because the system does no useful work while switching
22
Q
Interrupt vector
A
- Associated with each I/O device and interrupt line
- Part of the interrupt descriptor table (IDT)
- Contains the start address of an OS-provided internal procedure (interrupt handler)
23
Q
Who continues process execution after interrupts?
A
interrupt handler
24
Q
interrupt types
A
sw, hw, device (async), exceptions
25
what the lowest level of the operating system does when an interrupt occurs
1. Hardware stacks program counter, etc.
2. Hardware loads new program counter from interrupt vector.
3. Assembly language procedure saves registers.
4. Assembly language procedure sets up new stack.
5. C interrupt service runs (typically reads and buffers input).
6. Scheduler decides which process is to run next.
7. C procedure returns to the assembly code.
8. Assembly language procedure starts up new current process.
26
Every time an interrupt occurs, who gets control acts as a mediator?
the scheduler
27
thread
unit of execution within a process
28
threading +
+ allows space and time efficient parallelism
+ allows simple communication and synchronisation
+ responsiveness
+ resource sharing
+ economy
+ multiprocessor utilisation
29
dispatcher and worker thread
dispatcher: process incoming requests
working: handle the requests
30
threads
single-threaded process
finite-state machine / event driven process
parallelism, blocking syscalls
no parallelism, blocking syscalls
parallelism nonblocking syscalls, interrupts
31
Blocking syscalls
pause execution until completion, causing the process to wait
32
Nonblocking syscalls
return immediately, allowing the process to continue executing even if the requested operation isn't ready yet
33
user threads
managed without kernel support
34
kernel threads
managed directly by the kernel
35
thread model many to one
one is blocked → all blocked
can access the kernel one at a time; no space for utilisation
36
thread model one to one
costly: every user needs to create a kernel thread, heavy on the system
37
thread model many to many
multiple user-level threads to be multiplexed over multiple kernel-level threads
38
threads in a process
- threads reside in the same address space of a single process ⇒ all threads can access the same memory (fast access)
- All information exchange is via data shared between the threads
- Threads synchronise via simple primitives
- Each thread has its own stack, hardware registers, and state
- Thread table/switch: a lighter process table/switch
- Each thread may call any OS-supported system call on behalf of the process to which it belongs
39
per process items
1. address space
2. global variables
3. open files
4. child processes
5. pending alarms
6. signals and signal handlers
7. accounting information
40
per thread items
- ID
- program counter
- registers
- stack
- state
41
user-level thread package
kernel has no knowledge of it → can’t go to another thread
42
a thread package managed by the kernel
kernel maintains the threads, if a thread blocks a process the kernel can schedule it
43
user threads +/-
+ thread switching time (no mode switch)
+ scalability, customisable
- transparency
- parellelism
44
event driven servers
Implement server as finite-state machine that responds to events using
asynchronous system calls
45
When to schedule?
- Process exits
- Process blocks on I/O, Semaphore, etc.
- When a new process is created
- When an interrupt occurs:
○ I/O, clock, syscall, etc.
46
preemptive scheduling
"kick-out" running process no matter what
47
non-preemptive scheduling
keep the process running until it leaves the CPU
48
Categories of Scheduling Algorithms
batch
interactive
real time
49
scheduling algorithm goals
fairness: giving each process a fair share of the CPU
policy enforcement: seeing that stated policy is carried out
balance: keeping all parts of the system busy
50
batch systems
Throughput: maximise jobs per hour
Turnaround time: minimise time between submission and termination
CPU utilisation: keeping the CPU busy all the time
51
interactive systems
response time: respond o requests quickly
proportionality: meet user expectations
52
policy vs mechanism
Important principle
Here: we may have a scheduling algorithm, but parameters to be filled in by user (process)
For instance, to give some child processes higher priority than others
53
real time systems
meeting deadlines: avoid losing data
predictability: avoid quality degradation in multimedia systems
timing plays an essential role
soft real time vs. hard real time
periodic and aperiodic tasks
static or dynamic schedules
54
schedulable formula
55
scheduling criteria - all systems
- Fairness—giving each process a fair share of the CPU
- Policy enforcement—seeing that stated policy is carried out
- Balance—keeping all parts of the system busy
56
scheduling criteria - batch
- Throughput—maximize jobs per hour
- Turnaround time—minimize time between submission and termination
- CPU utilization—keep the CPU busy all the time
57
scheduling criteria -interactive
- Response time—respond to requests quickly
- Proportionality—meet users’ expectations
58
scheduling criteria - real-time
- Meeting deadlines—avoid losing data
- Predictability—avoid quality degradation in multimedia systems
59
scheduling algorithms for batch systems
FCFS
Shortest job first
Shortest remaining time next
60
scheduling algorithms for interactive systems
round-robin
priority
multiple queues
shortest process next
guaranteed scheduling
lottery scheduling
fair-share
61
scheduling for real time systems
soft vs hard
period vs aperiodic
static or dynamic
62
Operating Systems
flashcards
Decks in class (8)
# Cards
