DB 설계 규칙 정리

DB 네이밍 규칙 테이블명, 컬럼명은 소문자로 작성하고 snake_case를 사용한다. 테이블명은 복수형을 사용하자. (선택사항) 여러 개 데이터를 가지고 있음을 표현 회사마다 규칙이 갈리므로, 복수형이든 단수형이든 일관성 있게만 사용하면 됨 축약어를 사용하지 않는다. SQL문은 예약어만 대문자로 작성하자. (SELECT, FROM, WHERE…) DB 설계 핵심 원칙 핵심 원칙: 중복 없애기 (정규화) 데이터 간 모순(이상 현상)의 근본적 원인은 데이터 중복이고, 정규화는 데이터 중복을 제거 e.g. 두 테이블에 작성자 컬럼이 있는데, 모두 수정하다가 한 데이터를 빼먹으면 갱신 이상 발생 DB 설계 과정 저장해야 하는 데이터 파악하기 대략적인 UI 디자인 기획을 보고 필요한 데이터 파악 가끔 글로만 정리된 요구사항이 있을 수 있지만, 놓치는 부분이 생길 수 있어 좋지 않은 방식 기준: 나중에 조회해서 쓸 일이 있겠다 싶은 데이터를 전부 저장 그룹핑해서 분류하기 관련 있는 것들끼리 묶어 상위 개념을 찾음 (= 엔터티 = 테이블) 따로 법칙이 있다기보다 인간이 모두 가지고 있는 보편적인 분류 능력을 따르자 e.g. 아이디, 패스워드, 이름, 이메일 → 사용자 (엔터티) 영화 이름, 영화에 출연한 배우, 영화 상영 시간 → 영화 (엔터티) 게시글 제목, 게시글 내용, 게시글 생성 시간 → 게시글 (엔터티) 6가지 규칙을 적용하며 테이블 분리해나가기 유의점 데이터 예시를 입력하며 파악하자 규칙 1 + 규칙 2의 결과는 규칙 3의 결과 동일 (무얼 선택해도 괜찮음!) 처음에 완벽한 설계가 안돼도 추후 데이터 중복을 발견해 수정 가능하니 불안해하지 말자 연관 관계 파악 관련 규칙 규칙 1: 한 칸에 한 가지 정보만 들어가야 한다 (제1정규형) 한 칸에 두 가지 정보가 있을 시, 테이블을 분리하고 FK를 적용 FK 적용이 규칙 1을 어길 경우, 반대쪽 테이블에도 FK를 적용해보자 ‘한 가지 정보’의 기준은 절대적이지 않아서, 자신의 서비스에 맞게 판단해야 함 e.g. 손/흥민 or 손흥민, 01012341234 or 010/1234/1234 규칙 2: 어떤 테이블에 FK를 넣어도 ‘규칙 1’을 못 지킬 때는 중간 테이블을 하나 더 만들자 양쪽 테이블의 FK를 중간 테이블로 옮기기 중간 테이블의 이름은 동사를활용하면 좋음 (직관성, 가독성 상승) e.g. students & courses -> course_registrations {id(PK), student_id(FK), course_id(FK)} movies & actors -> casting {id(PK), movie_id(FK), actor_id(FK)} 규칙 3: 헷갈릴 땐 연관 관계를 파악해보자 (1:1, 1:N, N:M) 판단 방법 엔터티 간에 어울리는 동사를 찾기 (A가 B를 ___.) e.g. 사용자가 이메일을 소유한다. 이메일은 사용자에 의해 소유되어진다. 적절한 단어 찾기 (하나의 or 여러개의) e.g. ‘하나의’를 고정해서 따져보기 하나의 사용자는 ___ 이메일을 소유한다. 하나의 이메일은 ___ 사용자에 의해 소유되어진다. 관계 파악하기 (1:1, 1:N, N:M) e.g. 사용자와 이메일은 1: N 관계 1:N 관계 N 쪽 테이블에 FK 들어가야 함 N:M 관계 중간 테이블이 있어야 하고, 중간 테이블에 두 테이블의 FK가 들어가야 함 (1:N으로 해소) 1:1 관계 아무 테이블에 FK를 넣어도 됨 합쳐도 되는지 고려해보자 (왠만하면 1:1 관계로 분리하지 않는 걸 추천) 통쨰로 조회하는 일이 많다면 합치는게 좋음 만약 각각 따로 조회할 일이 많다면 분리하는게 좋음 중복 없애기 관련 규칙 규칙 4: 데이터 중복이 발생하는 컬럼이 있는지 확인하자 임의의 데이터를 넣고 시뮬레이션해서 데이터 중복 발생 여부 파악 e.g. 게시물 테이블의 작성자 데이터가 중복됨 중복이 있다면 테이블 분리하고 FK 적용 수정 포인트가 하나가 되므로, 갱신 이상 여지가 사라짐 규칙 5: 가짜 중복과 진짜 중복 구별하기 실제 서비스에서 A 데이터 값을 수정하면, B 데이터 값도 같이 수정되어야 하는가? e.g. id 1 게시물의 작성자를 수정하면, id 2 게시물의 작성자도 수정해야 하나? 같이 수정되어야 하면 진짜 중복, 아니라면 가짜 중복 진짜 중복인 경우 테이블 분리해야 함 규칙 6: 숨어있는 중복을 찾아라 숨어 있는 중복 겉으로는 중복이 아닌 것 같지만, 무언가 수정해야할 때 같이 수정해야 하는 경우 e.g. users & posts -> likes (중간 테이블) 좋아요를 제거할 때, 게시글의 좋아요 수도 같이 수정해야 함 주로 통계치(합계, 평균, 최대값 등)를 낼 때 발생 해결 방법: 테이블에서 통계치 칼럼을 없애야 함 e.g. 좋아요 수 없애기 좋아요 수를 알고 싶다면, 좋아요 테이블에서 필터링하여 개수 카운팅하자 DB 설계 반영 지침 최대한 정규화를 지켜서 DB 설계하자 정규화 적용하지 않은 케이스의 의견들 정규화를 지키면 테이블 개수가 많아져서 관리가 불편해요. → 데이터 중복으로 인해 발생하는 단점들이 훨씬 크고 관리하기가 더 어렵다. JOIN을 많이 하면 할수록 성능이 안 좋아져서 정규화를 안 했어요. → 실제로 JOIN을 많이 했을 때 성능이 안 좋아지는 경우도 존재한다. 하지만 이렇게 얘기하는 사람치고 실제로 성능 측정해본 사람이 아무도 없다. (추측만 했을 뿐) 즉, 이상 현상 방지에 가장 초점을 두자 데이터 중복으로 인해 실수로 데이터가 잘못 관리되는 문제가 더 큼 성능 개선은 느려지기 전까지 최대한 안 건드리는 게 Best! 필요성을 느낀다면 반드시 ‘측정’을 기반으로 해야 함 역정규화는 정말 구조로 인한 성능 문제가 클 때만 사용하라 ERD 표기 지침 DB 설계 시 ERD 그리는 게 필수가 아니어서, 보고 해석하는 방법 정도만 알아도 충분 홀로할 때는 편하고 빠른 방법으로 진행 (엑셀, A4지…) 협업할 때는 툴 사용 (ERD Clould, dbdiagram…) 1:1 관계인지 1:N 관계인지만 파악할 수 있으면 됨 (그 외 표기는 잘 안쓰임) 데이터 타입 실전 활용 지침 (MySQL 기준) 주요 사용 타입 정수를 저장해야 하는 경우 : INT 10억이 넘어가는 정수를 저장해야 될 수도 있는 경우 : BIGINT 실수를 저장하고 싶은 경우 : DECIMAL 문자를 저장해야 하는 경우 : VARCHAR(글자수) 6만이 넘어가는 문자를 저장해야 하는 경우 : LONGTEXT TimeZone을 고려하지 않고 날짜/시간 데이터만 저장하면 되는 경우 : DATETIME ex) 국내 서비스 TimeZone을 고려하면서 날짜/시간 데이터를 저장해야 하는 경우 : TIMESTAMP ex) 글로벌 서비스 True, False의 형태를 저장하고 싶은 경우 : TINYINT(1) 참고: 숫자는 숫자로 저장할 수도 있고 문자로 저장할 수도 있음 DB 관점에서는 “계산에서 쓰는 값인지 안 쓰는 값인지”를 기준으로 선택 휴대폰 번호는 문자로 저장 (숫자를 더해서 사용하지 않고 단순히 고유의 값으로 사용할 뿐) 주민등록번호도 마찬가지로 문자로 저장 현업에서 잘 사용하지 않는 데이터 타입 : CHAR, FLOAT, DOUBLE, TEXT 등 Reference 비전공자도 이해할 수 있는 DB 설계 입문/실전

Computer Science · 2025-01-15

멀티 스레드와 디자인 패턴

Process & Thread 차이 Thread는 서로 메모리 공유 O 문제 모든 Thread가 하나의 자료구조(e.g. queue)를 공유하면 자료구조가 망가질 것 해결책: 배타제어 (=동기화) Concurrent Class (동시성 컬렉션) Lock 특정 코드 구간을 반드시 한 Thread만 실행하도록 막음 (크리티컬 섹션) Lock을 건 코드 구간의 실행시간이 길수록 성능저하가 발생 최악의 경우 Single Thread가 차라리 나음 One Process, One Thread Architecture가 나온 이유 Redis도 처음에 이 아키텍처를 따름에도 매우 빨라서 인기 얻음 Lock Free Lock을 사용하지 않고 배타제어 관련 키워드: interlocked.increment(), Atomic Operation, Lock-Free 알고리즘, Non-Blocking 알고리즘, CAS(compare and set) Thread Safe하게 일반 Class 사용하기 Write는 한 Thread에서만, Read는 여러 Thread에서 진행하면 유용 Process는 서로 메모리 공유 X 문제 Process끼리는 메모리 공유가 안되기 때문에, 통신이 필요 (HTTP, TCP…) MSA를 지향하는 현대 사회에서는 Process간 통신 필수 MSA = Multi Process Multi Process 필요성 서버 머신 한 대 성능에는 한계, Scale Out 필수! 서버 Architecture 구상하는 입장에서는 Process 하나가 작은 기능을 담는 것이 훨씬 유리 (One Process, One Thread가 설득력 얻는 부분) 언어가 다른 Process끼리는 서로 패킷 주고 받는게 스트레스 해결책: Multi Process 간 통신 방법 서버 간 통신 방법 Google Protobuf, Apache Avro (Good) IDL 파일에 모델을 정의해두면 Java, C++, JS, C# 등 여러 언어에서 사용 가능 JSON (Bad) 필드 추가시 상대방에게 알려주기 어려움 오타로 인한 디버깅 Cost 데이터를 어딘가에 올려놓고 필요한 서버가 알아서 가져가게 하는 방법 Redis Pub/Sub 특정 key에 데이터를 넣고 Pub/Sub Queue 이용하기 (AWS SQS) Queue에 넣고 데이터가 추가됐을 때, 특정 Topic으로 Event 받기 제 3 스토리지를 이용하는 것이므로 상대적으로 느림 빠르게 통신할 필요가 없는 경우 이용 웹서비스는 느리다는 느낌은 안듦 TCP 실시간 통신 서비스는 느리다 느낄 수 있음 Thread Thread란? 흐르는 시냇물 위에 띄워놓은 돛단배 스레드 스타트 이후 계속 원하는 작업들이 진행될 것이고 내 손을 떠나도 계속 돌아감 Entrypoint (진입점) public static void Main(String[] args) {} Process가 맨 처음 실행하는 함수, 함수가 종료되면 Process도 종료 Main Thread에서 실행 쓰레드 사용하기 var thread = new Thread(Func); 스레드 생성 thread.Start(); Thread 생성자에 넣어준 함수를 별도의 스레드에서 실행 thread.Join(); 스레드가 종료될 때까지 대기함 (Blocking) Blocking & Non-Blocking Blocking 함수를 실행하고 모든 코드가 완료된 후 리턴 Non-Blocking 실행한 함수의 코드가 완료되지 않고 리턴 Non-Blocking 함수의 실행과 완료를 아는 방법 Polling 주기적으로 확인하기 어떤 스레드에서 isFinish에 true 값을 넣으면 스레드 실행의 완료를 파악 while(true) { if (isFinish == true) { Break; } sleep(1000); //CPU 100%되지 않게 } e.g. HTTP 통신 Event Event가 발생했을 때 내가 원하는 함수를 호출해줌 setTimeout(callback, 1000); //1초 후 callback 함수 실행 콜백 지옥 유의 (요즘은 async & await 사용) async & await 장점은 무엇인가요? 멀티스레드 프로그래밍(비동기 실행)을 하지만 Blocking 방식으로 진행해서 편함 **콜백지옥 피할 수 있음 ** public async function Task<string> GetString() { ... } string result = await GetString(); Console.Write(result); getString() 함수는 다른 스레드에서 실행되지만 Blocking 방식으로 호출 = 비동기로 실행하지만 Blocking 방식 Server Thread Model 웹 서버, TCP 서버 등 서버 구현에 일반적으로 사용되는 스레드 모델 생산자 소비자 문제와 일치 생산자: I/O 스레드 (혹은 Worker 스레드라 부르기도 함) 네트워크 카드가 요청 데이터를 읽으면, I/O 스레드에서 해당 데이터를 Job Queue로 넘김 네트워크 카드 메모리가 매우 작으므로, 패킷이 가득차지 않게 작업만 빠르게 넘김 웹 서버나 프레임워크가 생산을 처리해 줌 Buffer: Job Queue Job Queue는 메인 메모리에 위치 e.g. 웹이라면 request들이 담김 소비자: Worker Thread (혹은 Logic 스레드라 부르기도 함) Worker Thread가 Job Queue에 작업들을 읽어서 처리 무거운 작업들 실행 (DB 접속, Redis 통신) 무거운 작업이라 오래 걸리지만, 최대한 빨리 실행되도록 해야 함 빨리 동작하지 않으면 Job Queue에 데이터가 차서 서비스 응답이 느려짐 일반적으로 개발자가 짠 로직은 Worker 스레드에서 돌아가는 코드를 짠 것 IOCP, EPoll OS에서 제공하는 비동기 I/O 작업을 하기 위한 기술이다. 즉, I/O 요청을 하면 비동기로 처리해주고 결과도 비동기로 받게 된다. Windows에는 IOCP, Linux에는 Epoll이라는 기능이 이에 해당한다. Guarded Suspension 패턴 할 일이 없는 Thread는 대기열에 넣고 할 일이 생기면 대기열에서 빼서 실행해주는 패턴 작업이 있으면 깨우고 없으면 쉼 Balking 패턴 내가 해야될 작업이 있는지 주기적으로 확인 (반복문) 작업이 있으면 하고 없으면 무시 (RUNNABLE) 스레드가 계속 동작하므로 작업이 없을 때 해야할 동작을 지정할 수도 있음 Read-Write Lock 패턴 Read 락과 Write 락을 따로 두는 락 메커니즘 한 스레드가 Write할 때는 다른 스레드가 Read 및 Write 모두 불가능 한 스레드가 Read할 때는 다른 스레드도 Read 가능 Read 스레드가 많고 Write 스레드가 좀 적다면, Read 성능 효율이 향상 Read 할 때는 Write를 하는지 안하는지만 판단 Read를 더 편하고 자유롭게 할 수 있음 만일, 사용한다면 각 언어에 구현된 클래스 찾아 사용할 것 Thread-Per-Message 패턴 하나의 작업 당 하나의 Thread가 실행하도록 위임 스레드 개수가 너무 많아지면 컨텍스트 스위칭 오버헤드가 높아져 성능 저하 Future 패턴 Main 스레드가 다른 스레드에 작업을 위임하고 본인 스스로도 다른 작업을 할 수 있게 하는 패턴 Thread-Specific Storage 패턴 스레드 마다 별도의 저장 공간을 가지게 하는 패턴 = 스레드 로컬: 각 스레드 별로 사용할 수 있는 변수 Reference Backend 멀티쓰레드 이해하고 통찰력 키우기

Computer Science · 2024-09-29

데이터베이스 첫걸음

Computer Science · 2024-04-29

MySQL 주요 명령

MySQL 주요 관리명령 show status MySQL의 상태에 대한 여러 정보 확인 Threads_connected 커넥션의 상태 및 수 Uptime 서버 가동 후 경과 시간 Queries 실행한 SQL의 수 show databases 데이터베이스 목록 보기 show tables 테이블 목록 보기 show table status 통계정보 보기 show create table 테이블명\G 테이블 정의 보기 explain SQL문 해당 SQL문의 실행계획 취득 show index from 테이블명 인덱스를 표시 desc 테이블명 테이블 열 정보 보기 use 데이터베이스 이름 특정 데이터베이스 사용하기 quit 로그오프 MySQL 주요 SQL CREATE TABLE 테이블명 1 LIKE 테이블 2; 테이블 구조만 복제해 생성하기 INSERT INTO 테이블명 VALUES (..., ..., ...), (..., ..., ...), (..., ..., ...); 복수 행 입력 (Multi row insert) INSERT 문 처리를 1번으로 정리해서 기존 INSERT 문 복수 회 실행 보다 처리시간이 더 짧음 다른 DBMS도 구현되어 있는 경우가 있음 (PostgreSQL, SQLServer, DB2…)

Computer Science · 2024-04-13

HTTP URI 및 Status Code 설계 방법

