Back

Let's talk about Operating system

Sat, Dec 08 201833 min read
Nathaniel

What is the difference between a process and a thread?

-Process (Process) is the basic unit of system resource allocation and scheduling, and thread (Thread) is the basic unit of CPU scheduling and dispatch; -Thread depends on the process to exist, a process has at least one thread; -Processes have their own independent address space, and threads share the address space of their own process; -A process is an independent unit that owns system resources, and the thread itself basically does not own system resources, only a few essential resources (such as a program counter, a set of registers and stacks) in operation, and share the process with other threads Related resources such as memory, I/O, cpu, etc.; -During process switching, it involves the setting of the saving environment of the entire current process CPU environment and the setting of the newly scheduled CPU environment. The thread switching only needs to save and set the contents of a small number of registers, and does not involve memory management. Operation, it can be seen that the overhead of process switching is much greater than the overhead of thread switching; -The communication between threads is more convenient. The threads in the same process share data such as global variables, and the communication between processes needs to be carried out in the way of inter-process communication (IPC); -As long as one thread crashes in a multi-threaded program, the entire program crashes, but the crash of one process in a multi-process program will not affect other processes, because the process has its own independent address space, so the multi-process is more robust
What data can be shared by threads in the same process?
Expand
-Process code segment -Process public data (global variables, static variables...) -File descriptor opened by the process -The current directory of the process -Signal processor/signal processing function: how to process the received signal -Process ID and Process Group ID
Which resources do threads exclusively occupy?
Expand
-Thread ID -The value of a set of registers -The thread's own stack (heap is shared) -Error return codes: threads may produce different error return codes, and the error return code of one thread should not be modified by other threads; -Signal mask/Signal mask: Indicates whether to shield/block the corresponding signal (except SIGKILL, SIGSTOP)

What are the ways of inter-process communication?

  1. Pipe
Expand
-The pipeline is half-duplex, and data can only flow in one direction; when two parties are required to communicate, two pipelines need to be established; -What a process writes to the pipe is read by the process at the other end of the pipe. The written content is added to the end of the pipeline buffer every time, and data is read from the head of the buffer every time; -Can only be used between parent and child processes or sibling processes (processes with kinship)
  1. Named pipes
  2. Message Queue
  3. Signal
  4. Shared memory
  5. Semaphore: initialization operation, P operation, V operation; P operation: semaphore -1, check whether it is less than 0, the process enters the blocking state; V operation: semaphore +1, if less than or equal to 0, Then wake up a waiting process from the queue and enter the ready state
  6. Socket

Process synchronization problem

