라비린스6_개발 블로그

목차

4주차 범위

Chapter 09: 운영체제 시작하기
Chapter 10: 프로세스와 스레드
Chapter 11: CPU 스케줄링

이번주차부터 운영체제네요

CPU 스케줄링 저거 어려웠던거 같은데 최대한 꼼꼼히 봐야겠네요

학습 내용 정리

Chapter 09: 운영체제 시작하기

운영체제 : 사용자와 하드웨어 사이에 인터페이스 역할을 하는 소프트웨어

운영체제는 하드웨어와 응용프로그램 사이에 동작하며 자원을 관리

커널 영역과 사용자 영역

메모리 내 공간은 커널 영역과 사용자 영역으로 나뉨

• 커널 영역: 운영체제가 적재되는 영역
• 사용자 영역: 프로그램이 동작하기 위해 사용되는 메모리공간으로 스택영역, 힙 영역, 데이터 영역, 코드 영역으로 이루어짐

사용자 인터페이스 (UI): 운영체제가 제공하는 서비스 중 하나(커널에는 포함안됨)

UI 의 종류

• CLI(Command Line Interface): 입출력이 텍스트로 이루어지는 인터페이스 (cmd, dos 등)
• GUI(Graphic User Interface): 그래픽 환경의 인터페이스
• NUI(Natural User Interface) : 자연스러운 움직임을 통해 기기를 조작하는 인터페이스

이중 모드: 운영체제가 응용 프로그램이 자원에 접근하는 과정을 요청받으면 대신 수행

커널 모드: 커널 영역 코드 실행 가능
사용자 모드: 커널 영역 코드 실행 불가

커널 모드에서는 자원에 접근이 가능하다

시스템 콜: 프로그램이 자원에 접근 하기 위해서는 운영 체제에 요청을 보냄
시스템 콜을 통해 커널 모드로 전환되면 운영체제 서비스를 제공 받을 수 있음
시스템 호출은 소프트웨어 인터럽트임

시스템 콜 작동 과정
(사용자모드)시스템 호출을 발생 시킴 -> (커널모드)운영체제 코드 실행 -> (사용자모드) 시스템 호출 복귀

운영 체제의 핵심 서비스

• 프로세스 관리
• 자원접근 및 할당
• 파일 시스템 관리

CPU 스케줄링: 하나의 CPU는 한번에 하나의 프로세스만 할당 가능하므로 어떤 프로세스 부터, 얼마나 오래 할당할지 스케줄링 필요

가상머신: 소프트웨어적으로 만들어낸 가상컴퓨터
하이퍼바이저 모드: 가상머신을 위한 모드

가상 머신은 대표적으로 VMWare, Virtual Box 등이 있습니다. 

Chapter 10: 프로세스와 스레드

프로세스: 메모리에 적재되어 실행되고있는 프로그램
포그라운드 프로세스: 사용자가 상호작용 할수 있으며 보이게 실행되고 있는 프로세스
백그라운드 프로세스: 보이지 않게 실행되고 있는 프로세스
사용자와 상호작용하지 않는 백그라운드 프로세스는 유닉스 계열에서는 데몬, 윈도우 계열에서는 서비스라고 지칭

PCB(프로세스제어 블록): 프로세스 관련 정보를 저장 하는 자료구조
PCB 에 담기는 정보

• PID: 프로세스ID - 프로세스 식별번호
• 레지스터 값
• 프로세스 상태 정보

프로세스의 메모리 영역

• 코드영역
• 데이터 영역: 프로그램이 실행되는 동안 유지되는 데이터가 저장
• 힙 영역: 프로그래머가 직접 할당할수있는 메모리 공간으로 후에 반환해야함
• 스택 영역: 데이터를 일시 저장 

변수의 종류 별 저장 영역

전역 변수: 데이터 영역

매개변수, 지역 변수: 스택 영역

정적 할당 영역과 동적 할당 영역

정적 할당 영역: 데이터 영역

동적 할당 영역: 스택 영역, 힙 영역

프로세스상태 다이어그램

1: 생성 / 2: 준비 / 3: 실행/ 4: 완료/ 5: 대기

디스패치: 프로세스가 준비상태에서 실행 상태로 전환

프로세스 계층 구조
부모 프로세스, 자식프로세스

자식 프로세스는 부모 프로세스로 부터 생성된 프로세스다.

부모 프로세스가 종료되면 자식 프로세스도 종료된다.

스레드: 프로세스를 구성하는 실행의 흐름 단위
단일 스레드 프로세스: 스레드를 하나 가지는 프로세스

멀티프로세스: 프로세스가 여러개 실행 됨

멀티스레드: 스레드를 여러 개 가지는 프로세스