HTTP 통신 유스 케이스 데이터 전송 방식 분류 쿼리 파라미터 전송 (검색어를 포함한 정렬 필터) GET 메시지 바디 전송 POST, PUT, PATCH 유스케이스 정적 데이터 조회 이미지, 정적 텍스트 문서 리소스 경로로 단순 조회 동적 데이터 조회 검색어 포함 필터 및 정렬 적용 쿼리 파라미터 조회 HTML Form을 통한 데이터 전송 GET, POST만 지원 GET 전송 form 내용을 쿼리 파라미터 형식으로 전달 POST 전송 Content-Type: application/x-www-form-urlencoded (default) form 내용을 메시지 바디 통해서 전송 (key=value 형태) 전송 데이터를 url encoding 처리 한글 같은 것이 들어오면 자동으로 인코딩 됨 abc김 -> abc%EA%B9%80 Content-Type: multipart/form-data form 내용 및 다른 종류의 여러 파일을 메시지 바디 통해서 전송 (boundary로 타입마다 나눔) 파일 업로드 같은 바이너리 데이터 전송시 사용 API를 통한 데이터 전송 AJAX, Axios 등을 통한 자바스크립트 통신 Content-Type: application/json (JSON 데이터로 소통) 서버 to 서버, 웹 혹은 앱 클라이언트 URI 설계 단위 문서(Document) 단일 개념 (파일 하나, 객체 인스턴스, 데이터베이스 row) members/1, /files/star.jpg 컬렉션(Collection) 서버가 관리하는 리소스 디렉토리 POST 기반 등록 서버가 리소스 URI를 결정 /members 스토어(Store) 클라이언트가 관리하는 리소스 디렉토리 PUT 기반 등록 (없으면 생성, 있으면 수정) 클라이언트가 리소스 URI를 결정 파일 시스템, 게시판 등에 적용 /files 컨트롤러(Controller), 컨트롤 URI 일반적인 HTTP 메서드만으로 해결하기 애매한 경우 사용 문서, 컬렉션, 스토어로 해결하기 어려운 추가 프로세스 실행 동사로 된 리소스 경로 사용 /members/{id}/delete HTTP API 설계 예시 HTTP API - 컬렉션 회원 관리 시스템 예시 회원 목록: GET /members 회원 등록: POST /members 회원 조회: GET /members/{id} 회원 수정: PATCH, PUT, POST /members/{id} 실무에서는 엔터티의 속성이 매우 많으므로 PATCH를 쓰는게 제일 좋음 PUT은 하나라도 누락되면 데이터가 날아가버릴 위험 (게시판 게시글 수정 정도 OK) 둘 다 애매한 경우는 POST 사용 회원 삭제: DELETE /members/{id} HTTP API - 스토어 파일 관리 시스템 예시 파일 목록: GET /files 파일 조회: GET /files/{filename} 파일 등록: PUT /files/{filename} 파일 삭제: DELETE /files/{filename} 파일 대량 등록: POST /files HTML Form 순수 HTML, HTML Form만을 사용해야 할 때의 시나리오 GET, POST만 지원 메서드 제약을 컨트롤 URI로 해결 회원 관리 시스템 예시 회원 목록: GET /members 회원 등록 폼: GET /members/new 회원 등록: POST /members/new (혹은 /members) 회원 조회: GET /members/{id} 회원 수정 폼: GET /members/{id}/edit 회원 수정: POST /members/{id}/edit (혹은 /members/{id}) 회원 삭제: POST /members/{id}/delete List 형식의 쿼리 파라미터 쿼리 파라미터에서 같은 키 값에 대해 복수의 value를 보낼 수도 있음 id=1&id=2&id=3&id=4 HTTP 상태코드 클라이언트는 상위 상태코드로 해석해 처리하므로 미래에 새 상태코드가 추가되어도 클라이언트는 변경 X 2xx (Successful) 200 OK 201 Created 요청 성공해서 새로운 리소스가 생성됨 응답의 Location 헤더 필드로 생성된 리소스 식별 (Location: /members/1) 혹은 응답 메시지 바디에 id를 리턴해 생성된 리소스 식별 202 Accepted 요청이 접수되었으나 처리가 완료되지 않았음 배치 처리 (요청 접수 1시간 후 배치 프로세스 시작) 204 No Content 서버가 요청을 성공적으로 수행했지만, 응답 페이로드 본문에 보낼 데이터가 없음 웹 문서 편집기 save 버튼 3xx (Redirection) 요청을 완료하기 위해 유저 에이전트의 추가 조치 필요 웹브라우저는 3xx 응답 결과에 Location 헤더가 있으면, Location 위치로 자동 이동 영구 리다이렉션 (거의 사용 X) 리소스 URI가 영구적으로 이동 원래의 URL을 사용하지 않고 검색엔진에서도 변경을 인지 301 Moved Permanently 리다이렉트시 요청 메서드가 GET으로 변하고, 본문(메시지 바디)이 제거될 수 있음 308 Permanent Redirect 301과 같은 기능 리다이렉트시 요청 메서드와 본문 유지 (POST로 보내면 리다이렉트도 POST) 일시 리다이렉션 리소스 URI가 일시적으로 변경 검색엔진에서 기존 URI 유지 처음 302의 의도는 메서드 유지였으나 애매한 스펙 기재로 웹브라우저들이 GET으로 변경하도록 구현되었고 결국 명확한 스펙의 307, 303이 등장 함 (301 대응의 308도 마찬가지) 302 Found (현실적으로 이미 많은 라이브러리가 디폴트로 사용하므로 302만 써도 무방) 리다이렉트 요청 메서드가 GET으로 변하고, 본문이 제거될 수 있음 307 Temporary Redirect 302와 같은 기능 리다이렉트시 요청 메서드와 본문 유지 (POST로 보내면 리다이렉트도 POST) 303 See Other 302와 같은 기능 리다이렉트시 요청 메서드가 GET으로 변경 PRG (Post/Redirect/Get) (자주 사용) POST 주문 후 새로고침하면 재요청으로 인해 중복 주문이 될 수 있음 따라서, POST 주문 후에 주문 결과 화면을 GET 메서드로 리다이렉트 특수 리다이렉션 304 Not Modified 클라이언트에게 서버 리소스가 수정되지 않았음을 알려줌 클라이언트는 로컬 캐시로 리다이렉트 (캐시 재사용) 응답 메시지 바디 X 조건부 GET, HEAD 요청시 사용 4xx (Client Error) - 오류의 원인이 클라이언트에 있으므로, 재시도가 항상 실패 400 Bad Request 클라이언트가 잘못된 요청을 해서 서버가 요청을 처리할 수 없음 요청 파라미터가 잘못되거나, API 스펙이 맞지 않을 때 (백엔드는 철저히 validation해야 함) 401 Unauthorized 클라이언트가 해당 리소스에 대한 인증이 필요함 (인증 실패) 응답에 WWW-Authenticate 헤더와 함께 인증 방법 설명 403 Forbidden 서버가 요청을 이해했지만 승인을 거부함 (인가 실패, 접근 권한 불충분) 로그인한 어드민 등급이 아닌 사용자가, 어드민 등급 리소스에 접근하는 경우 404 Not Found 요청 리소스가 서버에 없음 혹은 권한이 부족한 클라이언트에게 해당 리소스를 완전히 숨기고 싶을 때 (403도 안내고 완전히 숨기고 싶을 때) 5xx (Server Error) - 오류의 원인 서버에 있으므로, 재시도가 성공할 수도 있음 500 Internal Server Error 서버 내부 문제로 오류 발생 애매하면 500 503 Service Unavailable 서비스 이용 불가 서버가 일시적인 과부하 혹은 예정된 작업으로 잠시 요청을 처리할 수 없음 Retry-After 헤더 필드로 얼마뒤에 복구되는지 보낼 수 있음 서버는 왠만하면 500대 에러를 내서는 안됨. 항상 200대 혹은 400대 에러로 해결할 것 Reference 모든 개발자를 위한 HTTP 웹 기본 지식

Computer Science · 2024-02-28

HTTP 헤더 종류

HTTP header HTTP 전송에 필요한 모든 부가정보 History RFC2616 (폐기) Header를 General header, Request header, Response header, Entity header로 분류 Entity body(실제 데이터)는 Message body에 담음 Entity header는 Entity body 해석을 위한 정보 제공 (Content-Type, Content-Length) RFC723x Entity => Representation(표현) 회원이라는 리소스를 특정 데이터 형식(HTML, JSON, XML)으로 표현해 전달하겠다는 의미 Representation = Representation Metadata + Representation Data Representation Data는 Payload(=Message body)에 담음 일반 HTTP 헤더 표현 헤더 Content-Type 미디어 타입, 문자 인코딩 text/html; charset=utf-8, application/json (디폴트 인코딩: utf-8), image/png Content-Encoding 표현 데이터의 압축 정보 (전달자가 헤더 추가) gzip, deflate, identity(=압축 X) Content-Language 자연 언어 ko, en, en-US Content-Length 바이트 단위 Transfer-Encoding 사용 시에는 필요 없음 협상 헤더 (Content Negotiation) 클라이언트가 선호하는 표현을 서버에 요청하고 서버는 최대한 클라이언트 선호에 맞춰 응답 요청시에만 사용하는 헤더 종류 Accept (미디어 타입) Accept-Charset (문자 인코딩) Accept-Encoding (압축 정보) Accept-Language (자연 언어) 협상 우선순위 Quality Values(q) 0~1: 클수록 높은 우선순위 생략 시 1 Accpet-Language: ko-KR,ko;q=0.9,en-US;q=0.8,en;q=0.7 구체적인 것이 우선 Accept: text/*, text/plain, text/plain;format=flowed, */* text/plain;format=flowed > text/plain > text/* > */* 전송방식 관련 헤더 단순 전송 Content-Length 헤더와 함께 한번에 데이터 전송 압축 전송 Content-Length + Content-Encoding 헤더와 함께 압축된 데이터를 전송 분할 전송 Transfer-Encoding: chunked 헤더와 함께 데이터를 일정한 단위로 쪼개어 보냄 Content-Length 헤더는 보내면 안됨 큰 용량의 데이터를 한 번에 보내느라 기다리는 상황이 생기지 않도록, 분할된 데이터가 오는대로 바로바로 보여주는 방식 서버에서 5byte가 만들어지면 클라이언트에 먼저 보내고, 또 만들어지면 또 보내서 마지막에 0바이트 \r\n을 보내고 끝을 표현 범위 전송 Range(요청 헤더), Content-Range(응답 헤더)와 함께 범위를 지정해 데이터를 전송 데이터를 절반정도 받다가 연결이 끊겼을 때, 못받은 범위만큼만 재요청하면 효율적 일반 정보 헤더 요청 헤더 From 유저 에이전트의 이메일 정보 거의 사용되지 않지만 검색 엔진 같은 곳에서 주로 사용 (크롤링 그만해달라는 요청을 할 수 있는 연락 수단) Referer 이전 웹 페이지 주소 유입 경로 분석에 사용 User-Agent 클라이언트의 애플리케이션 정보 (웹브라우저 정보) user-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/ 537.36 (KHTML, like Gecko) Chrome/86.0.4240.183 Safari/537.36 통계 정보 혹은 특정 브라우저의 장애에 대한 파악에 이용 응답 헤더 Server ORIGIN 서버의 소프트웨어 정보 ORIGIN 서버: 여러 프록시 서버, 캐시 서버를 제외하고 정말로 요청을 처리해 응답하는 서버 Server: Apache/2.2.22 (Debian) server: nginx Date 메시지가 발생한 날짜와 시간 최신 스펙에서 응답에만 사용하도록 명시 특별 정보 헤더 요청 헤더 Host (필수) 요청한 호스트 정보 (도메인) 클라이언트가 DNS를 거쳐 얻은 IP로 가상호스팅 중인 서버에 패킷을 보냈을 때, 어떤 도메인으로 전달해야 할지 판단하는 것에 구분점이 됨 가상호스팅: 하나의 IP 주소에 여러 도메인이 적용되어 있는 상황 (도메인이 다른 여러 애플리케이션 구동) 응답 헤더 Location 페이지 리다이렉션 201: 요청에 의해 생성된 리소스 URI 3xx: 요청을 자동으로 리다이렉션할 리소스 URI Allow 해당 Path에서 허용 가능한 HTTP 메서드를 확인해 서버에서 보냄 405 (Method Not Allowed)에는 반드시 포함 실제로 구현되어 있는 곳은 별로 없음 Retry-After 유저 에이전트가 다음 요청을 하기까지 기다려야 하는 시간 503 (Service Unavailable) 응답 시 서비스가 언제까지 불능인지 알려줌 날짜표기 혹은 초단위 표기 인증 헤더 Authorization (요청 헤더) 클라이언트 인증 정보를 서버에 전달 Authorization: Basic xxxxxxxxx Authorization: Bearer xxxxxxxxx WWW-Authenticate (응답 헤더) 리소스 접근시 필요한 인증 방법 정의 정의해준 방법으로 다시 제대로 인증 정보를 생성해서 인증하라는 의미 401 (Unauthorized)와 함께 사용 WWW-Authenticate: Newauth realm="apps", type=1, title="Login to \"apps\"", Basic realm="simple" 쿠키 헤더 특징 HTTP는 Stateless 프로토콜이므로 상태가 요구되는 상황에서는 쿠키로 저장 사용자 로그인 세션 관리 광고 정보 트래킹 GDPR(General Data Protection Regulation, EU 개인정보보호 법령)로 인해 EU 회원국의 웹사이트들은 유저들로부터 쿠키 수집 동의를 받아야 함 (필수쿠키, 기능쿠키, 성능쿠키, 마케팅쿠키 등에 대해 각각 선택도 가능) 쿠키는 항상 서버에 전송되므로 네트워크 트래픽이 유발되기 때문에, 최소한의 정보만 사용해야 함 (세션 id, 인증 토큰) 보안에 민감한 데이터는 저장하면 안됨 (주민번호, 신용카드 번호) 생명주기 세션 쿠키: 만료 날짜가 생략된 쿠키는 브라우저 종료시까지만 유지 영속 쿠키: 만료 날짜가 입력된 쿠키는 해당 날짜까지 유지 Cookie (요청 헤더) 서버에서 받은 쿠키를 클라이언트가 HTTP 요청시 전달 Set-Cookie (응답 헤더) 서버에서 클라이언트로 쿠키 전달 Field Value expires 만료일이 되면 쿠키 삭제 max-age 0이나 음수를 지정하면 쿠키 삭제 domain 쿠키를 전송받는 서버 도메인의 범위 제한 예시) domain=example.com 명시 기준 도메인 + 서브 도메인 적용 example.com&dev.example.com까지 쿠키 접근 가능(=쿠키 전송) 생략 기준 도메인만 적용 example.com만 쿠키 접근 가능 path 해당 경로를 포함해 하위 경로 페이지까지만 쿠키 접근 가능 일반적으로 path=/ 루트로 지정 Secure https인 경우에만 쿠키 전송 HttpOnly 자바스크립트로 쿠키 접근 불가, http 전송에만 사용 가능 XSS 공격 방지 SameSite 쿠키를 전송하는 요청 도메인(=현재 접속해 있는 페이지)의 범위 제한 요청 도메인이 쿠키에 설정된 도메인과 같은 경우에만 쿠키 전송 XSRF 공격 방지 속성 Strict: 같은 도메인에서만 접근 가능 퍼스트 파티 쿠키 only Lax: <a>, <link>, <form method="GET">통한 이동은 다른 도메인이어도 cookie 전송 Chrome 80 default 퍼스트 파티 쿠키 + 일부 서드 파티 쿠키 None: cross-site에서도 쿠키 전송 가능 (단, Secure 옵션 추가필수) 퍼스트 파티 쿠키 + 모든 서드 파티 쿠키 캐시와 조건부 요청 HTTP 헤더 (캐시 제어 헤더) + (검증 헤더 & 조건부 요청 헤더 한 쌍) 캐시 조합 권장 cache-control: max-age=... + Last-Modified cache-control: max-age=... + ETag (Recommendation) 캐시 기본 동작 첫 번째 요청시응답에서 특정 캐시 헤더 및 바디 데이터를 브라우저 캐시에 저장 cache-control: max-age=60 Last-Modified: 2023-04-23... ETag: "aaaaaaaaa" 두 번째 요청시 캐시 유효시간(max-age 값) 검증 유효: 캐시에서 조회 유효 X 서버로 요청 조건부 요청 헤더 추가 검증 헤더에 따라 If-Modified-Since 혹은 If-None-Match 서버 검증 기존 데이터 변경 X 304 Not Modified (HTTP Body X) 응답 캐시에서 조회 (재사용) 브라우저 캐시갱신 (응답 캐시 헤더) 기존 데이터 변경 200 OK, 변경된 데이터 응답 브라우저 캐시 갱신 (응답 캐시 헤더 + 바디) 헤더 종류 캐시 제어 헤더 Cache-Control (캐시 제어) max-age 캐시 유효 시간, 초 단위 no-cache 데이터를 캐시해도 되지만, 항상 원 서버(Origin Server)에 검증하고 사용 no-store 데이터에 민감한 정보가 있으므로 저장하면 안됨 (메모리에서 사용하고 최대한 빨리 삭제) Pragma (캐시 제어, HTTP 1.0 하위호환) no-cache (위와 동일) Expires (Cache-Control: max-age 하위호환, 함께 사용시 Expires는 무시됨) 캐시 만료일을 정확한 날짜로 지정 검증 헤더 (Validator) 캐시 데이터와 서버 데이터가 같은지 검증하는 데이터 Last-Modified 데이터가 마지막으로 수정된 시간 1초 미만 단위의 캐시 조정이 불가능 ETag (Entity Tag) 캐시용 데이터에 임의의 고유한 버전 이름(Hash)을 붙이고 데이터 변경시 Hash 재생성 ETag가 같으면 캐시유지, 다르면 변경된 데이터 전송 서버에서 별도 캐시 로직을 관리하고 싶은 경우 사용 데이터 수정 날짜가 다르지만 A -> B -> A로 수정해 데이터 결과가 똑같은 경우 스페이스나 주석 같이 크게 영향 없는 변경 무시 애플리케이션 배포 주기에 맞추어 ETag 모두 갱신 조건부 요청 헤더 검증 헤더를 통해 브라우저 캐시에 저장된 값으로 조건에 따른 분기 요청 If-Modified-Since: Last-modified 값 사용 If-Unmodified-Since: Last-modified 값 사용 If-None-Match: ETag 값 사용 If-Match: ETag 값 사용 장점 비싼 네트워크 사용량을 줄일 수 있음 (캐시 유효시간동안 네트워크 이용은 용량이 적은 헤더 전달뿐) 브라우저 로딩 속도가 매우 빨라져서 사용자 경험이 좋아짐 프록시 캐시 원 서버가 멀리 있는 경우 중간에 프록시 캐시 서버(CDN 서비스)를 두어 속도적 이점을 얻음 클라이언트(한국) - (0.5초) - 원 서버(미국) 클라이언트(한국) - (0.1초) - 프록시 캐시 서버(한국 어딘가) - (0.4초) - 원 서버(미국) 보편적 캐시 방법 첫 번째 접근이 오래걸리고 두 번째 이후부터는 다운이 이미 받아져 빨라짐 유튜브의 인기 있는 영상은 로딩이 빠르고 인기 없는 영상은 로딩이 느림 원 서버에서 캐시 서버로 데이터를 밀어 넣는 경우도 있음 관련 캐시 응답 헤더 Cache-Control: public 응답이 public 캐시에 저장되어도 됨 (=중간 프록시 캐시 서버에 저장되어도 됨) Cache-Control: private 응답이 private 캐시에 저장되어야 함 (기본값) Cache-Control: s-maxage 프록시 캐시에 적용되는 max-age Cache-Control: must-revalidate 캐시 만료 후 최초 조회시 원 서버에 검증해야 함 원 서버 접근 실패시 반드시 오류가 발생해야 함 (504 Gateway Timeout) 캐시 시간이 유효하다면 캐시 사용 Age: 60 원 서버에서 응답 후 프록시 캐시 내에 머문 시간(초) 확실한 캐시 무효화 응답 Cache-Control: no-cache, no-store, must-revalidate Pragma: no-cache 기본적으로 웹브라우저 임의로 캐시를 할 수 있기 때문에 완전한 캐시 무효를 위해 사용 네트워크 단절 등으로 인한 원 서버 접근 불가 시 must-revalidate이 필요 no-cache의 경우 캐시 서버 설정에 따라 원 서버에 접근할 수 없는 경우, 캐시 데이터를 반환할 수 있음 (오류보다는 오래된 데이터라도 보여주기, 200 OK) must-revalidate은 원서버에 접근할 수 없는 경우, 항상 오류 발생시킴 (매우 중요한 돈과 관련된 결과들에 필수, 504 Gateway Timeout) 용어 원 서버 (Origin Server): 실제 요청을 처리하는 서버 public 캐시: 프록시 캐시 서버 private 캐시: 각각의 브라우저의 로컬 캐시 Reference 모든 개발자를 위한 HTTP 웹 기본 지식 마케터를 위한 웹사이트 쿠키 동의 환경의 이해 What are the security differences between cookies with Domain vs SameSite strict? SameSite란? None, Lax, Stricts

Computer Science · 2024-02-22

HTTP 기본 구조

