채니의 mimimimamimimo 블로그

What?

동기화(同期化, synchronization)란, 말그대로 동시에 시스템을 작동시킬 수 있도록 만드는 것이다. 

그러므로 프로세스 동기화란, 멀티프로세스를 가능하게 만드는 것이다. 

이렇게 따로 용어까지 있는 정도면, 프로세스를 동시에 작동하는 것이 어떤 문제를 발생시킬 수 있을 정도로 중요한 문제가 될 수도 있다는 것이다. 바로 자원의 문제이다. 

먼저, 프로세스를 작동시키는 물리적인 주체는 cpu가 어떻게 프로세스를 작동시키는지,  자원을 어떻게 다루는지 보자..

*cpu 하나는 한번에 프로세스 하나만 처리할 수 있다.*

*프로세스는 ram 위에 작동되는 프로그램을 뜻하고, ram 위에는 프로세스마다 자신의 Code,Data,Stack에 대한 주소공간이 있다*

*cpu가 프로세스를 작동시키는 과정은 다음 그림과 같다*

cpu는 하나의 프로세스 Data(on ram)에서 연산할 data를 가져와 연산을 하고, 연산 결과를 다시 Data(on ram)에 저장한다.

Issue?

그렇다. 한 프로세스의 주소공간은 다른 프로세스의 주소공간에 독립적이므로, Data 자원에 대해 문제가 생길 일이 없다. 하지만 프로세스 사이에 공유메모리(이전글)를 사용하는 경우라면, 얘기가 달라진다. 

예를 들어, a프로세스가 cnt란 변수를 1만큼 올렸는데, b프로세스가 cpu를 빼앗아서 cnt를 2로 올리고, 다시 a프로세스가 cpu를 빼앗으면 cnt를 1에서 이어서 올리는 것이 아닌, 2에서부터 올리게 되어 원래의 의도와 달라진다. 이것을 cpu를 빼앗기는 타이밍에 의해 Data의 일관성이 깨진다고 한다. 

Solution?

cpu가 하나인 경우) 프로세스 선택 정책을 선점이 아닌 비선점을 택하면 된다. 위의 경우에서, a프로세스가  cnt를 올리려고 했던만큼 완전히 올리기 전까진 b프로세스가 cpu를 뺏지 못하는 것을 의미한다. 

cpu가 여러개인 경우) 프로세서 자체가 구분되어 있어서 자원에 접근하는 것을 막을 방법이 없다. 그래서 커널에서 락을 걸어서, 커널이 자원에 한 프로세스만 접근하도록 결정한다. 피터슨 알고리즘, 세마포어, 모니터가 있다. 

먼저, 용어에 대해 정리하고 가자. 

락(lock 상호배제 or mutex or mutual exclusion):  동기화 메커니즘

Issue에서 설명한 것과 같이, 공유 자원에 대해 여러 개의 프로세스가 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 경쟁상태라고 말한다. 

공유자원 중에서도, 둘 이상의 스레드가 동시에 접근해서는 안되는 코드의 일부를 크리티컬 섹션,임계구역, 공유변수라고 말한다. 

1)피터슨 알고리즘(소프트웨어적 락):

자신 프로세스의 turn=0, 다른 프로세스의 turn=1 일 때(각각 다른 프로세서가 맡았을 때) 0을 기준으로 while(turn!=0)은 1의 순서인 동안 루프만 돌며 임계영역에 진입하지 않는다는 뜻이다. 1의 순서가 끝났으면 자신 프로세스는 루프를 지나 critical section에 진입하고, 볼 일을 다 보면  다시 turn=1로 순서를 바꾸어준다. 다른 프로세서의 turn 1 프로세스는 자신의 차례이니 critical section에 진입한다. 

Issue->cpu는 instruction 단위로 빼앗길 수도 있어서, critical section 중도에 뺏기면  turn을 돌려놓지 않고 빼앗기는 것이기 때문에 다른 프로세스에서는  turn의 값이 바뀔때까지 기다리고, 자신 프로세스 또한 cpu를 뺏긴 상태기 때문에  <progress,진행 문제>와 <스핀락> 현상이 일어날 수도 있다.

