AndroidTeacher

JOIN(조인)

JOIN이란 '연결하다' 라는 뜻을 지닌 단어이다. 이 단어의 뜻처럼, 데이터베이스에서는

둘 이상의 테이블을 연결해서 테이블을 검색하는 방법을 이야기 한다.

JOIN의 종류

1. INNER JOIN
2. OUTER JOIN
3. CROSS JOIN
4. SELF JOIN

그렇다면, 이제 다음과 같은 테이블 두 개를 가지고 각각의 조인에 대해 알아보자.

[Star 테이블]

[Dep 테이블]

1. INNER JOIN (이너조인)

이너조인은 위의 그림처럼 두 개의 테이블에서 공통된 요소들을 통해 결합하는 조인방식이다.

가장 일반적인 조인으로, 조인 사용시 명령어로 INNER JOIN 대신 JOIN 만을 입력해도 INNER JOIN이 사용된다.

그럼 다음과 같이 SQL을 입력해보자.

SELECT Star.Name, Dep.DepName
From Star JOIN Dep ON Star.DepNo = Dep.DepNo

위의 Star, Dep 테이블을 가지고 INNER JOIN 을 수행한 결과는 다음과 같다.

Star테이블과 Dep테이블 중에서 Star의 DepNo와 Dep의 DepNo가 일치하는 요소들만 골라서 출력을 하게된다.

여기서 눈여겨 보아야 할 부분은,

Star테이블의 '이병헌'과 Dep테이블의 '이경규가 간다' 라는 행이 누락되어 있는 것이다.

이 둘은 두 테이블 간의 공통된 데이터가 없기 때문이다.

즉, '이병헌'은 DepNo가 Null이기 때문에 Dep테이블과 겹치는 부분이 없으며

'이경규가간다' 는 Star테이블에서 같은 DepNo 코드를 가진 데이터가 없기 때문에 출력되지 않은 것이다.

이렇듯, INNER JOIN은 ON의 조건에 맞는 공통된 부분이 있는 경우에만 출력이 된다.

2. OUTER JOIN (아우터조인)

위의 INNER JOIN은 공통된 부분이 있는 행만 출력을 해주었는데,

공통된 부분이 없는 데이터도 함께 보고싶은 경우가 있을 것이다.

이럴 때 사용하는 것이 바로 OUTER JOIN이다.

OUTER JOIN은 크게 LEFT(OUTER) JOIN과 RIGHT(OUTER) JOIN, FULL OUTER JOIN으로 나눌 수 있다.

2.1 LEFT JOIN

공통적인 부분 + LEFT 테이블에 있는 것만 출력

SELECT Star.Name, Dep.Name
FROM Star LEFT JOIN Dep
ON Star.DepNo = Dep.DepNo

위의 쿼리를 실행한 결과는 다음과 같다.

공통된 값 + 왼쪽 테이블에만 있는 값이 출력된 것을 알 수 있다.

반면, 여기서 만약 공통된 부분마저 제외하고 왼쪽에 '만' 있는 것을 출력하고 싶다면
다음과 같이 NULL을 이용하여 한 가지 조건만 더 추가해주면 된다.

SELECT Star.Name, Dep.Name
From Star LEFT JOIN Dep
ON Star.DepNo = Dep.DepNo
WHERE Star.DepNo IS NULL

위 쿼리를 실행한 결과는 다음과 같다.

2.2 RIGHT JOIN

공통적인 부분 + 오른쪽에 있는 것만 출력

SELECT Star.Name, Dep.Name
FROM Star RIGHT JOIN Dep
ON Star.DepNo = Dep.DepNo

위 쿼리를 실행한 결과는 다음과 같다.

여기서, 위의 LEFT JOIN과 마찬가지로 RIGHT 테이블에 '만' 있는 것을 출력하고 싶다면
똑같이 NULL 속성을 이용하여 출력할 수 있다. (위의 LEFT JOIN 설명 참고)

2.3 FULL OUTER JOIN

A테이블이 가지고 있는 것 + B 테이블이 가지고 있는 것 모두

SELECT Star.Name, Dep.Name
FROM Star FULL OUTER JOIN Dep
ON Star.DepNo = Dep.DepNo

위 쿼리를 실행한 결과는 다음과 같다.

즉, LEFT OUTER JOIN과 RIGHT OUTER JOIN의 결과값을 합친 것이라고 볼 수 있다.

3. CROSS JOIN(크로스 조인)

크로스 조인은 두 테이블 간의 가능한 모든 경우의 수에 대한 결과를 보여 준다.

즉, 카디널리티 곱을 한 것이다.

SELECT Star.Name, Dep.DepName
FROM Star CROSS JOIN Dep

위 쿼리를 실행한 결과는 다음과 같다.

위의 결과 처럼, 두 테이블의 모든 행들을 서로 교차하여 곱한다고 생각하면 된다.

그래서 Star테이블(7행) x Dep테이블(4행) = 28 행이 탄생하게 된다.

4. SELF JOIN(셀프조인)

셀프 조인은 이름처럼 자기 혼자서 '스스로' 결합을 하는 방식이다.

즉 위의 LEFT, RIGHT 조인과는 다르게 다른 테이블을 참조하는 것이 아닌 자기 자신을 참조한다.

SELF JOIN이 필요한 상황을 예를 들어 설명해보겠다.

[A 테이블]

위의 A 테이블을 보면 각각의 스타의 ID와 이름, Partner의 번호가 부여되어 있다.

