[CS] 면접 대비 OS

운영체제란

하드웨어를 연결하고 응용 프로그램과 하드웨어 사이에서 인터페이스 역할을 하며 시스템의 동작을 제어하는 시스템 소프트웨어

운영체제는 시스템의 자원과 동작을 관리하는 소프트웨어이다. (시스템의 역할 구분에 따라 운영체제의 역할은 모두 다를 수 있다.)

프로세스 관리

프로세스, 스레드
스케줄링
동기화
IPC 통신

저장장치 관리

메모리 관리
가상 메모리
파일 시스템

네트워킹

TCP/IP
기타 프로토콜

사용자 관리

계정 관리
접근권한 관리

디바이스 드라이버

순차접근 장치
임의접근 장치
네트워크 장치

항목별로 하나씩 좀 더 자세히 살펴보자

프로세스 관리

운영체제에서 작동하는 응용 프로그램을 관리하는 기능이다.

어떤 의미에서는 프로세서(CPU) 관리하는 것이라고 볼 수도 있다. 현재 CPU를 점유해야 할 프로세스를 결정하고, 실제로 CPU를 프로세스에 할당하며, 이 프로세스 간 공유 자원 접근과 통신 등을 관리하게 된다.

저장장치 관리

1차 저장장치에 해당하는 메인 메모리와 2차 저장장치에 해당하는 하드디스크, NAND 등을 관리하는 기능이다.

1차 저장장치(Main Memory)
- 프로세스에 할당하는 메모리 영역의 할당과 해제
- 각 메모리 영역 간의 침범 방지
- 메인 메모리의 효율적 활용을 위한 가상 메모리 기능
2차 저장장치(HDD, NAND Flash Memory 등)
- 파일 형식의 데이터 저장
- 이런 파일 데이터 관리를 위한 파일 시스템을 OS에서 관리
- FAT, NTFS, EXT2, JFS, XFS 등 많은 파일 시스템들이 개발되어 사용 중

네트워킹

네트워킹은 컴퓨터 활용의 핵심과도 같아졌다.

TCP/IP 기반의 인터넷에 연결하거나, 응용 프로그램이 네트워크를 사용하려면 운영체제에서 네트워크 프로토콜을 지원해야 한다. 현재 상용 OS들은 다양하고 많은 네트워크 프로토콜을 지원한다.

이처럼 운영체제는 사용자와 컴퓨터 하드웨어 사이에 위치해서, 하드웨어를 운영 및 관리하고 명령어를 제어하여 응용 프로그램 및 하드웨어를 소프트웨어적으로 제어 및 관리를 해야한다.

사용자 관리

우리가 사용하는 PC는 오직 한 사람만의 것일까? 아니다.

하나의 PC로도 여러 사람이 사용하는 경우가 많다. 그래서 운영체제는 한 컴퓨터를 여러 사람이 사용하는 환경도 지원해야 한다. 가족들이 각자의 계정을 만들어 PC를 사용한다면, 이는 하나의 컴퓨터를 여러 명이 사용한다고 말할 수 있다.

따라서, 운영체제는 각 계정을 관리할 수 있는 기능이 필요하다. 사용자 별로 프라이버시와 보안을 위해 개인 파일에 대해선 다른 사용자가 접근할 수 없도록 해야 한다. 이 밖에도 파일이나 시스템 자원에 접근 권한을 지정할 수 있도록 지원하는 것이 사용자 관리 기능이다.

디바이스 드라이버

운영체제는 시스템의 자원, 하드웨어를 관리한다. 시스템에는 여러 하드웨어가 붙어있는데, 이들을 운영체제에서 인식하고 관리하게 만들어 응용 프로그램이 하드웨어를 사용할 수 있게 만들어야 한다.

따라서, 운영체제 안에 하드웨어를 추상화 해주는 계층이 필요하다. 이 계층이 바로 디바이스 드라이버라고 불린다. 하드웨어의 종류가 많은 만큼, 운영체제 내부의 디바이스 드라이버도 많이 존재한다.

이러한 수많은 디바이스 드라이버들을 관리하는 기능 또한 운영체제가 맡고 있다.

프로세스 & 스레드

프로세스 : 프로그램을 메모리 상에서 실행중인 작업

스레드 : 프로세스 안에서 실행되는 여러 흐름 단위

기본적으로 프로세스마다 최소 1개의 스레드 소유 (메인 스레드 포함)

20211114_161352

프로세스는 각각 별도의 주소공간 할당 (독립적)

Code : 코드 자체를 구성하는 메모리 영역(프로그램 명령)
Data : 전역변수, 정적변수, 배열 등
- 초기화 된 데이터는 data 영역에 저장
- 초기화 되지 않은 데이터는 bss 영역에 저장
Heap : 동적 할당 시 사용 (new(), malloc() 등)
Stack : 지역변수, 매개변수, 리턴 값 (임시 메모리 영역)

스레드는 Stack만 따로 할당 받고 나머지 영역은 서로 공유

하나의 프로세스가 생성될 때, 기본적으로 하나의 스레드 같이 생성

프로세스는 자신만의 고유 공간과 자원을 할당받아 사용하는데 반해, 스레드는 다른 스레드와 공간, 자원을 공유하면서 사용하는 차이가 존재함

멀티프로세스

하나의 컴퓨터에 여러 CPU 장착 → 하나 이상의 프로세스들을 동시에 처리(병렬)

