운영체제

01 Intro

• assignment 0:  virtualbox랑 ubuntu(14.04) 다운받기

OS Basics

• Von Neumann architecture = CPU + Memory + Storage
• CPU = Register + PC + ALU 

“Three Easy Pieces” -  Virtualization, Concurrency, Durability

• Virtualization: The OS takes the physical resources and transforms into virtual form of itself(OS is often referred as virtual machine)
• Concurrency: multi-thread
• Durability: surviving failure(persistence)

When a program runs:

Fetch -> Decode -> Execute

• c에서 volatile을 쓰면 해당 변수에 접근할 때 마다 캐시 대신 메모리에 접근한다
• SSD: solid-state drives

02 Abstraction

• data abstraction 
• procedural abstraction
• lazily: on demand = not executed unless necessary
• memory load를 on demand로 한다
• 48쪽 memory 그림 사실은 거꾸로임 code(text)맨 아래, 그 위에 data, heap, 맨 위에 stack. stack은 밑으로 쌓이고 heap은 위로 쌓인다
• 49쪽 64bit architecture. 
• bss segment: guard page. 
• kernal space에는 접근할 수 없다
• process는 3개의 state를 가지고 있다 - running/ready/blocked
• 53쪽 실제 register context used by the xv6 kernel
• 54쪽 proc에서 중요한 것: mem, proc_state, parent, context, tf
• 57쪽에서 return value빼고 parent에서 child로 모두 복사됨. child의 return value(address)는 0임! -> parent와 child 구분법
• %>/.program의 parent: bash

03 Mechanism

OS는 physical CPU를 time sharing을 이용해서 공유해야 한다. 이 때 고려해야할 것 두가지는:

1. performance
2. control

68쪽의 경우 run이라는 행위가 언제 끝날지 모르기 때문에 문제이다. (ex)infinite loop

+ 다른 프로그램에서 io를 access할 수 없음

kstack - kernel의 stack. 8kb

1. esp는 stack, eip는 code(text)를 가리키고 있다.
2. write()를 실행하면
3. eip는 kernel space, esp는 kernel stack을 가리킨다.

System Call

• system call을 call할 때마다 trap이 발생함.
• return-from-trap: call한 user program으로 되돌아감

IDTR table에 base address를 제대로 셋팅해주기 전까지는 아무일도 일어날 수 없다. 어떻게 handle해야 할 지 모르기때문

kernel은 자신만의 heap, stack등 구조를 가지고 있지 않다. 왜냐하면 OS의 주인이기 때문에 필요가 없음 - 모든것에 접근가능함

linux의 모드에는 두가지가 있다 - protected/real

• protected에서는 CPU가 previleged instruction을 실행하지 못하게 함

76쪽 intel의 CPU

85쪽 CPU의 register는 kstack에 저장되어야함. syscall이 끝난 후에 실행되어야 할 프로세스는 kstack의 syscall부분 다음에 저장.

—

//과제1

• while문 내에서 quit을 입력할 때 까지 반복
• batch mode일 경우 한 줄 한 줄 실행한 후 break
• interactive mode일 경우 한 줄 실행한 후 반복

1. 명령어 한 개일경우
• 현재 프로세스에서 exec로 실행
2. 여러개일경우
• strtok을 이용해서 명령어를 분리하고 fork로 명령 개수만큼 프로세스를 생성 후 exec 하고 모든 프로세스가 끝날때까지 wait한다

• 프로세스에서 fork를 호출하면 내부에서 pcb를 생성한다
• os를 부트하면 제일 먼저 idt를 set up함. 마우스와 키보드가 작동하는 것도 interrupt handler가 일하기 시작했기 때문에 마우스와 키보드의 interrupt를 handle할 수 있게 되어서 이다
• kernel stack이 user stack과 별개로 존재하는 이유는 다른 쓰레드가 접근하지 못하게 하기 위함이다 + interrupt 이전의 cpu state를 저장하고 끝난 후 다시 원상태로 복원해주기 위해
• process A와 B를 왔다갔다 ㅏ하는것을 context switching이라고 한다. 바꿀 때 현재 cpu register 상태를 pcb의 register context에 저장해주고 바꾼 후 다시 돌아올 때 cpu register로 저장한 내용을 그대로 가져옴
• 96쪽의 esp, eax는 레지스터의 종류이다 
• 스택의 가장 밑은 return address이다. -> protocol임
• %esp는 value, (%esp)는 address
• 4(%esp)는 esp가 가리키는 곳에서 4바이트 이후의 포인터를 가져오라는 뜻임
• kstack에서 pop해서 context(eax가 가리키고있음)에 집어넣는다.
• 이 코드에서 순서를 하나라도 바꾸면 안됨
• 10~16줄을 차례대로 context에 옮긴다
• 따로따로 말고 한꺼번에 못하는 이유는 메모리가 physically 연결되어있지 않기 때문

