操作系统笔记 from Neso

Index

https://www.youtube.com/watch?v=vBURTt97EkA&list=PLBlnK6fEyqRiVhbXDGLXDk_OQAeuVcp2O

1. Introduction to Operating System
2. Basics of OS (Computer System Operation)
3. Basics of OS (Storage Structure)
4. Basics of OS (I/O Structure)
5. Computer System Architecture
6. Operating System Structure
7. Operating System Services
8. User Operating System Interface
9. System Calls
10. Types of System Calls
11. System Programs
12. Operating System Design & Implementation
13. Structures of Operating System
14. Virtual Machines
15. Operating System Generation and System Boot
16. Process Management (Processes and Threads)
17. Process State
18. Process Control Block
19. Process Scheduling
20. Context Switch
21. Operation on Processes – Process Creation
22. Operation on Processes – Process Termination
23. Interprocess Communication
24. Shared Memory Systems
25. Message Passing Systems (Part 1)
26. Message Passing Systems (Part 2)
27. Message Passing Systems (Part 3)
28. Sockets in Operating System
29. Remote Procedure Calls (RPC)
30. Issues in RPC & How They're Resolved
31. Introduction to Threads
32. Multithreading Models & Hyperthreading
33. fork() and exec() System Calls
34. Threading Issues [fork() & exec() System Calls]
35. Threading Issues (Thread Cancellation)
36. Introduction to CPU Scheduling
37. CPU and I/O Burst Cycles
38. Preemptive and Non-Preemptive Scheduling
39. Scheduling Criteria
40. Scheduling Algorithms - First Come First Served (FCFS)
41. First Come First Served Scheduling (Solved Problem 1)
42. First Come First Served Scheduling (Solved Problem 2)
43. Scheduling Algorithms - Shortest Job First (SJF)
44. Shortest Job First Scheduling (Solved Problem 1)
45. Shortest Job First Scheduling (Solved Problem 2)
46. Scheduling Algorithms - Priority Scheduling
47. Priority Scheduling (Solved Problem 1)
48. Priority Scheduling (Solved Problem 2)
49. Scheduling Algorithms - Round Robin Scheduling
50. Round Robin Scheduling (Turnaround Time & Waiting Time)
51. Round Robin Scheduling - Solved Problem (Part 1)
52. Round Robin Scheduling - Solved Problem (Part 2)
53. Multilevel Queue Scheduling Algorithm
54. Multilevel Feedback-Queue Scheduling Algorithm
55. Scheduling Algorithms – Solved Problems
56. Process Synchronization | Chapter-6 | Operating System
    (To be continued)
57. Deadlocks | Chapter-7 | Operating System
58. Main Memory | Chapter-8 | Operating System
59. Virtual Memory | Chapter-9 | Operating System
60. File Systems | Chapter-10 | Operating System
61. File System Implementation | Chapter-11 | Operating System
62. Mass Storage Structure | Chapter-12 | Operating System

Notes

23 IPC

OS里运行的processes可以是independent processes or cooperating processes

• Independent processes: 无法影响和被影响系统里 其他进程
• Cooperating processes: 可以影响和被影响
  凡是share data的进程都是cooperating process
  进程合作的好处：
• Information sharing 共享信息
• Computation speedup 计算加速
• Modularity 模块化
• Convenience

IPC的两种基本模型：

1. Shared memory：给一片共享内存，然后合作进程可以通过读写这片共享内存交换信息。
2. Message passing： 合作进程通过交换message来进行通信
   

24 Shared Memory Systems

• 通信的进程需要建立一块共享内存
• 一般来说，共享的内存在发起方的address space里
• 其他进程如需通信，需要将共享内存attach在他们自己的address space上
• 通常OS会阻止不同进程访问彼此内存
• 共享内存会让2个或更多进程同意移除此限制
  一个使用例子是生产消费问题, 可以通过buffer of items来满足生产与消费。
  Buffer有两种
• Unbounded buffer：buffer size没有limit
• Bounded buffer: fixed buffer size, buffer为空消费者等；buffer为满生产者等

25,26,27 Message-Passing Systems

不用共享内存，在分布式环境里尤其有用。
需要同时拥有收发能力。
进程发送的Message可以是固定长度也可以是可变长度。
Fixed size: 系统层面直接，编程层面困难
可变长度: 系统实现复杂，编程层面简单

进程之间需要有communication link，这个link有多种实现方式。可以逻辑上实现link并拥有send()/receive()操作的方法有：

• Direct or indirect communication
• Synchronous or asynchronous communication
• Automatic or explicit buffering
  同时有几个问题要解决：
  Naming
  Synchronization
  Buffering

Naming

需要通信的进程必须要有refer to each other的方法，可以direct or indirect communication

Direct communication

在direct communication里，每个进程必须明确地指出通信的接收方

