1. Operating System Development Process
Computer System Without an Operating System Concept: the hardware runs programs directly Application scenarios: early simple embedded devices, such as electronic calculators Single-program Batch Processing System Concept: a batch of jobs is entered off-line onto magnetic tape and processed in sequence Application scenarios: early scientific computing centers, where administrators processed jobs in sequence Multiprogramming Batch Processing System Concept: multiple programs are stored in memory at the same time, sharing resources alternately Application scenarios: large data processing centers, bank batch processing businesses Time-Sharing System Concept: multiple users share the computer in a time-sharing manner, taking turns using the CPU Application scenarios: computer experiments for learning, remote login systems Real-Time System Concept: respond to external events in a timely manner and complete processing on time Application scenarios: aircraft flight control systems, video conferencing systems
2. Basic Characteristics of Operating Systems
Concurrency (Concurrent) Meaning: multiple events occur within the same time interval; macroscopically they are simultaneous, microscopically they alternate Effect: improves resource utilization and system throughput Sharing (Sharing) Meaning: system resources are shared by multiple processes Effect: improves resource utilization and helps processes cooperate Virtualization (Virtual) Meaning: a physical entity becomes multiple logical counterparts Effect: provides a convenient and flexible way, improving resource utilization and flexibility Asynchronism (Asynchronism) Meaning: processes execute concurrently, starting and stopping Effect: the system coordinates and manages, ensuring stability and correctness
3. Main Functions of Operating Systems
Processor Management: allocates and schedules the processor, allowing multiple programs to run efficiently Memory Management: allocates memory reasonably and guarantees space for programs to run Device Management: controls and manages various devices, making them convenient for users to use User Interface: provides an interactive interface, making it convenient for users to operate and use the system
4. Basic Concepts of Process Synchronization
Meaning: when multiple processes run concurrently, they cooperate according to rules to execute correctly Purpose: prevent race conditions and ensure smooth cooperation Mechanisms: semaphores, monitors, message passing, etc., coordinate process access to resources and cooperation Semaphore: an integer variable used to implement process synchronization and mutual exclusion, which controls process access to resources through P (wait) and V (signal) operations. Monitor: a high-level synchronization mechanism that encapsulates shared resources and their operations in a module; processes access shared resources by calling procedures in the monitor, which automatically implements synchronization and mutual exclusion internally. Message Passing: communicates and synchronizes by sending and receiving messages; the sender waits for the receiver’s response, thereby achieving coordination
Critical Section
- Whether it is a hardware critical resource or a software critical resource, multiple processes must access it mutually exclusively
- In each process, the code that accesses the critical resource is called the critical section (Critical Section)
- Before entering the critical section, each process should first check the critical resource it wants to access to see whether it is being accessed. If at this moment the critical resource is not being accessed, the process may enter the critical section and set the flag indicating that it is being accessed; the code executed before the critical section is called the entry section (Entry Section)
- A section of code should also be added after the critical section to change the flag for accessing the critical section back to “not being accessed”; this is called the exit section (Exit Section)
The execution flow is shown in the figure:
5. Basic States of Processes and Their Transitions
Practice 1.0
If both of the following situations occur at the same time to a process in the running state: (a) after performing a P operation on a semaphore, the result is negative; (b) the time slice expires and an interrupt occurs. Then the process will transition from the running state to the ( A ) state. A. Blocked B. Ready C. Blocked or Ready D. Undetermined
In a multiprocess system, in order to ensure the integrity of shared variables, each process should enter the critical section mutually exclusively. The so-called critical section refers to (D) A. A buffer B. A data area C. A synchronization mechanism D. A section of program
Practice 2.0
A data acquisition and processing system has two processes, A and B. Process A is responsible for data acquisition and stores the collected data into buffer H for process B to process. The system stipulates that only after process B has taken the data from H can process A store new data in H. To enable the processes to execute concurrently and correctly, PV operations are used for management. Answer the following questions:
S1 with an initial value of 1, used by process B to notify process A that the data has been taken==
==Define a semaphore S2 with an initial value of 0, used to notify process B to take the data==
(2) Fill in the appropriate P or V operation in the box position of the following program so that they can execute correctly and concurrently.
At position ① fill in P(S1), at position ② fill in V(S2), at position ③ fill in P(S2), at position ④ fill in V(S1)
Practice 3.0
An automatic assembly line consists of three processes: production process A, inspection process B, and packaging process C. Every time process A produces an item, it puts it into the inspection box. Process B inspects the item to be checked; if it is qualified, it puts it into the packaging box, otherwise it throws it into the waste box. Process C packages the qualified products. Suppose the inspection box and the packaging box can each hold only one item at a time; PV operations are now used for management. To make the assembly line coordinate and work correctly, please complete the following program.
S1,S2,S3,S4 : 1.semaphore ; S1 := S2 := 1; S3 := S4 := 0; cobegin process A begin L1: 生产一件物品; 2.P(S1) ; 物品存检验箱; 3.V(S3) ; goto L1 end; process B begin L2: 4.P(S3) ; 从检验箱取物品; 5.V(S1) ; 检验; if 合格 then begin 6.P(S2) ; 物品存包装箱; end 7.P(S4) ; else 丢弃; goto L2 end; process C begin L3 8.P(S4) ; 从包箱取物品; 9.V(S2) ; 包装; goto L3 end; coend;
## Practice 4.0
Supplement 1: **What is a process? Briefly describe the main differences between a process and a program**
==**Answer**: It is the dynamic execution process of a program in a computer, including the program, data, and the process control block (PCB). It is the basic unit of resource allocation and scheduling, and has such characteristics as concurrency, dynamism, independence, and asynchronism.==
==**Differences from a program:**==
==State: a program is static, while a process is dynamic==
==Resources: a program does not occupy resources; a process is allocated resources when running==
==Correspondence: one program can correspond to multiple processes, while a process corresponds to only one program at a certain time==
Supplement 2:
Suppose there is a driver and a conductor on a bus, and their activities are as follows:
Driver: Conductor:
Start the vehicle Sell tickets
Drive normally Open the doors
Stop at the station Close the doors
Please analyze the synchronization relationship between the driver and the conductor, and how to implement it with PV operations.
**==Answer**: Define two semaphores:
`S1` with an initial value of `0`, used to indicate whether the conductor has closed the doors; `0` means not closed, `1` means closed;
`S2` with an initial value of `1`, used to indicate whether the driver has stopped at the station; `0` means not stopped, `1` means stopped.==
==**Driver**==begin 定义信号量 S1 = 1; // allow the conductor to start working 定义信号量 S2 = 0; // the conductor waits for the stop notification
plain L1: P(S1); // wait for the conductor to close the doors 启动车辆; 正常行车; 到站停车; V(S2); // notify the conductor that the bus has stopped at the station goto L1; end;
**==Conductor==**begin 定义信号量 S1 = 1; // allow the conductor to start working 定义信号量 S2 = 0; // the conductor waits for the stop notification
plain L2: P(S2); // wait for the driver’s notification of stopping at the station 开车门; 售票; 关车门; V(S1); // notify the driver that the doors are closed goto L2; end;
## Practice 5.0
1. **First-Come, First-Served (FCFS) Algorithm**
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
2. **Shortest Job First (SJF) Algorithm**
- **Selection rule**: select the job (process) that has already arrived and has the shortest service time to execute
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
## Practice 6.0
## Practice 7.0
---
## Practice 8.0
## Practice 9.0
## Practice 10
## Practice 11
Priority should be calculated according to the response ratio,
the formula is: (current time - arrival time + service time) / service time
## Practice 12
## 6. Deadlock
### Definition of Deadlock
**Definition**: multiple processes fall into a state of waiting for each other because they compete with each other for resources, causing these processes to be unable to execute or release resources, forming a deadlock
**Necessary conditions for its occurrence:**
**Mutual exclusion condition**: at least one resource cannot be shared, that is, only one process can use it at a time (==used exclusively)==
**Hold and wait (request and hold condition)**: a process already holds some resources and is requesting other resources, but these resources are already held by other processes
**No preemption**: allocated resources cannot be preempted; they can only be released by the process itself
**Circular wait**: there is a cycle in which each process waits for the resources held by another process, forming a loop
Methods for handling deadlock:
**Deadlock prevention**: avoid it by breaking one of the necessary conditions
**Deadlock avoidance**: dynamically allocate resources to ensure the system is always in a safe state, e.g., the banker's algorithm
**Deadlock detection and recovery**: monitor the system's resource allocation, detect deadlocks and take measures, e.g., terminating processes, rolling back operations
**Deadlock ignorance**: in some cases, the probability of deadlock is very small, so no handling is needed and it is left to the user to resolve
**Safe state**
**Concept**: it means that the system can, according to some process order (P1, P2, ..., Pn), allocate the required resources to each process Pn until the maximum demand of each process for resources is satisfied, enabling every process to complete successfully. If the system cannot find such a ==safe sequence==, the system is said to be in an ==unsafe state==.
# Formulas
### I. Process Scheduling Algorithms
1. **First-Come, First-Served (FCFS) Algorithm**
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
2. **Shortest Job First (SJF) Algorithm**
- **Selection rule**: select the job (process) that has already arrived and has the shortest service time to execute
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
3. **Highest Response Ratio Next (HRRN) Algorithm**
- Waiting time: current start time of the system - process arrival time
- **Response ratio**: (waiting time + required service time) / required service time
- **Selection rule**: select the job (process) with the highest response ratio each time to execute
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
4. **Round Robin (RR) Algorithm**
- **Turnaround time**: completion time - arrival time
- **Average turnaround time**: sum of the turnaround times of all processes / number of processes
- **Weighted turnaround time**: turnaround time / service time
- **Average weighted turnaround time**: sum of the weighted turnaround times of all processes / number of processes
- **Execution rule**: each process is allocated a time slice and executes in turn; after the time slice is used up, regardless of whether it has finished, the system switches to the next process
### II. Page Replacement Algorithms
1. **Optimal (OPT) Replacement Algorithm**
- **Predict the future usage of pages, so as to select the page that will not be used for the longest time in the future for replacement.**
- **Number of page faults**: count the number of times the required page is not in memory and needs to be loaded from external memory
- **Page fault rate**: number of page faults / length of the page reference sequence
- **Replacement rule**: select the page that will not be accessed for the longest time in the future for replacement (difficult to implement in practice; used for theoretical comparison)
2. **First-In, First-Out (FIFO) Algorithm**
- **It means the page that enters memory first is replaced out first.**
- **Number of page faults**: count the number of times the required page is not in memory and needs to be loaded from external memory
- **Page fault rate**: number of page faults / length of the page reference sequence
- **Replacement rule**: select the page that entered memory first for replacement
3. **Least Recently Used (LRU) Algorithm**
- **Eliminate the page that has been least recently used.**
- **Number of page faults**: count the number of times the required page is not in memory and needs to be loaded from external memory
- **Page fault rate**: number of page faults / length of the page reference sequence
- **Replacement rule**: select the page that has not been used for the longest time for replacement
### III. Disk Scheduling Algorithms
1. **First-Come, First-Served (FCFS) Algorithm**
- **Seek time**: the time required for the head to move to the specified track, calculated based on the number of tracks the head moves
- **Total seek time**: the sum of all seek times
- **Average seek length**: total seek length / number of disk requests
- **Processing rule**: process in sequence according to the arrival order of disk requests
2. **Shortest Seek Time First (SSTF) Algorithm**
- **Seek time**: the time required for the head to move to the specified track, calculated based on the number of tracks the head moves
- **Total seek time**: the sum of all seek times
- **Average seek length**: total seek length / number of disk requests
- **Processing rule**: select the track request closest to the current head position for processing
3. **SCAN Algorithm (Elevator Algorithm)**
- **Seek time**: the time required for the head to move to the specified track, calculated based on the number of tracks the head moves
- **Total seek time**: the sum of all seek times
- **Average seek length**: total seek length / number of disk requests
- **Processing rule**: the head moves in one direction, processing the disk requests along the way, until it reaches one end, then changes direction and continues processing
4. **Circular SCAN (CSCAN) Algorithm**
- **Seek time**: the time required for the head to move to the specified track, calculated based on the number of tracks the head moves
- **Total seek time**: the sum of all seek times
- **Average seek length**: total seek length / number of disk requests
- **Processing rule**: the head moves in one direction, processing the disk requests along the way; after reaching one end, it immediately returns to the starting end, and then processes in the same direction again
### IV. Cache Related
1. **Cache hit rate calculation**: number of cache hits / total number of accesses
2. **Average access time**: hit rate × cache access time + (1 - hit rate) × main memory access time
### V. Virtual Memory Related (Using Paging as an Example)
1. **Maximum number of pages for a user job**: size of the virtual address space / page size
2. **Number of blocks into which main memory space is divided**: main memory capacity / page size
3. **Page number**: INT (logical address / page size)
4. **Offset within a page**: logical address MOD page size
5. **Physical address**: block number × page size + offset within the page
6. Offset within a page: logical address MOD page size
If you enjoyed this, leave a comment~