Explain what an operating system is

The operating system is the most important software running on the computer. It manages the resources and processes of the computer as well as all the hardware and software. It provides an intermediate layer between computer hardware and software

Typically, there are many applications running on the computer that need to interact with the memory and CPU, and the purpose of the operating system is to ensure that these accesses and interactions are accurate.

What is the main purpose of an operating system

An operating system is a piece of software that serves three main purposes

  • Manages computer resources, including CPU, memory, disk drives, printers, and so on.
  • Provide a graphical interface, as we described earlier, that provides a bridge between the user and the computer.
  • Providing services to other software, the operating system interacts with the software in order to allocate any necessary resources to it to run.

What are the types of operating systems

The operating system is usually pre-installed before you buy the computer. Most users will use the default operating system, but you can upgrade or even change the operating system. But there are only three common operating systems: Windows, macOS, and Linux.

Operating system architecture

Monomer system

In most systems, the entire system runs as a single program in kernel mode. The entire operating system is written as a collection of programs, linked together to form a large binary executable program, this system is called a monolithic system.

When the actual object program is constructed in a singleton system, all the individual procedures (or files containing them) are first compiled and then bound together into an executable using the system linker

In a singleton system, there is a service to secure and run each system call. A set of utilities is required to compensate for the functionality required by the service, such as fetching data from the user program. Processes can be divided into a three-tier model

Many operating systems support additional extensions in addition to the core operating system that is loaded when the computer is first booted up. Such as I/O device drivers and file systems. These parts can be loaded on demand. They are called shared libraries in UNIX and Dynamic Link Libraries (DLLS) in Windows. Their extension is.dll, and there are more than 1000 DLL files in C:\Windows\ System32, so don’t delete the FILES on drive C easily, or they might explode.

Layered system

Layered systems use layers to separate different functional units. Each layer communicates only with the upper and lower layers of that layer. Each layer uses the layer below to perform its functions. Communication between layers is via predefined fixed interfaces.

The microkernel

To achieve high reliability, it is necessary to divide the operating system into small, hierarchical modules, with only one module – the microkernel – running in kernel mode and the rest running as normal user processes. Because each device driver and file system is treated separately as a normal user process, errors in these modules can crash the modules, but not the entire system.

MINIX 3 is a masterpiece of the microkernel, and its structure is as follows

Outside the kernel, the system is constructed with three layers, all of which run in user mode, with the device driver at the bottom. Because they run in user mode, they cannot physically access the I/O port space or issue I/O commands directly. Instead, to be able to program the I/O device, the driver completes a call by building a structure that specifies which parameter values are written to which I/O port and claiming a kernel call.

Client-server mode

The microkernel strategy is to divide processes into two types: servers, each used to provide services; Clients, using these services. This pattern is called the client-server pattern.

Client-server mode will have two carriers, one case is a computer is both client and server, in this way, the operating system will have some optimization; But it is common for the client and server to be on different machines, connected over a local area network or wan.

The client communicates with the server by sending messages that the client does not need to know whether the messages are being processed on the local machine or sent over the network to a remote machine. For the client, both situations are the same: you send a request and get a response.

What is on-demand paging

In an operating system, processes are loaded into memory on a page basis, and on-demand paging is a virtual memory management approach. In systems that use request paging, the operating system copies disk pages into memory only if a page miss exception occurs when an attempt is made to access the disk where the page is located and the page is not already in memory.

Advantages of multiprocessing systems

With the increasing of processors, our computer system has changed from a single system to a multi-processing system. The throughput of multi-processing system is relatively high. Multi-processing system has multiple parallel processors, which share clock, memory, bus, peripheral equipment and so on.

Multiprocessing systems can save money by sharing resources. The reliability of the whole system is also improved.

What is the kernel

In computers, the kernel is a computer program that is the core of the operating system and controls everything in the operating system. The kernel is usually the first program loaded before the Boot Loader loads the program.

Here also need to understand what is the boot loader.

A boot loader, also known as a boot loader, is a program that puts the computer’s operating system into memory. When the power is turned on or the computer restarts, the BIOS performs some initial tests and then transfers control to the master boot record (MBR) where the boot loader resides.

What is a real-time system

Real-time operating system has made strict requirements on time. Real-time operating system is divided into two types: hard real-time and soft real-time

Hard real-time operating systems dictate that an action must be completed or occur at a specified time, such as in a car factory, where welding machines must be completed at a certain time. Welding too early or too late can cause permanent damage to the car.