progress,진행 문제:  아무도 critical section에 들어가지 않는 상태

스핀락,바쁜대기: critical section에 진입이 가능할 때까지 루프를 돌면서 재시도하는 상태(cpu와 메모리를 계속 써서 낭비함)

2)Test and Modify(하드웨어적 락):

 instruction 단위로 cpu 뺏길수도 있어서 생기는 위의 문제를 

하드웨어적으로 instruction이 끝날때마다 flag 바꿔주는 것을 지원하는 방법이다. 

Issue->여전히 프로그래머의 실수가 영향을 미친다는 단점을 가지고 있다.

3)세마포어: 

위의 방식들을 추상화시킨 방법이다. 

세마포어 S는 정수값을 가지는 변수이고, P와 V라는 명령으로만 접근할 수 있다. 

즉, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.

방법1...스핀락 사용

P(S) { while S <=0; // 아무것도 하지 않음 (반복문)  S--; } 자원 얻음

V(S) { S++; }  자원 반납

방법2...슬립락 사용(바쁜대기를 보완하여, cpu와 메모리를 쓰지않는동안 넘겨준다 )

P(S) { S--; if S < 0 // 이 프로세스를 재움 큐에 추가 (block) }  가용자원 없으니 block하는거다. 1편 참고

V(S) { S++; if S <= 0 // 재움 큐로부터 프로세스를 제거 (wakeup) } 되돌려줬는데도 음수란건 누군가가 음수로 만들고 block되있는 상태라는걸 뜻한다. block된  프로세스를 깨운다.

Issue->여전히 프로그래머의 실수가 영향을 미친다는 단점을 가지고 있다.

종류: 이진 세마포어(0또는 1만 가질 수 있고 mutex구현을 위해 사용한다), 계수 세마포어(그 외. 다른 프로세스가 접근 못한다는 특성을 이용해서 자원카운팅만 할 때 사용한다)

4)모니터(최종보스)

고급 언어(Java)에서 이 기능을 지원하며, 한번에 하나의 프로세스만 모니터에서 활동하도록 보장해준다. 모니터는 안에 공유변수 넣어두고, 공유변수 접근하는 함수들을 내부에 모아둔다.그리고 자체적으로 활동 가능한 함수는 하나만 되도록 만듬.프로세스가 모니터에 들어가고자 할 때 다른 프로세스가 모니터 내부에 있다면 입장 큐에서 기다려야 한다.

Difference?

세마포어는 스핀락이라 자원낭비가 생기거나, 보완된 방식을 사용해도 block 때문에 문맥교환 비용이 증가하는 반면

모니터는 입장 큐에 대기만 하면 되기 때문에 그 비용이 발생하지 않는다. 또한, 락을 거는 것이 아니기 때문에 자원을 더 쓸 수 있어서 효율적이다

위에서 나왔던 모든 Issue를 처리한 상태로 동기화한 것을 thread safe라고 한다.

//자바의 String 관련 동기,비동기도 알아보자

//생산자,공급자 ..배고픈 철학자 등 건넜음

//세마포어,뮤텍스 구현 한번 해보면 좋을듯

(1)프로세스 생성

What? 프로세스를 생성하는 방법은 부모프로세스가 자식프로세스를 낳는 것이다.

즉, 프로세스를 복제시키는 것이다. 

How? 리눅스에서는 fork()함수를 호출해서 생성한다

code,data,stack+pc까지 복제해서 생성된다.

다음에 exec()함수를 호출해 새로운 프로그램을 올린다.

main부터 코드 실행하다가 fork (시스템콜,운영체제 필요)만나면 프로세스 하나 만들고 아무 일 없듯이 다시 아래 코드 실행한다.자식은 문맥을 복사했기 때문에 부모가 pc가 어디에 멈춰있는지 알아서 그 다음부터 실행한다.

즉, 자식은 if부터 시작한다는 말!(물론 fork반환은 각각 다르게 리턴되서 각자 실행하는 코드분기 다르다)

+cpu는 한번에 하나 프로세스인데 동시에 실행된다고? 스레드가 아닌데?

Why?

1.fork 전의 리소스(간단히 variable이라고 함)를 자식프로세스가 복사해 가지는 것인데, 리소스자체가 많으면 무거워지는 단점이 있지만(그래서 쓰레드가 나온걸로 알고 있습니다), 자식프로세스와 부모프로세스간 또는 자식프로세스간의 통신을 위해서 IPC의 동일한 키값을 갖기 위해서는 이것만큼 쉬운 방법이 없다. 직접 멀티 프로세스 프로그램을 해 보시면 느낄 수 있다고 한다.

2.동일한 프로세스의 여러 인스턴스를 매우 효율적으로 만들 수 있다. 예를 들어 웹 서버에 여러 클라이언트가 동일한 프로세스를 여러 개 제공 할 수 있습니다. 다른 프로세스를 생성하는 비용이 현재 프로세스를 복제하는 비용보다 훨씬 큰 경우는 스레드를 사용하지만 공유자원때문에 오류가 생길 확률이 높아진다.

+exec라는 시스템콜도 있지만 걔는 완전히 새로운 프로세스를 실행하는거다.

exec()라는 함수 호출 뒤의 코드는 실행불가능하다.

+wait()은 자식프세가 끝날때까지 기다려줌. sleep으로 잠들어있는다.기존과 다르게 부모-자식이 원래 프로세스 사이의 모양답게 경쟁이었는데 잠시 협력으로 모양이 변함.

+exit()

자발적 종료:컴파일러가 위치를 잡아줌. 스스로 종료

비자발적: 프세법칙이 부모보다 자식이 먼저 죽는거랬다. 부모가 kill같은 사용자로부터 멈춰짐을 당하면 함수 타고 내려가서 자식들 다 죽이고 자신도 죽음->근데 독립적인데 어케 말함?아, 트리형태로 저장이랬지

혹은 부모가 자식이 자원 너무 많이 써서 죽이는 경우. 프세 우선순위가 부모인갑다..

프로세스 원칙적으로 독립적(지 변수 지만 봄.자신만의 주소공간 가짐).하지만 가끔 협력해야하는 경우 두가지 방법 씀.

1.쉐어드 메모리(면접쓰):물리적으로 변수 공유(커널한테 미리 말해야됨)

2.메시지 통신:필요한 것 커널통해서 메시지로 서로 전달

~스레드간의 협력도 기대해라~

프로세스들 보면 cpu만 주루룩(cpu burst) 쓰는게 많은 프로세스가 있고

IO만 주루룩(IOburst) 쓰는게 더 많은 프로세스가 있는데 이 둘이 교차 됨.

근데 사용자가 더 체감크니 IO프로세스에 좀 더 자원 줌.

그래서 CPU 스케줄러&디스패쳐 필요!

스케줄러는 뭐로 되있니?하드?소프? -> 운체 안에 코드로 있다

스케줄러가 결정을 내리면 디스패쳐가 실질적으로 문맥교환 도와주는거임

그래서 그게 언제 어떻게 적용되는데??

1은 나 cpu더 못써~io로 간다 해서 일어나는거

2는 한 애가 cpu 너무 오래 못쓰게 방지하려고 일어나는거

..

+선점형(뺏아서 바꿈),비선점형 있음(자진반납으로 바꿈)

(2)CPU스케줄링

2가지 이슈로 나뉜다.

1.다음에 누구에게 줄건지 2.강제로 할건지 끝나면 할건지

->현대는 선점형!

5가지로 성능을 평가할 수 있다.

1. cpu사용량:주방장이 놀지않고 일하는 비율

2.대기시간:밥먹는 시간말고 기다리는 시간

3.소요시간:들어왔다가 나가기까지

4.처리한 양:손님 얼마나 받았냐

5.응답시간: 첫 밥 먹기까지 걸린시간.중요. 초반에 단무지라도 주며 기다려야함.

그래서, 이런 종류들이 있다.(어디에 쓰면 좋을지랑 예제 하나 풀어보며 해보자)

1.FCFS: 온 순서대로. 비선점

앞에 긴거오면 다른 프로세스들 입장에서 겪는 대기시간이

길어짐 (waiting시간 증가)

고민해보자..공평성이 중요할 때 좋을듯!티켓팅

그럼 짧은거 먼저 앞으로 땡겨올까?

2.SJF:짧은거 먼저

nonpre,pre 다 있는데 

pre는 스케줄 되있다가도 중간에 더 짧은애 오면 뺏음(참고로 계속 기준은 앞으로 더 써야하는 시간, 즉

남은 시간이다). 뺏는거라 대기 시간은 더 짧아짐

화장실생각! 대기가 치명적일떄!

+근데 더 짧은애 와도 강제없이 기다리면 그게 그냥 fcfs아닌가?

ㄴㄴ!계산해보면 뭔 차인지 안다. 먼저 온 애가 길어서 일단 실행중일때

큐에 쌓여있으면 그 중에서 스케줄링 하는거임.

->하지만 기아현상 발생!긴거는 영원히 못먹을수도..

꼭 대기중에 자기보다 짧은애만 들어오는 경우!

->실제cpu얼마나 잡을지 예측을 못하지만 예측공식(예전거 토대로) 있긴함

ㄴ왜하는거? 이미 계산되있는거 아녔나?->예측하고 들어왔는데 인터럽트 등으로 더 길어졌을때

본래 의도대로 가장 먼저 있는게 아니게 되니..예측을 사용하는 거임 

3.우선순위큐:우선순위 젤 높은 애 한테 줄래. 우선순위는 다양하게 정의.

pre,nonpre.

사실 sjf도 결국 cpu타임이 기준인 우선순위큐임.

->그래서 마찬가지로 aging이라는 현상발생..

오래기다리면 순위높여주는걸로!

4.라운드로빈:가장 현대적!할당시간 세팅해서 줬다가 뺏고 다시 주고...

->공평해서 기아현상 ㄴㄴ!쓸 시간 예측도 불필요!

프세 길면 퀀텀도 길게 줌. 하긴 안그러면 오버헤드 많이 붙어서 더 안좋을듯.

지나치게 퀀텀 짧을때의 예시기도 함.

+스케줄링으로도 모자라서 큐를 여러층으로 분리해서 더 최적화를 했다!

위의 큐일수록 우선순위 주고 아래일수록 안주는데 그렇게하면

starvation 생길 수 있으니 일단 위의 큐에 담기되 퀀텀내에 안끝나면

다음 순위 큐(퀀텀 김)로 밀려남.RR에서도 긴거일수록 퀀텀 길게 줬으니까.

큐마다 적용하는 스케줄링 다르다! 윗큐에 있다는건 빠르게 진행된단거니까

IO버스트가 짧게 자주 있거든, 그래서 거기엔 RR..

+Realtime스케줄러:데드라인 있어서 그 데드라인까지 각각 끝낼 수 있도록 먼저 스케줄링해두는 방식

하드-반드시 지켜야함

소프트-우선순위를 둠

+쓰레드 스케줄러:

로컬-운체가 일단 cpu를 프로세스에게 넘기면 그 뒤로 사용하는건 알아서 하도록 하는거

글로벌-운체가 쓰레드까지 스케줄링에 관여하는 것

지금까지 cpu하나 얘기였는데 여러개면 더 복잡~~

그리고 여기서 내가 더 주목할건

멀티프로세서랑 멀티프로세싱(앞에 위키백과 올린거)이 다르다는거!

멀티프로세싱은 cpu가 하나일수도 있지만 프로세서는 아니다.

성능비교 위해서 실제로 시뮬한다.(과제 있는듯)

참고자료)이화여대 반효경 선생님 KOCW 강의

프로세스: 실행중인 프로그램이다.(윈도우 작업관리자 열면 볼 수 있는 것들!)

 우리가 C하드(보조기억장치-하드,시디)에 저장하듯 하드디스크에 저장되어 있고,

그걸 실행하는 작업대가 ram(주기억장치-램,롬)이다. 컴퓨터의 메모리라고 하면 일반적으로 램을 말한다.

바로 프로그램이 램에서 작업이 되는건 아니고 커널에 의해 레디큐로 갈지 말지 결정해서 레디큐로 갔다가,(이 과정은 커널의 데이터영역에서 이루어진다.그리고 이 커널의 주소공간 또한 램에 있다! https://whereisusb.tistory.com/10 참고, 헷갈렸던거 제대로 나와있음) 디스패쳐를 통해 램에 올라가 cpu에게 처리받는다. 

운영체제가 여러 프로그램을 실행하기 위해 자원(cpu,메모리,네트워크)을 분배한다.  

How??일단 기준보다 방법을 먼저 보자!

초록점이 프로세스 하나다.

CPU가 빠른 속도로 프로세스를 처리하고 있을 때 (해당프로세스상태:running)

정해진 시간이 끝나면(라운드로빈!) 큐의 뒤로 빠지고(해당프로세스상태:ready) 큐의 앞에 있던 프로세스가 시작된다.

혹은, 실행중인 프로세스가 IO처리가 필요하면 블록큐로 넘어가 끝날때까지 대기하게 된다.(해당프로세스상태:blocked)

IO에서 완료되면 cpu에 IO인터럽트를 해서 끝났다고 알려주고 CPU는 커널(깜빡깜빡!)을 통해 운영체제에게 아까 프로세스의 상태를 ready으로 바꿔달라고 요청한다. 우선적으로 처리할 수 있도록!

+프로세스의 상태(프로세스 스케줄링)

 ex) 어떤 프로그램이 사용자 입력을 읽고 처리하는 내용이면 키보드 입력 받기위해 프로세스를 키보드큐에 보내주고, 블락처리한다. 그동안 다른걸 수행하다가 키보드에 있던 애가 끝나면 키보드 컨트롤러가 cpu에게 인터럽트를 걸어서 알리고,cpu는 운영체제에게 프로세스상태를 ready로 바꾸도록해서 자신이 곧 실행할 수 있게 한다.

+공유데이터(면접질문!): IO 디바이스 서비스 기다리느라 block되는 경우 말고 소프트웨어 서비스 기다리느라 block되는 경우도 있다.

ex) 한 프로세스가 접근하는 도중에 cpu를 뺏겨서 다른 프로세스가 접근하면 일관성이 깨지므로 데이터를 막아둔 경우.

