y-log

풀이

pypy3으로 출력해야 시간초과가 나지 않는다~!

1. N으로 개수 입력을 받는다.
2. numbers 라는 빈 리스트를 만들어준다.
3. 받아준 N 횟수만큼 for문을 돌리며 숫자를 입력받는다.
4. sort함수를 써서 오름차순 정렬을 해준다.
5. 출력은 '\n'.join(리스트) : \n과 값을 넣어서 하나의 문자열로 합쳐준다.

import sys
input = sys.stdin.readline

N = int(input())
numbers = []

for _ in range(N):
    numbers.append(int(input()))

numbers.sort()
print('\n'.join(map(str, numbers)))

AUSG spring 기초 스터디를 참여하게 되었다.

올해 초부터 스프링을 붙잡고 있긴 했는데, 생각보다 공부를 딥하게 해보지 않았고 아직도 잔잔바리 수준이라 이론반에 참여하지 못하고 기초반에 참여하게 되었다....

이번 기회에 마스터해보리라~~~

저자 깃허브 : https://github.com/jojoldu/freelec-springboot2-webservice

자바 프로그래밍 = 객체 지향 프로그래밍

OOP
Object Oriented Programming
객체 지향 프로그래밍

객체란 말 그대로 대상을 나타내는 단어

예를 들어, 사람 개인 한 명 한 명을 모두 객체라 할 수 있고, 책 한 권 한 권을 객체라 할 수 있다.

클래스

사람들은 일반적으로 같은 속성들을 갖고 있는데, 여기서 속성이란 눈, 코, 입, 손, 발, 등의 신체들을 의미한다.

사람같은 객체들이 공통적으로 갖는 속성들을 모아서 정의내린 것을 클래스라고 한다.

객체 = 붕어빵

클래스 = 붕어빵 틀

oop하면 자동으로 4가지 속성이 떠올라야 한다.

OOP 속성

1. 캡슐화 Encapsulation

캡슐화란 하나의 객체에 대해 그 객체가 특정한 목적을 위해 필요한 변수나 메소드를 하나로 묶는 것을 의미한다.

따라서 클래스를 우리가 만들 때 훗날 이클래스에서 만들어진 객체가 특정한 목적을 가지고 사용해야할 변수와 그 변수를 가지고 특정한 액션 즉 메서드 또는 함수를 관련성 있게 클래스에 구성해야한다.

예를 들자면, 은행이라는 클래스는 잔고라는 변수가 있고 그 잔고를 조회하거나, 잔고를 수정할 수 있는 메서드등이 있다고 치는 것이다. 

근데 캡슐화를 하는 중요한 목적은 바로 정보의 은닉화이다.  잔고라는 변수가 만약 public 으로 선언되어있다고 치자. 200만원인 나의 잔고가 누군가 접근에 의해 0원이 될수도 있는 것이다. 따라서 잔고라는 변수를 바로 접근할 수 없도록 private로 선언하고 데이터를 보호하는 것이다.

이렇게 보호된 변수는 getter나 setter등의 메서드를 통해서만 간접적으로 접근이 가능하도록 하는 것이 바로 캡슐화의 중요한 목적이다.

2. 추상화 Abstraction

추상적으로 생각해 일단 큰틀의 클래스를 구현하고 거기에 최소 이러한 공통적인 요소나 필수적인 요소는 들어갔으면 하는 바램에서 만든 것이 추상클래스이다.

이 과정에서 공통적인 요소나 특징을 추출하는 과정이 추상화 인것 같다. 

예를 들자면, 벤츠,아우디,소나타,티코,밴틀리 등등 우리가 생각하는 여러종류의 자동차이 있다. 이것을 다 클래스화하고 변수와 메서드 등을 개별적으로 만드는 것은 무모한 짓이다. (거두절미하고 말하면 확장성때문에 추상화할 필요가 있다.)