Soft real-time operating systems don’t want to occasionally violate final deadlines, but they are still acceptable. And it won’t cause any permanent damage. Such as digital audio, multimedia, mobile phones are soft real-time operating systems.

You can easily understand the two metrics of hard real time and soft real time: whether it has to be done in the moment and whether it causes serious damage.

What is virtual memory

Virtual memory is a memory allocation scheme and a mechanism that can be used to assist memory allocation. As we know, applications are loaded into memory on a per-page basis. But not all pages load into memory, and the hardware and software in the computer make up for the memory deficit by temporarily transferring data from RAM to disk. If you don’t have virtual memory, the computer will talk to you once you fill it up

Uh, no, sorry, you cannot load any more applications, please close another application to load a new one. For virtual memory, the computer can perform operations by looking at areas of memory that have not been used recently and then copying them to the hard disk. Virtual memory is realized by copying technology girl, you can see brother can install so many programs capital. Replication is automatic, you don’t know it’s there.

What are processes and schedules

A process is an instance of an executing program. For example, a Web program is a process, a shell is a process, and the article editor Typora is a process.

The operating system is responsible for managing all running processes, allocating a specific amount of time to each process to occupy CPU, and allocating specific resources to each process.

The operating system maintains a process table to keep track of the activity status of each process. Inside the process table, the status of each process and the resources used by each process are listed.

Courses.cs.vt.edu/csonline/OS… This site has an animation about the state rotation of the process, which is really well done.

What is a thread and the difference between a thread and a process

This is another old question, let’s answer it from the perspective of operating system.

We mentioned above that a process is an instance of a running program, and a thread is actually a single stream in a process. Threads are also called lightweight processes because they have certain properties in the process. If the browser is a process, each TAB page below the browser can be thought of as a thread.

The following is the difference between threads and processes holding resources

Threads are not as independent as processes, and they share data

The overhead of creating a thread is much lower than that of a process, because all you need to create a thread is a stack pointer and a program counter, while creating a process requires the operating system to allocate new address space, data resources, etc., which is expensive.

What are the benefits of using multiple threads

Multithreading is one of the basic things programmers have to know, so here are some of the benefits of multithreading

  • Improves the sequence of responses to users
  • Resource sharing in the process
  • Comparative economy
  • In-depth understanding of multi-threaded architectures

What is RR scheduling algorithm

The round-robin (RR) scheduling algorithm is mainly for time-sharing systems. The RR scheduling algorithm allocates the same time slice to each process in a cycle. The RR scheduling algorithm has no concept of priority. The implementation of this algorithm is relatively simple, and each thread will occupy the time slice, there is no thread hunger problem.

Deadlock occurs in the system

The following four conditions must be met for a deadlock to occur

  • The mutex (Mutual Exclusion): Only one process can use a resource at a time. If another process requests the resource, the requesting process must be delayed until the resource is released.
  • Hold and Wait: There must be a process that holds at least one resource and is waiting to acquire resources currently held by other processes.
  • No Preemption: The resource cannot be preempted, that is, after the process has completed its task, the resource can only be released automatically by the owning process.
  • Circular Wait: There must be groups {p0, p1,….. The waiting process of pn} makes P0 wait for a resource held by P1, P1 wait for a resource held by P2, pN-1 wait for a resource held by PN, and PN wait for a resource held by P0.

Different RAID levels

RAID is called redundant array of Disks, or disk array for short. The virtualization technology is used to combine multiple disks into one or more disk arrays to improve performance or data redundancy.

RAID has different levels

  • RAID 0 – Fault-tolerant striped disk array
  • RAID 1 – Mirroring and duplex
  • RAID 2 – Memory error correction codes
  • RAID 3 – Bits interleaved parity check
  • RAID 4 – Block staggered parity check
  • RAID 5 – Block staggered distributed parity check
  • RAID 6 -P + Q redundancy

What is the DMA

The Chinese name for DMA is direct memory access, which means that the CPU grants I/O modules permission to read or write to memory without involving the CPU. That is, DMA can be done without the CPU. This process is managed by a chip called a DMA controller (DMAC). Because DMA devices can transfer data directly between memory, rather than using the CPU as an intermediary, congestion on the bus can be alleviated. DMA improves system concurrency by allowing the CPU to perform tasks while the DMA system transfers data across the system and memory bus.

What are the benefits of multithreaded programming

I’m sorry. I can’t help laughing