이 때, Partner의 번호 대신 이름을 알고 싶다면 어떻게 해야 할까?

이때 SELF JOIN을 이용하면 이름을 알 수 있다.

Partner의 정보도 같은 테이블 내에 존재하기 때문이다.

이렇게 Self 조인 쿼리를 작성해보자.

SELECT A.ID, A.Name, A.Partner, B.Partner PartName
FROM Star A JOIN Star B 
ON A.Partner = B.ID

위 쿼리를 실행한 결과는 다음과 같다.

이렇게 하나의 테이블을 가지고 SELF JOIN을 이용하여 원하는 값을 출력할 수 있다.

마치며..

데이터베이스는 개발직 면접에서 자주 등장하는 단골 분야이다.

따라서, 다음과 같은 질문에 답을 할 수 있도록 미리 준비해보는 것도 추천한다.

• JOIN의 종류와 각각의 종류의 특징에 대해 이야기 해보세요
• SELF 조인을 사용할 경우를 예를 들어 보세요
• LEFT OUTER JOIN을 수행할 때, 오직 LEFT에만 있는 값을 가져오도록 쿼리를 한번 짜보세요.

오늘은 이렇게 데이터베이스의 조인(Join)에 대해 알아보았습니다.

이외에 전체적인 CS주제들은 https://github.com/HongEunho 와 https://github.com/MLifeFam/cs_interview 에 정리되어 있습니다.

관계 데이터 모델

관계 데이터 모델에서 지원하는 언어는 총 2가지가 있다.

1. 관계 해석 - 원하는 데이터만 명시하고 질의를 "어떻게 수행할 것인가"는 명시하지 않는 선언적 언어
2. 관계 대수 - "어떻게 질의를 수행할 것인가"를 명시하는 절차적 언어

관계 대수 (Relation Algebra)

• 릴레이션들을 다루는 연산들
• 기존의 릴레이션들로부터 새로운 릴레이션을 생성함.
• 연산자들을 사용하여 보다 복잡한 관계 대수식을 점차적으로 만들 수 있음.
  기본적인 연산자들의 집합으로 이루어짐.
• 결과 릴레이션은 또 다른 관계 연산자의 입력으로 사용될 수 있음.
  1. 단일 혹은 두 개의 테이블들을 입력 받아 결과 테이블을 생성.
  2. 집합 연산을 토대로 만든 것이 관계 대수이며, 기본적으로는 집합 연산자에 속함.
• 특징

셀렉션 (Selection)

• 릴레이션 R에서 어떤 선택 조건을 만족하는 튜플들을 선택(원하는 데이터를 수평적으로 도출)
• 결과 릴레이션은 R과 동일한 애트리뷰트(속성)을 가짐
  

  

프로젝션 (Projection)

• 한 릴레이션의 속성들의 부분 집합을 구함(원하는 데이터를 수직적으로 도출)
• 중복 튜플 존재 X
  

  

합집합 (Union)

• 릴레이션1에 있거나, 릴레이션2에 있는 튜플들로 이루어진 릴레이션을 반환
• 결과 릴레이션에서 중복된 튜플들을 제거
  

  

교집합 (Intersection)

• 릴레이션1과 릴레이션2에 동시에 속하는 튜플들로 이루어진 릴레이션
  

  

차집합 (Relative Complement)

• 릴레이션R과 릴레이션S에 대해 R에는 속하지만 S에는 속하지 않은 튜플들로 이루어진 릴레이션
  

  

카티션 프로덕트 (카티션 곱 연산자(Cartesian Product))

• 카디널리티가 i인 릴레이션 R(A1, A2, ... An)과 카디널리티가 j인 릴레이션 S(B1, B2, ... Bn)의 카티션 곱 R X S는
  차수가 n+m이고 카디널리티가 i*j이고, 속성이 (A1, A2, ... An, B1, B2, ... Bn)이다
• R과 S의 튜플들의 모든 가능한 조합인 릴레이션으로, 카티션 곱의 결과 릴레이션은 크기가 매우 클 수 있다.
• 유용하지 않음(보통 카티션 곱의 일부분만 원하기 때문)
  

  

디비전 (Division)

• 차수가 n+m인 릴레이션R 과 차수가 m인 릴레이션S 의 디비전 R / s는 차수가 n이 되고,
  S에 속하는 모든 튜플 u에 대하여 tu가 R에 존재하는 튜플 t들의 집합

릴레이션R % 릴레이션S 로 표현

조인(Join)

• 두 개의 릴레이션으로부터 연관된 튜플들을 결합하는 연산자이다.
  관계형 데이터베이스에서 두 개 이상의 릴레이션들의 관계를 다루는데 매우 중요한 연산자
• 세타 조인, 동등 조인, 자연 조인, 외부 조인 등이 있다.

오늘은 이렇게 데이터베이스의 관계대수에 대해 알아보았습니다.

이외에 전체적인 CS주제들은 https://github.com/HongEunho 와 https://github.com/MLifeFam/cs_interview 에 정리되어 있습니다.

데이터베이스 키(Key)

데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때, 다른 튜플들과 구별 할 수 있는 유일한 기준이 되는 속성

키(key)의 특징

Key의 특징으로는 다음과 같은 종류가 있다.

이 특징들은 Key의 종류에 따라 만족하는 경우도 있고, 그렇지 않은 경우도 있다.

