“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Processes and threads

process

Processes are the basic unit of resource allocation.

Process Control Block (PCB) is a data structure in the core of the operating system, which mainly represents the Process state, including Process state, program counter, CPU register, CPU layout, memory management, accounting information, input and output state. PCBS are created when a process is created and destroyed when a process is destroyed.

Virtual address space

Each process has its own virtual address space. Converting a virtual address to a physical address requires searching the page table. Searching the page table is a slow process, so a Cache is usually used to Cache common address maps to speed up searching the page table. This Cache is the TLB (Transaction Lookaside Buffer).

Because each process has its own virtual address space, then obviously each process has its own page table, then when a process switch after the page table also need to switch, switch a page table TLB after failure, Cache invalidation results in the decrease of shooting, the virtual addresses into physical addresses will slow down, show is the program runs slower. Threads share process resources. Switching does not.

Process status

The state of a process changes as it executes. By state, we mean the current action of a process:

  • New: The process is being generated.
  • Runing: Executing.
  • Waiting: waiting for something to happen, such as for user input to complete. Called blocked.
  • Ready: Waiting for the CPU in a shift.
  • Terminated: Execution is complete.

thread

A thread is the smallest unit in which an operating system can schedule operations. In most cases, it is contained within a process and is the actual operational unit of the process. A thread is a single sequential flow of control in a process, and multiple threads can be concurrent in a process, each performing a different task in parallel.

Threads are the basic unit of independent scheduling and dispatch.

Multiple threads in the same process share all system resources in that process, such as virtual address space, file descriptors, signal processing, and so on. But multiple threads in the same process have their own call stacks, their own hosting environment, and their own thread local storage.

Thread state

  • To give birth to
  • Block (block)
  • Unblock
  • Finish

Classification of threads

In terms of the running space of a thread, it can be divided into user-level threads (ULT) and kernel-level threads (KLT).

Kernel-level threads: These threads depend on the kernel and are also called kernel-supported threads or lightweight processes. Threads, whether in user programs or in system processes, are created, destroyed, and switched by the kernel. For example, Intel I5-8250U has 4 cores and 8 threads, and the threads here are kernel-level threads.

User-level threads: They exist only at the user-level and are independent of the operating system core. Application process use thread library to complete its creation and management, the speed is relatively fast, the operating system kernel can not perceive the existence of user-level threads.

The difference between

Has the 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.

overhead

Since the system allocates and reclaims resources, such as memory space and I/O devices, 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 the saving of the current executing CPU environment and the setting of the new scheduling process CPU environment, while the thread switch only needs to save and set a small amount of register content, and the cost is very small.

communications

Threads can communicate by directly reading and writing data in the same Process, but inter-process Communication requires the help of IPC (inter-process Communication refers to some technologies or methods for transmitting data or signals between processes, such as files and shared memory locally and HTTP remotely). .

Switching process status

Note:

  • Only the ready state and the running state can be converted to each other; everything else is one-way. 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 changes 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.

Batch system

There is not much user action in batch systems, where throughput and turnaround times (from commit to termination) are guaranteed when scheduling algorithm targets.

First-come-first-serverd (FCFS)

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

It is good for long jobs, but bad 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. It is also not good for I/ O-intensive processes, which have to queue up again after each I/O operation.

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.

Shrotest Remaining Time Next (SRTN)

Preemptive scheduling algorithm, scheduling in order of the 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.

The author think

Similar to SJF, but unlike SRTN, which is FCFS in nature, SRTN preempts new jobs based on the time remaining. It should be FCFS+ new preemption based on the remaining time. It’s a more comprehensive algorithm.

Interactive systems

There are a lot of user interactions in interactive systems. The goal of scheduling algorithms in this system is to respond quickly.

Time slice rotation

All ready processes are arranged into a queue according to FCFS principles. During each scheduling, CPU time is allocated to the peer 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 opposite process.

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

  • Since process switching requires saving process information and loading new process information, if the time slice is too small, it will cause the process to switch too frequently and take too much time to switch between processes.
  • If the time slice is too long, real-time performance cannot be guaranteed.

The author think

Therefore, the choice of time slice is very important. It can be analyzed according to the time spent by all tasks to ensure that most tasks can respond in a timely manner and the CPU utilization is high. But the task is dynamic, and it is best to adjust the time slice dynamically at regular intervals.

Priority scheduling

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

To prevent low-priority processes from never waiting for a schedule, the priority of waiting processes can be increased over time.

The author think

It is reasonable to adjust the waiting time priority. But there must be a monitor or a strategy to determine whether the wait meets the requirement to reprioritize and consume additional resources.

Multistage feedback queue

A process executes 100 time slices. If the time slice rotation scheduling algorithm is adopted, it needs to swap 100 times.

Multi-stage queue time is for such processes that need 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 7 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.

The author think

Note that the priority of the previous process will be adjusted if the task scheduling algorithm based on priority has not been executed for a long time. This algorithm is relatively comprehensive, and it is generally selected.

Real-time systems

Real-time systems require a request time to be responded to within a certain 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

A critical region