기본 용어 IP (Internet Protocol) 패킷(Packet)을 단위로 특정 주소(IP Address)에 데이터를 전달할 수 있는 프로토콜 IP 패킷 (보내려는 메시지 + 출발지 IP, 도착지 IP…) 한계 비연결성 패킷을 받을 대상이 없거나 상대 서버가 불능 상태여도 전송 비신뢰성 중간에 패킷이 누락되거나 순서대로 오지 않는 경우 존재 프로그램 구분 같은 IP인데 통신하는 애플리케이션이 2개 이상인 경우 구분 불가 전송계층(Transport Layer) 네트워크 4계층에서 TCP 혹은 UDP 추가 정보로 IP 패킷을 보완하는 단계 TCP (Transmission Control Protocol) 앞선 IP의 문제점을 해결 (전송제어 정보를 패킷에 추가) TCP/IP 패킷 (IP 패킷 + 출발지 PORT, 목적지 PORT, 전송제어, 순서, 검증정보…) 특징 연결지향 (3 way handshake) SYN, SYN+ACK, ACK 3단계로 연결을 확인하고 그 후 데이터를 보냄 최근엔 최적화되어 세 번째 단계 ACK에서 데이터를 함께 보내는 것이 가능 데이터 전달 보증 서버는 데이터를 잘 받았다는 응답을 클라이언트에게 줌 순서 보장 기본적으로는 패킷 1, 3, 2 순서로 왔다면 2부터 다시 보낼 것을 클라이언트에 요청 서버 최적화에 따라 다시 보내달라는 요청 없이 내부적으로 처리하기도 할 것 UDP (User Datagram Protocol) IP와 비슷할 정도로 기능이 거의 없음 (하얀 도화지) PORT, 체크섬 정도만 추가 TCP의 연결지향, 데이터 전달 보증, 순서 보장 등이 없다. 덕분에 단순하고 빠름 TCP는 3 way handshake와 패킷의 추가정보들로 인해 데이터가 크고 속도가 느림 따라서, 속도 최적화는 UDP 이용 HTTP3 스펙에서도 UDP를 활용하며 최근 각광 PORT 같은 IP(내 서버) 내에 여러 프로세스가 통신 중일 때, 응답 패킷이 어느 애플리케이션의 패킷인지 구분 IP가 아파트면 PORT는 동호수를 표현 0~65535 할당 가능 0~1023은 잘 알려진 포트로 사용하지 않는 것이 좋음 HTTP - 80 HTTPS - 443 DNS (Domain Name System) 전화번호부 같은 서버를 제공하여 도메인명을 IP 주소로 변환하는 역할 수행 IP는 기억하기 어렵고 가변적이어서 DNS가 이를 해결 URI (Uniform Resource Identifier) 자원을 식별하는 방법을 총칭 URL(Uniform Resource Locator) + URN(Uniform Resource Name) URL: https://www.inflearn.com/course/lecture URN: urn:isbn:01270712 URN은 보편화 되지 않아서 URI = URL로 생각해도 무방하다. URL 문법 Syntax: scheme://[userinfo@]host[:port][/path][?query][#fragment] 예시: https://www.google.com:443/search?q=hello&hl=ko scheme 주로 프로토콜 사용 (어떤 방식으로 자원에 접근할 것인가에 대한 약속) http, https, ftp port http 80 포트, https 443 포트 등 보편적인 경우 생략 가능 userinfo URL에 사용자 정보를 포함해서 인증하는 경우 사용하지만 거의 쓰이지 않음 host 도메인명 또는 IP 주소를 직접 사용 가능 path 계층적 구조의 리소스 경로 query key-value 형태 ?로 시작, &로 추가 서버로 요청시 모두 문자로 넘어감 = query parameter = query string fragment html 내부 북마크에 사용 서버 전송 정보가 아님 브라우저 요청 흐름 클라이언트 애플리케이션 계층 웹 브라우저에 요청: https://www.google.com:443/search?q=hello&hl=ko 웹 브라우저가 DNS 조회 및 PORT 정보 파악 웹 브라우저가 HTTP 요청 메시지 생성 SOCKET 라이브러리 파악한 IP 및 PORT 정보로 구글 서버와 3 way handshake로 연결 맺기 OS로 데이터 전달 OS 계층 (TCP/UDP & IP 계층) TCP/IP 패킷 생성 (HTTP 메시지 포함) 네트워크 인터페이스 패킷에 이더넷 프레임을 씌워 인터넷망으로 던짐 인터넷 망 수많은 인터넷 노드를 거쳐 목적지 구글 서버에 패킷 전달 구글 서버 구글 서버는 반대 과정으로 tcp/ip 패킷을 까서 http 메시지를 해석 구글 서버는 요청에 맞는 http 응답 메시지를 생성하고 TCP/IP 패킷을 씌워 클라이언트에 다시 보냄 인터넷 망 수많은 인터넷 노드를 거쳐 클라이언트 웹브라우저에 응답 패킷 전달 클라이언트 클라이언트는 응답 패킷을 까서 http 메시지를 해석 메시지 내 데이터를 웹 브라우저가 렌더링하여 화면에 출력 HTTP (HyperText Transfer Protocol) 모든 형태의 데이터를 HTTP 메시지로 전송 가능 처음엔 HTML 같은 HyperText 문서 전송 용도로 시작 HTTP/1.1 (1997) 가장 많이 사용되는 중요한 버전 주요 기능이 이미 모두 포함됨 RFC7230~7235(2014)이 최신 개정판 HTTP/2, HTTP/3은 성능 개선에 초점 TCP 이용 HTTP/1.1, HTTP/2 UDP 이용 HTTP/3 특징 클라이언트-서버 구조 클라이언트(UI, 사용성) & 서버(비즈니스 로직, 데이터) 분리로 각각이 독립적 진화 가능 무상태 프로토콜(Stateless) 서버가 클라이언트의 상태를 보존하지 않음 서버 Scale Out(수평 확장)에 유리 무상태는 응답 서버를 쉽게 바꿀 수 있으므로 무한한 서버 증설 가능 갑자기 클라이언트 요청(고객)이 증가해도 서버(점원)를 대거 투입할 수 있음 한계 무상태로 설계할 수 없는 경우도 있음 쿠키 세션 로그인 요청 데이터가 많음 최대한 무상태로 설계하고 어쩔 수 없는 경우에만 상태 유지 정말 같은 시간에 딱 맞추어 발생하는 대용량 트래픽 감당을 위한 필수 설계 선착순 1000명 이벤트는 수만명 동시 요청 발생 첫 페이지에 로그인도 필요 없는 정적 페이지 하나를 두면 조금 분산이 됨 비연결성(Connectionless) 요청 및 응답할 때만 연결하고 바로 끊음 서버의 자원을 매우 효율적으로 사용할 수 있음 HTTP는 초 단위 이하의 빠른 속도로 응답 1시간 동안 수천명이 서비스를 이용해도 서버에서 실제 동시에 처리하는 요청은 수십개 이하로 작음 (1초에 몇 명 되지도 않을 것) HTTP 지속 연결(Persistent Connections) 기본으로 사용해 연결 시간을 어느정도 최적화 TCP/IP 연결(3 way handshake) 시간이 사용자에게 매번 추가되는 상황이 비효율적 js파일, html 파일, css 파일을 각각 다운 받을 때마다 연결을 맺음 (0.9초) HTTP 지속 연결로 해결 HTML 페이지 하나가 전부 다운 받아질 때까지 TCP 연결을 유지하고 해제함 (0.5초) HTTP 메시지 구조 구조 시작 라인(start-line) 요청과 응답 기본 형태는 start-line만 다름 request-line (요청 메시지 경우) (HTTP 메서드) (SP=공백) (request-target=absolute path) (SP) (HTTP version) (CRLF=엔터) ex) GET /search?q=hello&hl=ko HTTP/1.1 status-line (응답 메시지 경우) (HTTP version) (SP) (status-code) (SP) (reason-phrase) (CRLF) ex) HTTP/1.1 200 OK 헤더(header) HTTP 전송에 필요한 모든 메타 정보 담김 수많은 표준 헤더가 존재 & 임의의 헤더 추가 가능 구조 (header-field) (field-name) (:) (OWS=띄어쓰기 허용) (field-value) (OWS) field-name은 대소문자 구분 X, field-value는 대소문자 구분 O request example Host: www.google.com response example Content-Type: text/html;charset=UTF-8 Content-Length: 3432 공백 라인(empty line) - Required 메시지 바디(message body) - Optional 실제 전송할 데이터 담김 byte로 표현할 수 있는 모든 데이터 가능 HTML, 이미지, 영상, JSON etc… HTTP 메서드 API URI 설계 표준 리소스 식별 (명사) 리소스: 회원 계층 구조 상 상위 => 컬렉션 => 복수 명사(/members) 계층 구조 상 하위 => 도큐먼트 => 식별자 구분 (/members/{id}) 행위는 HTTP 메서드로 분리 (동사) 행위: 조회, 등록, 삭제, 변경 주요 HTTP 메서드 종류 GET 리소스 조회 쿼리 파라미터로 데이터 전달 최신 스펙에서 메시지 바디로 데이터 전달이 가능하지만, 지원하지 않는 곳이 있어 권장 X POST 요청 데이터 처리 리소스마다 요청 데이터를 어떻게 처리할지 따로 정해야 함 신규 리소스 등록 회원가입, 게시판 글쓰기… 프로세스 처리 단순한 데이터 생성 및 변경을 넘어서 엮여있는 프로세스들을 처리해야 하는 경우 POST의 결과로 새 리소스가 생성되지 않을 수 있음 주문에서 결제완료 -> 배달시작 -> 배달완료 같은 큰 작업들이 엮인 상태변경 POST /orders/{orderId}/start-delivery (보통 POST에서 컨트롤 URI 사용) 다른 메서드로 처리하기 애매한 경우 JSON으로 조회 데이터 넘겨야 하는데, GET 메서드 사용하기 어려운 경우 한 문서 끝에 내용 추가 즉, 서버에서 큰 변화가 일어나는 것은 POST 사용 PUT 리소스 대체 & 해당 리소스가 없을시 생성 (=덮어쓰기) 요청에서 데이터가 누락되면 그대로 삭제됨 (위험성 존재) 클라이언트가 리소스를 식별 (URI) PATCH 리소스 부분 변경 실무 엔터티들은 데이터가 많기 때문에 변경에 주로 PATCH를 사용 PATCH를 못받아들이는 서버가 있다면 POST를 부분 변경에 사용한다. DELETE 리소스 삭제 HTTP 메서드의 속성 안전(Safe Methods) 호출해도 리소스를 변경하지 않음 안전한 메서드: GET 멱등(Idempotent Methods) 여러 번 호출해도 결과가 똑같음 서버에 문제가 있을 때, 클라이언트가 같은 요청을 다시 해도 되는가의 판단 근거 멱등하지 않은 메서드: POST, PATCH 캐시가능(Cacheable Methods) 응답 결과 리소스를 캐시해서 사용 가능 큰 용량의 데이터를 로컬 PC 웹 브라우저 내부에 저장하고 있을 수 있는지 여부 캐시 가능 메서드: GET, POST, PATCH POST, PATCH는 메시지 바디까지 캐시 키로 고려해야 해서 구현이 어려움 실제로 GET 정도만 캐시로 사용 Reference 모든 개발자를 위한 HTTP 웹 기본 지식

Computer Science · 2024-02-20

관계형 데이터베이스 모델 개념

Relational Data Model & Relational Database Relation in Mathematics Set 서로 다른 elements를 가지는 collection elements의 순서는 중요하지 않음 Cartesian Product Set A & Set B의 element로 만들 수 있는 모든 pair의 조합 Relation Cartesian product의 부분 집합 (subset of Cartesian product) n-ary relation: n개의 Set에 대한 cartesian product의 부분집합 tuple들의 집합 (set of tuples) tuple은 하나의 pair를 의미 Relational Data Model Relation이 Relational Data Model에서는 Table로 표시 Relation = Table = Set of Tuples tuple(행) & attribute(열) Relation Schema Relation의 구조를 나타냄 (constraints 포함) e.g. Student(id, name, grade, major, phone_num, emer_phone_num) Degree of Relation Relation schema에서 attributes의 수 Relational Database Relational data model에 기반하여 구조화된 database (여러개의 relations로 구성) Relational Database Schema relation schemas set + integrity constraints set Constraints Implicit constraints Relational Data Model 자체가 가지는 제약 Explicit constraints (Schema-based Constraints) 주로 DDL을 통해 schema에 직접 명시 종류 Domain Constraints Attribute value는 해당 attribute가 가질 수 있는 value여야 함 Key Constraints 서로 다른 tuple은 같은 key 값을 가질 수 없음 Null value Constraints Attribute가 NOT NULL로 명시 됐다면, NULL을 값으로 가질 수 없음 Entity Integrity Constraints Primary key는 NULL을 가질 수 없음 Referential Integrity Constraints FK는 PK에 없는 value를 값으로 가질 수 없음

Computer Science · 2023-10-03

데이터베이스 기본 용어

Database 전자적으로 저장되고 사용되는 관련있는 데이터들의 조직화된 집합 Electronically, Related, Organized collection DBMS (Database Management System) 사용자에게 DB를 정의 및 관리하는 기능을 제공하는 소프트웨어 시스템 PostgreSQL, MySQL, Oracle Database, SQL Server Metadata(=Catalog, Data about Data) DB를 설명하는 데이터 (Descriptive) DBMS를 통해 관리됨 e.g. 데이터 유형, 구조, 제약 조건, 보안, 저장, 인덱스, 사용자 그룹 etc… Database System Database + DBMS + 연관된 applications 포괄적으로 database라고 부르기도 함 Data Model DB의 구조를 추상화해 설명하는 모형 (DB 구조: 데이터 유형, 데이터 관계, 제약 사항 etc…) DB 기본 Operations(CRUD)를 포함 종류 Conceptual Data Model (=high-level) 일반 사용자들이 쉽게 이해할 수 있게 DB를 구조화 (추상화 수준이 가장 높음) 비즈니스 요구사항 기술에 사용 Logical Data Model (=representational) 특정 DBMS에 종속되지 않는 수준에서 디테일하고 이해하기 쉽게 DB를 구조화 실제 DB 설계를 할 수 있는 수준 종류 (DBMS가 채택) relational data model (MySQL, Oracle DB, SQL Server) object data model object-relational data model (PostgreSQL) Physical Data Model (=low-level) 컴퓨터에 데이터가 어떻게 파일 형태로 저장되는지를 기술 data format, data orderings, access path(e.g. index…) Database Schema Data Model을 바탕으로 database의 구조를 기술한 것 Database State (=Snapshot =현재 instances의 집합) 특정 시점에 database에 있는 실제 데이터 Three-Schema Architecture User Application으로 부터 물리적인 database를 분리 각 레벨을 독립시켜 어느 레벨의 변화가 상위 레벨에 영향을 주지 않게 함 (안정적인 데이터베이스 운영) Database system을 구축하는 architecture 중 하나로 가장 많이 사용됨 대부분의 DBMS가 어느정도 따르나 three level을 완벽하게 나누지는 않음 Conceptual 변화는 External Level에 영향을 안 미치는 것이 상대적으로 힘들기 때문 각각의 Schema는 DB 구조를 표현만 함. 데이터가 실제 존재하는 곳은 internal level 분류 external schemas at external level (user view) 특정 유저들이 필요로 하는 데이터만 표현 (그 외 데이터는 숨김) logical data model을 통해 표현 conceptual schemas at conceptual level internal schema를 추상화해서 물리적인 저장 구조 내용은 숨기고 전체 DB 구조를 기술 entities, data types, relationships, user operations, constraints에 집중 logical data model을 통해 표현 internal schemas at internal level 물리적으로 데이터가 어떻게 저장되는지 physical data model을 통해 표현 data storage, data structure, access path 등 실체가 있는 내용 기술 Database Language 오늘날 DBMS는 DML, VDL, DDL이 따로 존재하기 보다는 통합된 언어로 존재 (e.g. SQL) 언어 종류 DDL (Data Definition Language) Conceptual Schema를 정의하기 위해 사용하는 언어 SDL (Storage Definition Language) Internal Schema를 정의하기 위해 사용하는 언어 최근엔 파라미터 설정으로 대체 (SDL은 거의 없음) VDL (View Definition Language) External Schema를 정의하기 위해 사용하는 언어 대부분의 DBMS에서 DDL이 VDL 역할까지 수행 DML (Data Manipulation Language) Database에 있는 실제 data를 활용하기 위한 언어 (CRUD)

Computer Science · 2023-10-01

데이터베이스

Computer Science · 2021-06-21

9-2. 가상 메모리

Page replacement - 다양한 캐싱 환경 캐싱 기법 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다. 즉, 한 번 썼던 데이터는 빠른 접근이 가능한 캐쉬 메모리에 저장해두었다가 가까운 시기에 해당 데이터에 대한 접근이 요청되면 빠르게 제공해준다. Paging system과 더불어 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용되는 방식이다. 캐싱 기법의 운영상 시간 제약 다만, 이러한 캐싱 기법은 운영상 시간 제약이 존재한다. 교체 알고리즘이 삭제할 항목을 결정하는 일에 지나치게 많은 시간을 소요하지 않아야 한다. 예를 들어, Buffer caching이나 Web caching의 경우 시간 복잡도가 O(1) ~ O(logN) 정도까지 허용한다. 반면, Paging system에서는 기존의 LRU, LFU 등의 삭제 항목 결정 알고리즘이 실제로 사용되기는 어렵다. Paging system의 경우 page fault가 생길 때만 OS가 관여하기 때문에, 페이지가 이미 메모리에 존재하는 상황에서의 참조 시각 정보는 OS가 알 수 없다. 즉, 특정 상황의 참조 시각과 참조 빈도 등을 알 수 없으므로, 앞에서 살펴봤던 LRU, LFU 등의 알고리즘은 실제 시스템에서는 사용되기 어렵다. Clock Algorithm (=Second Chance Algorithm) 캐싱 제약을 극복하기 위해, paging system에서는 일반적으로 Clock Algorithm이 쓰인다. 이 알고리즘에서는 각각의 page table entry에 최근에 참조함을 나타내는 reference bit을 둔다. 그리고 이미 메모리에 올라와 있는 페이지에 대해 참조가 일어날 경우, 하드웨어가 reference bit을 1로 바꿔 최근에 참조함을 기록한다. 그리고 메모리에 새로운 page를 올려할 상황이라 OS가 내쫒을 page를 결정할 때에는 위와 같은 과정으로 reference bit을 참고해 오래된 page를 내쫒는다. 또한, 조금 더 개선된 성능을 위해 modified bit을 둬서 page에 write가 일어났는지 여부를 기록한다. 만일, modified bit이 1인 page가 있다면 해당 페이지는 메모리에 올라와서 최근에 내용이 변경된 것이기 때문에, backing storage로 쫒아낼 때 변경된 내용을 반영하고 쫒아내야 한다. Page Frame의 Allocation 지금까지는 페이지가 어떤 프로세스에 속하느냐를 구체적으로 고려하지 않고 작업을 수행했다. 하지만, 각 프로세스마다 얼마만큼의 page frame을 할당한 것인가는 중요한 문제이다. 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지를 동시에 참조하게 되는데, 이 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있기 때문이다. 예를 들어, 반복문을 구성하는 page가 3개라고 한다면, 3개가 한번에 할당되는 것이 좋다. 2개가 할당된다면, 매 loop마다 page fault가 일어나 원활한 수행에 방해가 된다. 3가지 Allocation 방법 (∝ Local repacement) Equal Allocation: 모든 프로세스에 똑같은 갯수 할당 Proportional Allocation: 프로세스 크기에 비례하여 할당 Priority Allocation: 프로세스의 priority에 따라 다르게 할당 Global replacement VS Local replacement Global replacement는 따로 프로세스마다 할당되어야할 frame 개수를 정해놓지 않더라도 알고리즘을 수행하다보면 알아서 필요한 프로세스에 page가 더 많이 할당되는 것을 말한다. 반면에, Local replacement는 프로세스마다 할당할 page 개수를 정해둔 것을 말한다. Thrashing 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생한다. 위 그래프와 같이, 메모리에 동시에 올라온 프로세스 개수가 많아질수록, 특정 순간에 CPU 이용률이 급감해버리는 thrashing 현상이 발생한다. 보통 위와 같은 과정을 거쳐 thrashing으로 이어진다. 이를 해결하기 위해 두 가지 알고리즘을 소개한다. Working-Set Algorithm VS PFF (Page-Fault Frequency) Scheme (∝ Global repacement) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-11

9-1. 가상 메모리

