프로세스

실행중인 프로그램을 프로세스라 한다

 

프로세스의 문맥(context)

특정 시점에서 프로세스가 어디까지 실행됐는지를 파악하기 위해

- CPU 수행 상태를 나타내는 하드웨어 문맥

   Program counter

   각종 register

- 프로세스의 주소 공간

   code, data, stack

- 프로세스 관련 커널 자료 구조

   PCB(Process Control Block)

   Kernel stack

 

 

프로세스의 상태

Running : CPU를 잡고 인스트럭션(instruction)을 수행중인 상태

Ready : CPU를 기다리는 상태(메모리 등 다른 조건을 모두 만족하는 상태)

Blocked (wait, sleep) :

 - CPU를 주어도 당장 instruction을 수행할 수 없는 상태

 - process 자신이 요청한 event(ex: I/O)가 즉시 만족되지 않아 이를 기다리는 상태

  ex) 디스크에서 file을 읽어와야 하는 경우

Suspended (stopped) :

 - 외부적인 이유로 프로세스의 수행이 정지된 상태

 - 프로세스는 통째로 디스크에 swap out 된다

 ex) 사용자가 프로그램을 일시 정지 시킨 경우,

      메모리에 너무 많은 프로세스가 올라와 있을 때(Medium-term Scheduler에 의해)

New : 프로세스가 생성 중인 상태 (보통 프로세스의 상태로 포함되지 않음)

Terminated : 수행이 끝난 상태 (보통 프로세스의 상태로 포함되지 않음)

 

※ Blocked 와 Suspended 의 차이

Running, Ready, Blocked 모두 CPU 관점에서의 상태 분류일 뿐 실제로 프로세스의 작업이 수행이 되고 있는 상태 (CPU에서 프로세스 수행중(Running), I/O에서 프로세스 수행중(Blocked)), 반면 Suspended 는 프로세스 수행 자체가 외부에 의해 정지된 상태

Blocked : Blocked 자신이 요청한 event가 만족되면 Ready

Suspended : 외부에서 resume 해주어야 Active

 

 

프로세스 상태의 흐름

1. CPU에서 하나의 프로세스를 처리 중 (Running)

2. 타이머 인터럽트가 들어오며 프로세스가 Ready Queue 맨 뒤로 가서 줄을 서게 됨 (Ready)

   (실제론 Queue 순서가 아닌, 우선순위에 의해 실행함)

3. 다음 프로세스를 처리

4. I/O 입력이 요구되어 프로세스의 상태가 blocked 로 바뀌고 키보드 I/O Queue 로 이동하여 줄을 서게 됨 (Blocked)

5. 입력이 완료되면 device controller 가 인터럽트를 걸어 CPU 에게 알림

 

 

PCB(Process Control Block)

운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보

1) OS가 관리상 사용하는 정보

Process state, Process ID, Priority, Scheduling information

2) CPU 수행 관련 하드웨어 값

Program Counter, registers

3) 메모리 관련

Code, Data, Stack 위치정보

4) 파일 관련

Open File Descriptors

 

 

문맥 교환(Context Switch)

CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정

1) CPU를 내어주는 프로세스 상태를 그 프로세스의 PCB에 저장

2) CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴

 

a) 프로세스 A --> 인터럽트 or 시스템콜 --> 커널 --> 프로세스 A : 문맥교환 X

b) 프로세스 A --> 인터럽트 or 시스템콜 --> 커널 --> 프로세스 B : 문맥교환 O

a의 경우에도 CPU 수행 정보 등 context 일부를 PCB에 저장해야 하지만 문맥교환을 하는 b의 경우가 오버헤드가 훨씬 더 크다. (b의 경우 cache memory flush 가 수행됨)

 

 

프로세스 큐의 종류

1) Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 (Ready Queue + Device Queues)

2) Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스 집합 (Device Queue와 베타관계)

3) Device Queues : I/O device 의 처리를 기다리는 프로세스 집합 (Ready Queue와 베타적 관계)

 


스케쥴러 (Scheduler)

1) Long-term Scheduler (장기 스케쥴러/Job scheduler)

- 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정(new -> ready 로 갈 프로세스를 결정)

- 프로세스에 memory를 주는 문제

- 메모리에 올라갈 프로세스 수를 제어 (메모리에 프로그램이 너무 적거나 많으면 효율/성능이 좋지 않음)

- Time sharing system 에서는 보통 장기 스케쥴러가 없다 (무조건 ready 상태로.. (무조건 메모리에 올라감))

 

2) Short-term Scheduler (단기 스케쥴러/CPU scheduler)

- 어떤 프로세스를 다음번에 running 시킬지 결정

- 프로세스에 CPU를 주는 문제

- millisecond 단위로 매우 빨라야 함

 

3) Medium-term Scheduler (중기스케쥴러/Swapper)