프로세스 실행) code가 stack에 쌓인다. 그 과정에서 data를 참조한다.

+JRE로 따지면 code,data영역이 코드와 static저장하는 method 영역 역할이고

stack은 jvm stack 역할이고 나와있진 않지만 heap은 그대로 heap역할을 하는듯하다.

인터럽트 등의 이유로 다른 프로세스로 문맥교환) 커널에게 요청(시스템콜)을 한다. pc의 주소는 프로세스주소공간이 아닌 커널 주소공간을 가리키게 된다.

운영체제-커널 동작) 프로세스 실행과정과 마찬가지이다. 다만, 커널은 자신의 data영역에 큐 자료구조를 만들어서 프로세스 상태를 변화시키며 순서를 바꾼다.

이때!!! 커널은 모든 프로세스가 접근할 수 있기 때문에 동시에 접근하는 경우를 막기 위해서

커널스택을 프로세스가 나눠가진다. 

+그리고 위의 큐들이 모두 커널의 주소공간-데이터 영역에 있기 때문에

운영체제가 프로세스 스케줄링이 가능한 것

프로세스가 cpu를 뺏겼다가 다시 cpu를 되찾을 때 처음부터 다시 하는게 아니라 하던 곳에서 하려면 그 문맥 (레지스터 상황,코드 위치)을 기억해둬야 한다. 즉, cpu를 뺏기기 전에 해당 프로세스의 정보들을 자신의 PCB에 저장을 해두고 나중에 되찾을 때 cpu하드웨어에 그때의 상황을 복구를 하는 작업을 운영체제가 해준다.