따라서 방금 나열한 자동차들의 공통적인 요소나 특징을 추출하는 과정인 추상화를 거쳐 요소를 끄집어 내면, 바퀴,배기통,핸들,차문,유리창,등 필수적인 부품이 있고 바퀴는 굴러가야하며, 핸들은 좌우로 돌아가야하고 

차문은 열려야한다는 공통적인 행등 즉 어떤 차든 필수적으로 필요한 메서드가 추출된다. 

3. 다형성 Polymorphism

다형성은 상속을 통해 기능을 확장하거나 변경하는 것을 가능하게 해준다. 이를 통해 코드의 재사용, 코드길이 감소가 되어 유지보수가 용이하도록 도와주는 개념이다.

쉽게 같은 동작이지만 다른결과물을 나올때 이를 다형성이라고 생각하면 된다.

크게 자바프로그래밍 객체지향에서 다형성의 개념을 녹여내는 방법은 두가지인데, 바로

오버라이딩(Overriding) 과 오버로딩(Overloading) 이다.

오버라이딩은 부모클래스에서 상속받은 서브클래스 즉 자식클래스에서 부모클래스,즉 상위클래스에서 만들어진 메서드를 자신의 입맛대로 다시 재창조해서 사용하는 것을 말한다.

오버로딩은 하나의 클래스 안에서 같은이름의 메서드를 사용하지만 각 메서드마다 다른 용도로 사용되며 그 결과물도 다르게 구현할 수 있게 만드는 개념인데 오버로딩이 가능하려면 메서드끼리 이름은 같지만 매개변수의 갯수나 데이터타입이 다르면 오버로딩이 적용되어 메서드 이름이 같아도 
문법 에러가 나지않는다..

4. 상속성, 재사용 Inheritance

상속은 객체지향의 꽃이라고 할 수 있다. 상속이란 기존 상위클래스에 근거하여 새롭게 클래스와 행위를 정의할 수 있게 도와주는 개념이다.

기존클래스에 기능을 가져와 재사용할 수있으면서도 동시에 새롭게 만든 클래스에 새로운 기능을 추가할 수 있게 만들어 준다.

* 자바에선 상속은 단일상속밖에 지원이 안된다.

그러나 다중상속이 필요할 순 있다고 인정하여 대비책으로 인터페이스를 다중상속(구현) 할 수 있게해서 임시적인 다중 상속에 대한 활로는 뚫어줬다. 그렇지만 인터페이스의 존재이유가 다중상속을 지원하기 위함이다 라고 생각하면 안된다.

JVM
Java Virtual Machine
자바 가상 머신

* 가상 머신 : 프로그램을 실행하기 위해 물리적 머신과 유사한 머신을 소프트웨어로 구현한 것

• JVM은 JAVA와 OS 사이에서 중개자 역할을 수행하여 JAVA가 OS에 구애받지 않고 재사용을 가능케 해준다.
• 메모리관리, Garbage collection을 수행한다.
• JVM은 스택기반의 가상머신이므로 스택기반으로 동작한다.

왜 자바 가상머신을 알아야할까?

한정된 메모리를 효율적으로 사용하여 최고의 성능을 내기 위해서이다.
메모리 효율성을 위해 메모리 구조를 알아야 하기 때문.
동일한 기능의 프로그램이라도 메모리 관리에 따라 성능이 좌우된다. 메모리가 관리가 되지 않은 경우 속도 저하 현상이나 튕김 현상등이 일어날 수 있다. 

자바 프로그램 실행과정

1. 프로그램 실행시 JVM은 OS로부터 이 프로그램이 필요로 하는 메모리를 할당받는다. 
                         JVM은 이 메모리를 용도에 따라 여러 영역으로 나누어 관리한다.
2. 자바 컴파일러가 자바 소스코드를 읽어들여 자바 바이트 코드로 변환시킨다. ( .java -> .class )
3. Class Loader를 통해 class 파일들을 JVM으로 로딩한다.
4. 로딩된 class 파일들은 Execution engine을 통해 해석된다.
5. 해석된 바이트 코드는 runtime data areas에 배치되어 실질적인 수행이 이루어진다.
             이러한 실행과정 속에서 JVM은 필요에 따라 Thread Synchronization과 GC 같은 관리작업 수행

