본문 바로가기

Computer Science

 (28)
[운영체제] CPU 스케줄링 | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. CPU 프로그램의 기계어 명령을 수행하는 컴퓨터 내 중앙 처리 장치 CPU 스케줄링 Ready Queue에 있는 프로세스 중 CPU를 줄 프로세스를 고르는 것. 운영체제 코드인 CPU 스케줄러에 의해 수행된다. CPU 스케줄링의 필요성 사용자 프로그램은 CPU 작업과 I/O 작업의 반복으로 이루어진다. CPU Burst: 사용자 프로그램이 CPU를 가지고 빠른 명령을 수행하는 작업. I/O Burst: I/O 요청이 발생한 후 커널을 통해 입출력을 수행하는 비교적 느린 작업. 프로세스는 이런 특성에 따라 두 가지로 나눌 수 있다. CPU-bound process: I/O 요청이 거의 발생하지 않아 CPU 버스트가 길게 나타나는 프로세스. I/O-bound pr..
📌유니온 파인드(Union-Find)를 알아보자 (이코테 WITH 파이썬) 어젯밤 알고리즘 스터디 모의 코테 중 못 푼 문제가 있는데 검색해보니 유니온 파인드로 푼다고 했다. 유니온 파인드가 뭔지 알아보고 못 풀었던 백준 문제도 풀어보겠다😇 유니온 파인드 우선 서로소 집합(Disjoint Sets)에 대해 알아야 한다. 서로소 집합은 공통 원소가 없는 두 집합을 말한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 데이터를 처리하기 위한 자료구조이며, union과 find 연산으로 조작할 수 있기 때문에 유니온 파인드 자료구조라 불리기도 한다. union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find: 특정 원소가 어느 집합에 포함되어있는지 찾는 연산 유니온 파인드 알고리즘은 서로소 집합을 표현하기 위한 알고리즘이다. 이를 통해 각 집합이 어떤 원..
[운영체제] 프로세스 관리(2) | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. Thread lightweight process. 프로세스의 실행 단위라고도 할 수 있다. 같은 프로그램을 여러 개 실행했을 때 각각의 프로세스를 만드는 것은 비효율적이다. 스레드를 사용하면 프로세스 내의 주소 공간(코드, 데이터)이나 자원을 공유할 수 있다. 스레드 ID, 프로그램 카운터, 레지스트 집합, 스택으로 구성된다. 하나의 프로세스 내에서 스레드간 자원을 공유하고, 자원의 생성과 관리의 중복성을 최소화해서 수행 능력을 향상시키는 것을 멀티 스레드라고 한다. 응답 속도가 빠르고, 자원을 공유하기 때문에 경제적이고, 다중 CPU 구조에서 각각의 스레드를 병렬처리 할 수 있다는 장점이 있다. 단, 스레드 간 자원을 공유하기 때문에 값을 정확히 읽고 쓰기 ..
[운영체제] 프로세스 관리(1) | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. 프로그램의 실행 프로그램이 실행될 때 각각의 프로그램은 독자적인 주소 공간인 가상 메모리를 가진다. 이는 코드, 데이터, 스택 영역으로 구성된다. 운영체제의 커널도 하나의 프로그램이기 때문에 코드, 스택, 데이터 영역을 가진다. 프로세스 프로세스란 실행 중인 프로그램을 말한다. 프로세스 문맥 (Process Context) 시분할 시스템 환경에서는 타이머 인터럽트에 의해 CPU 관리가 이루어진다. 따라서 CPU를 뺏겼다가 다시 얻었을 때 이전에 어디까지 명령을 수행했는지 정보가 필요하다. 이를 프로세스 문맥이라고 한다. 프로세스 문맥은 다음과 같이 구분할 수 있다. 1. 하드웨어 문맥: Program Counter 등 각종 레지스터에 저장된 값 2. 프로세스의..
[운영체제] 컴퓨터 시스템의 구조 | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. 운영체제 컴퓨터 하드웨어 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층. 좁게는 운영체제의 핵심 부분으로 메모리에 상주하는 커널을, 넓게는 커널 뿐만 아니라 각종 시스템 유틸리티를 의미한다. 운영체제의 분류 운영체제는 동시 작업 가능 여부, 사용자의 수, 처리 방식으로 나눌 수 있다. 동시 작업 가능 여부 1. 단일 작업: 한 번에 하나의 작업만 처리한다. 예) 과거 MS-DOS 프롬프트상의 명령어 수행 2. 다중 작업: 동시에 두 개 이상의 작업을 처리한다. 사용자의 수 1. 단일 사용자: 예) MS-DOS, MS Windows 등 2. 다중 사용자: 한 대의 컴퓨터에 여러 사용자가 접속. 예) Unix 등 처리 방식 1..
📌다익스트라 최단 경로 알고리즘 (이코테 WITH 파이썬) 이번달 코딩테스트 중에서 이거 딱 다익스트라인데 하면서 못 푼 문제가 있었다. 끝나고 후기를 찾아보니 정말 다익스트라로 풀 수 있는 문제여서 아쉬웠던 기억이 있다. 이참에 다익스트라 알고리즘을 복습해보자. 최단 경로 알고리즘 말 그대로 가장 짧은 경로를 찾는 알고리즘. 그래프를 이용해 표현하며 각 지점은 노드로, 지점간의 연결은 간선으로 표현한다. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프의 여러개의 노드가 있을 때 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단경로를 구하는 알고리즘이다. 과정은 다음과 같다. 출발 노드 설정 > 최단 거리 테이블 초기화 > 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 > 해당 노드에서 부터 다른 노드로 가는 거리를 계산한 후 테이블 갱신 > 반..
[운영체제] 운영체제 개요 | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. 운영체제 컴퓨터 하드웨어 바로 위에 설치. 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어. 운영체제의 목적 1. 하드웨어 자원(CPU, 메모리)을 효율적으로 관리 2. 응용프로그램 및 사용자에게 편리한 인터페이스 제공 운영체제의 기능 CPU 스케줄링 : CPU 큐에서 기다리는 프로그램 중 어떤 프로그램에게 먼저 CPU 사용권을 줄까? 1. FCFS (First Come First Served) 먼저 온 프로그램 순서대로. 📌단점: CPU를 길게 쓰는 프로그램이 먼저 도착한다면 전체 프로그램의 대기 시간이 늘어난다. 2. SJF (Shortest Job First) CPU를 짧게 쓰는 프로그램 먼저 사용. 📌단점: Starvation(기아 현상..
자료 구조 | 스택, 큐, 딕셔너리 간단하지만 많이 쓰이는 데이터 구조 세 가지를 살펴보자. 학습 목표 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있다. 큐 큐(Queue)는 값이 아래로 쌓이는 구조다. 값을 넣고 뺄 때 선입 선출(FIFO, First in first out) 방식을 따른다. 배열이나 연결 리스트를 통해 구현할 수 있다. 스택 스택(Stack)은 값이 위로 쌓이는 구조다. 값을 넣고 뺄 때 후입 선출(LIFO, last in first out) 방식을 따른다. 배열이나 연결 리스트를 통해 구현할 수 있다. 딕셔너리 딕셔너리(Dictionary)는 키(Key)와 값(Value)이라는 요소로 이루어져 있다(쌍으로 이루어짐). 키에 해당하는 값을 저장하고 읽어오는 방식이다. 일반적으로 해시 테이블과 동일한 개념이라 할 수..

티스토리툴바