Process synchronization is the purpose, and inter-process communication is a means to achieve process synchronization
Monitor
The monitor encapsulates the shared variables and the operations on these shared variables to form a functional module with a certain interface, so that the resources in the monitor can only be accessed through a certain process provided by the monitor. Processes can only use monitors mutually exclusive, and must release the monitors and wake up the processes in the entry waiting queue after use.
When a process tries to enter the monitor, it waits in the entry waiting queue. If the P process wakes up the Q process, the Q process is executed first, and P waits in the emergency waiting queue. (HOARE Management)
Wait operation: the process executing the wait operation enters the end of the condition variable chain, wakes up the process in the emergency waiting queue or the entry queue; signal operation: wakes up the process in the condition variable chain, enters the emergency waiting queue by itself, if the condition variable chain is empty, then Continue to execute. (HOARE Management)
MESA Management: Replace the signal in HOARE with notify (or broadcast to notify all those that meet the conditions), and notify instead of immediately exchanging the right to use the management. When appropriate, the first process in the conditional queue can be Enter, you must use while to check whether the conditions are appropriate before entering. Advantages: no additional process switching
Producer-consumer problem
Problem description: Use a buffer to store data, only the buffer is not full, the producer can write the data; only the buffer is not empty, the consumer can read the data
Code:
// Pseudo code description
// Define the semaphore, full record the number of items in the buffer, empty represents the number of vacancies in the buffer, mutex is a mutex
semaphore full = 0, empty = n, mutex = 1;
// Producer process
void producer(){
do{
P(empty);
P(mutex);
// Producer produces
To
V(mutex);
V(full);
} while(1);
}
void consumer(){
do{
P(full);
P(mutex);
// Consumers consume
V(mutex);
V(empty);
} while(1);
}
The philosopher’s meal problem
Problem description: There are five philosophers sitting around the dining table. Each philosopher either thinks or eats. In order to eat, the philosopher must pick up two pairs of chopsticks (at the left and right ends). Unfortunately, the number of chopsticks is equal to that of the philosophers, so each chopstick must be shared by two philosophers.
Code:
#define N 5 // number of philosopher
#define LEFT (i + N-1)%N // number of i's left neighbors
#define RIGHT (i + 1)%N // number of i's right neighbors
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N]; // array to keep track of everyone's state
semaphore mutex = 1; // mutual exclusion of critical region
semaphore s[N];
void philosopher(int i) {
while (TRUE) {
think();
take_forks(i);
eat();
put_forks(i);
}
}
void take_forks(int i) {
down(&mutex); // enter critical region
state[i] = HUNGRY; // record that i is hungry
test_forks(i); // try to acquire two forks
up(&mutex); // exit critical region
down(&s[i]); // block if forks are not acquired
}
void put_forks(int i) {
down(&mutex); // enter critical region
state[i] = THINKING; // record that has finished eating
test_forks(LEFT); // see if left neighbor can now eat
test_forks(RIGHT); // see if right neighbor can now eat
up(&mutex); // exit critical region
}
void test_forks(int i) {
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
state[i] = EATING;
up(&s[i]);
}
}
Reader-Writer Questions
The concept of critical section?
Expand
Program fragments that operate on critical resources (mutually exclusive resources/shared variables, which can only be used by one process at a time) in each process
The concept of synchronization and mutual exclusion?
Expand
-Synchronization: Due to the cooperation of multiple processes, the execution of the processes has a certain order. For example, a process needs a message provided by another process, and enters the blocking state before obtaining the message; -Mutual exclusion: Only one process can enter the critical section from multiple processes at the same time
What is the difference between concurrency, parallelism and asynchrony?
Expand
Concurrency: There are multiple programs running at the same time in a period of time, but in fact, only one program is running on the CPU at any one time, and the macroscopic concurrency is achieved through constant switching;
Multithreading: A piece of code that runs concurrently. Is a means of achieving asynchrony
Parallel (compared to serial): In a multi-CPU system, multiple programs are executed at the same time regardless of the macro or micro level
Asynchronous (compared to synchronous): Synchronization is sequential execution, and asynchronous is to continue to do your own thing while waiting for a certain resource

What kinds of states does the process have?

Process State
-Ready state: The process has obtained the required resources other than the processor, and is waiting for processor resources to be allocated -Running status: running with processor resources, the number of processes in this status is less than or equal to the number of CPUs -Blocking state: The process is waiting for a certain condition and cannot be executed until the condition is met Row

What are the process scheduling strategies?

  1. Batch Processing System:
First-come first-serverd (FCFS)
Dispatch in the order of request. Non-preemptive, low overhead, no starvation problems, and uncertain response time (maybe slow);
Bad for short processes, bad for IO-intensive processes.
shortest job first (SJF)
Schedule in the order of the shortest estimated running time. Non-preemptive, high throughput, high overhead, which may cause starvation problems;
Providing good response time for short processes is not good for long processes.
shortest remaining time next (SRTN)
Schedule in the order of remaining running time. (Preemptive version with shortest job first). High throughput, high overhead, and good response time;
It may lead to starvation problems, which is not good for the long process.
Highest Response Ratio Next (HRRN)
Response ratio = 1+ waiting time/processing time. At the same time, the length of the waiting time and the estimated length of execution time are considered, and the length of the process is well balanced. Non-preemptive, high throughput, high overhead, good response time, no starvation problem.
  1. Interactive System The interactive system has a large number of user interaction operations, and the goal of the scheduling algorithm in this system is to respond quickly.