이번 챕터부터는 메모리 관리 기법 중 paging 기법을 사용하는 것을 가정한다. 실제로도 대부분의 시스템은 paging 기법을 채택하고 있다. Demand Paging 실제로 특정 page에 대한 요청이 있을 때 해당 page를 메모리에 올리는 것을 말한다. 프로그램에는 안정적인 실행을 위해 방어적으로 넣은 자주 쓰이지 않는 코드 영역들이 매우 많이 존재한다. 그렇기에 실제로 쓰이는 코드들만 메모리에 올리면, I/O 양과 메모리 사용량을 크게 감소시킬 수 있고 더 많은 사용자들이 멀티 프로세싱할 수 있는 환경이 만들어진다. Demand Paging에서 페이지 테이블의 entry에 존재하는 valid/invalid bit의 역할을 살펴보자. Invalid는 주소 영역에서 사용되지 않는 부분이나 페이지가 물리적 메모리에 올라와 있지 않은 상황을 의미한다. 처음에는 모든 page entry가 invalid로 초기화되어 있다. 그리고 주소 변환시 해당 페이지가 invalid로 세팅되어 있다면, page fault를 일으킴과 동시에 trap을 걸어 운영체제에게 CPU를 넘기고 page fault가 난 페이지를 메모리에 올리게끔 한다. Page fault에 대한 처리 루틴은 운영체제에 정의되어 있으며, 구체적으로는 위 그림과 같은 과정을 거친다. Backing storage에서 메모리에 페이지를 올리는 디스크 I/O는 시간이 오래걸리기 때문에, page fault가 얼마나 나느냐에 따라 메모리 접근 시간에 차이가 날 수 있다. 위의 Effective Access Time에서 p는 보통 굉장히 작아서 대부분의 경우 page fault가 나지 않는다. 하지만, 적은 확률로 page fault가 나는 상황에서는 위의 붉은 글씨의 요인들처럼 큰 시간적 오버헤드가 발생함을 유의한다. Page replacement 메모리에 여유 공간이 필요할 때, 운영체제가 어떤 frame을 빼앗아서 page를 쫒아낼지 결정하는 것을 Page replacement라고 한다. 이것을 구현하는 알고리즘을 Replacement Algorithm이라고 하는데, page fault rate을 최소화하는 방향으로 page를 쫒아내도록 알고리즘을 잘 설정해야 한다. Optimal Algorithm (실제로 쓰이진 않음) Optimal Algorithm은 가장 먼 미래에 참조되는 page를 replace하는 방식으로 Page fault를 최소화하는 알고리즘이다. 위 예시처럼, 미래의 page 참조를 전부 안다고 가정하고 진행하기 때문에 실제로 시스템에서 쓰이진 않지만, 가장 최고의 성능을 나타내는 지표로서 다른 알고리즘들의 성능에 대한 upper bound를 제공한다. FIFO Algorithm (실제로 쓰임) 간단하게 먼저 올라온 page를 먼저 쫒아내는 방식이다. 특이한 점은 frame 수를 늘리면 성능이 좋아져야 할 것 같지만, FIFO 알고리즘에서는 오히려 성능이 떨어지는 현상이 발생하는데, 이를 FIFO Anomaly 혹은 Belady’s Anomaly라고 부른다. LRU (Least Recently Used) Algorithm (실제로 쓰임) LRU(Least Recently Used) 알고리즘은 참조의 측면에서 가장 오래 전에 참조된 page를 쫒아내는 방법이다. 얼핏보면 FIFO와 비슷하지만, FIFO보다 효율적으로 동작하여 더 많이 쓰이는 알고리즘이다. LFU (Least Frequently Used) Algorithm (실제로 쓰임) LFU(Least Frequently Used) 알고리즘은 참조 횟수가 가장 적은 page를 쫒아내는 방법이다. 동일한 참조 횟수를 기록 중인 page가 여럿 있을 때는 일반적으로 큰 의미를 두지 않고 알고리즘이 임의로 쫒아낸다. 다만, 그 중에서도 가장 오래 전에 참조된 page를 쫒아내도록 알고리즘을 설계하는 것이 성능 향상에 이로울 수 있다. LRU VS LFU LRU는 참조 시점의 최근성을 반영한다. 반면에 LFU는 장기적인 측면에서 page의 인기도를 더 정확히 반영하는 장점이 있다. 다만, LFU는 LRU보다 구현이 복잡하다. LRU의 경우는 시간에 따라 일렬로 줄 세우고 가장 최근에 참조했던 페이지를 내쫒으면 된다. 따라서, Linked List 자료구조로 구현하여, 페이지를 내쫒는 작업을 O(1) 시간 복잡도로 수행하게끔 한다. 반면에, LFU는 페이지의 참조 빈도가 계속 바뀌기 때문에, heap 자료구조를 사용하여 지속적으로 정렬하는 방법을 사용한다. 이 경우 페이지를 내쫒는 작업은 O(log n)의 시간 복잡도로 수행된다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-10

8-2. 메모리 관리

Allocation of Physical Memory 메모리는 일반적으로 Interrupt vector와 함께 낮은 주소 영역을 사용하는 OS 상주 영역과 높은 주소 영역을 사용하는 사용자 프로세스 영역 둘로 나뉜다. 사용자 프로세스 영역의 할당 방법 1. Contiguous allocation (연속 할당) 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것이다. 연속 할당 방식은 두 가지가 존재한다. 고정 분할 방식 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션(partition)으로 나눠놓는 것을 말한다. 이 경우, 동시에 메모리에 load되는 프로그램의 수가 제한되고 최대 수행 가능 프로그램 크기도 제한된다. 위 그림을 예시로 보면 메모리 영역은 이미 고정되어 나뉘어져 있고 프로그램 A와 B는 각각 자신의 크기에 맞는 파티션을 찾아 그 위에서 실행된다. 이 과정에서 프로그램을 담을만큼 충분한 용량을 가지지 못해 남겨진 메모리 영역을 의미하는 외부 조각과 파티션에서 프로그램이 실행되고 남은 메모리 영역을 의미하는 내부 조각이 발생한다. 가변 분할 방식 사용자 메모리 영역을 미리 나눠놓지 않는 방법을 말한다. 가변 분할 방식은 프로그램의 크기를 고려해 프로그램들을 차곡차곡 메모리 영역에 할당한다. 이 때, 앞서 실행된 프로그램이 종료되거나 새로운 프로그램이 실행됨에 따라 남겨져버는 메모리 영역, 즉 외부조각이 발생할 수 있다. 이 가용 메모리 공간을 Hole이라고 하는데, 운영체제는 할당 공간과 흩어져 있는 가용 공간(hole)을 잘 고려해서 프로그램의 실행을 매끄럽게 도와야 한다. 한편, 가변 분할 방식에서는 미리 정해진 파티션이 없기 때문에 내부 조각은 발생하지 않는다. Dynamic Storage Allocation Problem 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제를 말한다. First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 더 효과적인 것으로 알려져 있다. First-fit Size가 n이상인 것 중에 최초로 찾아지는 hole에 할당하는 방법이다. Best-fit Size가 n이상인 가장 작은 hole을 찾아서 할당하는 방법이다. 많은 수의 아주 작은 hole들이 생성되며, hole들의 리스트가 크기순으로 정렬되지 않은 경우 모든 hole의 리스트를 탐색해야 한다. Worst-fit 가장 큰 hole에 할당하는 방법이다. 이 역시 hole들의 리스트가 크기순으로 정렬되어 있지 않으면, 모든 리스트를 탐색해야 하고, Best-fit과는 달리 상대적으로 아주 큰 hole들이 생성된다. Compaction 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만듦으로써 외부조각 문제를 해결하는 방법이다. 다만, Run time binding이 지원되어야 수행 가능하고, 최소한의 메모리 이동을 고려하는 복잡한 문제를 해결해야 하기 때문에 비용이 매우 많이 든다는 단점이 있다. 2. Noncontiguous allocation 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있는 방법을 말한다. Paging 기법 프로세스의 virtual memory를 동일한 사이즈의 page로 나누는 방법이다. 따라서 virtual memory의 내용이 page 단위로 비연속적으로 저장되며, 일부는 backing storage에, 일부는 physical memory에 저장된다. Paging 기법을 사용하기 위해서 physical memory를 동일한 크기의 frame으로, logical memory를 동일한 크기의 page로(frame과 같은 크기) 나눠야 한다. 그리고 기존과 달리 page table을 사용해서 logical address를 physical address로 주소 변환한다. 이 기법을 사용하면 가장 마지막 페이지로 인해 발생하는 내부 조각은 존재할 수 있지만, 마지막 page를 제외한 모든 page와 frame의 크기가 동일하기 때문에 외부 조각은 발생하지 않는다. 위 그림으로 조금 더 자세히 살펴보자. CPU가 어떤 논리적 주소를 주면, 논리적 주소의 앞 부분 p는 페이지 번호가 되고, 뒷 부분 d는 페이지 번호의 주소에서 얼마나 떨어져 있는지 알려주는 offset이 된다. 따라서, p를 page table의 entry(=index)로 사용하면, 페이지 번호에 해당하는 frame 번호 f를 구할 수 있고 논리적 주소를 물리적 주소로 변환할 수 있게 된다. 그렇다면 위의 page table의 구현은 어떻게 이루어질까? 앞서 살펴본 기존의 연속 할당 방식에서는 MMU를 이용한 2개의 레지스터(base register, limit register)만으로 주소변환을 충분히 할 수 있었다. 하지만 불연속 할당 방식을 사용하는 paging 기법에서는 page table을 따로 두고 기존과 다르게 처리한다. 일단, Paging 기법에서 프로세스는 주로 4KB의 크기의 수많은 페이지로 나뉘어진다. 그래서 상당히 많은 entry 정보를 저장해야 하는 page table은 그 용량을 감당하기 위해 physical memory에 상주하게 된다. 즉, CPU의 논리적 주소를 주소 변환하기 위해서는 총 2번(page table 접근 한 번, 실제 data/instruction 접근 한 번) physical memory에 접근하게 된다. Page table 운용에 사용되는 Register의 경우에는 page table을 가리키는 Page-table base register(PTBR)과 테이블 크기를 보관하는 Page-table length register(PTLR)이라는 2개의 register를 사용한다. 또한, 속도를 높이기 위한 하드웨어 측면의 방책으로 associative register나 translation look-aside buffer(TLB)라는 고속 lookup hardware cache를 사용한다. TLB에 대하여 그림으로 살펴보자. 위 그림처럼 paging 기법에서 주소 변환을 수행하려면 두 번의 메모리 접근을 해야 하기 때문에, TLB라는 하드웨어의 지원을 통해 속도를 더 빠르게 가져갈 필요가 있다. TLB는 실제 캐쉬 메모리와는 다르지만 주소 변환만을 위한 일종의 캐쉬 메모리 역할을 하는데, page table에서 자주 쓰이는 일부 entry들을 TLB에 저장해두고 메모리보다 조금 윗단에서 entry를 빠르게 가져다 쓸 수 있게 해주는 역할을 한다. 즉, CPU가 주는 논리적 주소를 주소 변환할 때 먼저 TLB를 살펴보고, 만약에 TLB에 해당 entry가 있다면 한 번의 메모리 접근을, TLB에 entry가 없다면 원래대로 두 번의 메모리 접근을 한다. 유의할 점은 page table의 경우 page number를 index로 바로 frame number를 알 수 있는 반면, TLB는 page number와 frame number가 쌍으로 이루어져 있어서 frame number를 알고 싶다면 전체 TLB의 원소를 모두 다 검색해봐야 검색 유무를 판단할 수 있다는 것이다. 따라서, 이 검색을 원활히 진행시키기 위해 associative register들로 parallel search가 가능하도록 해 단번에 frame number를 알 수 있도록 만든다. 또한, page table은 각 프로세스마다 다르게 존재하므로, 이에 대응하기 위해 context switch가 일어날 때마다 TLB는 flush되어야 한다. 앞서 살펴본 것을 토대로 메모리 접근 시간을 파악해보면 위와 같다. 결론적으로 1보다 작은 값 입실론과 1에 아주 가까운 알파 값으로 인해 EAT(Effective Access Time)는 2보다 작아지게 되어, 적어도 메모리에 두 번 접근하는 것보다 나은 방법이 된다는 것이 증명된다. Two-Level Page Table (2단계 페이지 테이블) Two-Level Page Table은 위와 같이 바깥 page table과 안쪽 page table 두 개를 활용하는 방법이다. 본래의 Page Table에서는 공간적 낭비가 발생하기 때문에, 이를 막고자 나타난 것이 Two-Level Page Table이다. 현대 컴퓨터는 address space가 매우 큰 프로그램도 잘 지원할 수 있는데, 용량이 큰 프로세스라고 할지라도 대부분의 프로그램은 자신의 주소 공간의 매우 일부분만 사용한다. 이 경우, 기존의 page table은 배열이기 때문에 논리적 주소의 일부분만 사용되어 빈공간이 생기더라도 전체의 주소 공간을 저장할 수 있게끔 생성된다. 즉, 이 과정에서 생기는 빈공간들이 공간적 비효율성을 야기한다. 사실 바깥 page table과 안쪽 page table 두 가지를 사용하니까 시간적으로나 공간적으로나 더 낭비가 클 것 같지만 실제로는 충분한 이점이 있다. 앞서 말햇듯이 프로세스의 주소 공간 중 거의 쓰이지 않는 부분이 훨씬 많기 때문에, 바깥 page table에서 해당 부분들을 Null로 처리해버리면 Null로 처리된 곳에는 안쪽 page table이 생성되지 않아 공간적인 낭비가 감소하는 효과가 있다. Two-Level Page Table은 위와 같이 바깥 page table 속의 entry마다 안쪽 page table을 둬서 이 page table들을 두 번 거친 후에 물리적 메모리 주소에 도달하게 한다. 이 때, 안쪽 page table 각각의 크기는 4KB로 본래의 page의 크기와 동일하게 된다. Two-Level Page Table의 주소 공간에 대한 bit 수 분배는 위의 예시와 같으니 참고하도록 하자. Multi-Level Paging 프로세스의 주소 공간이 더 커지면, 다단계 페이지 테이블이 효율적이다. 페이지 테이블이 더 많아져 메모리 접근 횟수 역시 더 많아질 수 있지만, 공간 낭비를 더욱 줄일 수 있다. 또한, TLB를 사용하면 메모리 접근 횟수 및 총 소요 시간도 크게 줄일 수 있다. 예를 들어, 4단계 페이지 테이블을 이용하는 경우만 해도 위와 같이 메모리 접근 시간이 크게 소요되지 않음을 알 수 있다. Paging 기법에 관한 몇 가지 Issue 페이지 테이블의 Valid / Invalid bit 페이지 테이블에는 해당 페이지가 실제로 사용되느냐 안되느냐를 표현하는 valid-invaild bit이 존재한다. Valid는 해당 주소의 frame에 프로세스를 구성하는 유효한 내용이 있어 접근을 허용함을 뜻하고, invalid는 해당 주소의 frame에 유효한 내용이 없어 접근을 허용하지 않음을 뜻한다. Invalid에서 해당 주소 frame에 유효한 내용이 없다는 것은 프로세스가 해당 주소 부분을 사용하지 않는 경우 혹은 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우를 말한다. 만일 프로세스의 주소 공간에서 거의 쓰이지 않는 영역에 해당하는 페이지라면 invalid임을 표시해 구분하는 것이 유용하다. Frame number를 0으로 두는 것만으로는 그것이 0번 frame을 의미하는 것인지 메모리에 올라와 있지 않다는 것을 말하는지 분별할 수 없기 때문이다. 페이지 테이블의 Protection bit 페이지 테이블에는 또 하나의 bit이 존재한다. Protection bit이라고 불리는 이 bit은 해당 page의 연산(read/write/read-only)에 대한 권한을 부여한다. 프로세스에는 code, stack, data 영역이 있는데, code 부분에 해당하는 page의 경우 내용이 바뀌면 안되기 때문에 read only 연산만 가능하게 설정하고 다른 영역은 read, write 모두 가능하게 설정한다. Inverted Page Table 기존 page table의 큰 공간 낭비 문제를 해결하기 위한 또 하나의 방법이다. 기존 page table이 page number에 따라 page table entry를 만드는 것과 달리, inverted page table은 frame number에 따라 page table entry를 만든다. 그렇기에 page table도 프로세스마다 존재하는 것이 아니라 시스템에 단 하나 존재한다. 그리고 이를 보완하기 위해 page table 각각의 entry에 프로세스 ID를 추가로 넣어줘 어떤 프로세스의 page인지 구분할 수 있도록 한다. Inverted 방식의 page table은 한 개만 존재함으로써 공간 낭비를 극적으로 줄일 수 있다. 다만, 주소 변환을 하기 위한 시간적 overhead는 커지기 때문에, associative register를 활용해 병렬적으로 page table 검색을 하게끔하는 방식을 보완해 사용한다. Shared Page Shared page는 shared code가 page로 나뉠 때 사용되는 용어이다. Shared Code(=Re-entrant Code =Pure code)는 프로세스마다 동일한 프로그램을 실행함으로 인해 같은 코드가 쓰이는 경우에 read-only 상태로 공유하고 메모리에 올리는 하나의 코드를 말한다. 예를 들어, Text editor나 compiler, window systems 같은 프로그램들은 굳이 코드를 여러번 중복할 필요가 없기 때문에, shared code로 공유한다. 이러한 shared code는 모든 프로세스의 논리적 주소 공간에서 동일한 위치에 있어야 하며, 각 프로세스의 독립적인 private code와 data는 프로세스의 논리적 주소 공간 어디에 위치해도 상관없다. Segmentation 기법 이제 또 다른 대표적인 불연속 할당 방식으로 Segmentation 기법을 알아보자. Segmentation은 프로그램을 의미 단위로 구성된 여러개의 segment로 나누어 할당하는 방식이다. Segment는 크게는 프로그램 전체, 작게는 함수 하나하나로 정의 될 수 있는데, 일반적으로 code, data, stack 영역이 하나씩 segment로 분류된다. Segmentation에서 논리적 주소는 segment-number와 offset으로 구성된다. 또한 Paging 기법과 비슷하지만 다르게 사용되는 segment table이 존재하며, 테이블 내 각각의 entry에는 segment의 물리적 주소 시작점을 담는 base와 segment의 길이를 담는 limit이 존재한다. 또한, 물리적 메모리에서 segment table의 위치를 담는 Segment-table base register(STBR)와 프로그램이 사용하는 segment의 수를 기록하는 Segment-table length register(STLR)가 존재한다. 위의 그림에서 CPU가 논리적 주소를 주게 되면, segment table에서 논리적 주소의 segment 번호 s에 해당하는 entry를 찾게 된다. 그리고 entry에서의 base 값과 논리적 주소의 offset d를 이용해 물리적 주소에 접근한다. 또한, 물리적 메모리에 접근하기 전에 해당 entry에서 limit 값을 확인하여, 논리적 주소의 offset 값이 프로그램의 주소 범위를 벗어나지 않았는지 파악한다. Paging 기법과 달리 각각의 Segement는 길이가 다르기 때문에, entry에 존재하는 limit 값을 통해 segment의 길이를 결정짓는 것이 중요하고, 이를 활용해 프로그램의 범위를 벗어나는 악의적인 접근에 대해 trap을 건다. Segmentation은 segment 각각의 길이가 동일하지 않으므로 외부조각이 발생하는 문제가 있다. 하지만, read/write/execution 등의 권한을 부여하는 protection 작업이나 각각의 프로세스가 동일한 코드를 공유하는 sharing 작업에서는 의미 단위를 강조하는 Segmentation이 매우 효과적이라는 장점도 있다. 위 그림은 Segmentation의 한 예시인데, paging 기법의 크기가 4KB인 수많은 page 개수에 비하면 segment의 개수는 현저히 적음을 알 수 있다. 프로그램이 의미 단위로 큼직큼직하게 쪼개지기 때문에 위 예시에서는 segment의 개수가 5개밖에 되지 않는다. 대신 segment의 용량은 4KB로 크기가 고정되어 있는 page에 비하면 매우 커질 수 있다. 또한, segment의 개수가 적어짐에 따라 segment table의 entry 개수도 적어지므로, page table과 달리 table로 인한 공간 낭비가 현저하게 감소한다. Paged Segmentation (=Segmentation with Paging) Paged Segmentation은 Paging 기법과 Segmentation 기법을 혼합하여 Segmentation된 각각의 segment에 paging을 적용하는 방법이다. 이렇게 혼합 방식을 사용하면 Segmentation에서 발생하는 외부 조각 문제를 해결하고 protection과 sharing은 본래의 의미 단위대로 처리할 수 있어 유용하다. 실제로도 순수한 Segmentation만을 사용하는 컴퓨터는 없으며 Segmentation을 사용한다면 이렇게 Paging과 혼합적으로 운용한다. Paged Segmentation의 과정을 살펴보자. 위 그림에서 CPU가 논리적 주소를 주면 segment 번호 s를 사용해 segment table의 해당 entry에 접근한다. 그리고 offset d가 해당 entry의 limit 값을 넘어가지 않는다면, d에 존재하는 페이지 번호 p를 사용해 해당 segment에 mapping된 page table의 entry에 접근한다.(offset d가 limit 값을 넘어간다면, trap을 건다.) 그 후, entry에 해당하는 프레임 번호 f와 d에 존재하는 offset d’을 더해 물리적 주소로 변환을 완료한다. Memory Management 챕터에 관하여 메모리 관리 챕터는 물리적 메모리에 관하여 다뤘다. 이 메모리 접근 과정에서 운영체제의 역할은 없었고, 오직 하드웨어의 역할만 있었음을 유의하자. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-09

8-1. 메모리 관리

