둔필승총

프로세스 제어블록 PCB는 프로세스를 실행하는데 필요한 정보를 보관하는 자료구조로 TCB(Task Control Box)라고도 한다. 모든 프로세스는 고유의 프로세스 제어 블록을 가지며, 프로세스 제어블록은 프로세스 생성 시 만들어져서 프로세스가 실행을 완료하면 폐기된다. 프로세스 제어 블록에 저장되는 정보는 무엇일까?

1. 포인터 : 프로세스 제어블록의 첫번째 블록에는 포인터가 저장된다. 준비 상태나 대기 상태는 큐로 운영되는데, 프로세스 제어블록을 연결하여 준비 상태나 대기 상태의 큐를 구현할 때 포인터를 사용한다.

2. 프로세스 상태 : 프로세스 상태에는 생성, 준비, 실행, 대기, 보류 준비, 보류 대기 등이 있다. 이는 프로세스가 현재 어떤 상태에 있는지를 나타내며, 프로세스 제어블록의 두번째 블록에 저장된다.

3. 프로세스 구분자 : 운영체제 내의 여러 프로세스를 구별하기 위한 구분자를 저장한다. (PID)

4. 프로그램 카운터 : 다음에 실행될 명령어의 위치를 가리키는 프로그램 카운터 값을 저장한다. (레지스터의 한 종류)

5. 프로세스 우선순위 : 프로세스 상태를 설명할 때 이해를 돕기위해 대기 상태에서 기다리는 모든 프로세스가 한 줄로 서있다고 가정했다. 이는 대기 큐waiting queue가 하나라는 의미로, 모든 프로세스의 우선 순위가 같다고 본 것이다. 그러나 실제로는 프로세스의 중요도가 각각 다르다. 사용자 프로세스보다 중요도가 큰 커널 프로세스는 우선순위가 높고, 사용자 프로세스끼리도 우선순위가 다르다. 

 다양한 우선순위의 프로세스가 대기 상태로 들어오기 때문에 대기 상태의 큐도 우선순위별로 따로 운영된다. 다시 말해, 우선순위에 따라 프로세스 제어블록들이 여러 줄로 서 있다. CPU스케쥴러가 준비상태에 있는 프로세스 중 실행상태로 옮겨야 할 프로세스를 선택할 때는 프로세스 우선순위를 기준으로 삼는다. 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스보다 먼저 실행되고 더 자주 실행된다. 

6. 각종 레지스터 정보 : 프로세스 제어블록에는 프로세스가 실행되는 중에 사용하던 레지스터, 누산기(accumulator), 색인 레지스터(index register), 스택 포인터(stack pointer)와 같은 레지스터의 값이 저장된다. 이전에 실행할 때 사용한 레지스터의 값을 보관해야 다음에 실행할 수 있기 때문에 자신이 사용하던 레지스터의 중간값을 보관한다.

7. 메모리 관리 정보 : 프로세스 제어 블록에는 프로세스가 메모리의 어디에 있는지 나타내는 메모리 위치 정보, 메모리 보호를 위해 사용하는 경계 레지스터 값과 한계 레지스터 값 등이 저장된다. 그 외에 세그먼테이션 테이블(segmentation table), 페이지 테이블(page table)등의 정보도 보관한다.

8. 할당된 자원 정보 : 프로세스를 실행하기 위해 사용하는 입출력 자원이나 오픈 파일 등에 대한 정보를 말한다. 어떤 프로세스가 하드디스크에 저장된 파일을 열어서 작업하거나, 음악을 출력하기 위해 사운드카드에 접근하고 있다면, 파일이나 사운드카드에 대한 정보가 필요한데, 이러한 정보를 프로세스 제어 블록에 저장한다.

9. 계정정보 : 계정번호, CPU 할당시간, CPU 사용시간 등

10. 부모 프로세스 구분자와 자식 프로세스 구분자 : ParentPID(PPID), ChildPID(CPID)

**포인터의 역할**

 프로세스 제어블록의 맨 위에 있는 포인터의 역할을 알아보자. 입출력이 완료되기를 기다리는 프로세스는 대기상태로 모인다. 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 대기상태로 모이는 프로세스도 다양하다. 그런데 이것들을 하나로 모아놓으면 관리하기가 불편하다. 예를 들어, 하드디스크로부터 인터럽트가 들어왔을 때, 대기상태의 프로세스가 한군데에 모여 있다면 해당 프로세스를 찾기 위해 대기 상태의 모든 프로세스를 뒤져야 한다. 이러한 불편함이 없도록 대기 상태에는 같은 입출력을 요구한 프로세스끼리 모아놓는다.

**문맥 교환**

1. 문맥 교환의 의미

 문맥 교환context switching은 CPU를 차지하던 프로세스가 나가소 새로운 프로세스를 받아들이는 작업을 말한다. 이때 두 프로세스 제어 블록의 내용이 변경된다. 실행상태에서 나가는 프로세스 제어 블록에는 지금까지의 작업 내용을 저장하고, 반대로 실행상태로 들어오는 프로세스 제어 블록의 내용으로 CPU가 다시 세팅된다. 이와 같이 두 프로세스의 프로세스 제어 블록을 교환하는 작업이 문맥 교환이다. 

2. 문맥 교환의 절차

 실행상태에 있는 프로세스 P1이 자신에게 주어진 시간을 다 사용하여 타임아웃이 되면, P1의 프로세스 제어 블록에 현재까지의 작업결과가 저장되고, P1은 준비상태로 쫓겨난다. 준비 상태에 있던 프로세스 P2가 실행상태로 가면, CPU의 레지스터가 P2의 프로세스 제어 블록 값으로 채워진다.

운영체제에서 프로세스는 하나의 작업 단위이다. 사용자가 마우스를 더블클릭하여 프로그램을 실행하면 그 프로그램은 프로세스가 된다. 이렇게 실행된 프로세스는 복잡한 과정을 거쳐 사용자가 지시한 작업을 완료한다. 여기서는 운영체제의 프로세스 과정을 살펴보겠다. 

1. 프로세스의 개념

 프로그램과 프로세스의 차이는 뭘까? 프로그램은 하드디스크같은 저장장치에 보관되어 있다가 마우스로 더블클릭하면 실행된다. 폰 노이만 구조에서 프로그램이 실행된다는 것은 해당 코드가 메모리에 올라와서 작업이 진행된다는 의미이다. 프로그램은 저장장치에 저장되어있는 정적인 상태이고, 프로세스는 실행을 위해 메모리에 올라온 동적인 상태이다. 프로세스는 컴퓨터 시스템의 작업 단위로 태스크task라고도 부른다. 

 따라서 프로그램이 실행되면 프로세스가 된다.

2. 프로그램에서 프로세스로의 전환 

 우선 운영체제는 프로그램을 메모리의 적당한 위치로 가져온다. 그와 동시에 작업지시서를 만든다. 작업지시서는 프로세스 제어블록 Process Control Block PCB라는 것이다. 프로세스 제어블록에는 프로세스를 처리하는 데 필요한 다양한 정보가 들어있다. PCB가 없으면 프로그램이 프로세스로 전환되지 못한다. 어떤 프로그램이 프로세스가 된다는 것은 운영체제로부터 프로세스 제어블록을 받았다는 의미이다. 

 PCB에 있는 정보 중 대표적인 3가지는 다음과 같다. 