장점 : 안전성 (메모리 침범 문제를 OS 차원에서 해결)

단점 : 각각 독립된 메모리 영역을 갖고 있어, 작업량 많을 수록 오버헤드 발생. Context Switching으로 인한 성능 저하

Context Switching이란?

프로세스의 상태 정보를 저장하고 복원하는 일련의 과정

즉, 동작 중인 프로세스가 대기하면서 해당 프로세스의 상태를 보관하고, 대기하고 있던 다음 순번의 프로세스가 동작하면서 이전에 보관했던 프로세스 상태를 복구하는 과정을 말함

→ 프로세스는 각 독립된 메모리 영역을 할당받아 사용되므로, 캐시 메모리 초기화와 같은 무거운 작업이 진행되었을 때 오버헤드가 발생할 문제가 존재함

멀티 스레드

하나의 응용 프로그램에서 여러 스레드를 구성해 각 스레드가 하나의 작업을 처리하는 것

스레드들이 공유 메모리를 통해 다수의 작업을 동시에 처리하도록 해줌

장점 : 독립적인 프로세스에 비해 공유 메모리만큼의 시간, 자원 손실이 감소 전역 변수와 정적 변수에 대한 자료 공유 가능
단점 : 안전성 문제. 하나의 스레드가 데이터 공간 망가뜨리면, 모든 스레드가 작동 불능 상태 (공유 메모리를 갖기 때문)
- 멀티스레드의 안전성에 대한 단점은 Critical Section 기법을 통해 대비함

하나의 스레드가 공유 데이터 값을 변경하는 시점에 다른 스레드가 그 값을 읽으려할 때 발생하는 문제를 해결하기 위한 동기화 과정

상호 배제, 진행, 한정된 대기를 충족해야함

프로세스 주소 공간

프로그램이 CPU에 의해 실행됨 → 프로세스가 생성되고 메모리에 프로세스 주소 공간이 할당됨

프로세스 주소 공간에는 코드, 데이터, 스택으로 이루어져 있다.

코드 Segment : 프로그램 소스 코드 저장
데이터 Segment : 전역 변수 저장
스택 Segment : 함수, 지역 변수 저장

왜 이렇게 구역을 나눈건가?

최대한 데이터를 공유하여 메모리 사용량을 줄여야 한다.

Code는 같은 프로그램 자체에서는 모두 같은 내용이기 때문에 따로 관리하여 공유한다.

Stack과 data를 나눈 이유는, 스택 구조의 특성과 전역 변수의 활용성을 위한 것이다.

20211114_165040

프로그램의 함수와 지역 변수는, LIFO(가장 나중에 들어간게 먼저 나옴)특성을 가진 스택에서 실행된다.

따라서 이 함수들 안에서 공통으로 사용하는 ‘전역 함수’는 따로 지정해주면 메모리를 아낄 수 있다.

인터럽트(Interrupt)

정의

프로그램을 실행하는 도중에 예기치 않은 상황이 발생할 경우 현재 실행 중인 작업을 즉시 중단하고, 발생된 상황에 대한 우선 처리가 필요함을 CPU에게 알리는 것

지금 수행 중인 일보다 더 중요한 일(ex. 입출력, 우선 순위 연산 등)이 발생하면 그 일을 먼저 처리하고 나서 하던 일을 계속해야한다.

외부/내부 인터럽트는 CPU의 하드웨어 신호에 의해 발생 소프트웨어 인터럽트는 명령어의 수행에 의해 발생

외부 인터럽트

입출력 장치, 타이밍 장치, 전원 등 외부적인 요인으로 발생 전원 이상, 기계 착오, 외부 신호, 입출력

내부 인터럽트

Trap이라고 부르며, 잘못된 명령이나 데이터를 사용할 때 발생

0으로 나누기가 발생, 오버플로우, 명령어를 잘못 사용한 경우 (Exception)

소프트웨어 인터럽트

프로그램 처리 중 명령의 요청에 의해 발생한 것 (SVC 인터럽트) 사용자가 프로그램을 실행시킬 때 발생

소프트웨어 이용 중에 다른 프로세스를 실행시키면 시분할 처리를 위해 자원 할당 동작이 수행된다.

인터럽트 발생 처리 과정

20211114_165909

주 프로그램이 실행되다가 인터럽트가 발생했다.

현재 수행 중인 프로그램을 멈추고, 상태 레지스터와 PC 등을 스택에 잠시 저장한 뒤에 인터럽트 서비스 루틴으로 간다. (잠시 저장하는 이유는, 인터럽트 서비스 루틴이 끝난 뒤 다시 원래 작업으로 돌아와야 하기 때문)

만약 인터럽트 기능이 없었다면, 컨트롤러는 특정한 어떤 일을 할 시기를 알기 위해 계속 체크를 해야 한다. (이를 폴링(Polling)이라고 한다)

폴링을 하는 시간에는 원래 하던 일에 집중할 수가 없게 되어 많은 기능을 제대로 수행하지 못하는 단점이 있었다.

즉, 컨트롤러가 입력을 받아들이는 방법(우선순위 판별방법)에는 두가지가 있다.

폴링 방식

사용자가 명령어를 사용해 입력 핀의 값을 계속 읽어 변화를 알아내는 방식