+반드시 인터럽트나 시스템콜이 발생한다고 context switch가 발생하는건 아니다. 예를 들어서, 프로세스 A->인터럽트 발생(프로세스A를 위한)->프로세스A 의 상황이라면 프로세스가 바뀌는게 아니기 때문에 context switch가 발생하지 않는다.  문맥교환은 프로세스가 바뀔때 정보를 저장하는게 목적임을 명심하자!

프로그램 시작전 / Job 스케줄러 / 장기)

메모리에 프로세스 올라가서 ready되기 직전에 올라와도 될지 안될지를 결정.

메모리에 몇 개 올려놓을건지를 기준으로 판단한다. degree of Muliprocess와 관련있다.

시작후 / Swaper / 중기)

메모리에 프로세스가 너무 많이 올라가있으면 몇 개를 쫓아냄.

시작후/ CPU스케줄러 / 단기)

굉장히 빨라야하고, 다음에 어떤 프로세스를 running할지 결정.

+중기 스케줄러가 확실히 성능을 개선시켜준다. 메모리를 뺏는거니까!

+Suspend상태는 사용자가 프로그램을 직접 중지시킨 경우고, 이땐 메모리에서 나와 디스크로 swap out된다.

+프로세스를 너무 적게 올려놔도 안좋은 이유? 한 프로세스 IO로 블락된 동안 cpu놀고 있게 되니까.

