CS

큐를 나누고, CPU는 어느 큐를 먼저 고를지, 그리고 그 큐에서 어떤 프로세스를 먼저 고를지 스케줄링 CPU 사용시간이 적은 프로세스에 RR보다 더 큰 우선순위 부여 기타 상황에서의 CPU 스케줄링 Real-Time Scheduling Hard real-time systems: Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 Soft real-tme computing: Soft real-time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 스케줄링 Thread Scheduling Local scheduling: user level thread는 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정 Global scheduling:..

CPU burst: 프로세스 실행 과정 중 CPU의 제어권을 얻어 연속적으로 인스트럭션을 실행하는 단계 I/O burst: CPU 제어권을 잃고 I/O를 실행하는 단계 CPU bound job: 계산 위주의 job (few very long CPU bursts) I/O bound job: CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job (many short CPU bursts) 중요 용어: nonpreemtive(비선점형), preemtive(선점형) 시스템 입장에서: CPU utilization, Throughput 프로그램 입장에서: Turnaround time, Waiting time, Response time 선점형 스케줄링에서 대기 시간은 여러번 있을 수 있지만 응답 시간은 ..

최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다 743. network delay time - 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인 heapq 모듈에는 우선순위 업데이트 기능 없음 이전 노드의 값이 무엇인지 필요없으므로 생략 787. cheapest flights within k stops - 다익스트라 알고리..

프로세스 생성: 부모 프로세스가 자식 프로세스 생성 -> 트리(계층 구조) 형성 프로세스는 자원을 필요로 함 (OS로부터 or 부모와 공유) 자원의 공유 Copy-on-write(COW): write하기 전까지는 부모와 자원을 공유하다가 이후 copy write하게 되면 본래의 내용이 바뀌게 됨 부모와 자식이 모든 자원을 공유하는 모델 일부를 공유하는 모델 전혀 공유하지 않는 모델 수행(execution) 부모 자식이 공존하며 수행되는 모델 자식이 종료될 때까지 부모가 기다리는 모델 주소 공간 자식은 부모의 공간 복사 (binary and OS data) 자식은 그 공간에 새로운 프로그램을 올림 유닉스의 예 fork() 시스템 콜이 새로운 프로세스 생성 이후 exec() 시스템 콜을 통해 새로운 프로그램..

그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기) 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로 해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제) 해밀턴 순환: 원래의 출발점으로 돌아오는 경로 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화 그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임 DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로..

Thread (lightweight process): CPU의 수행 단위 thread의 구성: program counter, register set, stack space (CPU 수행 관련 정보) thread끼리 공유하는 부분(=task): code section, data section, OS resources heavyweight process: 하나의 thread 다중 스레드로 구성되면 하나의 서버 스레드가 blocked 상태여도 다른 스레드가 실행되어 빠른 처리 가능 동일한 일을 수행하는 다중 스레드가 협력하여 높은 처리율과 성능 향상 동일한 일을 수행하는 프로세스를 여러개 실행하면 메모리 낭비가 심함 스레드 생성, CPU switching이 프로세스 생성, context switching보다 ..

프로세스: 실행중인 프로그램 프로세스의 맥락(context) CPU 수행 상태를 나타내는 하드웨어: Program counter, 각종 레지스터 PC가 어떤 코드를 가리키는가, 레지스터에 어떤 정보를 담고 있는가 프로세스의 주소 공간: code, data, stack 프로세스 관련 커널 자료 구조: PCB(Process Control Block), kernel stack 프로세스가 실행 될 때마다 각각 별도로 PCB를 data에 두고 관리 A의 코드 실행 중에 함수 호출이 일어나면 본인의 스택에 그 함수를 호출하고 리턴 후 관련 정보 쌓음 A 본인이 스스로 할 수 없는 것을 OS에 요청하면(시스템콜) 그와 관련되어 실행되는 커널에서의 코드가 함수를 호출하면 A의 커널 스택에 개별적으로 쌓고 관리 프로세스..

동기식 입출력: I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감 구현 방법 1 입출력이 끝날 때까지 CPU 낭비 -> 매 시점 하나의 입출력만 일어날 수 있음 구현 방법 2 입출력 완료까지 해당 프로그램에게서 CPU 빼앗음 입출력 처리를 기다리는 줄에 그 프로그램을 줄 세움 다른 프로그램에게 CPU를 줌 비동기식 입출력: I/O 시작 후 입출력 작업이 끝나기 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감 두 경우 모두 I/O의 완료는 인터럽트로 알려줌 서로 다른 입출력 명령어 메모리에 접근하는 인스트럭션, I/O 수행 인스트럭션 따로 Memory Mapped I/O: 메모리에 접근하듯이 I/O 수행 저장장치 계층 구조 윗 계층일수록 빠르며, 가격이 높아 용량이 적다 pr..

CPU: 매 클럭마다 메모리에서 인스트럭션(기계어)을 차례로 읽어 실행하는 작업 반복 레지스터: 메모리보다 빠른 작은 정보 저장 공간 다음 인스트럭션의 주소를 담고 있음 mode bit: 실행중인 프로세스가 OS인지 사용자 프로그램인지 구분해준다 1 (사용자 모드): 사용자 프로그램 수행 -> 제한된 인스트럭션만 수행 가능 (보안) 0 (모니터 모드): OS 코드 수행 (=커널모드) -> I/O 관련된 인스트럭션까지 모두 수행 가능 interrupt line: CPU는 매 인스트럭션을 읽기 전에 interrupt line이 세팅되어 interrupt될 사항이 있는지 체크한다 CPU에 인터럽트가 걸리면 실행중인 프로그램에서 OS로 CPU 제어권이 넘어간다 프로그램 실행 중에 I/O 장치의 관여가 필요하다면..

운영체제: 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 좁은 의미(커널): 운영체제의 핵심 부분으로 메모리에 상주하는 부분 넓은 의미: 커널 뿐 아니라 각종 주변 시스템 유틸리티(ex. 파일 복사 프로그램)를 포함한 개념 운영체제의 목적 컴퓨터 시스템의 자원(하드웨어 + 소프트웨어)을 효율적으로 관리 (효율성 + 형평성) & 사용자/운영체제 보호 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공 동시 사용자/프로그램들이 각각 독자적인 컴퓨터에서 수행되는 것 같은 경험 제공 하드웨어를 직접 다루는 복잡한 부분 대행 운영체제의 분류 동시 작업 가능 여부 단일 작업(single tasking) 예)MS-DOS 다중 작업(multi tasking) ..