- 메모리 여유 공간 마련을 위해 프로세스를 통째로 디스크로 쫓아냄

- 프로세스에게서 memory를 뺏는 문제

 

 

※ 이화여대 반효경 교수님의 운영체제 강의내용 정리

 

반응형
저작자표시 비영리

'Computer Science > OS' 카테고리의 다른 글

[OS] 운영체제 6. CPU Scheduling : CPU 성능척도, 스케쥴링 방법(FCFS, SJF, Priority Scheduling, Round Robin)  (0) 2020.02.04
[OS] 운영체제 5. Process Management : 프로세스 생성/종료  (0) 2020.02.01
[OS] 운영체제 4. Thread : 스레드 정의, 효과 및 장점  (0) 2020.01.27
[OS] 운영체제 2. System Structure & Program Execution : 시스템구조, 입출력  (0) 2020.01.24
[OS] 운영체제 1. OS  (0) 2020.01.19

 

1. Mode bit

사용자 프로그램의 잘못된 수행으로 다른 프로그램 및 운영체제에 피해가 가지 않도록 하기 위한 보호 장치

1 사용자모드 : 사용자 프로그램 수행

0 모니터모드 : OS 코드 수행

 

- 보안을 해칠 수 있는 중요한 명령어는 모니터 모드(OS)에서만 수행 가능 == 특권명령

- Interrupt 나 Exception 발생시 하드웨어가 mode bit 을 0으로 바꾼다

- 사용자 프로그램에게 CPU를 넘기기 전에 mode bit 을 1로 바꾼다

 

2. Timer

- 정해진 시간이 흐른 뒤 운영체제에게 제어권이 넘어가도록 interrupt 를 발생시킨다

- 타이머는 매 클럭 틱 마다 1씩 감소

- 타이머 값이 0이 되면 타이머 interrupt 발생 

- CPU를 특정 프로그램이 독점하는 것으로부터 보호

- 타이머는 time sharing을 구현하기 위해 널리 이용된다

- 타이머는 현재 시간을 계산하기 위해서도 사용된다

 

3. Device Controller

3-1. I/O device Controller

- I/O 장치유형을 관리하는 일종의 작은 CPU

- 제어 정보를 위해 control register, status register 를 가진다

- local buffer 를 가진다

- I/O는 실제 device와 local buffer 사이에서 일어난다

- Device controller는 I/O가 끝났을 경우 Interrupt 로 CPU에 그 사실을 알린다

 

※

Device Driver (장치구동기) : OS 코드 중 각 장치별 처리루틴 (software)

Device Controller (장치제어기) : 각 장치를 통제하는 일종의 작은 CPU (hardware)

 

※ 인터럽트(Interrupt)

인터럽트 당한 시점의 레지스터와 program counter 를 save 한 후 CPU의 제어를 인터럽트 처리 루틴에 넘긴다

- Interrupt (하드웨어 인터럽트) : 하드웨어가 발생시킨 인터럽트

- Trap (소프트웨어 인터럽트) :

  Exception : 프로그램 오류

  System Call : 프로그램이 커널 함수 호출

 

인터럽트 관련 용어

- 인터럽트 벡터

  해당 인터럽트의 처리 루틴 주소를 가지고 있음

  : 함수의 주소 값을 가지고 있는 일종의 테이블

- 인터럽트 처리 루틴 (=Interrupt Service Routine, 인터럽트 핸들러)

  해당 인터럽트를 처리하는 커널 함수

  : 인터럽트마다 처리하는 작업내용이 다르므로 각각의 인터럽트마다 어떤 작업을 수행해야 하는지가 작성되어 있는 코드

 

※ 입출력의 수행

모든 입출력 명령은 특권 명령

사용자 프로그램이 I/O 하는 방법 : 시스템콜(System Call)

1) 인터럽트 라인 세팅

2) CPU는 실행중이던 인스트럭션을 실행한 후 interrupt 확인

3) mode bit 0 으로 바뀜

4) 운영체제에게 CPU 제어권이 넘어감

5) device controller 에게 I/O 데이터 요청

6) CPU는 I/O 를 기다리지 않고, 다른 인스트럭션 실행

7) I/O 입력

8) device controller가 인터럽트 라인 세팅

9) CPU는 실행중이던 인스트럭션을 실행한 후 interrupt 확인

10) mode bit 0으로 바뀜

11) 운영체제에게 CPU 제어권이 넘어감

12) device controller로부터 buffer에 저장된 데이터를 운영체제가 받아옴

13) I/O를 요청했던 인스트럭션의 메모리영역에 buffer 데이터 저장

 

* CPU는 레지스터 중 program counter 가 가르키는 메모리 주소(인스트럭션)을 실행

* program counter 가 가리키는 메모리 주소를 실행하기 전에 interrupt line 을 확인