• 유일성 : 유일한 값을 가져야 함.
• 최소성 : 최소한의 값으로 식별할 수 있어야 함.
• 불변성 : 변하는 값이어선 안 됨.

키(Key)의 종류

키의 종류에는 슈퍼키, 후보키, 기본키, 대체키, 외래키가 있다.

다음의 릴레이션을 예시로 종류 별로 알아보도록 하자.

슈퍼키

• 유일성 O , 최소성 X
• 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키. 
• 유일성을 만족하므로 릴레이션을 구성하는 모든 튜플 중 슈퍼키로 구성된 속성의 집합과 동일한 값은 나타나지 않는다.

<학생> 릴레이션에서는 학번, 주민등록번호, [학번, 주민등록번호], [학번, 주민등록번호, 이름] 등이 슈퍼키이다.

후보키

• 유일성 O , 최소성 O
• 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분집합
• 최소성을 만족하므로 최소의 개수로 이루어져야 한다.

<학생> 릴레이션에서는 학번, 주민등록번호가 후보키 이며
<수강> 릴레이션에서는 [학번, 과목명]으로 조합해야 유일성과 최소성을 만족하므로 [학번, 과목명] 이 후보키가 된다.

기본키

• 후보키 중 선택받은 키
• 후보키의 성질을 가지므로 유일성과 최소성을 만족한다
• NULL 값과 중복된 값을 가질 수 없다.

<학생> 릴레이션에서의 후보키인 학번이나 주민등록번호 중에 하나를 기본키로 설정할 수 있고,
<수강> 릴레이션에서는 [학번, 과목명] 을 기본키로 설정 할 수 있다.

대체키

• 후보키 중 선택받지 못한 키

<학생> 릴레이션에서 학번이 기본키가 된다면 주민등록번호는 대체키가 된다.

외래키

• 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합
• 릴레이션 간의 관계를 표현할 때 사용한다
• 참조 릴레이션의 기본키와 동일한 키 속성을 가진다

<수강> 릴레이션의 학번은 <학생> 릴레이션의 기본키인 학번을 참조하고 있으므로,
<수강> 릴레이션에서 학번은 외래키가 된다.

이로써 <학생> 릴레이션과 <수강> 릴레이션이 학번을 기준으로 관계가 설정된 것이라 할 수 있다.

외래키가 필요한 이유?!

외래키의 존재 이유는 데이터 무결성 때문이다.

여기서 무결성이란, 데이터가 항상 정확한 값을 유지하는 성질을 의미한다.
예를 들어 학생 릴레이션의 학번이 변경되었을 때, 수강 릴레이션의 학번 값이 변경되지 않는다면 무결성이 깨지게 된다.

마치며..

오늘은 이렇게 데이터베이스의 키에 대해 알아보았습니다.

이외에 전체적인 CS주제들은 https://github.com/HongEunho 와 https://github.com/MLifeFam/cs_interview 에 정리되어 있습니다.

데이터베이스

• 데이터베이스는 일반적으로 컴퓨터 시스템에 전자적으로 저장되는 구조화된 정보
  또는 데이터의 조직화된 모음이다.
• 데이터베이스는 데이터베이스 관리 시스템(DBMS)에 의해 제어된다.
• 데이터베이스는 다음의 4가지 특징을 갖는다.
  • 실시간 접근 (real-time accessibility)
  • 계속 변화 (continuous evolution)
  • 동시 공유 (concurrent sharing)
  • 내용으로 참조 (content reference)
• 주로 사용되는 데이터베이스의 종류로 크게 2가지가 있다.
  • 관계형 데이터베이스
    • 행과 열로 구성된 테이블간의 관계를 나타내며, SQL을 통해 관리한다.
    • MySQL, Maria DB, MS-SQL 등이 있다.
  • NoSQL
    • 관계형 데이터 베이스의 한계를 극복하기 위한 데이터 저장소의 새로운 형태로, 수평적 확장성을 갖고 있다.
    • Mongo DB, Cassandra 등이 있다.

데이터

• 데이터베이스의 가장 중요한 목적은 데이터를 모아두는 것이다.
• 데이터는 형태에 따라 3가지로 분류할 수 있다.
  • 정형 데이터
    • 구조화된 데이터, 즉 미리 정해진 구조에 따라 저장된 데이터다.
    • 엑셀의 스프레드시트, 관계형 데이터베이스의 테이블
  • 반정형 데이터
    • 구조에 따라 저장된 데이터지만, 정형 데이터와 달리 데이터 내용 안에 구조에 대한 설명이 함께 존재
    • HTML, XML, JSON 등이 반정형 데이터에 속한다.
  • 비정형 데이터
    • 정해진 구조 없이 저장된 데이터다.
    • 소셜 데이터의 텍스트, 영상, 이미지, PDF와 같은 멀티미디어 데이터가 비정형 데이터에 속한다.

데이터베이스 관리 시스템(DBMS)

• 데이터베이스 관리 시스템 등장 이전에 사용되던 파일 시스템의 데이터 중복과 데이터 종속 문제를 해결하기 위해 제시된 소프트웨어이다.
• 응용 프로그램을 대신하여 데이터베이스에 들어 있는 데이터를 삽입, 삭제, 수정, 검색하고, 모든 응용 프로그램이 데이터베이스를 공유할 수 있게 한다.

SQL (Structured Query Language)

• SQL은 데이터를 조작 및 제어하기 위해 거의 모든 관계형 데이터베이스에서 사용되는 프로그래밍 언어이다.