Time slice rotation Round Robin
All ready processes are arranged in a queue according to the FCFS principle, and the processes that have used up the time slice are arranged at the end of the queue. Preemptive (when the time slice is used up), low overhead, no starvation problem, and good response time for short processes;
If the time slice is small, process switching is frequent and throughput is low; if the time slice is too long, real-time performance cannot be guaranteed.
Priority scheduling algorithm
Assign a priority to each process and schedule according to priority. In order to prevent low-priority processes from never waiting for scheduling, the priority of waiting processes can be increased over time.
Multilevel Feedback Queue Scheduling Algorithm Multilevel Feedback Queue
Set multiple ready queues 1, 2, 3..., the priority decreases, and the time slice increases. Only when the queue with higher priority is empty will the processes in the current queue be scheduled. If the process runs out of the time slice of the current queue, it will be moved to the next queue.
Preemptive (when the time slice is used up), the overhead may be large, which is beneficial to IO-type processes, and starvation problems may occur.
What is priority inversion? How to solve?
Expand
When a high-priority process waits for a resource occupied by a low-priority process, priority inversion occurs, that is, a process with a lower priority is executed before a process with a higher priority. Here is a detailed explanation of the problems caused by priority inversion: if a medium-priority process preempts a low-priority process, then the low-priority process cannot proceed normally at this time and releases the occupied resources later, resulting in High-priority tasks have been suspended until the middle-priority process is completed, the low-priority process can continue and subsequently release the occupied resources, and finally the high-priority process can be executed. The problem is that high-priority processes are scheduled after medium-priority processes.
Solution: -Priority ceiling: When a task applies for a resource, the priority of the task is raised to the highest priority among all tasks that can access this resource. This priority is called the priority ceiling of the resource. Simple and easy. -Priority inheritance: When task A applies for shared resource S, if S is being used by task C, by comparing the priority of task C with itself, if it is found that the priority of task C is lower than its own priority, then The priority of task C is raised to its own priority. After task C releases resource S, the original priority of task C is restored.

What is a zombie process?

After a child process ends, its parent process does not wait for it (call wait or waitpid), then the child process will become a zombie process. The zombie process is a dead process, but it has not really been destroyed. It has given up almost all memory space, does not have any executable code, and cannot be scheduled. It only reserves a position in the process table to record the process ID, termination status, and resource utilization information (CPU time, memory usage, etc.) of the process. Etc.) for the parent process to collect. In addition, the zombie process no longer occupies any memory space. This zombie process may remain in the system until the system restarts.
Harm: Occupy process ID, and the process ID that the system can use is limited; Occupy memory.
The following situations will not produce zombie processes: -The parent process of the process ends first. At the end of each process, the system will scan for the existence of child processes, and if so, use the Init process to take over, become the parent process of the process, and call wait to wait for its end. -The parent process calls wait or waitpid to wait for the end of the child process (you need to check whether the child process is over at regular intervals). The wait system call causes the parent process to suspend execution until one of its child processes ends. For waitpid, you can add the WNOHANG`'' (wait-no-hang) option. If the finished child process is not found, it will return immediately, and the process calling waitpid will not be blocked. At the same time, waitpid can also choose to wait for any child process (same as wait), wait for the child process of the specified pid, wait for any child process under the same process group, or wait for any child process whose group ID is equal to pid; -When the child process ends, the system will generate the SIGCHLD(signal-child) signal, you can register a signal processing function, call waitpid in this function, and wait for all finished child processes (note: generally need to loop Call waitpid, because before the signal processing function starts to execute, multiple child processes may have ended, and the signal processing function is executed only once, so it is necessary to recycle all the ended child processes to recycle); -You can also use signal(SIGCLD, SIG_IGN)(signal-ignore) to notify the kernel to ignore the SIGCHLD``` signal, then the kernel will recycle after the child process ends.
What is an orphan process?
Expand
A parent process has ended, but its child processes are still running, then these child processes will become orphan processes. Orphan processes will be taken over by Init (process ID is 1), and when these orphan processes are over, Init will complete the state collection work.

What are the ways to synchronize threads?