• 프로세스 구분자 : 메모리에는 여러 개의 프로세스가 존재하므로 각 프로세스를 구분하는 구분자Identification ID가 필요하다 PID라고 부른다.
• 메모리 관련 정보 : CPU는 실행하려는 프로세스가 메모리의 어디에 저장되어 있는지를 알아야 작업할 수 있다. 이를 위해 PCB에는 프로세스의 메모리 위치 정보가 담겨있다. 또한 메모리 보호를 위한 경계 레지스터와 한계 레지스터도 포함되어 있다.
• 각종 중간값 : 프로세스 제어 블록에는 프로세스가 사용했던 중간값이 저장되는데, 니는 어떤 프로세스가 어느 정도 진행되었는지 표시하는 것과 유사하다. 시분할 시스템에서는 여러 프로세스가 번갈아가며 실행되기 때문에 각 프로세스는 일정시간 작업을 한 후 다른 프로세스에 CPU를 넘겨 주기 때문에 중간값을 기록해 두어야 한다.

 프로세스 A가 103번행까지 작업한 후 다른 프로세스에 CPU를 넘겨주었다고 가정하자. 시간이 흘러 다시 프로세스 A의 차례가 되면 104번행부터 작업을 시작해야 한다. 이를 위해 프로세스 제어 블록에는 다음에 작업해야 할 코드의 위치가 담긴 레지스터인 프로그램 카운터가 저장된다. 또한 작업의 중간값을 보관 중인 다른 레지스터도 같이 저장된다. 이렇게 저장된 값은 작업을 계속 진행할 수 있게 해준다. 

결론적으로 하나의 프로세스를 실행하려면 프로세스 구분자, 메모리 관련 정보, 프로그램 카운터와 각종 레지스터 같은 중간값을 관리해야 하며, 이러한 정보를 보관하는 데이터 구조가 프로세스 제어 블록이다. 프로그램이 프로세스가 되려면 메모리에 올라오는 것과 동시에 프로세스 제어블록이 생성되어야 한다. 

 프로세스 제어 블록은 운영체제가 해당 프로세스를 위해 관리하는 데이터 구조이기 때문에 운영체제 영역에 만들어진다. 또한 프로세스가 종료되면 프로세스가 메모리에서 삭제되고 프로세스 제어블록도 폐기된다. 

프로세스 = 프로그램 + PCB

프로그램 = 프로세스 - PCB

또 컴퓨터 내에 사용자가 실행한 프로세스만 있는 것은 아니다. 운영체제도 프로그램이기 때문에 프로세스 형태로 실행되어야 한다. 운영체제 프로세스를 메모리에 올리는 프로그램은 부트스트랩(부팅)이다. 부트스트랩이 많은 운영체제 관련 프로세스를 실행한 후 일반프로세스가 실행되므로 컴퓨터에는 일반 사용자의 사용자 프로세스user process 와 운영체제의 커널 프로세스kernel process가 섞여서 실행된다.

3. 프로세스의 상태

 운영체제에서는 여러가지 이유로 프로세스 상태process status가 변화된다. 일괄 작업 시스템의 경우 프로세스가 생성된 후 CPU를 얻어 실행되고 작업을 마치면 종료된다. 따라서 일괄 작업 시스템의 프로세스 상태는 생성create, 실행run, 완료terminate 이다. 시분할 시스템(요즘 프로그램들의 시스템)에서의 프로세스 상태는 일괄 작업 시스템보다 복잡하다. CPU를 얻어 실행 중인 프로세스가 중간에 다른 프로세스에 CPU를 넘겨주는 일이 빈번하기 때문이다. 운영체제에서 이제 막 프로세스가 되었거나 CPU를 사용하다가 쫓겨난 프로세스는 준비 상태에서 자기 순서를 기다린다. 

3.1 프로세스의 네가지 상태

 프로세스는 생성상태에서 PCB(프로세스 제어 블록)을 얻으면 준비상태가 된다. 여기서 디스패치되면 실행상태가 되고, 실행상태에서 타임아웃(인터럽트)가 되면 준비 상태가 된다. 실행완료하면 PCB가 떨어지고 완료상태가 된다. 아래에서 더 자세히 설명하겠다.

• 생성상태 create status : 프로세스가 메모리에 올라와 실행준비를 완료한 상태. 프로세스를 관리하는데 필요한 프로세스 제어 블록(PCB)가 생성된다. (작업 : 메모리 할당, 프로세스 제어 블록 생성)
• 준비상태 ready status : 생성된 프로세스가 CPU를 얻을때까지 기다리는 상태. CPU가 하나인 컴퓨터에서는 한번에 하나의 프로세스만 실행할 수 있기 때문에 자기 실행 순서가 될 때까지 준비 상태에서 기다려야 한다.
• 실행상태 running status : 준비상태에 있는 프로세스 중 하나가 CPU를 얻어 실제 작업을 수행하는 상태로 execute status 라고 표현하기도 한다. 실행 상태에 들어간 프로세스는 일정 시간동안 CPU를 사용할 권리를 가진다. 만약 주어진 시간을 다 사용하고도 작업이 끝나지 않았다면 프로세스는 준비상태로 돌아와 다음 차례를 기다린다. 프로세스는 자신의 작업이 끝날때까지 준비상태와 실행상태를 왔다갔다한다.
• 완료상태 terminate status : 실행 상태의 프로세스가 주어진 시간동안 작업을 마치면 완료상태로 진입한다. 완료상태는 프로세스 제어 블록이 사라진 상태를 의미한다. 

 준비상태에 있는 여러 프로세스 중 다음에 진행할 프로세스를 선정하는 일은 CPU스케쥴러(CPU Scheduler)가 담당한다. CPU스케쥴러는 준비상태의 맨 앞에서 기다리고 있는 프로세스 제어 블록을 CPU에 전달하여 작업이 이루어지도록 한다. 준비 상태의 프로세스 중 하나를 골라 실행 상태로 바꾸는 CPU스케쥴러의 작업을 디스패치dispatch라고 한다.  CPU스케쥴러는 프로세스의 모든 상태, 즉 생성, 실행, 완료에 관여하여 모든 프로세스의 작업이 원만하게 이루어지도록 관리한다.

 CPU스케쥴러에 의해 선택된 프로세스는 실행상태에서 일정 시간동안 작업을 하는데, 프로세스에 배당된 작업시간을 타임 슬라이스 또는 타임 퀸텀이라고 부른다. 프로세스는 자신에게 주어진 하나의 타임 슬라이스 동안 작업을 끝내지 못하면 다시 준비 상태로 돌아가는데 이를 타임아웃time out이라고 한다.

 새로운 프로세스가 실행상태로 돌아오면 CPU는 일정시간(타임슬라이스)이 흐른 뒤 알려달라고 클럭에 요청한다. 이는 알람을 맞춰놓는 것과 같다. 타임아웃, 인터럽트는 클럭으로부터의 인터럽트이다.

3.2 프로세스의 다섯가지 상태

 프로세스는 생성, 준비, 실행, 완료라는 네가지 상태만으로 작업을 진행하는데 큰 문제가 없다. 그러나 오늘날의 운영체제의 효율성을 고려하여 한가지 상태를 더 만들었다. 어떤 프로세스가 실행 상태에 들어가 입출력을 요구했다고 가정해보자. 인터럽트 시스템에서 프로세스가 입출력을 요구하면 CPU가 직접 데이터를 가져오지 않고 입출력 관리자에게 명령을 내린다. 이 상태에서 프로세스는 요청한 작업이 끝날때까지 다음 작업을 할 수 없다. 따라서 CPU는 아무작업을 하지않고 기다리게 되어 효율성이 떨어진다.

 입출력을 요구한 프로세스가 입출력이 완료될때까지 기다리는 상태를 대기상태blocking state 라고 한다. 이는 작업 효율성을 높이기 위해 입출력을 요청한 프로세스를 실행상태에 두지 않고 대기상태로 옮기는 것이다. 입출력을 요구한 프로세스가 대기 상태로 옮겨지면 CPU스케쥴러는 준비 상태에 있는 프로세스 중 하나를 가져다 실행상태로 만든다. 그러면 시스템 입장에서는 새로운 작업을 진행하게 되어 효율성이 높아진다.

 대기상태의 프로세스는 요청한 입출력이 완료되면 입출력 관리자로부터 인터럽트를 받는다. 대기 상태에서 입출력이 끝난 프로세스는 준비상태로 돌아가 자기 차례를 기다린다.