JVM 구성

Class Loader

JVM내로 클래스( .class 파일 )를 로드하고 링크를 통해 배치하는 작업을 수행하는 모듈이다. runtime 시에 동적으로 클래스를 로드한다. jar 파일 내 저장된 클래스들을 JVM 위에 탑재하고 사용하지 않는 클래스들은 메모리에서 삭제한다. (컴파일러 역할) 자바는 동적 코드, 컴파일 타임이 아니라 런타임에 참조한다. 즉, 클래스를 처음으로 참조할 때, 해당 클래스를 로드하고 링크한다는 것이다. 그 역할을 수행하는 것이 클래스 로더다.

Execution Engine 

클래스를 실행시키는 역할이다. 클래스로더가 JVM 내의 런타임 데이터 영역에 바이트 코드를 배치시키고, 이것은 실행 엔진에 의해 실행된다. 자바 바이트코드는 기계가 바로 수행할 수 있는 언어보다는 비교적 인간이 보기 편한 형태로 기술된 것이다. 그래서 실행 엔진은 바이트 코드를 실제 JVM 내부에서 기계가 실행할 수 있는 형태로 변경한다. 

이때 두가지 방식을 사용하게 된다.

Interpreter 
실행 엔진은 자바 바이트 코드를 명령어 단위로 읽어서 실행한다.
하지만 이 방식은 인터프리터 언어의 단점을 그대로 갖고 있다. 
한 줄 씩 수행하기 때문에 느리다는 것이다.

JIT ( Just - In - Time )
인터프리터 방식의 단점을 보안하기 위해 도입된 JIT 컴파일러다. 
인터프리터 방식으로 실행하다가 적절한 시점에 바이트 코드 전체를 컴파일하여 네이티브 코드로 변경하고, 이후에는 더이상 인터프리팅 하지 않고 네이티브 코드로 직접 실행하는 방식이다.
네이티브 코드는 캐시에 보관하기 때문에 한 번 컴파일된 코드는 빠르게 수행하게 된다.
물론 JIT컴파일러가 컴파일 하는 과정은 바이트코드를 인터프리팅하는 것보다 훨씬 오래걸리므로, 한번만 실행되는 코드라면 컴파일하지 않고 인터프리팅하는 것이 유리하다.
따라서 JIT컴파일러를 사용하는 JVM들은 내부적으로 해당 메서드가 얼마나 자주 수행되는지 체크하고 일정 정도를 넘을 때에만 컴파일을 수행한다.

Garbage collector

GC를 수행하는 모듈(thread)이 있다.

Runtime Data Area

:프로그램을 수행하기 위해 OS에서 할당받은 메모리 공간

1. PC 레지스터

Thread가 시작될 때 생성된다.

스레드마다 하나씩 존재하고 thread가 어떤 부분을 어떤 명령으로 실행해야할지에 대한 기록을 하는 부분으로 현재 수행 중인 JVM 명령의 주소를 갖는다.

2. JVM 스택 영역

프로그램 실행과정에서 임의로 할당되었다가 메소드를 빠져나가면 바로 소멸되는 특성의 데이터를 저장하기 위한 영역이다. 각종 형태의 변수나 임세 데이터, 스레드나 메소드의 정보를 저장한다.

메소드 호출 시마다 각각의 스택 프레임(그 메소드만을 위한 공간)이 생성된다.

메소드 수행이 끝나면 프레임 별로 삭제를 한다.

메소드 안에서 사용되는 값들(local variable)을 저장한다.

또 호출된 메소드의 매개변수, 지역변수, 리턴 값 및 연산 시 일어나는 값들을 임시로 저장한다.

3. Native method stack

