Processes and threads

1.1, processes,

concept

  • Processes are the basic unit of resource allocation.
  • Process Control block (PCB) describes the basic information and running status of a process. The so-called create process and cancel process refer to the operation of PCB.

The following diagram shows four programs creating four processes that can execute concurrently.

1.2, thread

concept

  • Threads are the basic unit of independent scheduling
  • A process can have multiple threads that share process resources
  • QQ and browser are two processes. There are many threads in the browser process, such as HTTP request thread, time response thread, rendering thread and so on. The concurrent execution of threads makes the browser click a new link to initiate HTTP request, and the browser can also respond to other events of the user

1.3 the difference between,

  • 1. Owning resources: The basic unit of resource allocation for a process. However, threads do not own resources and can access resources belonging to the process
  • 2, scheduling: thread is the basic unit of independent scheduling, in the same process, thread switching will not cause process switching, from a process in the thread to another process in the thread, will cause process switching
  • 3. System overhead:
    • Since the system allocates or reclaims resources such as memory, IO devices, etc. to processes when they are created or destroyed, the overhead is much higher than when threads are created or destroyed
    • Similarly, the process switch involves saving the CPU environment of the current executing process and setting the CPU environment of the new scheduler process, while the thread switch only needs to save and set a small amount of register content with little overhead
  • 4. Communication: Threads can communicate by directly reading and writing data in the same Process, but inter-process Communication needs IPC (Inter-process Communication).

2. Switch the process status

  • Ready: Waiting to be scheduled
  • Running Status
  • Stuck: Waiting for a resource

Attention should be paid to the content:

  • Only the ready state and the running state can be converted to each other, the rest are one-way conversion. The process in the ready state can obtain CPU time by scheduling algorithm and turn to running state. A running process, on the other hand, will be ready to wait for the next schedule when the CPU time slice allocated to it runs out
  • A blocked state is a lack of resources needed to transition from a running state, but resources do not include CPU time, which transitions from a running state to a ready state

3. Process scheduling algorithm

Scheduling algorithms in different environments have different objectives, so it is necessary to discuss scheduling algorithms in different environments.

3.1 batch processing system

There is not much user action in batch systems where scheduling algorithms aim to ensure throughput and turnaround time (from commit to end time)

3.1.1 first come, first served (FCFS)

  • A non-preemptive scheduling algorithm that schedules requests in order
  • It’s good for long work, but bad for short work. Short jobs can be executed only after the previous long jobs are completed, and long jobs need to be executed for a long time. As a result, short jobs wait too long.

3.1.2 Short Work Gives priority to Shortest Job First (SJF)

  • Non-preemptive scheduling algorithms schedule in the order of the shortest estimated running time
  • Long operations may starve to death, waiting for short operations to finish. Because if short jobs keep coming, long jobs will never get scheduled.

3.1.3 Shortest Remaining Time Takes precedence over Other Time Next (SRTN)

  • A preemptive version of shortest job first, scheduling in order of remaining time.
  • When a new job arrives, its total running time is compared to the remaining time of the current process. If the new process takes less time, suspend the current process and run the new process. Otherwise, the new process waits

3.2 interactive system

In interactive systems with a large number of user interactions, the goal of scheduling algorithms is to respond quickly

3.2.1. Time slice flow

All ready processes are placed in a queue according to FCFS principles. During each scheduling, CPU time is allocated to the queue leader process, which can execute a time slice. When the time slice runs out, a clock interrupt is issued by a timer, and the scheduler stops the process and sends it to the end of the ready queue, continuing to allocate CPU time to the process at the head of the queue.

The efficiency of time slice rotation algorithm has a great relationship with the size of time slice:

  • Since process switching requires saving the process information and loading the new process information, if the time slice is too small, the process switching will be too frequent and too much time will be spent on process switching.
  • If the time slice is too long, real-time performance cannot be guaranteed.

3.2.2 Priority scheduling

  • Assign a priority to each process and schedule the process according to the priority
  • To prevent low-priority processes from never waiting for scheduling, you can increase the priority of waiting processes over time