스레드: 코드를 나눠서 처리할 수 있는 부분은 병렬적으로 따로 처리하는 것

Why?장점이 뭐길래?

->웹화면 객체 띄워지는걸 다 받아서 출력하는거보다 따로 처리해서 오는대로 보여주면 응답성 향상!

->0*10이 cpu하나면 하나하나 해야하지만 각각 나눠서 계산하고 나중에 합하는 방식도 가능

->일부 변수를 공유하기 때문에 프로세스 여러개 있는 것보다 단일 프로세스에 다중스레드 방식이 메모리 절약 됨.

어떻게 메모리를 절약하냐?

프로세스 하나->PCB 하나->프로세스상태값, 프로세스id, 메모리제한, pc, 레지스터 위치정보.

ㄴPCB는 운영체제(커널)는 프로세스들을 관리하기 위해 자신만의 메모리를 가진 것이다.

'PC와 레지스터만'  스레드들이 각각 나눠저장하고 (코드를 쪼개서 따로 풀거니까 그 코드 위치도 따로 알고 있어야 됨)

나머지는 공유한다~~아래 그림을 참고하자

왼쪽과 오른쪽 그림을 잘 보자. 프로세스마다 주소공간을 가지고 있다.(그걸 읽으면서 동작하니까)

각 프로세스는 커널스택과 PCB 또한 나누어가진다.(정확히는 운영체제가 관리하기 위해서 프로세스별로 있는거임)

