개구리의 개발 블로그 개구리의 개발 블로그

1. 임계 구역 문제 프로세스 동기화는 임계 구역 문제로부터 시작한다. 각 프로세스는 임계 구역이라고 부르는 코드 부분을 포함하고 있다. 임계 구역은 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있는 코드 영역이다. 즉 임계 구역은 경쟁 상태가 발생할 수 있는 곳이다. 임계 구역 문제 해결을 위한 조건 상호 배제(mutual exclusion) : 프로세스가 자신의 임계 구역에서 실행된다면, 다른 프로세스들은 자신의 임계 구역에서 실행될 수 없다. 진행(progress) : 다른 프로세스가 임계 구역에서 실행 중이지 않다면 프로세스는 임계 구역에서 실행될 수 있다. 한정된 대기(bounded waiting) : 프로세스가 자기의 임계 구역에 진입하려는 요청을 한 뒤부터 그 요청이 허용될 때까지 ..

1. O(n²) 정렬 1.1 선택 정렬 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택 1번째 인덱스부터 배열을 탐색하여 1번째로 작은 값을 1번째에 위치 → 2번째 인덱스부터 탐색 & 2번째에 위치 → 3번째부터 탐색 & 3번째에 위치 → … → 총 (n-1)번 반복 추가 공간 없이 주어진 배열에서 위치만 변경한다. O(1)의 공간 복잡도 시간 복잡도 1번째 루프에서 비교 : n-1 2번째 루프에서 비교 : n-2 (n-1)+(n-2)+…+1 = n(n-1)/2 최선, 최악, 평군 모두 O(n²) def selection_sort(L): for i in range(N): #해당 위치 i에 들어갈 원소를 선택 minVal_idx = i for j in range(i+1,N): if L[j] < ..

0. 들어가기 전에… TCP가 제공하는 신뢰적인 데이터 전달 서비스는 무엇일까? TCP는 프로세스가 자신의 수신 버퍼로부터 읽은 데이터 스트림이 손상되지 않았으며 손실이나 중복이 없다는 것과 순서가 유지된다는 것을 보장한다. 즉, 수신자가 받은 바이트 스트림은 송신자가 전송한 것과 같은 바이트 스트림이다. 어떻게 이러한 서비스를 제공하는 것일까? 1. 트랜프스포트 계층 서비스 1.0 트랜스포트 계층과 애플리케이션 계층 트랜스포트 계층 프로토콜은 서로 다른 호스트에서 동작하는 애플리케이션 프로세스들 간의 논리적인 통신을 제공한다. 즉, 애플리케이션의 관점에서 프로세스들이 동작하는 호스트들이 직접 연결된 것처럼 보이도록 한다. 트랜스포트 계층 프로토콜은 네트워크 라우터가 아닌 종단 시스템에서 구현된다. 애플..

1. 네트워크 애플리케이션 1.1 프로세스 간 통신 네트워크 애플리케이션이 통신할 때 실제 통신하는 것은 프로그램이 아닌 프로세스다. 같은 종단 시스템에서 실행되는 프로세스들의 통신은 운영체제에서 자세하게 다루는 내용이다. 서로 다른 종단 시스템에서 프로세스들은 네트워크를 통해 메시지를 교환한다. 클라이언트와 서버 네트워크 애플리케이션은 네트워크에서 서로 메시지를 보내는 두 프로세스로 구성된다. (ex. 웹 애플리케이션에서 클라이언트 브라우저 프로세스는 웹 서버 프로세스와 메시지를 교환한다. P2P 파일 공유 시스템에서 한 피어의 프로세스에서 다른 피어의 프로세스로 파일을 전송한다.) 네트워크를 통해 통신하는 프로세스는 클라이언트 프로세스와 서버 프로세스 중 하나로 이름 짓는다. 소켓 프로세스가 집이라면..

가장 기본적인 자료구조인 스택과 큐를 python 코드를 이용해 구현해보겠습니다. Stack 후입선출 특성의 자료구조(Last In First Out) 1. 배열을 이용한 구현 스택을 위한 배열 선언(최대 크기 설정) / index = 0 index가 선언한 배열의 크기 이상이면 stack 꽉 찬 상태 / index = 0 이면 비어있는 상태 push() : index 자리에 값 추가, index+=1 pop() : index에 위치한 값 리턴, index-=1 모든 연산의 시간 복잡도 : O(1) class arrayStack: def __init__(self): self.array = [] #maxSize 설정. self.top = -1 def isEmpty(self): if self.top==-1:..

0. 들어가기 전에 경쟁 상태 : 여러 프로세스가 공유 자원에 접근할 수 있는 상태 임계 구역 : 경쟁 상태가 발생할 수 있는 코드 영역 동기화 : 임계 구역을 보호하고 이를 통해 경쟁 상태를 방지하는 것 1. 경쟁 상태란? 여러 개의 프로세스가 동일한 자료에 접근하여 조작할 때, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황. 경쟁 상태로부터 보호하기 위해 한 순간에 하나의 프로세스만이 변수를 조작하도록 보장해야 한다. 이를 위해 동기화가 필요하다. 2. 경쟁 상태 발생 케이스 프로세스는 자신의 데이터로 일을 수행한다. 기본적으로 프로세스간에는 메모리를 공유하지 않기 때문에 운영체제를 사용해서 일을 수행하는 경우 경쟁 상태가 발생하게 된다. 2.1 프로세스 A가 커널 모드 수행 중 conte..

0. 들어가기 전에 종단 시스템에서 다른 종단 시스템으로 데이터를 보내려고 한다. 송신 종단 시스템은 데이터를 세그먼트로 나눈다. 세그먼트에 헤더를 붙여 패킷을 구성한다. 패킷이 네트워크를 통해 목적지 종단 시스템에 도착하고 다시 조립된다. 패킷 교환기(스위치)는 링크에 도착하는 패킷을 받아 전달한다. 패킷 스위치의 종류에는 라우터와 링크 계층 스위치가 있다. 종단 시스템과 패킷 스위치는 다양한 프로토콜을 수행하는데 TCP, IP는 인터넷에서 가장 중요한 프로토콜이다. 소켓 인터페이스는 인터넷에 접속된 종단 시스템들은 한 종단 시스템에서 수행되는 프로그램이 다른 종단 시스템에서 수행되는 목적지 프로그램에게 데이터를 전달하는 규칙이다. 1. 패킷 교환 송신 종단 시스템에서 목적지 종단 시스템으로 메세지를 ..

1. Process Concept 초기의 컴퓨터는 작업(job)을 실행하는 시스템이었다. 이어서 사용자 프로그램(user program) 혹은 태스크(task)를 실행하는 시분할 시스템(time-sharing)이 뒤를 이었다. 1.1 Process 비공식적으로 프로세스란 실행 중인 프로그램이다. 프로세스의 현재 활동 상태는 프로그램 카운터 값과 프로세서 레지스터의 내용으로 표현한다. 프로세스의 메모리 배치는 일반적으로 여러 섹션으로 구분된다. Text section - 실행 코드 (excutable code) Data section - 전역 변수 (global variables) Heap section - 프로그램 실행 중에 동적으로 할당되는 메모리( memory that is dynamically al..