Why thread synchronization is needed: Threads sometimes share some resources with other threads, such as memory, database, etc. When multiple threads read and write the same shared resource at the same time, conflicts may occur. Therefore, thread synchronization is required, and multiple threads access resources in sequence.
-Mutexes Mutex: Mutex is a kernel object, and only the thread that owns the mutex has the authority to access the mutex resource. Because there is only one mutex object, it can be guaranteed that the mutex resource will not be accessed by multiple threads at the same time; the thread that currently owns the mutex object must hand over the mutex object after processing the task, so that other threads can access the resource; -Semaphore Semaphore: Semaphore is a kernel object, which allows multiple threads to access the same resource at the same time, but it is necessary to control the maximum number of threads that access this resource at the same time. The semaphore object saves the maximum resource count and current available resource count. Every time a thread accesses shared resources, the current available resource count is decremented by 1, as long as the current available resource count is greater than 0. Send the semaphore signal, if it is 0, put the thread into a queue to wait. After the thread finishes processing the shared resources, it should add 1 to the number of currently available resources through the ReleaseSemaphore function while leaving. If the value of the semaphore can only be 0 or 1, then the semaphore becomes a mutex; -Event Event: Allows a thread to actively wake up another thread to perform the task after processing a task. Events are divided into manual reset events and automatic reset events. After the manual reset event is set to the activated state, all waiting threads will be awakened and remain in the activated state until the program resets it to the unactivated state. After the automatic reset event is set to the excited state, it will wake up a waiting thread, and then automatically return to the uninitiated state. -Critical Section Critical Section: Only one thread is allowed to access critical resources at any time. The thread that owns the critical section object can access the critical resource, and other threads trying to access the resource will be suspended until the critical section object is released.
What is the difference between a mutex and a critical section?
Expand
Mutexes can be named and can be used for synchronization between different processes; critical regions can only be used for synchronization of threads in the same process. More resources are needed to create a mutex, so the advantage of a critical section is that it is fast and saves resources.

What is a coroutine?

The coroutine is a lightweight thread in the user mode, and the scheduling of the coroutine is completely controlled by the user. The coroutine has its own register context and stack. When the coroutine is scheduled to switch, save the register context and stack to other places. When switching back, restore the previously saved register context and stack. Directly operating the stack basically has no kernel switching overhead, and you can access global variables without locking. , So the context switching is very fast.
How many coroutines are compared with threads?
Expand
  1. A thread can have multiple coroutines, and a process can also have multiple coroutines alone, so that multi-core CPUs can be used in python.
  2. Thread processes are synchronous mechanisms, while coroutines are asynchronous
  3. The coroutine can retain the state of the last call, and each time the process is reentered, it is equivalent to entering the state of the last call

The exception control flow of the process: traps, interrupts, exceptions and signals

A trap is an "exception" caused by intentional, and is the result of executing an instruction. The traps are synchronized. The main function of the trap is to implement the system call. For example, the process can execute the syscall n instruction to request services from the kernel. When the process executes this instruction, it will interrupt the current control flow, trap to the kernel mode, and execute the corresponding system call. After the execution of the kernel processing program ends, it will return the result to the process and return to the user mode at the same time. The process now continues to execute the next instruction.
The interrupt is generated by the hardware external to the processor. It is not the result of executing a certain instruction, and it is impossible to predict when it will occur. Because the interrupt is independent of the currently executing program, the interrupt is an asynchronous event. Interrupts include I/O interrupts issued by I/O devices, clock interrupts caused by various timers, and debug interrupts caused by breakpoints set in the debugger.
An exception is an error condition that is the result of executing the current instruction, which may be corrected by the error handler, or the application may be terminated directly. The exception is synchronous. This specifically refers to the error conditions caused by the execution of the current instruction, such as division exception, page fault exception, etc. In order to distinguish between some books, this type of "abnormal" is also called "fault".
A signal is a higher software exception, which also interrupts the control flow of the process and can be handled by the process. A signal represents a message. The function of the signal is to notify the process that a certain system event has occurred.
For more details, please refer to: https://imageslr.github.io/2020/07/09/trap-interrupt-exception.html

What is IO multiplexing? How to achieve it?