* mode bit 이 0일 땐 OS 가 CPU 를 가지고 있으므로 모든 인스트럭션 실행이 가능

* mode bit 이 1일 땐 사용자 프로그램이 CPU 를 가지고 있으므로 실행 불가한 인스트럭션이 존재(인터럽트를 걸어 운영체제에게 서비스 요청)

인스트럭션 1개는 4byte

 

※ 입출력 방식

동기식 입출력 : I/O 요청 후 입출력 작업이 완료된 후, 사용자 프로그램에 제어가 넘어감

비동기식 입출력 : I/O 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감

* I/O 완료여부는 interrupt로 알린다.

 

※ DMA (Direct Memory Access)

- 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용

- CPU의 중재 없이 device controller 가 device의 buffer storage의 내용을 메모리에 block 단위로 직접 전송

- 바이트 단위가 아니라 block 단위로 인터럽트를 발생시킴

* CPU에 인터럽트를 매번 걸지 않아 효율이 증가

 

저장장치 계층구조

* Volatility 휘발성

 

프로그램 실행시 메모리 로드

File System --> virtual memory --(Address transaction 논리메모리 주소를 물리 메모리 주소로 변환)--> physical memory

1) 프로그램 실행시 실행된 각각의 프로그램의 Address space 를 virtual memory 에 생성

2) physical memory 에 virtual memory 의 필요한 일부만 올림

3) 불필요한 경우 Swap area(메모리의 한계로 메모리 연장을 위한 공간으로 사용) 에 저장

 

 

커널 주소 공간의 내용

 

※ 이화여대 반효경 교수님의 운영체제 강의내용 정리 (kocw.net)

반응형
저작자표시 비영리

'Computer Science > OS' 카테고리의 다른 글

[OS] 운영체제 6. CPU Scheduling : CPU 성능척도, 스케쥴링 방법(FCFS, SJF, Priority Scheduling, Round Robin)  (0) 2020.02.04
[OS] 운영체제 5. Process Management : 프로세스 생성/종료  (0) 2020.02.01
[OS] 운영체제 4. Thread : 스레드 정의, 효과 및 장점  (0) 2020.01.27
[OS] 운영체제 3. Process : 프로세스의 상태흐름(Ready,Running,Blocked, Suspended), PCB, 문맥교환(Context switch)  (0) 2020.01.25
[OS] 운영체제 1. OS  (0) 2020.01.19

1. 운영체제 (Operating System) 란?

-컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층

-좁은 의미의 운영체제 : 커널(Kernel), 운영체제의 핵심 부분으로 메모리에 상주하는 부분

-넓은 의미의 운영체제 : 커널 뿐만 아니라 각종 주변 시스템 유틸리티 포함한 개념

 

 

2. 운영체제의 목적

2-1) 효율적인 컴퓨터 시스템의 자원 관리

- 프로세서, 기억장치, IO 장치 등의 효율적 관리

 사용자간의 형평성 있는 자원 분배

 주어진 자원으로 최대한의 성능을 내도록

- 사용자 및 운영체제 자신의 보호

 프로세스, 파일, 메시지 등을 관리

2-2) 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공

- 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행

 

 

3. 운영체제의 분류

3-1) 동시 작업 가능 여부에 따른 분류

- 단일 작업(single tasking) : 한 번에 하나의 작업만 처리

ex) MS-DOS

- 다중 작업(multi tasking) : 동시에 두개 이상의 작업 처리

ex) UNIX, MS windows

 

3-2) 사용자의 수에 따른 분류

- 단일사용자(single user)

ex) MS-DOS, MS Windows

- 다중사용자(multi user) : 동시에 여러명의 사용자가 하나의 컴퓨터에 접속하여 사용, 더 세밀한 자원관리 요구됨

ex) UNIX

 

3-3) 처리 방식에 따른 분류

- 일괄처리(Batch Processing) 

작업 요청의 일정량을 모아서 한 번에 처리 (ex: OMR 카드)

- 시분할(Time Sharing)

여러 작업을 수행할 때 컴퓨터 처리 능력을 일정 시간 단위로 분할하여 사용 (대부분의 OS)

CPU의 시간을 분할하여 나누어 쓴다는 의미

- 실시간(Real Time)

정해진 시간 안에 작업이 반드시 종료되는게 보장되어야 하는 시스템을 위한 OS (반도체/미사일/원자로 등)

※ 실시간 시스템의 개념 확장

Hard realtime system(경성 실시간 시스템) : 시간이 엄밀하게 지켜져야 하는 시스템(ex:미사일)

Soft realtime system(연성 실시간 시스템) : 시간이 지켜져야 하지만 엄격하게 지켜질 필요는 없는 시스템(ex: 영사기)

 

4. 운영체제의 예

- UNIX : 코드 대부분을 C언어로 작성, 높은 이식성, 소스 코드 공개, 프로그램 개발에 용이 