프로세스의 다섯가지 상태

• 생성상태 create status : 프로그램이 메모리에 올라오고 운영체제로부터 프로세스 제어 블록을 할당받은 상태
• 준비상태 ready status : 실행 대기 중인 프로세스가 자기 순서를 기다리는 상태. 프로세스 제어 블록을 준비 큐ready queue에서 기다리며 CPU스케쥴러에 의해 관리된다. 지금까지 준비 큐가 하나인 것처럼 설명했지만 실제로는 다수의 준비 큐가 운영된다. CPU 스케쥴러는 준비 상태에서 큐를 몇 개 운영할지, 큐에 있는 어떤 프로세스의 프로세스 제어 블록을 실행 상태로 보낼지를 결정한다. 
   CPU스케쥴러가 어떤 프로세스 제어 블록을 선택하는 작업은 dispatch(PID)명령으로 처리하는데, 여기서 PID는 프로세스 구분자이다. CPU 스케쥴러가 dispatch(PID)를 실행하면 해당 프로세스가 준비 상태에서 실행상태로 바뀌어 작업이 이루어진다. 
• 실행상태 running status : 프로세스가 CPU를 할당받아 실행되는 상태. 준비상태에 있는 많은 프로세스 중 실행상태에 들어가는 프로세스는 CPU의 개수 만큼이다. 실행상태에 있는 프로세스는 자신에게 주어진 시간, 즉 타임슬라이스 동안만 작업할 수 있다. 그 시간을 다 사용하면 timeout(PID)가 실행된다. 
   timeout(PID)는 프로세스 제어 블록을 실행상태에서 준비상태로 옮긴다. 만약 실행상태동안 작업이 완료되면 exit(PID)가 실행되어 프로세스가 정상 종료된다. 실행상태에 있는 프로세스가 입출력을 요구하면 block(PID)를 실행한다.
• 대기상태 blocking state : 효율성을 위해 만들어진 상태이다. 입출력이 완료되면 인터럽트가 발생하고, 대기상태에 있는 여러 프로세스 중 해당 인터럽트로 깨어날 프로세스를 찾는데 이것이 wakeup(PID)이다. wakeup(PID)로 해당 프로세스의 프로세스 제어 블록이 준비상태로 이동하게 된다. 어떤 프로세스가 대기 상태에서 준비 상태로 이동하는 것은 인터럽트 때문이다. 인터럽트는 이렇게 입출력으로도 발생하고, 어떤 이벤트에 의해서도 발생한다.
• 완료상태 terminate status

3.3 휴식 상태와 보류 상태

 대부분의 프로세스는 생성, 준비, 실행, 대기, 완료 상태로 운영된다. 이것을 활성상태 active status 라고 한다. 프로세스의 상태는 활성 상태외에 또다른 상태가 있다.

• 휴식 상태 pause status : 프로세스가 작업을 일시적으로 쉬고 있는 상태. 유닉스에서 프로그램 실행 도중에 ctrl+z를 하면 볼 수 있다. 해당 프로그램이 종료된 것처럼 보이지만, 사실은 실행을 잠시 멈춘 것이다. jobs나 ps명령어로 프로세스의 상태를 보면 'stop'인 것을 알 수 있다. 
• 보류 상태 suspend status : 프로세스가 메모리에서 잠시 쫓겨난 상태. 휴식상태와 차이가 있다. 다음과 같은 경우에 보류 상태가 된다.
  
  1. 메모리가 꽉차서 일부 프로세스를 메모리 밖으로 내보낼 때
  2. 프로그램에 오류가 있어서 실행을 미뤄야 할 때
  3. 바이러스 같이 악의적인 공격을 하는 프로세스라고 판단될 때
  
  보류상태로 들어간 프로세스는 메모리 영역에서 쫓겨나 스왑영역swap area에 보관된다. 보류상태는 대기 상태에서 옮겨진 보류 대기 상태 block suspend status와 준비 상태에서 옮겨진 보류 준비 상태로 구분되며, 보류 대기 상태에서 입출력이 완료되면 보류 준비 상태로 옮겨간다. 

CPU성능 향상 방법은 CPU의 클럭을 높이거나 캐시의 크기를 늘리는 것이다. 그러나 CPU 클럭을 높이면 발열문제가 있기때문에 현재의 기술로서는 5Hz가 넘는 CPU개발은 힘들다. 캐시의 크기를 늘리는 것도 비용문제 때문에 한계가 있다. 그래서 CPU 개발사들은 CPU의 성능 향상을 위해 CPU의 핵심 기능을 가진 코어를 여러개 만들거나, 동시에 실행 가능한 명령의 개수를 늘리는 방법을 사용한다. 

1. 병렬 처리의 기법

 병렬처리 parallel processing는 동시에 여러 개의 명령을 처리하여 작업의 능률을 올리는 방식이다. 요즘 컴퓨터용 CPU나 스마트폰용 CPU의 사양을 보면 듀얼 코어duel core, 쿼드 코어 quad core라고 쓰여 있는데, 이는 CPU의 주요 기능을 담당하는 코어가 1개가 아니라 2개, 4개 라는 뜻이다. 

 여러 개의 명령을 동시에 처리하는 병렬처리는 코어가 여러 개인 CPU는 물론, 코어가 하나인 CPU에서도 작동가능하다. 서로 겹치지 않는 작업을 동시에 진행함으로써 여러 개의 작업을 하는 시간을 줄일 수 있다. 하나의 코어가 여러 개의 스레드thread를 이용한다. 병렬 처리에서는 이러한 방식을 파이프라인 기법 이라고 한다. 여기서 스레드는 CPU가 처리할 수 있는 작업의 단위를 나타내며, 여러 개의 스레드를 동시에 처리하는 방법을 CPU멀티 스레드 라고 한다. 

 병렬 처리에는 파이프인 기법 말고도 슈퍼스칼라 기법이 있다. 예를 들면 듀얼 코어 CPU는 한 CPU에 작업을 처리하는 코어가 2개씩 있고, 슈퍼스칼라 기법을 활용하여 2개의 작업을 동시에 처리할 수 있다.

**CPU의 멀티 스레드**

 스레드는 CPU의 작업 단위로, 한 번에 여러 개의 스레드를 처리하는 방식을 멀티스레드 라고 한다. 스레드는 운영체제가 사용하는 프로그래밍 기법을 가리키는 말이기도 하다. 

2. 병렬 처리 시 고려 사항

