(No image to view, please download it in the group~) Chapter 3: The relationship and difference between processes and programs:
1) A program is an ordered collection of instructions, with no inherent meaning of execution. It is a static concept.
2) A process is the execution of a program on a processor. It is a dynamic concept.
3) A process has concurrent characteristics and can operate concurrently with other processes.
4) A process is the unit for resource allocation and processor scheduling.
5) One program can correspond to multiple processes (processing different data sets such as I, C, P).
6) A process consists of a program segment, a data segment, and a process control block.
4. Process states and transitions:
A process is created when initiated and terminated when revoked. During its lifecycle, it generally has three states, as shown in Figure 3-4. In different systems, more states can be set for processes. Commonly used primitives include: creation, revocation, waiting (blocking), awakening, process delay primitive and delayed awakening primitive, process suspension primitive and process activation primitive, P operation, V operation. Process control is part of the kernel's function but not all of it.
Multiple processes need to coordinate their operations to solve four problems:
1. Synchronization and mutual exclusion of processes
2. Communication between processes
Types: shared memory system; message system; communication using shared files (pipes).
Reasons for deadlock: insufficient resources; improper process progression order.
Necessary conditions for deadlocks: mutual exclusion; non-preemption condition; request and hold condition; circular wait.
Methods to resolve deadlocks: prevention: avoidance (safety checks); detection (monitoring programs); recovery (these systems take no measures, once a deadlock occurs, user intervention is needed to resolve it, such as ending front-end applications, restarting, etc. Unix and Windows both adopt this method).
3. Processor scheduling:
Three-level processor scheduling: job scheduling, process scheduling, and intermediate scheduling.
4. Threads:
3.3.1 Concept of threads:
Threads are smaller units of activity than processes and represent one execution path of a process. (A single execution of a process without its own resources or memory.)
Threads can be described as follows:
1) A thread is one execution path within a process.
2) It has its own private stack and processor execution environment (especially processor registers).
3) It shares the main memory allocated to its parent process.
4) It is one of many threads created by a single process.
Comparison between threads and processes:
1. Scheduling: Threads are the basic units of scheduling, while processes are the basic units of resource ownership.
2. Concurrency: Not only can processes execute concurrently, but multiple threads within a process can also execute concurrently.
3. Resource Ownership: A process is an independent unit that owns resources, while a thread does not own system resources but can access all resources belonging to the process.
4. System Overhead: Creating or terminating a process incurs higher system overhead compared to creating or terminating a thread.
Chapter 4 (Memory Management. Fixed partitioning, dynamic partitioning, focusing on paging storage management):
Relative address: This is the address relative to the current page in the linked file. It may also refer to similar addresses, such as reference addresses.
Absolute address: This is the absolute position of the file on the network or locally.
Relocation: After a program is loaded into memory, the absolute address and relative address are different. The mapping or conversion from relative address to absolute address is called address relocation. According to the timing of address relocation, it can be divided into static relocation and dynamic relocation.
Dynamic relocation: Similar to fixed partitioning, mainly involving the base address and program length, which are placed in the corresponding registers of the MMU during program execution. (Typically, MMU components use page tables, now protected.)
Storage protection: Upper and lower boundary protection; storage key protection.
Fixed partitioning: Understand data structures and algorithms.
Logical address: Each address contains two parts, the page number and the offset within the page. Here, the page size is set to 4K, and the intra-page offset is represented by 12 bits.
Page size in paging systems is generally 1K, 2K, or 4K, as shown in the figure.
Page fault interrupt calculation (refer to slides);
Assume the sequence of pages is: P=1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, and assume the number of main memory blocks allocated to this job is 3. Calculate the number of page faults F and the page fault rate f (page fault rate = the ratio of the number of page faults to the number of page accesses over a period of time) when using FIFO and LRU algorithms for page replacement.
Solution: Main memory blocks m=3, using FIFO algorithm, the number of page faults and page fault rate are shown in the diagram below.
In the diagram, the P row represents the page access sequence, the M row represents the page numbers in main memory, where the ones marked with "+" are newly loaded pages. The columns in the M row are arranged in the order of loading, and the circled numbers indicate the pages to be replaced in the next moment. The F row indicates whether a page fault occurs, with "√" indicating a page fault.
The number of page faults is F=9 times, the page fault rate f=9/12=75%.
When using the LRU algorithm, how is the replacement situation?
Answer: 10, 83%.
Chapter 5:
I/O system includes various channels, device controllers, and devices, along with four major functional software modules (device management software) - hardware & software.
Functions of device controllers:
1. Receive and identify commands sent from the CPU or channel.
2. Implement data exchange: including data exchange between the CPU, memory, and devices.
3. Identify and report the status of the device.
4. Device address recognition: Used to identify the address of each device it controls.
(Multi-path systems where a microcomputer control mode controls only one device, but a controller can control multiple devices.)
Channel concept:
A channel is a dedicated processor capable of reading, writing, reverse reading, testing device status, controlling devices (such as tape rewinding, page changing, etc.), and controlling channel program jumps, thus having six types of instructions.
Channels complete input/output tasks by executing channel programs composed of channel instructions.
Classification:
There are typically three types of I/O channels: byte multiplexing channel, array selection channel, and array multiplexing channel.
Connection methods:
There are typically two connection methods for channels: single-path I/O system and multi-path system.
Concept of device independence: (User programs are independent of the specific physical characteristics of devices.)
To improve the adaptability and scalability of the OS, almost all operating systems currently implement device independence. The basic idea is that users do not directly use physical device names or physical addresses but instead use logical device names. Logical device names abstract the attributes of physical devices and are not limited to specific physical devices. For example, in DOS, the logical device name "con" corresponds to basic input/output devices, including keyboards and monitors, while the printer's logical name is PTR or LPT. Users do not care whether the printer is laser or inkjet; when one breaks, the system automatically detects and selects another good one, demonstrating device independence.
Characteristics and functions of device drivers:
Set up a process for each type of device;
Set up an I/O process throughout the entire system;
Do not set up a dedicated device processing process;
Functions:
Receive commands and parameters from the I/O process and convert the abstract requirements in the command into specific requirements;
Check the legality of user I/O requests. For example, if the disk is reading, write requests are not allowed, judged and blocked by the driver;
Read out and check the status of the I/O device, such as busy or idle, damaged or not, and start the device controller if ready;
Pass relevant parameters to the device controller.
Buffer technology: Maximum speed, how to achieve maximum speed, dual buffering is the limit, multi-buffering increases data volume.
Multi-buffering is not for increasing speed but for solving discontinuous input/output issues.
Question 13 on page 172 (Elevator scheduling is important)
Chapter 6:
File and file system concepts:
Files consist of bytes, which is an unstructured file or stream file. Currently, UNIX and MS-DOS systems use this file format.
Files consist of records, which are collections of related information. Records can consist of several data items, and the data item types can be character, numeric, Boolean, etc.
Windows supports these types of files:
Concepts of file logical structure and physical structure:
Logical structure: Record-based files, unstructured files.
The physical structure of a file refers to the storage structure form of a logical file on a physical storage device.
File access methods:
Sequential access; Random access;
Disadvantages of physical structures: Continuous files - like partition allocation in main memory, have fragmentation problems.
The main disadvantage of linked files - suitable only for sequential access; slower access speed;
Cannot randomly access because to read information from a certain block, all preceding physical blocks must be read sequentially, following the pointer to find the required block.
Record storage formula (calculation):
Method to determine the physical block address and relative address within the physical block of any logical record:
Determine the relative block number of the record based on its logical address. The calculation formula remains RBN=[LBA/PBL], [Next page Hai].
Look up the index table to determine the physical block number PBN.
Calculate the relative address within the physical block. The calculation formula remains: PBO=[LBA mod PBL]
Calculate the logical byte length ALBL within that physical block.
The calculation formula is as follows: ALBL=min[LBL, (PBL-PBO)]
Calculate the remaining byte length LBL and judge. If it is 0, return; if not 0, proceed to the next step.
The calculation formula is: LBL=LBA-ALBL
Calculate the logical address of the remaining part of the record. The calculation formula is: LBA=LBA+ALBL
Structure of FCB: File name; Internal name; User name
Writing relative paths and absolute paths, especially relative paths. (Page 181)
File system and file access protection measures: Passwords, encryption technology, access control.
Common access control technologies: (1) Access control matrix (2) Access control list
Management of disk free space: Bit map method (Hard drive, given the number of pages, tracks, sectors, asking how many words, bits, and possibly further questions: Which physical block number corresponds in the bit map?)
Bit maps are also known as bit vectors, a mapping structure.
The adopted method treats a certain agreed area of memory as a vector, representing a certain file storage device. Each bit in the vector corresponds to a physical block, and the length of the vector equals the number of blocks in the file storage device. It is agreed that "0" in a certain bit indicates that the block is free, otherwise "1" indicates it is occupied.
Chapter 1: Introduction to Operating Systems
1. The entire computer system is divided into four layers:
Machine layer - Instruction interface,
Operating system layer - Application programs
System layer - Job interface - Assembler, compiler, editor, debugger, system maintenance programs, database management systems, data communication programs. (API is the interface of the operating system to users.)
Application layer - Office automation systems, transaction processing systems, and various application software packages and program libraries.
2. Five basic functions of the operating system: Job management; Processor management; Storage management; Device management; File management
3. The formation and development of various systems in the operating system - Definitions and differences (Multiple-choice questions, specific applications). How concurrent execution occurs in a multi-programming system, how programs run Page 28, Question 8
4. Commonly used operating systems: Multi-programming batch processing operating system, time-sharing system, real-time system, embedded operating system - Definitions and differences. Learn more about embedded systems.
5. Performance indicators of the operating system: (Understanding) Different focuses vary. Emphasize which indicators (Key points)
Multi-programming batch processing - Resource utilization rate
Real-time - Response time
Time-sharing - Facilitates user interaction processing
6. Interrupt system: Composition; Hardware - Interrupt register and interrupt scanning mechanism, Software - Interrupt handling program.
General process of interrupt handling: Protect the scene; Analyze the cause of the interrupt, enter the corresponding interrupt handling subroutine, handle the corresponding interrupt, one interrupt corresponds to one interrupt subroutine; Restore the scene, exit the interrupt.
7. Programs related to the interrupt system are divided into
Relevant privileged programs (core programs of the operating system) - Respond to same-level interrupts
User programs and outer-layer system programs - Respond to all interrupts accordingly.
Chapter 2 Job Management and User Interface
1. User interfaces: Program interface; Command interface
Program interface: An interface used by programmers when writing source programs.
It consists of a set of system call commands (shortened as system calls). This is provided for programmers to interact with the operating system through assembly programs.
Assembly source programs can directly use these commands, high-level language source programs can only use procedure call statements, which are translated by the compiler into system call commands.
System calls are essentially some subroutines provided by the operating system.
Command interface: An interface used for job control.
That is, the job control interface, which is further divided into two major categories: online user interface and offline user interface.
Online user interface: Keyboard operation commands; Menu-driven way; Icon-driven way; Graphical user interface.
Offline user interface: Consists of a set of job control commands. These are interpreted and executed one by one by the system's command interpreter according to the operation manual.
2. Job, job step, job flow
Job: A collection of work that users require the computer system to perform in a single computation or transaction processing.
Job step: A relatively independent task that requires the computer system to perform is called a job step.
Job flow: A batch of jobs input in a certain sequence and running.
Steps in job processing: Editing, compiling, linking assembly, running.
3. Job input and output:
A. Early online input and output: Input or output under direct CPU control.
Jobs are loaded onto input devices (such as card readers, paper tape machines), then run by the CPU supervisory program to auxiliary storage (early magnetic tapes), and then selected by the scheduling program from the magnetic tape for execution.
B. Offline input and output: Host and satellite machine composition.
The satellite machine does not connect directly to the host but only interacts with external devices. The satellite machine transfers jobs from input devices to large-capacity backup storage (magnetic tapes, disks).
C. Spooling system: Refers to the offline I/O no longer using a separate satellite machine but instead completed by the host's channel and can work concurrently with the host. Mainly includes: Input program module and output program module (software)
The channel is the hardware foundation of the Spooling system.
4. Job scheduling
A. Four states of job status: Submission state, standby state, running state, completion state.
B. Control block (JCB, Job Control Block)
The system sets up a job control block for each job to record relevant job information.
JCB is a sign of the existence of a job.
C. Job scheduling
The program that completes job scheduling is called a job scheduling program.
Measuring scheduling performance: Average turnaround time, average weighted turnaround time.
Calculation:
The turnaround time Ti for job i is defined as:
Ti=Tei-Tsi (where Tei is the completion time of job i, Tsi is the submission time of job i);
The average turnaround time T for n jobs is:
T=(T1+T2+...+Tn)/n
The weighted turnaround time Wi for job i is defined as:
Wi=Ti/Tri (where Tri is the actual runtime of job i)
The average weighted turnaround time W for n jobs is:
W=(W1+W2+...+Wn)/n
Master various job scheduling algorithms.
5. Windows XP user interface
Windows XP user interface: Windows XP system commands, Windows XP GUI
Win32 API functions
(Windows XP system commands, Windows XP GUI - Command interface; Win32 API functions - Program interface)
Windows XP commands have the following characteristics:
Some commands can only be executed directly through the command line.
Copy, paste operations differ.
Can browse the content displayed on the screen at each step before and after.
Directly supports system-hung code table input methods.
Elements of the Windows XP graphical user interface: Desktop, windows, menus, dialog boxes.
API is the programming interface provided by the Windows operating system to programmers.
Win32 API functions refer to API functions used in 32-bit Windows systems.
Three major categories of Windows API: Windows OS/2 DOSIX
Here are the answers to the post-class calculation questions provided by the teacher:
Chapter 2:
10. Method: List + Formula
Answers:
(1) T=22, W=5.85
(2) T=18, W=2.72 or 163/60
(3) T=19.2, W=5.01
(4) T=14, W=2
13. Start moments (1, 2, 3, 4) are: 8, 10.1, 10, 10.6
Completion moments are: 10, 10.6, 10.1, 10.8
Turnaround times are: 2, 53/30, 1.1, 29/30; Average is: 175/120
Weighted turnaround times are: 1, 53/15, 11, 29/6; Average is: 611/120
Answers to Questions 4, 9, and 10 in Chapter 3 (Highlighted in red, Key Points)
Answer to Question 4:
main()
{
semaphore Aempty=m