What is the physical meaning of P operation and V operation in mutually exclusive operation between two processes?

process management

Comparison between sequential execution and concurrent execution of programs

Sequential execution

concurrent execution

Program sequential execution

Intermittent execution, multiple programs are carried out in a "stop-and-go" manner.

The program has been closed.

The plan lost its closure.

Exclusive resources

Shared resources

Have the ability of the present.

Lose reproducibility

There are direct and simple constraints.

L multi-channel programming concept and its advantages

1. Multiprogramming: It means running two or more programs on a computer at the same time.

2. Features of multiprogramming: Multiple programs share system resources and execute at the same time.

3. Advantages of multiprogramming: improving resource utilization and increasing system throughput.

What is process, the difference and connection between process and procedure?

1. Process introduction:

Due to the characteristics of multi-channel programs, programs are parallel, restrictive and dynamic, which makes it difficult to describe and reflect the situation in the system.

2. Process: the execution process of a program in a concurrent environment.

3. The main differences between process and procedure:

1) The program is permanent and the process is temporary.

2) The program is static and the process is dynamic.

3) The process consists of three parts.

procedure

data

Process control block (data structure describing process activities)

4) Processes and procedures are not in one-to-one correspondence.

A program can correspond to multiple processes, that is, multiple processes can execute the same program.

A process can execute one or several programs.

4. Analogy between procedure and process

process sequence

advance

Music score of a singing or musical instrument.

Performance or performance

drama

fulfil

cook

5. Process characteristics: dynamic, concurrent, scheduling, asynchronous and structured.

The basic state of L process and its transformation

Basic status of 1. process:

1) is running: the process is occupying CPU；;

2) Ready status: the process has running conditions, but it has not occupied CPU；;

3) Blocking state: The process cannot enjoy the CPU because it is waiting for an event.

2. Process state transition:

What are the components of the process and the functions of the process control block?

1. process composition: it consists of three parts: program, data set and PCB.

2. Function of process control block: Process control block is the most critical part of process composition.

1) Each process has a unique PCB.

2) The operating system controls and manages the process according to PCB.

3) The dynamics and concurrency of the process are represented by PCB.

4) PCB is the only symbol of process existence.

L PCB organization mode

Linear queues, linked tables, index tables

L UNIX process management command:

1.PS- Show process status.

Function: Check the current process status in the system.

take for example

$ ps displays the basic information of the process related to control interrupt.

2. Hibernate-let the process hibernate

Function: Pauses the execution of the process for a period of time, and its parameter unit is seconds.

take for example

$ sleep 60 will wait 60 seconds and then return to the $ prompt.

3.&-background command characters

Function: Add&; At the end of the command line. Character, this command process will be executed in the background.

take for example

$ ls–l/usr & amp； Create a process that displays directory commands, which is executed in the background, that is, it can only run when there is no foreground process running.

4. Wait-Wait for the background process to end.

Function: Wait for the background process to end.

take for example

$ wait 2080 waits for the background process with PID of 2080 to terminate.

5. Terminate-Terminate the process

Function: Terminate the execution of a process.

For example (in superuser mode)

# kill 678 Stop the process with PID of 678.

6. Good-Set priorities

Function: It is to execute a command with different priorities.

take for example

Ordinary users can only lower the priority:

$ nice–n10cc f 1.c When executing the command ccf1.c, the nice value is 30 (i.e. 20+ 10).

The super user (root) can increase the priority of the process (that is, the increment value can be a negative number not less than -20).

# nice -n-10 vi abc executes vi abc (editing command) with nice value of 10 (i.e. 20- 10).

Synchronization and mutual exclusion of l processes

1. Synchronization: refers to the direct interaction between processes when completing a task together.

2. Mutual exclusion: Exclusive access refers to competition and mutual restriction for the same physical resources.

What are the key resources and key areas?

1. Critical resource: a resource that only one process is allowed to use at a time.

2. Key areas: procedures for accessing key resources in each process.

3. Criteria for mutually exclusive access to key areas:

1) If multiple processes request to enter the idle critical area, only one process is allowed to enter at a time.

2) At any time, there cannot be more than one process in the key area. If an existing process enters its own critical section, all other processes trying to enter the critical section must wait.

3) The process that enters the critical area should quit within a limited time, so that other processes can enter their own critical area in time.

4) If the process cannot enter its critical area, it should give up the CPU to avoid the process being "busy".

L semaphore

1. Semaphore definition:

Semaphore (semaphore) =

2. The physical meaning of semaphore:

Greater than 0: indicates the available quantity of the current resource.

1) signal value

Less than 0: its absolute value indicates the number of processes waiting to use resources.

2) The initial value of semaphore is a non-negative integer variable, which represents the number of resources.