To put it bluntly, why multithreading when a single thread can? Of course, in order to improve the program forced parallel ability. Multithreading can make your program run faster in some cases, which is why multi-core cpus are present, but the presence of multi-core cpus can cause data consistency issues that programmers can solve. On the other hand, multithreaded programming can improve the programming ability and programming thinking of programmers. At the same time can also improve the management ability of programmers, if you treat each thread flow as the female master of teacher time management, can timely coordinate all P friends of the relationship, then you are super god programmer, so, who said that programmers will not do management? Doug Lea is awesome!!

Ps: The JUC kit developed by Doug Lea, without the dog head.

What is a device driver

In a computer, a device driver is a computer program that controls or operates a specific device connected to the computer. Drivers provide software interfaces that interact with hardware, enabling the operating system and other computer programs to access a particular device without needing to know the specifics of its hardware.

Communication between processes

Communication concept

There are many ways to communicate between processes. First, you need to understand the following concepts

  • Race conditions: When two or more threads modify a shared data at the same time, affecting the correct execution of the program, they are called race conditions.

  • Critical sections: not only does sharing resources create race conditions. in fact, sharing files and shared memory can also create race conditions. so how can you avoid it? It is forbidden for one or more processes to read or write shared resources (including shared memory and shared files) at the same time. In other words, we need a mutual exclusion condition, which means that if one process uses shared variables and files in a certain way, other processes are prohibited from doing so (accessing unified resources).

    A good solution should include the following four conditions

    1. At no time can two processes be in a critical region at the same time
    2. No assumptions should be made about the speed and number of cpus
    3. Processes outside a critical area must not block other processes
    4. You cannot make any process wait indefinitely to enter a critical section

  • Mutual exclusion of busy: When one process is modifying a resource, other processes must wait. Each process must be mutually exclusive. The solution we discussed is based on mutual exclusion of busy.

The solution

The professional term for inter-process Communication is Inter Process Communication (IPC), which mainly includes the following Communication modes

  • The messaging: Message passing is the mechanism between processes to realize communication and synchronous waiting. With message passing, the communication between processes can communicate directly without sharing variables. Message delivery is divided into sender and receiver
  • Fifo queue: FIFO queue refers to the communication between two unrelated processes. The two processes can communicate with each other. This is a full-duplex communication mode
  • The pipeThe: pipe is used for communication between two related processes. This is a half-duplex communication mode. If full duplex is required, another pipe is required.
  • Direct communication: In this mode of process communication, only one link exists between processes, and the names of communication parties must be specified between processes.
  • Indirect communicationIndirect communication means that the communication parties do not directly establish a connection, but find a mediator, which may be an object and so on. The process can place messages in it, and can delete messages from it, so as to achieve the purpose of inter-process communication.
  • The message queueMessage queues are linked lists of stored messages in the kernel, identified by message queue identifiers, which provide full-duplex communication connections between different processes.
  • The Shared memoryShared memory uses memory between all processes to establish a connection. This type requires synchronous process access to protect each other.

Interprocess state model

cat chapter1 chapter2 chapter3 | grep tree
Copy the code

The first process, cat, cascades and outputs the three files. The second process is grep, which choose the tree contains a keyword from the input content, according to the relative speed of the two process (depending on the relative complexity of the two programs and their respective assigned to CPU time slice), below this kind of situation could occur, grep ready to run, but the input process is not yet complete, You must block the grep process until you finish typing.

When a process starts running, it may go through one of these states

There are three states involved in the diagram

  1. Running state, the running state refers to the actual elapsed CPU time slice of the process
  2. The ready state, ready is runnable but ready because other processes are running
  3. Blocking stateThe process cannot run unless some external event occurs

Logically, the running state and the ready state are very similar. Both cases indicate that the process is running, but the second case does not get CPU time sharding. The reason the third state is different from the first two is that the process cannot run, nor can it run when the CPU is idle.

The three states involve switching between the four states. A state 1 rotation occurs when the operating system finds that a process cannot continue. In some systems, a process makes a system call, such as pause, to obtain a blocked state. On other systems, including UNIX, a process is terminated automatically when no input is available to read from a pipe or a special file (such as a terminal).

Both transformations 2 and 3 are caused by the process scheduler (part of the operating system), which the process itself is unaware of. The occurrence of transformation 2 indicates that the process scheduler has determined that the current process has been running long enough that it is time for another process to run the CPU time slice. When all other processes have run and it is time for the first process to regain the CPU time slice, the transition 3 occurs.