자바 프로그램이 컴파일되어 생성되는 바이트 코드가 아닌, 실제 실행가능한 기계어로 작성된 프로그램을 실행시키는 영역이다. (JAVA가 아닌 다른 언어로 작성된 코드를 위한 공간)

JAVA Native Interface를 통해 바이트 코드로 전환하여 저장하게 된다. 

일반 프로그램처럼 커널이 스택을 잡아 독자적으로 프로그램을 실행시키는 영역이다.

이 부분을 통해 C code를 실행시켜 커널에 접근할 수 있다.

4. Metod Area = class area = static area

클래스 정보를 처음 메모리 공간에 올릴 때 초기화 되는 대상을 저장하기 위한 메모리 공간이다.

올라가게 되는 메소드의 바이트 코드는 프로그램의 흐름을 구성하는 바이트 코드이다. 자바 프로그램은 main 메소드의 호출에서부터 계속된 메소드의 호출로 흐름을 이어가기 때문이다. 

대부분 인스턴스의 생성도 메소드 내에서 명령하고 호출한다. 

사실상 컴파일 된 바이트 코드의  대부분이 메소드 바이트 코드이기 때문에 거의 모든 바이트코드가 올라간다고 봐도 상관 없다. 

이 공간에는 Runtime Constant Pool이라는 별도의 관리영역이 존재하는데, 이는 상수 자료형을 저장하여 참조하고 중복을 막는 역할을 수행한다.

올라가는 정보의 종류

- field information : 멤버 변수의 이름, 데이터 타입, 접근 제어자에 대한 정보
- method information : 메소드의 이름, 리턴 타입, 매개변수, 접근 제어자에 대한 정보
- type information : class인지 interface인지의 여부 저장, type이 속성, 전체 이름, super class의 전체 이름

* method area = 클래스 데이터를 위한 공간   |   heap 영역 = 객체를 위한 공간

  heap과 마찬가지로 GC의 관리 대상에 포함된다.

5. Heap

객체를 저장하는 가상 메모리 공간이다. new 연산자로 생성된 객체와 배열을 저장한다.

물론 class area 영역에 올라온 클래스들만 객체로 생성할 수 있다. 

힙은 세 부분으로 나뉜다.

• New/Young Generation

Eden : 객체들이 최초로 생성되는 공간

Survivor 0/1 : Eden에서 참조되는 객체들이 저장되는 공간

• Old 영역

new area에서 일정 시간 참조되고 있는, 살아남은 객체들이 저장되는 공간인 Eden 영역에 객체가 가득차게되면 첫번째 GC가 발생한다. eden 영역에 있는 값들을 survivor 1 영역에 복사하고 이 영역을 제외한 나머지 영역의 객체를 삭제한다.

* 인스턴스는 소멸 방법과 소멸 시점이 지역 변수와는 다르기에 힙이라는 별도의 영역에 할당 된다. JVM은 매우 합리적으로 인스턴스를 소멸시킨다. ( 더이상 인스턴스의 존재 이유가 없을 때 소멸시킨다 )

• Permanent Generation

생성된 객체들의 정보의 주소값이 저장된 공간이다.

class loader에 의해 로드되는 class, method 등에 대한 meta 정보가 저장되는 영역이고 JVM에 의해 사용된다. 

reflection을 사용하여 동적으로 클래스가 로딩되는 경우에 사용된다.

내부적으로 reflection 기능을 자주 사용하는 spring framework를 이용할 경우 이 영역에 대한 고려가 필요하다.

Array

가장 기본적인 자료구조
논리적 저장 순서 = 물리적 저장 순서

인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다.

그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다.

삽입의 경우도 마찬가지이다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 된다.

Linked List

각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억

자기 다음에 어떤 원소인지 기억해두기 때문에 그 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1) 만에 해결가능!

하지만 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 것이다. Array 와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다. 이것은 일단 삽입하고 정렬하는 것과 마찬가지이다. 이 과정 때문에, 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 

그렇지만 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

전반적으로 리스트의 사용이 훨씬 좋아보인다.