ex) Linux, Solaris

- DOS(Disk Operating System) : MS사가 1981년 개인 PC를 위해 개발, RAM 이 640KB로 제한

- MS Windows : MS 사의 GUI 기반 운영체제

 

 

※ 이화여대 반효경 교수님의 운영체제 강의내용 정리 (kocw.net)

반응형
저작자표시 비영리

'Computer Science > OS' 카테고리의 다른 글

[OS] 운영체제 6. CPU Scheduling : CPU 성능척도, 스케쥴링 방법(FCFS, SJF, Priority Scheduling, Round Robin)  (0) 2020.02.04
[OS] 운영체제 5. Process Management : 프로세스 생성/종료  (0) 2020.02.01
[OS] 운영체제 4. Thread : 스레드 정의, 효과 및 장점  (0) 2020.01.27
[OS] 운영체제 3. Process : 프로세스의 상태흐름(Ready,Running,Blocked, Suspended), PCB, 문맥교환(Context switch)  (0) 2020.01.25
[OS] 운영체제 2. System Structure & Program Execution : 시스템구조, 입출력  (0) 2020.01.24

Stack 두 개(First In First Out)로 Queue(Last In First Out) 구현하기

 

스택 두 개를 다음과 같은 용도로 분리하여 사용.

inStack : 데이터를 저장

outStack : 데이터를 꺼낼 때 임시 버퍼로 사용

 

[Queue.class]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package algo_datastructure.stack.queuebystack;
 
import java.util.Stack;
 
class Queue <T> {
    
    private Stack<T> inStack;
    private Stack<T> outStack;
    
    public Queue(){
        inStack = new Stack<T>();
    }
    
    public boolean add(T input) {
        return inStack.add(input);
    }
    
    public T poll() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.pop();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public T peek() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.peek();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public boolean isEmpty() {
        return inStack.isEmpty();
    }
    
}
 
 cs

[poll() 메소드 설명]

1. 데이터 입력

add(1);

add(2);

add(3);

inStack
3
2
1

2. poll(); 호출

if(!inStack.isEmpty()) {
   outStack = new Stack();
}

inStack outStack
3  
2  
1  

while(!inStack.isEmpty()) {
   outStack.add(inStack.pop());
}

inStack outStack
  1
  2
  3

T topItem = outStack.pop();   //1

inStack outStack
   
  2
  3

while(!outStack.isEmpty()) {
   inStack.add(outStack.pop());
}

inStack outStack
   
3  
2  

 

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package algo_datastructure.stack.queuebystack;
 
public class Main {
 
    public static void main(String[] args) {
        
        Queue<Integer> q = new Queue<>();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("peek : "+q.peek());
        System.out.println("poll : "+q.poll());
        
        q.add(4);
        System.out.println("peek : "+q.peek());
        while(!q.isEmpty()) {
            System.out.println("poll : "+q.poll());
        }
        
    }
    
}
 
 cs

[실행결과]

peek : 1
poll : 1
peek : 2
poll : 2
poll : 3
poll : 4

기술면접에서 단골 문제라고 하길래, 이렇게 구현하면 되지 않을까 하고 구현해보았습니다..

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

Queue

FIFO(First In First Out : 선입선출) 형태를 갖는 자료구조.

일상생활에서 Queue와 가장 밀접한 예로 줄을 서는 행위를 들 수 있다. 

보통 줄을 설 때 줄을 가장 먼저 선 사람이 가장 먼저 처리되므로 Queue와 같다.(Queue 라는 단어 자체가 줄을 서다 라는 뜻을 갖는 동사, 대기줄이라는 뜻을 갖는 명사 이다)

 

[java.util.Queue 의 기본적인 사용예]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package algo_datastructure.queue.queuebyarray;
 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        
        System.out.println("Queue---------");
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(2);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (default : ascending)---------");
        Queue<Integer> q2 = new PriorityQueue<Integer>();
        q2.add(1);
        q2.add(3);
        q2.add(2);
        System.out.println(q2.peek());
        while(!q2.isEmpty()) {
            System.out.print(q2.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (Descending)---------");
        Queue<Integer> q3 = new PriorityQueue<Integer>((o1, o2)->o2-o1);
        q3.add(1);
        q3.add(3);
        q3.add(2);
        System.out.println(q3.peek());
        while(!q3.isEmpty()) {
            System.out.print(q3.poll() + " ");
        }
    }
}
 
 cs

[실행결과]

Queue---------
1
1 2
PriorityQueue (default : ascending)---------
1
1 2 3
PriorityQueue (Descending)---------
3
3 2 1

Queue 는 입력된 순서대로 저장 및 출력되는(LinkedList 를 구현체로 사용) Queue 와

입력된 데이터들을 특정 기준에 의해 정렬된 상태로 저장 및 출력하는 PriorityQueue 가 있다.