Symbolic Address VS Logical Address VS Physical Address 1. Symbolic Address 프로그래머 입장에서 메모리를 다룰 때, 숫자가 아닌 변수명, 함수명 등으로 메모리를 조작하는 상징적 주소 Symbolic Address가 compile되면 숫자로 된 Logical Address가 됨 2. Logical Address (=Virtual Address) 프로세스마다 독립적으로 가지는 주소 공간 각 프로세스마다 0번지부터 시작 CPU가 보는 주소 3. Physical Address 실제 메모리에 올라가는 위치 프로그램이 실행될 때, Logical Address를 Physical Address로 주소 변환 (주소 바인딩) 주소 바인딩 (Address Binding) 어떤 프로그램이 실행되기 위해서는 물리적 주소에 올라가야 하는데, 물리적인 주소 어디로 올라갈지 결정하는 것을 의미한다. 현대 컴퓨터는 어떤 프로그램을 실행할 시 프로그램 내 instruction들을 산발적으로 여러 메모리 상 위치에 나눠 실행하지만, 여기서는 하나의 프로그램을 통째로 메모리 상 균일한 위치에 올린다고 가정하고 진행한다. 1. 주소 바인딩이 실현되는 3가지 시점 Compile time binding Physical Address가 컴파일 시에 정해져서 Logical Address와 Physical Address와 같음 이 때, 컴파일러가 생성한 코드를 절대 코드(absolute code)라고 지칭 메모리가 많이 비어있을 때도 특정 위치부터 주소를 바인딩하기 때문에 비효율적 시작 위치 변경시 재컴파일해야 함 과거에 쓰이던 방식 Load time binding 프로그램이 실행되는 타이밍에 Loader가 Physical Address를 부여함 정해진 위치가 아닌 비어 있는 메모리 위치에 주소를 바인딩 이 때, 컴파일러가 생성한 코드는 재배치가능 코드(relocatable code)라고 지칭 Execution time binding (=Run time binding) Physical Address를 부여하는 타이밍과 방식은 Load time binding과 동일 프로그램 실행 중에도 프로세스의 메모리 상 위치가 바뀔 수 있다는 점이 특징 CPU가 주소를 참조할 때마다 binding을 점검 이를 위해서 하드웨어적인 지원이 필요 (ex. MMU) 주소 바인딩이 되더라도 Logical Address는 코드상에 남아 있으므로, CPU는 Physical Address가 아닌 이 Logical Address를 참조하고 요청해 연산을 수행한다. 2. MMU (Memory-Management Unit) Logical Address를 Physical Address로 mapping해 주는 Hardware device Execution time binding을 지원 2개의 register를 이용해 주소 변환 지원 (relocation register, limit register) Relocation register(=base register): 접근할 수 있는 물리적 메모리 주소의 최소값 Limit register: 논리적 주소의 범위 user program은 logical address만 다루며, 실제 physical address는 볼 수 없고 알 필요도 없음 MMU scheme 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register 값을 더한다. 아래에 예시를 살펴보자. 위 그림은 process p1이 실행되어 있는 상황에서 CPU가 p1의 한 instruction을 요청하는 과정을 담고 있다. 먼저 왼쪽 하단의 p1 그림은 p1의 논리적 주소를 보여준다. p1은 0~3000번지까지의 논리적 주소를 가진다. 이 때, limit register는 p1의 가장 끝 주소인 3000을 기억한다. 또한, 현재 CPU는 0~3000까지의 논리적 주소 중 346번지에 있는 instruction을 요청한 상황이다. 물리적 주소 입장에서 보면, p1은 실행될 때 14000~17000번지까지의 주소를 부여 받았다. 논리적 주소의 범위인 3000만큼을 물리적 주소도 동일하게 받았다. 이 때, relocation register는 p1의 물리적 주소 시작위치인 14000을 기억한다. 그렇다면 CPU가 요청한 instruction의 물리적 메모리 상 위치는 어떻게 될까? CPU가 요청한 논리적 주소 346번지 instruction은 relocation register에 저장된 물리적 위치 시작 주소 14000에 346을 그대로 더한 14346번지 물리적 주소에 존재한다. 즉, 논리적 주소는 상대적으로 표현한 것이기 때문에 실제 위치에서 상대적으로 계산하면 원하는 instruction의 물리적 주소를 알 수 있다. 한편, limit register는 어떤 프로그램이 악의적으로 프로세스의 메모리 범위를 벗어나는 주소를 요청하는 경우를 막기 위해 존재한다. 예를 들어, 위 그림에서 CPU가 요청한 논리적 주소가 4000이라고 하면 p1의 물리적 주소 범위인 14000~17000을 벗어나 18000의 주소를 요청한 것이기 때문에 limit register가 이를 막는다. MMU의 지원을 받아 주소 변환을 하는 과정을 일반화하면 위와 같이 도식화할 수 있다. CPU가 어떤 instruction의 logical address를 요청하면 그 주소가 limit register에 저장된 값을 넘지 않는지(논리 주소가 프로그램의 크기를 넘어가지 않는지) 확인한다. 만약에 값을 넘어가면, trap이 걸려 운영체제가 해당 프로그램의 CPU 제어권을 앗아가고 범위를 벗어난 악의적인 시도에 대해 프로그램을 종료시키는 등의 제제를 가한다. 값이 벗어나지 않는다면, 요청한 logical address 값에 relocation register에 저장된 값을 더해 physical address로 주소 변환을 하고, 해당 주소에 존재하는 내용을 CPU에게 전달한다. Dynamic Loading 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것을 말한다. 프로그램의 코드는 모든 코드가 항상 일정하게 쓰이는 것이 아니라 오류 처리 루틴같은 상대적으로 덜 쓰이는 부분이 존재한다. Dynamic Loading은 이렇게 가끔씩 사용되는 많은 양의 코드를 다루는 경우에서 메모리의 효율성을 크게 증대시킨다. 다만, 이 개념은 운영체제가 제공하는 라이브러리로 프로그래머가 직접 구현하는 것을 의미하며, 운영체제가 스스로 메모리에 올리고 쫒아내는 것을 관리하는 paging system과는 다른 개념임을 유의해야 한다. Overlays 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 것을 말한다. Dynamic Loading과 그 의미가 거의 동일하나 초창기 컴퓨터 시스템에서 사용되던 말이다. 작은 공간의 메모리에 큰 프로그램을 실행시키기 위해 프로그래머가 직접 수작업으로 프로그램을 분할해 메모리에 올리던 방법으로, 운영체제의 지원없이 구현했기 때문에 프로그래밍이 매우 복잡했다. Swapping Swapping 프로세스를 일시적으로 메모리에서 backing store로 쫒아내는 것을 의미한다. 메모리에서 쫒았다가 다시 올리는 작업이므로, 프로세스가 특정 위치에 반드시 복귀해야 하는 Compile time binding, Load time binding보다는 빈 메모리 영역 아무곳에나 프로세스를 올릴 수 있는 Execution time binding에서 더 적합하다. Swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)에 해당한다. Backing store (=swap area) 하드 디스크의 일부분으로, 많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간을 말한다. Swap in / Swap out 프로세스가 메모리에서 쫒겨나 backing store로 내려가는 것을 Swap out이라고 하고, backing store에서 다시 메모리로 올라가는 것을 Swap in이라고 한다. 일반적으로 중기 스케줄러가 메모리에 올라와 있는 프로세스들의 CPU priority를 고려하여 swap out시킬 프로세스를 선정한다. Dynamic Linking Linking을 실행 시간(execute time)까지 미루는 기법이다. 본래의 Linking(=Static Linking)은 실행 파일을 만들 때, 라이브러리 실행 코드가 실행 파일 코드에 포함되어 실행 파일의 크기가 커진다. 즉, 같은 라이브러리를 쓰는 프로세스라고 하더라도 각각의 프로세스 주소 공간에 라이브러리 코드가 매 번 들어 있는 실행파일이 생성된다. 반면에, Dynamic Linking은 만들어진 실행 파일 속에 라이브러리 루틴의 위치를 찾기 위한 포인터(stub라고 하는 작은 코드)만 넣어 두고 라이브러리 코드 전체는 포함시키지 않는다. 그리고 실행 파일에서 해당 라이브러리를 호출할 시, 포인터로 라이브러리 파일의 위치를 찾아 해당 라이브러리 코드를 메모리에 올리고 실행한다. 만일, 다른 프로세스가 라이브러리를 호출해 이미 메모리에 올라와 있는 경우, 실행만 한다. 본래의 Linking에 비해 메모리 공간을 덜 잡아먹고 실행 파일의 크기가 줄어든다는 점에서 효율적이다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-06-08

7. Deadlock

Computer Science · 2021-06-03

6-2. Process Synchronization 문제

Computer Science · 2021-05-27

6-1. Process Synchronization 문제

Computer Science · 2021-05-27

5-2. CPU 스케줄링

Multi-level queue 우선도가 다른 ready queue Ready queue를 foreground(interactive)와 background(batch - no human interaction)으로 분리한다. 그리고 foreground에는 RR, background에는 FCFS 등으로 각 큐에 독립적인 스케줄링 알고리즘을 설계한다. 또한 어떤 큐에게 CPU를 줄 지 (그 이후에는 큐에 있는 어떤 프로세스에게 CPU를 줄 지)결정하는 작업이 필요한데, 이를 큐에 대한 스케줄링으로 해결한다. Fixed priority scheduling은 우선도를 최우선으로 하여 우선도가 높은 foreground에게 먼저 scheduling하고 그 다음 background에게 주는 방식이다. 이 방식에서는 starvation이 단점이 될 수 있다. 이에 대한 대안으로 Time Slice가 있는데, 이 스케줄링은 각 큐에 CPU time을 적절한 비율로 할당한다. (ex. foreground에 80% background에 20% CPU time 분배) Multi-level feedback queue 우선도가 높은 queue여도 상황에 따라 낮은 우선도 queue가 높은 우선도 queue보다 우선될 수 있다. Multi-level queue의 고정된 우선도라는 단점을 극복하기 위한 대안이다. 예를 들어, 들어오는 프로세스를 우선도가 가장 높은 queue에 줄 세우고 RR 방식을 사용하되, 우선도가 낮은 queue일수록 time quantum을 길게 준다. 그래서 time quantum 내에 프로세스가 완료되면 큐에서 내보내고, 완료되지 않았으면 다음으로 우선도가 높은 큐에 해당 프로세스를 줄 세운다. 이렇게 하면 CPU burst가 짧은 프로세스에 우선 순위를 더 많이 주고, CPU burst가 긴 프로세스의 우선도는 더 낮출 수 있다. 특수한 상황에서의 CPU Scheduling 1. Multiple-Processor Scheduling (간략히 다룸) Homogeneous Processor라면 Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있는가하면 어떤 프로세스는 특정 프로세서에서만 수행되어야 하는 경우가 존재하므로 이를 고려해야 한다. Load sharing 일부 프로세서에 job이 몰리지 않게 하는 적절한 메커니즘이 필요하다. 모든 CPU가 공동 큐를 사용하는 방법 혹은 각각의 CPU마다 별개의 큐를 사용하는 방법이 있다. Symmetric Multiprocessing (SMP) 각 프로세스가 각자 알아서 스케줄링을 결정한다. Asymmetric Multiprocessing 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그것에 따른다. 2. Real-Time Scheduling Time sharing과 달리 미리 스케줄링을 계획하고 데드라인이 보장되도록하는 방식 Hard real-time systems 정해진 시간안에 반드시 끝내도록 스케줄링하는 것 Soft real-time computing (많이 쓰임) 영화 스트리밍과 같이 time sharing 시스템에서 다른 일반적인 프로세스들과 섞여서 실행되지만, 일반 프로세스에 비해 높은 priority를 갖게해 데드라인을 지키도록 지향하는 스케줄링. (조금은 데드라인을 어기는 것이 허용됨) 3. Thread Scheduling Local Scheduling User level thread의 경우 운영체제가 thread의 존재를 모르기 때문에, 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다. (운영체제는 CPU를 프로세스에게 전달만 하고 어떤 스레드에 CPU를 줄지는 해당 프로세스 내부에서 결정한다.) Global Scheduling Kernel level thread의 경우 운영체제가 thread의 존재를 알고 있기 때문에, 일반적인 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정한다. Algorithm Evaluation 1. Queueing models (Server를 CPU로 보자.) 확률분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산한다. (이론적 측면에서 많이 사용하는 방법) 2. Implementation (구현) & Mesurement (성능 측정) 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 및 비교한다. ex) 리눅스 커널에 나의 CPU 스케줄링 알고리즘을 구현해보고, 실제 프로그램을 돌려서 원래의 리눅스 환경과 나의 알고리즘이 적용되어 있는 리눅스 커널의 성능을 비교해본다.) 3. Simulation (모의 실험) 알고리즘을 모의 프로그램으로 작성 후 trace(실제 프로그램으로부터 추출한 input data)를 입력으로 하여 결과를 비교한다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

5-1. CPU 스케줄링

CPU Burst & I/O Burst 어떤 프로그램이 실행된다는 것은 CPU Burst와 I/O Burst가 번갈아 가며 일어나는 것을 의미한다. 프로그램의 종류에 따라 두 Burst의 빈번함이 다를 수 있는데, ① 사용자 관여가 많은 (키보드 입력, 모니터 출력 등이 잦은) 프로그램(interactive job)은 CPU Burst 시간이 짧아지면서 두 Burst가 번갈아 빈번히 나타나고, ② 과학 계산용 프로그램 같은 연산 시간이 긴 프로그램은 CPU Burst 시간이 길어지면서 I/O 비중이 크게 줄어든다. 위 그래프는 CPU Burst 시간과 그 빈도에 따라 프로그램들을 분류한 것인데, CPU Burst 시간이 짧을수록 프로그램의 CPU Burst 빈도가 잦음을 알 수 있다. 이 같이 CPU를 잡고 계산하는 것보다 I/O에 더 많은 시간을 사용하는 프로그램들을 I/O bound job이라고 하며, 반대로 계산 위주로 구성된 프로세스는 CPU bound job이라고 부른다. 여러 종류의 job(=process)이 섞여 있기 때문에, 그들을 적절한 CPU Scheduling이 필요하다. → CPU bound job이 CPU를 너무 오래 사용하면 효율성이 떨어지므로, I/O bound job(=Interactive한 job)에게 우선적으로 CPU를 주도록 지향하는 것이 CPU Scheduling의 주요한 목표이다. CPU Scheduler & Dispatcher 1. CPU Scheduler 운영체제의 여러 코드 중 CPU schedule 기능을 담당하는 코드를 지칭하는 용어다. Ready 상태의 프로세스 중 어떤 프로세스에게 CPU를 줄 지 결정한다. 2. Dispatcher 역시 운영체제의 여러 코드 중 특정 코드를 지칭하는 용어다. CPU 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. 이 과정을 문맥 교환(Context Switch)이라고 한다. CPU Scheduling이 필요한 경우 1, 4의 스케줄링은 nonpreemptive(=자진 반납, 비선점형), 나머지 모든 스케줄링은 preemptive(=강제로 뺏음, 선점형, 대부분의 현대적인 CPU 스케줄링에서 사용) 3의 경우 일반적으로 원래 CPU를 점유하던 프로세스에게 timer가 끝날 때까지 CPU를 다시 쓰게 하지만, 만약 우선순위가 가장 높은 프로세스의 I/O가 완료된 것이었다면 해당 프로세스에게 CPU를 바로 넘기게 된다. Scheduling Criteria (CPU 스케줄링 성능 척도) 1. 시스템 입장에서의 성능 척도 : CPU 하나로 최대한 일을 많이 시키자! CPU utilization (이용률) : 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율 Throughput (처리량) : 주어진 시간 동안 완료한 작업(process)의 수 2. 프로그램 입장에서의 성능 척도 : 내가 CPU를 빨리 얻어서 내가 빨리 끝나는 게 중요! Turnaround Time (소요시간, 반환시간) : CPU를 사용하기 위한 대기시간을 포함해 CPU를 사용완료하고 빠져나갈 때까지 걸린 총 시간 (다른 프로세스와 번갈아 CPU를 사용하게 되어도 그 모든 시간을 합하여 계산한다.) 프로세스가 CPU를 쓰러 대기열에 들어와서 CPU를 사용하고 I/O하러 나갈 때까지의 시간 ex) 중국집 손님이 코스요리를 시켰을 때, 중국집에 들어와서 요리를 기다리고 먹고를 반복하다가 다 먹고 나갈 때까지의 모든 시간 Waiting Time (대기시간) : Ready queue에서 대기하며 걸린 순수한 시간 CPU Burst와 I/O Burst가 번갈아 반복된다면, 그동안 생긴 여러 번의 대기 시간을 모두 합하여 계산하는 것이 아래의 Response Time과의 차이점이다. ex) 손님이 코스요리 음식을 기다린 모든 시간 Response Time (응답시간) : Ready queue에 들어와서 처음 CPU를 얻기까지 걸린 시간 (∝ time sharing) ex) 첫 번째 음식이 나올 때까지 기다린 시간 CPU Scheduling Algorithm 1. FCFS (First-Come First-Served) - nonpreemptive (비선점형) 먼저 들어온 프로세스를 먼저 처리한다. 먼저 들어온 프로세스가 CPU bound job일 경우 처리 시간이 길어지므로, 효율적인 스케줄링은 아니다. ex 1) 0초 대에서 프로세스들이 간발의 차이로 P1, P2, P3 순으로 들어왔을 때 ex 2) 0초 대에서 프로세스들이 간발의 차이로 P2, P3, P1 순으로 들어왔을 때 FCFS는 ex 1과 ex 2의 waiting time 같이 들어온 작업의 순서에 따라 결과 차이가 크게 나타나는 비효율성이 있다. 이처럼 작업 시간이 긴 프로세스에 의해 작업 시간이 짧은 프로세스들이 실행되지 못하는 상황을 Convoy effect(호위 효과)라고 한다. 2. SJF (Shortest-Job-First) CPU Burst가 짧은 프로세스에게 CPU 제어권을 제일 먼저 스케줄한다. 이 때, 각 프로세스의 다음 번 CPU Burst time을 고려하여 스케줄링에 활용한다. Nonpreemptive SJF 일단 CPU를 잡으면 해당 프로세스의 CPU Burst가 완료될 때까지 CPU를 선점(preemption)당하지 않는다. → 프로세스가 CPU를 다 사용하고 나가는 시점에 CPU 스케줄링을 결정 ex) Preemptive SJF (SRTF = Shortest-Remaining-Time-First) 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗는다. 주어진 프로세스들에 대하여 minimum average waiting time을 보장한다. (어떤 알고리즘도 이 waiting time 보다 빠를 수 없다.) → 새로운 프로세스가 들어올 때와 프로세스가 빠져 나갈 때, 두 가지 시점에서 CPU 스케줄링이 이뤄진다. ex) SJF의 문제점 Starvation (기아 현상) : 우선도가 낮은 프로세스(=CPU burst time이 긴 프로세스)는 영원히 실행되지 못할 수 있다. CPU burst time의 추정 : CPU burst time은 추정만 가능하기에 실제 정확한 시간을 알고 SJF를 수행하기는 어렵다. CPU burst time 추정은 과거의 CPU 사용 흔적을 바탕으로 exponetial averaging 기법을 사용해 이뤄진다. 이 기법은 과거의 흔적일수록 덜 반영하고 최근 흔적일수록 많이 반영하는 흐름을 가진다. 3. Priority Scheduling 높은 우선 순위를 가지는 프로세스에게 CPU를 할당한다. 작은 정수가 high priority를 나타낸다. (SJF도 일종의 Priority Scheduling → priority = predicted next CPU burst time) Nonpreemptive : CPU를 선점한 프로세스에게서 CPU를 빼앗지 않는다. Preemptive : 우선도에 따라 CPU를 빼앗긴다. (SJF 설명과 유사) Problem : Starvation (기아 현상)!!! → Solution) Aging : 시간이 지남에 따라 우선도가 낮은 프로세스의 우선도를 높인다. 4. Round Robin (RR) - Preemptive (선점형), 현대적 CPU Scheduling 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지며 이 할당 시간이 지나면 CPU를 선점당하고 ready queue의 제일 뒤로 가서 다시 줄을 선다. n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. (어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.) RR의 특징 Response Time 빨라지는 장점 Waiting Time은 CPU burst time이 긴 프로세스일수록 길고 반대의 경우 짧음 Performance q large → FCFS q small → context switch 오버헤드가 커진다. ex) Time quantum이 20일 때 → 일반적으로 SJF보다 average turnaround time이나 waiting time은 길어질 수 있지만 response time은 더 짧다. 또한, CPU 실행 시간이 동일한 프로세스들일 경우 RR이 비효율적일 수 있지만, 일반적으로는 CPU 실행 시간이 다르기 때문에 대부분에서 효율적이다. Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

