Winwoo's Story

Process Concept

• Process : OS에서 프로그램을 수행시키는 기본 주체
  

- Runtime System의 수행 주체

- CPU나 다른 자원을 할당 받는 주체

- Process는 OS에서 가장 중요한 단위

• Decomposition
  

- 복잡한 문제를 단순한 여러 개의 문제로 나누어 처리하는 방법론

• Program과 Process의 차이

- Program : 저장매체에 저장된 수동적인 Code Sequence ( 수동적 )

- Process : Program을 실행할 때 일어나는 일 ( 능동적 )

(실행 시 메모리 할당 및 CPU할당 등 다양한 일을 포함)

• Program State
  - 무언가 Program이 실행될 때 모든 Data를 말한다.
      1. Memory ( Memory Context 
          - Code : 기계어
          - Data : Program 전역 변수
          - Stack : Program 지역 변수
          - Heap : Program 동적 메모리 공간
      2. CPU ( H/W Context )
          - Register value
      3. Per - Process Kernel Info ( System Context )
  
  

• Execution Stream
  - Process가 지금까지 수행한 모든 명령어들의 순서
  
  

• Process 정리
  - 수행중인 Program -> State 필요 -> State 위에 Thread of Control
  또는 excution Stream 존재
  
  

• Multi Programming
  - 여러개의 Active한 Process가 Memory에 올라가 있는 경우
  
  

• Swapping ( Main Memory의 공간이 작을 때 사용 )
  - 메모리 부족문제를 해결하기 위해 CPU를 사용하지 않는 일부 Process의 데이터를 Memory에서 다른 저장 장치로 옮기고 CPU를 사용할 Process의 데이터를 Memory에 Load 한다.
  
  

• Process Control Block (PCB)
  - OS가 가지고 있는 Process의 정보
  
  

• Process Table
  - 여러개의 PCB를 Array로 관리
  
  

• State Transition
  - Process Life Cycle : Process가 생성되었을 때 부터 종료될 때 까지 발생하는 일련의 상태 변화
  
  

- Ready State : Active한 Process가 CPU할당을 받지 못한 상태 

(Queue를 통해 관리한다)
*Ready Queue : Ready 상태의 Process들을 관리하기 위한 Queue형태의 자료구조 -> 일반적으로 PCB들을 Linked List로 구현

- Waiting State : 여러개의 Process가 Waiting 상태일 수 있다. 단, Process마다 Waiting 이유가 다를 수 있기 때문에 OS는 Waiting 이유에 따라 별도의 Queue를 통해  Process들을 관리 한다.

*본 자료는 서울대학교 홍성수 교수님의 '운영체제' 수업을 바탕으로 개인적으로 정리하여 올립니다. 관련 이미지 자료는 홍성수 교수님 수업 PPT자료가 출처임을 알립니다. 문제 시 말씀해주시면 삭제 조치 하겠습니다. 감사합니다.

Computer HardWare

운영체제 ---(가장 먼저 Interection)---> HardWare 

1. Computer System

1.1 System Bus

1.1.1 System Bus란 : 

CPU, Memory, I/O -> 상호간 Data 전송 역할 

1.1.2 System Bus의 종류 : 

Data Bus, Address Bus

1.1.3 System Bus의 행동 : 

Read & Write

- CPU <- Memory : Read

- CPU -> Memory : Write

1.2 Bus Master / Bus Arbiter / Bus Slave

1.2.1 Bus Master : 

-Bus Transaction을 시작하는 요소 

-System에는 여러개의 Bus Master가 존재함

* 대표적인 Bus Master : CPU, I/O Controller, DMA Controller 등

1.2.2 Bus Arbiter : 

여러Bus Master중 특정 Bus Master에게  Bus를 제공해주는 조정자

1.2.3 Bus Slave : 

데이터를 담고 있는 장치(Memory)

(*Transaction : CPU의 작업단위)

1.3 I/O Controller

1.3.1 Interrupt-Driven I/O :

I/O 동작이 완료되면 I/O Controller가 CPU에게 '비동기'적으로 완료되었음을 알려주는 방식

1.3.2 Polling I/O : 

I/O 동작이 완료 될 때까지 CPU가 반복해서 I/O Controller의 Resgister 상태를 확인하는 방식

1.4 DMA Operation (Direct Memory Access)

1.4.1 DMA 이란 :

CPU의 개입 없이 I/O Controller가 메모리에 직접 접근하여 Data를 읽거나 쓸 수 있도록 하는 기능

1.4.2 CPU가 DMA에게 전달하는 요소 :

CPU -----------> DMA Controller

- 전송 될 Block의 시작

- Block의 Size

- Operation Command (Read & Write)

(*DMA는 Block 단위로 전달 됨)

1.4.3 DMA 사용 이유 :

Block Data를 옮길 때 CPU Intervention을 최소화하기 위해 사용

1.4.4 DMA가 Block Data를 전송하는 방식

1. Cycle Stealing : 

CPU 성능에 영향이 없지만 DMA시간이 증가함

->CPU가 BUS를 사용하고 있지 않을 때만 DMA Controller가 Bus를 사용

2. Block Transfer : 

CPU 성능에 영향이 있지만 DMA시간이 감소

->CPU와 DMA Controller가 대등하게 경쟁하여 Bus를 사용

2. Interrupt Mechanism

2.1 Interrupt Mechanism이란

1. 비동기적 Mechanism

2. Hardware Interrupt

- CPU 외부에서 CPU가 관심을 가져야 될 상황에 대에서 CPU에게 전달 (비동기)

3. Software Interrupt

- 현재 수행하는 Program의 문제를 알리기 위해 사용

ex) Exception funtion