위와 같이 PriorityQueue는 Comparator 인터페이스를 파라미터로 넘겨 정렬순서를 원하는대로 선택할 수 있다. (위 예제에선 람다로 처리)

Comparator 인터페이스를 넘겨주지 않을 경우, 오름차순 정렬(default)로 처리된다.

 

두가지 queue 모두 공통적으로 아래와 같은 메소드를 갖는다.

add() : queue 에 값을 넣는다. (값 넣기 실패시 exception 을 뱉는다)

offer() : add()와 같이 queue에 값을 넣는다. (값 넣기 실패시 false 를 리턴한다)

peek() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

poll() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

[Array로 구현한 Queue]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package algo_datastructure.queue.queuebyarray;
 
public class Queue {
    
    private int[] array = new int[100];
int lastIdx = 0;
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int peek() {
        return array[0];
    }
    
    public int poll() {
        int rs = array[0];
        
        for(int i=1; i<=lastIdx; i++) {
            array[i-1] = array[i];
        }
        lastIdx--;
        
        return rs;
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
 cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package algo_datastructure.queue.queuebyarray;
 
public class Main {
    public static void main(String[] args) {
        
        Queue q = new Queue();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}
 
 cs

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

Stack

LIFO (Last In First Out : 후입선출) 형태를 갖는 자료구조.

임시로 자료를 저장하고 꺼내서 사용하는 임시 버퍼와 같다.

java 메모리구조에서 new 연산자로 생성된 인스턴스 등이 Stack 으로 관리된다.

 

일상생활에서 Stack과 가장 밀접한 예로 장독대를 들 수 있다.

김치를 넣고 꺼낼 때 가장 나중에 넣은 김치를 가장 먼저 꺼내야 하는 구조이므로 Stack과 같다.

 

[java.util.Stack 의 기본적인 사용예]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package algo_datastructure.stack;
 
import java.util.Stack;
 
public class BasicUsageOfStack {
    public static void main(String[] args) {
 
        Stack<Integer> s = new Stack<>();
        s.add(1);
        s.add(2);
        s.add(3);
 
        System.out.println(s.peek());
 
        while(!s.isEmpty()) {
            System.out.println(s.pop());;
        }
        
    }
}
 
 cs

 

add로 stack에 값을 넣는다. (push와 같음)

peek으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

pop으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

 

[Array로 구현한 Stack]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package algo_datastructure.stack.stackbyarray;
 
public class Stack {
    private int[] array = new int[100];
    private int lastIdx = 0;
    
    public Stack () {
    }
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int pop() {
        lastIdx--;
        int top = array[lastIdx];
        array[lastIdx] = 0;
        
        return top;
    }
    
    public int peek() {
        return array[lastIdx-1];
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
 cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package algo_datastructure.stack.stackbyarray;
 
public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println(s.peek());
        while(!s.isEmpty()) {
            System.out.println(s.pop());
        }
    }
}
 
 cs

 

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

[Set]

중복을 허용하지 않는 자료구조로, 모든 데이터가 Unique 하다.

Set Interface 를 구현하는 HashSet, LinkedHashSet, TreeSet 은 위와 같은 성질을 따른다.

 

[HashSet]

내부적으로 HashMap 을 사용

순서 보장 X

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[LinkedHashSet]

내부적으로 LinkedHashMap을 사용

순서 보장 O (입력한 순서)

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[TreeSet]

내부적으로 TreeMap을 사용

인자값으로 받은 Comparator 를 기준으로 정렬, 인자값이 없는 경우 오름차순 정렬

null 입력 불가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Set<Integer> set = new HashSet<>();
set.add(null);
set.add(null); //중복허용X
set.add(3);
set.add(2);
set.add(1);
set.add(1);    //중복허용X
 
System.out.print("HashSet: ");
 
Iterator<Integer> si = set.iterator();
while(si.hasNext()) {
    System.out.print(si.next()+" ");
}
System.out.println();
 
 
Set<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(3);
linkedHashSet.add(2);
linkedHashSet.add(1);
linkedHashSet.add(1); //중복허용 X
 
System.out.print("linkedHashSet: ");
for(int i : linkedHashSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(2);
treeSet.add(1);
treeSet.add(1); //중복허용X
 
System.out.print("TreeSet: ");
for(int i : treeSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSetDescending = new TreeSet<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        //내림차순
        return o2-o1;
    }
});
 
System.out.print("TreeSetDescending: ");
try {
    treeSetDescending.add(null);    //null 허용 X
}catch(NullPointerException ne) {
    System.out.println("exception:"+ne.getMessage());
}
treeSetDescending.add(3);
treeSetDescending.add(2);
treeSetDescending.add(1);
treeSetDescending.add(1); //중복허용X
 
for(int i : treeSetDescending) {
    System.out.print(i+" ");
}
 cs

 

[실행 결과]

HashSet: 1 2 3
linkedHashSet: 3 2 1
TreeSet: 1 2 3
TreeSetDescending: 3 2 1

 

[시간복잡도]

HashSet 이 LinkedHashSet, TreeSet보다 성능이 좋으며 메모리를 적게 사용.

   HashSet LinkedHashSet TreeSet
performance Θ(1) Θ(1) Θ(log(n))

 

참고 :

https://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

 

OSI (Open Systems Interconnection : 네트워크 통신의 개방 시스템 상호 연결)

여러 정보 통신 업체 장비들은 자신들의 장비끼리만 연결이 되는 등 호환성이 없었다.

이에 ISO 단체에서 1984년에 모든 시스템들의 상호 연결에 있어 표준이 되는 OSI 참조 모델 발표

 

데이터를 전송할 때 7-->1계층으로 내려가면서 각각의 층마다 인식할 수 있는 헤더가 붙고 이를 캡슐화(캡슐레이션)라 함

데이터를 수신할 때 1-->7계층으로 올라가면서 헤더가 벗겨지는데 이를 디캡슐레이션이라 함

 

7. Application
Services that are used with end user applications
사용자 인터페이스 제공
프로토콜 : http, ftp

6. Presentation
Formats the data so that it can be viewed by the user
운영체제의 입출력되는 데이터를 암/복호화, 포맷 변환 등 두 장치가 전송 데이터를 이해할 수 있도록 함
제어코드, 문자 및 확장자
jpeg, mpeg

5. Session
Establishes/ends connections between two hosts
통신 세션 구성 (port연결)
대표적인 프로토콜은 SSH

4. Transport
Responsible for the transport protocol and error handling
발신지 대 목적지간(종단 대 종단(end to end) 전체 메시지를 제어 및 에러 관리
L4(로드밸런싱)
대표적인 프로토콜은 tcp, udp

3. Network
Reads the IP address from the packet
패킷를 목적지까지 안전하고 빠르게 전달하는기능(라우팅)
대표적 프로토콜은 ip

2. Datalink
Reads the MAC address from the data packet
MAC주소를 이용하여 정확한 장치로 정보 전달 (브릿지, 스위치)
노드 대 노드 전달을 감독(1계층의 오류를 찾고 재전송)
3계층에서 정보를 받아 주소와 제어정보를 시작(header)과 끝(tail)에 추가

1. Physical 
Send data to the physical wire
비트 (1, 0 (on off)) 단위의 통신단위사용
데이터는 전달만 할 뿐 메시지 내용은 신경 X
통신 cable, hub(더미허브), 리피터 장비가 이에 해당

Hub, 스위치, 라우터 차이

1. Hub(더미허브)(L1)(bit)

1) 전기적 신호를 증폭시켜 LAN의 전송거리를 연장시키는 역할을 하는 네트워크 장비(리피터 역할)

- UTP케이블의 데이터 최대 전송거리는 100미터 남짓이므로 100미터 지점에 허브를 설치할 경우 더 먼거리까지 데이터 전송이 가능

2) 여러대의 장비를 LAN에 접속할 수 있도록 하나로 연결시켜주는 중심축(허브)역할을 하는 네트워크 장비

- IP를 할당하는 기능은 없으며 단순히 포트만 늘려주는 기능을 함

- 허브에 연결된 컴퓨터 및 네트워크 장비의 MAC 주소를 따로 저장하지 않으므로 한 장비에서 전송된 데이터 프레임을 허브에 연결된 모든 장비에 전송(플러딩)

- 허브는 단순한 분배 중계기에 불과하여 연결되는 컴퓨터 수에 따라 데이터 전송 대역이 분리됨(10Mbps 네트워크 라인에 허브를 물리고 허브에 5대의 컴퓨터를 연결했다면 각 컴퓨터 대역폭은 2Mbps)

3) 데이터 송신이 하나의 포트에서만 가능