1. 상호의존성이 없어야 병렬처리가 가능하다 : 각 명령이 서로 독립적이고 앞의 결과가 뒤의 명령에 영향을 미치지 않아야 한다는 뜻이다.
2. 각 단계의 시간을 거의 일정하게 맞춰야 병렬처리가 원만하게 이루어진다.
3. 전체 작업 시간을 몇 단계로 나눌지 잘 따져보아야 한다 

 병렬 처리에서 작업을 N개로 쪼개었을 때 N을 병렬처리의 깊이 depth of parallel processing 이라고 한다. 병렬처리의 깊이가 1인 경우는 병렬처리가 없는 일반적인 작업이다. 병렬처리의 깊이가 2인 경우는 작업을 2단계로 나눈 것으로 동시에 처리할 수 있는 작업의 개수가 최대 2개이다.

이론적으로는 N이 커질수록 성능이 높아진다. 하지만 작업을 너무 많이 나누면 각 단계마다 작업을 이동하고 새로운 작업을 불러오는데 시간이 너무 많이 걸려서 오히려 성능이 떨어진다. 이러한 오버헤드를 고려하여 보통은 병렬 처리의 깊이를 10~20으로 한다.

3. 병렬 처리 기법

 CPU내에서 명령어는 제어장치가 처리한다. 제어장치는 명령어를 가져와 해석한 후 실행하고 결과를 저장하는 과정을 반복한다. 이러한 과정 전체를 하나의 스레드라고 하며, 스레드를 이루는 각 단계는 CPU의 클럭과 연동되어 한 클럭에 한번씩 이루어진다. 다음은 하나의 스레드의 과정이다.

1. 명령어 패치 Instruction Fetch IF : 다음에 실행할 명령어를 명령어 레지스터에 저장
2. 명령어 해석 Instruction Decode ID 
3. 실행 EXecution EX
4. 쓰기 WriteBack WB : 실행된 결과 메모리에 저장

3.1 파이프라인 기법

 하나의 코어에는 여러 개의 스레드가 겹쳐서 실행된다. 명령을 겹쳐서 실행하는 것을 파이프라인 기법이라고 한다.

 파이프라인 기법에서는 명령어를 여러개의 단계로 분할한 후, 각 단계를 동시에 처리하는 하드웨어를 독립적으로 구성한다. 파이프라인 기법에서는 명령어 처리의 단계마다 독립적으로 구성하여 각 단계가 쉬지 않고 명령어를 처리할 수 있게 한다.

 파이프라인 기법에는 여러가지 문제가 있는데, 이를 파이프라인의 위험이라고 일컫는다. 파이프라인 위험에는 다음과 같은 것들이 있다. 

 ＊데이터 위험 Data Hazard

 데이터의 의존성 때문에 발생하는 문제이다. 예를 들어 A=C+D , E=A*2 와 같은 식을 순차적으로 실행해야 된다고 할 때, 데이터 A를 필요로 하는 두번째 명령어는 앞의 명령어가 끝날때까지 동시에 실행되어선 안된다. 데이터 위험은 파이프라인의 명령어 단계를 지연하여 해결한다.

＊제어 위험 Control Hazard

 분기를 하는 if문 혹은 바로가기의 goto문 같은 명령에서 발생한다. 프로그램 카운터 값을 갑자기 변화시켜 발생하는 위험이다. 보통 순차적으로 실행되는데 goto문 때문에 다른 문장으로 이동하게 되면 현재 동시에 처리되고 있는 명령어들이 쓸모없어진다. 제어 위험은 분기 예측이나 분기 지연으로 해결한다. 

＊구조 위험 Structural Hazard

 서로 다른 명령어가 같은 자원에 접근하려 할 때 생긴다. 예를 들어 명령어 A가 레지스터 RX를 사용하고 있는데 병렬 처리되는 명령어B도 RX를 사용해야 한다면 충돌한다. 이 문제는 해결하기 어렵다고 알려져 있다. 

파이프라인 기법을 intel CPU에서는 하이퍼스레드라고 부른다. 하이퍼스레드는 CPU에 여러개의 작업을 동시에 진행할 수 있는 부가장치를 만들어 하나의 코어에서도 여러 개의 스레드를 동시에 진행할 수 있게 한다. 

3.2 슈퍼스칼라 기법

 파이프라인을 처리할 수 있는 코어를 여러 개 구성하여 복수의 명령어가 동시에 실행된다. 파이프라인 기법과 마찬가지로 슈퍼스칼라 기법에서는 처리되는 명령어가 상호의존성 없이 독립적이여야 하며, 이를 위한 처리도 컴파일러에서 이루어지도록 오늘날의 CPU는 대부분 이 기법을 사용한다. 

이 외에도 슈퍼파이프라인 기법, 슈퍼파이프라인 슈퍼스칼라 기법이 있는데 모두 슈퍼스칼라 기법과 파이프라인의 결합이라고 보면 된다. 

3.3 VLIW 기법

 Very Long Instruction Word 이 기법은 파이프라인과 슈퍼스칼라 기법같은 병렬처리 기법과는 다르다. VLIW기법은 CPU가 병렬처리를 지원하지 않는 경우 소프트웨어적으로 병렬처리하는 방법이다. 동시에 수행할 수 있는 명령어들을 컴파일러가 추루하고 하나의 명령어로 압축하여 실행한다. 병렬처리 기법들에 비해 동시에 처리되는 명령어가 작다(CPU가 병렬처리 지원 안할때만 사용하기 때문임) 또한 앞의 병렬처리 기법들은 명령어 실행 시 이루어지지만 VLIW는 컴파일 시 병렬처리가 이루어진다. 

1. 인터럽트의 개념 : 초기의 컴퓨터에는 주변장치가 많지 않았다. 당시에는 CPU가 직접 입출력장치에서 데이터를 가져오거나 내보냈는데, 이러한 방식을 폴링Polling 방식이라고 한다. 폴링 방식에서는 CPU가 입출력장치의 상태를 주기적으로 확인하여 일정한 조건을 맞출 때 데이터를 처리한다. CPU가 명령과 해석이라는 본래 역할 외에 모든 입출력까지 관여해야 하므로 작업효율이 떨어진다. 오늘날은 입출력 장치가 많아져 폴링방식은 효율이 떨어진다. 이것을 해결하기 위해 등장한 것이 인터럽트interrupt 방식이다. 인터럽트 방식은 CPU의 작업과 저장장치의 데이터 이동을 독립적으로 운영함으로써 시스템의 효율을 높인다. 즉, 데이터의 입출력이 이루어지는 동안 CPU가 다른 작업을 할 수 있다. 

2. 인터럽트 방식의 동작 과정 