IO multiplexing (IO Multiplexing) means that a single process/thread can handle multiple IO requests at the same time.
Implementation principle: The user adds the file descriptor (File Descriptor) he wants to monitor to the select/poll/epoll function, which is monitored by the kernel and the function is blocked. Once a file descriptor is ready (ready to read or write ready), or timeout (set timeout), the function will return, and then the process can perform corresponding read/write operations.
The difference between select/poll/epoll?
-select: Put the file descriptors into a collection, and when calling select, copy this collection from user space to kernel space (Disadvantage 1: Copy every time, high cost) , The content of the set is modified by the kernel according to the ready state. (Disadvantage 2) Set size is limited, the default is 1024 (64-bit: 2048) for 32-bit machines; horizontal trigger mechanism is adopted. After the select function returns, you need to traverse this collection to find the ready file descriptor (disadvantage 3: polling method is less efficient). When the file descriptor is When the number increases, the efficiency will decrease linearly; -poll: There is almost no difference from select. The difference is that the storage method of file descriptors is different. Pol is stored in a linked list, and there is no limitation on the maximum storage quantity; -epoll: The kernel and user space share memory to avoid the problem of continuous replication; the upper limit of the number of simultaneous connections supported is very high (about 1G of memory supports about 10W of connections); when the file descriptor is ready , The callback mechanism is used to avoid polling (the callback function adds the ready descriptors to a linked list, and when epoll_wait is executed, the linked list is returned); horizontal triggering and edge triggering are supported, when the edge triggering mechanism is adopted, only active descriptors Will trigger the callback function.
In summary, the main differences are: -The maximum number of connections that can be opened by a thread/process -File descriptor transfer method (copy or not) -Horizontal trigger or edge trigger -Efficiency when querying ready descriptors (whether to poll)
When do you use select/poll and when do you use epoll?
When the number of connections is large and there are many inactive connections, the efficiency of epoll is much higher than the other two; but when the number of connections is small and they are all very active, because epoll requires a lot of callbacks, the performance may be lower than others. Both.
What is a file descriptor?
The file descriptor is a non-negative integer in form. In fact, it is an index value that points to the record table of files opened by the process maintained by the kernel for each process. When the program opens an existing file or creates a new file, the kernel returns a file descriptor to the process.
The kernel accesses files through file descriptors. The file descriptor points to a file.
What is horizontal trigger? What is edge trigger?
Expand
-In the level trigger (LT, Level Trigger) mode, as long as a file descriptor is ready, a notification will be triggered. If the user program does not read and write the data at one time, it will be notified next time; -In Edge Trigger (ET, Edge Trigger) mode, when the descriptor is never ready to become ready, it will be notified once, and will not be notified again until it is never ready to become ready again (the buffer changes from unreadable/writeable to available). Read/write). -Difference: Edge triggering is more efficient, reducing the number of repeated triggers, and the function does not return a large number of file descriptors that may not be needed by the user program. -Why non-blocking (non-block) IO must be used for edge triggering: Avoid starvation of tasks processing other descriptors due to blocking read/blocking write operations of one descriptor.
What are the common IO models?
Expand
-Synchronous blocking IO (Blocking IO): After the user thread initiates an IO read/write operation, the thread blocks until it can start processing data; the utilization of CPU resources is not enough; -Synchronous non-blocking IO (Non-blocking IO): You can return immediately after initiating an IO request. If there is no ready data, you need to continuously initiate an IO request until the data is ready; repeated requests consume a lot of CPU resources; -IO multiplexing -Asynchronous IO (Asynchronous IO): After the user thread sends an IO request, the execution continues. The kernel reads the data and puts it in the buffer specified by the user. After the IO is completed, the user thread is notified to use it directly.

What is user mode and kernel mode?

In order to limit the access capabilities of different programs and prevent some programs from accessing the memory data of other programs, the CPU divides the user mode and kernel mode into two levels of authority.
-User mode can only access memory with limited access, and is not allowed to access peripheral devices. There is no ability to occupy the CPU, and CPU resources can be obtained by other programs; -Kernel mode can access all data and peripherals in the memory, and can also switch programs.
All user programs are running in user mode, but sometimes some kernel mode operations are required, such as reading data from the hard disk or keyboard. At this time, system calls are required, using trap instructions, the CPU switches to kernel mode and executes The corresponding service is switched to the user mode and the result of the system call is returned.
Why is it divided into user mode and kernel mode?
Expand
(My own opinion:)
-Security: Prevent user programs from maliciously or accidentally destroying system/memory/hardware resources; -Encapsulation: The user program does not need to implement lower-level code; -Facilitate scheduling: If multiple user programs are waiting for keyboard input, then scheduling is required; it is more convenient to dispatch to the operating system in a unified manner.
How to switch from user mode to kernel mode?
Expand
-System call: For example, read command line input. In essence, it is achieved through interrupts -When an exception occurs in the user program: such as page fault exception -Peripheral device interrupt: After the peripheral device completes the operation requested by the user, it will send an interrupt signal to the CPU, and then the CPU will transfer to the corresponding interrupt handler

What is a deadlock?

In two or more concurrent processes, each process holds a certain resource and waits for other processes to release the resources they currently hold. They cannot move forward until this state is changed. This group of processes is called Deadlock (deadlock).

Necessary conditions for deadlock?

-Mutual exclusion: a resource can only be used by one process at a time; -Own and wait: A process occupies at least one resource and is waiting for another resource occupied by other processes; -Non-preemptive: The resources that have been allocated to a process cannot be preempted forcibly, and can only be released voluntarily after the process completes the task; -Circular waiting: A circular waiting resource relationship is formed between several processes. Each process in the loop is waiting for the resources occupied by the next process.

