OS - Overview

OSレビュー / オペレーションシステム

OS基礎の重要事項まとめ

目次

1. オペレーティングシステム the Operating System
2. プロセスとスレッド Processes and Threads
3. 並行処理 Concurrency
4. デッドロック Deadlocks
5. 食事する哲学者の問題 Dining Philosophers’ Problem
6. パーティショニング Ways of Partitioning
7. ページング Paging
8. 参考文献

オペレーティングシステム the Operating System

• オペレーティングシステムは、Primitive Processes、System Software、Virtual Memoryで構成されています。リソースを管理し、アプリケーションとハードウェア間のインターフェイス的役割を果たします。
• OS=Kernel。
• Kernelの目的：To directry communicate with harware。
• メモリを追加する要求がある場合は、カーネルモードでのみ可能なので、ユーザーモードでアプリケーションを実行している場合は、OSを呼び出して、カーネルモードに変更する必要があります。
• プログラムがKernel/Userモードかの確認は、Program Status Wordで行えます。
• MicrosoftにはHardware Abstraction Layer - HALという機能があり、これはOSとハードウェア間のコミュニケーションに使われます。
  (the Hardware Abstraction Layer is a layer of programs that allows the OS to interact with the hardware)
  
  https://microsoft.fandom.com/wiki/Architecture_of_Windows_NT

プロセスとスレッド Processes and Threads

• プログラムを実行すると、プロセスを作成する為OSが呼び出されます。「プログラム」は一連の命令のことを指し、「プロセス」はContext、データ、およびコードで構成されます。 2つのプロセスが同じホスト内で相互にコミュニケーションをとるためには、OSが呼び出され、IPCーinter process communicationが呼び出される必要があります。各プロセスにはそれぞれ独自のメモリスペースが割り当てられ、この割り当てられたメモリを超過しようとした場合は、OSが呼び出されなければいけません。

• context of a process includes address space, stack space, virtual address space, register set image,
  make a snapshot image of its associated kernetl data and also update its current state of the process.
  　

• プロセスが作成されると、Process Control Block -PCBが作成されます。 PCBには、context>プロセスに割り当てられたリソース、レジスター、ローカル変数、スケジュール、リンケージ（linkages）、ファイル、およびPMTが保存される。

• 7 States for a process:

1. New
   →新しいプロセスが作られる

2. Ready
   →プロセスは実行を待つため列に並ぶ

3. Running
   →それらのコンテキストがCPUレジスタに取り込まれ、実行される

   • if a thread in the running state calls "wait()" on a semaphore, the tread is in Running state.

4. Blocked / Wait
   →Time interruptやtrap（0で除算し算出する）、またblocking system call（retrive file）が原因で実行を継続できず、再び実行するためにOSを介さなければならない。←context switch発生
   　A context switch takes place when the OS must save current CPU registers into MM and exchange it with the next process in the ready state.

5. Suspend Ready
   →サスペンション状態をコントロールするMedium Scheduling Algorithmにより管理される。プロセスはスワップされ、適切なキュー（待ち）に配置される。この際、プロセスはメインメモリからセカンドメモリに移される。

6. Suspend Blocked
   →サスペンション状態をコントロールするMedium Scheduling Algorithmにより管理される。プロセスはスワップされ、適切なキュー（待ち）に配置される。この際、プロセスはメインメモリからセカンドメモリに移される。

7. Terminated / Exit
   
   https://media.geeksforgeeks.org/wp-content/uploads/20190604122001/states_modified.png