스레드 끼리는 프로세스 내의 자원을 공유한다.

프로세스 간은 기본적으로 자원을 공유 하지 않음

IPC: 프로세스 간 데이터를 주고받음.

Chapter 11: CPU 스케줄링

CPU 스케줄링: 프로세스들에게 합리적으로 CPU자원을 배분

프로세스 우선순위

CPU  버스트: 프로세스가 실행 되는 동안 CPU에서 연산을 처리 하는 시간

입출력 버스트: 프로세스가 실행 되는 동안  I/O 장치에서 작업을 하는 시간

스케줄링 큐: CPU 할당을 위해 프로세스를 대기시키고 이를 스케줄링 큐로 관리한다.

준비 큐: CPU 를 이용햐야하는  프로세스들이 대기

대기 큐: I/O 장치를 이용해야 하는 프로세스들이 대기

스케줄링 기법

과제

p,304 확인 문제 1번

프로세스 상태 구조도를 보고 빈칸에 알맞은 상태를 쓰시오

풀이

1: 시작하는 부분이므로 생성

2: 프로세스는 생성에서 준비 상태로 진입

3. 준비에서 실행 상태로 진입(디스패치)

4. 실행 후에 완료상태로 진입

5. 입출력 요청이 있으면 준비 상태로 진입, 완료 후에는 다시 준비 상태로 진입

정답

1: 생성

2. 준비

3: 실행

4. 완료

5. 대기

11-2 CPU 할당 순서

준비 큐에 A,B,C,D 순으로 삽입 되었을때 선입 선처리 알고리즘 적용 시 어떤 순서로 CPU를 할당받는가?

풍이

선입 선처리의 경우 무조건 먼저 삽입된 프로세스 부터 CPU를 할당한다.
따라서 A, B, C, D 순으로 프로세스를 할당 받는다

답: A, B, C, D

추가 학습

https://github.com/kangtegong/self-learning-cs/blob/main/process/process_cplusplus.md

예제 코드도 한번 확인해봅시다.

전 파이썬을 모르는 관계로 c++ 만 봤습니다.

1. 프로세스를 생성하고 PID 를 확인

참고로 예제코드에서는 unistd.h 사용하고 있는데 이건 리눅스환경에서 사용하는 헤더라고 합니다.

저처럼 윈도우 환경이신 분들은 다른방법을 사용해야 합니다

#include <iostream>
#include <string>
#include <cstring>
#include<stdio.h>
#include <io.h>
#include <sys/types.h>
#include <Windows.h>
using namespace std;

int main() 
{
    cout << "hello, os\n";
    // pid 확인
    cout << "pid: " << GetCurrentProcessId() << endl;
}

2. 자식 프로세스 생성, pid 확인

#include <iostream>
#include <string>
#include <cstring>
#include<stdio.h>
#include <io.h>
#include <sys/types.h>
#include <Windows.h>
#include <strsafe.h>

using namespace std;

int main() 
{
    cout << "hello, os\n";
    // pid 확인
    cout << "parent pid is " << GetCurrentProcessId() << "\n";

    STARTUPINFO si;

    PROCESS_INFORMATION pi;



    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    TCHAR exePath[MAX_PATH];

    // 자식 프로세스로 실행할 프로그램 경로
    StringCchCopy(exePath, MAX_PATH, TEXT("C:\\Windows\\System32\\notepad.exe"));

    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    static bool IsChildProcess = false;
    if (!IsChildProcess)
    {
        // 프로세스생성.
        IsChildProcess = true;
        if (!CreateProcess(NULL, exePath, NULL, NULL, FALSE, 0, NULL, NULL, &si, &pi))

        {
            printf("CreateProcess failed (%d)\n", GetLastError());
            return 0;
        }
        cout << "child pid is " << pi.dwProcessId;

        WaitForSingleObject(pi.hProcess, INFINITE);

        CloseHandle(pi.hProcess);
        CloseHandle(pi.hThread);

        return 0;
    }
    return 0;
}

예제코드랑은 동작이 다르다. 

fork() 는 프로세스를 복제 하는데 createprocess 는 경로에 해당되는 프로세스를 실행 하는 식으로 자식 프로세스를 생성하므로

예제처럼 동일한 프로그램을 자식 프로세스로 생성 할 수가 없어서 부득이하게 notepad.exe 를 자식 프로세스로 실행 하도록 했다.

정확히는 자기 자신의 경로를 CreateProcess 에 넣어서 실행하면 자식프로세스가 무한히 생기게 된다.

한번만 실행시키려면 외부 txt 파일이나 ini 파일같은데 플래그 저장해서 쓰면 되긴 하겠지만 복잡하므로 그냥 다른프로그램을 실행시켰습니다. 

