봉황대 in CS

문제 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 행복 유치원에는 N명의 원생들이 있다. (1 ≤ N ≤ 300,000) - 30만명이 있는 유치원 ㄷㄷ 이들을 키에 대하여 오름차순으로 일렬로 세운 후 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나눠진 조 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 공유 변수의 간섭 문제를 해결하기 위한 상호 배제 및 동기화 프로그래밍 수단으로는 뮤텍스(Mutual Exclusion, Mutex)와 세마포어(Semaphore)가 있다. 뮤텍스는 자원에 대한 접근을 동기화하기 위하여 사용되는 상호 배제 기술이다. 프로그램이 시작될 때 고유한 이름으로 생성되며, 프로세스 혹은 스레드는 임계 구역에 들어가기 전에 반드시 뮤텍스 lock을 얻어야 하고, 임계 구역을 빠져나올 때 반환해야 한다. 뮤텍스를 소프트웨어적으로 구현하는 방법과 하드웨어적으로 구현하는 방법에 대하여 알아보자..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 협력적 프로세스의 주요 이슈 : 결정성 / 상호 배제와 동기화 / 교착 상태 / 기아 프로세스 비간섭 관계 프로세스 시스템에서 두 개의 프로세스가 있을 때 1. 한 프로세스가 다른 프로세스를 선행하거나 (이 경우에는 간섭이 발생할 가능성이 없음) 2. 이들이 서로 독립적일 경우 한 프로세스의 출력 장소가 다른 프로세스의 입력 장소나 출력 장소가 아니면 이들은 비간섭 관계에 있다고 정의한다. 두 프로세스가 독립적이라는 것은 두 프로세스 사이에 선행 제약 관계가 없다는 것이다. 만약 두 프로세스가 독립적이지 않고,..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 협력적 프로세스(Cooperating Process)가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에 어떤 문제가 일어나는가? * 협력적 프로세스 : 시스템 내에서 실행 주인 다른 프로세스의 실행에 영향을 주거나 받는 프로세스 생산자-소비자 문제를 다시 보자. * 생산자 프로세스 : 정보를 생산하는 프로세스 * 소비자 프로세스 : 생산자 프로세스가 생산한 정보를 소비하는 프로세스 생산자와 소비자 프로세스들이 병행으로 실행되도록 하기 위해서 공유하는 메모리 영역에 원형 공유 버퍼를 생성..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 실시간 시스템 (Real-Time System) 실시간 시스템에서는 작업 수행이 요청되었을 때 이를 제한된 시간 안에 처리하여 결과를 내주어야 한다. 이는 연성 실시간 시스템과 경성 실시간 시스템으로 분류할 수 있다. 1. 연성 실시간 시스템 (Soft Real-Time System) 실시간 프로세스가 실시간이 아닌 프로세스들에 우선권을 가진다는 것만 보장하며, 이것이 스케줄 되는 시점에 관해서는 아무런 보장이 없다. (마감 시간(deadline)을 만족하는 것이 확률로만 존재) 2. 경성 실시간 시스템 (Ha..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 지금까지는 단일 처리기 시스템(처리기(CPU)가 하나 있는 시스템)에서의 CPU 스케줄링에 대하여 알아보았다. 한 시스템 내에서 여러 개의 CPU가 사용 가능하다면 어떤 것들이 변화되며, 어떤 문제들이 추가적으로 발생할까? 다중 처리기 스케줄링 (Multiple-Processor Scheduling) 다중 처리기에서는 부하 공유(load sharing)가 가능해진다. * 부하 공유 : 쉬고 있는 처리기에 할 일을 부여하는 것. 한 처리기는 계속 일하고 나머지는 놀고 있는 상태가 되어서는 안 된다. 하지만 이에 ..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 스레드를 지원하는 운영체제에서는 프로세스를 스케줄 하는 것이 아니라, 실질적으로는 스레드를 스케줄 한다. 하지만 "프로세스 스케줄링"과 "스레드 스케줄링"의 용어는 상호 교환적으로 사용된다. 따라서 해당 책에서는 일반적인 스케줄링 개념을 설명할 경우 "프로세스 스케줄링"을 사용하고, 스레드에 국한된 개념을 가리키는 경우에는 "스레드 스케줄링"이라는 용어를 사용하고 있다. 스레드 스케줄링 앞서 스레드의 2가지 형태, 사용자 스레드와 커널 스레드에 대하여 알아보았다. 1. 사용자 스레드 : 응용 프로그램 내의 라이..

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다. 선점(preemption) 선점은 현재 실행 중인 프로세스로부터 CPU를 회수하여 다른 프로세스에게 할당하는 것을 말한다. 시분할 시스템에서 타임 슬라이스 소진 시 우선순위가 더 높은 프로세스에게 CPU를 할당하는 것으로 일어난다. 동적 우선순위 프로세스의 실행 중에는 시스템의 성능, 프로세스의 특성 등을 고려하여 우선순위를 재조정하게 되고 결과적으로 스케줄링에 의해 선점이 발생한다. 전체적인 시스템 성능의 향상 및 프로세스의 속성을 고려하여 커널의 여러 곳에서 우선순위를 조정하는 원칙과 기법이 필요하다. 동적..