24.03.01 운영체제, 백준, KEYWORD

운영체제

3. 제한적 직접 실행 원리(Limited Direct Execution)

• CPU를 가상화하기 위해서 운영체제는 여러 작업들이 동시에 실행되는 것처럼 보이도록 물리적인 CPU를 공유한다. 이러한 가상화 기법을 구현하기 위해서는 두 가지 문제를 해결해야 한다.
  1. 성능저하
  2. 제어문제
• 제어권을 유지하면서 성능 저하가 없도록 하는 것이 운영체제를 구축하는데 핵심적인 도전 과제이다.

3.1 기본원리 : 제한적 직접 실행

• 운영체제 개발자들은 프로그램을 빠르게 실행하기 위하여 제한적 직접 실행이라는 기법을 개발했다. 운영체제가 프로그램을 실행하기 시작할 때 프로세스 목록에 해당 프로세스 항목을 만들고 메모리를 할당하면 프로그램 코드를 디스크에서 탑재하고 진입점을 찾아 그 지점으로 분기하여 사용자 코드를 실행하기 시작한다.
• 이 접근법은 CPU를 가상화 함에 있어서 두 가지 문제를 일으킨다.
  1. 프로그램을 직접 실행 시킨다면 프로그램이 운영체제가 원치않는 일을 하지않는다고 어떻게 보장하는가?
  2. 프로세스 실행 시, 운영체제는 어떻게 프로그램의 실행을 중단하고, 다른 프로세스로 전환 시킬 수 있는가.
• 프로그램 실행에 제한을 두지 않으면 운영체제는 어떠한 것도 제어할 수 없으며 따라서 단순한 라이브러리일 뿐이다.

3.2 문제점 1 : 제한된 연산

