0726学习笔记

操作系统-一些易错知识点

在计算平均访存时间时要注意快表TLB和页表的访问是串行还是并行的，也要注意页表是单级还是多级的
虚拟存储器的最大容量只和计算机的地址结构决定，实际容量和内存和外存有关
工作集不是驻留集的子集，只是数量要小于（不大于）驻留集的大小

一些你需要搞明白的概念：

链接，包括静态和动态

链接是将不同编译单元及其依赖库整合到一个统一逻辑地址空间的过程。根据发生时间不同，链接分为：

静态链接：在编译阶段将所有代码打包进可执行文件中；
动态链接：
- 加载时链接（Load-Time Linking）：程序加载时操作系统自动加载依赖库；
- 运行时链接（Run-Time Linking）：程序运行过程中手动加载库，例如通过 dlopen() 等函数调用。

类别	链接时间	控制方式	示例函数
静态链接	编译/链接阶段	编译器自动处理	-
动态链接（加载时）	程序加载阶段	操作系统自动处理	-
动态链接（运行时）	程序运行阶段	程序员手动调用	`dlopen`, `dlsym` 等

$>dive into the procedure of linking of a C code program(Gemini 2.5 pro)

The Final Step: Unraveling the Linking Process of a C Program

The journey from human-readable C code to an executable program culminates in a crucial, often-overlooked stage: linking. This final step in the compilation process is where all the disparate pieces of your program are brought together to create a single, functional executable file. The linker, a key component of the C toolchain, orchestrates this assembly, resolving references between different parts of your code and incorporating necessary library functions.

The compilation of a C program is a multi-stage process. First, the preprocessor handles directives like #include and #define. The preprocessed code is then compiled into assembly language, which is subsequently converted into machine-readable object files. These object files, however, are not yet ready to run. They are incomplete pieces of a larger puzzle, and it is the linker’s job to put them together.

The primary role of the linker is to take one or more object files, along with any necessary libraries, and combine them into a single executable file. A key function of the linker is symbol resolution. When you call a function in one C file that is defined in another, the compiler leaves a placeholder, or a reference, in the object file. The linker’s job is to find the actual memory address of that function in the other object file and replace the placeholder with this address. This ensures that when the program runs, the function call correctly jumps to the right location in memory.

Static vs. Dynamic Linking: Two Approaches to Integration

There are two fundamental ways a linker can incorporate external code into your program: static linking and dynamic linking.

Static Linking: In this approach, all the required library code is copied directly into the final executable file. This creates a self-contained program that does not rely on external libraries to be present on the system where it is run.

Advantages of Static Linking:
- Portability: The executable can be run on systems that do not have the required libraries installed.
- Potentially Faster Execution: Since all the code is in one place, it can sometimes lead to faster execution as there is no need to load external libraries at runtime.
Disadvantages of Static Linking:
- Larger Executable Size: Because all library code is included, the resulting executable file is larger.
- Inefficient Memory and Disk Space Usage: If multiple programs on a system use the same statically linked library, each will have its own copy, leading to redundant use of disk space and memory.
- Difficult to Update: To update a library, every program that uses it must be re-linked.

Dynamic Linking: In contrast, dynamic linking does not copy the library code into the executable. Instead, it only includes the names of the shared libraries that the program needs. The actual linking of the library code happens at runtime when the program is loaded into memory.

Advantages of Dynamic Linking:
- Smaller Executable Size: The executables are smaller as they only contain references to the shared libraries.
- Efficient Memory and Disk Space Usage: A single copy of a shared library in memory can be used by multiple programs.
- Easier Updates: To update a library, you only need to replace the shared library file; all programs that use it will automatically benefit from the update without needing to be re-linked.
Disadvantages of Dynamic Linking:
- Dependencies: The program will not run if the required shared libraries are not present on the system or if the version is incompatible.
- Slightly Slower Startup: There can be a minor performance overhead at startup as the dynamic linker needs to find and load the necessary shared libraries.

The Linking Process in Action with GCC

The GNU Compiler Collection (GCC) is a popular toolchain for compiling and linking C programs. The linking process can be performed as a separate step or combined with compilation.

To compile a C source file (.c) into an object file (.o), you can use the -c flag with gcc:

gcc -c my_program.c

This will create an object file named my_program.o. If your program is split across multiple source files, you would compile each one into an object file.

Once you have all the necessary object files, you can link them together to create an executable file using the -o flag to specify the output file name:

gcc -o my_executable my_program.o another_file.o

This command tells gcc to link my_program.o and another_file.o and create an executable file named my_executable.

Common Linker Errors