하지만 일반적인 알고리즘 문제를 풀이할 땐 리스트보다 배열이 훨씬 빠르고 좋다.

왜냐하면 대부분의 알고리즘 연습문제들은 그 메모리 공간의 범위를 주어지기 때문에 배열 선언을 그 MAX치로 잡을 수 있다면, 훨씬 더 편리하고 리스트와는 전혀 다른 속도를 보인다.

리스트의 입력은 추가 과정마다 메모리의 할당이 일어나고 삭제에서는 메모리의 해제가 일어난다. 메모리의 할당과 해제는 O() 시간으로 따지지 않지만, 이런 시스템 콜(System Call)을 사용하는 문구는 시간소요가 꽤 걸린다.

배열이든 리스트이든 단순히 이론을 떠나서 자기가 무엇을 하려는지, 그 목적에 따라 선택하는 것이 좋다.

Index

칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어둔다.

* DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에

원하는 값을 탐색하는 것은 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 query문 실행 속도가 느려진다.

DBMS에서 인덱스는 데이터의 저장 성능을 희생하는 대신 데이터의 읽기 속도를 높이는 기능이다.

Index 자료구조 - DBMS의 인덱스 관리

B+- Tree Index 알고리즘
일반적으로 사용되는 알고리즘이다.
B +- 인덱스는 칼럼의 값을 변형하지 않고(사실은값의 앞부분만 잘라서 관리한다고 한다),
원래의 값을 이용해 인덱싱하는 알고리즘이다.

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다.

하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다.

주로 메모리 기반의 데이터베이스에서 많이 사용한다.

왜 index 를 생성하는데 b-tree 를 사용하는가?
데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데?
SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다.
hash table 을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다.
동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.

Primary Index vs Secondary Index

클러스터(Cluster)란 여러 개를 하나로 묶는다는 의미로 주로 사용되는데, 클러스터드 인덱스도 크게 다르지 않다. 인덱스에서 클러스터드는 비슷한 것들을 묶어서 저장하는 형태로 구현되는데, 이는 주로 비슷한 값들을 동시에 조회하는 경우가 많다는 점에서 착안된 것이다. 여기서 비슷한 값들은 물리적으로 인접한 장소에 저장되어 있는 데이터들을 말한다.
클러스터드 인덱스는 테이블의 프라이머리 키에 대해서만 적용되는 내용이다. 즉 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터드 인덱스라고 표현한다. 클러스터드 인덱스에서는 프라이머리 키 값에 의해 레코드의 저장 위치가 결정되며 프라이머리 키 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 한다. 그렇기 때문에 프라이머리 키를 신중하게 결정하고 클러스터드 인덱스를 사용해야 한다.
클러스터드 인덱스는 테이블 당 한 개만 생성할 수 있다. 프라이머리 키에 대해서만 적용되기 때문이다, 이에 반해 non 클러스터드 인덱스는 테이블 당 여러 개를 생성할 수 있다.


Composite Index

인덱스로 설정하는 필드의 속성이 중요하다. title, author 이 순서로 인덱스를 설정한다면 title 을 search 하는 경우, index 를 생성한 효과를 볼 수 있지만, author 만으로 search 하는 경우, index 를 생성한 것이 소용이 없어진다. 따라서 SELECT 질의를 어떻게 할 것인가가 인덱스를 어떻게 생성할 것인가에 대해 많은 영향을 끼치게 된다.

Index의 성능과 고려해야할 사항

SELECT 쿼리의 성능을 월등히 향상시키는 INDEX 항상 좋을까?  아니다.

- INDEX 를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생

INSERT 의 경우 INDEX 에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따른다.

DELETE 의 경우 INDEX 에 존재하는 값은 삭제하지 않고 사용 안한다는 표시로 남게 된다.

즉 row 의 수는 그대로인 것이다. 이 작업이 반복되면 어떻게 될까? 실제 데이터는 10 만건인데 데이터가 100 만건 있는 결과를 낳을 수도 있는 것이다. 이렇게 되면 인덱스는 더 이상 제 역할을 못하게 되는 것이다.

