Process management

What are processes and threads?

  • Process is an independent unit of system resource allocation and scheduling, it can have its own address space; Processes are introduced to allow multiple programs to execute concurrently to improve system resource utilization and throughput.
  • Thread is an entity of process, is the basic unit of CPU scheduling, it is smaller than the process can run independently of a unit; Threads are introduced to reduce the overhead of programs in the process of concurrency and make OS concurrency more efficient.

What’s the difference?

  • Process is the smallest unit of resource allocation, thread is the smallest unit of scheduling;
  • A thread can only belong to one process, and a process can have multiple threads, but at least one thread;
  • Processes themselves retain resources, while threads contain only the resources necessary to maintain activities and do not own system resources.

Why is thread scheduling less expensive than process scheduling?

  • Since a process is the owner of a resource, the system must create or reclaim process control blocks, allocate or reclaim memory for it during the process of creating or canceling a process. During process switchover, the system must retain the CPU environment of the current process and then set the CPU environment of the newly selected process. Therefore, the scheduling of processes is relatively complex and takes a lot of processor time.
  • While threads have many of the characteristics of traditional processes, they do not hold resources themselves. In addition, because the resources in the same process are shared by all threads, threads can use these data to communicate more conveniently and quickly, thus reducing some system overhead. As a result, threads can schedule faster than processes, also known as “light processes”.

How many states does a process have?

  • Ready state: the process has obtained all the resources it needs except the processor and can execute immediately as soon as it obtains the processor. The state is called ready state
  • Running state: When a process has acquired a processor and its program is running on the processor, the state of the process is running
  • Blocked: An executing process that abandons the processor when it cannot execute because it is waiting for an event to occur. The blocking state can be caused by a variety of events, such as waiting for I/O to complete, requesting buffers that cannot be satisfied, waiting for signals, and so on