이후 실습은 CreateProcess()로는 직접 비슷하게 진행하긴 힘들어서 간단하게 확인만 하겠습니다. 

동일한 작업을 하는 프로세스 만들기

부모 프로세스는 다른 자식 프로세스를 생성할 수 있고,

자식 프로세스도 자식 프로세스를 생성할 수 있습니다.

https://www.acmicpc.net/problem/2108

백준 2108번 - 통계학(실버 3)

풀이

다른건 크게 어려울 것이 없는데 최빈값을 어떻게 처리할지 잘 생각해야 한다

unordered_map 에 <입력받은수, 등장횟수> 로 저장해서 최빈값을 찾는 식으로 구현했다.

그리고 밑에 조건에 평균에 -0 이 나오면 안된다고 되어 있다. 이 부분도 고려해서 출력해야 한다.

전체코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <unordered_map>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> num(n,-4001);
    vector<int> numcnt(n);

    // 등장횟수
    unordered_map<int, int> mapcnt;


    int intsum = 0;
    int intmin = 4000;
    int intmax = -4000;
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        // 숫자 저장
        // 위의 인덱스별로 나온 개수 저장
        mapcnt[k]++;

        num[i] = k;
        intsum+= num[i];
        if (intmin > num[i])
        {
            intmin = num[i];
        }
        if (intmax < num[i])
        {
            intmax = num[i];
        }
       
    }

    // n은 홀수
    int midindex = (n +1) / 2;

    vector<int> sortnum(n);
    sortnum  = num;
    sort(sortnum.begin(), sortnum.end());

    // 최빈값 구하기
    // 카운트 중에 최대 구하기
    vector<int> sortcnt(n);
    sortcnt = numcnt;
    sort(sortcnt.begin(), sortcnt.end(), greater<int>());
    int maxcntidx = sortcnt[0];
    // 최대 등장 횟수
    int freqnum = 0;
    // 최빈 값
    int intmostfreq;

    vector<int> freqno;
    for (auto it:mapcnt)
    {
        // num , 등장횟수
        if (freqnum < it.second)
        {
            freqnum = it.second;
        }
    }
   

    for (auto it : mapcnt)
    {
        if (freqnum == it.second)
        {
            freqno.push_back(it.first);
        }
    }

    if (freqno.size() > 1)
    {
        sort(freqno.begin(), freqno.end());
        intmostfreq = freqno[1];
    }
    else
    {
        intmostfreq = freqno[0];
    }

    // 평균
    if (round(static_cast<float>(intsum) / static_cast<float>(n)) == 0)
    {
        cout << 0 << "\n";
    }
    else
    {
        cout << round(static_cast<float>(intsum) / static_cast<float>(n)) << "\n";
    }

    // 중앙값
    cout << sortnum[midindex-1] << "\n";

    // 최빈값
    cout << intmostfreq << "\n";
    
    // 범위
    cout << intmax - intmin;
}

백준 문제풀이 하면서 STL을 다양하게 사용해보고 있는데 헷갈려서 정리한다

목차

vector 의 특징

vector 는 동적 배열 구조로 여러 가지 자료형으로 정의하여 사용 할 수 있다.

vector 는 데이터를 선형적으로 만들려고 하며 저장 공간을 초과하는 데이터를 추가 하는 경우 현재 보유하고 있는

메모리의 두 배 만큼을 할당. (메모리의 사용량이 증가하고 속도가 느려질수있음)

또한 배열의 크기가 빈번하게 변경될때도 성능이 저하될수 있다.

vector 의 검색 시 시간 복잡도는 O(n) 으로, 검색이 빈번한 경우 성능을 고려하면 map등  다른 자료구조가 효율적이

vector 기본 사용법

생성

고정 길이로 선언할시 미리 뒤에 vector 의 크기를 정의한다. 

// 고정 크기
// 변수도 사용 가능
vector<int> vec(n);

// 가변 크기
vector<int> vec;

선언 시 초기화

// 배열의 개수, 초기 값
vector<int> vec(10,0);

 * int 의 경우 기본적으로 0으로 초기화되어 있다.

요소 초기화 

vec.clear()

삽입

push_back()으로 삽입

vec.push_back(it.first);

삭제

erase() 로 삭제

인덱스 기준으로 삭제와 값 기준으로 삭제 다 가능

// 인덱스 기준
vec.erase(vec.begin() + idx);

정렬

오름차순, 내림차순 정렬

// 오름차순(기본)
sort(freqno.begin(), freqno.end());
// 내림차순
sort(freqno.begin(), freqno.end(), greater<int>());

사용자 정의 정렬(compare 함수 사용)