- CSMA/CD 프로토콜(Carrier Sense Multiple Access with Collision Detection)사용하여 충돌을 방지

* 더미허브 장비는 요즘은 거의 사용되지 않는 장비

 

2. 스위치(스위치허브)(L2)(frame)

- 데이터 송신이 여러 포트에서 가능

연결된 컴퓨터 및 네트워크 장비의 IP와 MAC주소 모두 테이블로 가지고 있어 프레임 전송시 목적지를 파악하여 해당 목적지에 프레임을 전송. 단, 테이블에 없는 목적지를 가진 패킷이 오면 허브의 동작과 마찬가지로 모든 기계에 포워딩.

 

3. 라우터(L3)(패킷)

- 둘 혹은 그 이상의 네트워크와 네트워크 간 데이터 전송을 위해 최적 경로를 설정하며 데이터를 해당 경로를 따라 한 통신망에서 다른 통신망으로 통신할 수 있도록 도와주는 인터넷 접속 장비

- 데이터에 담긴 수신처의 주소를 읽고 적절한 통신통로를 이용해 다른 통신망으로 데이터를 전송하는 장치

- LAN(Local Area Network)을 연결해주는 장치 외부로부터 내부  보호

 

* 공유기

ISP(Internet Service Provider) 업체에서 제공하는 한 개의 인터넷 IP address(공인IP)로 여러 대의 컴퓨터가 인터넷을 공유할 수 있는 기능을 제공