인터럽트 요청 플래그를 차례로 비교하여 우선순위가 가장 높은 인터럽트 자원을 찾아 이에 맞는 인터럽트 서비스 루틴을 수행한다. (하드웨어에 비해 속도 느림)

인터럽트 방식: MCU 자체가 하드웨적으로 변화를 체크하여 변화 시에만 일정한 동작을 하는 방식
- Daisy Chain
- 병렬 우선순위 부여

인터럽트 방식은 하드웨어로 지원을 받아야 하는 제약이 있지만, 폴링에 비해 신속하게 대응하는 것이 가능하다. 따라서 실시간 대응이 필요할 때는 필수적인 기능이다.

인터럽트는 발생시기를 예측하기 힘든 경우에 컨트롤러가 가장 빠르게 대응할 수 있는 방법이다

System Call

fork( ), exec( ), wait( )와 같은 것들은 Process 생성과 제어를 위한 System call

fork, exec는 새로운 Process 생성과 관련이 되어 있다.
wait는 Process (Parent)가 만든 다른 Process(child) 가 끝날 때까지 기다리는 명령어다.

Fork

새로운 Process를 생성할 때 사용.

그러나, 이상한 방식임.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
    printf("pid : %d", (int) getpid()); // pid : 29146

    int rc = fork();					// 주목

    if (rc < 0) {
        exit(1);
    }									// (1) fork 실패
    else if (rc == 0) {					// (2) child 인 경우 (fork 값이 0)
        printf("child (pid : %d)", (int) getpid());
    }
    else {								// (3) parent case
        printf("parent of %d (pid : %d)", rc, (int)getpid());
    }
}

pid : 29146 parent of 29147 (pid : 29146) child (pid : 29147)

위와 같이 출력한다. (parent와 child의 순서는 non-deterministic함. 즉, 확신할 수 없음. scheduler가 결정하는 일임.)

[해석]

PID : 프로세스 식별자. UNIX 시스템에서는 PID는 프로세스에게 명령을 할 때 사용함.

Fork()가 실행되는 순간. 프로세스가 하나 더 생기는데, 이 때 생긴 프로세스(Child)는 fork를 만든 프로세스(Parent)와 (almost) 동일한 복사본을 갖게 된다.

이 때 OS는 위와 똑같은 2개의 프로그램이 동작한다고 생각하고, fork()가 return될 차례라고 생각한다.

그 때문에 새로 생성된 Process (child)는 main에서 시작하지 않고, if 문부터 시작하게 된다.

그러나, 차이점이 있었다. 바로 child와 parent의 fork() 값이 다르다는 점이다. 따라서, 완전히 동일한 복사본이라 할 수 없다.

위와 같이 출력한다. (parent와 child의 순서는 non-deterministic함. 즉, 확신할 수 없음. scheduler가 결정하는 일임.)

Parent의 fork()값 => child의 pid 값

Child의 fork()값 => 0

Parent와 child의 fork 값이 다르다는 점은 매우 유용한 방식이다.

그러나! Scheduler가 부모를 먼저 수행할지 아닐지 확신할 수 없다. 따라서 아래와 같이 출력될 수 있다.

pid : 29146 child (pid : 29147) parent of 29147 (pid : 29146)

wait

child 프로세스가 종료될 때까지 기다리는 작업

위의 예시에 int wc = wait(NULL)만 추가함.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char *argv[]) {
    printf("pid : %d", (int) getpid()); // pid : 29146

    int rc = fork();					// 주목

    if (rc < 0) {
        exit(1);
    }									// (1) fork 실패
    else if (rc == 0) {					// (2) child 인 경우 (fork 값이 0)
        printf("child (pid : %d)", (int) getpid());
    }
    else {								// (3) parent case
        int wc = wait(NULL)				// 추가된 부분
        printf("parent of %d (wc : %d / pid : %d)", wc, rc, (int)getpid());
    }
}

pid : 29146 child (pid : 29147) parent of 29147 (wc : 29147 / pid : 29146)

wait를 통해서, child의 실행이 끝날 때까지 기다려줌. parent가 먼저 실행되더라도, wait ()는 child가 끝나기 전에는 return하지 않으므로, 반드시 child가 먼저 실행됨.

exec

단순 fork는 동일한 프로세스의 내용을 여러 번 동작할 때 사용함.

child에서는 parent와 다른 동작을 하고 싶을 때는 exec를 사용할 수 있음.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char *argv[]) {
    printf("pid : %d", (int) getpid()); // pid : 29146

    int rc = fork();					// 주목

    if (rc < 0) {
        exit(1);
    }									// (1) fork 실패
    else if (rc == 0) {					// (2) child 인 경우 (fork 값이 0)
        printf("child (pid : %d)", (int) getpid());
        char *myargs[3];
        myargs[0] = strdup("wc");		// 내가 실행할 파일 이름
        myargs[1] = strdup("p3.c");		// 실행할 파일에 넘겨줄 argument
        myargs[2] = NULL;				// end of array
        execvp(myarges[0], myargs);		// wc 파일 실행.
        printf("this shouldn't print out") // 실행되지 않음.
    }
    else {								// (3) parent case
        int wc = wait(NULL)				// 추가된 부분
        printf("parent of %d (wc : %d / pid : %d)", wc, rc, (int)getpid());
    }
}

exec가 실행되면,

execvp( 실행 파일, 전달 인자 ) 함수는, code segment 영역에 실행 파일의 코드를 읽어와서 덮어 씌운다.