왜냐하면, 다중스레드 처리를 위해서 프로세스 PCB의 PC,레지스터를 스레드별로 구분해서 가져야 하기 때문이다.

실행할 코드를 push pop할 공간을 위해 프로세스 주소공간의 스택영역도 스레드별로 구분되어 있다.

결국 프로세스와 스레드가 공유하는 것은 data영역과 code영역이라는 것이다.(커널주소공간은 os를 위한 것이니 프로세스 관점으로 보자면)

공부한걸 바탕으로 아래 그림을 이해해보자.

공룡책 문제 빨리 풀어보자~~

What? 알고리즘의 예상되는 실행 시간을 표현한 것

타이머로 실제 시간을 측정하는게 아니라, 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇 번인지를 

n(입력데이터 크기)에 관한 식으로 나타낸다. O(n)

How?

ex) 삽입정렬 알고리즘 : 정렬된 부분집합 A와 정렬되지 않은 부분집합 B로 나누어, B의 한 요소를 꺼내 A에 들어갈 위치를 찾아서 끼워넣는 방법. 반복하여 B가 공집합이 되면 정렬이 완성된다. 

시간복잡도를 구할 때는 비교연산(<,>,<=,>=), 교환연산(=)을 중심으로 구하면 된다.

void Insertion(int n) {
	int key;
	for (int i = 1; i <= n - 1; i++) {  //(1)외부루프는 n-1회 
		key = a[i];    //(2)외부루프에 의해 교환연산이 n-1회 일어남
		int j;
		for (j = i - 1; j >= 0; j--) {  //(3)내부루프는 최대 i회 
			if (a[j] >key){       //(4)외부르프x내부루프에 의해 비교연산 최대 (n-1)+(n-2)...1=n(n-1)/2회 일어남.<-등차수열의 합
				a[j + 1] = a[j]; //(4-1)조건에 의해 교환연산이 최대 n(n-1)/2회 
            }  
			else{
				break;  
            }
		}
		a[j + 1] = key;    //(5)외부루프에 의해 교환연산이 n-1회 일어남
	}
}

