도전북

함수

• 특징
  • 이게 바로 함수

  • #include <stdio.h>
    
    int sum(int x, int y)
    {
    	return x + y;
    }
    
    void main()
    {
    	int result = sum(1, 2);
    	printf("%d\n", result);
    }

  • C는 절차지향언어이므로, 위에서 아래로 차례대로 함수를 작성해 줘야 함 (혹은 main 아래에서 사용했을 경우 위에서 선언해 주어야 함)
  • 함수에서는 인자를 전달할 때 복사해서 사용함 (전달해주는 원래 변수는 함수에서 수정 불가, 이때 08. 포인터 로 메모리의 주소를 넘겨주면 변수 값을 바로 수정 가능

변수의 종류

• 지역변수 : 특정 함수 안에서만 쓸 수 있는 변수
  • 전역변수와 지역변수의 이름이 같은 경우, 지역변수에 우선 접근
• 전역변수 : 어디서나 사용 가능

  • #include <stdio.h>
    
    int global = 10;
    
    void globalTest()
    {
    	//여기서도 사용 가능
    }
    
    int main()
    {
    	//여기서도 사용 가능
    }

조건/분기

• if, else if

if(100 < num)
{
	printf("num은 100보다 큽니다.");
}

• break : 반복문을 빠져나가기
• continue : 바로 아래 코드는 무시하고 다음 반복문을 실행
• switch

void main()
{
	int input;	
	scanf("%d", &input);
	
	switch(input)
	{
		case 1:
			printf("1을 선택하셨습니다.\\n");
			break;
		case 2:
			printf("2를 선택하셨습니다.\\n");
			break;
		case 3:
			printf("3을 선택하셨습니다.\\n");
			break;
		case 4:
			printf("4를 선택하셨습니다.\\n");
			break;
		case 5:
			printf("5를 선택하셨습니다.\\n");
			break;
		default:
			printf("범위에 맞지 않는 값입니다.\\n");
			break;
	}
	
	return 0;
}

반복문

for

• 반복할 내용의 코드가 한 줄이라면 들여쓰기로 처리해도 되지만, 한 줄보다 많다면 중괄호로 묶을 것

int main()
{
	for(int i=0; i<5; i++)  // 초기식; 조건식; 증감식
	{
		printf("반복문!\\n"); 
	}
	return 0;
}

while

int main()
{
	int i = 0;    // 초기식(초기화)
	while(i<5)    // 조건식
	{
		printf("While 조건문!\\n");
		i++;       // 증감식
	}

	return 0;
}

do while

• do(먼저 한 번 코드를 실행)한 후 while(조건 확인 및 반복)

int main()
{
	int i = 0;
	do
	{
		printf("Hello, goorm!");    // 적어도 한 번 실행될 내용
	} while(1<i);                 // 조건식 (여기서는 거짓이므로 do가 반복 실행되지 않음)

	return 0;
}

이중 반복문

int main()
{
	for (int i = 1; i <= 3; i++)
	{
		printf("첫 번째 반복문 : %d\\n", i);
		for (int j = 1; j <= 5; j++)
			printf("     두 번째 반복문 : %d\\n", j);
	}
	return 0;
}

연산자

• 증감 연산자
  • 전위 연산자 : 값을 증감한 후 코드가 실행
  • 후위 연산자 : 연산자가 사용된 코드를 먼저 실행한 후 값을 증감 (다음 줄에서 값이 증감)

  // 전위 연산자
  printf("%d\\n", ++a); // a가 1 증가됨
  printf("%d", a); // 1 증가된 a가 출력
  
  // 후위 연산자
  printf("%d\\n", a--); // a가 출력된 다음에 1 감소
  printf("%d", a); // 1 감소된 a가 출력
  

  • 논리 연산자
    • && : AND, 논리곱, 양쪽이 둘 다 참(1)이어야 결과값이 참(1)이 됨
    • || : OR, 논리합, 양쪽 중 하나만 참(1)이어도 결과값이 참(1)이 됨
  • 비트 연산자
    • 참고자료
    비트 연산자 - 한 눈에 끝내는 C언어 기초
    • & : AND 연산
    • | : OR 연산
    • ^ : XOR 연산
    • ~ : 모든 비트 반전, NOT 연산
    • << : 지정한 수만큼 비트 열을 왼쪽으로 이동
    • >> : 지정한 수만큼 비트 열을 오른쪽으로 이동

출력

• printf
• 정수/실수 출력
  • 정수 %d : char, int 등
  • 실수 %f : float 등
  • 문자 %c : char

float

const double dNum = 1234.56789;
 
printf("%.0f\\n", dNum);   // 1235
printf("%.1f\\n", dNum);   // 1234.6
printf("%.2f\\n", dNum);   // 1234.57
printf("%.3f\\n", dNum);   // 1234.568

입력

• scanf
• 변수 앞에 &를 써주어야 함 (주소값 지정)

scanf("%d", &goorm.age);

자료형 종류

변수

• 초기화 : 변수를 선언함과 동시에 값을 대입

int i = 3;
float f = 3.14f;

상수

• 변수와 달리, 값을 영원히 바꿀 수 없는 수
• 자료형 앞에 const를 붙이면 됨

const double PI = 3.1415;

01장 CPU
02장 운영체제 - 프로세스와 스레드
03장 운영체제 - 메모리
04장 프로그래밍 언어, 컴파일러
05장 변수, 정수, 실수, 문자열
06장 함수
07장 객체지향
08장 클래스
09장 자료구조 1
10장 자료구조 2
11장 알고리즘
12장 네트워크
13장 데이터베이스

1. 메모리 계층

• 메모리 계층의 특징
  • 전달되는 데이터가 아래쪽에 있을 경우, CPU에 도달하려면 위에 있는 모든 계층을 거쳐야 함

    • 

  • 단계별 접근이 비효율적일 것 같은데 이게 더 빠른 이유 : 지역성
• 지역성
  • 시간적 지역성 : 한 번 접근한 데이터는 가까운 시간 내에 다시 접근할 확률이 높음
  • 공간적 지역성 : 이번에 접근할 데이터가 이전에 접근했던 데이터 근처에 있을 확률이 높음 (예를 들어 배열...)
  • (이런 특성 때문에 메모리 계층을 저렇게 구성한 것임)
• CPU가 필요한 데이터가 캐시에 있으면 캐시 히트, 없으면 캐시 미스 (캐시 히트가 잘 일어나도록 고려해서 작성한 코드를 캐시 프렌들리 코드라고 함)
• 메모리 저장 방식
  • 빅 엔디언(big-endian) : 숫자를 1, 2, 3, 4 순서대로 저장하는 방식
  • 리틀 엔디언(little-endian) : 숫자를 4, 3, 2, 1 역순으로 저장하는 방식

2. 가상 메모리

• 고정된 메모리 주소를 사용하기에는 물리 메모리가 너무 작아서 도입
  • 하드 디스크를 메인 메모리(RAM)처럼 사용할 수 있게 됨 (메인 메모리가 하드 디스크의 캐시 메모리 역할)
  • 각 프로세스(실행된 프로그램)가 독립된 가상 주소 공간을 가짐
  • 프로세스의 모든 데이터를 메인 메모리로 적재하지 않고 필요한 시점에만 적재
    • 예를 들어, 32bit 시스템에서는 프로세스가 실행되면 4GB(2^32) 메모리 주소를 할당 받는다.
• 주요 키워드
  
  • 주소
    • 논리 주소(logical address) : 가상메모리의 주소
    • 물리 주소(physical address): 실제 주소 (메인 메모리의 메모리 주소)
  • MMU(Memory Management Unit) : 논리 주소를 물리 주소로 젼환해 메인 메모리를 사용할 수 있게 해주는(런타임에 대응시키는) 하드웨어, CPU 내부에 있음

2-1. 가상 메모리 관리 기법

• 현재 운영체제는 대부분 두 가지를 함께 사용함 (segmentation on with paging)

2-2. 페이징

가상 주소 공간과 메인 메모리를 일정한 크기로 쪼개어 다룸

• 페이지(page) : 일정한 크기로 나눈 가상 메모리의 한 부분
  • VPN(Virtual Page Number) : 페이지 순서를 나타내는 비트 (페이지 넘버)
• 프레임(frame) : 일정한 크기로 나눈 물리 메모리(RAM)의 한 부분
  
  • PPN(Physical Page Number) : 프레임 순서를 나타내는 비트 (프레임 넘버)
• 요구 페이징(demand paging) : 가상 메모리를 구현하는 방법. 프로세스를 실행할 때 모든 페이지를 프레임에 매핑하는 것이 아니라, 필요한 페이지만 메인 메모리에 올려 실행하는 것
  • 프리페어링(preparing) : 프로세스가 처음 실행될 때 운영체제는 페이지 테이블을 메인 메모리에 만들고 실행에 필요한 페이지만 먼저 프레임에 매핑하는 것
• 페이지 테이블 : 하단 설명
• 페이지 폴트(page fault) : 요청한 페이지가 메인 메모리에 없을 때 발생, 하드디스크에서 가져와야 함
  • 이때 메인 메모리가 이미 페이지로 꽉 차 있다면 교체 알고리즘에 따라 페이지를 내린다. (가장 먼저 들어온, 가장 오래 전에 사용한, 가장 적게 사용한 페이지)
  • 페이지 폴트가 자주 일어나면 데이터를 읽어 오는 속도 때문에 성능이 떨어지므로, 페이지 폴트가 일어날 확률을 줄이기 위해 지역성을 고려하면서 프로그래밍해야 함 (자료 구조를 배열로 변경하거나, 다이내믹 힙을 사용하는 등)
• 변환 색인 버퍼(Translation Lookaside Buffer, TLB) : 페이지 테이블을 캐싱해 주는 (일종의) 캐시 메모리 (얘도 TLB 히트 남) 

2-2-1. 페이지 테이블

• 어떤 프로세스의 VPN, PPN, 상태(contral bit) 등을 저장하는 테이블
  • 테이블은 메인 메모리에 저장됨
  • CPU에는 페이지 테이블의 시작 주소(PTBR, Page Table Base Assress)를 가리키는 레지스터가 있음
  • MMU가 이것을 참조하여 논리 주소를 물리 주소로 바꿈
• 유효 비트(Vaild bit) : 프레임이 실제 메모리에 있는지(1), 하드디스크에 있는지(0)

2-3. 프로세스와 메모리

가상 메모리가 공간을 할당받으면 각 영역으로 나누어짐

---- 가상 메모리 공간 ----
커널 영역 OS가 사용하는 영역
유저 영역 프로그램 사용 영역	코드 세그먼트 함수, 클래스 등이 저장됨 (인스트럭션이 들어감)
	데이터 세그먼트 전역 변수가 저장됨 (main 밖에 있는 변수)
	힙 세그먼트 자유롭게 메모리를 할당하고 해제하는 공간 (동적 할당) malloc 하면 원하는 사이즈만큼 힙에 할당 (컴파일할 때 size를 알 수 없는 경우 사용) 동적 할당 후 해제하지 않을 경우 메모리 누수가 일어남 메모리 단편화 : 그때그때 할당할 공간을 찾기 때문에 공간이 쪼개짐, 지역성의 원리가 적용되지 않아 캐시 미스/페이지 폴트 확률이 높아짐 할당할 공간을 찾아야 하므로 느림
	스택 함수에서 사용할 지역 변수 등이 쌓이는 공간 최대 크기가 정해져 있음 함수 호출(콜 스택)에 따라 아래 이미지처럼 스택 프레임이 쌓임

각 세그먼트 사용 예시

#include <iostream> 

// ----- CODE ----- // 
int add(int a, int b){
		return a + b; } 

int sub(int a, int b){ 
		return a-b; } 

// ---- DATA ----- // 
int globalX = 10; 

int main(void){ 
		// ---- STACK ----- // 
		int localX = 20; 

		// ---- HEAP ----- // 
		int *heapX = (int*)malloc(sizeof(int)); 
		*heapX = 30; 
		free(heapX); 

		return 0; 
}

1. 운영체제

1-1. 운영체제가 하는 일

운영체제는 하드웨어와 소프트웨어를 관리하기 위해 만들어졌다. OS 규격과 관리 목적은 제품에 따라 다르지만 대부분 아래 기능을 수행한다.

• 메모리, CPU, 저장장치, 네트워크 등을 관리
• 파일 시스템
• 프로세스 실행 관리
• 하드웨어 추상화 계층 (HAL)
  • 프로그래머가 하드웨어에 신경쓰지 않게 해주는 것
  • 운영체제와 운영체제가 컴퓨터 장치를 사용하기 위한 드라이버 사이에서, 사용자가 필요한 동작들에 대하여 표준적인 접근 방법을 제공하는 것 

1-2. 운영체제의 종류

• 유닉스: 벨 연구소
  • macOS, iOS
• 리눅스: 대학원생 리누스 토르발스
  • 안드로이드
• 윈도우: MS
• Mac OS: apple

1-3. 운영체제의 구조

• 커널
  • 운영체제의 핵심. 항상 메모리에 상주
  • Linux의 경우 OS가 항상 메모리에 상주하기 때문에 운영체제와 커널이 같다
• System Call
  
  • 운영체제의 기능을 사용할 수 있게 해주는 API
  • 커널 모드, 유저모드
    • 보안을 위해 존재
    • 프로세스는 유저 모드와 커널 모드 두 가지 모드로 작동됨.
    • 시스템콜이 이뤄지면 커널 모드로 전환. 할 일이 끝나면 다시 유저 모드로 돌아감
• Shell 
  • 커널과 사용자 사이에 끼어서 명령을 해석하고 처리 결과를 보여주는 프로그램
  • 명령줄 셸 : cmd, powershell, sh, bash
  • 그래픽 셸 : 윈도우 탐색기

2. 프로세스

2-1. 프로그램과 프로세스

2-2. 프로세스의 상태 (생명 주기)

• 생명 주기
  • Created : 막 생성해서 실행 준비를 하는 단계, 실행 중인 프로세스와 우선순위를 비교
  • Waiting : 순서에 맞춰 실행을 기다리는 상태
  • Running : 운영체제로 부터 CPU를 할당 받아 실행되고 있는 상태 (순서에 맞춰 실행을 기다리는 상태)
    • Dispatch 디스패치 : 다음으로 실행될 프로세스에 CPU를 할당하는 것
    • Preemption 프리엠션 : 실행 중이던 프로세스에서 CPU를 해제하는 것
  • Blocked : I/O(읽고 쓰기처럼 디스크에서 정보를 불러오는 아주 간단한 일) 같이 오랜 시간 걸리는 작업에 들어간 경우 해당 상태로 변경됨 (I/O 작업이 끝나기 전까지 실행 불가능, 이때 실행 가능 상태의 프로세스 중 하나가 CPU를 할당받음)
  • Termiated : 종료, 소멸

2-3. 스케줄링

디스패치와 프리엠션이 일어날 때 운영체제가 어떤 프로세스에게 CPU를 할당할까?

• 스케줄링 : 운영체제가 여러 프로세스의 CPU 할당 순서를 결정하는 것
• 스케줄러 : 스케줄링을 하는 프로그램
• 스케줄링 종류
  • 선점형 : 어떤 프로세스가 실행 중에 있어도 스케줄러가 강제로 프로세스를 중지하고 다른 프로세스를 실행(CPU에 할당)
  • 비선점형 : 실행 중인 프로세스가 종료되거나, I/O 작업에 들어가거나, CPU를 반환하기 전까지는 계속해서 실행됨. 우선순위가 높은 프로세스가 생성되어도 실행 중인 프로세스가 자발적으로 CPU를 양보하지 않으면 사용하지 못함
• 스케줄링 알고리즘의 종류 (제품에 따라 다름)
  • 우선순위(Priority) : 우선순위를 매겨 높은 우선 순위부터 실행 선점형 
    • 기아 상태(starvation) : 낮은 우선순위가 계속 일을 하지 못하는 상황
    • 에이징(aging) : 오랫동안 실행되지 못한 프로세스의 우선순위를 높여 기아 상태 방지
  • 라운드로빈(Round-Robin) : 일정 시간동안 순서대로 할당 비선점형
    • 일정시간 : 타임 슬라이스(time slice) 또는 퀀텀(quantum)이라고 불림
  • FCFS(First Come First Served) : 실행 가능 상태에 먼저 들어온 순서대로 처리 비선점형
  • SJF(Shortest Job First) : 평균 대기시간을 최소화하기 위해 CPU 할당 시간이 가장 짧을 것으로 예측되는 것부터 처리 선점형&비선점형
    • 단점 : 할당 시간이 긴 프로세스는 계속해서 실행되지 않는 기아 상태에 빠질 수 있고, CPU의 실제 할당 시간을 알 수 없으니 예측에 의존해야 함

2-4. 컨텍스트 스위칭

• 컨텍스트 스위칭 : 실행되고 있는 프로세스가 변경될 때(디스패치, 프리엠션이 일어날 때) CPU에 프로세스를 실행하기 위한 정보(PCB)가 교체되는 것
  
  • 이때 현재 CPU의 레지스터 값들을 전환, 컨텍스트 스위칭이 일어날 때 기존 프로세스의 CPU 상태 정보는 PCB에 기록해 둠
    • CPU의 상태 정보 : 다음에 CPU를 점유하면 실행할 다음 인스트럭션의 위치(프로그램 카운터 정보), 현재 쌓인 스택 프레임의 정보(스택 포인터와 프레임 포인터의 정보), 현재 연산 중인 데이터가 저장된 레지스터 값(범용 레지스터 정보) 등
  • 잦은 컨텍스트 스위칭은 성능을 떨어트림
• PCB(Process Control Block) : 프로세스의 CPU 상태와 프로세스의 상태를 저장해 둔 메모리 블록
  • 프로세스의 상태 : 현재 실행 중인 인스트럭션, 스택 프레임, 프로그램 카운터 값, 스택 포인터와 프레임 포인터와 범용 레지스터의 값
  • 이 정보는 커널에 위치함 (OS가 사용하는 영역)

3. 멀티 스레드

3-1. 멀티 프로세스와 멀티 스레드

	멀티 프로세스	멀티 스레드
그게 뭐죠?	프로세스 : 알잖아 멀티 프로세스 : 프로세스 여러 개를 동시에 실행하는 것	스레드 : 프로세스 안의 실행 흐름 단위로, 스레드 단위로 CPU를 할당받을 수 있다. 멀티 스레드 : 스레드 여러 개를 동시에 실행하는 것
가진 것	PCB	TCB (PCB랑 거의 같음)
이미지
통신 방법	소켓, 메시지 큐, 파이프	공유되는 메모리 공간 (ex. 전역변수)
장점	독립된 구조로 안정성이 있음	컨텍스트 스위칭이 단순해 성능이 좋아짐
단점	프로세스 컨텍스트 스위칭이 일어나 성능이 떨어짐 (통신 비용이 큼)	자원을 공유할 때 동기화 문제 발생 가능성이 있음 (아래에서 설명할 공유 자원 문제)

3-2. 멀티 스레딩을 Python으로 구현하기

아래는 공유 자원 문제(동기화 문제)가 일어나는 코드이다.

# 공유 자원 문제가 일어나는 코드

import threading

g_count = 0

def thread_main():
    global g_count
    for i in range(1000000):
        g_count += 1

threads = [ ]
for i in range(50): #3
    th = threading.Thread(target = thread_main)
    threads.append(th)

for th in threads:
    th.start()

for th in threads:
    th.join()

print('g_count :{:,}'.format(g_count))

이러한 문제가 발생하는 이유는?

위의 경우 단순히 변수에 1을 더하는 작업이지만 instruction 기준으로 보면 여러 단계. 어느 시점에 컨텍스트 스위칭이 일어나는지에 따라 결과가 잘못 나온다.

• 경쟁 조건(race condition) : 스레드 여러 개가 공유 자원에 동시에 접근하는 것
• 임계 영역(critical section) : 공유 자원에 접근해 변경을 시도하는 코드 영역

3-3. 공유 자원 문제(동기화 문제) 해결

문제를 해결하기 위해, 공유 자원에 여러 스레드가 동시에 접근하지 못하도록 제어해야 한다.

# 문제 해결 코드 

import threading

g_count = 0

def thread_main():
    global g_count
    lock.acquire()    
    for i in range(1000000):
        g_count += 1
    lock.release()

lock = threading.Lock()
threads = [ ]
for i in range(50): 
    th = threading.Thread(target = thread_main)
    threads.append(th)

for th in threads:
    th.start()

for th in threads:
    th.join()

print('g_count :{:,}'.format(g_count))

이것을 상호 배제라고 한다.

• 뮤텍스 (상호배제, Mutual Exclusion = Mutex)
  • 스레드 하나가 공유 자원을 이용하는 동안 다른 스레드가 접근하지 못하게 막는 것
  • 1칸 짜리 화장실
• 세마포어 (더 좋은 방법, Semaphore)
  • 공유 자원에 최대 접근 가능한 스레드 개수를 제한하는 것
  • 자원에 접근 중인 스레드를 count해서 구현
  • 최대 접근 가능한 스레드 개수를 1로 하면 뮤텍스가 됨
    • 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없음
  • N칸 짜리 화장실

3-4. 교착 상태 (DeadLock)

둘 이상의 스레드가 다른 스레드가 점유하고 있는 자원을 서로 기다릴 때와 같이 무한 대기에 빠지는 상황