씌운 이후에는, heap, stack, 다른 메모리 영역이 초기화되고, OS는 그냥 실행한다. 즉, 새로운 Process를 생성하지 않고, 현재 프로그램에 wc라는 파일을 실행한다. 그로인해서, execvp() 이후의 부분은 실행되지 않는다.

PCB & Context Switching

Process Management

CPU가 프로세스가 여러개일 때, CPU 스케줄링을 통해 관리하는 것을 말함

이때, CPU는 각 프로세스들이 누군지 알아야 관리가 가능함

프로세스들의 특징을 갖고있는 것이 바로 Process Metadata

Process Metadata
- Process ID
- Process State
- Process Priority
- CPU Registers
- Owner
- CPU Usage
- Memeory Usage

이 메타데이터는 프로세스가 생성되면 PCB(Process Control Block)이라는 곳에 저장됨

PCB(Process Control Block)

프로세스 메타데이터들을 저장해 놓는 곳, 한 PCB 안에는 한 프로세스의 정보가 담김

20211114_173211

정리:

프로그램 실행 → 프로세스 생성 → 프로세스 주소 공간에 (코드, 데이터, 스택) 생성 → 이 프로세스의 메타데이터들이 PCB에 저장

PCB가 왜 필요한가요?

CPU에서는 프로세스의 상태에 따라 교체작업이 이루어진다. (interrupt가 발생해서 할당받은 프로세스가 wating 상태가 되고 다른 프로세스를 running으로 바꿔 올릴 때)

이때, 앞으로 다시 수행할 대기 중인 프로세스에 관한 저장 값을 PCB에 저장해두는 것이다.

PCB는 어떻게 관리되나요?

Linked List 방식으로 관리된다.

PCB List Head에 PCB들이 생성될 때마다 붙게 된다. 주소값으로 연결이 이루어져 있는 연결리스트이기 때문에 삽입 삭제가 용이하다.

즉, 프로세스가 생성되면 해당 PCB가 생성되고 프로세스 완료시 제거된다.

이렇게 수행 중인 프로세스를 변경할 때, CPU의 레지스터 정보가 변경되는 것을 Context Switching이라고 한다

Context Switching

CPU가 이전의 프로세스 상태를 PCB에 보관하고, 또 다른 프로세스의 정보를 PCB에 읽어 레지스터에 적재하는 과정

보통 인터럽트가 발생하거나, 실행 중인 CPU 사용 허가시간을 모두 소모하거나, 입출력을 위해 대기해야 하는 경우에 Context Switching이 발생한다.

즉, 프로세스가 Ready → Running, Running → Ready, Running → Waiting처럼 상태 변경 시 발생!

######Context Switching의 OverHead란?

overhead는 과부하라는 뜻으로 보통 안좋은 말로 많이 쓰인다.

하지만 프로세스 작업 중에는 OverHead를 감수해야 하는 상황이 있다.

프로세스를 수행하다가 입출력 이벤트가 발생해서 대기 상태로 전환시킴 이때, CPU를 그냥 놀게 놔두는 것보다 다른 프로세스를 수행시키는 것이 효율적 즉, CPU에 계속 프로세스를 수행시키도록 하기 위해서 다른 프로세스를 실행시키고 Context Switching 하는 것

CPU가 놀지 않도록 만들고, 사용자에게 빠르게 일처리를 제공해주기 위한 것이다.

IPC(Inter Process Communication)

20211114_180540

프로세스는 독립적으로 실행된다. 즉, 독립 되어있다는 것은 다른 프로세스에게 영향을 받지 않는다고 말할 수 있다. (스레드는 프로세스 안에서 자원을 공유하므로 영향을 받는다)

이런 독립적 구조를 가진 프로세스 간의 통신을 해야 하는 상황이 있을 것이다. 이를 가능하도록 해주는 것이 바로 IPC 통신이다.

프로세스는 커널이 제공하는 IPC 설비를 이용해 프로세스간 통신을 할 수 있게 된다.

커널이란?

운영체제의 핵심적인 부분으로, 다른 모든 부분에 여러 기본적인 서비스를 제공해줌

IPC 설비 종류도 여러가지가 있다. 필요에 따라 IPC 설비를 선택해서 사용해야 한다.

IPC 종류

1. 익명 PIPE

파이프는 두 개의 프로세스를 연결하는데 하나의 프로세스는 데이터를 쓰기만 하고, 다른 하나는 데이터를 읽기만 할 수 있다.

한쪽 방향으로만 통신이 가능한 반이중 통신이라고도 부른다.

따라서 양쪽으로 모두 송/수신을 하고 싶으면 2개의 파이프를 만들어야 한다.

매우 간단하게 사용할 수 있는 장점이 있고, 단순한 데이터 흐름을 가질 땐 파이프를 사용하는 것이 효율적이다. 단점으로는 전이중 통신을 위해 2개를 만들어야 할 때는 구현이 복잡해지게 된다.

2. Named PIPE(FIFO)

익명 파이프는 통신할 프로세스를 명확히 알 수 있는 경우에 사용한다. (부모-자식 프로세스 간 통신처럼)

Named 파이프는 전혀 모르는 상태의 프로세스들 사이 통신에 사용한다.

즉, 익명 파이프의 확장된 상태로 부모 프로세스와 무관한 다른 프로세스도 통신이 가능한 것 (통신을 위해 이름있는 파일을 사용)

