The hierarchy of a computer system is generally divided into five layers, with the next two layers belonging to the hardware part, described in the previous sectionComputer composition principleParts are introduced and part of the fourth layer assembly language machineX86 assembly instructionThere was a brief discussion.

This article builds on the third layer, the operating system, with an overview and process-related focus.

1 overview

1.1 Basic Concepts

1.1.1 What is an Operating system

In the subject of Operating system Principles, computer systems are divided into four levels: hardware, operating system, applications, and users, slightly different from the classifications introduced earlier. As the first software above hardware, operating system is used to manage various computer hardware and provide interfaces for other software and users. Operating system is the most basic system software in computer system.

1.1.2 Operating System Features

These features can be used to distinguish them from other software.

  1. Concurrence

Concurrency refers to the occurrence of two or more events at the same time interval. The concurrency of the operating system is the existence of multiple running programs at the same time. These programs are executed alternately on the micro level, and a CPU system can only have one program executing at any time. A related concept is parallelism. The latter refers to the ability to handle multiple tasks at the same time. Processes are introduced for concurrent execution of programs.

  1. Sharing

That is, resource sharing. Resources in the system can be used by multiple concurrent processes. Sharing can be classified into mutually exclusive sharing and simultaneous access. Mutually exclusive means that only one process can access some resources at a time. Only when the process is used up, another process can access the resources. Simultaneous access means that multiple processes access resources at a certain interval. Concurrency and sharing are the most basic characteristics of the operating system. Only concurrency can be shared, and only sharing can achieve concurrency.

  1. Virtual

Virtual is the mapping of a physical entity into a number of logical counterparts. The technology of virtual realization by users is called virtual technology. The operating system uses virtual technology to realize virtual processors, virtual memory and virtual devices. Among them, virtual processor and virtual device can make multiple users share the same physical entity as their own, and virtual memory can expand memory logically. The virtual technology of operating system can be summarized as

  • Time division multiplexing, such as processors
  • Space division multiplexing, such as memory
  1. Asynchronism

Under the premise of multiple concurrent programs, each program can not be executed at one time, the speed of which is unknown, which is the asynchronism of the process. If the operating system runs on the same operating environment, ensure that the results of multiple runs are the same.

1.1.3 function

In order to provide a good running environment for multiple programs, the operating system should have the following functions

  • Processor Management (CPU). In the multi-program environment, the allocation and operation of the processor are based on the process (or thread), so the management of the processor is the management of the process.
  • Memory management
  • File management
  • Equipment management

In order to enable users to operate computer hardware and play various functions of the operating system, corresponding interfaces need to be provided. Interfaces fall into two categories

  • The command interface can be divided into
    • Online command interface The user enters a command on the console or terminal, and the control is handed over to the operating system for execution. After the work is completed, the control is returned to realize interaction.
    • The offline command interface presents a set of control commands to the system. Users cannot interfere with the running of jobs, and the operating system performs batch operations.
  • A program interface consists of a set of system calls that the user can use the program to perform as functions

1.2 Development of operating system

1.2.1 No OPERATING system Phase

At this stage, the program loading, running, output of the results need manual intervention, I/O and CPU speed mismatch, machine utilization is very low

1.2.2 Batch processing Phase

In order to solve the aforementioned contradiction, the emergence of batch processing, batch processing is divided into single channel batch processing and multi-channel batch processing. Single-channel batch processing system always keeps a task in memory, in order to further improve resource utilization, the introduction of multi-channel program technology, the latter multiple programs run at the same time, when a program for I/O request to suspend running, the CPU will run another program, so that each component as busy as possible. The batch system is not interactive during the processing of tasks.

1.2.3 Time-sharing operating system

Time-sharing refers to dividing the running time of the processor into very short time slices by which the processor is assigned to each online job in turn. Because computers are so fast and jobs run so fast, each user feels like he or she owns a computer. A time-sharing operating system enables multiple users to simultaneously share a host through terminals, and they can interact with the host simultaneously without interfering with each other. A time-sharing operating system solves the interaction problem, but some scenarios require the system to process them in a short time.

1.2.4 Real-time operating System

In order to complete some urgent tasks in a short time without time slice queuing, the real-time operating system was introduced.

1.3 Operating Environment of the OPERATING system