UPDATE 의 경우는 INSERT 의 경우, DELETE 의 경우의 문제점을 동시에 수반한다.

이전 데이터가 삭제되고 그 자리에 새 데이터가 들어오는 개념이기 때문이다.

즉 변경 전 데이터는 삭제되지 않고 insert 로 인한 split 도 발생하게 된다.

- 컬럼을 이루고 있는 데이터의 형식에 따라서 인덱스의 성능이 악영향을 미칠 수 있다.

즉, 데이터의 형식에 따라 인덱스를 만들면 효율적이고 만들면 비효율적인 데이터의 형식이 존재한다.

이름, 나이, 성별 세 가지의 필드를 갖고 있는 테이블을 생각해보자.

이름은 온갖 경우의 수가 존재할 것이며 나이는 INT 타입을 갖을 것이고, 성별은 남, 녀 두 가지 경우에 대해서만 데이터가 존재할 것임을 쉽게 예측할 수 있다.

이 경우 어떤 컬럼에 대해서 인덱스를 생성하는 것이 효율적일까? 이름에 대해서만 인덱스를 생성하면 효율적이다.

*왜 성별이나 나이는 인덱스를 생성하면 비효율적일까? 

10000 레코드에 해당하는 테이블에 대해서 2000 단위로 성별에 인덱스를 생성했다고 가정하자. 값의 range 가 적은 성별은 인덱스를 읽고 다시 한 번 디스크 I/O 가 발생하기 때문에 그 만큼 비효율적인 것이다.

< 참고 >

https://mungto.tistory.com/312

CPU 스케줄링

메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것
Ready Queue에 있는 프로세스들 중에 누구에게 CPU를 할당해 줄 것인지 정하는 것

왜 필요한가?

CPU는 한 번에 하나의 프로세스만을 실행시킬 수 있다. --> 특정 프로세스가 I/O 요청으로 대기할 경우, CPU는 놀게됨

시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.

CPU 이용률 극대화

선점 및 비선점 스케줄링

CPU 스케줄러가 작동되는 4가지 상황

비선점 nonpreemptive

: 상황 1,4와 같이 프로세스가 자발적으로 CPU를 반납하는 경우

CPU가 한 프로세스에 할당되면 프로세스가 종료되든지, 또는 대기상태로 전환해 CPU를 방출할 때까지 점유한다.

선점 preemptive

: 상황 2,3과 같이 강제적으로 CPU를 빼앗기는 경우

Windows, macOS, Linux를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.

스케줄링 기준

CPU 이용률

전체 시스템 사용 시간 중 CPU가 작업을 처리하는 시간의 비율 

처리량

단위 시간당 완료된 프로셋의 개수

총 처리 시간

프로세스가 시작해서 끝날 때까지 걸리는 시간 ( 준비 큐에서 대기 시간 + CPU 실행 시간 + I/O 시간 )

대기 시간

프로세스가 준비 큐에서 대기하며 보낸 시간의 합

응답 시간

하나의 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간 ( 응답이 출력되는 시간은 포함하지 않는다 )

CPU 이용률과 처리량을 최대화하고 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는 것으로~!

스케줄링 알고리즘

선입 선처리 FCFS (First Come First Served)

특징

• 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
• 비선점형(Non-Preemptive) 스케줄링
  일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.

문제점

• convoy effect
  소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

SJF(Shortest - Job - First)

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
• 비선점형(Non-Preemptive) 스케줄링

문제점

• starvation
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 (Preemptive) 스케줄링
  현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

문제점

• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
• 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
• 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

문제점

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

특징

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

장점

• Response time이 빨라진다.
  n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
  공정한 스케줄링이라고 할 수 있다.

주의할 점

설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

< 참고 >

https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

TCP와 UDP는 TCP/IP의 전송계층(OSI 7계층 중 4계층, transport)에서 사용되는 프로토콜