하지만, Named 파이프 역시 읽기/쓰기 동시에 불가능함. 따라서 전이중 통신을 위해서는 익명 파이프처럼 2개를 만들어야 가능

3. Message Queue

입출력 방식은 Named 파이프와 동일함

다른점은 메시지 큐는 파이프처럼 데이터의 흐름이 아니라 메모리 공간이다.

사용할 데이터에 번호를 붙이면서 여러 프로세스가 동시에 데이터를 쉽게 다룰 수 있다.

4. 공유 메모리

파이프, 메시지 큐가 통신을 이용한 설비라면, 공유 메모리는 데이터 자체를 공유하도록 지원하는 설비다.

프로세스의 메모리 영역은 독립적으로 가지며 다른 프로세스가 접근하지 못하도록 반드시 보호되야한다. 하지만 다른 프로세스가 데이터를 사용하도록 해야하는 상황도 필요할 것이다. 파이프를 이용해 통신을 통해 데이터 전달도 가능하지만, 스레드처럼 메모리를 공유하도록 해준다면 더욱 편할 것이다.

공유 메모리는 프로세스간 메모리 영역을 공유해서 사용할 수 있도록 허용해준다.

프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당해주고 이후 모든 프로세스는 해당 메모리 영역에 접근할 수 있게 된다.

중개자 없이 곧바로 메모리에 접근할 수 있어서 IPC 중에 가장 빠르게 작동함

5. 메모리 맵

공유 메모리처럼 메모리를 공유해준다. 메모리 맵은 열린 파일을 메모리에 맵핑시켜서 공유하는 방식이다. (즉 공유 매개체가 파일+메모리)

주로 파일로 대용량 데이터를 공유해야 할 때 사용한다.

6. 소켓

네트워크 소켓 통신을 통해 데이터를 공유한다.

클라이언트와 서버가 소켓을 통해서 통신하는 구조로, 원격에서 프로세스 간 데이터를 공유할 때 사용한다.

서버(bind, listen, accept), 클라이언트(connect)

이러한 IPC 통신에서 프로세스 간 데이터를 동기화하고 보호하기 위해 세마포어와 뮤텍스를 사용한다. (공유된 자원에 한번에 하나의 프로세스만 접근시킬 때)

CPU Scheduling

스케줄링

CPU 를 잘 사용하기 위해 프로세스를 잘 배정하기

조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
목표
1. Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
2. Interactive System: 빠른 응답 시간. 적은 대기 시간.
3. Real-time System: 기한(deadline) 맞추기.
  1. 선점 / 비선점 스케줄링
선점 (preemptive) : OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우
비선점 (nonpreemptive) : 프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 어려움)

프로세스 상태

20211114_181516

비선점 스케줄링 : Interrupt, Scheduler Dispatch
선점 스케줄링 : I/O or Event Wait
프로세스의 상태 전이

✓ 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.

✓ 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

✓ 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

✓ 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

✓ 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것

CPU 스케줄링의 종류
- 비선점 스케줄링
FCFS (First Come First Served)
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
SJF (Shortest Job First)
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
HRN (Hightest Response-ratio Next)
- 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
- 우선순위 = (대기시간 + 실행시간) / (실행시간)

선점 스케줄링
1. Priority Scheduling
- 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
- 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
- Aging 방법으로 Starvation 문제 해결 가능

Round Robin
- FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할달 받음
  - Time Quantum or Time Slice : 실행의 최소 단위 시간
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 문맥 교환 (Context Switching) 잦아져서 오버헤드 증가
Multilevel-Queue (다단계 큐)

20211114_181914

작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법

20211114_181929

우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용
우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.

Multilevel-Feedback-Queue (다단계 피드백 큐)

20211114_182029

다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문
짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌
처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄옂줌

CPU 스케줄링 척도

1. Response Time
  - 작업이 처음 실행되기까지 걸린 시간
1. Turnaround Time
  - 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때 까지 걸린 시간

데드락(DeadLock)

프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태 ‘교착 상태’라고도 부름 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

데드락이 일어나는 경우

20211116_150408

프로세스1과 2가 자원1,2를 모두 얻어야 한다고 가정해보자

t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음

t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

→ 이것이 바로 DeadLock!!!!!!

[주로 발생하는 경우]

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상태로 들어감
대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 ‘교착 상태’ 발생

#####데드락(DeadLock) 발생 조건 4가지 모두 성립해야 데드락 발생 (하나라도 성립하지 않으면 데드락 문제 해결 가능)

상호 배제(Mutual exclusion)

자원은 한번에 한 프로세스만 사용할 수 있음