1.3.1 Operating mechanism of the OPERATING system

The program executed by CPU is divided into two kinds of nature, one is the kernel program, one is the application program, the former is the manager of the latter, can execute some privileged instructions. Privileged instruction refers to the system call, these calls involve resource management, process management, etc., have a great impact on the entire system, so only the kernel program call. There are two states in the CPU, the core state (also known as the tube state and the core state) and the user state (also known as the eye state). Privilege commands can only be executed while in nuclear state of mind. Kernel programs run in the core state, and applications run in the user state.

The kernel program consists of four aspects

  • Clock management, dealing with all kinds of time related
  • Interrupt mechanism, interrupt technology is introduced in order to improve the utilization of resources in the multi-program running, interrupt mechanism only a small part of the function belongs to the kernel, responsible for protecting and restoring the interrupt information, transfer control to the relevant processing program.
  • An atomic operation is a common set of operations that can be called to perform (without interruption) frequently called tasks, such as process communication, CPU switching, etc
  • System control data structure and processing, such as PCB, etc

In order for an application to make system calls and execute privileged instructions to invoke functions, it needs to execute trap instructions (trap instructions or access instructions), which give CPU usage to the kernel and return CPU usage to the application after the operating system kernel processes it. Here you can think of a system call as a function call.

1.3.2 interrupt

In the last article, computers made upInstruction cycleAn instruction cycle consists of multiple CPU cycles, as mentioned in. When the interrupt signal needs to be exchanged during the execution of an instruction, the instruction will contain an interrupt cycle, and the interrupt query signal will be sent before the instruction ends. If there is an interrupt request, the CPU will enter the interrupt processing stage.

Interrupts can be used to shift the CPU from user mode to core mode to perform privileged operations for an application, or to allow a program to free up unused resources to improve resource utilization.

  1. Interrupt classification

Interrupts can be divided into external interrupts and internal interrupts. Interruption, which is caused by events other than CPU instructions. For example, the I/O end interruption indicates that the input/output is complete, and the clock interruption indicates that a fixed time segment expires. This class of instructions is independent of the program being processed by the current processor. Internal interrupt (also called exception, trap) is an event caused by CPU instructions

  • Voluntary interruptions such as falling into commands
  • Forced interrupts such as address out of bounds, arithmetic overflow
  1. Interrupt handling procedure

Only the general flow of external interrupt processing is introduced here, which is divided into the following stages

  • Disable Interrupt After the CPU responds to an interrupt, it stops receiving higher-level interrupt requests
  • Saving breakpoints To ensure that the interrupt service program can continue to execute the original program after execution, you need to save breakpoints (instructions saved in the PC)
  • Outgoing Interrupt service routine Sends the entry address of the interrupt service routine to the PC
  • Memory that holds field and mask words, now usually the program state word register (PSWR) and certain general purpose registers, used to indicate interrupt states such as priority
  • On interrupt Starts receiving more advanced interrupt requests
  • Execute interrupt service routine
  • Close the interrupt
  • Restore live and masked words
  • Open interrupt, interrupt return, continue to execute the original program

1.4 Operating system architecture

The operating system is divided into big kernel and micro kernel. As mentioned above, the operating system is divided into core state and user state. The core state should provide interface for the user state.

2 Process Management

2.1 process

2.1.1 Concepts and Features

In the multi-program environment, the concept of process is introduced to make multiple programs execute concurrently. In order to mark and save the state data of a specific process, each process contains a data structure, namely PCB (Process Control block). Creating a process is the PCB that creates the process. PCB, program segment and related data segment together form a process entity, which is static, while the process itself is dynamic. It can be understood as a running process of the program, and combined with the process entity, the process can be understood as a running process of the process entity, which is an independent unit of resource allocation and scheduling.

Processes, relative to programs, have the following characteristics

  • Dynamic is the most basic characteristic of process. Process is a process with life cycle.
  • concurrency
  • independence
  • asynchrony
  • Structure is the three components of the process entity

The three parts of the process are as follows

  1. Process control block

As the unique symbol of a process, it stores various information about the process, which can be divided into the following four categories

  • Process description information, including process identifiers (to mark the process) and user identifiers (to mark the user to which it belongs)
  • Process control information, including status and priority
  • Resource allocation list, including memory location, list of open files, and input/output devices used
  • Processor information, the value of each register
  1. Procedures section