bool compare(Users user1, Users user2)
{
	// 나이를 기준으로 오름차순 정렬
	if (user1.age != user2.age)
	{
		return user1.age < user2.age;
	}
	// 나이가 같다면 들어온 순서(number)를 기준으로 정렬
	return user1.number < user2.number;
}

sort(user.begin(), user.end(), compare);

특정 원소의 개수

// vector 안에서 3의 개수를 구함
count(vec.begin(), vec.end(), 3)

* 시간복잡도는 그냥 반복문으로 구하는거랑 똑같음

vector의 요소의 개수 출력

vec.size();

https://www.acmicpc.net/problem/4134

입력수 n에 대해 n보다 같거나 큰 가장큰 소수를 찾으면 된다. 

1. 소수 판별

int isprime(long long int num)
{
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    for (long long int i = 3; i <= sqrt(num); i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

2. 소수를 찾을 때 까지 반복

long long int findMinPrime(long long int n)
{
    while (!isprime(n))
    {
        n++;
    }
    return n;
}

입력값 n에 대해 소수인지 확인한 후 소수가 아닌 경우 n 증가 수행

소수를 찾을 때 까지 반복한다. 

입력의 개수는 안주어지고, 입력 값은 최대 크기가 커서

에라스토테네스의 체를 사용하기보단 각각의 케이스별로 소수판별을 해야 하는 같다.

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int isprime(long long int num)
{
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    for (long long int i = 3; i <= sqrt(num); i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

long long int findMinPrime(long long int n)
{
    while (!isprime(n))
    {
        n++;
    }
    return n;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        long long int n;
        cin >> n;

       cout << findMinPrime(n) <<"\n";
    }

}

목차

3주차 범위

Chapter 06: 메모리와 캐시메모리
Chapter 07: 보조기억장치
Chapter 08: 입출력장치

벌써 책기준으로는 진도를 반정도 나갔네요

남은주차도 화이팅

학습 내용 정리

Chapter 06: 메모리와 캐시메모리

RAM 의 특징

- 휘발성 메모리: 전원을 끄면 저장된 내용이 사라짐

반대로 비휘발성 메모리로는 ROM, 하드디스크, SSD 등이 있음

RAM 종류

DRAM: Dynamic RAM

• 저장된 데이터가 동적으로 변하는 RAM
• 데이터의 소멸을 막기 위해 일정주기로 데이터를 재활성화
• 소비 전력 낮음, 집적도가 높음 -> 대용량으로 설계 용이

SRAM: Static RAM

• 시간이 지나도 저장된 데이터가 사라지지 않음
• 집적도 낮음, 소비 전력 높음

SDRAM: 클럭신호와 동기화된 DRAM

DDR SDRAM: 대역폭을 넓혀 속도가 빠른 SDRAM

물리 주소: 하드웨어가 사용하는 주소

논리 주소: CPU와 프로그램이 사용하는 주소

논리 - 물리 주소 간 변환:

• MMU(메모리관리 장치) 에 의해 수행
• 논리 주소 + 베이스 레지스터 값을 더하여 물리 주소로 변환

배이스 레지스터: 프로그램의 첫 물리 주소를 저장한 레지스터

한계 레지스터

• 프로그램의 논리 주소 범위를 벗어나는 명령어 실행을 방지, 다른 프로그램에 영향을 받지 않도록 보호
• 논리 주소의 최대 크기를 저장 후 접근 하고자 하는 논리 주소가 한계 주소보다 작은 지 검사

논리 주소 -> 물리 주소 변환 과정

저장 장치 계층 구조: CPU가 메모리에 빠르게 접근 할 수 있도록 분류

상단에서 부터 레지스터 -> 캐시 메모리 -> 메모리 -> 보조기억장치 

구조도의 상단에 있을수록 속도가 빠르고 용량이 작음

캐시 메모리: CPU의 연산 속도와 메모리 접근 속도의 차이를 줄임

캐시 적중률: 캐시가 히트 되는 비율

캐시 적중률 공식

캐시 히트 횟수 / (캐시 히트 횟수 + 캐시 미스 횟수)

Chapter 07: 보조기억장치

하드 디스크 구성 요소

플래터: 하드디스크에서 실제로 데이터가 저장

스핀들: 플래터를 회전시키는 요소

헤드: 플래터를 대상으로 데이터를 읽고 쓰는 요소

플래터의 구성 요소

트랙: 플래터를 동심원으로 나누었을 때 하나의 

섹터: 하드 디스크의 가장 작은 전송 단위

실린더: 같은 트랙이 위치한 곳을 연결한 논리적 단위

하드 디스크가 데이터 접근 시간

• 탐색 시간: 데이터가 저장된 트랙까지 헤드 이동 시키는 시간
• 회전 지연: 헤드가 있는 곳으로 플래터를 회전 시키는 시간
• 전송 시간: 하드 디스크와 컴퓨터 간의 데이터를 전송 하는 시간

플래시 메모리의 종류

• SLC: 한 셀로 2개의 정보 표현
• MLC: 한 셀로 4개의 정보 표현
• TLC: 한 셀로 8개의 정보 표현

참조

https://news.skhynix.co.kr/post/data-in-nand-flash-memory

RAID: 여러개의 물리적 보조기억장치를 하나의 논리적 보조기억장치로 사용 하는 기술

RAID 의 종류 (하단 심화과제 참조)

Chapter 08: 입출력장치

장치 컨트롤러의 구조

• 데이터 레지스터
• 상태 레지스터 
• 제어 레지스터

입출력 방법

• 프로그래 입출력
• 인터럽트 기반 입출력
• DMA 입출력: CPU를 거치지 않고도 입출력장치, 메모리가 상호 작용

입출력 방법 종류

• 메모리 맵 입출력: 메모리 주소 공간과 입출력 주소 공간을 하나로 간주
• 고립형 입출력: 메모리 주소 공간과 입출력장치 주소 공간을 분리

사이클 스틸링: DMA의 시스템버스 이용

과제

기본 과제 : p.185 3번 문제
                 p.205 1번 문제

p.185 3 .설명에 맞는 보기를 고르시오

SRAM, DRAM

• 주로 캐시 메모리로 사용됨 : (1)
• 주로 주기억장치로 사용됨: (2)
• 대용량화 유리: (3)
• 집적도 낮음: (4)

답:

(1): SRAM

(2): DRAM

(3): DRAM

(4) SRAM 

p.205 1 .저장장치 계층 구조도를 채우시오

답:

레지스터, 캐시 메모리, 메모리, 보조기억장치

심화 과제 : RAID 의 정의와 종류

RAID: 여러 개의 하드 디스크에 중복 데이터를 나누어 저장해 디스크가 고장나더라도 해당 디스크를 교체하면 원래의 데이터가 복원되는 신뢰성 높은 저장 장치

RAID 종류

출처: 정보통신기술용어해설

http://www.ktword.co.kr/test/view/view.php?nav=2&no=863&sh=RAID

목차

-

2주차 범위

Chapter 04: CPU의 작동원리
Chapter 05: CPU 성능 향상 기법

슬슬 인터럽트나 복잡한 주소 지정 방식이 나와서 어렵네요...

학습 내용 정리

Chapter 04: CPU의 작동원리

ALU (산술논리연산장치)

ALU는 제어 신호와 피연산자를 받아들인다.

ALU는 결과값 및 플래그를 내보낸다.

플래그의 종류

• 부호 플래그
• 제로 플래그
• 캐리 플래그
• 오버플로우 플래그
• 인터럽트 플래그
• 슈퍼바이저 플래그

플래그는 플래그 레지스터에 저장된다.

 제어장치

제어 장치: 제어 신호를 내보내고 명령어를 해석하는 부품

제어 신호: 컴퓨터 부품을 관리, 작동시키기 위한 전기신호

제어장치의 역할

• 클럭 신호 받음
• 명령어를 받음
• 플래그 레지스터속 플래그값 받음
• 제어 버스로 받아들인 제어 신호를 받음

레지스터

• 프로그램 카운터: 메모리에서 읽어들일 명령어 주소  저장
• 명령어 레지스터: 메모리에서 읽은 명령어를 저장
• 메모리 주소 레지스터: 메모리의 주소 저장
• 메모리 버퍼 레지스터: 메모리와 주고받을 값을 저장
• 범용 레지스터: 데이터와 주소를 모두 저장 가능
• 플래그 레지스터: 연산결과, CPU상태의 부가적인 정보 저장

특정 레지스터를 이용한 주소 지정 방식

1. 스택 주소 지정 방식: 스택과 스택 포인터를 활용한 주소 지정 방식
2.  변위 주소 지정 방식

스택은 메모리 내부 스택 영역 에 위치함

변위 지정 방식의 종류

• 상대 주소 지정 방식: 오퍼랜드와 프로그램 카운터의 값을 더해 유효 주소를 얻음
• 베이스 레지스터 주소 지정 방식: 오퍼랜드와 베이스 레지스터의 값을 더해 유효 주소를 얻음

베이스 레지스터에 저장된 주소가 기준주소가 됨

명령어 사이클의 종류

• 인출 사이클: 명령어를 CPU로 가져옴
• 실행 사이클: 명령어를 실행
• 인터럽트 사이클: 인터럽트를 실행
• 간접 사이클: 명령어를 가져온 후 메모리 접근이 더 필요한 경우

인터럽트

인터럽트: CPU의 정상적인 작업을 방해하는 신호

인터럽트의 종류

• 동기 인터럽트(예외)
• 비동기 인터럽트(하드웨어 인터럽트): 주로 입출력장치에 의해 발생

참고) 동기와 비동기

동기식은 요청후 응답까지 대기, 비동기는 요청 후 응답을 대기하지 않는 방식입니다.

자세한 내용은 아래 내용 참고

https://wikidocs.net/227912

하드웨어 인터럽트 처리 과정

인터럽트 서비스 루틴(인터럽트 핸들러): 인터럽트를 처리하기 위한 프로그램

예외 종류

• 폴트
• 트랩
• 중단
• 소프트웨어 인터럽트

Chapter 05: CPU 성능 향상 기법

클럭: CPU에서 연산을 조정하는 타이밍 신호

오버클럭: 최대 클럭 속도를 강제로 더 올리는 기법

코어: CPU내에서 명령어를 실행하는 부품

멀티코어: 코어를 여러개 포함하는 CPU

스레드: 실행 흐름의 단위

멀티 스레드 프로세서: 여러개의 하드웨어적 스레드를 지원하는 CPU

명령어 병렬 처리 기법

• 명령어 파이프라이닝: 동시에 여러개의 명령어를 겹처 실행
• 슈퍼스칼라: 여러개의 파이프라인 사용
• 비순차적 명령어 처리: 파이프라인 중단 방지를 위해 명령어를 비순차적으로 처리

ISA: 명령어 집합 구조

RISC 와 CISC

과제

기본 과제 : p.125 2번 문제
                 p.155 4번 문제

2. 설명에 맞는 레지스터를 보기에서 찾아 빈칸을 채워 보세요.
  - 프로그램 카운터, 명령어 레지스터, 플래그 레지스터, 범용 레지스터

• (1): 연산 결과 혹은 CPU상태에 대한 정보를 저장하는 레지스터
• (2): 메모리에서 가져올 명령어 주소를 저장하는 레지스터
• (3): 데이터와 주소를 모두 저장할 수 있는 레지스터
• (4): 해석할 명령어를 저장하는 레지스터

답: (1): 플래그 레지스터

     (2): 프로그램 카운터

     (3): 범용 레지스터

     (4): 명령어 레지스터

멀티코어 CPU를 도식화한 그림이다. 그림에 알맞은 용어를 쓰시오

[p.155 그림 참조]

정답: 코어

심화 과제: 코어와 스레드, 멀티 코어와 멀티 스레드의 개념 정리

스레드: 프로세스 내에서 실행되는 흐름의 단위

멀티 스레드: 하나의 프로세스 내에서 둘 이상의 스레드사 동시에 작업을 수행

코어: 명령을 실행하는 CPU 내의 단일 처리 장치

멀티 코어: 여러개의 독립 코어를 단일 집적회로로 이루어진 하나의 패키지로 통합한 CPU

요즘 나오는 pc들은 다 멀티코어라고 보시면 됩니다. 

심심하시면 한번 확인해보죠

ctrl+ alt +del 혹은 직접 작업관리자 여신 뒤에

성능 탭을 클릭합니다

그럼 우측 하단에 저렇게 표시가 되는데

저기서 코어 수가 표시됩니다

제 pc는 16개네요

나는야 포켓몬 마스터 이다솜 (실버 4)

https://www.acmicpc.net/problem/1620

 문제가 너무 길어서 링크에서 참조해주세요

입력받는 포켓몬 개수 N, 맞춰야하는 문제 M 이 주어집니다.

포켓몬은 1번부터 번호 순서대로 입력됩니다.

풀이

입력받고 {번호, 포켓몬이름} 의 구조체로 저장한 뒤, 

번호를 입력받으면 이름을, 이름을 입력받으면 번호를 찾아서 출력하면 되는 문제입니다.

논리적으로는 간단하지만, 제한 시간이 짧아서 

반복문을 통한 비교를 하면 바로 시간제한이 뜹니다.

map 등의 자료구조를 통한 탐색을 해야 합니다.

여기서 vector 또는 배열 사용 후 for 문으로 탐색 시 시간복잡도는 

O(n)

map 의 시간 복잡도는

O(logN)

unordered_map 의 시간복잡도는 

O(1) 

이 문제의 경우 정렬을 따로 쓰지 않으니, unordered_map을 사용하면 성능이 더 빨라집니다.

같은 코드로 map 과 unordered_map 사용을 비교해보니 백준 채점 기준

각각 200ms / 120ms 정도로 상당히 차이가 많이 나는것을 확인가능합니다.

map/ unordered_map  구조체의 경우 키 값을 string 으로도 설정할 수 있어서,

key 가 번호인 구조체랑 key 가 포켓몬 이름인 구조체 2개를 선언했습니다.

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

번호를 입력받은 경우  와   포켓몬 이름을 입력받은 경우 를 구분해서 처리해야 하는데,

포켓몬 이름은 알파벳으로 구성되었다고 언급되므로 입력은 string 으로 받은 후 isalpha()를 통해 첫번째 글자가 알파벳인지 확인했습니다.

        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }

번호 = 인덱스 + 1 이므로 번호를 입력받은 경우 는 바로 출력하면 되고,

포켓몬 이름을 입력받은 경우 는 find() 함수를 통해 탐색해야합니다.

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
using namespace std;
using std::cin;

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int k;

    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;

        pkmon.insert(make_pair(i, name));
        pkmonByName.insert(make_pair(name, i));
    }

    // 출력시작
    for (int i = 0; i < k; i++)
    {
        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }
        // 번호를 받은 경우
        else
        {
            int intnum = stoi(str);
            cout << pkmon[intnum -1] << "\n";
        }
    }
}

