[정글] WEEK 08 | 오고야 말았다 핀토스

핀토스는 2004년 스탠포드에서 만들어진 교육용 운영체제로

이를 기반으로 카이스트 권영진 교수님 주도 하에 만들어진 카이스트 핀토스 과제를 진행한다.

 

Subject	Done
스레드	✔
사용자 프로그램
가상 메모리
파일 시스템

 

📌 키워드 정리하기
QEMU

• 하이퍼바이저는 가상 머신을 생성하고 구동하는 소프트웨어, 가상 머신 모니터라고도 불림
• 하이퍼바이저 운영 체제와 가상 머신의 리소스를 분리해 가상 머신의 생성과 관리를 지원함
• qemu는 가상화 소프트웨어 중 하나로, 리눅스 OS를 소프트웨어적으로 구현하여 환경을 제공함

 

Memory Leak

• 메모리 누수, 컴퓨터 프로그램이 필요하지 않은 메모리를 계속 점유하고 있는 현상

 

Race Condition

• 경쟁 상태, 둘 이상의 입력 혹은 조작의 순서 등이 결과 값에 영향을 줄 수 있는 상태
• 두 개 이상의 프로세스 혹은 스레드들이 하나의 자원에 접근하기 위해 경쟁하는 상태

 

Deadlock (교착 상태)

• 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

 

Use After Free (UAF)

• 힙 영역에서 할당된 공간을 해제하고, 메모리를 다시 할당 받을 때 같은 공간을 재사용하면서 생기는 취약점
• UAF 취약점 : 할당했던 메모리 해제 후 재할당해서 사용할 때 같은 크기로 재할당 할 경우 이전에 사용했던 메모리 공간을 재사용하게 되는데, 이때 이전에 할당했을 때처럼 사용하는 경우에 발생

 

▼ 문제점

• 한 포인터 A를 힙에 할당한 후 해제하고 같은 크기로 또 다른 포인터 B를 할당하면 같은 주소가 할당됨
• 이전에 할당 후 해제했던 A에 접근이 가능하며 같은 주소값을 가짐
• 또한 해당 주소의 데이터를 바꾸면 (overflow data) 이전에 사용했던 A 변수의 데이터도 변경 가능하게 됨

 

Time-sharing system

• 시분할 시스템 = CPU 스케줄링 + 다중 프로그래밍

 

Context Switching (문맥 교환)

• 현재 진행하고 있는 태스크(프로세스, 스레드)의 상태를 저장하고 다음 진행할 태스크의 상태 값을 읽어 적용하는 과정

 

Scheduler
1) Round Robin (RR)

• 라운드 로빈 스케줄링, 시분할 시스템을 위해 설계된 선점형 스케줄링 중 하나
• 프로세스들 사이에 우선 순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식
• CPU를 사용할 수 있는 기회를 프로세스들에게 공정하게 부여하기 위해, 각 프로세스에 일정시간을 주어 돌아가면서 기회를 부여하는 운영 방식

 

2) Priority

• H가 L에게 CPU 점유를 넘겨주면 M이 L보다 우선 순위가 높으므로 점유권을 선점하여 실행, 즉 순서가 M -> L -> H가 되기 때문에 H보다 M이 더 우선 실행되는 문제
• H가 본인이 가진 우선순위를 L에게 일시적으로 양도하여, 자신의 실행을 위해 L과 동일한 우선순위를 가져 우선적으로 실행될 수 있도록 하는 방법

 

3) Multi-Level Feedback Queue Scheduler (MLFQS)

• 짧은 작업을 먼저 실행시켜 반환시간을 최적화 하고자 함
• 사용자에게 응답을 빨리 전달하기 위한 응답 시간을 최적화 하고자 함

 

4) 4BSD

• Berkeley Software Distribution, 동적 우선순위 스케줄링 알고리즘 개념 적용

 

5) Nice

• CPU 스케줄링 알고리즘에서 우선순위 값에 따라 CPU 시간 비율을 결정, 우선순위 = nice 값

 

Thread

스레드끼리 힙/데이터/코드 영역을 공유하고, 스택 영역만 복사하여 소유

 

Interrupt

• 인터럽트 : 태클, 일시정지
  
  • 인터럽트 발생
  • 현재 프로세스 정보 (문맥) 저장
• 인터럽트 처리 후 다시 돌아와야 하기 때문에 현재 프로세스 정보를 저장하는 것
• 스레드가 많아지면 오버헤드도 많아짐

 

Process Control Block (PCB)