스키마 (Schema)

• 스키마는 데이터베이스에 저장되는 데이터의 구조와 제약조건에 관해 전반적인 명세를 기술한 것이다.
  즉, DB내에 어떠한 구조로 데이터가 저장되는지를 나타내는 데이터베이스의 구조이다.
• 데이터베이스의 복잡한 내부 구조를 감추고 일반 사용자가 데이터베이스를 쉽게 이해하고 이용할 수 있도록 하기 위해, 사용자의 관점에 따라 세 가지로 분류한다.
  1. 외부 스키마
     
     • 프로그래머나 사용자 입장에서 데이터베이스의 모습으로 조직의 일부분을 정의한 것
     • 전체 데이터베이스의 한 논리적인 부분이므로 서브 스키마 라고도 한다.
     • 하나의 데이터베이스 시스템에는 여러개의 외부 스키마가 존재할 수 있고, 하나의 외부 스키마를 여러개의 응용 프로그램이나 사용자가 공용할 수도 있다.
     • 일반 사용자는 질의어(SQL)을 통해, 응용 프로그래머는 C, JAVA등의 언어를 통해 접근한다.
  2. 개념 스키마
     
     • 모든 응용 시스템과 사용자들이 필요로하는 데이터를 통합한 조직 전체의 데이터베이스 구조를 논리적으로 정의한 것
     • 개념스키마는 개체간의 관계와 제약 조건을 나타내고 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의한다.
     • 데이터베이스 파일에 저장되는 데이터의 형태를 나타내는 것으로, 단순히 스키마(Schema)라고 하면 개념 스키마를 의미한다.
  3. 내부 스키마
     
     • 전체 데이터베이스의 물리적 저장 형태를 기술하는 것으로, 물리적 저장장치의 관점에서 본 데이터베이스 구조이다.
     • 내부스키마는 실제로 데이터베이스에 저장될 레코드의 물리적인 구조를 정의하고, 저장 데이터 항목의 표현방법, 내부 레코드의 물리적 순서 등을 나타낸다.
     • 시스템 프로그래머나 시스템 설계자가 보는 관점의 스키마이다.

릴레이션 (Relation)

• 관계형 데이터 모델에서는 하나의 개체에 관한 데이터를 하나의 릴레이션에 담아 데이터베이스에 저장한다.
  즉, DB에서 릴레이션은 DB 테이블을 뜻한다.
• 릴레이션과 관련된 용어들은 다음과 같다.
  • 속성 (attribute)
    • 릴레이션의 열을 속성이라고 부른다.
    • 각 속성은 서로 다른 이름을 이용해 구별한다.
    • 릴레이션은 파일 관리 시스템에서의 파일, 속성은 필드에 대응하는 개념이다.
  • 튜플 (tuple)
    • 릴레이션의 행을 튜플이라고 부른다.
    • 튜플은 파일 관리 시스템에서 해당 파일의 레코드에 대응하는 개념이다.
  • 도메인 (domain)
    • 릴레이션에 포함된 각각의 속성들이 가질 수 있는 원자값들의 집합이다.
    • 예를 들어 속성의 값으로 Red, Green, Blue, White 중 하나만 허용될 때, 이 4가지 값을 모아놓은 것이 속성의 도메인이 된다.
  • 차수 (degree)
    • 하나의 릴레이션에서 속성의 전체 개수를 릴레이션의 차수라고 한다.
    • 모든 릴레이션은 최소 1 이상의 차수를 유지해야 한다.
    • 릴레이션의 차수는 일반적으로 자주 변하지 않는다는 정적인 특징이 있다.
  • 카디널리티 (cardinality)
    • 하나의 릴레이션에서 튜플의 전체 개수를 릴레이션의 카디널리티 라고 한다.
    • 튜플이 없는 릴레이션이 존재할 수도 있다.
    • 릴레이션의 카디널리티는 일반적으로 자주 변한다는 동적인 특징이 있다.

마치며..

오늘은 이렇게 데이터베이스의 기본 용어들에 대해 알아보았습니다.

이외에 전체적인 CS주제들은 https://github.com/HongEunho 와 https://github.com/MLifeFam/cs_interview 에 정리되어 있습니다.

Context(문맥 / 콘텍스트)

컨텍스트는 사용자와 다른 사용자, 혹은 사용자와 시스템 또는 디바이스 간의 상호작용에 영향을 미치는 사람, 장소, 개체 등의 현재 상태를 규정하는 정보들이다.

OS에서의 컨텍스트는 CPU가 해당 프로세스를 실행하기 위한 해당 프로세스의 정보들이다.

이러한 컨텍스트는 프로세스의 PCB(Process Control Block)에 저장된다.

PCB(Process Control Block)

PCB란 운영체제가 프로세스에 대한 중요한 정보를 저장해 놓을 수 있는 저장 장소를 뜻한다.

PCB는 프로세스 생성 시 만들어지며 주기억장치에 유지된다. 프로세스 상태 관리와 컨텍스트 스위칭을 위해 필요하다.

위 이미지는 PCB의 정보 저장 구조에 관한 이미지이고 PCB에는 다음과 같은 정보가 저장된다.

• 프로세스 상태 : 생성, 준비, 수행, 대기, 중지
• 프로그램 카운터 : 프로세스가 다음에 실행할 명령어 주소
• 레지스터 : 누산기, 스택, 색인 레지스터
• 프로세스 번호