가정용 소용량 라우터

라우터의 NAT(Network Address Translation) 기능을 가지고 있음

: 공유기 사용시 ISP에서 할당받은 공인IP를 내부 네트워크에서 여러개의 사설 IP 주소로 변환하여 사용

 

* 홈 네트워크 구성의 예

모뎀

  ㄴ 공유기(라우터) 

            ㄴ 컴퓨터1                           

            ㄴ TV 셋탑박스

            ㄴ 허브(스위치허브)

                             ㄴ 컴퓨터2

                             ㄴ 컴퓨터3

                             ㄴ NAS

 

 

TCP/IP 4계층 (인터넷모델)

4. Application : OSI 5,6,7

3. Transport : OSI 4

2. Internet : OSI 3

1. Network Interface : OSI 1,2

 

 

참고:

http://blog.naver.com/PostView.nhn?blogId=demonicws&logNo=40117378644

https://shlee0882.tistory.com/110

https://www.quora.com/What-is-the-difference-between-HTTP-protocol-and-TCP-protocol

https://instrumentationtools.com/7-osi-layers-of-communications/

https://m.blog.naver.com/PostView.nhn?blogId=wlsdml1103&logNo=220936267002&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

https://minwan1.github.io/2018/10/01/2018-09-03-network-network-divice/

https://m.blog.naver.com/PostView.nhn?blogId=vanshaw&logNo=220709918927&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

반응형
저작자표시 비영리

'Computer Science > data comm & network' 카테고리의 다른 글

[Network] 3. Application layer : DNS, TTL  (0) 2020.04.06
[Network] 2. Application layer : HTTP, Cookie, Web Cache, Conditional GET, SMTP  (0) 2020.04.05
[Network] 1. 네트워크 기본 : Network 구성요소, TCP vs UDP, 서킷 스위칭 vs 패킷 스위칭, 패킷 딜레이  (0) 2020.04.03
REST API 란  (0) 2019.02.22
IP 클래스(A/B/C) , 서브넷마스크  (0) 2019.02.20

[List]

순서가 있는 데이터의 집합, 데이터 중복을 허용

List Interface 를 구현하는 ArrayList, LinkedList, Vector 는 모두 위 성질을 따름

 

[사용법]

ArrayList, LinkedList, Vector 모두 사용법이 동일하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
List<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(2);    //중복허용, 순서보장
//al.remove(0);
 
System.out.print("ArrayList: ");
for(int i:al) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(2);    //중복허용, 순서보장
//ll.remove(0);
 
System.out.print("LinkedList: ");
for(int i:ll) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> v = new Vector<>();
v.add(1);
v.add(2);
v.add(2);    //중복허용, 순서보장
//v.remove(0);
 
System.out.print("Vector: ");
for(int i:v) {
    System.out.print(i+" ");
}
 cs

[실행 결과]

ArrayList: 1 2 2
LinkedList: 1 2 2
Vector: 1 2 2

 

[차이점]

ArrayList

배열과 동일하나 저장되는 자료크기에 따라 내부적으로 배열의 크기가 늘었다 줄었다 하는 resizable array.

조회 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 증가시킨다(한 칸씩 민다)

데이터 삭제가 발생하면 삭제된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 감소시킨다(한 칸씩 당긴다).

 

LinkedList

자료의 주소값을 기준으로 데이터들이 연결된 형태.

삽입과 삭제의 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입될 데이터 앞의 데이터는 삽입될 데이터의 주소값을,

삽입될 데이터는 삽입될 데이터 뒤에 위치한 데이터의 주소값을 참조하게 한다.

 

Vector

Thread Safe 한 ArrayList (Synchronized)

 

[ArrayList vs LinkedList 성능 비교]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
private static long START_TIME = 0;
    private static long END_TIME = 0;
    
    public static void main(String[] args) {
        
        List<Integer> ArrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.add(0);
        }
        setEndTime();
        System.out.print("ArrayList add: ");
        printDuration();
 
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.add(0);
        }
        setEndTime();
        System.out.print("LinkedList add: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.get(i);
        }
        setEndTime();
        System.out.print("ArrayList get: ");
        printDuration();
        
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.get(i);
        }
        setEndTime();
        System.out.print("LinkedList get: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        Iterator<Integer> ai = ArrayList.iterator();
        while(ai.hasNext()) {
            ArrayList.remove(0);
        }
        setEndTime();
        System.out.print("ArrayList remove: ");
        printDuration();
        
        
        setStartTime();
        Iterator<Integer> li = linkedList.iterator();
        while(li.hasNext()) {
            linkedList.remove(0);
        }
        setEndTime();
        System.out.print("LinkedList remove: ");
        printDuration();
        
    }
    
    private static void setStartTime() {
        START_TIME = System.nanoTime();
    }
    
    private static void setEndTime() {
        END_TIME = System.nanoTime();
    }
    
    private static void printDuration() {
        System.out.println(END_TIME - START_TIME);
    }
 cs