• 최악의 경우(역순으로 정렬되있음) =

      1*(n-1) + 2*(n(n-1)/2) + 1*(n-1) = n^2+n-2 =   O(n^2) 

         (2)           (4,4-1)          (5)

• 최선의 경우(이미 정렬되있음) =  

      1*(n-1) + (n-1) + 1*(n-1) = 3n-3 = O(n)

         (2)        (4)        (5)  

!!보통 못해도 이 정도의 성능을 보장한다는 의미로, 최악의 시간복잡도를 많이 사용한다!!

!!시간복잡도는 n의 최고 차수만 나타낸다!! 

                                Try! 실제로 횟수를 확인해보았다.(각 비교,교환 실행문마다 카운트 함..(n=5))

+추가 예제 

#include<iostream>
using namespace std;
int main() {
	int n = 5;
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt++;
		}
	}

	cout << cnt << endl;   //output: 25
    
    //앞서 말했듯이, 반복문을 중심으로 계산하면 되므로 시간복잡도는 n*n= n^2이 된다.

	cnt = 0;

	int i = 0,j=0;
	for (; i < n; i++) {
		for (; j < n; j++) {
			cnt++;
		}
	}
	cout << cnt << endl;   //output: 5
    //하지만, 반복문이 중첩되어 있더라도 언제나 두 반복문 범위의 곱은 아니라는 것에 유의하자.
    //위의 경우, 범위가 따로 놀기 때문에 cnt++가 포함된 루프만 생각해서 시간복잡도는 최대 n이다
	
    return 0;
}

다양한 시간복잡도

                                                        !! 전산학에서 log의 밑은 2이다 !!

그래프를 보면, 지수승으로 커지면 데이터의 양이 조금만 많아져도 그 연산량이 기하급수적으로 증가하는 것을 확인할 수 있다.  여기서 우리가 알고리즘을 짤 때, 시간복잡도를 고려해야 하는 이유가 드러난다. 

시간복잡도를 고려하는 이유

ex) 우리나라 인구 5000만명중에서 한 사람을 조회하는 알고리즘 2개가 있다. 

A알고리즘: O(log n)

B알고리즘: O(n^2)

->A알고리즘은 25번, B알고리즘은 2500000000000000번의 연산을 수행한다. 

...더보기

                       Try! 재미로 내 컴퓨터에서 1억번의 연산을 수행하고 시간을 측정해보았다. ㅎㅎ

 

 

 

즉 1억번에 0.2초 정도 걸렸다. 실행할 때마다 0.2~0.4초까지 나오더라..

참고로 실행환경은 인텔® 코어™ i5-7200U 프로세서(최고 3.10 GHz) 기준이다.

1Ghz는 1초에 10^9(10억)개의 단계를 처리할 수 있다고 한다.

그럼에도 저 정도의 시간이 나온건..다른 변수가 확실히 많다는 뜻..?

 

->A알고리즘은 1초도 안되는 시간이 걸린다. 

->B알고리즘은 120일 정도 걸린다..

하드웨어를 발전 속도가 매우 빠르기 때문에(무어의 법칙: 1년만에 반도체 집적률이 2배씩..)

소프트웨어의 발전 속도가 상대적으로 느리게 느껴지긴 하지만...

그럼에도 우리는 시간이란 소중한 자원을 낭비하지 않기 위해서 언제나 시간복잡도를 낮추기 위한 노력을 한다.

이러한 노력을 최적화라고 부른다.