4-2. 프로세스 관리

프로세스의 생성, 실행 및 종료에 관한 시스템 콜 프로세스 관리 시스템 콜 정리 1. fork() 시스템콜 위 그림의 두 코드는 부모 프로세스(좌), 자녀 프로세스(우)이다. 처음 부모 프로세스가 코드를 수행하다가 fork 시스템 콜을 만나면, 부모 프로세스를 똑같이 복사해 자녀 프로세스를 만들고 이후 명령을 계속 실행한다. 자녀 프로세스는 부모 프로세스의 Program Counter를 그대로 복제했기 때문에, 부모 프로세스와 마찬가지로 fork의 바로 밑 코드부터 실행한다. 또한, 부모 프로세스는 fork의 return 값으로 양수, 자녀 프로세스는 0을 pid에 취해 서로를 구분한다. 2. exec() 시스템콜 fork로 복사한 프로세스를 다른 프로그램으로 다시 덮어쓰기 위해 exec 시스템콜을 사용한다. 위와 같은 경우는 execlp 함수를 만나면, exec 시스템 콜이 발생해 복사한 자녀 프로세스에 새로 date 파일을 덮어써 실행하게 된다. 따라서, date가 실행되면 위 그림에 보이는 원래의 자녀 프로세스의 코드로는 다시 돌아갈 수 없다. 3. wait() 시스템콜 부모 프로세스가 wait 시스템 콜을 걸면, 부모 프로세스는 자식 프로세스가 종료될 때까지 blocked 상태가 된다. 자식 프로세스가 종료되면 부모 프로세스는 위 그림 처럼 wait 뒤에 있는 S2 코드를 계속 실행한다. (자식이 종료될 때까지 부모가 기다리는 모델에 해당) ex) 쉘 프롬프트의 커서가 깜빡이는 상태에서 프로그램을 실행 시 자식 프로세스 형태로 실행되고, 쉘 프롬프트 프로그램은 부모 프로세스로서 자식 프로세스가 종료될 때까지 기다렸다가(blocked 상태) 다시 실행된다. 4. exit() 시스템콜 자발적 종료 마지막 statement 수행 후 exit() 시스템 콜을 통해 이루어진다. 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치로 컴파일러가 넣어준다. 비자발적 종료 부모 프로세스가 자식 프로세스를 강제 종료 시킬 때 ex) 자식 프로세스가 한계치를 넘어서는 자원을 요청할 때, 자식에게 할당된 태스크가 더 이상 필요하지 않을 때 부모가 종료될 때 (프로세스는 항상 자식이 먼저 종료되고 부모가 종료됨) 키보드로 kill, break 등을 칠 때 프로세스 간 협력 독립적 프로세스 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못한다. 협력 프로세스 어떤 경우에는 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미치며 서로 정보를 교환하는 것이 효율적일 수 있다. 프로세스 간 협력 메커니즘 (IPC: Interprocess Communication) massage passing : 커널을 통해 메시지를 전달한다. (프로세스들끼리 직접은 불가능하다.) Message system : 프로세스 사이에 공유 변수를 일체 사용하지 않고 통신하는 시스템 Direct Communication : 통신하려는 프로세스의 이름을 명시적으로 표시 Indirect Communication : mailbox(혹은 port)를 통해 메시지를 간접 전달 (프로세스 이름을 명시하지 않으므로 다른 프로세스가 열어볼 수 도 있음) shared memory : (원칙적으로는 안되지만) 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 메커니즘 Thread는 하나의 프로세스이므로 프로세스 간 협력으로 보기에는 어렵다! Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

4-1. 프로세스 생성과 종료

프로세스의 생성 부모 프로세스가 자식 프로세스를 Copy-on-write(COW) 기법으로 생성한다. COW는 무언가의 변경(write)이 있을 때, 부모의 주소 공간 중 변화가 있는 부분을 copy해 자식의 주소 공간을 만드는 기법이다. 또한, 자식이 자식을 생성하고 그 수가 많아지면 프로세스는 트리를 형성한다. 자식은 부모 프로세스의 ① 주소 공간(binary & OS data)을 복사해 ② 그 공간에 새로운 프로그램을 올린다. ex) 유닉스에서는 fork() 시스템 콜이 주소 공간을 복사하고 exec() 시스템 콜이 새로운 프로그램을 메모리에 올린다. 생성된 프로세스는 자원을 운영체제로부터 받거나 부모 프로세스와 공유한다. (부모와 공유하지 않는 것이 일반적) 수행 : 부모와 자식이 공존하며 수행되는 모델 / 자식이 종료될 때까지 부모가 기다리는 모델 프로세스의 종료 프로세스는 마지막 명령을 수행한 후 exit이라는 시스템콜을 통해 운영체제에게 이를 알려준다. 프로세스 종료는 항상 자식이 먼저 종료되고 그것을 부모 프로세스가 정리하는 원칙이 있다. 그리고 wait 시스템콜을 사용해 자식 프로세스는 자신이 종료될 때 부모 프로세스에게 output data를 보내며 각종 자원들을 운영체제에 반납한다. 부모 프로세스가 자식의 수행을 abort 시스템콜로 강제 종료시키는 경우도 있다. 자식이 할당 자원의 한계치를 넘어설 때 (비유: 자식이 돈을 펑펑 쓸 때) 자식에게 할당된 태스크가 더 이상 필요하지 않을 때 (비유: 자식에게 시키던 일이 전부 끝나서 자식이 필요 없을 때) 부모가 종료될 때, 여러 개의 자식 프로세스들을 차례차례 단계적으로 죽이고 부모가 죽는다. 프로세스의 세계는 꽤 잔인하다! Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-26

3-2. 스레드

Thread (= lightweight process) (↔ heavyweight process, 전통적인 개념의 프로세스) 하나의 프로세스 내부에 CPU 수행 단위를 여러 개 두는 것을 말한다. 각각의 스레드는 CPU 수행과 관련된 정보만 제외하고 프로세스의 모든 것을 공유한다. 동일한 일을 수행하는 프로세스를 여러 개 띄워 놓고 싶다면, 하나의 주소 공간에 여러 개의 스레드를 사용하는 것이 효율적이다. 따라서, Program Counter를 여러 개 두고 register의 값들을 별도로 기억해두어 각각의 스레드가 스스로에게 필요한 code를 실행하게끔 한다. 함수 호출 및 return과 관련해서 stack도 스레드마다 따로 둔다. 스레드의 구성 1. Thread의 구성 program counter register set stack space 2. Thread가 동료 thread와 공유하는 부분 (=task) code section data section OS resources 3. Thread의 장점 Responsiveness(=빠른 응답성) 다중 스레드 태스크 구조에서는 하나의 서버 스레드가 blocked(waiting) 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행(running)되어 빠른 처리가 가능하다. ex) 웹페이지를 읽어오는 작업(I/O)이 오래걸리면 웹브라우저는 아무것도 못하는 blocked 상태가 된다. 반면에, 여러 개의 스레드로 웹브라우저를 만들면, 그림을 불러오는 작업이 오래 걸리더라도 다른 빠른 작업들을 먼저 화면에 보여줄 수 있다. (일종의 비동기식 입출력) Resource Sharing 메모리 자원을 효율적으로 사용할 수 있다. (자원 절약) Economy Thread를 Creating & CPU switching(문맥교환)하는 것은 process의 그것보다 훨씬 overhead가 작다. 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율(throughput)과 성능 향상을 얻을 수 있다. Utilization of MP Architectures (CPU가 여러 개 달린 컴퓨터(Multi-Processor)에서만 해당) 병렬성을 높일 수 있다. ex) 행렬 곱셈 작업을 각 스레드가 다른 CPU에서 서로 다른 행과 열을 병렬로 계산 가능 4. Thread 구현 방법 Kernel Threads Kernel에 의해 지원된다. 스레드가 여러 개 있다는 사실을 운영체제가 알고 있어서 하나의 스레드가 다른 스레드에게 CPU를 넘기는 작업도 운영체제가 CPU 스케줄링하듯 진행한다. User Threads Library에 의해 지원된다. 프로세스 안에 여러 개의 스레드가 있다는 사실을 운영체제가 모르고 유저 프로그램 스스로 여러 개의 스레드를 관리한다. 따라서, 구현 상의 제약이 더 있을 수 있다. 몇몇의 real-time threads Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-18

REST API 이해하기

REST API의 정의 Representational State Transfer의 약자 정보들을 주고 받는 HTTP 요청을 보낼 때, 어떤 URI에 어떤 메서드를 사용할지 개발자들 사이에 널리 지켜지는 약속 (Software Architecture) REST를 지켰을 때 각 요청이 어떤 동작이나 정보를 위한 것인지를 그 요청의 모습 자체만 봐도 추론 가능해짐 과거의 복잡했던 SOAP 방식을 대체하여 최근에 가장 널리 쓰이는 양식 REST API의 구성 자원(Resource) - URI를 통해 식별 (네트워크 상에 존재하는 자원을 구분하는 식별자) 행위(Verb) - HTTP Method에 따라 자원에 접근 표현(Representations) 혹은 정보(Message) - HTTP 헤더와 바디, 응답 코드를 활용 REST의 특징 Uniform 리소스에 대한 조작이 통일되고 한정적인 인터페이스로 구성된 아키텍처 스타일 (Uniform Interface) Stateless 작업을 위한 상태정보를 따로 저장, 관리하지 않고 단순히 들어오는 요청만 처리 덕분에 구현이 단순해짐 Cacheable 기존 웹표준을 사용하므로 웹의 기존 인프라를 이용해 캐싱 기능 적용 가능 Self-descriptiveness REST API 메시지만으로도 무슨 의미인지 쉽게 이해할 수 있는 자체 표현 구조를 가짐 Client - Server 구조 서버와 클라이언트의 구분이 명확 계층형 구조 REST 서버는 다중 계층으로 구성될 수 있으며 보안, 로드 밸런싱, 암호화 계층을 추가해 구조상의 유연성을 둘 수 있음 PROXY, 게이트웨이 같은 네트워크 기반의 중간매체를 사용할 수 있게 함 REST API 디자인 가이드 요약 REST API 중심 규칙 URI는 정보의 자원을 표현해야 합니다. 리소스 명은 동사보다는 명사를 사용 자원에 대한 행위는 HTTP Method(GET, POST, PUT, DELETE)로 표현합니다. POST: 해당 URI를 요청하면 리소스를 생성합니다. GET: 해당 리소스를 조회합니다. PUT: 해당 리소스를 수정합니다. DELETE: 해당 리소스를 삭제합니다. URI 설계 시 주의할 점 슬래시 구분자는 계층관계를 나타낼 때 사용합니다. 마지막 문자로 슬래시를 포함하지 않습니다. 하이픈(-)은 URI 가독성을 높이는데 사용합니다. 언더스코어(_)는 가독성을 해치므로 URI에 사용하지 않습니다. URI 경로에는 소문자가 적합합니다. 파일 확장자(.jpg, .png 등)는 URI에 포함시키지 않습니다. 리소스 간의 관계를 표현하는 방법 REST 간의 연관 관계는 다음과 같이 표현합니다. /리소스명/리소스 ID/관계가 있는 다른 리소스명 GET : /users/{userid}/books (일반적으로 소유 ‘has’의 관계를 표현할 때) 관계명이 복잡하다면 서브 리소스에 명시적으로 포함할 수 있습니다. GET : /users/{userid}/likes/books (관계명이 애매하거나 구체적 표현이 필요할 때) Collection과 Document 개념을 활용한 리소스 표현 Collection: 문서들의 집합, 객체들의 집합 Document: 하나의 문서, 하나의 객체 Collection과 Document로 표현하면 URI 설계가 더욱 용이해집니다. http://restapi.com/sports/soccer/players/7 sports, players라는 Collection과 soccer, 7이라는 document로 표현 Collection은 복수로 Document는 단수로 표현해주는 것이 좋습니다. REST API의 정보 HTTP 바디 자원에 대한 정보를 HTTP 바디에 데이터로 담아 전달합니다. 데이터 포멧으로는 최근 JSON이 가장 많이 쓰입니다. HTTP 헤더 HTTP 바디의 컨텐츠 종류를 명시할 수 있고 인증 권한 정보를 담습니다. 요청 HTTP 헤더는 ‘Accept’ 항목을, 응답 HTTP 헤더는 ‘Content-type’을 담습니다. 다음은 ‘Content-type’의 몇 가지 예입니다. application/json application/xml text/plain image/jpeg image/png HTTP 응답 상태 코드 잘 설계된 REST API는 URI 뿐만 아니라 요청에 대한 응답까지 잘 내어주어야 합니다. 200: 클라이언트의 요청을 정확히 수행함 201: 클라이언트가 어떤 리소스 생성을 요청했고, 해당 리소스가 성공적으로 생성됨 (POST로 리소스 생성 시) 400: 클라이언트의 요청이 부적절함 401: 인증 받지 않은 클라이언트가 인증이 필요한 리소스를 요청함 403: 인증 유무와 관계없이, 응답하고 싶지 않은 리소스를 클라이언트가 요청했을 때 사용 리소스의 존재를 인정하는 것이므로 403 사용을 지양하고 401, 404 사용을 권고 404: 클라이언트가 요청하는 리소스를 찾을 수 없음 405: 클라이언트가 요청한 리소스에서는 사용 불가능한 메서드를 이용함 301: 클라이언트가 요청한 리소스에 대한 URI가 변경됨 Location header에 변경된 URI 적어줄 것 500: 서버에 문제가 있음 Reference REST API 제대로 알고 사용하기 REST API 이해하기

Computer Science · 2021-05-07

3-1. 프로세스

프로세스(Process)의 개념 1. 프로세스 실행중인 프로그램을 의미한다. 2. 프로세스의 문맥(Context) 프로세스의 현재 진행 상태를 알려주는 것 time sharing, multitasking 등의 실현은 각 프로세스의 문맥을 정확히 기록해두어야 가능하다! 하드웨어 문맥 : CPU의 수행 상태를 나타냄 ex) Program Counter, 각종 register → CPU 관점에서 파악! 프로세스의 주소 공간 : 어떤 자료구조가 어떤 값을 가지고 있는지, 어떤 함수가 호출되고 return되는지 등을 파악함 ex) code, data, stack → 메모리 관점에서 파악! 프로세스 관련 커널 자료 구조 ex) PCB(Process Control Block), Kernel stack(프로세스마다 다른 커널 스택을 가지기에 개별로 상태 파악 가능) → 운영체제 관점에서 파악! (운영체제가 프로세스를 어떻게 평가하는지) 프로세스의 상태 (Process State) Running : CPU를 잡고 Instruction을 수행 중인 상태 Ready : 메모리에 올리는 것 등 다른 조건을 모두 만족하고 CPU를 기다리는 상태 Blocked (wait, sleep) : CPU를 주어도 당장 Instruction을 수행할 수 없는 상태 ex) 프로세스 자신이 요청한 event(ex. I/O)가 즉시 만족되지 않아 기다리는 상태, 프로세스 주소 공간 중 필요한 부분이 메모리에 아직 올라와 있지 않을 때 등 현대 컴퓨터에 중기 스케줄러의 등장으로 추가된 상태 Suspended (stopped) : 외부적 이유로 프로세스의 수행이 정지된 상태. 프로세스는 통째로 디스크에 swap out된다. ex) 메모리에 너무 많은 프로그램이 올라와 있을 때 (by 중기 스케줄러), 사용자가 프로그램을 일시 정지시킨 경우 Blocked : 자신이 요청한 event가 만족되면 Ready Suspended : 외부에서 resume해 주어야 Active 있을 수도 없을 수도 있는 상태 New : 프로세스가 생성 중인 상태 Terminated : 수행(Execution)이 끝난 상태 프로세스의 상태도 프로세스 상태도 - suspended 상태 추가 위의 프로세스 상태도는 운영체제의 입장에서 프로세스 상태를 명시한 것이다. 따라서, monitor mode에서도 운영체제가 running하고 있다고 말하지 않고, 사용자 프로세스가 Running 상태에 있다고 말한다. 또한, interrupt 혹은 system call을 진행 중일 때, 사용자 프로세스는 (커널모드 혹은 유저모드에서) Running 상태에 있다고 간주한다. Suspended 상태의 경우, 외부적인 이유로 메모리에서 벗어나 있는 상태로서 inactive하다고 말하고, Blocked에서 벗어났느냐 Ready에서 벗어났느냐에 따라 Suspended Blocked, Suspended Ready로 나뉜다. 또한, Suspended Blocked 상태에서 이전에 요청한 I/O 작업이나 event가 마무리되면 Suspended Blocked이 Suspended Ready로 바뀌기도 한다. 프로세스 진행과 queue 커널 주소 공간의 자료구조 Queue 위 상태도에서 나오는 하드웨어 및 CPU의 Queue들은 머릿 속에서는 모두 흩어져 있는 것으로 분류되지만, 사실은 모두 커널 주소 공간 중 Data 영역에서 queue 자료구조를 만들어 관리하는 것이다. PCB (Process Control Block) 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보 PCB의 구조 PCB의 구성 요소 (구조체로 유지) OS가 관리상 사용하는 정보 ex) Process state, Process ID, scheduling information & priority CPU 수행 관련 하드웨어 값 (프로세스 문맥 정보) ex) Program Counter, registers 메모리 관련 (프로세스 문맥 정보) ex) code, data, stack의 위치 정보 파일 관련 (프로세스 문맥 정보) ex) open file descriptors 문맥 교환 (Context Switch) CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정 문맥 교환 흐름 위 그림의 프로세스 A가 프로세스 B에게 CPU를 넘겨줄 때, 운영체제는 정확히 그 시점부터 프로세스 A가 다시 시작할 수 있게 프로세스 A의 PCB에 레지스터들의 저장된 값, Program Counter 값, 메모리 위치 정보 등을 저장한다. 새롭게 CPU를 얻게 되는 프로세스 역시 운영체제가 해당 프로그램의 PCB에서 상태를 읽어와 저장된 시점부터 다시 작업을 수행한다. 문맥 교환이 일어나는 경우와 아닌 경우 System call이나 Interrupt 발생 시 항상 문맥 교환이 일어나진 않는다. 보통은 위 그림의 (1)의 경우처럼 원래 작업 중이던 프로세스에게 다시 CPU 제어권을 넘겨 timer가 정한 시간에 도달할 때까지 작업을 수행하게 한다. 그러나 timer가 정한 시간이 다 되거나 I/O 요청으로 인해 프로세스가 blocked 상태가 되는 (2)의 경우에는 문맥 교환이 발생한다. 물론 (1)의 경우에도 커널 code를 실행하기 위해 CPU 수행 정보 등 약간의 context를 PCB에 저장해야 되지만 문맥 교환만큼 부담이 크지 않다. ex) Cache memory flush(캐시 메모리를 비우는 것)는 overhead가 큰데, 문맥 교환 시에는 이러한 캐시 메모리를 비워야 하는 반면, 단순한 커널모드와 유저모드 사이의 변환에서는 캐시 메모리를 비울 필요까지는 없다. 프로세스를 스케줄링하기 위한 큐 (Queue) Job queue : 현재 시스템 내에 있는 모든 프로세스의 집합 (Ready queue와 Device queue의 프로세스를 포함) Ready queue : 현재 메모리에 있으면서 CPU를 잡아 실행되기를 기다리는 프로세스의 집합 (혹은 줄) Device queue : I/O device의 처리를 기다리는 프로세스의 집합 (혹은 줄) 스케줄러 Long-term scheduler (장기 스케줄러 or job scheduler) 시작 프로세스 중 어떤 것에게 memory를 주고 ready queue로 보낼지 결정한다. degree of Multiprogramming(메모리에 올라가 있는 프로세스의 수)을 제어 메모리에 올라가 있는 프로그램 수가 너무 많아도 너무 적어도 안좋다. 그러나 현대의 대부분 컴퓨터의 time sharing system에서는 사용하지 않는다. (무조건 메모리에 프로세스를 올린다. = ready) Short-term scheduler (단기 스케줄러 or CPU scheduler) 어떤 프로세스에게 CPU를 주고 running 상태로 만들지 결정한다. 빠른 속도 (millisecond 단위) Medium-term scheduler (중기 스케줄러 or Swapper) 메모리 여유 공간을 마련하기 위해 메모리에 있는 프로세스를 통째로 디스크로 쫒아낸다. Long-term scheduler를 대신해 현대 컴퓨터의 degree of Multiprogramming을 제어 (프로그램은 실행 시 무조건 메모리에 올라가므로 어떤 것을 쫒아낼지가 이슈가 된다.) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-05-04