What are the ways in which threads are synchronized?

  • Mutex: Using the mutex mechanism, only the thread that owns the mutex can access the common resource. Because there is only one mutex, it is guaranteed that the common resource will not be accessed by multiple threads at the same time. But this can easily lead to deadlocks (
  • Semaphore: It allows multiple threads to access the same resource at the same time, but controls the maximum number of threads that can access the resource at the same time. A semaphore object is used when a counter is needed to limit the number of shared resources that can be used.
  • Event (signal) : through the way of notification operation to keep multi-thread synchronization, but also can easily achieve multi-thread priority comparison operation, that is, the event mechanism allows a thread after processing a task, the active awakening of another thread to execute the task.

What are the classic process synchronization problems?

  • Producer-consumer problems
    • A group of producer processes and a group of consumer processes share a buffer that is initially empty and of a certain size. Only when the buffer is not full can the producer process put messages into the buffer, otherwise it has to wait. The consumer process can retrieve messages from the buffer only if the buffer is not empty, otherwise it waits; Buffers can only be accessed by one process at a time.
    • Problem analysis: The producer and consumer processes have mutually exclusive access to the buffer, and the producer and consumer themselves have a synchronization relationship, that is, messages must be produced before they can be consumed. It is thus possible to set a mutex for access to the buffer and two semaphores, one to record the free buffer unit and one to record the full buffer unit, thus achieving synchronization between the producer and the consumer.
  • The problem of eating for philosophers
    • Problem description: There are five philosophers sitting on a round table, and a chopstick is placed between two philosophers. The philosopher can eat only when he picks up the left and right chopsticks at the same time, and put the chopsticks back to the original place after finishing the meal.
    • Problem analysis: in order to prevent philosophers from taking a chopstick deadlock, need to add certain restrictions.
    • Several solutions are as follows:
      • By limiting up to four philosophers to reaching for the chopsticks on the left at the same time, this would eventually ensure that at least one philosopher could eat and release the chopsticks he had used when he finished, thus allowing more philosophers to eat
      • The philosopher was allowed to eat with chopsticks only when both hands were available; The AND semaphore mechanism is used to solve the problem
  • The reader-writer problem
    • Problem description: Two concurrent processes, reader and writer, share one data. Multiple reader processes can access data at the same time, but the data access of the writer process is mutually exclusive with other processes
    • Problem analysis: Reader and writer mutually exclusive, writer and writer mutually exclusive, reader and reader share. Therefore, a mutex is needed to realize the mutual exclusion of the read-write process and the writer-write process. In addition, a counter is also needed to count the read-write thread to make the read synchronization and the read-write mutually exclusive.
    • Several solutions are as follows:
      • Readers first: But as long as there is a steady stream of readers, there is no resource for the writer, which tends to make the writer hungry
      • Read-write fairness: Readers and writers compete fairly for resources, but as long as there are already readers queued up before, the writer has to wait for all reader threads to end even if the resource is available
      • Writer First: While readers who have queued up before will have priority access to the resource, readers who have queued up after that will have to wait for the writer process to finish. As long as the writer is endless, the following readers will not have resources, easy to lead to the hunger of readers

What are the communication methods between processes?

  • Process communication refers to the exchange of information between processes. Therefore, the mutual exclusion and synchronization between processes using semaphores can be reduced to low-level communication due to the small amount of information exchanged.
  • The so-called advanced communication between processes means that users can use a group of communication commands provided by the operating system to transfer a large amount of data, while the operating system hides the implementation details of process communication, that is, the communication process is transparent to users.
  • Advanced communication mechanisms can be grouped into three broad categories:
    • Pipeline communication: Pipeline communication is a half duplex communication mode, data can only flow unidirectional between processes; The process that sends messages is called the write process, and the process that receives messages is called the read process. Pipes are mainly divided into ordinary pipes and named pipes. The difference between them is that ordinary pipes can only flow between processes that are related (such as parent-child processes), while named pipes allow unrelated processes to communicate.
    • Message buffering communication: Multiple independent processes can communicate with each other through message buffering. This communication is implemented with the message buffer as the intermediate mechanism. Both sides send and receive messages in the unit. In memory, message buffers are organized into queues, often called message queues; Once created, message queues can be shared by multiple threads.
    • Shared memory communication: Because message buffering consumes CPU for message replication, the OS provides a communication method that allows data exchange between processes directly, namely shared memory. It can directly map the shared memory page to the virtual address space of the process grid that communicates with each other without intermediate mechanism, so that multiple processes can directly access the same physical memory page, just as accessing their own private space. However, because the memory entity exists in the computer system, it can only be shared by the process in the same computer system, which is not convenient for network communication.

Processor scheduling and deadlocks

What are the process scheduling algorithms in the operating system?

  • First come, first served scheduling algorithm: the process that enters the queue first is selected each time
  • Short job first scheduling algorithm: each time selects a process with the shortest expected running time
  • High-priority scheduling algorithm:
    • Non-preemptive priority algorithm: once the processor is assigned to the process with the highest priority in the ready queue, the process will continue to execute until the execution is completed or the process voluntarily abandons the processor; This scheduling algorithm is mainly used in batch processing system, but also can be used in some real-time systems where the requirements of real-time are not strict.
    • Preemptive priority scheduling algorithm: it also assigns the processor to the current process with the highest priority. However, if a process with a higher priority appears during the execution, the execution of the current process will be stopped immediately and the processor will be re-assigned to the new process with the highest priority. It is usually used in the real-time system with strict requirements, as well as in the batch processing and time-sharing system with high performance requirements.

What is a deadlock?

A group of two or more concurrent processes is said to be deadlocked if each process holds a resource while waiting for the other processes to release a resource they currently hold, and cannot proceed until this state is changed. In simple terms, multiple processes block indefinitely and wait for each other.

What are the conditions under which a deadlock occurs?

There are four main conditions, if one of them is not true, deadlock will not occur:

  • Mutual exclusion: a resource can only be called by one process at a time
  • Request and hold conditions: when a process is blocked by a request for a resource, it holds on to the resource it has acquired
  • Inalienable conditions: Resources acquired by a process are not forcibly taken away until they are fully used
  • Loop waiting condition: a loop waiting relationship is formed between several processes

What are the basic ways to resolve deadlocks?

  • Prevent deadlocks:
    • One-time allocation of resources :(break request and hold condition)
    • Deprivable resource: Release occupied resources when new resources are not available for a process (breaking the inalienable condition)
    • Orderly allocation of resources: The system assigns a number to each type of resource, each process requests resources in ascending order, and releases resources in reverse (breaking loop waiting conditions)
  • Avoid deadlocks:
    • Banker algorithm: All kinds of resources from the perspective of the current state with the system residual amount examines each process to apply for a resource, find a all kinds of resources application is not greater than system process of remaining resources in P1, then resources allocated to it, assuming that P1 will return after finishing the work which possess all the resources, update the system resource state and remove remaining process in the list of P1, Then move on to the next process that meets the criteria. The banker (OS) is safe if a sequence is found that enables all clients (processes) to complete their work.
  • Detect deadlock:
    • Assign a unique number to each process and each resource
    • Set up a resource allocation table to record the relationship between each process and occupied resources
    • Set up a process representative to record the relationship between each process and the resource to be applied for
    • Check resource possession and request successively. If a loop occurs, a deadlock is caused
  • Undeadlock:
    • Exploit resources: Exploit resources from other processes in sufficient quantities to the deadlocked process to break the deadlock
    • Undo process: The simplest way to undo a process is to abort all deadlocked processes. A gentler approach is to undo the processes one by one in some order until sufficient resources are available to allow the deadlock state to be resolved

Memory management

What are the algorithms for dynamic continuous allocation?

Dynamic partition allocation, also known as variable partition allocation, is a method of dynamically planning memory partition. This method does not pre-partition memory, but dynamically creates partitions according to the size of the process when it is loaded into memory, and makes the size of the partition exactly fit the needs of the process. Therefore, the size and number of partitions in the system are variable. Dynamic continuous allocation mainly includes the following algorithms:

  • First adaptation algorithm: free partitions are linked in increasing address order. When allocating memory, search for the first free partition whose size meets the requirement in sequence
  • The best adaptive algorithm: the idle partition forms partition chain according to capacity increment, and finds the first idle partition that can meet the requirements
  • Worst adaptive algorithm: also known as maximum adaptive algorithm, idle partitions are linked in the order of decreasing capacity to find the first free partition that can meet the requirements, that is, to select the largest partition.

What is the difference between paging and segmented storage management?

  • Page is the physical unit of information, and paging is to realize discrete allocation to reduce the “fragment” of memory, improve the utilization rate of memory, so as to meet the needs of the system. A segment is a logical unit of information, which contains a group of relatively complete information and can better meet the needs of users.
  • The size of a page is fixed and determined by the system, while the length of a segment is not fixed, depending on the program written by the user.
  • Paging job address space is one-dimensional, that is, a single linear space, programmers only need to use a memory, can represent a segment of address; The segment address space is two-dimensional. When identifying an address, the programmer needs to give both the segment name and the segment address.

What is virtual memory?

If there is a program that requires more memory than the computer can actually provide, the program will not run because it cannot be loaded into memory. In order to solve this problem, the concept of virtual memory is extended.

  • Based on the principle of locality, when a program is loaded, only part of the program can be loaded into memory and the rest can be left outside. During program execution, when the accessed information is no longer in memory, the operating system calls the required part into memory and continues to execute the program. On the other hand, the operating system can swap out temporarily unused content into external memory to make room for information that will be called into memory.
  • In this way, it is as if the operating system has provided the user with a much larger storage capacity, called virtual storage.

What are the features of virtual storage?

  • Multiple: A job can be loaded into memory more than once. Repeatability is a property unique to virtual storage.
  • Commutativity: refers to the process of switching in and switching out during the operation of the job.
  • Virtuality: it logically expands the capacity of memory. Virtuality is the most important feature and the ultimate goal of virtual memory. It is based on multiplicity and commutation, which in turn are based on discrete distribution.

What are the common page replacement algorithms?

  • Optimal replacement algorithm: an algorithm that exists only in theory and prioritizes the longest future world pages that will not be accessed.
  • Fifo (first-in, first-out) algorithm: preferentially replace the earliest page to be called.
  • Most recently unused algorithm: An attempt at an optimal replacement algorithm that prioritizes the most recently unused pages. The algorithm entrusts each page with a access field, which is used to record the time t experienced by the last page to be visited till now, and the page with the largest t value is replaced each time. Substitution out. This is a better algorithm, but requires more hardware support, such as registers and stacks.
  • Clock algorithm: also known as the recently unused algorithm, is the latest and longest unused approximation algorithm; The algorithm sets an access bit for the page and links the page to a ring queue, where the stream will visit position 1 when the page is visited. When a page is swapped, if the current pointer points to a page with access bit 0, it is swapped, otherwise, it is swapped to 0, and then proceed to the next one until a page with access bit 0 is encountered.
  • Improved clock algorithm: add a modified bit on the basis of the clock algorithm, and make a comprehensive judgment according to the access bit and modified bit during the replacement. Preferentially replace pages with access bit 0 and change bit 0, actually pages with access bit 0 and change bit 1.

The rest can be sorted out if you want (‘ ω · ´)