What are the ways to deal with deadlock?

ostrich strategy
Ignore the deadlock directly. Because the cost of solving the deadlock problem is high, the ostrich strategy, which does not take mission measures, will achieve higher performance. When a deadlock occurs, it will not have much impact on the user, or the probability of a deadlock is very low, you can use the ostrich strategy.
Deadlock Prevention
The basic idea is to destroy the four necessary conditions for forming a deadlock: -Destruction of mutual exclusion conditions: Allow certain resources to be accessed by multiple processes at the same time. However, some resources themselves do not have this attribute, so the practicality of this scheme is limited; -Destroy possession and wait for conditions: -Implement the resource pre-allocation strategy (before a process starts running, it must apply to the system for all the resources it needs at once, otherwise it will not run); -Or only allow the process to apply for resources when it is not occupying resources (release the occupied resources before applying for resources); -Disadvantages: In many cases, it is impossible to predict all the resources required by a process; at the same time, it will reduce resource utilization and reduce the concurrency of the system; -Destruction of non-preemption conditions: Allow processes to forcibly preempt resources occupied by other processes. Will reduce system performance; -Breaking the cycle waiting condition: All resources are numbered uniformly, and all processes' requests for resources must be made in the order of increasing sequence number, that is, only resources with a smaller number can be applied for resources with a larger number. This avoids the process of occupying large resources to apply for small resources.
Deadlock avoidance
The resource allocation status is dynamically detected to ensure that the system is in a safe state, and resources are allocated only when it is in a safe state. The so-called safe state means that even if all processes suddenly request all the resources they need, there can be a certain order of resource allocation to the processes, so that each process runs to completion.
Banker's Algorithm
Deadlock removal
How to detect deadlock: detect whether there are loops in the directed graph; or use a detection algorithm similar to deadlock avoidance.
The method of deadlock release: -Use preemption: Suspend certain processes and seize its resources. But some processes should be prevented from being hungry for a long time; -Use rollback: Let some processes roll back to the point where the deadlock is resolved, and voluntarily release resources when the process rolls back. The system is required to maintain historical information of the process and set a restore point; -Use to kill the process: force to kill some processes until the deadlock is removed, you can proceed according to the priority.

What is the difference between paging and segmentation?

-Page storage: The user space is divided into equal parts called pages, and the memory space is divided into areas of the same size called page frames. The allocation is based on pages and is allocated according to the number of pages required by the process. Logically Adjacent pages may not be physically adjacent; -Segmented storage: user process address space is divided into several segments (such as code segment, data segment, stack segment) according to its own logical relationship, memory space is dynamically divided into areas with different lengths, and the allocation is based on segments , Each segment occupies a continuous space in the memory, and each segment can be non-adjacent; -Segment and page storage: User processes are divided by segments first, and then by pages within the segments, and memory is divided and allocated by pages.
the difference: -Different purposes: the purpose of paging is to manage memory and use it for virtual memory to obtain a larger address space; the purpose of segmentation is to meet the needs of users, so that programs and data can be divided into logically independent address spaces; -Different sizes: the size of the segment is not fixed, it is determined by the function it completes; the size of the page is fixed, it is determined by the system; -Address space dimensions are different: segment is a two-dimensional address space (segment number + offset within a segment), paging is a one-dimensional address space (one page table/multi-level page table for each process, and the corresponding can be found through a logical address Physical address); -Segmentation is convenient for information protection and sharing; paging sharing is restricted; -Fragmentation: Segmentation has no internal fragmentation, but will produce external fragmentation; paging has no external fragmentation, but will produce internal fragmentation (one page is not full)

What is virtual memory?

