Process States
CSci4061: Introduction to Operating Systems
September 21, 2021
Computer Science & Engineering, University of Minnesota
1
Announcements
• Project 1 to release today
• Topic: Creating processes using fork/exec/wait, according to a dependency
graph
• Objectives
• Brush up ‘C’ programming skills
• Use Makefile to build programs
• Setting up the project environment—use CSELabs machines
• Due: 10/07/2021
2
Last lecture
• Process: Abstraction of programs for OS virtualization • Creating a process (fork)
• Executing new programs (exec)
• Why do we use fork-exec to create a new process instead of from scratch?
• Waiting for a process (wait) • Termination
• Special processes
• Be aware of zombie process
3
This lecture
• Process states
• Effects of process states in applications
4
A motivating example
The following code will fork and run 10 processes of a program
for (int i=0; i < 10; ++i) { if (fork() == 0) {
execv("some/path", (char*)NULL);
}
}
// wait() omitted
5
A motivating example
Questions:
A single CPU with several cores
Process1 Process2 Process3 ... Process N
• Are these processes running truly simultaneously? • Is the running of processes “non-stop”?
6
Process States
Realizing time-sharing: Time quantums
• Quantum
• A short duration for CPU to execute a process • E.g., 100 ms as one quantum
• Why need quantum?
7
Realizing time-sharing: Time quantums
• Quantum
• A short duration for CPU to execute a process • E.g., 100 ms as one quantum
• Why need quantum?
• To realize time-sharing
7
Context switch
• Once a quantum expires, the process is stored away from the processor • Then, a new process comes to execute
• “Ready” queue
• OS maintains a list of all processes ready to be executed and schedules them based on some priority algorithm.
Quantum-based time sharing and context switching are the key mechanism for processes to share a single CPU.
8
The states of a process
A process can generally be described as existing in any one of following states:
• New/Start
• Ready
• Running
• Waiting/blocked • Terminated/done
9
State transition diagram
Taken from [1].
10
The new/start state
A process in the start state has been created (via fork) and is awaiting to be scheduled.
The scheduler will determine the priority of the process, which will determine when it gets to execute.
• The scheduling algorithms can be complicated
11
The ready state
• A process in the ready state is one which is ready to be executed. • It is not waiting on any resources from the OS such as:
• Network packets • Memory allocation • Concurrency locks • File I/O
• It needs to wait only for processes ahead of it in the queue to finish their quantums for executing
12
The running (executing) state
A process in the running state currently owns at least one processor and is executing its code.
A process will generally leave this state only when
• Its quantum expires
• Goes to the “ready” state
• It blocks when requesting resources that are not available in the current slide
• Goes to the “blocked” state
13
What happen specifically when switching running processes?
14
What happen specifically when switching running processes?
• Decide the switching
• The scheduler yields the CPU and selects the next process to be run
• A number of algorithms; to be covered in future lectures
• Save the state (context) of current process
• Get the pointer to new process descriptor(s)—PCB
• Locate and restore its saved state • Restore context
• Code, data, stack segments, program counter, etc. • Execute the new process
14
The blocked (waiting/sleep) state
A process in the blocked state has been removed from the processor and ready queue (list of ready processes)
• Due to its inability to immediately acquire some resource or perform some operation
• Resumed until the resources it needs become available
OK, your process is not running in this state
15
What can cause processes to be blocked?
16
What can cause processes to be blocked?
Example cases
• Data that has not yet been read in from disk • A message that has not yet been sent
• A lock that has not yet been released
• Too aggressive in using resources
Be aware of the causes to NOT enter the blocked state for better performance
17
The done (terminated) state
Once a process has finished, it is terminated and the OS reclaims its resources.
18
Effects of Process States in Applications
Performance implications
Transitioning into and out of the running state (context switch) can be detrimental to performance
• Due to context switches
• Remember what are happening here?
• Optimizations
• Minimizing the number of context switches
• Minimizing the time spent in the blocked state—improving throughput
19
Ways to help maximize throughput
• Resources such as locks should be released by processes as soon as possible
• To allow other processes to re-enter ready state
• Small granularity of locking
• Reduce I/O wait times. How?
20
Ways to help maximize throughput
• Resources such as locks should be released by processes as soon as possible
• To allow other processes to re-enter ready state
• Small granularity of locking
• Reduce I/O wait times. How?
E.g., less I/O requests and shorter I/O acquisition to reduce I/O contention, HDD->SSD
20
Recognizing state changes and improving performance
1. int main(int argc, char** argv) {
2. const int size = 50;
// Open input and output files.
3. int in = open(“input”, O_RDWR);
4. int out = open(“output”, O_RDWR);
// Copy one file into another.
<-- I/O request
<-- I/O request
5. char* buffer[size];
6. while (read(in, buffer, size) > 0) <-- I/O request
write(out, buffer size);
// Close the files.
7. close(in);
8. close(out);
9. }
<-- I/O request
<-- I/O request
<-- I/O request
21
Potential strategies for improvements
• Minimize I/O requests
• E.g., increase the read size
• Minimize locks
• E.g., specify read-only
• Minimize resource acquisition
• E.g., reserve only one file at a time
22
Improved code
int main(int argc, char** argv) {
// Get the file size for buffer.
struct stat fstat; stat("input", &fstat);
int fsize = fstat.st_size;
// Open input file as read-only.
int in = open(argv[1], O_RDONLY);
// Read file into large buffer.
char *buffer = malloc(fsize);
read(in, buffer, fsize);
<-- System Call
<-- I/O request
<-- I/O request
23
Improved code (contd.)
// Close input file.
close(in); <-- I/O request
// Open output file.
int out = open(argv[2], O_WRONLY); <-- I/O request // Write to file.
write(out, buffer, fsize);
// Close output file.
close(out);
free(buffer);
}
<-- I/O request
<-- I/O request
24
What have we improved?
• Open “input” with read-only
• Minimizing locks
• Read and write the whole file only once
• Minimizing I/O requests
• Separate the opening of files for read and write; immediately close files
• Minimizing resource acquisition
25
Come back to the motivating example
The following code will fork and run 10 processes of a program
for (int i=0; i < 10; ++i) { if (fork() == 0) {
execv("some/path", (char*)NULL);
}
}
Questions:
• Are these processes really running simultaneously? • Is the running of processes “non-stop”?
• How are they actually scheduled?
26
Summary on processes
• What a process is
• Purpose of PCB
• Creating, executing, waiting, and terminating a process • Special processes
• Process states
• Strategies for improving performance
27
Questions on processes
• What is the unit of execution and resource management in Unix? • How are those units implemented by the OS?
• What mechanism is involved in sharing a single CPU?
• For what reasons could a process become blocked?
• What is it called when two processes exchange a processor? • What does fork() return to a parent and child?
• Is the code, following a successful exec* call, going to run? • What is an orphan process?
28
More quizzes on Kahoot!
29
Next lecture
• Threads
• Reading: Robbins 2.2, 12.1
30
References
[1] http://www-users.cselabs.umn.edu/classes/Spring- 2018/csci4061/notes/processes.pdf [2] https://www.cs.ucr.edu/~csong/cs153/l/process2.pdf
31