• send (P, message) -send a message to process P
• receive (Q, message) - receive a message from process Q
  直连有如下性质：
• 每对想联络的process之间自动生成link, process需要知道对方身份。
• 每个link只关联两个process
• 每对process之间，只存在一个link
  这种方案展现了寻址里的对称性（symmetry in addressing): 收发方需要name the other来通信

一个直连方案的变种：发送方需要name接收方，接收方无需name发送方。

• send (P, message) -send a message to process P
• receive (id, message) - receive a message from any process; the variable id is set to the name of the process with which communication has taken place
  这种方案展现了寻址里的非对称性（asymmetry in addressing)
  这两种方案（symmetric and asymmetric）都有个缺点：limited modularity of the resulting process definitions。如果进程名称更改，则可能需要重新检查所有的其他进程定义。

Indirect communication

消息经由mailboxes或port收发。

• mailbox可被抽象地视为供进程存放移除message的物体
• 每个mailbox有unique identification
• 两进程只有同时拥有shared mailbox时才可以通信
  举例
• send (A, message) -send a message to mailbox A
• receive (A, message) - receive a message from mailbox A
  间接连有如下性质：
• 只有双方进程共享shared mailbox时，link才能建立
• 每个link能关联两个及以上process
• 每对通信的process之间，可以存在多个不同的links, 每个link对应一个mailbox
  mailbox可以由进程或者操作系统拥有。

Synchronization

进程间的通信通过send()和receive() 基元/primitives来实现。基元的实现可以有不同设计。消息可以是blocking或nonblocking, 也称之为synchronous和asynchronous。
收发X阻塞分阻塞，4种情况

Buffering

无论通信是直接还是间接，被进程们交换的信息都栖息在一个临时队列里。这种队列可以有三种实现：
Zero capacity: 队列长度为0. 发送者被block直至接受者收到消息。
Bounded capacity: 队列长度为n, 最多存n个messages. 如果link满了，sender会被阻塞，直至队列有新的空。
Unbounded capacity: 队列长度无限，sender永不阻塞。

28 Sockets

• A socket is defined as an endpoint for communication.
• A pair of processes communicating over a network employ a pair of sockets-one for each process.
• A socket is identified by an IP address concatenated with a port number.
• The server waits for incoming client requests by listening to a specified port. Once a request is received, the server accepts a connection from the client socket to complete the connection.
• Servers implementing specific services(such as telnet, ftp and http) listen to well- known ports(telnet 23, ftp 21, http 80)
• All ports below 1024 are considered well known; we can use them to implement standard services

29,30 RPC

RPC是一种通信协议，可以让一个program通过网络去请求另一台机器上的服务，而无需知道网络细节。

• 与IPC机制在很多方面相似，但是因为是跨环境，所以需要用 message based communication scheme来提供远程服务。
• 与IPC对比的是，RPC交换的messages都是well structured, 所以不只是packets of data。
• 每个消息都会发给远端系统里监听port的RPC daemon, 信息里包含了identifier of被执行的function和传递的参数
• 之后function被执行，output由另一个message返回

The semantics(语义) of RPC 让client能向远端host invoke(调用）a procedure如本地调用一般

• RPC系统通过在客户端提供一个stub来隐藏通信细节
• 一般来说，每个独立的remote procedure有一个独立的stub
• 当client要调用remote procedure时，RPC系统会call对应的stub, 传递需要的参数。这个stub会确定服务器上的端口并把参数序列化（marshal the parameters)
• 参数序列化包含把参数放入能通过网络传输的特定格式。
• 然后stub将message通过message passing发送给server
• 服务端类似的stub接受此message并调用服务器procedure
• 如果需要，返回值以相同方式被返回client

RPC有一些问题

• Data presentation: eg big-endian和little-endian.
• A: 解决方法是RPC定义了data的machine-independent representation，比方XDR(external data representation)。客户端参数序列化时就包括了把数据转换成XDR，服务器端反之亦然。
• 因为网络问题导致RPC失败，重复并被执行多次。
  A: 解决方法是OS必须保证messages只被执行正好一次。
• 在standard procedure call里，procedure call's name is placed by the memory address of the procedure call。RPC scheme也需要类似的binding of 服务端和客户端端口，客户端怎么知悉服务端port number? 他们又不共享内存。
  A:

1. Binding information可以是predetermined, 通过fixed port addresses. 程序编译后，服务器无法改变该服务端口。
2. Binding可以由rendezvous mechanism(同步汇合机制）来动态搞定。一般操作系统会提供一个rendezvous(也叫matchmaker) daemon在固定的RPC port上。客户端发送含有RPC名称的消息给rendezvous daemon, 请求它所需执行的port address。服务端返回端口信息，RPC调用可以发送到那个端口直至process terminates或者服务器挂了。