[실행 결과]

ArrayList add: 1049700
LinkedList add: 1224800
-------------------------------------------------
ArrayList get: 861200
LinkedList get: 42666800
-------------------------------------------------
ArrayList remove: 6322100
LinkedList remove: 1229300

 

조회(get)는 ArrayList가 상대적으로 뛰어난 성능을 보여준다.

삽입(add)/삭제(remove)는 LinkedList가 상대적으로 뛰어난 성능을 보여준다.

[ArrayList vs LinkedList 시간복잡도]

   ArrayList LinkedList
Indexing Θ(1) Θ(n)
Insert/delete at beginning Θ(n) Θ(1)
Insert/delete at end Θ(1) Θ(n)-last element is unknown
Θ(1)-last element is known
Insert/delete in middle Θ(n) search time + Θ(1)
Wasted space (average) Θ(n) Θ(n)

 

 

참고 :

https://dzone.com/articles/arraylist-vs-linkedlist-vs

http://www.nextree.co.kr/p6506/

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

Map은 키와 값이 한 쌍으로 이루어지는 데이터의 집합

값은 중복을 허용하나 키는 중복될 수 없음(키는 중복될 경우 덮어 씀)

Map Interface 를 구현한 HashMap, HashTable, LinkedHashMap, TreeMap 은 모두 위 규칙을 따름.

 

 

[HashMap]

순서가 보장되지 않는다.

Null을 허용한다.

Thread Safe 하지 않다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//순서를 보장하지 않음
//key, value 에 Null 허용
//Thread safe X
 
Map<Integer, Integer> map = new HashMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
try {
    map.put(0, null);
} catch(NullPointerException ne) {
    System.out.println(ne.getMessage());
}
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

person : 0, height : null
person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

1, 3, 2, 4, 3, 0 의 Key 를 순서대로 입력하였지만 순서는 지켜지지 않았다.

(혹여 정렬된 것 처럼 값이 출력된다 해도 정렬이 되어 나온게 아니다)

14번 라인에 null 값을 넣어봤지만 exception 이 찍히지 않았다 : null 허용

 

 

[HashTable]

순서가 보장되지 않는다

Null을 허용하지 않는다

Thread Safe 하다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//순서를 보장하지 않음
//key, value 에 Null 허용
//Thread safe
 
Map<Integer, Integer> map = new Hashtable<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
try {
    map.put(0, null);
} catch(NullPointerException ne) {
    System.out.println(ne.getMessage());
}
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

null
person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

HashMap 과 마찬가지로 순서가 보장되지 않았다.

14번라인에서 NullPointerException 이 발생하여 null 이라는 에러메시지를 찍고 있다.

 

 

[LinkedHashMap]

입력한 순서가 보장된다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//입력한 순서가 보장됨
//Thread safe X
 
Map<Integer, Integer> map = new LinkedHashMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

person : 1, height : 180
person : 3, height : 170
person : 2, height : 160
person : 4, height : 190

put 을 한 순서(1, 3, 2, 4)대로 결과가 출력되었다.

 

 

[TreeMap]

데이터가 내부적으로 정렬되어 존재한다. (RedBlackTree 구조)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//KEY를 기준으로 정렬함(내부적으로 RedBlackTree 구조로 정렬)
//Thread safe X
 
Map<Integer, Integer> map = new TreeMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 
 cs

[실행 결과]

person : 1, height : 180
person : 2, height : 160
person : 3, height : 170
person : 4, height : 190

오름차순 기준으로 key값을 정렬하여 출력되었다.

 

 

※ 정렬 순서를 바꾸고 싶다면?

Comparator 를 인자값으로 넘겨준다. Comparator 에 대한 설명은 이곳을 참고

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Map<Integer, Integer> map2 = new TreeMap<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}); 
 
map2.put(1, 180);
map2.put(3, 175);
map2.put(2, 160);
map2.put(4, 190);
map2.put(3, 170);
 
for(int s : map2.keySet()) {
    System.out.println("person : " + s + ", height : " + map2.get(s));
}
 cs

[실행결과]

person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

내림차순 기준으로 key값을 정렬하여 출력되었다.

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
트리 순회  (0) 2019.11.26

+ Recent posts

티스토리툴바