virtual memory: level of indirection

running user program

• create process and thread
  프로세스와 스레드를 만든다.
• setup virtual address of the program: code, data, stack
  프로그램의 가상 주소를 만든다.(코드영역, 데이터 영역, 스택 영역)
• load executable file
  실행 파일을 로드한다.
• start executables: passing parameters
  실행 파일 시작: 파라미터 전달

처음 프로그램이 로딩될 때 컴파일러가 없는 경우

OS(커널)가 컴파일러랑 똑같이 스택에 쌓아준다

file system도 virtual memory 기법과 유사하게 동작함

각각의 file이 실제 storage block에 함수로 매핑되는 구조 (버추얼 메모리가 물리 주소에 매핑되는 것 처럼)
file의 특정 offset을 storage block에 매핑하는 형태

OFFSET? (chat GPT)

"Offset"은 컴퓨터 메모리나 파일에서 특정 위치를 가리키는 값을 나타내는 용어입니다. 이 용어는 주로 메모리 주소나 파일 내의 위치를 나타내는 데 사용됩니다. 여기에서 메모리와 파일에서 offset에 대해 자세히 설명하겠습니다.

• 메모리에서의 Offset
  컴퓨터의 물리적 또는 가상 메모리에서 데이터의 위치를 가리키는 값입니다.
  프로그램이 실행되면, 해당 프로세스의 가상 주소 공간에서 데이터 또는 명령어를 찾기 위해 offset을 사용합니다.
  주로 바이트 단위로 표현되며, 0부터 시작하여 메모리 블록 또는 배열 내의 특정 위치를 가리킵니다.

• 파일에서의 Offset
  파일 내에서 데이터의 위치를 가리키는 값입니다.
  파일은 일련의 바이트로 구성되며, 파일 내에서 특정 위치에 접근하기 위해 offset을 사용합니다.
  일반적으로 파일의 시작 부분에서부터의 바이트 수로 표시됩니다. 예를 들어, 파일의 처음에서 100 바이트를 가리키는 offset은 100입니다.
  운영체제나 프로그래밍에서 offset은 파일 I/O 작업, 메모리 할당 및 관리, 포인터 산술 등 여러 가지 상황에서 사용됩니다. 예를 들어, 파일에서 데이터를 읽거나 쓸 때, 원하는 위치에 도달하기 위해 offset을 사용합니다. 또한 메모리 할당에서 특정 메모리 위치에 접근하거나 데이터 구조 내에서 원하는 요소에 접근할 때 offset을 사용할 수 있습니다.

예를 들어, C 언어에서는 파일을 읽거나 쓸 때 fseek 함수를 사용하여 파일 내에서 원하는 offset으로 이동할 수 있으며, 메모리 할당 및 포인터 산술에서도 offset을 사용하여 원하는 위치에 접근할 수 있습니다.

file system의 특이한 부분

메모리는 가상 메모리 주소가 부팅할때마다 바뀌어도 상관없지만 파일 시스템은 그러면 안된다.(영속성)
속도가 느리다. 그렇기 때문에 메모리 페이징은 MMU라는 하드웨어가 담당하여 빠른 속도를 맞출 수 있게 해준다.
그러나 file system은 느리기 때문에 소프트웨어로도 충분히 매핑 가능하다.
FAT, BTREE, indirect page table 등등 (페이징 방법들 → 3 easy piece 책에 나와있다.)

File: a logical unit of storage

• Identifier : pathname (path + filename)
• Location of data is identified by offset

OS subsystem maps the file to physical storage -> Let’s call it file system

위 그림에서 mode부터 size block count의 파란 부분이 파일의 metadata를 갖고 있는 inode이다.
파일의 내부의 index역시 디스크에 존재해야 한다.(영속성 - 지워지면 안 됨)

when to allocate physical block? vi 편집기에서 :w 엔터를 입력했을 때.(저장할 때)
이 때 :w는 어떤 시스템콜로 변환되는가? fsync(fd)

Any performance optimization for slow storage device?
데이터를 하나씩 입력할 때마다 disk에 저장하는 것은 매우 시간이 오래 걸리기 때문에
Dram에 데이터를 임시로 보관(page cache)했다가 저장할 때 disk에 쓴다.
이를 batching이라고 한다.
그러나 이때 두 개의 서로 다른 copy 가 존재하게 된다.(dram / disk) → 문제의 원인

