CS 4348 — Operating Systems Concepts, Final Review
Process Creation
- Processes are arranged in a tree, with distinct address spaces
The process image starts as a replica of another process
fork() system call makes a new “child” process
0 to the child process
- This makes sense because the child process can always get getpid() to get the ID
- PID to the parent process, since there is no other way to get the child process
- −1 on Failure
- They begin from the next instruction after the fork
- exec() system call replaces the current process image with a new process image and begins running it from the beginning
Process Synchronization
Sharing data between processes is very useful
But its difficult because of read/write
Processes cannot read/write concurrently
- What if the data is only half-written to a file, then a context switch occurs? This means that the data written to the file is not useful.
- What if two processes want to write data at the same time? Even if both finish writing, the data will be garbled
So we create some way of “mutual exclusion”
- Note that we could create mutual exclusion by stopping multiprogramming (at least partially), but this is of course not ideal
Concurrent programs have problems
- Race conditions
- Deadlocks
- Livelocks
Mutual Exclusion Problem
Locks
The process can “acquire” the lock
- The context switch cannot occur while the lock is acquired
The process can “release” the lock
- The process switch can occur while it is released
The code between the
acquireandreleaseis now seen as being atomic, and so is called a “critical section”Easy to use
Deadlocks may occur
Semaphore
Integer/counter value which is arbitrarily initialized
It wan be decreased (wait) or increased (signal)
wait()
- Decrease integer if its value is > 0
- Wait if value of semaphore is = 0
signal()
- integer value += 1
If a process is waiting for the value of a semaphore to become > 0, then increase will allow some other process’s wait() call to occur and continue in the code
wait and signal must be atomic, for example if wait() is called 2 times and context switches between, allowing the integer value to decrease below 0 then future signal() operations may not work
We can also think of a Lock as being a binary semaphore
Monitor
Semaphores are unreliable
- They work, but only when used correctly
- Monitors are simply a generalization of OOP which encapsulates data and operations within a class
- Objects of the class can be allocated and the methods can be invoked on the fields of the object
Only one process can execute an operation on an object at any one time
- All the fields are private
- Encapsulated semaphore
Deadlocks
One of the problems with process synchronization is that of deadlocks
A process has to wait for another to release a resource
If a wait is circular, then no process is able to execute
- This is a deadlock
A process requesting a process in a the set of processes involved in the circular wait is also blocked forever
Chained waiting
A resource must have mutual exclusion (i.e. only so many copies of the resource exist)
Every process in the circular wait must be holding a resource and waiting for another
No preemption
Circular wait
If many copies of the resource exist, you can use the bankers algorithm
Deadlock prevention
Make resources shareable
- Not all types of resources can be shared
Hold and wait
- Each process can request all of its resources to perform its task at once
- This is wasteful
Preemption
- You can interrupt processes to take away their resources
- This may require reverting a victim process, which is not always possible
Acquire resources in increasing order of rank
Give all resources a rank
Assign resources to processes in order of rank
Requires knowing all available resources beforehand
Deadlock avoidance
Claim edges
- A process may or may not use a process in the future
- Do not grant a request if it will create a cycle
Bankers algorithm
- Allocate resources such that the state is always safe
- Safe means that resources can be fully allocated to a process and a deadlock will not be created
Deadlock detection and management
- Detect by running bankers algorithm
If found
- Terminate a process
- Preempt a resource
Mass Storage
- Disk, Tape, SSD
We focus on disk
How do we schedule access on a disk (i.e. given a set of addresses, which order should we look up adresses?)
First Come First Serve
- Naive and easy to implement
- You have to cover alot of ground multiple times
Shortest Seek Time First
- Greedily go to shortest seek time
- Not amazing in practice
SCAN
- Bounce back and forth from beginning to end
Circular SCAN
- Keep looping around the
LOOK
- Bounce back and forth until you get from first request to last request
Circular LOOK
- Bounce back and forth until you get from first request to last request
RAID
- Redundant storage on inexpensive disks