Introduction to operating systems

Hi, Habr! I want to bring to your attention a series of articles-translations of one interesting in my opinion literature - OSTEP. This material takes a rather in-depth look at the work of unix-like operating systems, namely, working with processes, various schedulers, memory, and other similar components that make up a modern OS. The original of all materials you can see here . Please note that the translation was made unprofessionally (fairly freely), but I hope I saved the general meaning.

Laboratory work on this subject can be found here:

• original: pages.cs.wisc.edu/~remzi/OSTEP/Homework/homework.html
• original: github.com/remzi-arpacidusseau/ostep-code
• my personal adaptation: github.com/bykvaadm/OS/tree/master/ostep
• Part 3: Scheduler Introduction

Other parts:

• Part 1: Intro
• Part 2: Abstraction: the process
• Part 3: Introduction to the Process API
• Part 4: Scheduler Introduction

And you can also look to me on the channel in the telegram =)

Work program

What happens when a program works? Running programs does one simple thing - it executes instructions. Every second, millions and even possibly billions of instructions are retrieved by the processor from RAM, in turn, it decodes them (for example, recognizes what type, these instructions belong to) and executes. This can be the addition of two numbers, memory access, test conditions, the transition to the function and so on. After the end of the execution of one instruction, the processor proceeds to the execution of another. And so the instruction for the instruction, they are executed until the program ends.
')
This example is naturally considered simplified - in fact, to speed up the processor, modern hardware allows you to execute instructions out of turn, calculate possible results, execute instructions at the same time and similar tricks.

Von Neuman model of computation

The simplified form of work described by us is similar to the Von Neumann model of computation. Von Neumann is one of the pioneers of computer systems, he is also one of the authors of game theory . While the program is running, a lot of other events occur, many other processes and third-party logic are running, the main purpose of which is to simplify the launch, operation and maintenance of the system.

There is a set of software that is responsible for the ease of running programs (or even allowing several programs to run simultaneously), it allows programs to share the same memory, as well as interact with different devices. This set of software (software) is in fact called the operating system and its task is to ensure that the system works correctly and efficiently, as well as ensure the simplicity of managing this system.

operating system

An operating system, or OS for short, is a complex of interconnected programs designed to manage computer resources and organize user interaction with a computer .

The OS achieves its effectiveness primarily through the most important technique - the virtualization technique. The OS interacts with a physical resource (processor, memory, disk, and the like) and transforms it into a more general, more capable and simpler form of use for itself. Therefore, for a common understanding, you can very roughly compare the operating system with a virtual machine.

In order to allow users to give commands to the operating system and thus use the capabilities of the virtual machine (such as running the program, allocating memory, accessing the file, and so on), the operating system provides some interface called the API (application programming interface) and to which you can make calls (call). A typical operating system makes it possible to make hundreds of system calls.

Finally, since virtualization allows multiple programs to work (thus sharing the CPU), and simultaneously access their instructions and data (thereby sharing memory), and also access the disks (thus sharing I / O devices) ), the operating system is also called the resource manager. Each processor, disk, and memory is a system resource, and thus the task of managing these resources becomes one of the roles of the operating system, doing it efficiently, honestly or, on the contrary, depending on the task for which this operating system is designed.

CPU virtualization

Consider the following program:
(https://www.youtube.com/watch?v=zDwT5fUcki4)



It does not perform any special actions, in fact, all that it does is to call the spin () function, whose task is to cyclically check the time and return after one second has passed. Thus, it repeats endlessly the string that the user passed as an argument.

Run this program and pass the “A” symbol to it with the argument. The result is not very interesting - the system simply executes the program, which periodically displays the symbol “A”.

Now let's try the option when running multiple instances of the same program, but displaying different letters to make it clearer. In this case, the result will be somewhat different. Despite the fact that we have one processor, the program runs simultaneously. How is that? And it turns out that the operating system, not without the help of the capabilities of the equipment, creates an illusion. The illusion that there are several virtual processors in the system, turning one physical processor into a theoretically infinite number and thus allowing the programs to run at the same time. This illusion is called CPU virtualization .

This picture gives rise to many questions, for example, if several programs want to start at the same time, which one will be launched? The “policies” of the OS are responsible for this question. Politicians are used in many places of the OS and answer similar questions, as well as they are the basic mechanisms that the OS embodies. Hence, the role of the OS as a resource manager.

Memory virtualization

Now let's look at memory. The physical model of memory in modern systems is represented as an array of bytes . To read from memory, you need to specify the address of the cell to access it. To record or update data, you must also specify the data and the address of the cell where to write them.

Memory access occurs constantly in the process of the program. The program stores all its data structure in memory, and accesses it by executing various instructions. The instructions, meanwhile, are also stored in the memory, so it is also accessed for every request to the next instruction.

Call malloc ()

Consider the following program that allocates a memory area using the malloc () call (https://youtu.be/jnlKRnoT1m0):



The program does several things. First, allocates a certain amount of memory (line 7), then displays the address of the selected cell (line 9), writes zero to the first slot of the allocated memory. Next, the program enters a loop in which it increments the value stored in memory at the address in the variable “p”. It also displays the process id of itself. The process identifier is unique for each running process . Having started several copies, we will come across an interesting result: In the first case, if you do nothing and just run several copies, then the addresses will be different. But this does not fall under our theory! True, because in modern distributions, memory randomization is enabled by default. If you turn it off, we get the expected result - the memory addresses of two simultaneously running programs will be the same.



The result is that two independent programs work with their own private address spaces, which in turn are displayed by the operating system in physical memory . Therefore, the use of memory addresses within one program will not affect the others in any way, and it seems to each program that it has its own piece of physical memory, which is entirely at its disposal. The reality, however, is that physical memory is a shared resource managed by the operating system.

Consistency

Another important topic within operating systems is consistency . This term is used when it comes to problems in the system that may arise when working with many things at the same time within the same program. Consistency problems occur even in the operating system itself. In the previous examples with memory and processor virtualization, we realized that the OS manages many things at the same time — it starts the first process, then the second, and so on. As it turned out, this behavior can lead to some problems. For example, modern multi-threaded programs have such difficulties.

Consider the following program:



The program in the main function creates two threads using the Pthread_create () call. In this example, the stream can be thought of as a function running in the same memory space along with other functions, with the number of functions running simultaneously clearly more than one. In this example, each thread starts and executes the worker () function, which in turn simply increments the variable,.

Let's run this program with an argument of 1000. As you might have guessed, the result should be 2000, since each thread incremented a variable 1000 times. However, things are not so simple. Let's try to run the program with the number of repetitions an order of magnitude more.



By supplying a number to the input, for example, 100000, we expect to see the number 200000 at the output. However, by running the number 100000 several times, we will not only not see the correct answer, but we will get various incorrect answers. The answer lies in the fact that to increase the number requires three operations - extracting the number from the memory, incrementing and then writing the number back. Since all these instructions are not carried out atomically (all at the same time), such strange things can occur. This problem is called programming race condition . When unknown forces at an unknown time can affect the performance of any of your operations.