04 Scheduling

• 자원을 필요로 하는 프로세스에 자원을 배정해주는 것
• 스케줄링의 성능을 판단하는 기준:  turnaround time, fairness
• FIFO(FCFS)
• Convoy effect때문에 문제가 생김: 맨 처음 도착한 것이 엄청나게 오래걸릴경우
• SJF(Shortest Job First)
• 짧은 job들이 긴 job 실행 중에 도착할 경우 문제가 생김
• STCF(Shortest Time-to-Completion First)
• A가 실행되던 중 더 짧은 것이 도착하면 짧은것을 먼저 실행하고 A의 나머지는 그 다음에 실행함
• 스케줄링 성능 판단의 새로운 기준! response time
• 처음 schedule된 시간 - 도착한 시간
• 앞에 job이 있을 때 현재의 job이 길다고 맨 나중에 실행해버리면 답답할것이다. 적은 amount의 response라도 해야함
• 이전의 스케쥴링들은 response time이 안좋음
• RR(Round Robin)
• 하나의 job을 time slice로 잘라서 실행
• response time 훌륭
• 어떤 system이냐에 따라 적절한 size의 time slice가 필요
• 너무 작을 경우 response time은 좋지만 context switching 할 때 오버헤드 발생
• 너무 클 경우 반대의 장단점.
• real-time system의 경우 슬라이스를 작게하는것이 좋다 ex)미사일
• Incorporating I/O
• I/O가 개입될 경우 CPU 활용도를 최대한으로!
• Multi-Level Feedback Queue(MLFQ)
• priority마다 queue를 만듦. 내부에서는 rr실행
• 예) 어떤 job이 CPU를 오래 점령하고 있으면 priority를 낮춤
• CPU를 오래 사용하지 않는 interactive job은 priority를 높은곳에 둠
• 만약 interactive job이 엄청 많다면 long running job은 실행되지 못할것이다 -> starvation
• 90%정도 완료될 경우 yield하면 됨
• rule 5: 주기적으로 boost 진행(모든 프로세스를 맨 위의 queue로 이동)
• Proportional Share
• job이 필요로 하는 resource를 수치로 나타낸 후 퍼센트를 부여한다(CPU 점유 시간의 비율)
• Stride Scheduling(보폭 스케줄링)
• (A large number)/(the number of tickets of the process)
• 보폭은 스케줄링 대상을 의미한다

//과제2 String Scheduling + MLFQ 

05 Memory Virtualization