Context Switching(문맥교환 / 콘텍스트 스위칭)

컴퓨터가 매번 하나의 Task만 처리할 수 있다면?

=> 해당 Task가 끝날 때까지 다음 Task는 기다려야 함

=> 그렇다면 매우 느린 속도 때문에 사용하기 불편할 것.

이를 해결하기 위해 Context Switching이 등장.

다양한 사람들이 동시에 사용하는 것처럼 하기 위해서는 빠른 속도로 Task를 바꿔 실행해 실시간처럼 보이도록 해야 했고, CPU가 Task를 바꿔가며 실행하기 위해 Context Switching이 필요하게 되었다.

또한 새로 실행되는 Task가 아니라면 이전에 실행될 때 레지스터들이 지니고 있던 데이터들을 불러와서 이어서 실행해야 하므로 컨텍스트 스위칭이 필요하게 되었다.

Context Switching이란 멀티프로세스 환경에서 CPU가 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선순위 프로세스가 실행돼야 할 때 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(Context)를 교체하는 작업이다.

Context Switching의 순서

1. 실행 중지할 프로세스 정보를 해당 프로세스의 PCB에 업데이트하여 메인 메모리에 저장
2. 다음 실행할 프로세스 정보를 메인 메모리에 있는 해당 PCB 정보를 CPU에 넣고 실행

Context Switching의 단점

• 프로세스가 변경되는 과정에서 데이터를 서로 백업하기 때문에 CPU의 과부하가 생길 수 있다.
• 컨텍스트 스위칭이 잦으면 오버헤드가 발생하여 성능이 떨어질 수 있다.

오늘은 이렇게 Context Switching에 대해 알아보았습니다.

이외에 전체적인 CS주제들은 https://github.com/HongEunho 에 정리되어 있습니다.

팔로우 & 맞팔 환영입니다!

중앙처리장치(CPU)란?

중앙처리장치(CPU)는 명령어의 해석과 자료의 연산, 비교등의 처리를 제어하는 컴퓨터 시스템의 핵심장치이다.

다양한 입력 장치로부터 정보를 입력받아 처리한 후, 그 결과를 출력장치로 보내는 일련의 과정을 제어하고 조정하는 일을 수행한다.

CPU는 사람의 두뇌와 같이 컴퓨터의 모든 시스템을 제어, 처리하는 가장 핵심적인 장치라고 할 수 있다.

CPU의 구성요소

CPU는 크게 제어 장치, 연산 장치(ALU), 레지스터 와 각 구성 요소를 연결하는 내부 버스로 구성되어 있다.

1. 제어 장치 (CU, Control Unit)

• 컴퓨터 시스템의 작동을 통제하고 지시하는 장치
• 기억 장치로부터 프로그랭 명령을 순차적으로 꺼내 해독하고, 해석에 따라서 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력 장치 등으로 보내는 장치
• 프로그램 카운터(PC), 명령 해독기, 부호기, 명령 레지스터 등으로 구성된다.

2. 연산 장치 (ALU, Arithmetic and Logical Unit)

• 명령어를 실행하기 위한 마이크로 연산을 수행하는 장치
• 연산에 필요한 자료를 입력받아 산술, 논리, 관계, 이동(Shift) 등 다양한 연산을 수행하는 장치
• 가산기, 보수기, 누산기, 데이터 레지스터 등으로 구성된다.

3. 레지스터 (Register)

• CPU(중앙 처리 장치)내에 있는 소규모의 고속 기억장치
• 명령어 주소, 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장한다.
• 레지스터는 메모리 계층의 최상위에 위치하며 가장 빠른 속도로 접근 가능한 메모리이다.
• 용도에 따라 범용 레지스터와 특수 목적 레지스터로 구분됨

특수 목적 레지스터의 종류

• MAR (메모리 주소 레지스터) : 읽기와 쓰기 연산을 수행할 주기억장치 주소를 저장
• PC (프로그램 카운터) : 다음에 실행될 명령어의 주소를 저장
• SP (스택 포인터) : 스택의 최상위 주소를 저장
• IX (인덱스 레지스터) : 인덱스 주소 지정 방식에서 인덱스를 저장
• IR (명령어 레지스터) : 명령어를 호출해서 해독하기 위해 현재 명령어를 임시로 저장
• MBR (메모리 버퍼 레지스터) : 주기억장치의 내용을 임시로 저장하는 역할
• AC (누산기) : 산술 논리 장치의 연산 결과를 임시로 저장
• PSR (프로그램 상태 레지스터) : CPU의 현재 상태 정보를 저장

CPU의 연산

CPU의 연산 순서는 Fetch -> Decode -> Execute -> Writeback 으로 이루어지며 각 과정의 설명은 다음과 같다.

1. Fetch(인출) : 메모리상의 프로그램 카운터(PC)가 가리키는 명령어를 CPU로 인출하여 적재

2. Decode(해석) : 명령어의 해석. 이 단계에서 명령어의 종류와 타겟 등을 판단한다.

3. Execute(실행) : 해석된 명령어에 따라 데이터에 대한 연산을 수행한다.

4. Writeback(쓰기) : 명령어대로 처리 완료된 데이터를 메모리에 기록한다.

CPU의 동작 과정

(1) 보조기억장치에서 저장된 프로그램을 읽거나, 입력장치에서 입력받은 데이터를 주기억장치에서 읽는다.