점유 대기(Hold and wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

비선점(No preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

순환 대기(Circular wait)

프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

데드락(DeadLock) 처리

교착 상태를 예방 & 회피

1. 예방(prevention)

교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

상호배제 부정 : 여러 프로세스가 공유 자원 사용
점유대기 부정 : 프로세스 실행전 모든 자원을 할당
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

2. 회피(avoidance)

교착 상태 발생 시 피해나가는 방법

은행원 알고리즘(Banker’s Algorithm)

은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 - 사전에 검사하여 교착 상태 회피
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

교착 상태를 탐지 & 회복

교착 상태가 되도록 허용한 다음 회복시키는 방법

1. 탐지(Detection)

자원 할당 그래프를 통해 교착 상태를 탐지함

자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함

2. 회복(Recovery)

교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법

프로세스 종료 방법

교착 상태의 프로세스를 모두 중지 교착 상태가 제거될 때까지 하나씩 프로세스 중지

자원 선점 방법

교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴) 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

주요 질문

######1. 데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요. ######2. 회피 기법인 은행원 알고리즘이 뭔지 설명해보세요.

######3. 기아상태를 설명하는 식사하는 철학자 문제에 대해 설명해보세요.

교착 상태 해결책

n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘
한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

경쟁 상태(Race Condition)

공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태

동시 접근 시 자료의 일관성을 해치는 결과가 나타남

Race Condition이 발생하는 경우

1. 커널 작업을 수행하는 중에 인터럽트 발생

문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.

2. 프로세스가 ‘System Call’을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때

문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )
해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함

3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때

문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

세마포어(Semaphore) & 뮤텍스(Mutex)

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

이를 위해 나온 것이 바로 ‘세마포어’

세마포어 : 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

세마포어 P, V 연산

P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

구현 방법 ``` P(S);

// — 임계 구역 —

V(S)

procedure P(S) –> 최초 S값은 1임 while S=0 do wait –> S가 0면 1이 될때까지 기다려야 함 S := S-1 –> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함 end P

— 임계 구역 —

procedure V(S) –> 현재상태는 S가 0임 S := S+1 –> S를 1로 원위치시켜 해제하는 과정 end V

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다.

P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.


예시)

- 최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
3. A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

##### 뮤텍스 : 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

*상호 배제(Mutual Exclusion)의 약자임*

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

- lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )
- unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )

뮤텍스는 상태가 0, 1로 *이진 세마포어*로 부르기도 함


##### 뮤텍스 알고리즘
###### 1. 데커(Dekker) 알고리즘
flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

- flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
- turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

while(true) { flag[i] = true; // 프로세스 i가 임계 구역 진입 시도 while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인 if(turn == j) { // j가 임계 구역 사용 중이면 flag[i] = false; // 프로세스 i 진입 취소 while(turn == j); // turn이 j에서 변경될 때까지 대기 flag[i] = true; // j turn이 끝나면 다시 진입 시도 } } }

// ——- 임계 구역 ———

turn = j; // 임계 구역 사용 끝나면 turn을 넘김 flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

###### 2. 피터슨(Peterson) 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

while(true) { flag[i] = true; // 프로세스 i가 임계 구역 진입 시도 turn = j; // 다른 프로세스에게 진입 기회 양보 while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기 } }

// ——- 임계 구역 ———

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

###### 3. 제과점(Bakery) 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {

isReady[i] = true; // 번호표 받을 준비
number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정
isReady[i] = false; // 번호표 수령 완료

for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
    while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
    while(number[j] && number[j] < number[i] && j < i);

    // 프로세스 j가 번호표 가지고 있어야 함
    // 프로세스 j의 번호표 < 프로세스 i의 번호표
} }

// ——- 임계 구역 ———

number[i] = 0; // 임계 구역 사용 종료

---------

### 페이징과 세그먼테이션

###### 기법을 쓰는 이유

다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요하기 때문

##### 메모리 관리 기법
###### 1. 연속 메모리 관리
프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 함

고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할 (내부 단편화 발생)
동적 분할 기법 : 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

###### 2. 불연속 메모리 관리
프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법

페이지 : 고정 사이즈의 작은 프로세스 조각

프레임 : 페이지 크기와 같은 주기억장치 메모리 조각

단편화 : 기억 장치의 빈 공간 or 자료가 여러 조각으로 나뉘는 현상

세그먼트 : 서로 다른 크기를 가진 논리적 블록이 연속적 공간에 배치되는 것

**고정 크기** : 페이징(Paging)

**가변 크기** : 세그먼테이션(Segmentation)

- 단순 페이징
각 프로세스는 프레임들과 같은 길이를 가진 균등 페이지로 나뉨.
외부 단편화 X.
소량의 내부 단편화 존재.

###### 단순 세그먼테이션

각 프로세스는 여러 세그먼트들로 나뉨

내부 단편화 X, 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소

외부 단편화 존재

###### 가상 메모리 페이징
단순 페이징과 비교해 프로세스 페이지 전부를 로드시킬 필요X

필요한 페이지가 있으면 나중에 자동으로 불러들어짐

외부 단편화 X

복잡한 메모리 관리로 오버헤드 발생

###### 가상 메모리 세그먼테이션

필요하지 않은 세그먼트들은 로드되지 않음

필요한 세그먼트 있을때 나중에 자동으로 불러들어짐

내부 단편화X

복잡한 메모리 관리로 오버헤드 발생

-----

### 페이지 교체 알고리즘

##### 페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것 교체할 지 결정하는 방법

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.

하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다.

따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.

여기서 어떤 페이지를 out 시켜야할 지 정해야 한다. (이때 out 되는 페이지를 victim page라고 부름)

기왕이면 수정이 되지 않는 페이지를 선택해야 좋다.

(Why? : 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸림)

***이와 같은 상황에서 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재하는 것!***

##### Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구함

메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함 발생 X

따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String

###### 1.FIFO 알고리즘

##### First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

victim page : out 되는 페이지는, 가장 먼저 메모리에 올라온 페이지

가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법임

*초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음*

하지만 처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함

![20211116_153447](/assets/20211116_153447.png)

###### 2. OPT 알고리즘
##### Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임

![20211116_153559](/assets/20211116_153559.png)

###### 3. LRU 알고리즘
##### Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴

OPT의 경우 미래 예측이지만, LRU의 경우는 과고를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

(실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)

OPT보다는 페이지 결함이 더 일어날 수 있지만, **실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나임**

![20211116_153649](/assets/20211116_153649.png)

##### 교체 방식
- Global 교체

메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

- Local 교체

메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음

따라서, 다양한 프로세스의 페이지가 메모리에 존재함

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이

###### ▷실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적

----

### 메모리(Memory)

##### 메인 메모리(main memory)

###### 메인 메모리는 CPU가 직접 접근할 수 있는 기억 장치
###### 프로세스가 실행되려면 프로그램이 메모리에 올라와야 함
###### 메인 메모리는 주소가 할당된 일련의 바이트들로 구성되어 있다.

CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져온다.

명령어 수행 시 메모리에 필요한 데이터가 없으면 해당 데이터를 우선 가져와야 한다.

이 역할을 하는 것이 바로 MMU다.

메모리 관리장치(MMU)는 논리 주소를 물리주소로 변환해준다.

뿐만 아니라 메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어다.

메모리의 공간이 한정적이기 때문에, 사용자에게 더 많은 메모리를 제공하기 위해 '가상 주소'라는 개념이 등장했다.

(가상 주소는 프로그램 상에서 사용자가 보는 주소 공간이라고 보면 됨)

이 가상 주소에서 실제 데이터가 담겨 있는 곳에 접근하기 위해선 빠른 주소 변환이 필요한데, 이를 MMU가 도와주는 것이다.

또한 메인 메모리의 직접 접근은 비효율적이므로, CPU와 메인 메모리 속도를 맞추기 위해 캐시가 존재한다.

##### MMU의 메모리 보호

프로세스는 독립적인 메모리 공간을 가져야 되고, 자신의 공간만 접근해야 한다.

따라서 한 프로세스에게 합법적인 주소 영역을 설정하고, 잘못된 접근이 오면 trap을 발생시키며 보호한다.

![20211116_154216](/assets/20211116_154216.png)

base와 limit 레지스터를 활용한 메모리 보호 기법이다.

- base 레지스터는 메모리상의 프로세스 시작주소를 물리 주소로 저장

- limit 레지스터는 프로세스의 사이즈를 저장

이로써 프로세스의 접근 가능한 합법적인 메모리 영역(x)은

base <= x < base+limit ```