• OS가 각 프로세스에게 가상의 memory space를 제공 -> 각각의 프로세스마다 CPU를 가지고 있다고 볼 수 있음
• 이전에는 메모리에 한번에 하나의 프로세스만 할당될 수 있었음. 효율성 .. 참담
• 그래서 Multiprogramming과 time sharing이라는 것이 나옴.
• 메모리에 여러개의 프로세스를 조금씩 할당하는 것
• 하지만 protection issue를 초래할 수 있음..
• 자기가 아닌 프로세스에 접근 가능할 수 있어서 다른 프로세스를 손상시킬 수 있다
• protection issue를 어떻게 resolve 하느냐
• 프로세스마다 address space를 만듬
• 실행되고 있는 프로세스에 관한 모든 정보를 포함하고 있는 애(program code, heap, stack 등)
• 힙은 아래를 향해 쌓이고 스택은 위를 향해 쌓이는 이유
• 둘 다 dynamic하게 쌓이거나 없어지기 때문에 딱딱 나누어 같은 방향으로 쌓이게 하면 비효율적일 수 있다
• Memory API
• malloc()
• system call이 아닌 library function이다
• free()
• new()
• delete()
• 포인터는 스택에 저장됨
• string을 allocate할 때는 \0자리까지(1byte) 해서 malloc해야함. 안그러면 string의 끝이 어딘지 알수 없으니까
• Memory Leak
• “valgrind”: 메모리 leak되는 곳을 찾아주는 프로그램
• unused code를 free해주지 않으면 메모리에 계속 쌓여서 메모리가 다 차면 프로세스가 죽어버림
• malloc은 brk라는 system call을 사용한다
• 그래서 직접 brk/sbrk를 사용하면 안됨! malloc이나 free 자신이 스스로 하기 때문에 따로 하면 충돌할 수 있다
• brk는 프로그램의 break를 확장할 때 쓰인다
• break: address space내의 heap의 끝 주소
• good memory allocation -> jemalloc.so 또는 tcmalloc.so  (so: shared object)
• LD_PRELOAD = “/usr/(local/)lib/libjemalloc.so._
• 이렇게 하면 lib.c가 아닌 저기에 define 되어있는 function들을 대신 사용함
• main호출 전에 실행하고 싶은 것이 있을경우 library에 정의하고 LD_PRELOAD에 메인함수 전의 directory에 해당 library를 정의해놓으면 된다
• LD_PRELOAD는 굉장히 고급스킬임
• Address Translation
• 프로세스가 가진 address space안의 local address(0~16kb)는 실제 physical memory안의 address(0~64kb내의 어떤 16kb만큼의 space)와 다르기 때문에, 두개의 address를 서로 바꿀 수 있어야함
• OS는 이 작업에 최대한 관여를 안하는 것이 좋음. 하드웨어로 처리하는 것이 가장 빠르기 때문에
• Assumptions
• 1) user의 address space는 memory에 연속적으로 위치해 있다
• 2) address space의 크기는 memory의 크기보다 작다
• 3) 모든 address space의 크기는 같다
• Hardware-based Address Translation(Dynamic Relocation)
• 하드웨어가 virtual address를 physical address로 번역한다
• 소프트웨어(운영체제)만을 이용하여 번역하면 아주 오래걸리기 때문에 하드웨어의 도움이 필요하다
• 34쪽에서 5번 번역해야함. 아주 비효율적.
• base and bounds register를 이용!
• address space에서 bounds register라는 것을 가지고 있게 한다
• bounds register: 내 address space의 크기 (or +base)
• physical memory에서 base register라는 것을 가지고 있게 한다
• base register: 해당 address space가 시작하는 위치 
• base부터 bound만큼의 address space가 있다는 것을 알 수 있다. (Virtual Address + base = Physical Address)
• 이렇게 하면 translation 자체에는 OS가 관여할 필요가 없게됨. base만 CPU가 알아서 더하면 되니까
• 단, OS가 꼭 관여해야 하는 부분이 있음
• process가 시작할 때: physical memory에서 address space를 위한 공간을 확보할 때 -> free list를 찾음(사용되지 않고 있는 physical memory의 범위)
• process가 끝났을 때: 
• context switch가 발생할 때: PCB에 base-and-bounds pair를 저장해야 함
• process당 하나의 base and bound를 쓰는 것의 단점
• 비효율적이다 왜냐하면 heap과 stack사이에 free(unused) space chunk가 생기게 됨
• Segmentation: 따라서 한 process의 code, heap, stack마다 각각의 base and bound를 생성!
• virtual address를 두 파트로 나눔: segment와 offset으로.
• segment: address space내의 code인지, heap인지, stack인지 indicate하는 부분
• 왜 segmentation fault라고 하냐: 나에게 허용된 segment의 base와 bound를 넘었기 때문에
• hardware support
• 각 segment가 어떤 방향으로 자라는지 알고있어야 함
• read/write/execute등 각 segment가 어떤 작업에 허용될 수 있는지 알아야 함
• bound를 absolute값으로 잡으면 메모리를 더 차지하게 됨

06 Free-Space Management