(2) 주기억장치에서 읽어온 데이터를 중앙처리장치(CPU)가 읽고 처리한 후 다시 주기억장치로 보낸 후 저장한다.

(3) 주기억장치는 연산된 데이터를 출력장치에 보내거나 보조기억장치에 저장한다.

(4) 제어장치는 (1)-(3) 과정에서 명령어가 순서대로 잘 실행되도록 제어하는 역할을 수행한다.

CPU의 명령어

명령어 세트

연산 코드 (OP Code) | 피연산자 (Operand)

명령어 세트는 CPU가 실행할 명령어의 집합이다.

명령어 세트는 실행할 연산을 나타내는 연산 코드 (Operation Code)와 연산에 필요한 데이터나 데이터의 저장 위치를 나타내는 피연산자 (Operand)로 구성된다.

연산 코드 (Operation Code)

연산 코드는 실행하는 연산의 종류에 따라 다음과 같이 네 가지 기능으로 나뉜다.

• 연산 기능 : 사칙연산, 이동(shift), 보수 등의 산술연산과 논리곱, 논리합, 부정 등의 논리연산을 수행한다.
• 제어 기능 : 조건 분기와 무조건 분기 등을 사용하여 명령어의 실행 순서를 제어한다.
• 데이터 전달 기능 : 레지스터와 레지스터 사이, 레지스터와 주기억장치 사이에서 데이터를 전달한다.
• 입출력 기능 : 프로그램과 데이터를 주기억장치에 전달하고, 연산 결과는 출력장치에 전달한다.

피연산자 (Operand)

피연산자에는 주소, 숫자/문자, 논리 데이터 등을 저장할 수 있다.

• 주소 : 기억장치 혹은 레지스터의 주소가 저장된다.
• 숫자/문자 : 숫자는 정수, 고정 소수점 수, 부동 소수점 수 및 각각의 코드로 저장되고 문자는 아스키코드로 저장된다.
• 논리 데이터 : 참 또는 거짓을 표현할 때 사용하며 비트나 플래그로 저장된다.

명령어 사이클

CPU에서는 프로그램을 실행하기 위해 주기억장치에서 명령어를 순차적으로 인출하여 해독하고 실행하는 과정을 반복하는데, CPU가 주기억장치에서 한 번에 하나의 명령어를 인출하여 실행하는데 필요한 일련의 활동을 명령어 사이클 (Instruction Cycle)이라고 한다.

명령어 사이클은 인출 사이클, 실행 사이클, 간접 사이클, 인터럽트 사이클로 세분화 시킬 수 있는데, 인출 사이클과 실행 사이클은 항상 수행되지만 / 간접 사이클과 인터럽트 사이클은 주소 지정방식이 필요할 때나 인터럽트 요구가 있을 때만 수행된다.

인출 사이클과 특수 목적 레지스터의 동작 과정

1. 프로그램 카운터(PC)에 저장된 주소를 메모리 주소 레지스터(MAR)로 전달 한다.
2. 메모리 주소 레지스터(MAR)에 저장된 내용을 토대로 주기억장치의 해당 주소에서 명령어를 인출한다.
3. 인출한 명령어를 메모리 버퍼 레지스터(MBR)에 저장한다.
4. 다음 명령어를 인출하기 위해 프로그램 카운터 (PC)의 값을 증가 시킨다.
5. 메모리 버퍼 레지스터(MBR)에 저장된 내용을 명령어 레지스터(IR)에 전달한다.

위의 과정을 다음과 같이 표현하기도 한다.

T0 : MAR <- PC
T1 : MBR <- M[MAR], PC <- PC + 1
T2 : IR <- MBR

다음은 인출 사이클로부터 명령어를 인출한 이후 명령어를 실행하는 과정인 실행 사이클의 과정이다.

그 중에서도 더하기(ADD) 연산으로 과정을 살펴보자.

실행 사이클과 특수 목적 레지스터의 동작 과정

1. 명령어 레지스터(IR)의 내용을 메모리 주소 레지스터(MAR)로 전달한다.
2. 메모리에 저장된 데이터 값을 메모리 버퍼 레지스터(MBR)에 저장한다.
3. 누산기(AC)에 저장된 값에 ADD연산을 실행한다.

실행 사이클도 인출 사이클과 마찬가지로 다음과 같이 표현 할 수 있다.

ADD addr 명령어 연산

T0 : MAR <- IR(Addr)
T1 : MBR <- M[MAR]
T2 : AC <- AC + MBR

실행 사이클에서는 프로그램 카운터를 증가시키지 않는 이유
인출 사이클과 다르게 실행 사이클에서는 프로그램 카운터(PC)를 증가시키지 않는데, 이미 인출이 진행 되고 명령어 실행만 하면 되는 상황이기 때문에 프로그램 카운터를 증가시킬 필요가 없다.
즉, 이미 인출이 되어 명령어 레지스터(IR)에 메모리 버퍼 레지스터(MBR)의 값이 저장된 상태라는 의미이다.

오늘은 운영체제 중에서도 가장 중요하다고 꼽히는 프로세스와 스레드 및 차이점에 대해 알아보자.

먼저, 프로세스와 스레드를 알아보기 전에 프로그램 이라는 개념에 대해 알아야 한다.

프로그램

프로그램이란, 파일이 저장 장치에 저장되어 있지만 메모리에는 올라가지 않은 정적인 상태를 말한다.