3.2.3 Multi-level feedback queue

  • A process needs to execute 100 time slices. If the time slice rotation scheduling algorithm is used, it needs to swap 100 times.
  • Multi-stage queue for the process that needs to execute multiple time slices continuously, it sets up multiple queues, each queue time slice size is different, such as 1,2,4,8… . The process is moved to the next queue before it finishes executing on the first queue. In this way, the previous process only needs to swap seven times.
  • Each queue also has a different priority, with the highest priority at the top. Therefore, processes on the current queue can be scheduled only when there are no processes on the previous queue.
  • You can view this scheduling algorithm asTime slice rotation scheduling algorithmandPriority scheduling algorithmThe combination of

3.3. Real-time systems

  • Real-time systems require that a request be answered within a certain amount of time
  • It can be divided into hard real time and soft real time, the former must meet the absolute deadline, the latter can tolerate a certain timeout.

4. Process synchronization

4.1. Critical region

  • The section of code that accesses a critical resource is called a critical section
  • To have mutually exclusive access to critical resources, each process needs to be checked before entering a critical section
// entry section
// critical section;
// exit section
Copy the code

4.2. Synchronization and mutual exclusion

  • Synchronization: The direct constraint relationship between multiple processes due to cooperation, so that the processes have a certain sequence of execution relationship.
  • Mutually exclusive: Only one process can enter a critical section at a time.

4.3. Semaphore

  • A Semaphore is an integer variable on which you can perform down and up operations, the common p and V operations.
    • Down: If the semaphore is greater than 0, the operation -1 is performed. If the semaphore is 0, the process sleeps and waits for the semaphore to be greater than 0;
    • Up: +1 operation on the semaphore to wake up the sleep process to complete the down operation.
  • The down and up operations need to be designed as primitives, indivisible, and generally shielded from interrupts when performing these operations.
  • If the semaphore can only have a value of 0 or 1, it is a Mutex, with 0 indicating that the critical region is locked and 1 indicating that the critical region is unlocked.
typedef int semaphore;
semaphore mutex = 1;
void p1(){ down(&mutex); // Up (&mutex); } voidp2(){ down(&mutex); // Up (&mutex); }Copy the code

4.3.1 Using semaphores to implement producer-consumer problems

Use a buffer to store items, only if the buffer is not full can the producer put items; Consumers can take items only if the buffer is not empty.

Because the buffer is a critical resource, a mutex is used to control mutually exclusive access to the buffer.

To synchronize producer and consumer behavior, the number of items in the buffer needs to be recorded. Numbers can be counted using semaphores, which use two semaphores: empty to record the number of empty buffers, and full to record the number of full buffers. Where, empty semaphore is used in the producer process, when empty is not 0, the producer can put items; The full semaphore is used in the consumer process. When the full semaphore is not zero, the consumer can pick up the item.

Note: Buffers cannot be locked and then tested for semaphores. That is, we cannot execute down (mutex) before we execute down (empty). If you do this, you might have a situation where, after generating the pair of buffers and locking them, you execute down (Empty) and find empty = 0, and the producer falls asleep. The consumer cannot enter the critical section because the producer locks the buffer and the consumer cannot perform the up (empty) operation. Empty will always be 0, causing the producer to wait forever, the lock will not be released, and the consumer will wait forever.

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = 0;
semaphore full = N;

void producer() {while(true){
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
    
void consumer() {while(true){ down(&full); down(&mutex); int item = remove_item(); consumer_item(item); up(&mutex); up(&empty); }}Copy the code

4.4, monitor

Producer-consumer problems implemented using the semaphore mechanism require a lot of control from the client code, and the pipe separates the control code, which is not only less error-prone, but also makes it easier for the client code to call.

The C language does not support pipe procedures. The following example code uses a Pascal-like language to describe pipe procedures. The example code provides insert () and remove () methods that the client code uses to solve producer-consumer problems

monitor ProducerConsumer
    integer i;
    condition C;
    
    procedure insert(a);
    begin
    / /...
    end;
    
    procedure remove(a);
    begin
    / /...
    end;
end monitor;
Copy the code
  • One important feature of a pipe is that only one process can use a pipe at a time. A process cannot hold a pipe until it can no longer execute, or another process can never use the pipe.
  • The pipe introduces condition variables and related operations: wait () and signal () to implement synchronous operations. The condition variable’s wait () operation causes the calling process to block, leaving the pipe to be held by another process. The signal () operation is used to wake up a blocked process

Implement producer-consumer problems using pipe procedures

monitor ProducerConsumer
    condition full , empty;
    integer count := 0;
    condition c;
    
    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count +1;
        if count = 1 then signal(empty);' end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count -1 ; if count = N -1 then signal(full); end; end monitor; Procedure Producer begin while true do begin item = produce_item; ProducerConsumer.insert(item); end end; Procedure Consumer begin while true do begin item = ProducerConsumer. Remove; consume_item(item); end end;Copy the code

5. Classic synchronization problems

5.1. Eating for philosophers

Five philosophers stood around a round table, each with food in front of him. The philosopher’s life alternates between two activities: eating and thinking. When a philosopher eats, he should first pick up two chopsticks on his left and right, and only one chopstick.

The following is an incorrect solution: if all philosophers pick up the chopsticks on the left hand side at the same time, all philosophers wait for the other philosophers to finish eating and release their chopsticks, resulting in a deadlock

#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // Pick up the chopsticks on the left
        take((i+1)%N); // Pick up the chopsticks on the right
        eat();
        put(i);
        put((i+1)%N); }}Copy the code

To prevent deadlocks from occurring, two conditions need to be set:

  • You must pick up the left and right chopsticks at the same time;
  • Eating is allowed only if neither neighbor has eaten.
#define N 5
#define LEFT (i + N - 1) % N / / left neighbors
#define RIGHT (i + 1) % N    / / right neighbor
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // Keep track of each philosopher's status
semaphore mutex = 1;         // Critical sections are mutually exclusive. Critical sections are state arrays
semaphore s[N];              // One semaphore for each philosopher

void philosopher(int i) {
    while(TRUE) { think(i); take_two(i); eat(i); put_two(i); }}void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // You can only start eating when you are told otherwise you will be waiting forever
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // Try telling your neighbors that you can start eating when you've finished
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// Check if both neighbors are not eating, if so, up(&s[I]) so that down(&s[I]) can be notified and continue
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] ! = EATING && state[RIGHT] ! =EATING) { state[i] = EATING; up(&s[i]); }}Copy the code