• finding a free chunk of memory that can satisfy the request and splitting it into two: when request for memory allocation is smaller than the size of free chunks
• 링크드리스트를 이용하여 관리
• 실제 메모리의 bound말고 주소공간의 heap을 증가시키고싶다. 그것이 미덕
• Coalescing
• free list의 여러 node들을 하나의 node로 합치는 것
• free list의 node들이 contiguous할 때만 coalescing할 수 있음. 만약 떨어져있으면 안 free한것들까지 포인터를 다 바꿔줘야하는데 이건 불가능에 가깝다
• free(void *ptr)
• 어떻게 free해 줄 포인터의 size를 아느냐???
• malloc으로 메모리 할당해줄 때 요구한것보다 조금 더 해서 size 정보 등을 저장해놓기 때문에 거기서 알 수 있음
• magic number: 현재 사용되고 있는 process인지?
• Segregated List
• Slab Allocator
• on demand하게(free list에서) 말고 같은 size의 cache를 미리 allocate하여 요청이 있을때 바로바로 제공 (kmem_alloc/ kmem_cache)
• Buddy Allocation
• Binary Buddy Allocation
• free space를 계속 반으로 나누어 요청된 메모리를 수용할 수 있는 최소한의 space를 제공
• coalescing할 때 나의 buddy만 check하면 됨

07 Paging

• essence of memory virtualization
• Segmented Architecture
• 장점: address translation이 빠르다(하나의 adder logic이면 가능)
• 단점: 
• 외부단편화(요청한 메모리 양에 비해 segment가 너무 작아서 안들어가는 경우)
• 내부단편화(제공된 메모리 양이 모두 사용되지 않아 낭비될 경우)
• Swapping 옵션 제한
• segment가 작을수록 fragmentation이 적게 일어남. 그럼에도 불구하고 엄청 작게 하지 않는 이유는 process에 대해 segment를 관리하기가 어려워지기 때문이다
• Page: multiple fixed-size segments with mapping table
• process의 address만을 나누지 말고(segmentation) physical memory space도 나누자
• page table은 process마다 생성됨 -> context switch가 일어날 때마다 base-bound pair도 저장해야하기 때문에
• 장점: flexibility + 
• free space를 squeeze 할 필요가 없음. 그냥 사용할 수 있는 페이지를 보고 제공하면 됨.
• Address Translation
• page number + offset
• Page Table은 handle 하기 어려울 만큼 커질 수 있음
• 그걸 address space에 저장??? 안돼…
• Physical memory에 저장하고 process마다 어디에 저장했는지 기억한다.
• PTBR(Page Table Base Register)(=CR3) 레지스터는 자신의 페이지 테이블의 base(처음)를 가리킨다.
• 뭘 하려면 PTBR이 가리키는 곳에 가서 어딘지 보고 그 주소의 메모리에 가서 정보를 가져옴..50 cycles…too much memory reference->MMU(Memory Management Unit)로 해결!
• MMU에는 TLB라는 것이 있어서 mapping table의 cache로 작용한다. Memory-Address간 translating 없이 아주 적은 cycle로 해결 가능
• 실제 주소 = CR3 + VP# * 4byte
• page table을 효율적으로 만들어야한다. 모든 page에 대해 64bit 안에 맵핑할 수 있도록
• code, stack, heap에 page 하나씩 세개의 페이지면 충분하다
• 페이지 테이블에 존재하는 flag:
• valid/protection/present/dirty/reference bit
• 페이징의 문제점:
• extra memory access
• memory utilization for page table
• 46, 47쪽:
• edi -> &array[0]
• edx -> i
• 4 -> &(array + i * sizeof(int))
• array는 위쪽 주소에 있다(4만) 왜냐하면 function 내부(stack)에 정의되어있기때문에
• 그래프의 의미: paging때문에 memory access를 한번 더해야한다(page table 한번+실제 값을 fetch하기 위해 한번)

08 Translation Lookaside Buffers

• 프로그램 실행 시간은 clock cycle 속도보다 cache에 의해 결정된다
• vpn: virtual page number

09 Concurrency

• multiple execution flows within a process
• 실행 단위: thread
• 각자의 program counter와 register를 가지고 있다
• address space가 바뀌지 않기 때문에 process간의 context switching 보다 빠르다

• race condition(=data race)
• 여러개의 스레드/프로세스를 동시에 돌릴 때 같은 변수를 수정하면 그 여러개만큼 수정되지 않을 때
• atomicity를 보장하기 위해 lock을 이용하여 임계 영역을 지정해주어야 함