1. CPU가 입출력 관리자에게 입출력 명령을 보낸다. 
2. 입출력 관리자는 명령받은 데이터를 메모리에 가져다놓거나 메모리에 있는 데이터를 저장장치로 옮긴다.
3. 데이터 전송이 완료되면 입출력 관리자는 완료신호를 CPU에 보낸다. 

 입출력관리자가 CPU에 보내는 완료 신호를 인터럽트 라고 한다. CPU는 입출력 관리자에게 작업지시를 내리고 다른 일을 하다가 완료 신호를 받으면 하던 일을 중단하고 옮겨진 데이터를 처리한다. 이처럼 작업을 중단하고 처리해야 하는 신호라는 의미에서 인터럽트 라고 한다. 

 컴퓨터에는 하드디스크 뿐만 아니라, 마우스, 키보드, 프린터 등 다양한 입출력 장치가 있다. 하드디스크가 여러 개 장착된 경우, USB드라이버와 같은 외부 저장장치를 사용하는 경우 등 여러가지 경우가 있다. 인터럽트 방식에서는 많은 주변장치 중 어떤 작업이 끝났는지를 CPU에 알려주기 위해 인터럽트 번호interrupt number를 사용한다. 인터럽트 번호는 완료 신호를 보낼 때 장치의 이름대신 사용하는 장치의 고유번호로서 운영체제마다 다르다. 윈도우 운영체제의 경우 인터럽트 번호를 IRQ(Interupt ReQuest)라고 부르며 키보드의 IRQ는 1번, 마우스의 IRQ는 12번, 첫번째 하드디스크의 IRQ는 14번과 같이 구분해서 사용한다. 

 CPU는 입출력 관리자에게 여러 개의 입출력 작업을 동시에 시킬 수 있다. 이 경우 여러 작업이 동시에 완료되고 그때마다 인터럽트를 여러 번 사용해야 하는데 이는 매우 비효율적이다. (인터럽트가 너무 자주 일어나기 때문에 CPU가 작업을 못하게 된다) 그래서 여러 개의 인터럽트를 하나의 배열로 만든 인터럽트 벡터interrupt vector를 사용한다. 인터럽트는 1.입출력요청 2. 데이터 전송 3. 인터럽트 발생 순으로 진행된다. 만약 0번에서 5번까지의 인터럽트 벡터가 있다고 가정하자. 그중 0번과 3번이 완료되었다고 가정하자. 그렇다면 인터럽트는 0번과 3번이 동시에 발생한다. CPU가 인터럽트 벡터를 받으면 0번과 3번을 동시에 처리하는 것이다. 

 입출력 작업이 완료되었음을 CPU에 알리기 위한 것 외에도 다양한 종류의 인터럽트가 있다. 사용자가 컴퓨터의 전원을 눌러 강제로 종료하면 CPU는 하던 일을 모두 멈추고 처리중인 데이터를 안전하게 보관한 뒤, 시스템을 종료해야 한다. 또한, 메모리에서 실행 중인 어떤 작업이 자신에게 주어진 메모리 영역을 넘어서 작업을 하려 하거나 0으로 숫자를 나누는 경우에도 모두 인터럽트가 발생하게 된다. 

3. 직접 메모리 접근 Direct Memory Access DMA

 과거의 운영체제는 폴링 방식을 사용했기 때문에 CPU가 메모리나 주변장치에 대한 모든 권한을 가지고 있었다. 그러나 효율성을 높이기 위해 인터럽트 방식을 사용하게 되면서 입출력 관리자가 데이터의 입출력을 맡게 되었다. 입출력이 필요할 때 CPU는 입출력 관리자에게 입출력 요청을 보내고 자신은 하던 일을 계속한다. 명령을 받은 입출력 관리자는 CPU가 요청한 데이터를 메모리에 가져다놓아야 하는데 이때 문제가 있다. 메모리는 CPU만 접근 권한을 가진 작업공간이라 입출력 관리자는 접근이 불가능하다는 것이다. 따라서 입출력관리자에게는 CPU의 허락 없이 메모리에 접근할 수 있는 권한이 필요한데, 이러한 권한을 직접 메모리 접근DMA 라고 한다. 데이터 전송을 지시받은 입출력 관리자는 직접 메모리 접근 권한이 있어야 CPU의 관여없이 작업을 완료할 수 있다. 

4. 메모리 매핑 입출력 Memory-mapped I/O MMIO, I/O Mapped I/O

 직접 메모리 접근은 인터럽트 방식의 시스템을 구성하는데 필수 요소이다. MMIO방식은 메모리와 입출력장치가 하나의 연속된 주소영역에 할당된다. 그러나 직접 메모리 접근을 사용하면 메모리가 복잡해진다. 메모리에는 CPU가 사용하는 데이터와 입출력장치가 사용하는 데이터가 섞이게 된다. 직접 메모리 접근을 통해 들어온 데이터를 메모리에 아무렇게나 둔다면 CPU가 사용하는 데이터와 섞여서 관리하기 어려울 것이므로 이를 막기 위해 메모리를 나누어 사용하는 방법이 도입되었다. CPU가 사용하는 메모리 공간과 직접 메모리 접근을 통해 들어오거나 나가는 데이터를 위한 공간을 분리해두었다. 이것이 I/O Mapped I/O 방식이다. 

5. 사이클 훔치기

 메모리는 CPU가 관할하는 중요한 장치이지만 직접 메모리 접근을 통해 입출력 장치로 메모리를 사용할 수 있게 되었다. 그러나 만약 동시에 접근을 하려고 하면 어떻게 될까? 보통 CPU가 양보를하게 된다. 그 이유는 CPU의 작업속도보다 입출력장치의 속도가 훨씬 느리기 때문이다. 이러한 상황을 사이클훔치기 Cycle Stealing 이라고 하게된다.

1. 하드웨어의 구성

 컴퓨터는 중앙처리장치 CPU, 메인 메모리, 입력장치, 출력장치, 저장장치로 구성된다.

중앙처리장치와 메인 메모리를 필수장치, 입력장치, 출력장치와 저장장치를 주변장치라고 한다. 

메인 메모리는 전력이 끊기면 데이터를 잃어버리기 때문에 영구히 보관하려면 하드디스크나 USB메모리를 사용해야 된다.

(메인 메모리와 RAM은 다르다. 메인 메모리에 주로 사용되는 것이 RAM인 것이지 RAM에는 HDD 등의 장치들도 포함된다.)

1.1 CPU와 메모리

 CPU는 명령어를 해석하여 실행하는 장치이다.

메모리는 작업에 필요한 프로그램과 데이터를 저장하는 장소가 바이트 단위로 분할되어 있다. 분할 공간마다 주소로 구분을 한다.

1.2 입력장치와 출력장치

 입출력장치는 외부의 데이터를 컴퓨터에 입력하는 장치이다. 마우스, 키보드, 프린터, 모니터 등이 해당한다.

1.3 저장장치

 메인 메모리는 전자의 이동으로 데이터를 처리하지만 하드디스크나 CD와 같은 저장장치는 구동장치가 있는 기계이므로 상대적으로 속도가 느리다. 느리지만 하드디스크나 CD를 쓰는 이유는 저장용량에 비해 가격이 싸기 때문이다.

또, 전원의 온/오프와 관계없이 데이터를 영구적으로 저장할 수 있다. 저장장치의 종류는 어떤 것을 이용하여 저장하는지에 따라 나누어진다. 

 1) 자성을 이용하는 저장장치 : 카세트 테이프, 플로피 디스크, 하드 디스크

 2) 레이저를 이용하는 저장장치 : CD, DVD, 블루레이디스크

 3) 메모리를 이용하는 저장장치 : USB 드라이버, SD 카드, CF 카드, SSD

1.4 메인보드

컴퓨터의 다양한 부품은 버스로 연결되어있다. 버스가 정해진 경로로 다니는 것처럼 컴퓨터의 버스는 일정한 규칙에 따라 각 장치에 데이터를 전송하는 역할을 한다.

메인 보드는 CPU와 메모리 등 다양한 부품을 연결하는 커다란 판이다. 전력이 공급되면 버스로 연결된 부품이 작동한다. 메인 보드에는 각종 부품을 꽂을 수 있는 단자가 있는데, 이 단자에 그래픽 카드, 사운드 카드, 랜 카드 등이 기본으로 장착되어 있기도 하고, 성능 향상을 위해 따로 장착하기도 한다.

버스

각 장치를 연결하는 선의 집합이자 데이터가 지나다니는 통로이다. 컴퓨터 안의 부품들 간에, 또는 컴퓨터 간에 데이터와 정보를 전송하는 통로라고 생각하면 된다.

랜카드