네트워크 계층에서 데이터를 수신지 컴퓨터까지 전달했다면, 전송 계층에서는 컴퓨터가 받은 데이터를 애플리케이션까지 전달하는 것이다.

* 전송계층 : 전송에 적합한 크기로 쪼갠 후 목적지의 프로그램을 식별케하는 포트번호를 덧붙이며 IP에 의해 전달되는 패킷의 오류를 검사하고 재전송을 요구하는 등의 제어를 담당하는 계층

TCP와 UDP의 차이

TCP

​

트랜스포트 계층의 TCP 프로토콜은 수신지에 데이터가 정확하게 전달되도록 전송 속도를 조절하거나 도달하지 않은 데이터를 재전송한다. 한마디로, 속도보다는 정확한 전달을 중시

​

UDP

​

VoIP(인터넷 전화)나 동영상 스트리밍 서비스와 같이 실시간 통신이 필요하다면 전송 속도를 중시하는 UDP를 사용한다. TCP와 다르게 정확성보다는 속도를 중시

TCP의 3 way handshacking

TCP는 연결지향 프로토콜로 데이터 송수신 전에 커넥션 연결부터 한다.

커넥션을 맺는 과정에서 3단계로 진행하기 때문에 이것을 3방향 핸드셰이크(3-way handshake)라고 부른다.

커넥션이 맺어지면 데이터를 전송할 수 있는 상태가 되고, 데이터 전송이 끝나면 커넥션을 끊는다.

TCP가 정확하게 데이터를 전달하기 위해

TCP는 데이터 전송에 신뢰성을 더하기 위해 데이터를 세그먼트(segment)라는 단위로 분할하고, 전송속도를 조정하며, 데이터가 제대로 전달되지 않았을 경우 재전송을 하게 된다.

UDP가 신속하게 데이터를 전달하기 위해

통신 과정에서 데이터의 손실이 발생하는데, 일부 손실이 발생해도 문제없는 인터넷전화나 동영상 스트리밍 서비스에서 많이 사용한다.

TCP와 다르게 접속이 맺어졌는지 확인하지 않고(=비연결성) 바로 서버에서 클라이언트로 송신하며 패킷이 도중에 손실되더라도 상관하지 않고 계속 보낸다. 

( UDP의 패킷에 해당하는 데이터그램은 TCP의 세그먼트보다 헤더의 내용이 훨씬 가볍고 간단하다)

UDP에 신뢰성 추가~! ( 복잡해짐.. )

실시간 처리가 필요한 온라인 게임에서는 전송 속도가 우선인 UDP를 사용하긴 하지만, 데이터 전송의 신뢰성 역시 속도에 못지않게 중요하다. 이런 경우에는 애플리케이션 계층에서 흐름 제어(Flow Control)나 혼잡 제어(Congestion control)를 구현하여 부족한 신뢰성을 보완하게 된다.

<참고>

https://m.blog.naver.com/good_ray/221984839492 https://velog.io/@hidaehyunlee/TCP-%EC%99%80-UDP-%EC%9D%98-%EC%B0%A8%EC%9D%B4

HashMap과 HashTable

동기화가 필요없다면 해시맵을,
동기화 보장이 필요하다면 해시테이블을!

차이점

동기화 Synchronization

HashMap의 경우 동기화를 지원하지 않는다. 

반면 다중 스레드 환경에서 HashTable은 동기화를 지원하기 때문에 실행 환경에 따라 구분하여 사용하면 된다.

* vector의 상위 호환 개념인 ArrayList의 사용을 권장하듯, 새로운 버전인 HashMap을 주로 사용하고 동기화가 필요하면 ConcurrentHashMap을 사용하는 것이 더 좋은 방법이라고 한다. 구형인 HashTable은 동기화 처리라는 비용때문에 HashMap에 비해 느리다. 

Thread-safe 여부

Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다.

따라서 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다.

Null 값 허용 여부

Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

Enumeration 여부 

