Computer operating system – Process management

Computer operating system – Process management
- Processes and threads
  - Process of 1.
  - Thread 2.
  - 3. The difference between
- Switching process status
- Process scheduling algorithm
  - 1. Batch system
  - Interactive systems
  - 3. Real-time systems
- Process synchronization
  - 1. The critical region
  - 2. Synchronization and mutual exclusion
  - 3. The semaphore
  - 4. Monitor
- Classical synchronization problem
  - 1. Philosophers eat
  - 2. Reader-writer problem
- Process of communication
  - 1. The pipe
  - 2. FIFO
  - 3. Message queues
  - 4. The semaphore
  - 5. Share storage
  - 6. The socket

Processes and threads

Process of 1.

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 figure shows four programs creating four processes that can execute concurrently.

Thread 2.

Threads are the basic unit of independent scheduling.

There can be multiple threads in a process that share process resources.

QQ and browser are two processes. There are many threads in the browser process, such as HTTP request thread, event response thread, rendering thread and so on. The concurrent execution of threads makes it possible for the browser to respond to other events of the user when clicking a new link in the browser to initiate an HTTP request.

3. The difference between

ⅰ Owning Resources

The process is the basic unit of resource allocation, but the thread does not own the resources. The thread can access the resources belonging to the process.

Ⅱ scheduling

Thread is the basic unit of independent scheduling. In the same process, thread switching does not cause process switching, but when thread switching from one process to another process, process switching will cause.

ⅲ System Overhead

Since resources, such as memory space and I/O devices, are allocated or reclaimed by the system when a process is created or destroyed, the overhead is much higher than when a thread is created or destroyed. Similarly, the process switch involves the saving of the CPU environment of the current executing process and the setting of the CPU environment of the new scheduling process, while the thread switch only needs to save and set a small amount of register content, and the cost is very small.

ⅳ Communication

Threads can communicate with each other by reading and writing data directly from the same process, but process communication requires IPC.

Switching process status

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

The following should be noted:

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, becomes ready for the next schedule when its allocated CPU time slice is used up.
A blocked state is a lack of resources needed to transition from a running state, but this resource does not include CPU time, which transitions from a running state to a ready state.

Process scheduling algorithm

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

1. Batch system

In batch systems, where there is not much user action, the scheduling algorithm is aimed at ensuring throughput and turnaround time (from commit to termination).

1.1 First-come first-serverD (FCFS)

A non-preemptive scheduling algorithm that schedules requests in order.

It is good for long jobs, but not good for short jobs, because short jobs must wait for the completion of long jobs before they can be executed, while long jobs need to be executed for a long time, resulting in a long waiting time for short jobs.

1.2 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.

1.3 Shortest Remaining Time First (SRTN)

A preemptive version of shortest job first that schedules in order of remaining running 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.

Interactive systems

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

2.1 Time slice rotation

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 while continuing to allocate CPU time to the process at the head of the queue.

The efficiency of time slice rotation algorithm is closely related to the size of time slice:

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

2.2 Priority scheduling

Assign a priority to each process and schedule according to the priority.

To prevent low-priority processes from never waiting for scheduling, you can increase the priority of waiting processes over time.

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 is considered for the process that needs to execute multiple time slices continuously. It sets up multiple queues, each queue time slice size is different, for example, 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.

This scheduling algorithm can be regarded as the combination of time slice rotation scheduling algorithm and priority scheduling algorithm.

3. Real-time systems

Real-time systems require a response to a request 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.

Process synchronization

1. The 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

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.

3. The 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: Perform the +1 operation on the semaphore to wake up the sleeping process to complete the down operation.

The down and UP operations need to be designed as primitives and indivisible, and it is common practice to mask interrupts while performing these operations.

If the semaphore can only be 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(a) {
    down(&mutex);
    / / critical region
    up(&mutex);
}

void P2(a) {
    down(&mutex);
    / / critical region
    up(&mutex);
}
Copy the code

Implementing producer-consumer problems using semaphores

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 that you cannot first lock the buffer and then test the semaphore. That is, you cannot execute down(mutex) and then down(empty). If you do this, you might have a situation where the producer locks the buffer, executes down(Empty), finds 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, which is always zero, causing the producer to wait forever, never releasing the lock, and thus the consumer to wait forever.

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

void producer(a) {
    while(TRUE) {
        intitem = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); }}void consumer(a) {
    while(TRUE) {
        down(&full);
        down(&mutex);
        intitem = remove_item(); consume_item(item); up(&mutex); up(&empty); }}Copy the code

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, and the following example code uses a Pascal-like language to describe pipe procedures. The sample code’s pipe provides insert() and remove() methods, which the client code calls to solve the producer-consumer problem.

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. Performing wait() on a condition variable causes the calling process to block, leaving the pipe to be held by another process. The signal() operation is used to wake up blocked processes.

Implement producer-consumer problems using pipe procedures

/ / monitor
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;