랜LAN card 는 Network card라고도 불린다. 랜카드가 컴퓨터에 설치되어 있어야 바로 랜선이 꽂히는 포트가 생기는데 요즘은 대체적으로 메인보드에 내장되어 있다.

2. 폰 노이만 구조

 오늘날의 컴퓨터는 대부분 폰 노이만 구조를 따른다. 폰 노이만 구조란 CPU, 메모리, 입출력장치, 저장 장치가 버스로 연결되어 있는 구조를 말한다. 폰 노이만 구조의 이전에는 컴퓨터의 업그레이드를 위해서는 전체를 갈아엎어야 됐는데, 폰 노이만 구조가 등장한 이후로 하드웨어는 그대로 둔체 작업을 위한 프로그램만 교체하면 된다.

가장 중요한 특징은 '모든 프로그램은 메모리에 올라와야 실행할 수 있다.'라는 것이다.

3. 하드웨어 사양 관련 용어

 클럭clock

 클럭은 CPU의 속도와 관련이 있다. CPU가 작업할 때 일정한 박자가 있는데 이 박자를 만들어내는것을 클럭이라고 한다. 클럭이 일정 간격으로 틱을 만들면 거기에 맞춰서 CPU안의 구성 부품이 작업을 한다. 클럭이 틱을 보낼 때마다 데이터를 보내거나 받는다. 디지털 장치의 부품들을 움직이게 하는 전기적 신호를 클럭이라고 한다. 

헤르츠Hz

 클럭틱이 발생하는 속도를 헤르츠로 표시한다. 1초에 클럭틱이 한번이면 1Hz, 1000번이면 1kHz라고 한다.

시스템 버스와 CPU 내부버스

시스템 버스는 메모리와 주변장치를 연결하는 버스로 FSB(Front-Side Bus), 즉 전면 버스라고 한다.

CPU 내부버스는 CPU내부에 있는 장치를 연결하는 버스로 BSB(Back-Side Bus), 후면 버스라고 한다.

CPU 내부버스의 속도는 CPU클럭과 같다. 그래서 CPU 내부버스는 시스템 버스보다 훨씬 빠르다.

CPU는 CPU 내부버스의 속도로 작동하고, 메모리는 시스템 버스의 속도로 작동하기 때문에 두 버스의 속도 차이로 인해 작업 지연에 문제가 생긴다.

 1. 커널과 인터페이스

커널Kernel은 프로세스 관리, 메모리 관리, 저장장치 관리와 같은 운영체제의 핵심적인 기능을 모아놓은 것이다.

자동차에 비유하자면 커널은 자동차의 엔진에 해당한다. 따라서 운영체의 성능은 커널이 담당한다고 생각하면 된다.

즉, OS의 핵심부분이고 항상 메모리에 적재되어 있다. 

스마트폰 운영체제에도 커널이 있다. 유닉스 운영체제의 커널을 이용하여서 만든 구글의 안드로이드가 그 예이다. 유닉스 운영체제는 다양한 제조사가 이용하도록 커널 소스코드가 공개되어있다.

같은 커널을 이용하더라도 다른 인터페이스가 장착이 가능하다. 다른 인터페이스가 장착된다면 다른 운영체제로 보이게 된다.

우리가 사용하는 운영체제도 커널은 같은데 인터페이스가 달라서 다른 운영체제처럼 보이는 것이 많다.

예를 들면 유닉스의 사용자 인터페이스는 셸shell을 사용하는데 여기에는 C셸, T셸, 배시셸 등 여러 종류가 있다. 스티브 잡스의 매킨토시의 MacOS도 유닉스 커널을 사용한다. 사람들은 좋은 인터페이스의 컴퓨터를 사용하려는 경향이 있다.

(이를 이용한 사람이 바로 스티브 잡스이다.)

왜 인터페이스를 사용하는 것일까??

프로세스는 개발된 프로그래밍 언어가 모두 다르고, 시스템 콜(아래에서 설명하겠다)을 호출하는 방식이 모두 다르기 때문에 중간에 추상 계층이 필요하다. 

운영체제와 커널의 차이는 무엇일까?

아래 그림에서도 볼 수 있듯이 커널은 운영체제에 포함되는 하나의 모듈의 개념이다.

운영체제는 커널을 포함해, 컴퓨터 시스템을 총괄하는 개념이다. 

2. 시스템 호출과 디바이스 드라이버(커널 내부에 있는 것들이다)

1) 시스템 호출 System Call

시스템 콜은 커널이 자신을 보호하기 위해 만든 인터페이스이다. 커널은 사용자나 응용프로그램이 자원에 직접 접근하는 것을 차단한다.

자원을 이용하려면 시스템 호출이라는 인터페이스를 이용하여서 접근해야 한다. 프로세스가 OS 커널이 제공하는 서비스를 이용하고 싶을 때, 시스템 콜을 이용해서 실행한다.

직접 접근해야 더 편리할 거 같은데 왜 이렇게 할까?

직접 접근을 하면 사용자가 모든 것을 처리해야 한다. 그리고 보안도 취약해진다. 그래서 더 편리하고 안전한 시스템 호출이라는 방식을 사용한다. 예를 들어, C언어에서 printf 함수도 시스템 호출 함수의 한 종류이다. 

시스템 콜이 호출되면 커널은 CPU에게 Interrupt를 발생하고, CPU는 다음 명령을 실행할 때 해당 내용을 체크하고, 해당 커널 코드를 실행하게 된다. 

API와 SDK

API란 Application Programming Interface의 약자로 응용프로그램 인터페이스라고 한다. 응용프로그램이 자신과 관련된 프로그램을 만들 수 있도록 제공하는 인터페이스이다. 예를 들어 포토샵을 이용할 때, 포토샵 자체가 수백가지 필터를 모두 제공하지 않는다. 자신이 필요하면 포토샵은 필터를 개발하려는 사람들을 위해 다양한 프로그래밍 인터페이스를 제공한다.

UI가 사용자와 사용자가 다룰 대상을 연결한다면, API는 프로그램과 또 다른 프로그램을 연결해주는 일종의 다리라고 볼 수 있다. 

SDK System Developer's Kit는 프로그램 개발자를 위해 API 및 API 사용 메뉴얼 뿐만 아니라 프로그램 개발에 필요한 코드편집기와 에뮬레이터(다른 프로그램이나 장치를 모방하는 컴퓨터 프로그램) 같은 개발용 응용 프로그램까지 하나로 묶어서 배포하는 개발 툴이다.

SDK를 활용하여 개발자는 이러한 시스템, 프로그래밍 언어에 따라 애플리케이션을 개발할 수 있다.

예를 들어 안드로이드 SDK인 Android Studio가 있다.

 2) 드라이버 

커널과 하드웨어의 인터페이스는 드라이버driver가 담당한다. 커널이 모든 하드웨어에 맞는 인터페이스를 다 개발하기는 어렵다. 커널은 입출력의 기본적인 부분만 제작하고 하드웨어의 특성을 반영한 소프트웨어를 하드웨어 제작자에게 받아 커널이 실행될 때 함께 실행되도록 한다.

이를 디바이스 드라이버 라고 한다.

예를 들어 그래픽카드나 프린터 같은 장치를 설치하고 해당 장치의 디바이스 드라이버를 설치해 주어야 한다.

3. 커널의 구성

커널의 기능은 프로세스 관리, 메모리 관리, 파일 시스템 관리, 입출력 관리, 프로세스간 통신 관리이다.

커널은 이러한 기능을 `어떻게` 구현하는가에 따라 단일형 구조 커널, 계층형 구조 커널, 마이크로 구조 커널로 구분된다.