Problem of using buffer cache

DRAM에 metadata와 data가 같이 저장되어 있음
inode에 파일 사이즈 등의 메타데이터가 저장되어 있다.

문제는 이를 디스크로 저장할 때 하드디스크는 두 데이터를 동시에 저장하는 기능을 제공하지 않는다. 만약 한 데이터를 저장 중에 크래시가 난다면…

Non-atomic update

Each storage has a unit of atomic updates (atomic = 더 이상 쪼갤 수 없다는 뜻)

• e.g., 4 KB in harddisk (4096 byte, 2^12)

만약 8kb 데이터를 저장하려 한다면 하드디스크는 4kb씩만 저장한다. 즉, 8kb가 완전하게 저장될 것이라는 보장은 할 수 없다는 것

application에서 이를 해결해야 한다. → 파일이 중간에 깨진 상태로 저장되는 오류가 나오는 이유

Crash consistency

file a의 내용을 foo 에서 bar 로 업데이트 후 저장하려고 할 때 바람직한 경우는 두가지이다.

• bar 로 파일의 내용이 성공적으로 바뀌거나
• 저장이 실패하더라도 foo가 완전히 남아있는 경우

1. a single write: write(/a/file, "Bar")
   이 명령어를 실행 중 크래시가 발생한다면 다음과 같은 경우가 나타날 수 있다.
   
   업로드에 실패하더라도 파일의 내용이 망가지는 것을 막기 위한 방법으로 다음 두 방법을 생각할 수 있다.

• 원본을 백업하는 방법 - roll back logging
• 새로 쓸 업데이트를 백업하는 방법 - write ahead logging

2. roll back logging
   create(/a/log)
   write(/a/log, "Foo")
   write(/a/file, "Bar")
   unlink(/a/log)
   문제는 컴파일러가 코드를 실행 중 log 에 write하는 코드와 file에 write하는 코드의 순서를 제멋대로 바꿔서 실행하는 경우가 있을 수 있고 이러한 경우에는 1번 경우과 똑같은 경우가 발생할 수 있다는 것이다.

3. rollback logging with ordering
   create(/a/log)
   write(/a/log, "Foo")
   fsync(/a/log)
   write(/a/file, "bar")
   fsync(/a/file)
   unlink(/a/log)
   이런 경우에 발생할 수 있는 문제점은 log 디렉토리(파일)에 백업은 남아있으나 write 중 크래시가 발생했는데 a 디렉토리에서 log 파일을 못 찾는 경우가 있을 수 있다.

4. correct version
   create(/a/log)
   write(/a/log, "Foo")
   fsync(/a/log)
   fsync(/a/)
   write(/a/file, "Bar")
   fsync(/a/file)
   unlink(/a/log)
   앞에서 언급한 모든 문제점을 해결했다.
   하지만 모든 파일을 이런식으로 두 번 저장한다면 심각한 성능 저하가 발생할 것이다.

protection & isolation

design: how to archive protection

• Preventing applications from executing some important
  instructions
  어떤 명령어는 kernel 만 쓸 수 있어야 함. 예) hlt - CPU를 idle상태로 바꿈
  
• Preventing applications from reading/writing other applications’
  memory
  다른 application의 메모리에 함부러 read write 할 수 없도록 막기.
• OS must regain control from applications
  임의의 application이 자원을 독점하지 않도록 → timer interrupt

timer interrupt

타이머 라고 불리는 하드웨어를 이용하여 일어나는 인터럽트로, 타이머 카운터가 특정 값에 도달했을 때 타이머 인터럽트를 일으킬 수 있다.

Requirement for protection

• Privileged instruction
  • Preventing applications from executing some important
    instructions
    중요한 명령이 privilege가 없는 어플리케이션에 의해 실행되는 것을 막는다.
• Memory protection
  • Preventing applications from reading/writing other
    applications’ memory
• (Timer) interrupt
  • OS must regain control from applications
    OS가 주기적으로 application으로부터 제어를 빼앗아 온다.

Separation of privilege