スレッドが作成されると、Processはメモリ所有権、Threadはexecutionの単位になります。スレッドには、Threrad Control Block-TCBと呼ばれる独自のcontrol blockがあります。 TCBには、Schedule, Context, Local Variableがあります。
※Scheduler: to determine how long a process can stay alive in a running state
スレッドには、OSを呼び出さずに、他のスレッドと通信し、同じプロセスのスレッドと同じメモリスペースにアクセスできます。processとは異なり、threadには、READY, BLOCKED, RUNNINGの3つの状態しかありません。他の4つの状態は、プロセスレベルで発生する状態です。1つのスレッドが中断されると、すべてのスレッドが中断されます。スレッドには、カーネルレベルのスレッド、ユーザーレベルのスレッド、ハイブリッドスレッドの3種類があります。 OSがスレッドのタスク要件を満たしている場合は、カーネルレベルのスレッドを使用でき、それに伴いOSはこれらのスレッドのスケジュールを作成し、contextと、それらを実行するために必要なスタック（ローカル変数）を管理します。ユーザーレベルのスレッドは、OSがスレッドの概念をサポートしていない場合に使用されます。たとえば、Unixはmonolithicで、スレッドをサポートしていません。したがって、プログラマーは、スレッド、そのスケジュール、スタック、および概念をシミュレートするためのライブラリを作成する必要があります。これにより、プログラマーがプログラムを実行できるスケジュールを指示することができるという利点があります。ユーザーレベルのスレッドの主な欠点は、1つのスレッドがブロックされると、システムがそれを1つのプロセスと見なすため、すべてのスレッドがブロックされることです。最後のタイプのスレッドはhybrid threadであり、両方の長所を活かすことができます。ハイブリッドレベルのスレッドを使用すると、プログラマーは、軽量のプロセスに各スレッドを単独で配置することで、どのスレッドを優先するかを決定できます。軽量プロセスは、kernelレベルのスレッドで実行されるコンテナのことです。そして、OSはスレッドをサポートし、registersとlinkagesの作成、およびscheduleを処理します。
Threads are useful since they allow asynchrony, that is when the OS must service a thread, it can do a context switch and run a different thread. This allows for better time resource management as a single CPU can only run one process/thread at a time.
（スレッド＝DJ）

https://sites.google.com/site/sureshdevang/thread-vs-process

並行処理 Concurrency

Concurrencyには、asynchronyとparallelismの2つのタイプがあります。 Concurrencyは有益ですが、threadがお互いにアドレス空間を共有していることで問題が発生する場合があります。同時実行ということは、プロセスは1つのatomic instructionとして実行されないため、thread/processがインストラクション下にあるのに、context switchを行う必要が出てくる可能性があり危険です。この問題は毎回のcontext switchで発生するわけではありませんが、1つのatomic instruction下で実行する際は、データの安全を考慮し、この問題を回避する必要があります。この事はCritical sectionと呼ばれるもので解決でき、interruptsやpreemptionが発生するのを防ぎます。
　Critical Sectionは小さなatomic instruction下にあり、matual exclusionする必要があります。critical sectionには同時に複数のprocess/threadは入れません。またプロセスは非常に短かい間のみcritical sectionにいられます。特定のリソースに一度にアクセスできるのは1つのthreadであるという事です。Matual exclusionは、言い換えると、system busは、特定の時間にone processからのみmain memoryへのアクセスを許可します。システムバスは便利ですが、より高いレベルの相互排除が必要ですが、その解決策としてPettersonsアルゴリズムが提案されました。Petersonsアルゴリズムは、同時に実行された2つのスレッドに対し、critical sectionに入ることが可能かのみを確認しフラグを与えるというものですが、それだけの確認では、両スレッドとも同時にcritical sectionに入れるかの確認をすることにより、両方ともフラグが下がってしまうもしくは上がってしまう可能性があります。この解決策としてPetersonsはスレッドが互いに順番を提供できるようにし、critical sectionへ入ることができるか確認する順番を交互にローテーションすることにしました。
　->semaphores
semaphoresはシグナルを使用して、各threadがcritical sectionに入れるかどうかを指示します。(- the semaphonres are used to signal whether a thread can enter a critical section)まずセマフォが作成されると、シグナルが配置されます。 スレッドがクリティカルセクションに入ろうとすると、ひとまず待機の指示が出ます。もしシグナルが上がっている場合、スレッドはクリティカルセクションに入ります。 シグナルが下がっている場合、スレッドはブロックされ、ブロック待機となります。クリティカルセクションが使用可能になると、シグナルが呼び出され、ブロックされていたスレッドがクリティカルセクションに入ることができます。セマフォは、作成時にカウンターが1に設定され、スレッドがクリティカルセクションに入るとカウンターがマイナスされる（decrement）というアルゴリズムで実装されます。もしカウンターは負でスレッドがクリティカルセクションに入ることができる場合は、カウンターを+1に変更します。


https://msl-network.readthedocs.io/en/latest/concurrency_async.html
https://commons.wikimedia.org/wiki/File:Parallel-concurrent.png