1) 단일형 구조 커널 monolithic architecture

초창기 커널 구조로 커널의 핵심 기능을 구현하는 모듈들이 구분없이 하나로 구성된다. 

ex) MS-DOS, VMS, 초기의 유닉스

프로그램 만들 때 main()에 모두 때려박은거라고 생각하면 된다. 프로그래밍에서처럼 모듈간의 통신 비용이 줄어들어 효율적으로 운영가능하다(속도가 빠름).

그런데 모든 모듈이 묶여잇어 버그나 오류 처리가 어렵다. 작은 결함이 크게 확산이 가능하다.

2) 계층형 구조 커널 layered architecture

비슷한 구조기능을 가진 모듈을 묶어서 하나의 계층으로 만든다. 디버깅 하기 쉽다

ex) 마이크로소프트의 윈도우 운영체제

3) 마이크로 구조 커널

커널이 계속 커져서 이제 오류가 잡기가 어려워졌다. 그래서 생긴 것이 마이크로 구조 커널이다.

프로세스 관리, 메모리 관리, 프로세스 간 통신 관리 등 가장 기본적인 기능을 제공하고 많은 부분이 사용자 영역에 구현되어 있다.

각 모듈은 세분화되어 존재하고 모듈 간의 정보교환은 프로세스 간 통신을 이용하여 이루어진다. 

ex) 마하Mach -> 애플의 PC운영체제인 OS X와 모바일 iOS의 커널로 사용된다.

4. 가상 머신

맨 첨에 C언어로 유닉스 운영체제를 만들었는데, C언어는 호환성이 떨어진다.

윈도우 운영체제와 호환이 안되었던 것이다. 이걸 해결한 언어가 자바Java언어이다.

작동원리는 가상 머신virtual machine 을 만들고 그 위에서 작동하도록한다. 가상 머신은 운영체제와 응용 프로그램 사이에서 작동하는 프로그램이다. 

ex) JVM (Java Virtual Machine)

https://programmers.co.kr/learn/courses/30/lessons/42862

[문제 설명]

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

[제한사항]

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

[입출력 예]

[입출력 예 설명]

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

[풀이 과정]

[풀이 1] -> [풀이 2]((시행착오)) -> [풀이 3]

[그리디 알고리즘](https://jobdong7757.tistory.com/6) : 이 문제는 전체적으로 최적의 해가 있는 문제가 아니다. 여벌의 체육복이 있고, 앞이나 뒤에 도둑맞은 사람이 있다면 체육복을 그 때 그때 상황에 따라서 나누어 주어야 되기 때문에 부분적으로 최적인 해가 전체적으로 최적인 해가 아닌 경우가 생기게 된다.
 

[풀이 1] : 3, 7, 12번 오류

 먼저 lost.size()만큼 반복문을 실행한다. temp라는 변수에 lost[i]-1을 저장해서 lost의 왼쪽의 수가 reserve에 있는지 확인해 주는 것이다. <algorithm>헤더에 있는 find()함수를 이용하여서 reserve 배열에 있다면 lost를 0으로 바꾸어준다. 그리고 lost[i]+1을 if - else구문으로 확인해준다. 

 마지막에는 lost에 0이 아니면 여벌의 체육복을 받지 못한것이므로 count에 lost가 0이 아닌 것들의 수를 파악해주고 n에서 빼주었다. 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer;
    for(int i=0;i<lost.size();i++){
        int temp = lost[i]-1;
        if(lost[i]!=0){
            if(find(reserve.begin(),reserve.end(),temp)!=reserve.end()){
                lost[i]=0;
                int index = find(reserve.begin(),reserve.end(),temp)-reserve.begin();
                reserve.erase(reserve.begin()+index);
            }
            else{
                int temp = lost[i]+1;
                if(find(reserve.begin(),reserve.end(),temp)!=reserve.end()){
                    lost[i]=0;
                    int index = find(reserve.begin(),reserve.end(),temp)-reserve.begin();
                    reserve.erase(reserve.begin()+index);
                }
            }
        }
    }
    int count = 0;
    for(int i=0;i<lost.size();i++){
        if(lost[i]!=0) count++;
    }
    answer = n - count;
    return answer;
}

3번, 7번, 12번에서 오류가 났다. 제한사항의 마지막인 '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.' 이 부분의 테스트 케이스에서 오류가 난 것 같다. 

[풀이 2] : 테스트 7 오류

[풀이 2]에서는 [풀이 1] 앞에 반복문을 통해 lost와 reserve가 같은, 즉 제한사항의 마지막 번을 확인해 주었다. 같은 것이 있다면 lost와 reserve 양쪽 모두 해당하는 것을 제거해주었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer;
    for(int i=0;i<lost.size();i++){
        if(find(reserve.begin(),reserve.end(),lost[i])!=reserve.end()){
            int index = find(reserve.begin(),reserve.end(),lost[i])-reserve.begin();
            reserve.erase(reserve.begin()+index);
            lost.erase(lost.begin()+i);
        }
    }
    for(int i=0;i<lost.size();i++){
        int temp = lost[i]-1;
        if(lost[i]!=0){
            if(find(reserve.begin(),reserve.end(),temp)!=reserve.end()){
                lost[i]=0;
                int index = find(reserve.begin(),reserve.end(),temp)-reserve.begin();
                reserve.erase(reserve.begin()+index);
            }
            else{
                int temp = lost[i]+1;
                if(find(reserve.begin(),reserve.end(),temp)!=reserve.end()){
                    lost[i]=0;
                    int index = find(reserve.begin(),reserve.end(),temp)-reserve.begin();
                    reserve.erase(reserve.begin()+index);
                }
            }
        }
    }
    int count = 0;
    for(int i=0;i<lost.size();i++){
        if(lost[i]!=0) count++;
    }
    answer = n - count;
    return answer;
}

아직까지 7번 테스트 케이스에서 오류가 났다.. 

[풀이 3]

 중복제거에서 오류가 나는 것같아서 새로운 배열을 통해 해결하였다. 새로운 int 배열 student를 만들어서 n개의 원소를 1로 초기화시킨다. lost에 해당하는 원소가 student에 있으면 빼주고, reserve에 있으면 더해준다. 그래서 2보다 크면 왼쪽먼저 확인해서 0이면 주고, 그 뒤에 오른쪽을 확인한다. 

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n,1);
    
    for(int i=0;i<lost.size();i++){
        student[lost[i]-1]--;
    }
    
    for(int i=0;i<reserve.size();i++){
        student[reserve[i]-1]++;
    }
    
    for(int i=0;i<student.size();i++){
        if(student[i]==2){
            if(i!=0){
                if(student[i-1]==0) {
                    student[i]--;
                    student[i-1]++;
                }
            }
        }
        if(student[i]==2){
            if(i+1<student.size()){
                if(student[i+1]==0){
                    student[i+1]++;
                    student[i]--;
                }
            }
        }
    }
    for(int i=0;i<student.size();i++){
        if(student[i]!=0) answer++;
    }
    return answer;
}

운영체제의 역사는 흐름을 파악하기 위해서 중요하다. 또한 P2P와 클라우드 컴퓨팅 같은 용어들의 등장배경도 알아볼 수 있다.

1. 초창기 컴퓨터(1940) - '애니악' 2진법 사용의 배경이 되었다. 아직까지 운영체제는 없다.

2. 일괄 처리 시스템 (1950) 