3) The signal amplitude is variable, but it can only be changed by P and V operations.

Operation primitive

1. operation primitive:

1) P is operated once, and the value of s is reduced by 1, that is, S = S- 1 (requesting to allocate a resource);

2) if S≥0, the process continues;

If s < 0 indicates that there are no resources, the state of the process is set to a blocking state, the corresponding PCB is connected to the end of the semaphore queue, and the processor gives up waiting (until another process performs V(S) operation).

2.V operation primitive (Netherlands waiting) V(S):

1) V is operated once, and the value of s is added to 1, that is, S = S+ 1 (releasing a unit resource);

2) if s > 0, it means that there are resources, then the process continues to execute;

If S≤0, the process corresponding to the first PCB on the semaphore queue is released (the blocking state is changed to the ready state), and the process performing V operation continues to execute.

Realization of simple synchronization and mutual exclusion among L processes

A general model of mutual exclusion between 1.P and v primitives;

Set the initial value of the mutex to 1.

2. A simple example of P and V primitive operation synchronization.

The relationship between suppliers and users using buffers is as follows:

S 1 buffer is empty (0 means non-empty, 1 means empty), and the initial value is s1= 0;

Whether S2 buffer is full (0 means unsatisfied, 1 means full), the initial value S2 = 0；;

3. Producer-consumer problem (typical example of operating system)

Mutex mutex semaphore, initial value1; The number of full buffers, the initial value is 0; The number of empty buffers, with an initial value of n;

4. Application example

[Example 1] Suppose there is only one printer in the system, and all the programs of three users will use the printer to output the calculation results when they are executed. Let each user program correspond to a process. Q: What are the constraints between these three processes? Use p and v operations to write the algorithm for these processes to use printers.

[Solution]

Because the printer is a key resource, three processes can only use this printer mutually exclusive. Let three processes be PA, PB and PC respectively, and the initial value of mutex is 1. The implementation process is as follows:

[Example 2] Is the algorithm for judging the following synchronization problem correct? If there are any mistakes, please point out the reasons and correct them.

1) Let two processes, A and B, share a buffer Q. A writes information to Q and B reads information from Q. The algorithm block diagram is shown in the figure.

Note: the initial value of semaphore s is 0.

[Solution] This algorithm is incorrect. Because two processes, A and B, share a buffer Q, if A runs first and has enough information, the information in buffer Q will be washed out later, resulting in information loss, and B cannot read complete information from Q. The correction method is as follows:

A and B processes use buffer Q synchronously, and two semaphores should be set:

Empty means that the buffer q is empty, and the initial value is1; Full indicates that the buffer q is full, and the initial value is 0.

The algorithm block diagram is as follows:

2) Let A and B be two concurrent processes that share a key resource. The algorithm block diagram of its running critical area is shown in the figure.

[Solution] This algorithm is incorrect. Because two processes, A and B, execute concurrently and share a key resource, A and B should mutually exclude the use of the key resource, that is, only one process is allowed to enter the key resource at a certain time, and there is no time sequence relationship.

Modified algorithm: A and B processes should mutually exclude into the critical area, and set a semaphore mutex with the initial value of 1.

[Example 2] A computer has two I/O channels, which are respectively connected to a card input machine and a printer. The card reader inputs a stack of cards into buffer B 1 one by one, moves them to buffer B2 after processing, and prints them on the printer. Q:

1) How many processes should the system set to complete this task? What are their jobs?

2) What are the mutual constraints between these processes?

3) Write the synchronization algorithm of these processes with P and V operations.

[Solution]

1) The system can set up three processes to complete this task: the Read process is responsible for reading card information from the card input machine and inputting it into the buffer b1; Get process is responsible for fetching information from buffer B 1, processing it, and then sending the result to BufferB2; The printing process is responsible for obtaining information from buffer B2 and printing the output on the printer.

2) Operation process:

The reading process is affected by the acquisition process. After the B 1 buffer is full of information, the reading process cannot read the information until the get process takes all the information.

The Get process is constrained by the Read process and the Print process: the Get process can only fetch information from the B 1 buffer when it is full, and the Get process can only send the processing results to the B2 buffer when it is empty;

The printing process is constrained by the Get process. Only after the B2 buffer is full, the printing process can take out the information and print it out.

3) Meaning and initial value of semaphore:

B 1 full-buffer B 1 is full, with an initial value of 0.

B 1 empty-buffer B 1 is empty, with an initial value of 0.

B2 full- Buffer B2 is full, with an initial value of 0.

B2 empty- Buffer B2 is empty with an initial value of 0.

4) Operation block diagram is as follows:

L handle simple communication

classify

Low level communication mechanism

Advanced communication organization

trait

The amount of information transmitted is very limited.