Computer Science30 [OS] 메모리 관리(2) - 페이징 연속 메모리 할당 외부 단편화 문제 프로세스는 메모리의 연속된 공간에 존재해야한다. 그런데 이런 연속 메모리 할당(Contiguous Memory Allocation)은 외부 단편화(external fragmentation) 문제를 낳는다. 외부 단편화란, 메모리의 빈 공간이 불연속적으로 흩어져있어서 빈 공간을 합한 크기가 하나의 프로세스를 할당하기 충분한 크기임에도 프로세스를 할당하지 못하는 것이다. 그림으로 살펴보면 다음과 같다. 메모리에 프로세스 A, B, C가 올라와있다. 아무것도 할당되지 않은 빈 공간을 hole이라고 한다. B가 모든 작업을 마치고 메모리에서 내려간다. 메모리에는 총 1000의 빈 공간이 있지만 그림처럼 500, 500으로 나뉘어있다. 그래서 새로운 프로세스 D는 600의 공간.. 2021. 8. 8. [OS] 메모리 관리(1) - 동적 로딩,연결,스와핑 CPU 스케줄링과 더불어 OS의 중요한 업무 하나가 바로 메모리 관리(Memory Management)이다. 기술의 발전과 더불어 메모리의 용량이 빠르게 증가했지만 그 발전 속도만큼 메모리 사용량도 빠르게 증가했기 때문에 메모리를 얼마나 효율적으로 사용하는가는 컴퓨터 발전 역사에 있어서 항상 중요한 문제였다. 메모리를 효과적으로 사용하기 위한 방법에 대해 OS는 두 가지 측면에서 접근한다. 메모리 낭비 없애기 가상 메모리(Virtual Memory) 메모리 낭비 없애기 OS가 낭비되는 메모리를 줄이기 위해 어떤 방법을 이용하는지 알아보기 전에 우선 프로그램이 메모리에 적재되는 과정을 살펴보자. 프로그램이 메모리에 올라가는 과정 우선 메모리는 다음과 같이 주소(address)와 데이터(data)로 구성된다.. 2021. 8. 8. [그래프] 다익스트라 알고리즘 (Dijkstra algorithm) 다익스트라 알고리즘 에지에 가중치가 있는 그래프(weighted graph)에서 최단 경로를 찾는 알고리즘 에지의 가중치가 양수일때만 사용 가능하다. 시작 노드 S로부터 다른 모든 노드까지의 최단 경로를 찾는다. 기본 원리 필요한 자료구조 노드 사이의 관계를 표현할 그래프: graph 시작 노드로부터 각 정점까지의 거리를 기록할 배열: distance 최단 경로가 확정된 노드를 꺼내올 최소힙: min_heap 우선 시작 노드를 제외한 모든 노드의 비용을 가장 큰 값(이를테면, 무한대)으로 초기화한다. 시작 노드를 최소힙에 넣는다. 최소힙에서 노드를 꺼낸 후 인접한 노드를 확인한다. 이때, 인접한 노드로 이동하는 비용(현재까지의 비용+이동하는데 드는 비용)이 해당 노드에 기록되어있는 값보다 작다면? 값을 .. 2021. 7. 27. [정렬] 퀵정렬 (Quick Sort) 앞에서 살펴본 선택 정렬, 삽입 정렬, 버블 정렬은 모두 구현은 간단하지만 느린 정렬 알고리즘이었다. 이번 글에서 살펴볼 퀵 정렬은 가장 많이 쓰이는 정렬 알고리즘이며 분할과 정복을 기반으로 하는 알고리즘이다. 평균적인 시간 복잡도는 O(NlogN)이다. 기본 아이디어 우선 배열 안에서 임의의 요소를 고른다. 이 요소를 피벗(pivot)이라고 부른다. 설명을 위해 중간에 위치한 원소를 피벗으로 잡았지만, 아무 원소나 잡아도 상관없다. 이 피벗을 선택하는 방법에도 여러 알고리즘이 있다. 가장 왼쪽의 요소를 피벗으로 삼는 방법도 있고, 랜덤으로 선택하는 방법도 있고, 또 가장 오른쪽의 요소를 피벗으로 삼는 방법도 있는데, 최종적인 성능은 모두 비슷하다. 피벗을 잡았으면, 배열을 순회하면서 피벗보다 작은 쪽과.. 2021. 7. 27. [HTTP] REST API REST API가 무엇인지 알아본다. 비바 리퍼블리카 이응준 개발자님이 Naver DEVIEW에서 강연하신 내용을 듣고 요약했으며, 일부 예제는 김영한님의 HTTP 강의를 참고했다. 해당 자료에 대한 링크는 포스트 하단에 명시했다. REST API란 무엇인가 REST(REpresentational State Transfer)는 로이 필딩(Roy Fielding)이 '어떻게하면 웹을 망가뜨리지 않으면서 HTTP를 개선할 수 있을까'에 대한 고민을 하며 제안한 "분산 하이퍼미디어 시스템(ex.웹)을 위한 아키텍쳐 스타일"이다. 2000년에 자신의 박사 논문 에서 REST를 처음으로 제안하였다. 즉 REST API란 이 REST 아키텍쳐 스타일을 따르는 API를 말한다. 아키텍쳐 스타일은 제약 조건의 집합이다.. 2021. 7. 8. [HTTP] HTTP 상태코드 HTTP 상태코드란 클라이언트가 보낸 요청의 처리 상태를 응답에서 알려주기 위해 정의한 기능이다. 즉 클라이언트는 HTTP 상태코드를 보고 내가 보낸 요청이 어떻게 처리되었는지 알 수 있다. 따라서 서버는 요청 결과에 알맞은 상태코드를 보내줘야한다. 대략적인 의미 1xx (Informational): 요청이 수신되어 처리중 (거의 사용하지 않음) 2xx (Successful): 요청 정상 처리 3xx (Redirection): 요청을 완료하려면 추가 행동이 필요 4xx (Client Error): 클라이언트 오류, 잘못된 요청으로 서버가 요청을 수행할 수 없음 5xx (Server Error): 서버 오류, 올바른 요청이나 서버 문제로 요청을 처리할 수 없음 클라이언트가 인식할 수 없는 상태코드를 서버가.. 2021. 7. 8. 이전 1 2 3 4 5 다음