5.2. Reader-writer problem

  • Multiple processes are allowed to read data at the same time, but read and write operations are not allowed at the same time.
  • Count counts the number of processes that are reading data. Count_mutex locks count. Data_mutex locks read/write data.
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader(a) {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // The first reader needs to lock the data to prevent the write process from accessing it
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex); up(&count_mutex); }}void writer(a) {
    while(TRUE) { down(&data_mutex); write(); up(&data_mutex); }}Copy the code

6. Process communication

Process synchronization is confused with process communication. The difference is:

  • Process synchronization: Controls the execution of multiple processes in a certain sequence
  • Process communication: Transfer of information between processes

Process communication is a means, while process synchronization is an end. In other words, in order to achieve the purpose of process synchronization, the process needs to communicate and transmit some information needed for process synchronization.

6.1, pipes,

The pipe is created by calling the pipe function, fd[0] for reading and fd[1] for writing

#include<unistd.h>
int pipe(int fd[2]);
Copy the code

It has the following limitations:

  • Supports only half duplex communication (one-way alternating transmission);
  • Can only be used in parent-child or sibling processes.

6.2, FIFO

Also named pipes, removing the restriction that pipes can only be used in parent-child processes

#include<sys/stat.h>
int mkfifo(const char *path , mode_t mode);
int mkfifoat(int fd , const char *path , mode_t mode);
Copy the code

FIFO is commonly used in client-server applications, where A FIFO serves as a point of convergence to transfer data between the client and server processes.

6.3. Message Queues

Compared to FIFO, message queues have the following advantages:

  • The message queue can exist independently of the reading and writing process, thus avoiding the difficulties that may arise when the FIFO pipe is opened and closed;
  • The synchronization blocking problem of FIFO is avoided, and the process does not need to provide its own synchronization method;
  • A reading process can optionally accept messages based on the message type, rather than accepting them by default like a FIFO

6.4. Semaphore

It is a counter used to provide multiple processes with access to a shared data object

6.5 Shared Storage

  • Allows multiple processes to share a given storage area. Because data does not need to be copied between processes, this is the fastest IPC.
  • Semaphores are needed to synchronize access to shared storage.
  • Multiple processes can map the same file to their address space to achieve shared memory. In addition, XSI shared memory uses anonymous segments of memory instead of files

6.6. Sockets

Unlike other communication mechanisms, it can communicate with processes between different machines.