목차

혼공컴운 1주차 범위는 

Chapter 01: 컴퓨터 구조 시작하기
Chapter 02: 데이터
Chapter 03: 명령어 

로 이루어져 있습니다. 

기본 과제는 p.65 3번 문제고 선택 과제는 스택과 큐의 내용 정리하기 입니다.

스택과 큐는 기본적인 자료구조로 중요한 내용이니 선택 과제도 해 보았습니다.

아직까지는 크게 어려운 내용은 없고 간단하게 정리하면서 봤습니다.

학습 내용 정리

Chapter 01: 컴퓨터 구조 시작하기

컴퓨터가 이해하는 구조

• 데이터
• 명령어

컴퓨터의 4가지 핵심 부품

• CPU
• 메모리(주기억장치)
• 보조기억장치
• 입출력장치

주기억장치는 다음의 2가지로 나뉨

• RAM
• ROM

메모리

메모리(주기억장치)는 현재 실행되는 명령어와 데이터를 저장한다.

메모리에서 저장된 값의 위치는 주소로 알 수 있다

메모리 중 RAM은 휘발성 메모리로 전원이 꺼지면 데이터가 전부 지워진다

CPU

CPU는 명령어를 읽고 해석, 실행한다.

CPU의 3대 구성 요소

• ALU(산술논리연산장치)
• 레지스터
• 제어 장치