Scheduling refers to deciding which processes should be run first and for how long, which is important. Many algorithms have been designed to try to balance the overall efficiency of the system against the competing requirements of the various processes.

A transformation 4 occurs when an external event that the process is waiting for occurs, such as after some data is input from the outside. If no other process is running at this point, conversion 3 is triggered immediately and the process starts running, otherwise the process is in the ready phase, waiting for the CPU to be free before it is its turn to run.

What are the scheduling algorithms

Scheduling algorithms can be divided into three categories: batch scheduling, interactive scheduling and real-time scheduling

Scheduling in batch processing

First come, first served

It’s like a first come, first served… Perhaps the simplest design for a non-preemptive scheduling algorithm is first-come,first-serverd. Using this algorithm, cpus are allocated to processes in the order they are requested. At its most basic, there is a queue of ready processes. When the first task enters the system from outside, it starts immediately and allows it to run for any length of time. It will not be interrupted by running too long. When other jobs come in, they go to the end of the ready queue. When the running process blocks, the first process in the wait queue starts running. When a blocked process is back in the ready state, it will appear as a newly arrived task at the end of the queue, at the end of all processes.

The power of this algorithm is that it is easy to understand and program. In this algorithm, a single linked list keeps track of all ready processes. To select a process to run, simply remove a process from the head of the queue. To add a new job or block a process, simply append the job or process to the end of the queue. This is a very simple implementation.

If you have 100 I/O processes queuing and the 101st one is cpu-intensive, then you have to wait for 100 I/O processes to finish running before one cpu-intensive process runs. This is not possible in practice, so priority or preemptive processes are needed to prioritize important processes to run.

Shortest job first

In batch processing, the second scheduling algorithm is Shortest Job First, and we assume that the running time is known. An insurance company, for example, can predict with considerable accuracy how long it will take to process a batch of 1,000 claims because it does similar work every day. When several equally important jobs are started in the input queue, the scheduler should use the shortest first job algorithm

As shown in figure A, there are four jobs A, B, C, and D, with running times of 8, 4, 4, and 4 minutes respectively. If running in the order shown in the figure, the turnaround time of A is 8 minutes, B is 12 minutes, C is 16 minutes, D is 20 minutes, and the average time is 14 minutes.

Now consider using the shortest job first algorithm to run four jobs, as shown in Figure B. The current turnaround time is 4, 8, 12 and 20 respectively, with an average of 11 minutes, which can prove that shortest job first is optimal. Consider the case where there are four jobs with running times a, B, C, and D respectively. The first job ends at time A, the second at time A + B, and so on. The average turnaround time is (4A + 3b + 2C + d) / 4. Obviously A has the greatest impact on the average, so A should be the shortest priority job, followed by B, then C, and then D and it can only affect its own turnaround time.

It is important to note that the shortest job first algorithm is optimal when all processes are running.

Minimum remaining time is preferred

The Shortest job first preemptive version is known as the Shortest Remaining Time Next algorithm. With this algorithm, the scheduler always selects the process with the shortest remaining running time to run. When a new job arrives, its total time is compared to the remaining time of the current process. If the new process takes less time than the current running process, the current process is suspended and the new process is run. In this way, short-term operations can be well served.

Scheduling in interactive systems

Interactive systems are so common in PCS, servers, and other systems that it’s worth exploring interactive scheduling

Polling scheduling

One of the oldest, simplest, fairest and most widely used algorithms is the round robin algorithm. Each process is assigned a period of time, called a quantum, within which the process is allowed to run. If the process is still running when the time slice ends, it preempts one CPU and allocates it to another process. If the process blocks or ends before the time slice ends, the CPU switches immediately. The polling algorithm is relatively easy to implement. What the scheduler does is maintain a list of runnable processes, like a in the image below, that are moved to the end of the queue when a process runs out of time, like B in the image below.

Priority scheduling

It is not true that all processes are of equal priority. For example, in a university hierarchy, first the dean, then the professors, secretaries, support staff, and finally the students. This consideration of external circumstances enables priority scheduling

The basic idea is clear: each process is assigned a priority, and the process with the highest priority runs first.

This does not mean that high-priority processes can run forever, however, as the scheduler reduces the priority of the currently running process during each clock interrupt. If this action causes its priority to drop below that of the next highest process, a process switch occurs. Alternatively, each process can be assigned a maximum interval of time allowed to run. When the interval runs out, the next higher-priority process gets a chance to run.

Shortest process first