Tip

추가로 알고리즘 문제를 풀 때 시간복잡도를 대략적으로 맞추는 방법을 소개하려 한다.

(백준,swea를 이제 막 풀기 시작한 분들을 위해서 쓴 글입니다! 참고해주세요ㅎㅎ)

여기서 시간제한 1초가 의미하는 것은, 내 코드를 실행했을 때 실행시간이 1초 내여야한다는 것을 뜻한다.

대부분의 환경에서 1억번 연산이 1초 정도 걸리기 때문에,

내 코드에 제일 큰 테스트케이스를 돌려도 연산이 1억번 내여야만 통과가 된다는 것이다.

그러므로, 문제를 풀기 전에 시간 제한과 입력 데이터의 수를 확인하고 나서

어느정도의 시간복잡도로 코드를 짜야겠다고 계획을 하고 코딩을 하는 것이 좋다. 

1. 시간 제한, 최대 입력 데이터의 크기를 확인하고 내가 짜야하는 코드의 시간복잡도를 생각한다.

-> 데이터의 크기가 10^8개일 떄, 시간복잡도가 n, log n 이어야지 1억번의 연산 내로 실행된다.

-> 데이터의 크기가 10^6개일 때, 시간복잡도가 nlog n이어야지 1억번의 연산 내로 실행된다.

.....

2.그에 맞춰서 코딩을 한다

3.가장 큰 테스트 케이스를 넣어본다.

4.출력 시간을 체감해본다 or 프로파일링 기능을 사용해서 측정해본다 or <time.h>를 추가해서 시간을 출력해본다

프로그램을 실행했을 때, 바로 출력값을 확인할 수 있다면 대부분 1초 내에 실행되는 코드이다.

하지만 조금 몇 초 기다려야지 값이 나온다면?? 코드 제출을 하면 '시간초과'를 볼 확률이 높다ㅎ

물론 콘솔에 뜨는 시간으로 추측하기엔 꽤나 부정확하지만.. 알고리즘을 잘못 짰을 때 가장 먼저 드러나는 부분

아닌가 싶다. 만약 이런 경우, 자신의 코드를 한번 되돌아보자!!!

+난 정말 제대로 짰는데 시간초과가 뜨거나 좀 느린 것 같다?싶으면 다음 경우를 확인해보자. 

1)디버깅 / 릴리즈 모드:

디버깅모드는 추적할 수 있는 정보가 실행파일 안에 들어가는 모드이다. 반면에 릴리즈모드는 프로그램을

배포하기 위해 컴파일하는 모드이다. 자질구레한 정보는 제외하기 때문에 컴파일 속도가 빠르다.

2) cin, cout으로 입출력을 반복:

cin, cout 보단 scanf,printf가 훨씬 빠르다. 

나는 집합의 표현 문제에서 이걸 경험했다..cin을 쓰면 시간초과가 뜬다.

3)그 외의 모든 반복문들..

초기화가 필요하면 memset을 사용하는 경우가 많지만, 만약 직접 이중포문으로 초기화를 한다면 이 부분이 시간을 많이 잡아먹을 수도 있다. 주요 알고리즘이 아니라고 대충 넘어간다면 안된다! 또한, 범위의 끝까지 갈 필요가 없는 반복문인데 끝까지 가게 만든 경우도 시간초과가 발생한다. 이런 경우 적절히 break를 걸어줘야 한다. 

나는 벽돌깨기와 보호필름에서 이런 문제를 경험했다. 

처음 시간복잡도에 대해 생각해보기에는 로마 숫자 만들기가 좋은 것 같다.

아직 많이 부족하기 때문에 틀린 부분이 있을수도 있어요..

댓글로 알려주시면 정말 감사할 것 같습니다ㅎㅎ

학교에서 이산수학 책으로만 시간복잡도 몇 번 계산해보고,

코딩하면서 써먹으려니 뜬구름 잡는 것 같은 기분을 느낀 적이 있습니다. 

조금 야매스럽기도 하지만! 저같은 초보자 분들에게 조금이나마 도움이 되었으면ㅎㅎㅎ