ALU 는 컴퓨터 내의 연산을 담당 한다.

레지스터는 프로그램 실행에 필요한 값을 임시 저장한다

제어 장치는 제어 신호를 내보내고 명령어를 해석 한다

보조기억장치

물리적 디스크가 연결되어 있으며 컴퓨터가 꺼져도 데이터가 유지 된다

입출력장치

키보드, 마우스 등 외부에 연결되어 있는 주변장치로 컴퓨터 내부의 정보를 교환하는 장치

시스템 버스를 통해 컴퓨터 내부와 데이터를 주고 받는다

시스템 버스

시스템 버스 내부 구성

• 주소 버스: 주소를 주고 받음
• 제어 버스: 제어 신호를 주고 받음
• 데이터 버스: 명령어와 데이터를 주고 받음

Chapter 02: 데이터

정보 단위

bit: 0,1 을 표현 할 수 있는 가장 작은 정보 단위

byte: 8bit

그 밖에 KB(1000byte), MB, GB 등이 있다.

이진법

0, 1로 수를 표현

2의 보수법: 이진법을 음수로 표현하기 위한 방법

십육진법

0~9,  A~F로 수를 표현

문자 집합

컴퓨터가 인식하고 표현할 수 있는 문자 모음

대표적 문자 집합 종류