Each program has its own address space, this address space is divided into equal-sized pages, these pages are mapped to physical memory; but it is not necessary that all pages are in physical memory, when the program refers to pages that are not in physical memory At this time, the operating system loads the missing part into physical memory. In this way, for the program, logically there seems to be a lot of memory space, but actually part of it is stored on the disk, so it is called virtual memory.
The advantage of virtual memory is that the program can get more available memory.
The implementation of virtual memory, page tables/multi-level page tables, page fault interruption, and different page elimination algorithms: [Answer](https://imageslr.github.io/2020/07/08/tech-interview.html# virtual-memory).
How to map the address space to physical memory?
Expand
Memory Management Unit (MMU) manages the conversion between logical addresses and physical addresses. The page table (Page table) stores the mapping table of pages (logical addresses) and page frames (physical memory space). The page table It also contains valid bits (in memory or disk), access bits (whether it has been accessed), modified bits (whether the memory has been modified), and protection bits (read-only or read-write). Logical address: page number + page address (offset); each process has a page table, which is placed in the memory, and the starting address of the page table is in the PCB/register.

What are the page replacement algorithms?

When the program is running, if the page to be accessed is not in the memory, a page fault interrupt occurs and the page is loaded into the memory. If the memory has no free space at this time, the system must call a page from the memory to the disk to make room. The main goal of the page replacement algorithm is to minimize the frequency of page replacement (or the lowest page fault rate).
-Optimal replacement algorithmOPT (Optimal replacement algorithm): Replace pages that are not needed in the future or needed in the furthest future. It is a theoretical algorithm and an optimal strategy; -First-in-first-out FIFO: Replace the page that has been in memory for the longest time. Disadvantages: it is possible to swap out the pages that are frequently accessed, which will increase the page fault rate; -Second Chance Algorithm SCR: Press FIFO to select a page, if its access bit is 1, give a second chance and set the access location to 0; -Clock Algorithm Clock: In SCR, the page needs to be moved in the linked list (the page should be moved from the head of the linked list to the end of the linked list at the second chance). The clock algorithm uses a circular linked list, and then uses a pointer to point to the oldest Page, avoiding the overhead of moving the page; -NRU (Not Recently Used): Check the access bit R, modify the bit M, and replace R=M=0 first, followed by (R=0, M=1); -Least Recently Used Algorithm LRU (Least Recently Used): Replace the page with the longest unused time; Implementation method: Maintain a timestamp, or maintain a linked list of all pages. When a page is accessed, move the page to the head of the linked list. This will ensure that the page at the end of the linked list is the least visited recently. -Least frequently used algorithm**NFU: Replace the page with the least number of visits
Principle of Locality
-In terms of time: the most recently visited page will be visited in the near future; -Spatially : Pages surrounding the accessed page in memory are also likely to be accessed.
What is turbulence?
Thrashing essentially refers to frequent page scheduling behavior. A page must be replaced when the process is interrupted by a page fault. However, all other pages are in use, it replaces a page, but the page is needed again immediately. Therefore, page faults will continue to occur, leading to a sharp drop in the efficiency of the entire system. This phenomenon is called thrashing. Strategies to resolve memory thrashing include:
-Modify the page replacement algorithm; -Reduce the number of programs running at the same time; -Terminate the process or increase the physical memory capacity.

Buffer overflow problem

What is a buffer overflow? The C language uses a runtime stack to store process information. The information of each function is stored in a stack frame, including registers, local variables, parameters, return addresses, etc. C does not perform any boundary checking for array references, so write operations to array elements that are out of range will destroy the state information stored in the stack. This phenomenon is called buffer overflow. Buffer overflow can damage the program, and can also be used to attack the computer, such as using a pointer to the attack code to overwrite the return address.
How to prevent buffer overflow
There are three mechanisms to prevent buffer overflow attacks: randomization, stack protection, and limiting executable code area. -Randomization: Including stack randomization (a random-sized space is allocated on the stack at the beginning of the program) and address-space layout randomization (ASLR, which means different parts of the program each time it runs, including code segments) , Data segments, stacks, heaps, etc. will be loaded into different areas of the memory space), but it can only increase the difficulty of attacking a system and cannot completely guarantee security. -Stack protection: Store a randomly generated special value between the local variables of the stack frame of each function and the stack state, called the canary. Before restoring the register state and returning from the function, the program checks whether the canary value has been changed. If it is, the program terminates abnormally. -Restrict executable code area: There are three types of access to memory pages: readable, writable, and executable. Only the memory where the part of the code generated by the compiler is located is executable, and other pages are restricted to only allow reading and write.

Disk Scheduling

Process: head (find the corresponding disk surface); track (concentric rings on a disk surface, seek time); sector (rotation time). Scheduling algorithm to reduce seek time:
-First come first serve -The shortest seek time is prioritized -Elevator algorithm: The elevator always keeps running in one direction until there is no request for that direction, and then changes the running direction.

Comments(0)

Continue with
to comment