HashMap은 저장된 요소들의 순회를 위해 Fail-Fast Iterator를 반환한다.(ConcurrentHashMap의 경우에는 Fail-Safe Iterator)

Hashtable은 같은 경우 Enumeration을 반환한다.

* Fail-Fast Iterator : 말 그대로 빠른 에러를 발생시켜 버그를 예방할 수 있다.

반면에 Enumeration를 사용한 코드는 중간에 remove를 해도 예외가 발생하지 않는다. 그렇기 때문에 나중에 버그를 발견하지 못할 확률도 존재한다.

보조 해시 사용

HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.

<참고>

https://odol87.tistory.com/3 https://devlog-wjdrbs96.tistory.com/253 https://12216715011126.tistory.com/53

용어 정리

Hash 자료구조란

key와 value를 갖는 자료구조로 효율적인 검색과 저장을 위해 사용된다. 

linked list와 달리 해당 자료가 위치한 버킷의 주소값을 바로 알아내어 찾아갈 수 있다.

시간 복잡도가 O(1)에 수렴하게 된다.

Hash 함수, Hash 알고리즘, Hash 코드

임의의 길이의 데이터를 고정 길이의 데이터로 매핑하는 함수

비둘기집 원리에 의해 해시함수의 결과값이 중복 되어 해시 충돌을 야기할 수 있다.

* 비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣을 때, 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리

데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요하다.

예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다. 

만약, 
hello 라는 문자열을 정수형 key 값으로 바꾼다면,
h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는
해시코드로 변환할 수 있다.

여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되는데, 주어진 문제마다 적절한 해시 함수(해시 알고리즘)을 구현하는 것은 개발자의 역량에 달려있다.

Hash 코드를 사용해서 Hash table에 저장하기

해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없다.

이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있다.

예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용한다.

* 각 버킷은 몇 개의 슬롯으로 구성되어 있다.

OverFlow란 

여러개의 키값이 공통된 버킷을 가리키는 경우, 버킷들의 공간은 유한해서 결국 버킷이 꽉 차게 된다.

꽉 차있는 순간 또하나의 키값이 해당 버킷에 맵핑된다면 오버플로우가 발생한다.

충돌 Collision

다른 해시코드임에도 같은 인덱스가 나오는 경우가 발생할 수 있다.

이런 경우 충돌이 발생했다고 하는데 충돌의 해결방식은 여러가지가 있다. 

분리 체인법, 선형 탐사법, 2차 탐사법, 이중 해싱 등이 존재한다.

* 이러한 이유로 자바에서 hashCode( )를 오버라이딩 할 때 equals( )도 오버라이딩 해야한다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도 equals로 값의 동등성을 한번 더 확인하는 과정을 거치게 되면 충돌을 방지할 수 있다.

충돌 해결하기

1. 분리 체인법 seperate chaning (open hashing)

같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 Linked List를 선언하고 각 데이터들을 이 리스트에 저장한다.

이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다.

한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 한다. 

* 충돌이 발생하면 주어진 해시테이블 공간외의 새로운 공간을 할당해주기 때문에 open hashing이라고도 불린다.

2. Open Addressing (Closed Hashing)

주어진 해시테이블에서 정해진 규칙에 따라 버킷을 찾아 저장하는 방법이다. open addressing의 버킷 결정 방법에는 몇가지가 있다.

2.1 선형 조사

충돌이 일어난 다음 자리에 저장하는 방법

제 1 군집 현상이 발생한다

* 제 1 군집 현상 : 특정 영역에 데이터가 몰릴 때, linked list의 순차 탐색으로 데이터의 저장공간이 지정되어 성능이 치명적으로 저하된다. ( 이차원 조사로 해결 가능하다)

2.2 이차원 조사

충돌이 발생한 경우 다음 데이터의 자리를 이차함수로 결정한다.

2.3 더블 해싱

2.4 무작위 처리 방법

<참고>

https://siyoon210.tistory.com/85 https://galid1.tistory.com/171