Processes and Threads Flashcards
How do processors execute instructions?
1) Fetches the instructions from memory 2) Decodes them (to determine type and operands) 3) Executes them This is repeated for subsequent instructions
What does each process have?
An associated address space containing executable program, its data and its stack
How do processes work in multiprogramming?
Each process has its own logical program counter (there is only one physical program counter), so when a process runs its logical program counter is loaded into the physical program counter.
What events cause processes to be created?
1) System initialisation
2) Execution of a process creation system call by a running process
3) A user request to create a new process
4) Initiation of a batch job
How are processes that are not created at boot created?
They must be created by other processes issuing system calls to create processes to help out
CreateProcess
Windows call that both creates a new process and loads correct program
How does a process terminate and are these voluntary or involuntary?
1) Normal exit (voluntary) 2) Error exit (voluntary) 3) Fatal error exit (involuntary) 4) Killed by another process (involuntary)
Give an example of a fatal error
Seg fault Divide by 0 error Bus error
How many parents does a process have?
1, but may have 0-many children
How are signals sent to a process group?
Signals are sent to all members of an associated process group. Each process can choose to catch, ignore or take the default action (be killed) with regard to the signal
What is the default action of a process when receiving a signal?
To be killed
Explain the concept of process hierarchy in Windows
There is no concept of process hierarchy in Windows. All processes are created equal. The parent process is however given a token called a handle, which can be used to control the child process. However, this can be passed to other processes, invalidating the hierarchy.
Can parent processes in UNIX disinherit their children?
No
All processes in a system belong to what?
A single tree (inheritance) with init at the root
Explain the concept of process hierarchy in UNIX
Association exists between parent and child processes. A process and all of its descendants form a process group
How does init work?
This is present in the boot image. It reads in a file with the number of terminals and forks off one process per terminal. These terminals wait for a user to login. If successful, login process executes a shell to accept commands, including starting more processes
How many processes does a program running twice count as?
2
How does a process run a new program?
The process forks off a child process, which executes execve to change memory image and run a new program. By doing this, the child can change file descriptors between the new program and the execve to achieve redirection of standard input, output and error.
Are background processes associated with particular users?
No
Why shouldn’t programs be built with assumptions about timing?
Multiprogramming will cause inconsistencies in this if programs are temporarily stopped to let others run
What states can a process exist in?
1) Running: currently using CPU 2) Ready: ready to run, but waiting on another process currently using CPU 3) Blocked: unable to run until some external event happens
What are the transitions between the states that a process can exist in?
1) Running to Blocked: Process realises that it is dependent on some external information in order to continue execution 2) Running to Ready: Caused by scheduler deciding to allocate time to another process 3) Ready to Running: Caused by scheduler allocating time to this process 4) Blocked to Ready: External event occurs meaning that process is able to logically run. If no process is running, transition 3 will be automatically triggered
What states can a thread exist in?
1) Ready 2) Running 3) Blocked (same as process)
Why is there no protection between threads?
1) Not possible 2) Shouldn’t be necessary: a process is always owned by a single user and threads should be made to cooperate
What items are shared by everything within one process (ie. every thread of a process shares what)?
1) An address space 2) Global variables 3) Open files 4) Child processes 5) Pending alarms 6) Signals and signal handlers 7) Accounting information
What items within a process are specific to individual threads (assume that the process is multithreaded)?
1) Program counter: keeps track of which instruction to be executed next 2) Registers: hold current working variables 3) Stack: execution history with one frame for each procedure called but not yet returned from 4) State: running, ready, blocked
How does multithreading work on a single CPU?
The same way as multiprogramming. Only one thread can run at a time, so CPU implements pseudoparallelism through the technique of rapid switching between threads
What does a thread do when it’s finished its work?
It exits by calling the appropriate library procedure (eg. thread_exit)
Can threads exist in a hierarchical structure?
Yes; however, often threads are created equal.
What two concepts is the thread model based on?
1) Resource grouping 2) Execution
Does a thread have to execute in a process?
Yes
What’s the difference between a thread and a process?
Threads are entities scheduled for execution on the CPU, while processes are groups of related threads
What are the advantages of threads?
Allows multiple executions to take place in same environment mostly independently of each other Do not offer performance gain with just one CPU, but threads can overlap saving time if significant I/O is involved (not needing to wait while blocked) Real parallelism on multicore processors
How are new threads usually created?
A single thread calls a library procedure to create more threads with them: thread_create
What problems are introduced with multithreading?
1) If a parent process is multithreaded and creates a child process, does each thread have access to the child? 2) Threads share data structures. What happens if one thread closes a file that another thread is trying to read from? 3) Multiple space allocation - if all threads try to allocate more memory for the same thing
What is an advantage to having multiple threads as compared to having multiple processes?
Since threads do not have resources, they are easier to create and destroy than processes
Compare single threaded processes, multithreaded processes and finite state machines
Single threaded: No parallelism, blocking system calls Multithreaded: Parallelism, blocking system calls Finite state machines: Parallelism, non blocking system calls
What modes can threads be executed in?
User or kernel modes
What are the advantages to threads executed in user space?
1) Mode switch not required
2) Thread scheduling can be application specific
Explain the process of interrupt handling and scheduling
1) Hardware stacks program counter 2) Hardware loads new program counter from interrupt vector 3) Assembly language procedure saves registers 4) Assembly language procedure sets up a new stack 5) C interrupt service runs 6) Scheduler decides which process to run next 7) C procedure returns to assembly code 8) Assembly language procedure starts up new current process
Explain the difference between implementing threads in kernel and user modes
No runtime system needed in kernel Kernel mode has one thread table instead of one for each process
How do hybrid implementations of threads work?
Kernel level threads are used and user level threads are multiplexed onto some or all of these threads Kernel is only aware of kernel level threads User level threads are created and destroyed at minimal cost
What are some disadvantages to user level threads?
1) If one thread blocks, the entire process will block
2) Cannot take advantage of multiprocessors
What is the problem with changing user-level thread system calls to nonblocking?
This would require changes to the OS, which would invalidate one of the reasons why user-level threads are advantageous. Changes would need to be made to multiple other programs.
What is the problem with creating a wrapper around user-level threads to prevent blocking?
Parts of the system call library must be rewritten
Explain the concept of a jacket/wrapper with regard to user-level thread blocking
Code, referred to as a wrapper/jacket (eg. select in UNIX) is placed around the system call to check if it will read or block. If it blocks, the system call will not be executed, and other threads will start. This thread will be returned to later.
Explain how page faults affect user-level threads
If a program tries to access an instruction that is not in main memory, the OS will need to go to the disk to retrieve this instruction. The kernel, not knowing about threads, will block the entire process until disk I/O is complete - even though other threads might be runnable.
What is a possible solution to the problem of user-level threads running forever? Why will this solution not work?
Have runtime system request a clock signal (interrupt) regularly to give it control. This is messy to program and periodic clock interrupts may not be possible. If they are, there can be substantial overhead
What are some advantages to kernel-level threads?
1) Threads from same process can still run if one is blocked
2) Take advantage of multiple processors
What are some disadvantages to kernel-level threads?
1) Overhead of creating kernel threads
2) Mode switch is required
3) Less control over scheduling
Explain the process of thread recycling
Thread recycling involves marking a ‘destroyed’ thread as unrunnable, but keeping the data structures associated with it. When a new thread needs to be created, this data structures are reused.
Is thread recycling possible in user or kernel modes or both?
Both, but it doesn’t make sense to do it in user-mode as the overhead for creating/destroying threads is much less than kernel
What are the problems with scheduler activations?
The reliance on upcalls. Upcalls violate structure of a layered system. Usually higher layers can call on lower layers, but not the other way around.
How are incoming messages to processes traditionally handled? How else can they be handled?
They are traditionally handled by having some process of thread that is blocked, waiting for an incoming message. These can also be handled through the use of popup threads
Explain the concept of popup threads
When an incoming message (eg. service request) is received, a new thread can be created to handle this. This thread is a popup thread.
What are some advantages of popup threads?
1) These are entirely new and so no restoration is needed 2) They are quick to create
Is a popup thread quicker in kernel or user space?
Kernel
What is an advantage to popup threads running in kernel space?
Easy access to kernel’s tables and I/O devices (which may be needed for interrupt processing)
What is a problem with popup threads in kernel space?
A buggy kernel space is more damaging than a buggy user space. Eg. incoming data lost if it runs too long
What problems exist in making single-threaded code multithreaded?
1) Variables that are global to a thread but not the entire program (ie. many procedures in the thread use them): one thread may change these values if a thread is interrupted by scheduler, causing another thread to have wrong value 2) Many library procedures aren’t reentrant 3) Memory allocation: while mallocing is occurring, pointers to memory may be inconsistent (problem if thread switch occurs) 4) Signals that are thread specific: kernel doesn’t know about existence of threads and so can’t send to specific thread 5) Non-thread-specific signals: who catches them? 6) Stack faults: usually kernel automatically gives more space if a stack overflow occurs - if kernel doesn’t know about threads, it cannot give more space to the stack of individual threads
How can we solve the problem of global variables (global to a thread but not program) in the case of making single-threaded code multithreaded? What are the issues with these solutions?
1) Prohibit global variables: conflicts with existing code 2) Assign each thread private global variables: access can be difficult, as these are essentially an intermediate between local and global variables, which most languages don’t handle 3) Introduction of new library functions to create, set, manipulate these global variables (that is, allocate separate storage in different locations per thread): this could be difficult to write
What issues exist with IPC? Do these apply to threads?
1) Passing information between processes
2) Ensuring processes do not get in each other’s way (eg. taking last bit of memory)
3) Dependencies between processes 2 and 3 also apply to threads
Why is it easy for threads to pass information between each other?
They share an address space
How can data be exchanged between machines?
Message passing
What design issues exist with message passing?
1) Messages could be lost by a network. This can be solved by having recipient send back an acknowledgement that message has been received
2) Authentication - how can it tell it is communicating with real server and not imposter?
3) Copying messages between processes is slow
What categories of scheduling algorithms exist? Or rather, what environments do scheduling algorithms run in?
1) Batch: No user waiting impatiently so time isn’t an issue. Good for preemptive scheduling with long time periods, or non preemptive. This reduces switches which increases performance.
2) Interactive: Preemptive scheduling good as there are interacting users.
3) Real time: Preemption is not completely necessary here as these processes are only those that further the application at hand and so are often made to be quick/short
When must scheduling decisions be made?
1) Creation of a new process 2) When process exits 3) When a process blocks (on I/O, a semaphore) 4) When an I/O interrupt occurs
What’s the difference between preemptive and non preemptive scheduling algorithms?
Preemptive have a set time limit with a clock interrupt occurring at end of time period, regardless of whether process is completed. Non preemptive processes will continue to run until either they are blocked or they voluntarily exit.
What are the goals of scheduling algorithms for all systems?
1) Fairness: giving each system fair share of CPU 2) Policy enforcement: seeing that stated policy is carried out 3) Balance: keeping all parts of the system busy
What are the goals of scheduling algorithms for batch systems?
1) Throughput: maximise jobs per hour 2) Turnaround time: minimise time between submission and termination 3) CPU utilisation: keep the CPU busy at all times
What are the goals of scheduling algorithms for interactive systems?
1) Response time: respond to requests quickly 2) Proportionality: meet user’s expectations (ie. complex operations take more time than simple)
What are the goals of scheduling algorithms for real time systems?
1) Meeting deadlines: avoid losing data 2) Predictability: avoid quality loss in multimedia systems
What scheduling algorithms are used in batch systems?
1) First come first served 2) Shortest job first 3) Shortest remaining time next 4) Three level scheduling
What scheduling algorithms are used in interactive systems?
1) Round robin scheduling 2) Priority scheduling 3) Multiple queues 4) Shortest process next 5) Guaranteed scheduling 6) Lottery scheduling 7) Fair-share scheduling
Explain the first come first served scheduling algorithm. What system is it used in?
Batch system. Processes assigned CPU in order they request it.
Explain the shortest job first algorithm. What system is it used in?
Batch system. Shortest job runs first. This is only optimal if jobs are received simultaneously.
Explain shortest time remaining next algorithm. What system is it used in?
Batch system. This is a preemptive version of shortest job first. Scheduler chooses job with shortest remaining runtime
Explain three level scheduling algorithm. What system is it used in?
Batch system. Level 1: Jobs initially placed in input queue on disk. Admission scheduler decides which jobs to admit to the system. Level 2: When jobs are admitted to system, process is created for them. Memory scheduler determines which jobs remain in system and which are swapped to disk if memory fills up. Level 3: CPU scheduler (aka scheduler) picks a process in main memory to run next
Explain round robin scheduling algorithm. What system is it used in?
Interactive or batch system. Each process is assigned a time interval or quantum. It runs for either that quantum or less (if process finishes). At end, CPU time is assigned to another process. This process waits to execute remaining time. This has issues as switching processes wastes time. Setting quantum to long means slow response. Good rule is 20-50ms. Short quantum - good for interactive systems, good response, poor throughput Long quantum - good for batch systems, bad response, good throughput
Explain priority scheduling algorithm. What system is it used in?
Interactive system. Runnable process with highest priority runs first. To prevent these high priority ones from running indefinitely, scheduler may decrease priority once every clock tick. Alternatively, time quantums could be used. This works well in the case where priority classes are created and round robin is used within each priority class (groups of same priority).
Explain multiple queue scheduling algorithm. What system is it used in?
Interactive systems. Processes exist in priority classes. Each priority class is given a corresponding quantum (higher priority = higher quantum).
Explain shortest process next scheduling algorithm. What system is it used in?
Interactive systems. Run process with estimated shortest amount of time. This is based on previous times and a weighting value, a (often 1/2). eg, aT0 + (1-a)T1. This uses aging
Explain guaranteed scheduling algorithm. What system is it used in?
Interactive systems. Make real promises to users and live up to them (eg. the amount of CPU power for n users is 1/n each). This is hard to implement
Explain lottery scheduling algorithm. What system is it used in?
Interactive systems. Similar to guaranteed scheduling, but easier to implement. Give processes lottery tickets for different resources (eg. CPU time). When scheduler decisions have to be made, lottery ticket chosen at random. High priority processes can be given more lottery tickets. Cooperating processes may exchange tickets.
Explain fair-share scheduling algorithm. What system is it used in?
Interactive systems. In the case of multiple users, we don’t want 1 user to get a majority of the CPU time, so this takes owners of processes into consideration. Each user is allocated portion of CPU and individual processes are scheduled acccordingly
What 2 categories do real time systems exist in?
1) Hard real time: absolute deadlines that must be met 2) Soft real time: missing occasional deadlines is tolerable
What does separating the scheduling policy and scheduling mechanism achieve?
This helps in cases where a parent process has children of different importance. The scheduler cannot take inputs from process regarding importance of these children, but separation means that scheduling algorithm is parameterised with inputs.
What are the most commonly used scheduling algorithms?
Round robin and priority scheduling
What issues do we need to consider when creating a process?
Allocate memory to process Initialise process control block Mark as ready Estimate how long it will take to run Analyse memory requirements Load first part of process into memory
How does selfish round robin work?
Same as normal RR but does not put jobs in ready queue until demand for CPU is low
Explain multi level feedback queues?
Round robin with small quantum on first level, then larger on second and so on. Finally it gets a FCFS.
What will a scheduler give high priority to?
Real time systems
Explain EDF
Earliest deadline first. Schedule process with closest deadline first
What is a fundamental security mechanism in OSs?`
Kernel mode and user mode distinction
What’s contained within the address space of a process?
Text (program), data (variables) and stack
The gap corresponds to the heap.
What’s the difference between user and system processes?
Most processes user deals with are created by the user (by invoking program from command line or GUI)
Some services implemented by OS may be implemented as separate processes (eg. print daemon)
How many modes do most CPUs have? What are they?
- User and Kernel.
What does PSW register contain?
Program status word tells us what mode we’re in
How does a system call work?
It makes use of an API
How do we transition from user to kernel mode?
Through the use of system call APIs, which cause an interrupt to occur
What is the difference between a system call and a call to a normal function?
System call is a call to a privleged function
Name some typical system calls
- process control
- file management
- device management
- information maintenance
- communication
What happens when an interrupt occurs?
CPU’s hardware takes values in program counter and PSW registers and saves to privleged memory locations (reserved for this).
Replacement PSW puts CPU in kernel mode. Replacement PC causes execution to occur at start of interrupt handler.
What does interrupt handler do?
Save rest of status of current process
Service interrupt
Restore what is saved
execute return from interrupt or similar to go back to original process
What is a signal?
Some event that occurs that something needs to happen
What is the return value of fork()?
For the child, this is 0 and for the parent it returns the process ID of the child.
If it returns -1, an error has occurred
What does it mean if execve returns?
Error occurred
What 2 types of exceptions are there?
Synchronous and asynchronous
What’s the difference between a synchronous exception and an asynchronous exception?
Synchronous - caused by system call instruction, divide by 0 error, bus error, etc
These guys will happen every single time
Asynchrnous - interrupts
These may not happen every time, or may happen differently
What is the authorisation check with regard to system calls? Can users bypass this?
We must check if we are authorised to execute the system call. There is no bypassing this by users as they would have to change interrupt vector which is in privileged part of memory
What are aims of scheduling?
Fairness: each process gets fair share of CPU
Throughput: maximise jobs processed per unit time
Response Time: minimise waiting for active users
Turnaround Time: minimise waiting for batch jobs
How do threads process system calls and interrupts?
System calls: System switches to preallocated kernel stack in system space (one stack per thread).
Interrupts: system switches to preallocated interrupt stack in system space (usually 1 for whole system)
If the kernel of an OS doesn’t support threads, what can we do?
We can imperfectly attempt to simulate threads at user level
What are the advantages to a long quantum?
Poor response time, good throughput, good for batch systems
What is the difference between shortest job first and shortest job remaining?
Shortest job remaining uses preemption.
What are the advantages to a short quantum?
Good response time, good throughput, good for interactive systems
What is the EDF algorithm?
Earliest deadline first. Do those with earliest deadlines
What is 2 level sheduling?
When insufficient main memory is available, some processes have to be kept on disk. The two parts are:
1) deciding which processes should be kept in main memory
2) deciding which of these should get the CPU