Critical section objects can be used when multiple threads access an exclusive resource. The thread that owns the critical section can access the protected resource or code segment, and other threads that wish to access it are suspended until the critical section thread abandons the critical section.

Advantages: An easy way to ensure that only one thread can access data at a time.

Disadvantages: Can only be used to synchronize threads within a process, not multiple processes. (Threads share resources within a process, so mutual exclusion between processes requires a shared resource between processes.)

The mutex

Designed to coordinate common individual access to a shared resource. Mutex is similar to a critical section, but more complex than a critical section. There is only one mutex (shared between processes), and only the thread that owns the mutex has access to the resource.

Advantages: Using mutex not only enables safe sharing of resources between different threads of the same application, but also between threads of different applications.

Disadvantages: Mutex is namable, which means it can be used across processes, so creating a mutex requires more resources, so using critical sections for internal process use provides a speed advantage and reduces resource usage.

The author think

Process can be understood as a container of resources, thread is the execution unit, the essence of process synchronization is thread synchronization, but the environment is different (have different resources). Mutexes are like a progression of critical sections, but the key is the mutex, which is shared between processes. Shared mutex objects can be achieved within the same machine, such as shared kernel memory. For Java development, distributed lock is commonly used, which can be said to be dimensionally reduced.

A semaphore

A semaphore is a synchronization object used to hold a count between 0 and a specified maximum value. When a thread completes a wait for the semaaphore object, the value is reduced by one; When the thread completes a release of the Semaphore object, the count is incremented by one. Signaled from the object’s waiting state when the count reaches 0, the thread waits until the object becomes signaled. Signaled objects are signaled to be greater than 0. Signaled state = 0.

Usage: Designed to control a resource with a limited number of users. It allows multiple threads to access the same resource at the same time, but you need to limit the maximum number of threads that can access the resource at the same time. A mutex is a special case of a semaphore. It is a mutex when the maximum number of resources in the semaphore is 1.

Advantages: Suitable for Socket (Socket) program thread synchronization.

Disadvantages: The semaphore mechanism must have common memory and cannot be used in distributed operating systems, which is its greatest weakness.

PV operation

Counting semaphores have two kinds of operations, often called V(signal()) and P (wait()). The V operation increases the value of S and the P operation decreases it.

Operation mode:

  1. Class to give a non-negative integer value.
  2. When P (wait()) is executed, the value of signal S is reduced. A process attempting to enter a critical section needs to execute P (wait()). When the signal flag S is reduced to negative value, the process will be blocked and cannot continue; When S is not negative, the process is allowed to enter the critical section.
  3. When V (signal()) is executed, the value of S is incremented. To terminate a process that leaves a critical section, V (signal()) is executed. When S is not negative, other processes that were previously blocked will be allowed to enter the critical section.

The event

Used to notify the thread that something has happened, thus initiating the start of subsequent tasks.

Advantages: Event objects keep threads synchronized by notifying operations, and can implement thread synchronization operations in different processes.

Process of communication

Inter-process Communication (IPC) refers to technologies and methods for transmitting data or signals between at least two processes or threads.

A process is the smallest unit of resources allocated by a computer system (strictly speaking, threads). Each process is its own part of an independent shampoo resource, isolated from each other. Interprocess communication is created to enable different processes to access resources and coordinate their efforts. In general, two applications that use interprocess communication can be divided into client and server (see master-slave architecture), where the client process requests data and the server responds to the client’s data requests. Some applications themselves even the server is also the client, which is often seen in distributed computing. These processes can run on the same computer or on different computers connected to a network.

IPC is very important to the design process of microkernels and nano kernels. Microkernels reduce the amount of functionality provided by the kernel. These capabilities are then obtained by communicating with the server via IPC, which is a significant increase in the number of IPC’s compared to a normal macro kernel.

Reasons for using IPC:

  • Information sharing: Web servers that use interprocess communication to share Web files (web pages, etc.) and multimedia through web browsers
  • Acceleration: Wikipedia uses multiple servers that communicate via interprocess communication to accommodate user requests
  • modular
  • Separation of private rights

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.

FIFO

Also named pipes, removing restrictions that 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 customer-service applications, where A FIFO serves as a point of convergence, passing data between the customer process and the service process.

The message queue

Compared to FIFO, message queues have the following advantages:

  • Message queues can exist independently of the read-write process, avoiding the difficulties that can arise when synchronization pipes are opened and closed in FIFO.
  • The synchronization blocking problem in 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.

A semaphore

It is a counter that provides access to object data objects for multiple processes.

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 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 does not use files, but rather anonymous segments of memory.

The socket

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

signal

Signal is a complicated communication method, which can be sent to a process at any time without knowing the state of the process. Used for program termination, roll-out, timing, etc.

The author think

IPC was originally a concept within a single machine, with in-process communication evolving into a distributed architecture. The idea and strategy of a single machine also apply to distributed systems such as message queues.

reference

wikipedia

Process control block

thread

Communication between processes

Dispatch (computer)

Java concurrent programming – critical sections, mutex, semaphores

A semaphore

Signal…