즉, 메모리에 올라가지 않은 상태이기 때문에 아직 운영체제로부터 독립적인 메모리 공간을 할당받지 않은 상태이며

정적인 상태이기 때문에 아직 실행되지 않고 가만히 있는 상태이다.

즉, 그냥 코드 덩어리 라고 할 수 있다.

그럼 이를 인지한 후, 본격적으로 프로세스와 스레드에 대해 알아보자.

프로세스

프로세스란, 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램이다.

컴퓨터에서 실행되고 있다는 것은 운영체제로부터 독립적인 메모리 공간을 할당받았다는 것이며,

실행되고 있기 때문에 동적인 상태이다.

아래 그림은 프로세스를 나타낸 모습이다.

• 프로세스의 각각의 영역에 대한 설명
  • Code : 코드 자체를 구성하는 메모리 영역 (프로그램 명령)
  • Data : 전역 변수, 정적 변수, 배열 등의 데이터 (초기화된 데이터)
  • Stack : 지역 변수, 매개 변수, 리턴 값 등의 임시 데이터 (임시 메모리 영역)
  • Heap : 동적 할당 시 사용 (new(), malloc() 등)
• 프로그램 -> 프로세스 를 그림으로 표현하면 다음과 같다.
• 즉, 프로그램은 코드 덩어리 파일이며 이 프로그램을 실행한 것이 바로 프로세스 이다.
• 프로세스의 특징
  • 프로세스는 각각 독립된 메모리 영역(Code, Data, Stack, Heap)을 가진다.
  • 프로세스당 최소 1개의 스레드(메인 스레드)를 가지고 있다.
  • 각각의 프로세스는 별도의 주소 공간에서 실행되고, 기본적으로 서로 다른 프로세스의 자원에 접근할 수 없다. (운영체제에서 안전성을 위해 이렇게 설계됨)
  • 다른 프로세스의 자원에 접근하기 위해서는 프로세스 간 통신(IPC)을 이용해야 한다.

그럼 다음으로, 프로세스 내에 존재하는 스레드에 대해 알아보자.

스레드

스레드란, 프로세스 내에서 실행되는 여러 흐름의 단위 이다.

즉, 프로세스의 특정한 수행 경로이며, 프로세스가 할당받은 자원을 이용하는 실행의 단위 이다.

• 프로세스 내에서 Stack만 따로 할당받고, Code, Data, Heap영역은 공유하는 스레드

스레드는 프로세스의 공유적인 한계점을 극복하기 위해 만들어진 개념이기 때문에, 프로세스와는 달리 서로 메모리를 공유한다.

즉, 스레드 끼리는 프로세스의 자원을 공유하며 프로세스 실행 흐름의 일부가 되는 것이다.

• 스레드의 특징
  • 스레드는 프로세스 내에서 Stack만 각각 따로 할당받고 Code, Data, Heap 영역은 공유한다.
  • 프로세스 내의 주소 공간이나 자원들을 같은 프로세스 내의 스레드 끼리 서로 공유한다.
  • 한 스레드가 프로세스 자원을 변경하면, 다른 스레드(Sibling Thread)도 그 변경된 결과를 즉시 볼 수 있다.

지금까지 살펴본 프로그램과 프로세스와 스레드의 개념을 코드에 비유하여 정리해보면

• 프로그램은 아직 실행되지 않은 실행 파일로써 코드 덩어리라고 볼 수 있고
• 프로세스는 이러한 프로그램(코드 덩어리)을 실행한 것 이라고 볼 수 있고
• 스레드는 이 코드의 일부분(main문, 함수 등) 으로 볼 수 있다.

이제, 앞에서 살펴본 내용을 토대로 멀티프로세스와 멀티스레드에 대해 정리해보며 마무리를 하려고 한다.

멀티 프로세스

멀티 프로세스란, 하나의 응용프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나 이상의 작업을 동시에 처리하도록 하는 것이다.

쉽게 말하면 하나의 컴퓨터에 여러개의 CPU가 장착되어, 하나 이상의 프로세스들을 동시에 처리(병렬 처리) 하는 개념이다.

멀티 프로세스의 장점과 단점은 다음과 같다.

• 장점
  • 독립된 구조이기 때문에 안전성이 높다.
  • 프로세스 중 하나의 프로세스에 문제가 생겨도, 다른 프로세스에는 영향을 주지 않는다.
• 단점
  • 독립된 구조이기 때문에 Context Switching으로 인한 오버헤드가 발생하여 성능저하가 발생한다.
  • 프로세스는 각각의 독립된 메모리 영역을 할당받기 때문에 프로세스 끼리 공유하는 메모리가 없으므로, Context Switching 과정에서 캐시 메모리 초기화 등의 무거운 작업이 진행된다.

멀티 스레드

하나의 프로세스를 여러 스레드로 자원을 공유하며 작업을 나누어 수행하는 것이다.

윈도우나 리눅스 등의 운영체제들이 멀티 프로세싱을 지원하고 있으며, 멀티 스레딩을 기본으로 하고 있다.

• 장점
  • 시스템 자원소모 감소(자원의 효율성 증대)
  • 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리
  • 시스템 처리율 향상(처리비용 감소)
  • 스레드 간 데이터를 주고 받는 것이 간단하며, Context Switching이 빠름
  • 간단한 통신방법으로 인한 프로그램 응답 시간 빠름
  • 스레드는 프로세스 내의 Stack영역을 제외한 메모리 공간을 공유하기 때문에 통신이 빠름