Clearly, OS must have higher privilege than application.
당연히 OS의 권한이 app보다 더 높다.
How can guarantee (or define) the privilege level?
그렇다면 어떻게 권한의 수준을 정할 수 있을까?
HW vs SW. who has more privilege? - hardware
하드웨어 vs 소프트웨어 중 더 권한이 높은 것은? = 하드웨어
하드웨어가 OS에게 privilege를 endorse 해주고 OS는 application에게 privilege를 부여한다.

Hardware Protection Mechanisms

Protection mechanisms

• Dual mode operation (or ring mode)
  - mode bit is provided by hardware
• Privilege I/O instructions 예)hlt
• Memory protection mechanism

ring mode (char GPT)

Ring mode는 운영 체제와 하드웨어 간의 보안 및 권한 관리를 위한 메커니즘 중 하나로, 다음과 같은 방식으로 작동합니다:

권한 수준:
Ring mode는 보안 및 권한을 다른 수준으로 분리합니다. 일반적으로 0부터 3까지의 숫자로 표현되며, 낮은 번호일수록 더 높은 권한을 나타냅니다. 일반적으로 다음과 같이 사용됩니다:
Ring 0 (최고 권한 레벨): 운영 체제 커널 및 중요한 시스템 작업을 수행하는 프로세스가 실행됩니다.
Ring 1 및 Ring 2: 중간 권한 레벨, 일반적으로 운영 체제 확장 또는 가상화와 관련된 작업을 수행하는 프로세스가 실행됩니다.
Ring 3 (사용자 모드): 일반 응용 프로그램이 실행되는 권한 레벨입니다.

주로 ring 0 과 ring 3이 사용된다고 한다.

보호 경계:
Ring mode는 권한 수준 간의 보호 경계를 설정합니다. 예를 들어, 사용자 모드 (Ring 3)에 있는 응용 프로그램은 운영 체제 커널의 Ring 0로의 직접 액세스가 불가능합니다. 이러한 경계는 비정상적인 동작이나 보안 위협을 방지합니다.

시스템 콜과 인터럽트:
운영 체제에서는 사용자 모드 (Ring 3)에서 커널 모드 (Ring 0)로 전환해야 하는 작업을 수행할 때 시스템 콜을 사용합니다. 시스템 콜은 운영 체제 커널에 권한을 요청하는 메커니즘을 제공하며, 커널 모드로 전환될 때 높은 권한을 부여합니다. 인터럽트도 시스템 레벨에서 하드웨어와 통신하고 시스템 레벨의 작업을 수행하는 데 사용됩니다.

보안 및 안정성:
Ring mode는 시스템의 보안과 안정성을 향상시킵니다. 사용자 모드에서 실행되는 프로세스는 일반적으로 제한된 권한을 가지고 있으며, 운영 체제 커널과 하드웨어 리소스에 대한 액세스가 허용되지 않습니다. 이로 인해 악의적인 응용 프로그램이 시스템의 핵심 부분에 접근하는 것을 방지합니다.
Ring mode는 다중 작업 운영 체제 및 가상화 환경에서 중요한 역할을 합니다. 이를 통해 운영 체제는 프로세스 간의 격리를 유지하고 시스템의 안전성을 확보합니다. 또한 가상화 환경에서는 가상 머신 간의 격리를 달성하는 데 사용됩니다.

Address Translation Concept

OS가 작성한 page table을 하드웨어(MMU)가 보고 정당한 주소가 아닐 경우 Page fault를 일으킨다.

segment descriptor 의 권한 설정

DPL영역의 값이 0이냐 3이냐에 따라서 권한이 달라지고 실행할 수 있는 명령어도 달라짐

page table entry 의 권한 설정

이 페이지가 유저 페이지인지 커널 페이지인지 확인하는 부분 - user / supervisor

dirty - 사용자가 code를 기록했는지 여부 → fsync시에 디스크에 기록해야하는지 여부

dual mode OS

kernel과 user는 protection 했지만…APP사이의 isolation이 필요함

isolation

Isolating one application from another

• data-access confinement
• control-flow confinement

이를 위한 방법 중 하나로 page table을 나누는 방법이 있다.

class로도 구현할 수 있다.

• instance A 와 instance B는 서로 isolation 되어있다.

isolation of file

모든 파일 접근은 OS를 통해서만. privileged insruction

이를 담당하는 부분이 Reference Monitor. 이를 따라 커널이 접근할지 말지 결정함

• Access control method
  • DAC and MAC
  • Capability-based access control