이 영역 밖에서 접근을 요구하면 trap을 발생시키는 것이다.

안전성을 위해 base와 limit 레지스터는 커널 모드에서만 수정 가능하도록 설계한다. (사용자 모드에서는 직접 변경할 수 없도록)

메모리 과할당(over allocating)

실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스에 할당한 상황

페이지 기법과 같은 메모리 관리 기법은 사용자가 눈치 채지 못하도록 눈속임을 통해 메모리를 할당해준다. (가상 메모리를 이용해서)

과할당 상황에 대해서 사용자를 속인 것을 들킬만한 상황이 존재한다.

프로세스 실행 도중 페이지 폴트 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리의 빈 프레임에 페이지를 올려야 하는데, 모든 메모리가 사용중이라 빈 프레임이 없음

이러한 과할당을 해결하기 위해선, 빈 프레임을 확보할 수 있어야 한다.

메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻음
프로세스 하나를 swap out하고, 이 공간을 빈 프레임으로 활용

swapping 기법을 통해 공간을 바꿔치기하는 2번 방법과는 달리 1번은 사용자에게 페이징 시스템을 들킬 가능성이 매우 높아서 하면 안된다.

(페이징 기법은 사용자 모르게 시스템 능률을 높이기 위해 선택한 일이므로 들키지 않게 처리해야함)

따라서, 2번과 같은 해결책을 통해 페이지 교체가 이루어져야 한다.

페이지 교체

메모리 과할당이 발생했을 때, 프로세스 하나를 swap out해서 빈 프레임을 확보하는 것

프로세스 실행 도중 페이지 부재 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리에 빈 프레임이 있는지 확인

빈 프레임이 있으면 해당 프레임을 사용
빈 프레임이 없으면, victim 프레임을 선정해 디스크에 기록하고 페이지 테이블을 업데이트함

빈 프레임에 페이지 폴트가 발생한 페이지를 올리고, 페이지 테이블 업데이트

오버헤드를 감소시키는 해결법

이처럼 빈 프레임이 없는 상황에서 victim 프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 두 번의 디스크 접근이 이루어진다.

페이지 교체가 많이 이루어지면, 이처럼 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생한다.

방법1

변경비트를 모든 페이지마다 둬서, victim 페이지가 정해지면 해당 페이지의 비트를 확인

해당 비트가 set 상태면? → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 뜻 (즉, 페이지가 메모리 올라온 이후 한번이라도 수정이 일어났던 것. 따라서 이건 디스크에 기록해야함)

bit가 clear 상태라면? → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황 (즉, 디스크와 내용이 같아서 기록할 필요가 없음)

비트를 활용해 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법이다.

방법2

페이지 교체 알고리즘을 상황에 따라 잘 선택해야 한다.

현재 상황에서 페이지 폴트를 발생할 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용

FIFO
OPT
LRU

캐시 메모리