• 프로세스 제어 블록, OS의 스케줄러에 의해 스케줄링 되는 것
• OS의 스케줄러에 의해 context switching되는 프로세스의 정보 단위

 

Thread Control Block (TCB)

• 스레드 제어 블록, 프로세스에 있는 스레드 라이브러리에 의해 스케줄링 되는 것
• 스레드 라이브러리에 의해 context switching되는 스레드의 정보 단위

 

Timer Interrupt

• 일정 시간일 때 발생되는 인터럽트, 타이머가 일정한 시간 간격으로 CPU에게 인터럽트를 요청함

 

Timer Sleep

• 일정 시간동안 프로세스를 일시정지 하는 것

 

Synchronization

1) Semaphore

• Signal 메커니즘 세마포어 count가 0일 때 non-signable, 1일 때 signable
• 누구든 세마포어의 count를 up/down 할 수 있음

 

2) Lock

• Locking 메커니즘
• Lock의 주인이 존재하여 mutex는 lock의 주인만 릴리즈 가능

 

3) Condvar

• Conditional variable
• 특정 조건이 성립할 때까지 기다림
• 특정 조건이 성립되면 기다리고 있는 스레드 1개 혹은 여러개를 깨움

 

📌 프로젝트 이해하기

Testing PintOS

• build 디렉토리에서 make check 실행, 각 테스트에 대한 합격 또는 불합격 메세지가 출력됨
• 테스트가 실패하면 실패 이유에 대한 몇 가지 세부 정보도 출력함
• 개별적으로 테스트하려면 result 디렉토리에서 명시적으로 파일 생성 make tests/threads/alarm-multiple.result
• 테스트를 다시 실행할 때, make clean 실행
• make check VERBOSE=1과 같이 make 명령줄에 VERBOSE=1을 지정하여 각 테스트의 진행 상황을 관찰할 수 있음

 

Introduction

• 최소한의 기능을 갖춘 스레드 시스템이 제공되며 여기에 Synchronization을 추가하는 것이 과제
• threads/devices 디렉터리에서 작업, threads 디렉토리에서 컴파일
• 과제 들어가기 전에 '동기화' 개념에 대해 배우고 들어갈 것

 

Synchronization

• 동기화를 구현하는 가장 간단한 방법은 인터럽트를 비활성화 하는 것
• 즉 CPU가 인터럽트에 응답하지 못하도록 일시적으로 차단하는 것
• include/threads/synch.h: 세마포어, 락, 모니터 관련 작업
• 모든 동기화 문제는 인터럽트를 끄면 쉽게 해결 가능, 인터럽트가 꺼져 있는 동안에는 동시성이 없으므로 경쟁 조건이 발생하지 않기 때문
• 하지만 대부분의 동기화 문제를 세마포어, 잠금 및 조건 변수를 사용하여 해결할 것
• 인터럽트 비활성화 방법은 커널 스레드와 인터럽트 처리기 간에 공유되는 데이터를 조정할 때 유일하게 사용됨
• 인터럽트 핸들러는 잠들 수 없기 때문에 잠금을 획득할 수 없음, 이때만 인터럽트를 꺼 커널 스레드 내에 보호되도록 할 것

 

Semaphores

• Down or P: 값을 감소시킴
• Up or V: 값을 증가시킴, 대기 중인 스레드 깨움
• 리소스를 사용하기 전 Down, 리소스 사용을 마친 후에 Up 하는 것
• 세마포어는 내부적으로 인터럽트를 비활성화하도록 설계되었음
• sema_try_down: 기다리지 않고 down 실행을 시도함
• lib/kernel/list.c: 대기중인 스레드 목록을 유지 관리

 

Locks

• Lock은 초기값이 1인 세마포어와 같다고 생각하면 됨
• 락에선 Release, Acquire이란 용어를 사용함, Up = Release / Down = Acquire
• 락을 획득한 스레드만 락을 해제할 수 있음
• lock_try_acquire: 기다리지 않고 acquire 실행을 시도함

 

Monitors

• 모니터 = 동기화되는 데이터 + 모니터 잠금 + 하나 이상의 조건 변수
• 스레드는 모니터 잠금을 획득한 후 데이터에 접근 가능, 이걸 "In the monitor"라고 함

 

Optimization Barriers

• 베리어란 메모리를 순차적으로 접근하도록 보장하기 위한 것
• 즉 CPU가 반드시 소스 코드 상에 나온 순서대로 Instruction을 실행하도록 지시
• 최적화 베리어를 사용하는 이유는 컴파일러가 모르는 사이에 다른 스레드나 인터럽트 핸들러에 의해 데이터가 비동기적으로 변경될 수 있기 때문
• 또 다른 이유는 코드의 순서를 강제할 수 있음, 컴파일러는 코드의 순서를 바꿔 실행할 수도 있음

 