デッドロック-deadlocks

• Requirements:

  1. Mutual Exclusion (2つのスレッドが同時にcritical sectionにアクセスできない。e.g.,最初に持ったフォークが正しいと信じ込み離さない) ->semaphorescould be a high-level solution for mutual exclusion @ critical section
  2. Hold and Wait(ガンコ、他のフォークが欲しいと分かっていながら、一旦手にしたものを手放せない)
  3. No Preemption（割り込みできない）
     　- Preemption: Forcefully take away the process that holds a resource.
  4. Circular Wait（最後の人が自分のフォークがないため永遠に待ちの状態に。）

• Solutions:

  1. Prevention (before it hapeenes、４つの条件のうち１つ取り除く必要がある。mutual exclusionはプリンターなどには適用できない)
  2. Avoidance (e.g., a banker's algo)
     • Deadlocks are possible but constant vigilance is maintained
  3. Detection

2 types of resources

1. Consumable resources (signals, keyboard inout)
2. Reusable resources (libraries, memory)

食事する哲学者の問題 Dining Philosophers’ Problem

Solutions of Dining Philosopher problem

1. Deadlock Prevention
   →allwing only 4 philosophers in at any given time (the last one should wait till all 4 will be done.)
2. Semaphores : to avoid mutual exclusion
   →resource ordering (give a number to a fork and you are only allowed to pick the HIGHEST number of forks)

---

メモリ管理-5つの用件(Memory Management -needed for the use of multiprocessing)

1. sharing
2. protection
3. relocation (e.g. how to move register and processess stored in memory around)
4. logical organization (プログラムがデータを格納)
5. physical organization（プロセスが実行される時に使用される。＠main memory）
   →The Hardware Memory Management Unit (@ CPU) computes the translation from logical address to physical address.

数式：Logical address→Physical address
PMTLookUp(logicalAdd/ PgSize) * PgSize + logicalAdd % PgSize;

https://www.geeksforgeeks.org/requirements-of-memory-management-system/

パーティショニング Ways of Partitioning

Partitioning Methods
※ it is not necessary for memory to be saved in a contiguous manner, since memory has constant search time.

1. fixed
   →同じサイズのメモリブロックを作成して、その中にプロセスを配置する。
   プロセスが作成されると、このメモリブロックの1つが割り当てられますが、内部が断片化され、多くのメモリが無駄になる。
2. dynamic
   →複数のサイズのブロックをon the fly で割り当てるため、内部の断片化は減るが、外部の断片化が起こる。（この問題は対処可能。）
   i.e., Static Array
3. buddy
   ・Best fit
   →断片化は少ないが、n個のブロックを検索し、それぞれをチェックする必要があるため、オーバーヘッドが大きくなる。
   ・First fit
   →プロセスが、最初にフィットするメモリブロックを探すが、すぐに内部フラグメンテーションが発生する。
   ・Next fit
   →シンプルかつ効率的で、実は最も適した方法。
4. paging ※next chapter
   →同じ大きさの小さなメモリブロックをページと呼び、プロセスも同じ大きさのパーティションに分割されるため、断片化はほとんど起こらない。
   ページサイズはビット倍数に制限されており、OSがシフト操作で容易に求めることができる。
5. segmentation
   →複数のセグメントサイズを使用。（multiples of bits）
   オーバーヘッドが少なく、後々、より多くのメモリの割り当てが必要となった時、プロセスの拡張がしやすい。

ページング Paging

page ≒ frame

• Paging: Retrives processess from the secondary memory into main memory
• Paging is a concept that arises due to the need to partition memory for different processes.
• ページングでは、どのメモリブロック（frames）が特定のページを保持しているかを追跡する必要があり、これはPage Map Table -PMTを介して行われる。
• PMTはprocesses PCBに格納されており、HMMUが、変換のためにアクセスする。
• PMTは、フレームにページを一致させるとともに、使用、変更、および現在のビットを維持する。これはlook up problem（OSがまずPMTをチェックし、次にメインメモリ内のフレームを探さなければならない）を引き起こすが、この問題は、HMMUとともにCPU内部に存在するTranslation Lookaside Buffer -TLBによって解決される。TLBに対応するプロセス情報、つまりページがあれば、OSはPMTをチェックするために呼び出される必要はない。ただ、TLBの記憶容量には限りがあり、どのページをキャッシュに残すかを決めなければならないという課題がある。
• 4つの解決策：
  • LRU
    　→最後に使用されたページを削除するもので、しばらくは再び使用されない
  • Optimal
    　→将来どのページが必要になるかを知る必要があ流ため、不可能
  • FIFO
    　→最も重要なページを消してしまう可能性があるため、プロセスにとって有害
  • Clock Page Replacement Algorithm
    • →今日多くのキャッシュで使用されている。ページが故障したとき、Clock Page Replacement Algorithmが使われる。
      ・ページが使用されているときはTLBは1に。使用されていない時は0
      ・ページ障害が発生したときは、TLB内のに、nページを探し回るポインタが存在しており、ポインタが0に設定されたbitを見つけると、ページが使用されていないことを認識し、メモリ内の別のページと交換する。
      
      source: https://www.geeksforgeeks.org/translation-lookaside-buffer-tlb-in-paging

---

メインメモリには、Resident set　とWorking setがあり、プロセスが機能するためには、使用するページ（Working set）がメインメモリのResident setsに入っていなければならない。しかし、メモリの容量は限られており、実際はごく一部がworking set、残りのプロセスは、Virtual Memoryで保持される。
(For use, working set should be in resident set @ main memory.
But as memory capacity is limited, little is in working set, and remaining is in Virtual memory.)

Virtual Memory

• Compensate for physical memory shortage
• Temporarily transfer data from RAM to disk
  • (プログラマが「RAMには利用可能なメモリよりも多くのメモリがある」と思い込ませること。)

.

What is the resident set and working set of a process?

• Resident Set :- Set of a process's pages that are currently exist in memory,these pages may be referenced without generating a page fault. This set might differ in size from a process's working set, which is the set of pages that must be in memory for a process to execute efficiently

• Working Set:-- A program's favored subset of pages in main memory .Number of pages depends on the working set window size.
  （https://practice.geeksforgeeks.org/problems/what-is-the-resident-set-and-working-set-of-a-process）

https://upload.wikimedia.org/wikipedia/commons/3/32/Virtual_address_space_and_physical_address_space_relationship.svg

• Page Fault
  • プログラムがRAM(Physical memory)に格納されていないmemory blockにアクセスしようとしたときに発生する。
  • fixプロセス：データをstrage(HDD/SSD)を、Virtual Memoryを介して、RAMに送る。

https://www.geeksforgeeks.org/page-fault-handling-in-operating-system/

difference between Process switch and Thread switch

• Thread switch: virtual address space is remaining the same and thus has the same content in the cache, so there is no need for TLB.

  • A translation lookaside buffer (TLB) is a memory cache that stores the recent translations of virtual memory to physical memory.

• Process switch: Must invalidate the TLB cache since virtual address space does not remain the same.

Difference between Program and Process

• Program: Executing a program = just compiled. then the OS will generate a PROCESS to execute a program.

• Process: process = job = = instance = program code that has been loaded into a computer's memory so that it can be executed by the CPU(central processing unit).

• when the programmer runs a program, our OS creates a process.

principle of locality

• Principle of locality = locality of reference: Let a computer program access only a very small memory space at any single instance during execution.?
• Caching the useful data centers around a fundamental property of computer programs

Context Switch

Context Switch is to switch the process to run.
When it occurs in the system, it stores the old running process’s status in the register and assigns the CPU to a new process to execute its task.

Processor Affinity

• a process can have an affinity for one CPU out of multiple CPUs.
• Improves cache performance : Processor affinity is useful when a heavy program like video rendering. When we decide the code for only that task, it ensures that the core of the process is always dedicated to the task. It improves performance because ir reduces cache problems as there is no delay with a dedicated core.

Logical / Physical address

Hardware Memory Management computes translation from Logical address to Physicall address

user mode

• To prevent kernel crash.
• MS‑DOS allowed all user processes to access the kernel directly, without OS control and
  supervision. Why is this not allowed by more modern, widespread operating systems?

Context:

• replacement mechanism when main memory runs out
  • page fault can happen in FIFP algo: we throw out the oldest page we brought in, but if its still in use, there will be a page fault.

参考文献

• Modern Operating Systems by Andrew S. Tanenbaum, Herbert Bos