For batch systems, since shortest job first is often accompanied by shortest response times, one approach is to make assumptions based on the past behavior of the process and execute the one with the shortest estimated elapsed time. Assuming that the estimated running time of each command on each terminal is T0, now assuming that its next run time is measured to T1, the estimated time can be improved by weighting two values, namely aT0+ (1-1)T1. By choosing the value of A, you can decide whether to forget the old running times as soon as possible or to keep them in mind for a long time. When a is equal to 1/2, you get the following sequence

As you can see, after three rounds, T0’s share of the new estimate has dropped to 1/8.

This technique of taking a weighted average of a current measurement and a previous estimate to get the next one is sometimes called aging. This method uses a lot of predictive values based on the current values.

Lottery scheduling

There is an algorithm that can give prediction results and has a relatively simple way to achieve it, namely lottery Scheduling algorithm. His basic idea is to provide a lottery of system resources for processes. When a scheduling decision is made, a lottery ticket is drawn at random, and the process that owns the lottery ticket gains resources. For example, during CPU scheduling, the system could hold 50 sweepstakes per second, and each winning process would be rewarded with extra running time.

Think of the lottery as a buff, which gives you a 15% chance to produce speed boots.

Fair share scheduling

If user 1 starts nine processes and user 2 starts one, using rotation or the same priority scheduling algorithm, user 1 will get 90% CPU time and user 2 will get 10% CPU time.

To prevent this, some systems take process owners into account before scheduling. In this model, each user allocates some CPU time, and the scheduler selects processes and forces them to execute. So if two users are each guaranteed a 50% CPU slice, then no matter how many processes a user has, they will get the same CPU share.

Page replacement algorithms are what

algorithm annotation
The optimal algorithm Not implementable, but can be used as a benchmark
NRU(not recently used) algorithm It’s very similar to the LRU algorithm
FIFO(First in, first out) algorithm Important pages may be discarded
Second chance algorithm Compared with FIFO has a great improvement
The clock algorithm The actual use
LRU(least recent) algorithm Good, but hard to achieve
NFU(least frequently consumed) algorithm Very similar to LRU
Aging algorithm Efficient algorithm for LRU approximation
Working set algorithm It’s expensive to implement
Working set clock algorithm A more efficient algorithm
  • The optimal algorithmReplaces the last page to be visited in the current page. Unfortunately, there’s no way to determine which page will be the last to visit,So actually the algorithm can't be used. However, it can be used as a yardstick against which other algorithms can be measured.
  • NRUThe algorithm classifies the page atmosphere into four categories according to the states of R bits and M bits. Select a page at random from the least numbered category. The NRU algorithm is easy to implement, but not very good performance. There are better algorithms.
  • FIFOIt tracks the order in which pages are loaded into memory and places them in a linked list. It is possible to delete the oldest pages that are still in use, so this algorithm is not a good choice either.
  • A second chanceThe algorithm is a modification to the FIFO that checks to see if a page is still in use before deleting it. If the page is in use, it is reserved. This improvement greatly improves performance.
  • The clockThe clock algorithm is another implementation of the second chance algorithm. The clock algorithm performs about the same as the second chance algorithm, but takes less time to execute the algorithm.
  • LRUThe algorithm is a very good algorithm, but noSpecial Hardware (TLB)Difficult to implement. If you don’t have hardware, you can’t use the LRU algorithm.
  • NFUThe algorithm is similar to LRU algorithm, but its performance is not very good.
  • agingThe algorithm is a closer implementation of the LRU algorithm, and can be better implemented, so it is a good choice
  • The last two algorithms use the working set algorithm. The working set algorithm provides reasonable performance overhead, but its implementation is complicated.WSClockIs another variant that not only provides good performance, but can be implemented efficiently.

The best algorithms are aging algorithm and WSClock algorithm. They are based on LRU and working set algorithms respectively. They all have good performance and can be implemented effectively. There are other good algorithms out there, but actually these two are probably the most important.

What are the metrics that affect the scheduler

Several factors determine whether a scheduler is good or bad

  • CPU usage:

The percentage of time the CPU is executing a task (that is, not idle).

  • Waiting time

This is the time when the process is executed in rotation, that is, when the process is switched

  • throughput

The number of processes completed per unit of time

  • The response time

This is the time that passes between submitting the process and getting useful output.

  • Turnaround time

The time elapsed from submission to completion of the process.

What is a zombie process

A zombie process is a completed and terminated process that still exists in the process table. Zombie processes usually occur in parent-child processes because the parent process still needs to read the exit status of its child process.