Understanding Threads

• 거의 모든 곳에 printf를 추가하여 무슨 일이 어떤 순서로 발생하는지 확인해볼 것
• 반드시 하나의 스레드가 실행되고 나머지는 비활성화, 스케줄러는 다음에 실행할 스레드를 결정
• GDB 디버거를 사용하여 컨텍스트 스위치를 통해 어떤 일이 발생하는 지 확인해볼 것

 

Memory Allocation

Pintos에는 두 개의 메모리 할당자가 있음, 하나는 페이지 단위로 메모리를 할당하고 하나는 모든 크기의 메모리를 할당함

 

1) Page Allocator

• include/threads/palloc.h: 페이지 할당자 관련
• 한번에 한 페이지씩 혹은 한번에 여러 개의 연속 페이지 할당 가능

2) Block Allocator

• threads/malloc.h: 블록 할당자 관련
• 페이지 할당자로부터 페이지를 얻을 수 있는 한 작은 할당은 항상 성공, 하지만 큰 할당은 항상 페이지 할당기를 호출해야 함
• 여기서 두 개 이상의 연속된 페이지가 필요할 경우 조각화로 인해 실패할 수 있음
• 따라서 대용량 할당의 횟수를 최소화 하는 것이 중요

📌 프로젝트 파고들기

Todo	Done
Alarm Clock	✔
Priority Scheduling	✔
Advanced Scheduler

 

Alarm Clock

• 정해진 시간만큼 호출 스레드의 실행을 일시 중단함, 적절한 시간 동안 기다린 후 준비 대기열에 넣으면 됨

 

Priority Scheduling

• 현재 실행중인 스레드보다 우선 순위가 높은 스레드가 준비 목록에 추가되면 현재 스레드는 즉시 새 스레드에 양보
• 또한 스레드가 세마포어, 잠금, 조건 변수를 기다리고 있을 때 우선 순위가 가장 높은 대기 스레드가 먼저 깨어나야 함
• Priority Inversion(우선 순위 역전): H는 L을 기다리고 M이 준비 목록에 있으면 H는 기회를 얻지 못함, L이 보유하고 있는 동안 H 우선순위를 L에 기부한 다음 L이 잠금해제하면 H가 획득할 수 있게 됨
• 여러 우선순위가 단일 스레드에 기부되는 다중 기부, 중첩 기부 등 다양한 상황을 모두 고려할 것

라운드 로빈 → 우선 순위 스케줄링

1) Priority Scheduling

• Ready List 우선 순위 정렬
• 새 스레드가 현재 스레드보다 우선 순위 높다면, 새로운 스레드가 선점되어야 함

 

2) Synchronization

• 세마포어, Condition Variable 사용하여 스레드 간 Race Conditioin 방지
• 이때, Wait List 우선 순위 정렬

 

3) Priority Donation

• Priority Inversion 예방하기 위해 Danation 구현

 

세마포어

• 은행에는 직원 수가 제한이 있음
• 직원 수가 0이 아니면 서비스를 받을 수 있음
• 직원 수가 0이면 대기
  
  • 공유자원에 대한 접근 조절
  • 동시 접근 제어 및 상호 배제

조건 변수

• 특정 업무를 처리하기 위해서는 특정 업무 처리 창구를 이용해야 함
• 여기서 이 창구가 조건 변수에 대항
  
  • 조건에 만족할 때까지 스레드들을 대기시키는 역할
  • 특정 조건에 따른 대기와 깨어남 조절

정리

• condition : 기다리는 손님들
• lock : 웨이터
• lock_release : 웨이터가 딴 테이블로 가버림
• sema_down : 웨이터가 음식을 가져다 줌, 손님은 대기에서 벗어남
• lock_aquire : 웨이터는 다시 손님과 상호 작용 가능

Advanced Scheduler

• 우선 순위에 따라 실행할 스레드를 선택하는 기능인 Advanced Scheduler를 구현할 것
• Pintos 시작 시 스케줄링 알고리즘 정책을 선택할 수 있도록 구현할 것
• 기본적으로 우선순위 스케줄러가 활성화되어 있어야 하지만, 커널 옵션이 있는 4.4 BSD 스케줄러를 선택할 수 있어야 함
• 4.4 BSD 스케줄러가 활성화되면 스레드는 더 이상 자체 우선 순위를 직접 제어하지 않음