3. Data segment includes raw data, intermediate data and output results

2.1.2 Process status and conversion

The life cycle of a process changes between the following states

  • When a create process is being created, the following steps are usually required
    • Apply for a blank PCB and write some control and management information
    • The system allocates some necessary resources
    • Put the process into the ready state
  • The ready process gets all the resources it needs except the processor and enters the running state as soon as it gets the processor (processor). There may be more than one ready process in the system, and they form a queue, namely the ready queue
  • A runnable process runs on a processor. In a uniprocessor environment, only one process is running at any one time
  • A blocked state, also known as a wait state, stops running due to lack of resources other than the processor or waiting for an event (such as I/O)
  • End State After a process is put into the end state, further resources are released

2.1.3 Process Control

Process control is to switch a process between various states, controlled by a variety of primitives, which can be divided into

  1. Process creation

In the operating system, processes are created when terminal users log in to the system, when jobs are scheduled, when the system provides services, and when user programs request applications. A process can also create another process. In this case, the creator process is the parent process and the created process is the child process. The child process inherits the resources of the parent process and returns the resources to the parent process when the child process is destroyed. The create process uses the create primitive as follows

  • Assign a PID to the new process and apply for a blank PCB (PCB limit). If the application fails, the creation fails
  • Allocates resources to a process, such as memory, and blocks waiting for resources if there are insufficient resources
  • Initialize the PCB
  • If the ready queue is accepted, the ready state is entered
  1. Termination of a process

There are three kinds of events that can cause a process to terminate

  • The end of the normal
  • Internal exception End
  • Outside intervention

To terminate a process, use the undo primitive as follows

  • Retrieves the PCB according to the PID and reads its status
  • If it is in the executing state, it immediately terminates and allocates the processor to another process, and then returns its resources and those of descendants to the parent or operating system
  • Remove this PCB from its queue
  1. Process blocking and waking up

Switch between running and blocking states using blocking and wake primitives, respectively

  1. Process switching

Process switching is the process by which a processor moves from one process to another

  • Saves processor context, including PC and other registers
  • Update the original process PCB and move it to the ready or blocking queue
  • Run another process and update its PCB
  • Recovering processor context

2.1.4 Process Communication

Here we will introduce three communication methods with higher speed and high transmission capacity, and PV communication will be introduced later.

  1. The Shared memory

Processes that need to communicate have a space that both processes can read and write, including data structures and memory. The OPERATING system provides shared storage space and mutually exclusive synchronization tools. Each process performs read and write operations independently.

  1. Information transfer

Processes can be transmitted through the message delivery methods provided by the system, including direct communication and indirect communication

  1. Pipeline communication

A pipe is a pipe file that connects a reader process to a writer process for communication. The writer process writes as a stream of characters and the reader process reads. This communication is half – duplex and is discarded when read.

2.2 the thread

2.2.1 Necessity of introducing threads

Process solves the concurrency of multiple programs, but the time and space cost of process creation, destruction and switching is too large, so thread is introduced, which can be understood as lightweight process. After the introduction of thread, process only as a resource allocation unit in addition to CPU, thread as CPU allocation unit, each thread in addition to a small amount of necessary resources, but also with the same process of other threads to share other resources, the same process thread switching overhead is very small. Threads also have three states: ready, blocked, and running.

2.2.2 Implementation of threads

Threads are divided into user-level threads and kernel-level threads. For user-level threads, the kernel does not feel the existence of threads. Applications start with a single thread, and new threads can be created using thread libraries. Kernel-level threads, thread management is done in the kernel, and applications have only one interface to kernel-level threads.

2.2.3 Multi-threaded model

Some systems support both user-level and kernel-level threads, resulting in a different multi-threading model, that is, the mapping between user-level threads and kernel-level threads

  • Many-to-one model Multiple user-level threads correspond to a kernel-level thread, which is managed in the application
  • One-to-one model
  • Many-to-many model

2.3 Processor Scheduling

2.3.1 Scheduling Reasons

In a multiprogram system, the number of processes is often greater than the number of processors, so it is necessary to allocate processors to each process, where the process assigned to the processor is running.