• ASCII
• 유니코드

인코딩

문자를 컴퓨터가 이해 할 수 있도록 0과1로 변환시킴

대표적인 유니코드의 인코딩 종류

• UTF-8
• UTF-16
• UTF- 32

Chapter 03: 명령어

컴퓨터 언어의 종류

고급 언어: 사람이 이해하기 쉬운 언어

저급 언어: 기계 친화적인 언어

고급 언어는 C, C++, Java, Python 등

저급 언어는 기계어, 어셈블리어 등

( C, C++ 는 메모리 직접 접근 등 저급 언어의 일부 특성을 가지고 있다)

고급 언어의 변환 방식에 따른 분류

고급 언어는 저급 언어로 변환 되어 실행 됨

변환 방식

• 컴파일 방식
• 인터프리트 방식

컴파일 방식: 소스 코드 전체를 저급 언어 변환 시킴 (C언어 등)

인터프리트 방식: 인터프리터에 의해 소스코드 한 줄씩 저급 언어로 변환 후 실행 시킴(Python 등)

목적 코드: 컴파일러로 인해 저급 언어로 변환된 코드

컴파일 언어 vs 인터프리트 언어

명령어의 구조

• 연산 코드(연산자)
• 오퍼랜드(피연산자)

연산 코드: 명령어가 수행 할 연산