• 직접 실행의 장점은 빠르게 실행된다. 그러나 CPU에서 직접 실행시키면 디스크 입출력 요청이나 CPU 또는 메모리와 같은 시스템 자원에 대한 추가 할당 요청이 필요하다.
• 프로세스가 디스크에 대하여 입출력 하는 것을 제한하지 않으면, 프로세스는 전체 디스크를 읽고 쓸 수 있기 때문에 접근 권한을 검사하는 기능이 의미가 없다.
• 이 때문에 사용자 모드(User mode)라고 알려진 새로운 모드가 도입됐다. 사용자 모드에서 실행되는 코드는 할 수 있는 일이 제한된다. 프로세스가 사용자 모드에서 실행중이면 입출력 요청을 할 수 없도록 설정한다. 이때 입출력 요청을 하면 프로세서가 예외를 발생시키고, 운영체제는 해당 프로세스를 제거한다.
• 커널모드(Kernel mode)는 운영체제의 중요한 코드들이 실행된다. 이 모드에서 실행되는 코드는 모든 특수한 명령어를 포함하여 원하는 모든 작업을 수행할 수 있다.
• 사용자 프로세스가 디스크를 읽기와 같은 특권 명령어를 실행해야 할 때 어떻게 해야 하는가? 이런 제한작업의 실행을 허용하기 위해서 거의 모든 현대 하드웨어는 사용자 프로세스에게 시스템 콜을 제공한다.
• 시스템 콜을 실행하기 위해 프로그램은 trap 특수 명령어를 실행 해야한다. 이 명령어는 커널 안으로 분기하는 동시에 특권수준을 커널모드로 상향조정한다. 커널 모드로 진입하면 운영체제는 모든 명령어를 실행 할 수 있고, 이를 통하여 프로세스가 요청한 작업을 처리할 수 있다. 완료되면 운영체제는 return-from-trap 특수 명령어를 호출한다.
• 이 명령어는 특권 수준을 사용자 모드로 다시 하향 조정하면서 호출한 사용자 프로그램으로 리턴한다.
• 하드웨어가 trap 명령어를 수행할 때, 호출한 프로세스의 필요한 레지스터들을 저장해야 한다. 운영체제가 return-from-trap 으로 사용자 프로세스로 리턴하기 위해서다. x86에서는 커널 스택(Kernel Stack)에 저장한다. return-from-trap 명령어가 이 값들을 스택에서 팝(pop)하여 사용자 모드 프로그램의 실행을 다시 시작한다.
• 커널은 부팅시에 트랩테이블(trap table)을 만들고 이를 이용하여 시스템을 통제한다. 컴퓨터가 부트될 때는 커널모드에서 동작하기 때문에 하드웨어를 원하는대로 제어할 수 있다. 운영체제가 하는 초기 작업중 하나는 하드웨어에게 예외사건이 일어났을 때 어떤 코드를 실행해야 하는지 알려주는 것이다.
• 운영체제는 특정 명령어를 사용하여 하드웨어에게 트랩 핸들러(trap handler)의 위치를 알려준다. 하드웨어는 이 정보를 전달받으면 해당 위치를 기억하고 있다.
• 모든 시스템 콜은 자신의 고유 번호를 갖는다. 사용자 프로그램은 원하는 시스템 콜을 호출하기 위해서, 해당 시스템 콜 번호를 레지스터 또는 스택에 지정된 위치에 저장한다. trap 명령어가 호출되면 이 명령어를 처리하는 trap 핸들러가 실행된다.
• trap 핸들러는 운영체제의 일부분이다. 운영체제는 시스템 콜 번호를 읽어 사용자가 명시한 시스템 콜 변호가 유효한 시스템 콜에 해당하는지를 먼저 파악한다. 유효한 시스템 콜로 판명되면 해당 코드로 이동하여 실행한다.
• 각 시스템 콜의 코드 위치는 운영체제만 알고있다. 시스템 콜 코드위치를 사용자 프로그램으로부터 숨김으로써, 사용자는 시스템 콜 번호를 이용하여 커널에게 시스템 콜의 실행을 요청해야 한다. 커널 코드의 무분별한 실행을 방지하기 위한 일종의 보안 기법이다.
• 프로세스는 커널 스택을 각자 가지고 있다. 커널 모드로 진입하거나 진출 할 때 하드웨어에 의해 프로그램 카운터와 범용레지스터 등의 레지스터가 저장되고 복원되는 용도로 사용된다.
• LDE 방식은 두 단계로 진행된다. 전반부에서(부팅 시) 커널은 트랩 테이블을 초기화하고 CPU는 나중에 사용하기 위하여 테이블의 위치를 기억한다. 커널은 이러한 작업을 커널모드에서만 사용할 수 있는 명령어를 이용하여 수행한다.
• 후반부에서(프로세스를 실행할 때) return-from-trap을 이용하여 사용자 프로세스를 시작할 때 몇 가지 작업을 수행한다. 새로운 프로세스를 위한 노드를 할당하여 프로세스 리스트에 삽입하고, 메모리를 할당하는 등의 작업이 포함된다. return-from-trap 명령어는 CPU를 다시 사용자 모드로 전환하고 프로세스 실행을 시작한다. 프로세스는 이후 자신의 할 일을 다하면 main()에서 리턴한다. 이때 일반적으로 스텁코드를 리턴하고 스텁코드가 프로그램을 종료시킨다. 종료시킬 때 exit() 시스템을 호출하고, 다시 운영체제로 트랩된다. 이 시점에 운영체제는 정리작업을 하게 되어 모든 일이 완료된다.

3.3 문제점 2 : 프로세스간 전환

• 프로세스의 전환은 간단해야 한다. 프로세스의 전환은 실행 중인 프로세스를 멈추고 다른 프로세스를 실행하는 것이다.

협조 방식 : 시스템 콜 호출시 까지 대기