2-2. 프로그램의 실행

Computer Science · 2021-05-02

2-1. 컴퓨터 시스템 구조

Computer Science · 2021-04-25

1. 운영체제 개요

운영체제(Operating System, OS)란? 하드웨어 바로 위에 설치되어 사용자 및 소프트웨어를 하드웨어와 연결시켜주는 시스템 소프트웨어이다. 협의의 운영체제 : 보통 커널을 지칭한다. 커널은 운영체제의 핵심 부분으로 메모리에 상주한다. 전공자 입장에서 주로 이 의미로 많이 쓰인다. 광의의 운영체제 : 컴퓨터 부팅 시, 커널 및 커널과 함께 실행되는 주변 시스템 유틸리티를 모두 총칭하는 개념이다. 운영체제의 목적 1. 컴퓨터 시스템 자원의 효율적 관리 효율성 : 주어진 하드웨어 자원(CPU, 기억장치, 입출력장치 등)을 활용하여 최대한 성능을 내도록 한다. ex) 실행 중인 프로그램들에게 짧은 시간 간격으로 CPU를 번갈아 할당하거나 메모리 공간을 적절히 분배하는 것 형평성 : 특정 사용자가 차별받지 않도록 사용자 간의 형평성을 고려하여 자원을 분배한다. 소프트웨어 자원(프로세스, 파일, 메시지)을 관리하거나 사용자 및 운영체제 스스로를 보호하기도 한다. 2. 사용자에게 편리한 컴퓨터 시스템 이용 환경 제공 실제로는 하나의 컴퓨터를 이용하는 여러 사용자들이 마치 자신만의 독자적 컴퓨터에서 프로그램을 실행시키는 듯한 느낌을 받게 한다. 또한, 하드웨어를 직접 다루는 복잡한 역할을 대신해준다. 운영체제의 분류 1. 동시 작업 가능 여부 단일 작업(single tasking) : 한 번에 하나의 작업만 처리한다. ex) MS-DOS 다중 작업(multi tasking) : 동시에 두 개 이상의 작업을 처리한다. ex) UNIX, MS Windows 2. 사용자 수 단일 사용자 ex) MS-DOS, MS Windows 다중 사용자 ex) UNIX, NT server 3. 처리 방식 시분할(time sharing) 여러 작업을 수행할 때, 컴퓨터 처리 능력을 일정한 시간 단위로 분할하여 사용하는 방식이다. 우리가 주로 사용하는 현대적 범용 컴퓨터는 대부분 이 방식을 사용한다. 일괄 처리 방식에 비해 짧은 응답시간을 가지지만 사용자의 수에 따라 처리시간이 달라진다. (0.01초의 처리시간이 사람이 많아질수록 0.1초, 1초와 같이 느려진다.) 이로 인해, Interactive한 속성(컴퓨터에 무언가를 입력하면 바로 화면에 결과가 나오는 방식)을 느낄 수 있으며, 실시간 방식과 달리 처리 시간의 제약이 따로 존재하진 않는다. 실시간(Realtime OS) 정해진 Deadline에 어떠한 작업이 무조건 마무리되어야 하는 실시간 시스템을 위해 만들어진 OS이다. 따라서, 한 치의 오차도 발생해서는 안 되는 공장 제어, 미사일 제어, 반도체 공정 등 특수 목적 시스템에 많이 사용된다. · Hard realtime system(경성 실시간 시스템) : 시간을 어기면 큰 문제가 생기는 시스템 ex) 공정 파이프라인 · Soft realtime system(연성 실시간 시스템) : 약간의 시간 어김이 허용되는 시스템 ex) 영화 스트리밍 영화 스트리밍, 웹서핑 등에 사용하는 보통의 범용 컴퓨터는 시분할 방식의 OS를 사용하지만 내비게이션 앱이나 블랙박스 영상 촬영 등은 잠깐의 시간 어김도 허용되서는 안 된다. 따라서, 범용 컴퓨터의 OS가 Realtime을 요구하는 Application들을 어떻게 지원해줘야 할 지에 대한 연구도 진행되고 있다. 일괄처리(batch processing) 과거의 컴퓨터 처리 방식 중 하나로 현대에는 익숙지 않은 방식이다. 작업 요청을 일정량 모아서 한꺼번에 처리하는 방식으로 interactive하지 않다. 다음 작업을 위해서는 작업이 완전히 종료될 때까지 기다려야 하는 불편함이 있다. 요즈음의 범용 컴퓨터 OS는 다중 작업, 다중 사용자, 시분할 처리 방식의 속성을 가진다. 다중 작업 관련 용어 정리 아래의 모든 용어는 ‘컴퓨터에서 여러 작업이 동시에 수행되는 것’을 의미한다. Multitasking Multiprogramming : 여러 프로그램이 메모리에 올라가 있음을 강조한다. Time sharing : CPU의 시간을 분할하여 사용하는 것을 강조한다. Multiprocess : process는 실행 중인 프로그램을 뜻하여, 여러 개의 실행 중인 프로그램을 말한다. Multiprocessor : 하나의 컴퓨터에 여러 CPU(processor)가 붙어 있음을 뜻한다. (하드웨어적으로 강조) 운영체제의 예 1. 유닉스(UNIX) 초기의 대형 컴퓨터(서버)를 위해 만들어진 운영체제로, multitasking과 다중 사용자가 가능하다. 복잡한 어셈블리어로 유닉스를 만든 것에 한계가 있어, 보다 high level에 해당하는 C언어가 탄생했다. 코드의 대부분이 C언어로 작성된 유닉스는 덕분에 기계어 집합이 전혀 다른 컴퓨터에도 이식하는 것이 쉬워져 높은 이식성을 보였다. (C언어 코드를 단순히 컴파일하면 되었다.) 유닉스는 최소한의 핵심적인 커널 구조만 가지며 메모리를 아꼈고, 복잡한 시스템에 맞게 확장이 용이했다. 또한, ‘공개 Software 정신’의 개념 하에 소스 코드를 공개하며 수많은 유닉스 기반의 OS들을 배출했다. System Ⅴ, FreeBSD(버클리 대학교 제작), SunOS, Solaris, Linux 등의 다양한 버전이 그 예이다. 특히, Linux는 개인용 컴퓨터를 비롯해 여러 환경에서 사용 가능한 특징을 보인다. 2. Microsoft 운영체제 단일 작업, 단일 사용자를 상정하며 시작되었다. DOS(Disk Operating System) : 단일 사용자용 운영체제이며, 640KB의 적은 메모리는 한계점이다. 이러한 한계가 있는 DOS에 새로운 기능이 계속 추가되며 DOS의 코드는 복잡해지고 누더기(?)가 되었다. 그 이후, DOS 위에서 Windows를 실행시키는 것이 가능해지고 점차 Windows가 독자적인 OS로 독립하였다. MS Windows : 제작된 다중 작업이 가능한 GUI 기반 운영체제이다. 하드웨어를 연결하면 별도의 사용자 조작이나 프로그램 설치 없이 바로 사용 가능한 Plug and Play 지원(그 당시엔 혁신적이었다.), DOS용 응용 프로그램과의 호환성, 풍부한 지원 소프트웨어 등의 특징이 있다. 3. 이외에도 애플 OS(Macintosh OS→Mac OS), 소형 디바이스(Handleheld device)를 위한 OS(PalmOS, Pocket PC(WinCE), Tiny OS) 등이 존재했고, 점차 iOS 같은 스마트 디바이스(Smart device)를 위한 OS 등 여러 형태의 운영체제로 발전하였다. 운영체제의 Issue 운영체제의 구조 CPU 스케줄링 : 빠른 처리 속도를 가진 CPU지만, 작업들을 어떤 순서로 할당하는 게 가장 효율적일지 고민한다. 메모리 관리 : 한정된 메모리를 어떤 작업들에 많게 혹은 적게 배분하고 제외시킬지에 관한 주제이다. 파일 관리 : 디스크에 파일을 어떻게 보관할지에 관한 주제이다. 디스크 헤드의 효율적인 움직임을 고민한다. 입출력 관리 : 다양한 입출력 장치와 컴퓨터 간의 정보 교환을 어떻게 할지 고민한다. 입출력 장치의 느린 처리속도를 극복하기 위해 빠른 처리 속도를 가진 CPU를 순간적으로 멈추는 Interrupt도 이 주제에서 다룬다. 프로세스 관리 : 컴퓨터 소프트웨어(프로그램)들을 어떻게 관리할지에 대한 주제이다. 보호 시스템, 네트워킹, 명령어해석기(Command Line Interpreter) 등의 주제도 존재한다. 내 스스로가 운영체제가 되었다고 생각하며 공부해보자 :) Reference 운영체제, 이화여대 반효경 교수님

Computer Science · 2021-04-24

투 포인터 (Two Pointers)

Computer Science · 2021-03-08

소수 판별 알고리즘 - 에라토스테네스의 체

소수 (Prime Number) 판별 알고리즘 소수란 1보다 큰 자연수 중 1과 자기자신을 제외한 자연수로는 나누어떨어지지 않는 자연수를 말한다. 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되므로 알고리즘을 기억해두면 좋다. 다음은 기본적인 소수 판별 알고리즘을 파이썬으로 구현한 것이다. # 소수 판별 함수 정의 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x - 1)까지의 모든 수를 확인하며 for i in range(2, x): # x가 해당 수로 나누어떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is_prime_number(7)) 기본적인 소수 판별 알고리즘의 시간 복잡도는 O(N)이다. 2부터 N - 1까지의 모든 자연수에 대하여 차례차례로 연산을 수행하기 때문이다. 다만, 자연수의 범위가 10억과 같이 커진다면 연산 수행에 문제가 생기므로 시간복잡도를 개선할 필요성이 있다. 개선된 소수 판별 알고리즘 약수의 성질에서 시간 복잡도 개선의 단서를 찾을 수 있다. 어떤 한 수에 대한 모든 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다. 예를 들어, 16의 약수 1, 2, 4, 8, 16에서 2 X 8 = 16이고 8 X 2 = 16이다. 즉, 특정한 수에 대한 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 충분하다. 다음 코드는 이를 활용하여 소수 판별 알고리즘을 개선한 형태이다. # 소수 판별 함수 (2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(x ** 0.5) + 1): # x가 해당 수로 나누어 떨어진다면 if x % i == 0: return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is_prime_number(7)) 이 경우 특정 수의 제곱근까지만 확인하는 과정이므로, 시간 복잡도는 O(√N)이 된다.(루트 N) 에라토스테네스의 체 알고리즘 지금까지 특정 수에 대하여 소수를 판별하는 과정을 살펴보았다. 더 나아가 만일 특정한 수의 범위가 주어지고 그 범위안의 존재하는 모든 소수를 찾아야 한다면 어떻게 해야할까? 이 상황에서는 다수의 자연수에 대하여 소수 여부를 판별하는 대표적 알고리즘인 에라토스테네스의 체를 사용할 수 있다. 에라토스테네스의 체 알고리즘의 동작 과정은 다음과 같다. 2번 단계에서는 남은 수 중에서 아직 처리하지 않은 가장 작은 소수 i(남은 수가 결국 소수)를 찾고, 3번 단계에서 i를 제외한 그 i의 배수를 모두 제거하는 과정을 반복한다. 다음은 N=26인 상황일 때의 동작과정이다. 에라토스테네스의 체 역시 약수의 성질을 적용할 수 있다. 예를 들어, 위 경우는 26의 대략적인 제곱근인 5까지만 확인하면 된다. 6부터는 배수가 5를 넘어갈 수 없고, 이미 앞에서 소수 2, 3, 5의 배수를 제거했기 때문이다. 따라서, √N까지의 자연수만 확인해도 동일한 결과를 얻을 수 있다. 다음은 에라토스테네스의 체 알고리즘을 파이썬 코드로 구현한 것이다. n = 1000 # 2부터 1000까지의 모든 수에 대하여 소수 판별 # 처음엔 모든 수를 소수(True)인 것으로 초기화(0, 1은 제외) array = [True for i in range(n + 1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(n ** 0.5) + 1): if array[i] == True: # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j <= n: array[i * j] = False j += 1 # 모든 소수 출력 for i in range(2, n + 1): if array[i]: print(i, end=' ') 이러한 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN) 으로 선형시간에 가까울 정도로 매우 빠르므로, 다수의 소수를 찾는 문제에서 효율적이다. 다만, 각 자연수에 대한 소수 여부를 저장해야 하기 때문에 메모리가 많이 필요하다는 단점이 있다. 예를 들어, N이 10억인 경우 문제 해결이 어렵다. 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2021-03-03

기타 그래프 이론 - 최소 신장 트리 (MST, Minimum Spanning Tree)

신장 트리(Spanning Tree)란? 신장 트리(Spanning Tree)란 원본 그래프의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 뜻한다. 위의 가운데 그림처럼 간선들이 모든 노드를 잇고 있지만, 사이클은 생기지 않는 부분 그래프가 신장 트리의 예시가 된다. 반면, 오른쪽 그림처럼 모든 노드를 잇지도 않고 사이클마저 생기는 것은 신장 트리에 해당되지 않는다. 이 개념을 트리라고 부르는 이유는 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건이 트리의 조건에 해당하기 때문이다. 이러한 트리의 특성으로 인해, 신장 트리가 가지는 총 간선의 개수는 노드의 개수 - 1이 된다. 최소 신장 트리(MST, Minimum Spanning Tree) 최소 신장 트리(MST, Minimum Spanning Tree)란 최소한의 비용으로 구성되는 신장 트리를 의미한다. 최소 신장 트리의 개념은 여러 문제 상황에서 유용할 수 있는데, 만일 N개의 도시가 있고 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 하는 경우 최소 신장 트리가 사용된다. 위 그림을 예시로 보면, 3개의 도시가 있는 상황에서 모든 도시를 최소 비용으로 연결하는 방법은 오른쪽 그림과 같다. 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm)은 대표적인 최소 신장 트리 알고리즘들 중 하나이다. 그리디 알고리즘으로 분류되며 동작 과정은 다음과 같다. 요약하자면, 모든 간선을 최소 비용 순으로 하나씩 확인하여 사이클을 생성하지 않는 간선들만 최소 신장 트리에 포함시키는 것이다. 구체적인 예시로 더 살펴보자. 위와 같이 원본 그래프가 주어졌을 때, 먼저 간선을 오름차순으로 정렬하고 작업을 수행한다. 위 그림의 테이블은 가독성을 위주로 간선 정보가 나열되어 있기 때문에 혼돈하지 않도록 하자. 처음으로 가장 최소인 비용을 가지는 3, 4번 노드를 잇는 간선을 확인한다. 두 노드는 다른 집합에 속해 있어 사이클 생성이 불가능하므로 Union 함수를 호출해 같은 집합으로 만들어 최소 신장 트리에 포함한다. 다음으로 다음 최소 비용에 해당하는 4, 7번 노드를 잇는 간선을 확인한다. 두 노드 역시 다른 집합에 속해 사이클을 생성하지 않으므로, Union 함수로 최소 신장 트리에 포함한다. 다음 최소 비용에 해당하는 4, 6번 노드를 잇는 간선도 두 노드가 다른 집합에 속해 있으므로 Union 함수를 호출해 최소 신장 트리에 포함시킨다. 다음 최소 비용에 해당하는 6, 7번 노드를 잇는 간선을 확인한다. 6번과 7번 노드의 경우 같은 집합에 속해 있기 때문에, 사이클을 발생시킨다. 따라서, 최소 신장 트리에 해당 간선을 포함시키지 않고 무시한다. 다음 최소 비용인 1번과 2번 노드를 잇는 간선을 확인한다. 두 노드는 다른 집합에 속하므로 Union 함수를 호출하여 같은 집합으로 합쳐 최소 신장 트리에 포함한다. 다음 최소 비용에 해당하는 2번 6번 노드를 연결하는 간선도 서로 다른 집합에 속하므로 최소 신장트리에 포함시킨다. 다음 최소 비용에 해당하는 2번 노드와 3번 노드를 연결하는 간선은 두 노드가 같은 집합에 속하므로 무시한다. 다음 최소 비용에 해당하는 5번과 6번 노드를 잇는 간선은 두 노드가 서로 다른 집합에 속하므로, Union 함수를 호출하여 최소 신장트리에 포함시킨다. 마지막으로 1번과 5번 노드를 잇는 간선은 두 노드가 서로 같은 집합에 속해 있으므로 무시하도록 한다. 연산을 모두 수행하면 최종적으로 위와 같은 최소 신장 트리가 나온다. 이 최소 신장 트리의 모든 간선의 비용을 합하면, 해당 값이 최종 비용이 된다. 위의 과정을 파이썬 코드로 구현하면 다음과 같다. # input # 7 9 # 1 2 29 # 1 5 75 # 2 3 35 # 2 6 34 # 3 4 7 # 4 6 23 # 4 7 13 # 5 6 53 # 6 7 25 # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input().split()) parent = [0] * (v + 1) # 부모 테이블 초기화하기 # 모든 간선을 담을 리스트와 최종 비용을 담을 변수 edges = [] result = 0 # 부모 테이블에서, 부모를 자기 자신으로 초기화 for i in range(1, v + 1): parent[i] = i # 모든 간선에 대한 정보를 입력 받기 for _ in range(e): a, b, cost = map(int, input().split()) # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정 edges.append((cost, a, b)) # 간선을 비용순으로 정렬 edges.sort() # 간선을 하나씩 확인하며 for edge in edges: cost, a, b = edge # 사이클이 발생하지 않는 경우에만 집합에 포함 if find_parent(parent, a) != find_parent(parent, b): union_parent(parent, a, b) result += cost print(result) 크루스칼 알고리즘의 시간 복잡도는 Elog(E)이다. 이와 같은 시간복잡도를 가지는 이유는 크루스칼 알고리즘에서 가장 시간이 오래 걸리는 부분이 정렬을 수행하는 작업이며, E개의 간선을 정렬하기 때문이다. 내부에서 이뤄지는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작기 때문에 무시한다. 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2021-02-20

기타 그래프 이론 - 서로소 집합 (Disjoint Sets)