// Producer client
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// Consumer client
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;
Copy the code

Classical synchronization problem

The problem of producers and consumers has already been discussed.

1. Philosophers eat

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 at a time.

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, you can set two conditions:

Two chopsticks must be picked up 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

2. Reader-writer problem

Multiple processes are allowed to read data at the same time, but read and write operations and write and write operations are not allowed.

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

The following content is provided by @bandi Yugandhar.

The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).

int readcount, writecount;                   //(initial value = 0)
semaphore rmutex, wmutex, readLock, resource; //(initial value = 1)

//READER
void reader(a) {
<ENTRY Section>
 down(&readLock);                 // reader is trying to enter
 down(&rmutex);                  // lock to increase readcount
  readcount++;                 
  if (readcount == 1)          
   down(&resource);              //if you are the first reader then lock the resource
 up(&rmutex);                  //release for other readers
 up(&readLock);                 //Done with trying to access the resource

<CRITICAL Section>
//reading is performed

<EXIT Section>
 down(&rmutex);                  //reserve exit section - avoids race condition with readers
 readcount--;                       //indicate you're leaving
  if (readcount == 0)          //checks if you are last reader leaving
   up(&resource);              //if last, you must release the locked resource
 up(&rmutex);                  //release exit section for other readers
}

//WRITER
void writer(a) {
  <ENTRY Section>
  down(&wmutex);                  //reserve entry section for writers - avoids race conditions
  writecount++;                //report yourself as a writer entering
  if (writecount == 1)         //checks if you're first writer
   down(&readLock);               //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
  up(&wmutex);                  //release entry section

<CRITICAL Section>
 down(&resource);                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
  //writing is performed
 up(&resource);                //release file

<EXIT Section>
  down(&wmutex);                  //reserve exit section
  writecount--;                //indicate you're leaving
  if (writecount == 0)         //checks if you're the last writer
   up(&readLock);               //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
  up(&wmutex);                  //release exit section
}
Copy the code

We can observe that every reader is forced to acquire ReadLock. On the otherhand, Writers don’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.

From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

int readCount;                  // init to 0; number of readers currently accessing resource

// all semaphores initialised to 1
Semaphore resourceAccess;       // controls access (read/write) to the resource
Semaphore readCountAccess;      // for syncing changes to shared variable readCount
Semaphore serviceQueue;         // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

void writer()
{ 
    down(&serviceQueue);           // wait in line to be servicexs
    // <ENTER>
    down(&resourceAccess);         // request exclusive access to resource
    // </ENTER>
    up(&serviceQueue);           // let next in line be serviced

    // <WRITE>
    writeResource();            // writing is performed
    // </WRITE>

    // <EXIT>
    up(&resourceAccess);         // release resource access for next reader/writer
    // </EXIT>
}

void reader()
{ 
    down(&serviceQueue);           // wait in line to be serviced
    down(&readCountAccess);        // request exclusive access to readCount
    // <ENTER>
    if (readCount == 0)         // if there are no readers already reading:
        down(&resourceAccess);     // request resource access for readers (writers blocked)
    readCount++;                // update count of active readers
    // </ENTER>
    up(&serviceQueue);           // let next in line be serviced
    up(&readCountAccess);        // release access to readCount

    // <READ>
    readResource();             // reading is performed
    // </READ>

    down(&readCountAccess);        // request exclusive access to readCount
    // <EXIT>
    readCount--;                // update count of active readers
    if (readCount == 0)         // if there are no readers left:
        up(&resourceAccess);     // release resource access for all
    // </EXIT>
    up(&readCountAccess);        // release access to readCount
}

Copy the code

Process of communication

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

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

Process communication is a means and 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.

1. The pipe

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.

2. FIFO

Also known as named pipes, removes 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, passing data between the client process and the server process.

3. Message queues

Compared to FIFO, message queues have the following advantages:

The message queue can exist independently of the read-write process, thus avoiding the difficulties that may arise when the synchronization pipe is opened and closed in FIFO.
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 receive messages based on the message type, unlike a FIFO, which can only receive messages by default.

4. The semaphore

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

5. Share storage

Allows multiple processes to share a given storage area. Because data does not need to be copied between processes, this is the fastest type of 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. The socket

Unlike other communication mechanisms, it can be used for process communication between different machines.

Computer operating system – Process management

Computer operating system – Process management

Processes and threads

Process of 1.

Thread 2.

3. The difference between

Switching process status

Process scheduling algorithm

1. Batch system

Interactive systems

3. Real-time systems

Process synchronization

1. The critical region

2. Synchronization and mutual exclusion

3. The semaphore

4. Monitor

Classical synchronization problem

1. Philosophers eat

2. Reader-writer problem

Process of communication

1. The pipe

2. FIFO

3. Message queues

4. The semaphore

5. Share storage

6. The socket

Related Posts

Quick Learn Go Notes (1) : Getting started

ConcurrentHashMap source code analysis

Mybatis Generator automatic code generation