주기억장치에 저장된 내용의 일부를 임시로 저장해두는 기억장치

CPU와 주기억장치의 속도 차이로 성능 저하를 방지하기 위한 방법

CPU가 이미 봤던걸 다시 재접근할 때, 메모리 참조 및 인출 과정에 대한 비용을 줄이기 위해 캐시에 저장해둔 데이터를 활용한다

캐시는 플리플롭 소자로 구성되어 SRAM으로 되어있어서 DRAM보다 빠른 장점을 지녔다.

CPU와 기억장치의 상호작용

CPU에서 주소를 전달 → 캐시 기억장치에 명령이 존재하는지 확인

(존재) Hit 해당 명령어를 CPU로 전송 → 완료
(비존재) Miss 명령어를 갖고 주기억장치로 접근 → 해당 명령어를 가진 데이터 인출 → 해당 명령어 데이터를 캐시에 저장 → 해당 명령어를 CPU로 전송 → 완료

이처럼 캐시를 잘 활용한다면 비용을 많이 줄일 수 있다.

따라서 CPU가 어떤 데이터를 원할지 어느정도 예측할 수 있어야 한다.

(캐시에 많이 활용되는 쓸모 있는 정보가 들어있어야 성능이 높아짐)

적중률을 극대화시키기 위해 사용되는 것이 바로 지역성의 원리

#####지역성

기억 장치 내의 정보를 균일하게 액세스 하는 것이 아니라 한 순간에 특정부분을 집중적으로 참조하는 특성

지역성의 종류는 시간과 공간으로 나누어진다.

시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에도 참조되는 특성

공간 지역성 : 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

캐싱 라인

빈번하게 사용되는 데이터들을 캐시에 저장했더라도, 내가 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비다.

즉, 캐시에 목적 데이터가 저장되어있을 때 바로 접근하여 출력할 수 있어야 캐시 활용이 의미있어진다.

따라서 캐시에 데이터를 저장할 시, 자료구조를 활용해 묶어서 저장하는데 이를 캐싱 라인이라고 부른다.

즉, 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하면서 빠르게 원하는 정보를 찾을 수 있다. (set이나 map 등을 활용)

파일 시스템(File System)

컴퓨터에서 파일이나 자료를 쉽게 발견할 수 있도록, 유지 및 관리하는 방법이다.

저장매체에는 수많은 파일이 있기 때문에, 이런 파일들을 관리하는 방법을 말한다.

특징

커널 영역에서 동작
파일 CRUD 기능을 원활히 수행하기 위한 목적
계층적 디렉터리 구조를 가짐
디스크 파티션 별로 하나씩 둘 수 있음

역할

파일 관리
보조 저장소 관리
파일 무결성 메커니즘
접근 방법 제공

개발 목적

하드디스크와 메인 메모리 속도차를 줄이기 위함
파일 관리
하드디스크 용량 효율적 이용

구조

메타 영역 : 데이터 영역에 기록된 파일의 이름, 위치, 크기, 시간정보, 삭제유무 등의 파일 정보
데이터 영역 : 파일의 데이터

접근 방법

1. 순차 접근(Sequential Access)

가장 간단한 접근 방법으로, 대부분 연산은 read와 write

20211116_155056

현재 위치를 가리키는 포인터에서 시스템 콜이 발생할 경우 포인터를 앞으로 보내면서 read와 write를 진행. 뒤로 돌아갈 땐 지정한 offset만큼 되감기를 해야 한다. (테이프 모델 기반)

2. 직접 접근(Direct Access)

특별한 순서없이, 빠르게 레코드를 read, write 가능

20211116_155140

현재 위치를 가리키는 cp 변수만 유지하면 직접 접근 파일을 가지고 순차 파일 기능을 쉽게 구현이 가능하다.

무작위 파일 블록에 대한 임의 접근을 허용한다. 따라서 순서의 제약이 없음

대규모 정보를 접근할 때 유용하기 때문에 ‘데이터베이스’에 활용된다.

3. 기타 접근

직접 접근 파일에 기반하여 색인 구축

20211116_155220

크기가 큰 파일을 입출력 탐색할 수 있게 도와주는 방법임

디렉터리와 디스크 구조

1단계 디렉터리

가장 간단한 구조

파일들은 서로 유일한 이름을 가짐. 서로 다른 사용자라도 같은 이름 사용 불가

20211116_155418

2단계 디렉터리

사용자에게 개별적인 디렉터리 만들어줌

UFD : 자신만의 사용자 파일 디렉터리
MFD : 사용자의 이름과 계정번호로 색인되어 있는 디렉터리

20211116_155454

트리 구조 디렉터리

2단계 구조 확장된 다단계 트리 구조

한 비트를 활용하여, 일반 파일(0)인지 디렉터리 파일(1) 구분

20211116_155522

그래프 구조 디렉터리

순환이 발생하지 않도록 하위 디렉터리가 아닌 파일에 대한 링크만 허용하거나, 가비지 컬렉션을 이용해 전체 파일 시스템을 순회하고 접근 가능한 모든 것을 표시

링크가 있으면 우회하여 순환을 피할 수 있음

20211116_155549

참조:https://gyoogle.dev/blog/computer-science/operating-system/Operation%20System.html

여길 보면서 면접 대비로 눈으로 보는것 보다 한줄 씩 다 적어보면서 베끼기만 하려는 것이 아닌 이해하려고 최대한 노력했다.