오퍼랜드: 연산에 사용될 데이터 또는 연산에 사용될 데이터 주소

유효 주소: 연산 대상 데이터가 저장 된 위치

주소 지정 방식

• 즉시 주소 지정 방식: 오퍼랜드에 데이터를 직접 명시
• 직접 주소 지정 방식: 오퍼랜드에 유효 주소 직접 명시
• 간접 주소 지정 방식: 유효 주소의 주소를 오퍼랜드에 명시
• 레지스터 주소 지정 방식: 연산 대상 데이터를 저장한 레지스터를 오퍼랜드에 명시
• 레지스터 간접 주소 지정 방식: 연산에 사용할 데이터를 메모리에 저장하고 유효 주소를 저장한 레지스터를 오퍼랜드에 명시

과제

기본 과제: p.51 3번문제
               p.65 3번문제

3. 다음 설명의 빈칸에 들어갈 내용을 쓰시오.
프로그램이 실행되려면 반드시 ( _____ ) 에 저장되어 있어야 한다.

프로그램이 실행되려면 메모리에 저장 되어야 합니다. 정답: 메모리

3. 1101(2) 를 2의 보수법으로 표현하라

과정도 문제에 나와 있어서 그대로 따라하면 됩니다.

제 풀이 입니다.

2의 보수법으로 음수 표현하는 방법은

1) 모든 0과 1을 반대로 적는다

2) 마지막에 + 1 해준다

1101(2)의 음수값은 0011(2) 인 것을 간단하게 구할 수 있습니다.

심화 과제: 스택과 큐 내용 정리하기

스택 과 큐는 대표적인 선형 자료구조입니다.

스택은 한쪽 끝이 막혀 있고, 큐는 양쪽이 뚫려 있는 형태로 표현합니다.

스택에 데이터를 새로 저장하는 명령어는 push, 데이터를 꺼내는 명령어는 pop 입니다.

구조상 스택에서 꺼내는 데이터는 마지막으로 저장된 데이터부터 꺼내지게 됩니다.

이러한 관리 방식을 LIFO(후입선출) 이라고 합니다.

반대로 큐는 구조상 한쪽 끝에서 데이터를 저장하고 반대편 끝에서 먼저 저장된 데이터부터 꺼내지게 됩니다.

큐 에서 데이터를 추가하는 연산을 Enqeue, 데이터를 삭제하는 연산을 Dequeue 라고 합니다

이러한 관리 방식을 FIFO(선입선출) 이라고 합니다

실습 - 스택 구현하기

여기서부턴 개인적인 실습입니다.

 아래 문제를 풀고 스택 구조를 구현하고 해당 프로그램을 작성 해 보았습니다.

백준 - 스택2(28278)

https://www.acmicpc.net/problem/28278

스택 구조를 구현 하고 명령어에 따라 처리 하는 문제입니다. (실버 4단계)

저는 c++ STL에 있는 stack  구조체를 활용하여 구현했습니다.

#include <iostream>
#include <stack>
using namespace std;
using std::cin;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	
	stack<int> Stack01;

	// 명령의수
	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		// 스택에 push
		if (input == 1)
		{
			int n;
			cin >> n;
			Stack01.push(n);
		}
		// 스택에 pop
		else if (input == 2)
		{
			if (Stack01.empty())
			{
				cout << -1 << "\n";
			}
			else
			{
				cout << Stack01.top() << "\n";
				Stack01.pop();
			}
		}
		// 스택에 들어가있는 정수 개수
		else if (input == 3)
		{
			cout << Stack01.size() << "\n";
		}
		// 스택이 비어 있으면 1, 아니면 0
		else if (input == 4)
		{
			if (Stack01.empty())
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}
		}
		// 스택 맨 위에 정수를 출력, 없으면 -1 출력
		else if (input == 5)
		{
			if (Stack01.empty())
			{
				cout << -1 << "\n";
			}
			else
			{
				cout << Stack01.top() << "\n";
			}
		}
		// 유효하지 않은 명령
		else
		{
			cout << "유효하지 않은 명령" << "\n";
		}
	}
}

실행 결과

처음에 13을 push 한 후 6을 push 했습니다.

pop 수행 시 6, 13 순으로 출력 되는걸 확인 가능합니다.

참고

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)