-코드분석을 통해 문제를 알 수 있음

(동기적)

2.2 Interrupt의 구현

1. Interrupt Source 

- I/O Controller, DMA Controller 등

2. Interrupt의 처리과정

- 현재 Instruction을 완료하고 마이크로 프로세서의 프로그램 카운터(PC)값을 안전한 곳에 저장

- 현재 수행중인 프로그램 중단

- Interrupt Request Number(IRN)를 통해 Interrupt Source 확인

- Interrupt Vector Table을 검색해서 Interrupt Service Routine(ISR)의 주소를 확인하고 수행

3. PIC(Programmable Interrupt Controller)

- CPU의 Interrupt PIN의 유동적 확장을 위해 사용

- PIC 하나당 16개 Interrupt 처리 가능

3. Hardware Protection Mechanism

3.1 Hardware Protection Mechanism 이란

- Multi Programming을 할 때 Memory에 Active한 여러 Job들이 다른 영역에 접근하지 못하게 하는 기법

*Privileged Instruction

 -> Operation System만 수행할 수 있는 Instruction

3.2 Duel Mode Operation

- Kernel Mode : Privileged Instruction들을 수행 시킬 수 있는 Mode

- User Mode : Privileged Instruction들을 수행 시킬 수 없는 Mode

- Mode변환은 Kernel Mode만 가능

- User Mode에서 Kernel Mode로 변환하기 위해선 Interrupt를 이용

*본 자료는 서울대학교 홍성수 교수님의 '운영체제' 수업을 바탕으로 개인적으로 정리하여 올립니다. 관련 이미지 자료는 홍성수 교수님 수업 PPT자료가 출처임을 알립니다. 문제 시 말씀해주시면 삭제 조치 하겠습니다. 감사합니다.

prototype을 이용한 Java의 super개념 구현

• super의 개념
  - 상속 받은 부모 그 자체
  
  

• javascript에서 구현 방법

병합 정렬

1. 병합 정렬이란?

- 분할 정복 ( DAC - Divide And Conquer ) 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법

* 분할정복이란? 복잡한 문제를 분할 하여 정복 후 결합하는 방법

∙ 1단계 분할(Divide) 해결이 용이한 단계까지 문제를 분할해 나간다.

∙ 2단계 정복(Conquer) 해결이 용이한 수준까지 분할된 문제를 해결한다.

∙ 3단계 결합(Combine) 분할해서 해결한 결과를 결합하여 마무리한다

2. 분할 방법

3. 재귀적 구현 (최소단위 까지 분할)

간단한 정렬 알고리즘

1. 버블 정렬

- 버블 정렬의 이해

- 소스 코드

- 성능 평가

* 비교 횟수 : 두 데이터간의 비교연산 횟수

* 이동 횟수 : 위치의 변경을 위한 데이터의 이동 횟수

-> 실제로 시간 복잡도에 대한 빅-오(O)를 결정하는 기준은 '비교 횟수'이다. 하지만, 이동 횟수에 관한 성능까지 체크 한다면 동일 한 빅-오 연산에 대한 세밀한 성능평가가 가능하다.

- 비교 횟수 : O(n^2)

- 이동 횟수

-> 정렬이 되어 있는 경우 : 한번도 이동이 발생 하지 않음

-> 역순으로 정렬 되어 있는 경우 : O(n^2) 

(실제론 비교 횟수의 3배 소요)

2. 선택 정렬

- 선택 정렬의 이해

- 소스 코드

void SelSort(int arr[], int n) { int i, j; int maxIdx; int temp; for(i=0; i<n-1; i++) { maxIdx = i; // 정렬 순서상 가장 앞서는 데이터의 index for(j=i+1; j<n; j++) // 최소값 탐색 { if(arr[j] < arr[maxIdx]) maxIdx = j; } /* 교환 */ temp = arr[i]; arr[i] = arr[maxIdx]; arr[maxIdx] = temp; } } int main(void) { int arr[4] = {3, 4, 2, 1}; int i; SelSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

- 성능 평가

- 비교 횟수 : O(n^2)

- 이동 횟수 : O(n) Worst Case와 Best Case관계 없이 동일

3. 삽입 정렬

- 삽입 정렬의 이해

- 소스 코드

void InserSort(int arr[], int n) { int i, j; int insData; for(i=1; i<n; i++) { insData = arr[i]; // 정렬 대상을 insData에 저장 for(j=i-1; j>=0 ; j--) { if(arr[j] > insData) arr[j+1] = arr[j]; // 비교 대상 한 칸 뒤로 밀기 else break; // 삽입 위치 찾았으니 탈출! } arr[j+1] = insData; // 찾은 위치에 정렬 대상 삽입! } } int main(void) { int arr[5] = {5, 3, 2, 4, 1}; int i; InserSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<5; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

- 성능 평가

- 비교 횟수 : O(n^2)

- 이동 횟수 : 

Worst Case -> O(n^2)

Best Case -> 한번도 발생 안함