Errors that occur during the linking phase are known as linker errors. Some of the most common linker errors include:

Undefined Symbol/Undefined Reference: This is the most frequent linker error. It occurs when the linker cannot find the definition for a function or variable that has been declared and used in the code. This often happens when you forget to link an object file that contains the definition or mistype a function name.
Multiple Definitions: This error arises when the linker finds more than one definition for the same function or variable. This can happen if you define a function in a header file that gets included in multiple source files or if you link the same object file multiple times.

In conclusion, the linking process is the essential final act in the creation of a C program. By understanding how the linker works, the differences between static and dynamic linking, and how to use tools like gcc to control the linking process, developers can gain a deeper insight into how their code is transformed into a runnable application and more effectively troubleshoot common errors.

$>are there different categories of dynamic linking technique?(Gemini 2.5 pro)

Yes, there are different categories of dynamic linking techniques, each with its own timing and mechanism for connecting a program to the shared libraries it needs. The main distinctions lie in when the linking happens and who initiates it.

Here’s a breakdown of the primary categories of dynamic linking:

1. Load-Time Dynamic Linking (Implicit Linking)

This is the most common form of dynamic linking. When you compile and link your program against a shared library, the linker embeds references to that library directly into the executable file.

How it works:

At compile time: The linker records the names of the shared libraries the program depends on and the symbols (functions and variables) it uses from them.
At load time: When you run the executable, the operating system’s program loader (also known as the dynamic linker or runtime linker) reads this dependency information. It then locates the necessary shared libraries on the system, loads them into the process’s address space, and resolves all the symbol references before the program’s main function begins to execute.

Key Characteristics:

Automatic: The entire process is handled automatically by the operating system.
Dependencies are required at startup: If any of the required shared libraries are missing or incompatible, the program will fail to start.
Slight startup overhead: There is a small performance cost at program launch while the dynamic linker does its work.

2. Run-Time Dynamic Linking (Explicit Linking or Dynamic Loading)

This technique gives the programmer more control over the linking process. Instead of the operating system automatically loading libraries at startup, the program itself can explicitly load and unload libraries at any point during its execution.

How it works:

Programmatic Control: The program uses specific API calls (like dlopen(), dlsym(), and dlclose() on POSIX systems, or LoadLibrary(), GetProcAddress(), and FreeLibrary() on Windows) to manage shared libraries.
- dlopen() or LoadLibrary(): Loads a specified library into memory.
- dlsym() or GetProcAddress(): Retrieves the address of a specific function or variable within the loaded library.
- dlclose() or FreeLibrary(): Unloads the library from memory.

Key Characteristics:

Flexibility: Programs can decide which libraries to load based on runtime conditions. This is the foundation for a “plugin” architecture, where new functionality can be added to a running application by loading new shared libraries.
No startup dependency: The program can start even if the optional libraries are not present. It can then check for their availability and load them if needed.
More complex to implement: The programmer is responsible for managing the loading, symbol lookup, and unloading of libraries, which requires more code and error handling.

A Special Case: Lazy Linking

Lazy linking is an optimization often used with load-time dynamic linking to improve program startup time.

How it works:

Instead of resolving all function addresses when the program is first loaded, the dynamic linker defers the resolution of each function until it is actually called for the first time.
The first time a function in a shared library is called, a small piece of code (a “trampoline” or “stub”) in the program’s Procedure Linkage Table (PLT) transfers control to the dynamic linker. The dynamic linker then looks up the real address of the function, patches the PLT entry to point directly to it, and then calls the function.
Subsequent calls to that same function will then go directly to the function’s address without involving the dynamic linker, resulting in minimal overhead.

Key Characteristics:

Faster startup: By avoiding the upfront cost of resolving every single function, the program can start executing more quickly.
Minimal overhead on first call: There is a small performance penalty the very first time each dynamically linked function is called.
Transparent to the developer: This is typically a default behavior of the dynamic linker and doesn’t require any special coding by the programmer.

In essence, while load-time and run-time dynamic linking are the two main strategies, lazy linking is a common optimization that fine-tunes the performance of load-time linking. The choice between these techniques depends on the specific needs of the application, balancing ease of use, startup performance, and the flexibility to load code on demand.

卡特兰数，用于计算给定输入栈序列，所有可能的输出排列
$$ \frac{1}{n+1}\binom{2n}{n}=\frac{2n!}{(n+1)!n!} $$

英语-单词（词根词缀分开）

a vail
mock
gigantic
zoom
speci fication
pa nel
pre mise
sovereign
utter
deem
mono poly
spec ulate
con form