• 협조(Cooperative) 방식으로 알려진 방법이다. 이 방식은 각 사용자 프로세스가 비정상적인 행동은 하지 않을것으로 가정한다. CPU를 장기간 사용해야 하는 프로세스들은 다른 프로세스들이 CPU를 사용할 수 있도록 주기적으로 CPU를 반납할 것이라고 믿는다. 착한 사람들만 사는 곳이다. 😊
• CPU를 반납하기 위해서는 운영체제가 해당 프로세스의 실행 상태를 저장해주어야 한다. CPU 반납 문제의 핵심은 응용 프로세스가 어떻게 제어권을 운영체제에게 넘기느냐로 귀결된다. 대부분의 프로세스는 시스템 콜을 자주 호출하는 것으로 알려져있다. 시스템 콜을 호출하면 자연스럽게 운영체제의 코드가 실행되며, 제어권이 운영체제로 넘어간다. 협조 방식을 사용하는 운영체제는 yield 시스템 콜을 제공한다. 이 시스템 콜은 운영체제에게 제어를 넘겨 운영체제가 CPU를 다른 프로세스에게 할당할 수 있는 기회를 제공한다.
• 응용프로그램이 비정상적인 행위를 하면 운영체제에게 제어가 넘어간다. 그러면 운영체제는 다시 CPU를 얻어 해당 프로세스를 종료할 수 있다.
• 협조 방식의 스케줄링 시스템은 근본적으로 수동적이다. CPU 제어권 획득을 위해 운영체제는 시스템 콜이든 불법적인 연산이 일어나기를 대기하는 것이다.

비협조 방식 : 운영체제가 제어권을 확보

• 타이머 인터럽트(timer interrupt)를 이용한다. 타이머는 수 밀리 초마다 인터럽트라 불리는 하드웨어 신호를 발생시키도록 프로그램 가능하다. 인터럽트가 발생하면 운영체제는 현재 수행 중인 프로세스를 중단시키고 해당 인터럽트에 대한 인터럽트 핸들러(interrupt handler)를 실행한다. 인터럽트 핸들러는 운영체제의 일부분이다. 인터럽트를 처리하는 과정에서, 제어권이 자연스럽게 운영체제로 넘어간다.
• 운영체제는 타이머 인터럽트가 발생 시 실행해야 할 코드의 주소를 기록해 두어야 한다. 타이머가 시작되면, 타이머 인터럽트가 발생할 때마다, 제어권이 운영체제에게 넘어간다. 타이머는 인터럽트를 주기적으로 발생시킨다. 운영체제는 사용자 프로그램이 비정상적으로 작동하는 경우가 발생하더라도 언제든지 해당 프로그램을 적절히 처리 할 수 있는 기회를 갖을 수 있다.

문맥의 저장과 복원

• 현재 프로세스를 계속 실행할 것인지, 다른 프로세스로 전환할 것인지 이런 결정은 운영체제의 스케줄러(Scheduler)라는 부분에 의해 내려진다.
• 현재 프로세스를 중단하고 다른 프로세스를 실행하기로 결정을 하면 운영체제는 문맥교환(context switching)이라 불리는 코드를 실행한다. 문맥교환은 현재 실행중인 프로세스의 레지스터 값들을 커널 스택 같은 곳에 저장하고, 새로이 실행될 프로세스 커널 스택으로부터 레지스터 값을 복원하는 것이 전부다. 그렇게 함으로써 운영체제는 return-from-trap 명령어가 마지막으로 실행될 때 현재 실행중이던 프로세스로 리턴하는 것이 아니라 다른 프로세스로 리턴하여 실행을 다시 시작할 수 있다.
• 문맥을 전환하는 과정에서 서로 다른 두 가지 종류의 레지스터의 저장/복원이 발생한다는 것을 주의해야 한다.
  • 첫 번째는 타이머 인터럽트가 발생했을 때 일어난다.
  • 두 번째는 운영체제가 A에서 B로 전환하기로 결정했을 때 일어난다. 이 경우 커널 레지스터는 운영체제에 의해 해당 프로세스의 프로세스 구조체에 저장된다.

백준

1012 유기농 배추

#include <bits/stdc++.h>
using namespace std;