• Authentication of user and system (mutually distrust)
• Protected communication between the protection
  boundary
  - IPC: 다른 방법은 전부 막아놓고 이 API를 통해서만 프로세스간의 데이터를 공유한다.

IPC(chat GPT)

프로세스 간 통신(Inter-Process Communication, IPC)은 컴퓨터 시스템에서 다른 프로세스 간에 데이터를 교환하고 상호 작용하기 위한 메커니즘입니다. IPC는 다양한 상황에서 사용되며, 프로세스 간 데이터 공유, 동기화 및 통신을 가능하게 합니다. 아래에는 주요 IPC 메커니즘과 간단한 설명을 제공합니다:

• 파이프 (Pipe)
  파이프는 한 프로세스에서 다른 프로세스로 데이터를 전달하는 데 사용됩니다. 일반적으로 단방향 통신을 제공하며, 부모 프로세스와 자식 프로세스 또는 관련된 프로세스 간의 통신에 많이 사용됩니다.

• 명명된 파이프 (Named Pipe 또는 FIFO)
  명명된 파이프는 파이프와 유사하지만 이름을 가지며 독립적인 프로세스 간 통신에 사용됩니다. 여러 프로세스가 동시에 읽고 쓸 수 있습니다.

• 메시지 큐 (Message Queue)
  메시지 큐는 메시지를 전송하고 수신하기 위한 통신 메커니즘을 제공합니다. 메시지는 큐에서 비동기적으로 수신되며, 메시지 큐를 사용하여 프로세스 간 통신 및 동기화를 수행할 수 있습니다.

• 공유 메모리 (Shared Memory)
  공유 메모리는 두 개 이상의 프로세스가 메모리 영역을 공유할 수 있도록 하는 메커니즘입니다. 이를 통해 프로세스 간 데이터 공유가 빠르고 효율적으로 이루어질 수 있습니다. 그러나 데이터 동기화에 주의해야 합니다.

• 세마포어 (Semaphore)
  세마포어는 프로세스 간의 공유 자원에 대한 액세스를 조절하기 위한 동기화 메커니즘입니다. 세마포어는 크리티컬 섹션, 임계 영역 및 자원 공유에서 중요한 역할을 합니다.

• 소켓 (Socket)
  소켓은 네트워크 프로그래밍을 위한 IPC 방법 중 하나이며, 네트워크를 통해 데이터를 주고받을 수 있게 해줍니다. 소켓은 인터넷이나 로컬 네트워크에서 프로세스 간 통신에 사용됩니다.

• RPC (Remote Procedure Call)
  RPC는 원격 프로시저 호출을 통해 원격 프로세스와 통신할 수 있게 해줍니다. 클라이언트 프로세스는 원격 서버의 함수를 로컬 함수처럼 호출할 수 있습니다.

• 파일 기반 IPC
  파일을 공유: 프로세스는 파일을 생성하고 다른 프로세스는 해당 파일을 읽거나 쓰는 방식으로 데이터를 공유할 수 있습니다.
  메모리 매핑: 파일을 메모리에 매핑하여 공유 메모리와 유사한 방식으로 데이터에 접근할 수 있습니다.

IPC 메커니즘은 다양한 운영 체제 및 프로그래밍 언어에서 지원되며, 프로세스 간 통신 및 협력을 가능하게 합니다. 적절한 IPC 메커니즘을 선택하고 사용하면 다중 작업 및 다중 프로세스 환경에서 프로세스 간 효율적인 협력이 가능해집니다.

IPC - shared memory

같은 physical memory 영역을 사용하도록 os가 virtual memory를 설계함
Cache coherence를 통해 CPU의 코어끼리 같은 데이터를 공유할 수 있게 함

프로세서 p1에서 바꾼 내용을 p2에서 알 수 있게 하는 방법

• signal - 좀 느리다.
• polling - CPU를 항상 쓰지만 즉시 알 수 있다.

IPC - message passing

Process1의 데이터를 kernel에 카피 → 커널에서 Process2에 카피
프로그래밍이 쉽고 전달하는 데이터가 작을 때는 오버헤드가 적다.

Two types of sharing

• time sharing - CPU ⇒ scheduling
• space sharing - memory ⇒ page replacement (page eviction + swap)

mechanism 과 policy의 구분

