Processes and Threads
After equipped with how the kernel is booted in the previous article, we're gonna see two of the most important concepts in operating systems - Processes and Threads.
Process
Process is rarely a unfamiliar concepts for those who use computer every day. When you open the task manager in Windows, you will see how many processes is running, how many RAM they're using, and so are the CPU usage. However, only a few people could pin point the exact meaning of process and its difference to another concept - program.
Process and Program
An executable program is a static concept, to be specific, a set of meaningful source code after being compiled, assembled, linked and eventually loaded into executable file is just a piece of binary record lying in the hard disk drive. While a process of a program is a rather dynamic concept. A process is a running instance (entity) of its corresponding program in the main memory. For example, when we double click the Notepad in Windows or just type the 'ssh' command in Unix, the operating system load the program from hard disk drive into main memory; then do some initialization for the memory address space and flags (in Linux, the fork() system call is used to create a process, copying the address space from the father process), then keeps the fetch-decode-execute loop (in Linux, the execve() system call is invoked to set up the new address space, registers, stack pointers, flags and then grab and execute instructions), which was a runtime status of that program; And we call that a process. A program could have multiple processes when running.
State of Process
There're roughly three states of a process: running, ready and blocked. There's a finite state machine model of the three states:
1 When a process is created, typically, it goes to ready status. And it's gonna be inserted into ready task queue unless it's with a very high priority.
2 When a process with ready status in the ready task queue is brought into the front and about to execute, it goes to running state.
3 When a process is in running status, and its time share is exausted or it's chosen to be the victim to give up CPU usage, it goes to ready status and is inserted into task queue waiting for the next time share.
4 When a process is in running status, and it's waiting for input or it's waiting for data transfer between memory and hard disk. We could say it was blocked by the I/O. Thus this process will go to blocked status.
5 When a process is in blocked status, which means it might be waiting for input, and the input is ready, it'll goto ready status and being inserted to the end of ready task queue.
Process Control Block
As I just said above, a process has it's own memory address space and has its code and data need to be executed. A data structure lays in memory keeps the status, identification info and control info of a process call a Process Control Block.
Remembering the first article in this category, modern OSes is like a virtual machine that different users could use the same system at the same time as if they were the only user of this machine thanks to multi-processes and virtual memory. Because each process has a quota of CPU usage so every one get a share. The switching time is so small that nobody could sense it. For virtual memory, I'm gonna talk about it in the next several articles.
A process is just a running entity has its own memory address space, code and data. Thus, the corresponding process control block contains the following information: (referenced from Wikipedia)
The process scheduling state:, e.g. in terms of "ready", "suspended", etc., and other scheduling information as well, like a priority value, the amount of time elapsed since the process gained control of the CPU or since it was suspended. Also, in case of a suspended process, event identification data must be recorded for the event the process is waiting for.
Process structuring information: process's children id's, or the id's of other processes related to the current one in some functional way, which may be represented as a queue, a ring or other data structures.
Interprocess communication information: various flags, signals and messages associated with the communication among independent processes may be stored in the PCB.
Process privileges: in terms of allowed/disallowed access to system resources.
Process state: State may enter into new, ready, running, waiting, dead depending on CPU scheduling.
Process No: a unique identification number for each process in the operating system.
Program Counter: a pointer to the address of the next instruction to be executed for this process.
CPU registers: indicates various register set of CPU where process need to be stored for execution for running state.
CPU scheduling information: indicates the information of a process with which it uses the CPU time through scheduling.
Memory management information: includes the information of page table, memory limits, Segment table depending on memory used by the operating system.
Accounting information: includes the amount of CPU used for process execution, time limits, execution ID etc.
IO status information: includes a list of I/O devices allocated to the process.
Thread
A thread, like a process, is also an executing context, or an sequence of programmed instructions. But the granularity of thread is more fined than process. The implementation of threads and processes differs between operating systems, but in most cases a thread is a component of a process. Multiple threads can exist within one process, executing concurrently and sharing resources such as memory, while different processes do not share these resources. In particular, the threads of a process share its executable code and the values of its variables at any given time.
As the picture illustrated above, the left one is one process only have one thread, thus the code in this process could only be executed in serial, while the right one shows the same process could be divided into three threads that has their own registers and stack, and could be executed in parallel. Intel x86 processor has a technology called hyper-threading, which allows one physical core be divided into two or more seperate cores that has seperate register files, can be individually halted, interrupted, and could let different threads running at the same time.
Kernel-level Thread
Kernel-level Thread means this kind of threads are totally scheduled and managed by kernel, which means when do context switch between kernel threads, trapping into kernel is needed. The advantage of kernel-level threads is that in a multi-core machine or with hyper-threading, kernel-level threads could run in parallel, taking full advantage of CPU resource. The disadvantage of kernel-level threads is that context switch overhead between kernel-level threads are quite considerable compared with that between user-level threads, because each context switch need to go in kernel mode for scheduling.
User-level Thread
User-level Threads means this kind of threads are scheduled and managed in user space, which means the context switch only happens in user space. One thing need to be pointed out is that user-level threads also require system call to operate. The advantage of user-level threads is that context switch overhead is less than that of kernel-level thread. The disadvantage of user-level threads is pure level-threads (N-to-1 Thread Model) could not run in parallel, which means CPU resouce are not fully used.
Threads Models
N-to-1 Model: There're N user-level threads in one process but the kernel is only aware of a single thread of the process owning these threads. That means at one time, only one user-level thread could run, the kernel is not going to be able to distribute the other threads on other CPUs if the system has more than one. Further more, if the currently running thread is blocked for input then all other threads are blocked.
1-to-1 Model: There're N kernel-level threads in one process, and some (the maximum kernel threads that CPU supports) could be executed in parallel in optimal. If one of them are blocked by interrupt or I/O operation, others' not gonna be affacted.
N-to-M Model: This model combines the advantages of both user-level thread and kernel-level thread. And this is the most difficult one to implement. One method to implement it is to set all kernel threads as a thread pool, and grab user-level threads to run once there's an idle kernel-level thread. I used to implement this model of thread library. I'm gonna writing a detailed article on my thread library. The source code you could find in my Github.
Difference between Process and Thread
The granularity are different. Typically, for a simple program, its process may contain all of the codes and data. However, it could be divided into several threads, and each threads has its own codes but shared data, and be able to be executed in parallel.
Memory Address Space are different between different processes, while threads in the same process share the same address space.
Communicate overhead between processes is quite high because they're in different memory address space, we could use pipe, setting shared memory or use message queue to do IPC (Inter-Process Communication). Since different threads in the same process share the same address space, even if they have different runtime stack, it's much easier and light-weight to communicate.
Inter-Process Communication
As it said above, different processes have different memory address space. Thus, to communicate between different process, we need some new approaches: (reference from wikipedia)
The process scheduling state:, e.g. in terms of "ready", "suspended", etc., and other scheduling information as well, like a priority value, the amount of time elapsed since the process gained control of the CPU or since it was suspended. Also, in case of a suspended process, event identification data must be recorded for the event the process is waiting for.
Process structuring information: process's children id's, or the id's of other processes related to the current one in some functional way, which may be represented as a queue, a ring or other data structures.
Interprocess communication information: various flags, signals and messages associated with the communication among independent processes may be stored in the PCB.
File: A record stored on disk, or a record synthesized on demand by a file server, which can be accessed by multiple processes.
Socket: A data stream sent over a network interface, either to a different process on the same computer or to another computer on the network. Typically byte-oriented, sockets rarely preserve message boundaries. Data written through a socket requires formatting to preserve message boundaries.
Message Queue: A data stream similar to a socket, but which usually preserves message boundaries. Typically implemented by the operating system, they allow multiple processes to read and write to the message queue without being directly connected to each other.
Pipe: A unidirectional data channel. Data written to the write end of the pipe is buffered by the operating system until it is read from the read end of the pipe. Two-way data streams between processes can be achieved by creating two pipes utilizing standard input and output.
Named pipe: A pipe implemented through a file on the file system instead of standard input and output. Multiple processes can read and write to the file as a buffer for IPC data.
Shared memory: Multiple processes are given access to the same block of memory (virtual addresses in different address space mapped to the same physical address) which creates a shared buffer for the processes to communicate with each other.