• 단점
  • 자원 공유시, 잘못된 변수 공유나 미묘한 시간차로 인한 오류 발생 가능
  • 동기화 문제로 인한 데드락(병목 현상) 발생 가능
  • 하나의 스레드에 문제가 생기면 프로세스 전체에 영향을 줌
  • 디버깅이 어려우며 주의 깊은 설계가 필요함

이렇게 오늘은 프로세스와 스레드에 대해 알아보았다.

혹시 SW면접을 준비하고 있다면 프로세스와 스레드의 차이점들을 명확히 알아두는 것을 추천한다.

이외의 CS 다른 주제들은 https://github.com/HongEunho 과 https://hongcoding.tistory.com에 정리되어 있습니다!

그래프란?

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다.

정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다.

이러한 면에서 트리는 그래프의 일종인 셈이다.

하지만 그래프는 트리와는 달리 정점마다 간선이 있을 수도 있고 없을 수도 있으며, 루트노드와 부모와 자식이라는 개념이 존재하지 않는다.

그래프와 트리의 차이점에 대해서는 아래의 표로 좀 더 자세하게 설명하겠다.

그래프와 트리의 차이

그래프와 관련된 용어

• 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
• 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.
• 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 (0과 2은 인접정점)
• 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우. 한붓그리기와 같이 같은 간선을 지나가지 않는 경로 ( 0->3->2->1 은 단순경로 )
• 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3)
• 진출 차수(in-degree) : 방향 그래프에서 외부로 향하는 간선의 수
• 진입 차수(out-degree) : 방향 그래프에서 외부에서 들어오는 간선의 수
• 경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
• 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 구현 방법

그래프를 구현하는 방법에는 인접행렬과 인접리스트 방식이 있다. 두 개의 구현방식은 각각의 상반된 장단점을 가지고 있다.

• 인접행렬 방식
  
  인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.
  노드들 간에 직접 연결이 되어있으면 1을, 아니면 0을 넣어서 행렬을 완성시킨 것이다.
  
  
• 인접행렬의 장점
  • 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
  • 인접리스트에 비해 구현이 쉽다.
• 인접행렬의 단점
  • 모든 정점에 대해 간선 정보를 대입해야 하므로 $O(n^2)$ 의 시간복잡도가 소요된다.
  • 무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다.
    

    ---

• 인접리스트 방식
  인접리스트는 그래프의 노드를 리스트로 표현한 것이다.
  
  주로 정점의 리스트 배열을 만들어 관계를 설정하며 노드들 간에 직접 연결이 되어있으면 해당 노드의 인덱스에 그 노드를 삽입해주면 된다.
  
  즉, 1에는 2와 3이 직접 연결되어 있기 때문에 배열의 1번째 칸에 2와 3을 넣어준다.

• 인접리스트의 장점
  1. 정점들의 연결 정보를 탐색할 때 O(n) 시간이면 가능하다.
  2. 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
• 인접리스트의 단점
  1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. (O(E) 시간 소요. E는 간선의 개수)
  2. 구현이 비교적 어렵다.

그래프의 종류

• 무방향 그래프(Undirected Graph)
  무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.

• 방향 그래프(Directed Graph)
  방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다.
  간선의 방향으로만 이동할 수 있다.
  

  

• 가중치 그래프(Weighted Graph)
  가중치 그래프는 간선에 가중치(비용)가 할당된 그래프로, 두 정점을 이동할 때 비용이 드는 그래프이다.
  

  

• 연결 그래프(Connected Graph)
  무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 그래프
  즉, 노드들이 하나도 빠짐없이 간선에 의해 연결되어 있는 그래프로 트리(Tree)가 대표적인 예이다.
  

  

• 비연결 그래프(Disconnected Graph)
  
  무방향 그래프에서 특정 정점 사이에 경로가 존재하지 않는 그래프
  즉, 노드들 중 간선에 의해 연결되어 있지 않은 그래프이다.
  
  

  

• 완전 그래프(Complete graph)
  그래프의 모든 정점이 서로 연결되어 있는 그래프이다. (인접 연결)
  
  

  

• 순환그래프(Cycle)
  
  단순 경로에서 시작 정점과 도착 정점이 동일한 그래프이다. (A에서 시작-> A에서 끝 가능)
  
  

  

• 비순환그래프(Acyclic Graph)
  
  사이클 그래프를 제외한 그래프로, 사이클이 없는 그래프이다.
  
  

  

• 신장트리(Spanning Tree)

원래 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프

트리의 속성을 만족하기 때문에 사이클이 존재하면 안된다.

• 최소 신장트리(Minimum Spanning Tree)
  
  신장트리(Spanning Tree)중 간선의 가중치 합이 최소인 신장 트리
  
  

면접에서 나올 수 있는 질문

• 인접행렬과 인접리스트의 차이점과 각각의 장단점에 대해 이야기 해보세요
• 연결그래프와 완전그래프의 차이점에 대해 이야기 해보세요
• (원래 그래프의 그림을 주고) 이 그래프로 신장 트리 N개를 만들어 보세요
• 최소신장트리를 찾을 수 있는 알고리즘에 대해 설명해주세요
• -> https://velog.io/@dnjscksdn98/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC 참고

참고 자료

• 코딩팩토리님 블로그
• heejeong Kwon님 블로그
• gimtommang11님 블로그
• dnjscksdn98님 블로그

기여자

_HongEunho
📦