• policy
  • what should be done?
  • Decision
  • pintos - round robin, fifo 등
• mechanism
  • how to do something?
  • tool for implementing policy
  • pintos - context switching 등

seperate policy from mechanism (반대 역시 마찬가지): policy 나 mechanism 중 하나가 바뀌어도 다른 쪽엔 영향을 끼치지 않도록 짜야한다.

policy 는 보통 하나의 function으로 작성 (pintos 에서는 next_to_run 함수)

time scheduling

언제 preemptive scheduler 가 쓰이는지 - multi program: interactive applictaion
예) 클라우드, 데스크톱

non-preemptive schedulter는? - application의 속도를 증가시킴 (context switching을 안 하기 때문)
예) 성능이 중요한 슈퍼컴퓨터의 경우

• FIFO (First In First Out)
  • 장점: 쉬운 구현
  • 단점: convoy effect (처음 들어온 task가 너무 오래 걸림)
• SJF (Short Job First)
  • 장점: convoy effect 해결
  • 단점: starvation 발생( 짧은 태스크가 많이 들어올 때)
• round-robin
  • 장점: no starvation
  • 단점: turnaround 시간이 길어짐 + MLFQ에서 해결할 수 있는 단점을 가지고 있다.
  • task마다 time slice가 짧을수록 좋은 경우, 길수록 좋은 경우가 있다.
  • 여러 경우에 맞춰서 round-robin queue를 여러 개 만들고 짧은 task에 우선순위를 주는 것이 MLFQ

page sharing

새로운 페이지를 allocation해야 하는데 memory가 가득찬 경우
특정 메모리를 빼서 disk로 보내야 하는 경우

Page replacement policy

• When a page fault occurs, the OS loads the faulted page from disk into a page frame of physical memory
  page fault 가 발생했을 때, OS는 디스크에서 faulted page를 물리 메모리의 page frame 으로 load한다
• At some point, the process used all of the page frames it is allowed to use
  어느 순간, 프로세스는 사용할 수 있는 페이지 프레임을 모두 사용하게 된다.
  - This is likely (much) less than all of available memory
  이건 사용할 수 있는 메모리 전부보다 (훨씬) 적을 것이다.
• When this happens, the OS must replace a page for each page
  faulted in
  이런 상황이 일어난다면 OS는 각 페이지 폴트에 대해서 페이지를 교체해야 한다.
  - It must evict a page (called victim) to free up a page frame
  페이지 프레임을 반환하기 위해 (Victim이라 불리는)페이지를 evict쫒아내야 한다.
• The page replacement algorithm determines how this is done
  페이지 교체 알고리즘이 이 작업을 어떻게 수행할지 결정한다.

페이지 교체 알고리즘의 원칙

똑같은 일을 했을 때 page fault 의 수가 적은 것이 좋다.
access된 것이 계속 access되는 것이 좋다.
앞으로 접근할 미래의 page에 대한 정보는 과거의 기록들로부터 추론한다.
가장 오랫동안 안 읽은 페이지 = 앞으로 읽을 일이 적은 페이지
이 알고리즘이 LRU
loop가 있는 프로그램 덕분에 LRU가 꽤 잘 작동한다.

하지만 LRU는 제대로 구현하려면 많은 비용이 든다. 최근에 읽은 페이지를 linked list의 맨 앞으로 옮기면 모든 page에 page fault 가 발생해서 그 때마다 리스트를 다시 만들어야 하기 때문

그렇기 때문에 clock이라는 방법으로 LRU를 비슷하게 따라하는 방식을 사용한다.

페이지에 접근했을 때 access라는 비트를 1로 바꾼다.
page의 linked list를 뒤에서부터 scan했을 때 해당 access 비트가 0일 때까지 스캔 후 0인 페이지를 disk로 보낸다. access 비트가 1이라면 0으로 바꾸고 넘어간다.(LRU의 tail을 찾는 것을 어느정도 흉내냄)

how to design OS

• Monolithic Kernel (성능 중시)
  • All kernel components runs in the same kernel address space
  • 현대 사용되는 컴퓨터 시스템
• Microkernel(커널 일부가 다운되어도 시스템은 돌아가는 안정성 중시)
  • Moving some OS subsystems to user-level
  • 자율주행, 군수 등 안정성이 성능보다 더 중요한 분야