2.3.2 Scheduling Layers

A job needs three levels of scheduling from submission to completion, respectively

  • Job scheduling, also known as advanced scheduling, selects jobs in the backup state according to certain principles and allocates resources to create a process. If no work is performed, the job scheduling will be performed twice, once in and once out
  • Memory scheduling, also known as intermediate scheduling, switches a process that cannot run temporarily to the external memory waiting state from blocked state to suspended state, that is, one more state than the five states, increasing the memory utilization

  • Process scheduling, also known as low-level scheduling, is used to select an allocation processor from the ready queue.

2.3.3 Process Scheduling Mode

That is, if a higher priority process enters the ready queue, how do I allocate processors

  • Non-deprivation scheduling a running process continues to run until it completes or blocks
  • Deprivation scheduling stops the current process immediately and allocates the processor to a higher priority process

2.3.4 Scheduling mode

Several scheduling algorithms described below can be applied to one or more of the three levels of scheduling

  • First come, first served
  • Short work priority
  • Priority scheduling
  • High response ratio is preferred
  • Time slice rotation
  • Multi-level feedback queues, combining time slices and priorities

2.4 Process Synchronization

2.4.1 Concept of process synchronization

In a multi-program environment, processes have dependencies, and due to the asynchronism of the operating system, the execution order may not be certain if there is no restriction, which refers to process synchronization. Here are a few concepts

  • A critical resource is a resource that only one process is allowed to use at a time, such as a printer.
  • Synchronization synchronization refers to direct constraint relationships that coordinate the execution order of multiple processes created to complete a task
  • Mutual exclusion is also called an indirect constraint relationship in which one process uses a critical resource while another must wait. There are two kinds of mutually exclusive implementation: software implementation and hardware implementation

2.4.2 semaphore

Semaphores can be used to solve synchronization and mutual exclusion problems, consisting of two standard primitives: Wait and signal, also known as p operations and V operations, the former for waiting and the latter for wake up.

2.4.3 tube side

In the semaphore mechanism, each access to critical resources need to have their own PV operation, a large number of decentralized synchronous operations to bring trouble to the system management, so the introduction of a new process management tool, pipe procedures, to achieve the process mutually exclusive, but do not need to process itself.

2.5 a deadlock

2.5.1 concept

In a multi-program system, a deadlock occurs when multiple processes are waiting for each other’s resources to fall into wait

  • Mutually exclusive processes require resources that can only be used by one process
  • Inalienable Conditions Resources cannot be taken away until they are used up
  • Request and hold on to existing resources that will not be released if other required resources cannot be obtained
  • Circular wait There is a circular wait chain of process resources

2.5.2 Deadlock Handling Policy

To avoid deadlocks, the four necessary conditions for deadlocks need to be broken, or deadlocks can be allowed to occur but detected and resolved.

3 Memory Management

Memory management includes the following functions

  • Allocation and reclamation of memory space
  • Address translation Converts a logical address into a physical address
  • Memory space is expanded to use virtual space
  • Storage The storage space of each channel does not interfere with each other

Traditional memory management requires that all jobs be loaded into memory at once and remain there, which wastes memory. In order to solve this problem, virtual memory was introduced, which is to load part of the program into memory, put the memory that is needed into memory, and move out of memory that is not needed temporarily. In this way, it seems to provide users with much larger memory than the actual memory, that is, virtual memory.

4 File Management

This chapter introduces basic concepts related to files, but does not discuss implementation.

4.1 concept

A file is a collection of information stored in secondary storage, including text documents, images, programs, etc. User input and output, usually in the unit of files, can use the file management system for file management.

4.1.1 File Attributes

  • The name of the
  • Identifier, the internal id of the system
  • type
  • location
  • The size of the
  • To protect the
  • Time, date, and user ID

4.1.2 Basic Operations of files

  • Create a file
  • Write files
  • Read the file
  • Documents addressing
  • To truncate a file is to delete its contents

4.2 Logical Structure of files

The logical structure of the file is the organizational form of the file seen from the user’s perspective, which can be divided into

  • The unstructured file (streaming file) front end can be used by referring to the WHATWG specification Stream
  • Structured files (record files) are included
    • Sequential file
    • Index file
    • Indexed sequential file
    • Direct file or hash file