• performance가 증가했다가 유지되지 않고 감소하는 이유(spinlock에서)
• 1. convoy effect
• t1이 락을 가지고있으면 다른 스레드들도 cpu를 사용(burn)하고 있지만 t1락이 풀릴때까지 뭔가를 process 할 수 없다. 따라서 이 경우에 멀티쓰레드 상황은 performance를 worsen할 뿐이다
• 그래서 critical section는 적으면 적을수록 좋다
• lock holder인 t1에게 cpu시간을 많이 주어서 언락을 빨리 할 수 있게 하면 좋다
• 2. cache invalidation
• 락홀더가 캐쉬에 있는 값을 바꾸면 다른 쓰레드들에게 값을 똑같이 바꾸라고 보내는 메시지. 메시지가 있는 동안에는 process를 할 수 없음
• 하드웨어의 메시지 (메모리 버스)
• moesi, mesi protocol
• Thread API
• process의 시작은 fork. thread의 시작은 start_routine
• join: 어떤 스레드가 끝났는지 안끝났는지 알 수 있는 방법
• BSP(Bulk Synchronous Processing): 한 태스크를 여러 스레드로 돌리고, 다음 태스크로 갈 땐 이전 스레드들이 모두 끝났는지 확인해야함
• trylock(lock이 되어있으면 failure, 안되어있으면 락 - opportunistic locking), timelock(일정시간 이후 락을 풀음)
• condition variables: thread의 상태를 나타냄(wait(=sleep)/signal(=wake))
• 락 안에서 자면 안됨. 아무도 깨울수가 없음…
• 그래서 락 안에서 잘 경우 바로 락을 풀어야함

10 Locks

• 두가지 상태가 있다: available = unlocked, acquired = locked
• pthread는 lock에 관련한 여러 api를 제공한다
• interrupt는 현재 execution flow를 방해할 수 있는 최상의 priority를 가진다
• lock에서 interrupt를 disable한다? 안됨. 다양한 문제가 발생한다
• atomic instruction을 사용하는 애와 안사용하는 애가 shared variable을 사용하기 원하면 atomicity를 보장할 수 없음. 따라서 모든 instruction이 atomic하도록 주의해야함!!
• 만약 어떤 variable이 발생하는 곳에 락을 걸면 그 variable이 나오는 모든 코드 부분에 똑같이 락을 걸어야함
• ticket lock에서 발생할 수 있는 문제: 같은 번호의 티켓이 두개의 프로세스에 발급될 경우(티켓 발급이 atomic하지 않을 경우)
• spinlock 해결방법
• spin하려고 할 때 yield한다
• context switch 비용 발생
• 따라서 critical section이 작을 때는 spin waiting 하고 클 때는 yield하면 좋다
• sleeping
• 이것도 주의할점이 있음. 영원히 잠드는 애가 발생할 수 있다
• futex
• 영원히 잠드는것을 방지
• two-phase locks
• lock을 두 단계(phase)로 나눔

11 File System

• file = named permanent storage
• data와 metadata를 포함하고 있다
• directory
• collection of files/directories
• file system은 logically continuous하고 physically spread하다. process에서의 page table처럼
• file allocation table(FAT)
• “direct” mapping table
• allocation 작업이 O(1)이기 때문에 아주 빠르다는 장점이 있다
• direct하기 때문에 search는 오래걸림(linear time)
• 따라서 general purpose에 적절하지 않음
• Inode
• fat와 달리 direct하지 않기 때문에 서치가 비교적 빠름(logarithmic time)
• mmap: system call로 하지 않고 memory operation으로 실행. a few cycle 뿐이기 때문에 시간이 아주 절약된다
• file system을 durable하게 만드는 방법
• write하는 것을 자주 저장(survive in short term)
• 데이터를 오래 저장할 수 있게 함
• 데이터를 여기저기 복제해놓아서 independence of failure를 보장

• RAID(Redundant Arrays of Inexpensive Disks)
• level이 올라갈수록 redundancy가 증가
• level 0: striping
• 라운드로빈을 이용하여 여러 디스크에 block을 나누어 저장
• performance와 capacity가 훌륭함
• 그림에서 (0,1,2,3)을 하나의 stripe set이라고 한다
• 실제 field에서 아주 기본적이고 중요한 technique
• no redundancy
• level 1: mirroring(=replication)
• redundancy가 존재하기 때문에(같은 data를 여러번 저장) 시간이 오래 걸린다
• level 4: saving space with parity
• 하나의 디스크를 추가하여 같은 stripe set에 있는 정보를 해당 디스크에 저장
• level 5: rotating parity
• parity block을 하나의 디스크가 아니라 전체 디스크에 돌아가며 저장
• 보통 0+1을 합쳐서 사용한다