서로소 집합 (Disjoint Sets) 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어, {1, 2}, {3, 4}는 서로소 관계이지만, {1, 2}, {2, 3}은 2라는 공통된 원소가 존재하므로 서로소 관계가 아니다. 서로소 집합 자료구조 (Union Find 자료구조) 서로소 집합 자료구조(Union Find 자료구조)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조에는 두 가지 연산이 존재하는데, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 합집합(Union) 연산과 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 찾기(Find) 연산이 그것이다. 서로소 집합 자료구조의 동작 과정 1. 기본 동작 과정 (합치기 연산이 여러 개 주어졌을 경우) 합치기 연산이 여러 개 주어졌을 경우, 위와 같은 동작 과정을 거쳐 작업을 수행한다. 이를 구체적으로 살펴보자. 위와 같이 4개의 Union 연산이 주어졌을 상황을 가정해보자. 먼저 노드 개수만큼의 크기를 가지는 부모 노드를 표현하는 테이블을 생성하고, 테이블 내 각 노드의 부모노드를 자기자신으로 초기화한다. 테이블 생성 및 초기화가 끝나면, 첫 번째로 Union(1, 4) 연산을 처리한다. 이를 처리하기 위해 Union 연산의 인자 값으로 주어진 노드 1과 노드 4의 루트 노드를 찾는다. 여기서는 각자 자기자신이 루트 노드에 해당하므로, 1과 4 중 더 큰 번호에 해당하는 노드 4의 부모노드를 1번 노드로 설정한다. 일반적으로, 큰 번호 노드를 작은 번호 노드의 자식 노드로 설정하는 것이 관행이 있어서 이 규칙을 따라 예시를 진행하겠다. Union(1, 4) 연산이 끝나면, Union(2, 3) 연산을 진행한다. 노드 2와 노드 3에 대하여 루트 노드를 찾는데, 이번에도 자기자신이 루트 노드이고 3이 더 큰 번호 노드이므로 3번 노드의 부모 노드를 2번 노드로 설정한다. 다음으로 Union(2, 4) 연산을 위와 같은 방식으로 또 진행한다. 2번 노드의 루트 노드는 자기 자신이고, 4번 노드의 루트 노드는 1번 노드이다. 2번 노드가 1번 노드보다 큰 번호이므로, 1번 노드를 2번 노드의 부모 노드로 설정한다. 마지막으로 Union(5, 6) 연산을 똑같은 방법으로 수행한다. 각각의 노드의 루트 노드는 자기자신이고 6번 노드가 더 큰 번호이므로, 5번 노드는 6번 노드의 부모 노드로 설정된다. 이와 같은 서로소 집합 자료구조는 각 집합들간의 연결성을 통해 총 몇 개의 집합이 존재하는지를 손쉽게 확인할 수 있다는 장점이 있다. 위의 1, 2, 3, 4번 노드들은 하나의 루트 노드를 가지며 트리 구조 형태를 띈다. 이런 경우 1, 2, 3, 4번 노드들은 원소가 4개인 하나의 집합으로 파악할 수 있다. 또한 5, 6번 노드도 원소가 2개인 또 다른 집합으로서 존재한다. 결론적으로, 위 그래프에서는 총 2개의 집합(1, 2, 3, 4번 노드 집합과 5, 6번 노드 집합)이 존재하고, 그 2개의 집합은 서로소 관계를 가진다. 다만, 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다는 단점도 동시에 가지고 있다. 루트 노드를 찾기 위해서는 부모 테이블에서 해당 노드의 부모 노드를 계속 확인하며 거슬러 올라가야만 한다. 위의 과정을 파이썬 코드로 구현하면 다음과 같다. # input # 6 4 # 1 4 # 2 3 # 2 4 # 5 6 # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != x: return find_parent(parent, parent[x]) return x # 두 원소가 속한 집합을 합치기 (Union 연산) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input().split()) parent = [0] * (v + 1) # 부모 테이블 초기화하기 # 부모 테이블에서, 부모를 자기 자신으로 초기화 for i in range(1, v + 1): parent[i] = i # Union 연산을 각각 수행 for i in range(e): a, b = map(int, input().split()) union_parent(parent, a, b) # 각 원소가 속한 집합 출력하기 print('각 원소가 속한 집합: ', end='') for i in range(1, v + 1): print(find_parent(parent, i), end=' ') print() # 부모 테이블 내용 출력하기 print('부모 테이블: ', end='') for i in range(1, v + 1): print(parent[i], end=' ') 2. 기본 구현 방법의 개선 위의 기본적인 Union Find 구현 방법은 수행 시간 면에서 문제점이 있다. 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다는 점이다. 위는 최악의 경우를 가정한 예시다. 위와 같이 Union 연산이 편향적으로 수행되면, 5번 노드에 대해서 찾기(Find) 함수를 수행할 시 모든 노드를 다 확인하여 1번 노드를 루트 노드로 반환하는 비효율적인 동작을 보인다. 이 때, 시간 복잡도는 O(V)다. 따라서 Find 함수를 개선하기 위해 경로 압축(Path Compression) 기법을 사용한다. 다음은 경로 압축 기법을 구현한 파이썬 코드인데, 이는 기본적인 Find 함수에 약간의 변형만으로 구현된다. # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] 경로 압축 기법을 적용하면, 각 노드에 대하여 Find 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다. 위의 파이썬 코드를 사용하면 같은 예시에 대하여 위 그래프와 같이 모드 노드들이 자신의 루트 노드를 부모 노드로 가지는 결과를 보여준다. 시간 복잡도도 개선되는 모습을 보인다. 서로소 집합을 활용한 사이클 판별 서로소 집합은 무방향 그래프에서 사이클을 판별할 때 사용 가능하다. (방향이 있는 그래프에서는 DFS를 사용한다.) 서로소 집합을 사용한 사이클 판별 알고리즘의 과정은 다음과 같다. 이를 더 구체적으로 살펴보자. 처음에는 기존 서로소 집합 자료구조 구현과 같은 초기화 과정을 거친다. 각 노드에 대하여 부모 노드를 자기자신으로 설정한다. 그 다음, 1번 노드와 2번 노드를 연결하는 간선을 확인하여, 어떤 노드가 부모노드가 될 지 판단한다. 1번과 2번 노드의 부모 노드는 각자 자기자신이므로, 더 큰 번호에 해당하는 2번 노드의 부모 노드를 1번 노드로 설정한다. 다음은 1번 노드와 3번 노드를 잇는 간선을 확인한다. 1번 노드와 3번 노드도 각각의 부모 노드가 자기 자신이므로, 더 큰 번호에 해당하는 3번 노드의 부모 노드를 1번 노드로 설정한다. 끝으로 2번 노드와 3번 노드 사이의 간선을 확인한다. 2번 노드와 3번 노드 각각의 루트 노드는 1번 노드이므로, 이미 같은 집합에 속해 있음을 알고 사이클이 발생함을 파악할 수 있다. 서로소 집합을 사용한 사이클 판별 알고리즘의 파이썬 구현은 다음 코드와 같다. # input # 3 3 # 1 2 # 1 3 # 2 3 # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input().split()) parent = [0] * (v + 1) # 부모 테이블 초기화하기 # 부모 테이블에서, 부모를 자기 자신으로 초기화 for i in range(1, v + 1): parent[i] = i cycle = False # 사이클 발생 여부 for i in range(e): a, b = map(int, input().split()) # 사이클이 발생한 경우 종료 if find_parent(parent, a) == find_parent(parent, b): cycle = True break # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행 else: union_parent(parent, a, b) if cycle: print("사이클이 발생했습니다.") else: print("사이클이 발생하지 않았습니다.") 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2021-02-14

최단 경로 (Shortest Path) - 벨만 포드 (Bellman-Ford)

Computer Science · 2021-02-11

최단 경로 (Shortest Path) - 플로이드 워셜 (Floyd-Warshall)

Computer Science · 2021-01-04

최단 경로 (Shortest Path) - 다익스트라 (Dijkstra Algorithm)

Computer Science · 2020-12-19

다이나믹 프로그래밍 (Dynamic Programming)

Computer Science · 2020-11-27

이진 탐색

순차 탐색 일반적으로 자주 사용되는 탐색으로, 앞에서부터 데이터를 하나씩 차례대로 확인하며 리스트 안에 있는 특정 데이터를 찾는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용한다. 충분한 시간이 있다면 데이터가 아무리 많아도 항상 원하는 데이터를 찾을 수 있는 것이 장점이다. 시간 복잡도는 최악의 경우 O(N)을 보장한다. # 순차 탐색 함수 구현 def sequential_search(target, array): for i in range(len(array)): if array[i] == target: return i + 1 # 현재 위치 반환 (인덱스이므로 1을 더함) array = [4, 5, 1, 3, 2] target = 3 print(sequential_search(target, array)) 4 이진 탐색 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 순차 탐색과는 다르게 배열 내부의 데이터가 정렬된 상태여야만 사용 가능하다. 이진 탐색에는 탐색하고자하는 범위의 시작점, 끝점 그리고 중간점을 위치를 나타내는 변수로서 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다. 한 번 확인할 때마다 확인하는 원소의 개수가 대략 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 1. 재귀함수를 이용한 이진 탐색 n = 10 target = 7 array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array, target, start, mid - 1) else: return binary_search(array, target, mid + 1, end) result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1) 4 2. 반복문을 이용한 이진 탐색 n = 10 target = 7 array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: end = mid - 1 # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: start = mid + 1 return None result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1) 4 파이썬 이진 탐색 라이브러리 bisect - bisect_left(array, x): 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 왼쪽 인덱스를 반환 - bisect_right(array, x): 정렬된 순서를 유지하면서 배열 array에 x를 삽입할 가장 오른쪽 인덱스를 반환 from bisect import bisect_left, bisect_right a = [1, 2, 4, 4, 8] x = 4 print(bisect_left(a, x)) # 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 print(bisect_right(a, x)) # 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 2 4 - 값이 특정 범위에 속하는 데이터 개수 구하기 from bisect import bisect_left, bisect_right # 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 def count_by_range(a, left_value, right_value): right_index = bisect_right(a, right_value) left_index = bisect_left(a, left_value) return right_index - left_index a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9] # 값이 4인 데이터 개수 출력 print(count_by_range(a, 4, 4)) # 값이 [-1, 3] 범위에 있는 데이터 개수 출력 print(count_by_range(a, -1, 3)) 2 6 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2020-11-18

정렬 알고리즘

정렬(Sorting)이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 선택 정렬 (Selection Sort) 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 앞으로 보내는 과정을 반복하는 정렬이다. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 다음으로 작은 데이터를 골라 앞에서 두 번째 데이터와 바꾸는 과정을 끝까지 반복해 데이터를 정렬한다. 선택 정렬을 파이썬으로 구현하면 다음과 같다. # 배열의 원소를 오름차순으로 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) 선택 정렬은 다른 더 빠른 정렬 알고리즘들에 비해 비효율적인 면이 있다. 선택 정렬의 시간 복잡도는 이중 for문을 수행한다는 점에서 직관적으로 O(N²)임을 알 수 있다. 삽입 정렬 (Insertion Sort) 삽입 정렬은 특정 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘이다. 이는 특정 데이터의 앞까지 데이터들은 정렬되어 있다고 가정하고, 정렬된 데이터들 사이에서 적절한 위치를 골라 해당 데이터를 삽입하는 방식으로 진행된다. 삽입 정렬을 파이썬으로 구현하면 다음과 같다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): for j in range(i, 0, -1): if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동 array[j], array[j - 1] = array[j - 1], array[j] else: # 자신보다 작은 데이터를 만나면 그 위치에서 멈춤 break print(array) 삽입 정렬은 선택 정렬에 비해 실행 시간의 측면에서 더 효율적인 알고리즘으로 알려져 있고, 특히 데이터가 거의 정렬되어 있을 때 매우 빠르게 동작하는 특징이 있다. 삽입 정렬의 시간 복잡도는 이중 for문이 사용된 점을 보고 O(N²)임을 알 수 있지만 최선의 경우 O(N)을 가진다. 데이터가 거의 정렬되어 있는 상황이라면, 퀵정렬 알고리즘보다도 빠르게 동작한다. 퀵 정렬 (Quick Sort) 퀵정렬은 일반적으로 가장 많이 사용되는 알고리즘이자 대부분의 프로그래밍 언어 정렬 라이브러리의 근간이 되는 알고리즘이다. 기준 데이터(Pivot, 피벗)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 교환한 후, 리스트를 반으로 나누는 방식(분할)을 반복해 정렬을 진행한다. 파이썬으로 이를 구현하면 다음과 같다. 여기서 피벗을 정하는 방식은 리스트의 첫 번째 데이터를 피벗으로 정하는 호어 분할(Hoare Partition)을 바탕으로 한다. array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: # 원소가 1개면 종료 return pivot = start left = start + 1 right = end # 엇갈릴 때까지 반복 while left <= right: # 피벗보다 큰 데이터를 찾을 때까지 반복 while left <= end and array[left] <= array[pivot]: left += 1 # 피벗보다 작은 데이터를 찾을 때까지 반복 while right > start and array[right] >= array[pivot]: right -= 1 if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체 array[right], array[pivot] = array[pivot], array[right] else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 array[left], array[right] = array[right], array[left] # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 quick_sort(array, start, right - 1) quick_sort(array, right + 1, end) quick_sort(array, 0, len(array) - 1) print(array) 퀵정렬의 평균 시간 복잡도는 O(NlogN)이다. 데이터를 절반씩 분할하며 진행한다고 가정하면, 기하급수적으로 분할 횟수가 감소함을 알 수 있다. 퀵정렬은 데이터가 무작위로 입력되는 경우 빠르게 동작할 가능성이 높지만, 이미 데이터가 정렬되어 있는 경우에는 최악의 경우 O(N²)의 시간 복잡도를 가지며 느리게 동작한다. 하지만, 대부분의 정렬 라이브러리는 피벗값 설정 로직을 추가해 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장하므로 크게 신경쓰지 않아도 된다. 계수 정렬 (Count Sort) 계수 정렬 알고리즘은 특정 조건(모든 데이터가 0을 포함한 양의 정수로 표현될 수 있어야 함)에 부합해야 한다는 제약이 있지만, 조건이 갖춰지면 매우 빠르게 동작하는 정렬 알고리즘이다. 데이터의 모든 범위를 담을 수 있는 크기의 리스트를 선언해, 데이터를 직접 세어 리스트에 기록한 후 정렬한다. 그러므로 가장 큰 데이터와 가장 작은 데이터의 차이가 작을 때(1,000,000을 넘지 않을 때) 효과적으로 사용할 수 있다. # 모든 원소 값은 0보다 크거나 같음 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 원소 값이 0으로 초기화 된 모든 범위를 포함하는 리스트 생성 count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 # 리스트의 정보를 확인하여 그 값만큼 출력 반복 for i in range(len(count)): for j in range(count[i]): print(i, end=' ') 모든 데이터가 양의 정수(0을 포함한)로 표현될 수 있다면, 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N + K)의 시간 복잡도를 보장한다. 공간 복잡도 역시 O(N + K)이다. 또한, 데이터의 크기가 한정되어 있고 많이 중복되어 있을수록 유리하다. 정렬 알고리즘 비교 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2020-11-17

DFS(Depth-First Search) & BFS(Breadth-First Search)

그래프 탐색 하나의 자료구조로서 그래프(Graph)는 데이터와 데이터 사이의 관계를 잘 표현해주는 자료구조이다. 그래프는 기본적으로 데이터가 담기는 노드(Node)와 데이터 사이를 연결하는 간선(Edge)으로 이루어져있다. 노드는 정점(Vertex)이라고도 불린다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며, 간선으로 연결되어 있는 두 노드는 서로 ‘인접’해 있다고 한다. DFS (Depth-First Search, 깊이 우선 탐색) DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 먼저 최대한 깊숙이 탐색한 후, 다시 돌아와 다른 경로를 탐색한다. DFS는 스택이나 재귀함수를 활용해 구현하며, 기본 순서는 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 위와 같은 그래프를 DFS로 탐색 시, 방문 순서는 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5 이다. 파이썬으로 이를 구현하면 다음과 같다. def dfs(graph, v, visited): # 현재 노드 방문 visited[v] = True print(v, end=' ') # 현재 노드의 인접 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보 표현 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [6, 8], [1, 7] ] # 각 노드의 방문 정보 표현 visited = [False] * 9 # DFS 함수 호출 dfs(graph, 1, visited) BFS (Breadth-First Search, 너비 우선 탐색) BFS는 가까운 노드부터 탐색하는 알고리즘이다. BFS는 큐 자료구조를 활용해 구현하는 것이 일반적이며 다음과 같은 절차로 이루어진다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 위 그래프를 BFS로 탐색하면 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6 이다. 이를 파이썬으로 구현하면 다음과 같다. from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): queue = deque([start]) visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 아직 방문하지 않은 인접 노드들을 큐에 삽입하고 방문 처리 for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True # 각 노드가 연결된 정보 표현 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [6, 8], [1, 7] ] visited = [False] * 9 bfs(graph, 1, visited) Reference gimtommang11 자료구조 그래프 3. DFS & BFS 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2020-10-20

재귀 함수(Recursive Function)

자기 자신을 다시 호출하는 함수를 의미한다. 이는 어린 시절 수학 과목을 공부할 때 마주하는 프랙털(Fractal) 구조와 비슷하다. 프랙털 구조에서는 같은 모양의 도형이 무한히 반복되는 형태를 볼 수 있다. 같은 모양이 무한히 반복되는 삼각형 재귀 함수가 자기 자신을 호출하는 것도 무한히 반복되는 양상을 보인다. 따라서, 재귀 함수를 사용할 때는 항상 종료 조건을 명시해 함수의 끝을 만들어야 한다. 또한, 재귀 함수는 컴퓨터 내부 메인 메모리의 스택 공간에 적재된다. 이 말은 재귀 함수가 스택 자료구조와 내부적으로 동일함을 의미한다. 따라서, DFS와 같이 스택 자료구조를 사용해야 하는 알고리즘은 재귀 함수를 통해 간편히 구현할 수 있다. 다음은 파이썬으로 구현한 간단한 재귀 함수이다. def recursive_function(n): if n == 100: return print(n, "번째 재귀함수에서", n+1, "번째 재귀함수를 호출합니다.") recursive_function(n+1) print(n, "번째 재귀함수가 종료됩니다.") recursive_function(1) 위 재귀 함수는 100번째에 호출될 때 가장 나중에 호출되었던 함수들부터 모든 함수들이 하나씩 종료되는 스택과 같은 구조를 보인다. 본 포스팅은 ‘안경잡이 개발자’ 나동빈 님의 저서 ‘이것이 코딩테스트다’와 그 유튜브 강의를 공부하고 정리한 내용을 담고 있습니다.

Computer Science · 2020-10-19

스택(Stack)과 큐(Queue)

스택(Stack) 스택 자료구조는 상자 쌓기와 비슷하다. 차곡 차곡 아래서부터 위로 상자를 쌓아 나가면, 상자를 뺄 때는 상자들이 무너지지않게 맨 위의 가장 나중에 쌓은 상자부터 빼야 한다. 스택도 마찬가지다. 가장 나중에 들어온 데이터를 가장 먼저 빼는 후입선출(LIFO: Last In First Out) 구조를 가진다. 상자 쌓기 게임 Dropping Box 파이썬에서는 별도의 라이브러리 없이 기본 리스트 자료형으로 스택을 쉽게 구현할 수 있다. # Stack으로 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() 구현 stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() # 가장 윗 부분부터 출력 print(stack[::-1]) 큐(Queue) 큐는 우리에게 상당히 익숙한 자료구조다. 흔히 얘기하는 선착순 혹은 놀이공원 대기줄처럼 먼저 도착한 데이터가 먼저 그 대기줄을 빠져나가게 된다. 이러한 구조를 선입선출(FIFO: First In First Out) 구조라고 한다. 이러한 큐는 구조적 속성상 ‘공정한 자료구조’라고도 불린다. 흔한 놀이공원의 대기 줄.jpg 큐를 파이썬으로 구현할 때는 collections 라이브러리의 deque 자료구조가 유용하다. 리스트 자료형보다 데이터의 삽입 및 삭제가 빨라 구현이 용이하다. # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() from collections import deque queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() print(queue) # 역순으로 출력

Computer Science · 2020-10-18

Lucian Log

Contact

Computer Science

DB 설계 규칙 정리

멀티 스레드와 디자인 패턴

데이터베이스 첫걸음

MySQL 주요 명령

HTTP URI 및 Status Code 설계 방법

HTTP 헤더 종류

HTTP 기본 구조

관계형 데이터베이스 모델 개념

데이터베이스 기본 용어

데이터베이스

9-2. 가상 메모리

9-1. 가상 메모리

8-2. 메모리 관리

8-1. 메모리 관리

7. Deadlock

6-2. Process Synchronization 문제

6-1. Process Synchronization 문제

5-2. CPU 스케줄링

5-1. CPU 스케줄링

4-2. 프로세스 관리

4-1. 프로세스 생성과 종료

3-2. 스레드

REST API 이해하기

3-1. 프로세스

2-2. 프로그램의 실행

2-1. 컴퓨터 시스템 구조

1. 운영체제 개요

투 포인터 (Two Pointers)

소수 판별 알고리즘 - 에라토스테네스의 체

기타 그래프 이론 - 최소 신장 트리 (MST, Minimum Spanning Tree)

기타 그래프 이론 - 서로소 집합 (Disjoint Sets)

최단 경로 (Shortest Path) - 벨만 포드 (Bellman-Ford)

최단 경로 (Shortest Path) - 플로이드 워셜 (Floyd-Warshall)

최단 경로 (Shortest Path) - 다익스트라 (Dijkstra Algorithm)

다이나믹 프로그래밍 (Dynamic Programming)

이진 탐색

정렬 알고리즘

DFS(Depth-First Search) & BFS(Breadth-First Search)

재귀 함수(Recursive Function)

스택(Stack)과 큐(Queue)