IC(Integrated Circuit)이라고 논리회로를 아주 작게 구현하였다. 천공카드리더punch card reader라는 입력장치(OMR의 원조라고 보면 된다)와 라인프린터라는 출력장치를 가지고 있게 되었다. 모든 작업을 한꺼번에 처리해야 하고 실행 중간에 사용자가 데이터를 입력하거나 수정이 불가하다. 여기에 사용되는 운영체제의 방식이 일괄 처리 시스템 방식이다.

3. 대화형 시스템(1960)

키보드와 모니터가 등장하였다. 작업 중간에 사용자가 입력이 가능해서 중간 결과값도 출력 가능하다. 이것을 대화형 시스템이라고 한다. CPU집중작업(CPU bound job)은 프로그램 실행 도중 입출력이 불가능하다. (일괄 처리 시스템의 특징이다) 대화형 시스템은 입출력 집중 작업으로 I/O bound job이라고 한다.

4. 시분할 시스템(1960년대 후반)

다중 프로그래밍 기술이 개발되었다. 하나의 CPU로 여러 작업을 동시에 실행한다. 따라서 효율성이 올라간다. 다중 프로그래밍 기술은 CPU 사용시간을 잘게 쪼개어 여러 작업에 나누어주어 동시에 진행되는 것처럼 보이게 한다. 오늘날 대부분의 컴퓨터도 시분할 시스템을 사용한다. 그렇지만 시분할 시스템을 쓰지 못하는 경우도 있다. 이런 것들은 예외적으로 일정시간 안에 끝나지 않으면 심각한 문제가 생기는 것들이다. 원자력이나 미사일같은것들을 조절하는 프로그램은 실시간 시스템 방식을 사용한다.

*유닉스(C언어로 개발됨) : 멀티 프로그래밍과 다중 사용자를 지원하는 운영체제로 개발되었다.

5. 분산 시스템(1970년대 후반)

 이즈음 스티브 잡스가 애플II를 만들면서 개인용 컴퓨터 시대를 열었다. 개인용 컴퓨터의 운영체제는 대부분 애플의 매킨토시나 마이크로소프트의 MS-DOS를 사용하였다. 

 이때 인터넷도 등장한다. 서로 호환되지 않는 LAN을 하나로 묶어 아르파넷ARPnet이 생성되고 컴퓨터 간의 네트워킹을 위한 TCP/IP 프로토콜도 정의된다. 아르파넷은 냉전시기에 개발되었는데 이후 대학교에서 학문 연구를 이유로 서로 컴퓨터를 연결하려는 시도가 늘어나자 아르파넷을 민간에 풀어버린다. 이것이 이후에 인터넷으로 진화했다.

 개인용 컴퓨터가 보급되면서 값이 싸고 크기가 작은 컴퓨터들을 하나로 묶어 시스템을 생성하였다. 이것을 분산 시스템 distributed system 이라고 한다.

6. 클라이언트/서버 시스템(1990~현재)

분산 시스템의 문제는 모든 컴퓨터가 동일한 지위를 갖는 것이였다. 클라이언트/서버 시스템은 웹 시스템 보급 후 알려졌는데 서버에 데이터를 요청하면 클라이언트가 정보를 받는 역할을 하는 것이다. 클라이언트/서버는 상대적인 개념으로 누구든지 서버와 클라이언트가 될 수있다. 

데몬

클라이언트/서버 시스템에서 서버는 멈추지 않고 계속 작동해야 한다. 이렇게 멈추지 않고 계속 작동하는 프로그램을 데몬demon이라고 한다. 웹 데몬(웹 서버) 역할을 하는 프로그램은 아파티 톰캣, IIS 등이 있다.

7. P2P 시스템

P2P 시스템은 클라이언트/서버 시스템에서 불편한 점을 해결하기 위해 시작되었다. 클라이언트/서버 시스템에서 너무 많은 클라이언트가 서버에 요청을 하면 서버가 과부화 수도 있다. 보통 게임을 많이 하는 사람들은 경험해본적이 있을것이다. (서버가 터졌다니, 서버가 과부화되었다니,,그런 말들)

P2P 시스템(peer to peer)은 서버를 거치지 않고 사용자와 사용자를 연결해 준다. 각각 서버와 클라이언트가 되는 것이다. 메인 서버의 부하가 적다는 장점이 있다. P2P시스템의 예는 메신저 프로그램이나 MP3, 파일 공유 같은 P2P 시스템이 있다. 또한 비트코인, 블록체인 같은 것은 거래 장부를 분산시켜서 안정성을 확보한다.

(P2P 시스템도 서버가 있을 수는 있다. 예를 들면, P2P 메신저 프로그램같은 것은 사용자 인증, 출석과 같은 기능은 서버에서 한다.)

파일 공유

 만약 기존에 MP3 P2P에서 전송하는 쪽에서 프로그램을 종료해버리면 어떻게 될까? 전송 중단이 되어 P2P 시스템에 치명적인 오류가 발생한다. 그래서 해결한 방안이 파일 공유이다. 파일 공유는 같은 파일을 가진 여러 사람으로부터 데이터를 나누어 받아서 속도를 향상할 수 있다.

8. 기타 컴퓨터 환경

1) 그리드 컴퓨팅 : 컴퓨팅 자원을 구매하여 사용하는 컴퓨팅 환경이다. 서로 다른 기종의 컴퓨터들을 하나로 묶어 가상의 대용량 고성능 컴퓨터를 구성하여 고도의 연산 작업 혹은 대용량 처리를 수행하는 것을 일컫는다. 보통 연구용이나 상업용으로 이용한다. 일반인은 웹 하드 서비스에서 경험을 할 수 있다.

ex) 웹 하드 서비스 : 웹 하드에서 파일을 내려받을려고 하면 서버에서 주는 것이 아니라 파일을 내려받은 컴퓨터로부터 몰래 데이터를 빼와서 전달한다. 이것을 '그리드 딜리버리' 라고 한다.

(그래서 파일노리, 큐다운 같은 웹하드를 다운받으면 컴퓨터 속도가 느려지는 것이다. 무료로 웹하드 이용권을 나누어주는 것도 서비스 가입자 몰래 그리드 딜리버리를 깔아서 서버의 부하를 줄이기 위함이다.)

SaaS

 그리드 컴퓨팅의 소프트웨어적 버전. 소프트웨어를 영구 구매할 필요 없어 사용자의 초기 비용이 줄어든다. 단, 서비스 성능이 인터넷 연결 속도에 좌우되므로 사용자가 빠른 네트워크 하드웨어에 투자해야 된다.

(ex: Google Docs, Microsoft Office 365, IDE)

2) 클라우드 컴퓨팅 : 언제 어디서나 응용 프로그램과 데이터를 자유롭게 사용하는 환경이다. 그리드 컴퓨팅+SaaS라고 생각하면 된다.

클라우드 컴퓨팅이라는 이름은 시스템(하드웨어 포함)이 구름에 가려진 것처럼 사용자에게 보이지 않아서 붙여진 것이다. 

ex) 회사 홈페이지를 제작하고 싶으면 클라우드 서버에 회사 홈페이지를 올려놓고 사용한 만큼 비용을 지불하는 식이다. 그렇지 않으면 직접 서버 관리와 많은 초기 자원이 필요한데 클라우드 컴퓨팅을 통해 절감할 수 있다. 

ex) 또 휴대전화를 바꿀때 클라우드 백업을 통해서 직접 옮기지 않고도 손쉽게 전화번호부, 사진 등을 전달할 수 있게 된다. 

3) 사물 인터넷 IOT : 사물에 인터넷이 연결된 것.