const int MAX = 51;
int test_case, m,n,k;
int board[MAX][MAX];
int visited[MAX][MAX];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };

void DFS(int y, int x) 
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++) 
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= m || ny < 0 || ny >= n)
			continue;

		if (board[ny][nx] == 1 && visited[ny][nx] == 0) {
			DFS(ny, nx);
		}
	}
}

int main() 
{
    cin >> test_case;

    for(int i = 0; i< test_case; ++i)
    {
        cin >> m >> n >> k;

        memset(board, 0, sizeof(board));
        memset(visited, 0, sizeof(visited));

        for(int i = 0 ; i<k; ++i)
        {
            int x, y;
            cin >> x >> y;
            board[y][x] = 1;
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && visited[i][j] == 0) {
                    DFS(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }
}

• DFS로 풀었던 문제
• dx, dy를 생각해서 풀어야하는 문제 유형이다.
• x축 y축을 생각해서 넣어주는 것을 주의하면서 했다.

KEYWORD

문맥교환(Context Switching)

• 하나의 프로세스가 CPU를 사용중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기위해, 이전의 프로세스의 상태(문맥)을 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말한다.
• 이때 한 프로세스의 문맥은 그 프로세스의 프로세스 제어블록(PCB)에 기록되어 있다.

PCB(Process Control Block)

• 운영체제가 시스템 내의 프로세스들을 관리하기 위해 프로세스 마다 유지하는 정보들을 담는 커널 내 자료구조로 커널 주소 공간의 data 영역에 존재한다.

PCB에 저장되는 내용들

• Process 상태 : CPU를 할당해도 되는지 여부를 결정한다.
• PC 값 : 다음에 수행할 명령어를 가리킨다.
• CPU Register : CPU연산을 위해 현 시점에 레지스터에 어떤 값을 저장하고 있는지 나타낸다.
• CPU 스케줄링 정보
• 메모리 관리 정보
• 자원 사용 정보
• 입출력 상태 정보
• 이러한 Context 정보를 사용해 CPU를 선점하고 있던 프로세스는 프로세스 문맥을 PCB에 저장하게 되고, 새롭게 CPU를 할당받을 프로세스는 PCB로부터 예전에 저장했던 자신의 문맥을 실제 하드웨어로 복원하는 과정을 거친다.

문맥교환이 일어나는 과정

1. 요청발생 : 인터럽트 또는 트랩에 의한 요청이 발생한다.
2. PCB에 저장 : 운영체제는 현재 실행중인 프로세스의 정보를 PCB에 저장한다.
3. CPU 할당 : 운영체제는 다음 프로세스 정보를 PCB에서 가져와 CPU를 할당한다.

데드락(Dead Lock)/교착상태

• 두 개 이상의 프로세스나 쓰레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태이다.
• 무한히 다음 자원을 기다리게 되는 상태를 말한다.
• 시스템 적으로 한정된 자원을 여러곳에서 사용하려고 할 때 발생한다

데드락의 발생조건

• 4가지 모두 성립해야 데드락 발생(하나라도 성립하지 않으면 데드락 문제 해결 가능하다.)
  1. 상호 배제(Mutual exclusion)
     1. 자원은 한 번에 한 프로세스만 사용할 수 있다.
  2. 점유 대기(Hold and Wait)
     1. 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.
  3. 비선점(No Preemption)
     1. 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 빼앗을 수 없다.
  4. 순환대기(Circular Wait)
     1. 프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

데드락 처리

• 교착 상태를 예방&회피
  1. 예방(Prevention)
     • 교착 상태 발생 조건 중 하나를 제거하면서 해결한다.(자원낭비 심함)
       • 상호 배제 부정 : 자원들을 공유 가능하게 만들어주면 Mutual Exclusion이라는 조건을 만족시키지 않을 수 있다. 예를 들면 읽기 전용 파일(Read-only file)은 여러 프로세스가 동시에 접근할 수 있도록 허용해주는 방법 등이다. 하지만 Mutex lock과 같이 본질적으로 공유가 불가능한 자원들이 존재하기 때문에 일반적으로 사용하기는 어려운 면이 있다.
       • 점유 대기 부정 : 이 조건을 만족시키지 않기 위해, 프로세스가 어떤 자원을 점유하고 있다면, 다른 자원을 요청하지 못하게 만드는 방법을 사용할 수 있다. 이를 위해서 프로세스는 작업을 먼저 요청하고 할당을 받는 방법이나, 또는 자신이 가지고 있는 모든 자원을 방출하고 나서야, 새로운 자원을 요청할 수 있게 만드는 방법을 사용해야 한다.
         • 할당된 자원을 오랫동안 사용하지 않을 수 있기 때문에 자원의 이용도가 낮아질 수 있다.
         • 자주 쓰이는 자원들을 여러 개 필요로 하는 프로세스라면, 해당 자원들을 모두 모으지 못하면 실행할 수 없기 때문에 기아 문제(starcation)가 발생할 수도 있다는 것이다.
       • 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다.
       • 순환 대기 부정 : 모든 자원에 전체적인 순서를 부여하여, 각 프로세스들이 순서에 따라 오름차순으로만 자원을 요청할 수 있도록 만든다.
  2. 회피(avoidance)
     • 교착 상태 발생시 피해나가는 방법
       • 은행원 알고리즘
         • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하여 교착상태를 회피한다.
         • 안정상태면 자원할당, 아니면 다른 프로세스들이 지원해지까지 대기한다.
• 교착상태를 탐지 & 회복
  • 교착 상태가 되도록 허용한 다음 회복시키는 방법
    1. 탐지(Detection)
       • 자원 할당 그래프를 통해 교착 상태를 탐지한다.
       • 자원 요청 시 , 탐지 알고리즘을 실행시켜 그에 대한 오버헤드가 발생한다.
    2. 회복(Recovery)
       • 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법이다.

CPU 스케줄링 알고리즘

• CPU 스케줄링은 다중 프로그램 환경에서 CPU의 사용 시간을 효율적으로 분배하기 위한 방법이다.
• 이를 통해 시스템의 성능을 최적화하고, 대기시간을 최소화하며, CPU 사용률을 극대화하는 것이 목표다.

알고리즘 종류

• 선입선출 스케줄링(FCFS : First-Come, First-Served Scheduling)
  • 이 알고리즘은 먼저 도착한 프로세스부터 처리하는 알고리즘이다.
  • 프로세스 실행 시간을 예측하기 쉽고 단순하고 공평하지만 CPU 버스트 시간이 긴 프로세스가 먼저 도착하면 다른 프로세스들은 긴 대기 시간을 감수해야 하는 호흡성문제가 발생할 수 있다.
• 최단 작업 우선 스케줄링(SJN : Shortest Job Next Scheduling)
  • CPU 버스트 시간이 가장 짧은 프로세스부터 처리하는 알고리즘
  • 평균 대기 시간을 최소화 할 순 있지만, CPU버스트 시간을 미리 알 수 없기 때문에 예측에 의존하게 된다.
• 우선 순위 스케줄링(Priority Scheduling)
  • 각 프로세스에 우선순위를 부여하고, 우선 순위가 높은 프로세스부터 처리한다.
  • 우선순위가 낮은 프로세스가 계속 대기 상태에 머무르는 기아 상태가 발생할 수 있다.
• 라운드 로빈 스케줄링(RR : Round Robin Scheduling)
  • 각 프로세스에게 동일한 시간 할당량(타임 퀀텀)을 부여하고, 그 시간 동안만 CPU를 사용하도록 한다.
  • 모든 프로세스가 공평하게 CPU를 사용할 수 있어 멀티 프로그래밍 환경에 적합하다.
• 다단계 큐 스케줄링(Multilevel Queue Scheduling)
  • 프로세스를 여러 대기열로 분류하고, 각 대기열에 다른 스케줄링 알고리즘을 적용한다.
  • 프로세스가 시스템에 도착하면 우선적으로 가장 높은 우선순위를 가진 큐 대기열에 배치된다. 그리고 주어진 시간동안 작업을 완료하지 못했을 시 한 단계 낮은 우선순위의 대기열로 이동하게 된다.
• 최단 잔여 시간 우선 스케줄링(SRT : Shortest Remaining Time First)
  • SJN 방식을 선점 스케줄링 방식으로 변경한 기법
  • 실행중인 프로세스보다 남은 처리 시간이 짧은 프로세스가 들어오면 실행 중인 프로세스를 중단하고 교체한다.
  • 평균 대기 시간이 가장 짧은 알고리즘이지만, 기본적으로 선점형 방식이기 때문에 잦은 문맥교환이 일어나고 그에 따른 오버헤드가 커진다.
    • 기아 현상도 더 심하게 발생할 수 있다.

버스트(Burst)

• CPU 스케줄링에서 중요한 개념이며 CPU 버스트와 I/O 버스트 두 가지 주요 형태가 있다.
• CPU 버스트
  • 프로세스가 CPU를 연속적으로 사용하는 시간을 의미하며, 연산이나 명령 실행과 같은 작업을 수행하는데 필요한 시간을 나타낸다.
  • CPU 버스트의 길이는 프로세스마다 다르며, 이를 기반으로 CPU 스케줄링 알고리즘이 작업 순서를 결정하게 된다.
• I/O 버스트
  • 프로세스가 입출력 작업을 수행하는 데 걸리는 시간을 의미하며, 디스크 액세스, 네트워크 통신과 같은 I/O 작업을 수행하는데 필요한 시간을 나타낸다.
  • I/O 버스트 동안에는 CPU가 다른 프로세스를 실행할 수 있으므로, 다른 프로세스에서 CPU버스트를 처리할 수 있다.

호흡성 문제(Convoy effect)

• 특히 선입선출 알고리즘에서 주로 발생하는 CPU 스케줄링 문제이다.
• CPU 버스트 시간이 긴 프로세스가 먼저 CPU를 점유하게 되면, 그 뒤에 대기하고 있는 CPU 버스트 시간이 짧은 프로세스들이 불필요하게 오랫동안 대기해야 하는 상황을 말한다.
  • 이로 인해 전체적인 시스템 효율이 저하되며, 평균 대기 시간이 증가하게 된다.

기아 상태(Starvation)

• 운영체제에서 특정 프로세스가 필요한 자원을 무한정 기다리고 있지만, 다른 프로세스들이 계속해서 그 자원을 점유하고 있어서 원하는 작업을 수행할 수 없게 되는 상태를 말한다.
• 기아 상태는 특히 우선순위 스케줄링에서 발생할 수 있으며, 우선순위가 높은 프로세스가 계속 도착하게 되면, 낮은 우선순위를 가진 프로세스는 CPU를 사용할 기회를 얻지 못하고 무한히 기다리게 될 수 도 있다.
  • 기아 상태를 해결하기 위한 방법 중 하나는 에이징(Aging)이 있다.

에이징(Aging)

• 프로세스가 시스템에서 대기하는 시간이 길어질수록 그 프로세스의 우선순위를 점차 높여주는 방법이다.
• 이를 통해 모든 프로세스가 언젠가는 CPU를 사용할 수 있는 기회를 얻게 되어 기아 상태를 방지할 수 있다.

타임퀀텀(Time Quantum)

• 운영체제에서 프로세스 스케줄링에 사용되는 시간 단위를 의미하며, 특히 라운드 로빈 스케줄링에서 중요한 역할을 한다.
• 타임 퀀텀의 길이는 너무 짧으면, 프로세스 간에 자주 전환되어 오버헤드가 증가하게 되고, 반대로 너무 길면, 특정 프로세스가 CPU를 오랫동안 점유하게 되어 다른 프로세스들이 불필요하게 대기하는 상황이 발생할 수 있다.